首页 > 代码库 > 针对明棋类游戏的策梅洛定理的每个人都能读懂的证明过程(下象棋、围棋、国际象棋等的必胜下法求解)
针对明棋类游戏的策梅洛定理的每个人都能读懂的证明过程(下象棋、围棋、国际象棋等的必胜下法求解)
网上流传的博弈论策梅洛定理的中文证明资料,其证明都不是那么容易理解读懂。因此这里描述一下我的通俗一点的证明。
策梅洛定理:在有限步数内一定会结束的已经明确规则的明棋类游戏中(例如中国象棋、国际象棋),对于特定的任一局面,设A先下,B后下,那么要么A有必胜下法,要么B有必胜下法,要么A、B都有必和下法。
证明用的是归纳法。
把相邻的A走一步棋、B走一步棋的下法组合作为本证明中的一回合走法。证明对于有限n回合的棋类游戏局面(正规开局也算是一种局面),要么A有必胜下法(1),要么B有必胜下法(2),要么A、B都有必和下法(3)。对于确定的局面,可以得知必然的、确切的结论。
第一步证明:
先证明只有1回合的游戏,A知道那个回合下棋法可以得到胜W、败L,平(Tie)。如果回合走法选择中有W,A必选W;如果回合走法选择中没W但有T,A必选T。如果所有回合走法选择都是L,那么A只能失败。
例如下图中的子游戏1的情形
再证明2个回合的游戏,A也是知道所有W, L, T情形的,A会选择对自己有利的下法。例如下图中的子游戏3的情形。
推而广之,对于n-1个回合内结束的游戏,A都能明智的选择有利下法。对于n亦然。证毕。
注一:可以无限着法的棋类是不适用这个原理的,但是实际上比赛时的中国象棋、国际象棋都有若限定步内不吃子就是和局(或起类似作用)的规定,所以中国象棋、国际象棋的每一个对局都是在有限步内就一定会结束的游戏)
注二:这个证明和网上流传的不同之处,好像那些傻子证明人都不会下棋似的,没有把A, B相邻步合并成回合,只有合并成回合了,就变成了每次都是A先下,每次都是A先选择,从而每个正常人都能轻松读明白这个证明。
注三:那么这个证明对于B必胜的局面也是有效的,就是B的棋艺太高超了,每次B落子都能导致A的选择都只有败的情形。要记住,一个回合里面A下一招,B也下一招,这个可能性是有的。
注四:有一些特殊回合,可能A下一招,B已经判输,B就不用下了。例如中国象棋中的A把B的老将吃了,B就不用动作,这是一种A胜的回合下法。这种也是回合。避免有的人抬杠说回合的定义模糊。
注五:简单的游戏(包括井字棋、成三棋、中国象棋残局排局、小棋盘(例如7x7)的五子棋这类)很容易用计算机求得最佳走法,但是,对于正规完整开局的象棋类的这种难道大的游戏,计算机没有办法求的最优解的,因为计算机的计算能力、存储空间有限,而那些经典棋类的局面可能性要比宇宙的原子总数都要多的多。
注六:策梅洛定理只证明了一定有最优下法,但无助于如何找到具体的最优解法。
针对明棋类游戏的策梅洛定理的每个人都能读懂的证明过程(下象棋、围棋、国际象棋等的必胜下法求解)