《关于象棋的不败算法》由会员分享，可在线阅读，更多相关《关于象棋的不败算法（4页珍藏版）》请在金锄头文库上搜索。
1、第? ?卷第?期? ?年?月华中理工大学学报? ? ? ?乙? ? ? 关于象棋的不败算法黄文奇宋恩民陈亮王权利?计算机 科学与工程系?摘要给出了数学方 法,根据它可以写 出算法,依此算法,在高速大容量 电子计算机的帮助下,象 棋?中国象棋或国际象棋?棋手与任何人或机器下两盘?一盘先着子,一盘后着子?后,按总成绩计 皆不输?关健词象棋?算法?可计算性?人工智能分类号? ? ?定义中国象棋?,?双方共? ?个棋子,矩形棋盘的宽和长分别为?和?,其上共? ?十? ? ? ?一?个格点,每个子在任一时刻可能是处在棋盘的某一格点上或在棋盘之外,因此,所可能处的不同位置 的个数不超过? ?定义 ?在某一
2、时刻,说一个格局被决定了,是指全部? ?个棋子中的每一个都被决定了一个位置,并且现 在是应该由?走还是由?走也被决定了?显然,不同的格局的总个数不超过? ?”?定义?可将每一格局称作平面上的结点,将现在该 由?走 的结点称作?类结点,该由?走的结点称作?类结点?将表示 一盘棋赛开始前夕的结点称作始结点,若?先走 则称之为?类始结点,若?先则称之为?类始结点?定义?对于任一结点?和任一结点?,如果存在一个合法的动作,它能将?演变为?,则称?为?的子结点,或称?为?的父结点?结点?为?的子结点记为?一? ?显然,任一结点的子结点的个数皆有限?定义 ?称结点?是一终结点,是指应该作动作的一方已没有任
3、何合法的动作可作了,也不必要作任何动作了,因为此时这一方已经失败了或者胜利了,按规则竞赛在此刻终止?对于终结点?,设该走的一方是?,若此时?已失败了,则称它为?一类终结点?若?已胜利了则称它为?类终结点?对?一类与?十类终结点的定义 由对称的涵 义给出?一类终结点的特征是?方的将帅处于棋盘之外位置,或者他的棋子个个都已被憋死?对于?类终结点,其特征是?和?双方的将帅处 于直接对面的局势?收稿日期? ?一?一?黄文奇,男,? ?年生,教授?武汉,华中理工大学计算机科学与工程系? ? !? ?,国家 自然科学基金资助重点项目? ? ?华中理工大学学报? ? 年?算法通过以下五个步骤四个定理对棋手的
4、算法进行描述?步骤?将全 部不 同的结点都画在平面的不 同位置上?对于其中的每一结点?和每一结点?,如果?是?的子结点,则 画一自?向?的箭头?步骤?对 于每 一个终结点都按 其棋局涵义,在其上标上 记号?一或?一或?十或?一下 面紧接着的三个步 骤是分批地逐渐将一切 现在尚未标上记号的结点都标上记号?步骤?对每一个尚未标上记号 的?类结点,若其全部子结点中至少有一个在过 去的步骤中已标上 了记号?一,则将此结点标上记 号?若其全部子结点都在过去的步骤中已标上了记号?,则将此结点标上记号?一对每一尚未 标上记号的?类结 点,若其全部子结点中至少有 一个在 过去 的步 骤 中已标上了记 号?一,
5、则将此结点标上 记号?十?若其全部子结点都在过 去的步骤中已标上 了记号?十,则将此结点标上记号?一对于在 步骤?中首步 被标上记 号 的任一结 点?,若?上被标上的记 号 为?,则 显然,从此格局?出发,棋赛往下 进行,经过?有穷步?实 际上 是一步?的努力,?一定能取胜?若?上 被标上 的 记号 为?一,则 显 然,从此 格局?出发,棋赛往 下 进行,经?有穷步?实 际上是。步?的努力,?一定能 取胜?对 于被标上了记号?或?一的结点?有对称的结果?步骤?转至步骤?,再 对一批尚未被标上记 号的结点标上 记号?或?一或?十或?一,若已没有尚未被标上记号的结点 能被新标上记号则标记 的过程暂
6、时终止?因为结点 的总个数有限,所以这种标记的过程一定会 进行到暂时终止 的时候?步骤?将所有目前还未被标上记号 的?类结点标上记号?“,?类结点标上 记号 ? ?至此,平面 上的全部结点都被标上 了记 号?十或?一或?或?一或?“或?“?定理?若?类始结点 上被标上 的记 号是?,则在 开局?先走 的情形,?经 过有穷步的努力一 定能取胜?一?尸 ?一? 一, 、 、?尸户一?十?卞、?十一一一? ?, 、?一?十?十?一角、?”?一?一终结点 节?一?一?一?十终 结 点图?以?一为始结点的演变过程证明参见 图?根据在结点上杨衬己号的过程,开始时?能选 择一 个动作将标有记号?的始结点演变
7、成一个在早期步骤 被标上了记 号?一的结点?而 在达到这个 结点后,根据标记号?一的标记 规则,?无论作何动 作都必然将 这 个结点 演变成一 个在 早期步骤被标上了记号?的结点?即,随棋局进行,在结点逐渐演变的过程中,其上的记号只可能取到?与?一,且依次按序 列?,?一,?卜,?一,交 替 出现,不可以取到其 它符号?一,?十,?“,? ?等?由于标记号的全过程是在有穷步骤?时 间?里完成,所以序列?,?一,?一,?一,不会延续至无穷,只能是个有穷序列?即,以上棋局进行的过程是有限的,最后 一定会达到终格局,其上标上 的记号 为?一或?,即?经过有穷步 的努力取 得 了胜利?定理?若?类始结
8、点上被标上 的记号 是?一,则在 开局?先 走的情形,?经过有穷步 的努力一定 能取胜?若?类始结点上被 标上 的记号 是?一,则 在?先走的情形,?经过 有穷步 的第?期黄文奇 等?关于象棋 的不败算法努力一 定能取胜?证明仿定理?的证明?推理?自被标上了记号?或?一的格局出发,?经过有穷步的努力一定能取胜?自被标上 了记号?”或?一的 格局出发,?经过有 穷步 的努力一定能取 胜?证明仿定理?的证 明?定理?若?类始结 点上被标上的记号是?“ ,则在开局?先走的情形,?可经过努力保证 自己不会被击败?证明参见 图?,根据记 号?的标记规 则,对 这个被标上了记号?“的始结点,在其全 部的子
9、结点 中不可能有被标上 记 号?一者?否 则始结点上的 记 号 应 为?十?,这 些子结点 亦 不 可 能?”卜?八?、。一户尸?。?十? 口产一入?“、二九穷一夕尹尸 ”、 ?刃,?、二图三以?“为始钾汽的演变过程全部都被标上 了记 号?十?否则 始 结点 上 的记 号 应 为?一?因此 这 些子结点 上 的 记 号的分布为?至少有一个 ? ?,有?个或有穷个?因此 开局时?可选到 一个动作将结点演变成一个被 标上了记号 ? ?的结点?接着该?走,若?不慎,将结点演变成了一 个被标上了?的接点,则由推论?可知往下?可通过自己的努力在有穷步 内取胜?若?时时谨慎,永远将结点演变成一个被标上 了
10、?“的结点,则 只要?也类似地 时时谨慎,这盘棋最终成为和 局?定 理?若?类始结点上被标上 的记号 是?“,则在开 局?先走 的情形?可经过努力,保证自己不会被击败?证明仿定理?的证明?定理?存在着 一个 完 整 的中国象棋着 子法,它 能保证棋手按它的指示与任何人或机 器下两盘棋?一盘先着子,一盘后着 子?后按总成绩 皆不输?证明以上五个步骤中所制成的计算图,结合以上四个定理的证明过程,事实上已给予了?方一个完整 的下棋着子法?即算法?,它能保证,若?与?下两盘棋,一次先下,一次后 下,则按总成绩?不 会输?因为,若?类始结点上被标上的记号是?,则 当?先下时,按定理?,?一定会胜?若?类
11、始结点上 被标 上的记号是?一,则 由对称性知?类始结点上 被标 上 的记号是?一,于是按定理?,知当?后下时一定能取胜?若?类始结点上被标上 的记号是?“,则由对称性知?类始结点 上被标上的 记号也是? ?,因此由定理?和 定理?知,在?先下 的一盘和在?后下 的一盘,?都能 争取到 不败的结局?结语命题关于中国象棋的定义?定义?,步骤?步骤?,定理?定理?,都可类比地转移到 国际象棋中去,从而对于 国际象棋存在着类比于定 理?的定理,即存在着不败算法?证明略?华中理工大学学报? 年由于所述算法 在执行中所涉及 的空 间与时间皆为有限?定理?的证明过程中所示的无穷序列?。? ?。一? ?一无
12、穷?只是想象 中的,实际上是不存在 的?因此在存储量充分大、速度充分高的计算机的帮助下,象棋棋手利用这个算法与任何人下棋确实皆能保持不败的记录?根据墨子的 矛盾律,对于任何棋都不存在常胜算法,因此我们所得出的算法,在可计算性的意义上已是最好的算法?当然,由于现 实物 质技术条件的 限制,直到距目前若干年以内的将来,这种高指标的计算机还 不可能被制造 出来?因此本文所述算法在目前不具有直接的实战价值?但是,对于这种算法的存在性,以及对这 种存在性的证明的 具体技术,哲学家和爱好下棋的学者多半会有点兴趣?本文 的意义还在于从可计算性的角度证明了对于像棋的不败博奕策略的客观存在,从而为有悠 久历 史
13、的博奕论中的相应 问题? ? ?提供了答案?谨以此文献给王浩先生和程民德先生?参考文献? !?# ? !%a lgorithm;eo mputa bility;artifieia linte l li geneeHuangWenqi, pro f. ; Dept. o fCo mputer Sei.邑Eng.,H.U.5.T.,Wu han430074,China月心冲匆联神K 侧令玲仓玲令玲仓甲翻联幻任川冷玲令玲令玲令片毛之玲令登淤 令玲称玲令玲令玲令玲份冲匆洲铆只川隐玲令玲仓甲翻枉冲K国家人事部领导到我校检查博士后工作3月22日,国家人事部 专家司司长、全 国博后管 委会办公室 主任庄毅、湖北省人事厅副厅长蔡国启到 我校检 查博士后 的工作情况.校 长杨叔子等陪同客人们参观 了图书馆、电子与通讯博后 站、机械工程博后站、金属材料及热处理博士点、塑性成形模拟与模具技术实验 室、数控中心、CAD中心、引力中心等.庄毅司长对我校的博士后工作情况表 示满意.
