资源描述：
《关于象棋的不败算法 (2).pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第卷第期华中理工大学学报年月乙关于象棋的不败算法’黄文奇宋恩民陈亮王权利计算机科学与工程系,根据它可,,摘要给出了数学方法以写出算法依此算法在高速大容量电子计算机的帮助,,,下象棋中国象棋或国际象棋棋手与任何人或机器下两盘一盘先着子一盘后着子后按总成绩计皆不输关健词象棋算法可计算性人工智能分类号定义,,,中国象棋双方共个棋子矩形棋盘的宽和长分别为和其上共十
2、,,,一个格点每个子在任一时刻可能是处在棋盘的某一格点上或在棋盘之外因此所可能处的不同位置的个数不超过,,定义在某一时刻说一个格局被决定了是指全部个棋子中的每一个都被决定了一个位置,并且现在是应该由走还是由走也被决定了显然,不同的格局的总个数不超过”,,定义可将每一格局称作平面上的结点将现在该由走的结点称作类结点该由走的结点称作类结点将表示一盘棋赛开始前夕的结点称作始结点,若先走则称之为类始结点,若先则称之为类始结点,,,定义对于任一结点和任
3、一结点如果存在一个合法的动作它能将演变为则称为的子结点,或称为的父结点结点为的子结点记为一显然,任一结点的子结点的个数皆有限,,定义称结点是一终结点是指应该作动作的一方已没有任何合法的动作可作了也不必要作任何动作了,因为此时这一方已经失败了或者胜利了,按规则竞赛在此刻终止,,,设该走的一方是已则称它为一已对于终结点若此时失败了类终结点若胜利了则称它为一十类终结点对类与类终结点的定义由对称的涵义给出一,类终结点的特征是方的将帅处于棋盘之外位置或者
4、他的棋子个个都已被憋死对,于类终结点其特征是和双方的将帅处于直接对面的局势收稿日期一一·,,,,黄文奇男年生教授武汉华中理工大学计算机科学与工程系!,国家自然科学基金资助重点项目华中理工大学学报年算法通过以下五个步骤四个定理对棋手的算法进行描述步骤将全部不同的结点都画在平面的不同位置上对于其中的每一结点和每一结点,如果是的子结点,则画一自向的箭头,一一十步骤对于每一个终结点都按其棋局涵义在其上标上记号或或
5、或一下面紧接着的三个步骤是分批地逐渐将一切现在尚未标上记号的结点都标上记号,步骤对每一个尚未标上记号的类结点若其全部子结点中至少有一个在过去的步骤一,中已标上了记号则将此结点标上记号若其全部子结点都在过去的步骤中已标上,了记号则将此结点标上记号一对每一尚未标上记号的,类结点若其全部子结点中至少有一个在过去的步骤中已标上一,十十,了记号则将此结点标上记号若其全部子结点都在过去的步骤中已标上了记号则将此结点标上记号一,‘,,对于在步骤中首步被标上记号的任一结点若上被标上
6、的记号为则显然从,,,此格局出发棋赛往下进行经过有穷步实际上是一步的努力一定能取胜若,,,,上被标上的记号为一则显然从此格局出发棋赛往下进行经有穷步实际上是。步的努力,一定能取胜一对于被标上了记号或的结点有对称的结果,一十一,步骤转至步骤再对一批尚未被标上记号的结点标上记号或或或若已没有尚未被标上记号的结点能被新标上记号则标记的过程暂时终止因为结点的总个数有限,所以这种标记的过程一定会进行到暂时终止的时候“,步骤将所有目前还未被标上记号的类结
7、点标上记号类结点标上记号至此,十或一一““平面上的全部结点都被标上了记号或或或或定理若类始结点上被标上的记号是,则在开局先走的情形,经过有穷步的努力一定能取胜十一户一十尸尸终结点一一卞一一十一一一,、、—、、十一—,、、角—、”节、一—一一十一终结点图一以为始结点的演变过程,证明参见图根据在结点上杨衬己号的过程开始时能选择一个动作将标有记号的始结点演变成一个在早期步骤被标上了记号一的结点而在达到这个结
8、点后,根据标记号一,的标记规则无论作何动作都必然将这个结点演变成一个在早期步骤被标上了记号,,,一,的结点即随棋局进行在结点逐渐演变的过程中其上的记号只可能取到与且依次,,卜,,,,,一一一十“,按序列⋯交替出现不可以取到其它符号等,,一,一,一,由于标记号的全过程是在有穷步骤时间里完成所以序列⋯不会延续至无穷,只能是个有穷序列即,以上棋局进行的过程是有限的,
