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