五子棋计算思路

时间:2023-01-08 19:12:04

    五子棋分为有禁手和无禁手,有禁手就是在无禁手的规则的基础上加上禁手规则,具体是规则不讲了。所以就人机对战来讲,从无禁手来做,比较好做。这里只讲无禁手的情况。无禁手就是只要能连成5个子,或者5个子以上,就算赢。
    而计算机博弈要解决的问题,抽象地讲只有一个问题“下一步怎么走”,对五子棋来讲,就是下一步在哪个点落子。
一般的思路在 棋类人机对战的一般原理 - BillySir - 博客园  已经有说。下面重点讲五子棋特有的算法思路。

下一步怎么走,总体思路:
    1.如果下一步能赢,就走这一步
    2.如果下一步会输,就阻止对方赢
    3.计算机得分决定在哪里落子。
其中 阻止对方赢,就是在对方能赢的点上落子,一般会有1到3个点。
前面2点比较好理解,重点是第3点,计算得分。
得分的思维很普遍,就是棋盘上每个空位置,算出一个分,所有空位置的分中,哪个点(位置)得分最高就落子在那个点。

每个点的分数怎么算?
    扫描棋盘上所有空位置(没有白子也没有黑子的点),计算每一点的得分。
每一点的得分受到8个方向的影响,图形上就是一个“米”字。这个点就是米字的中心点。把同一线上的2个方向看作1个方向,即是4个方向的影响。就是扫描4个方向,看看这个点如果落子会构成什么(对自己一方而言)
如果是5,当然就是赢了,得分最高
从得分最高到最低的顺序是:
     五(或者五以上)> 活四 > 冲四 > 活三 > 冲三 > 活二 > 冲二 > 活一 > 冲一
(ps.活四活三经常有听说,活二冲一这些也不知道棋坛有没有这种说法,不过不影响我们对软件的编写。)
扫描出一个方向上的情况,对应上面的9种情况之一。查得分表,得到分数。得分表是上面的每种情况给一个固定的数字作为分数。4个方向的得分加起来,当作总分。

这还只是落子对自己一方而言的情况,就是攻的得分。
落子也会给对方造成阻碍,所以落子除了有“攻”的作用之外,还有“防”的作用。
但是攻就是自己先手(肯定是轮到自己的时候计算机才思考如何下),防来讲就是后手(我方走一步后轮到对方走,对对方而言,算后手),同样一种情况,先手得分与后手得分是不一样的。于是得分表就有3列:情况、先手得分、后手得分。

总结一下,对于棋盘上一个空点,它的得分来自8个数字相加,其中4个是4个方向的攻分,另4个是4个方向的防分。

同一种情况,攻分大于防分,所以特殊情况下,双方都是冲四活四的情况,自然是先完成自己的五,而不是先堵住对方的四。

  • 搜索

前面讲的是一次扫描,得到每个点的分数,挑最高分的点落子。但我们知道,五子棋,要赢,往往是最后几步连着下的,比如先成【冲四活三】,然后再走几步才能赢。而如果发现对方准备【冲四活三】就要赶快阻止,而不是等到【活四】再堵,那样已经来不及了。所以,需要在内存中演练接下来的几步,双方可能怎么走。这就是搜索。

回到刚才的情况,计算机在思考这一步应该在哪个点落子,我们挑出最高分的几个点(可以设高于冲三的才算,也可以设最高的X个点,比如8个点),假设我方下了其中一个点(这算第1步),那么下一步就轮到对方下子了,对方也是一样的思维,从对方的角度,计算机出每个点的得分,挑最高分的几个点试(这算第2步),然后又轮到我方下子,思维和算法是一样的。这么就可以搜索好几步。这样,情况就分支为很多情况,成为一棵树。由于每一步都在试几种不同的走法,所以最终还是要从几种走法中确定一种对自己(相对而言)最有利的走法。每一步都是这样。这个叫最大原理。如果作为旁观者,始终站在一方进行评价,就是最大最小化原理。

由于不可能一直搜索到有胜负出现,所以搜索到一定的步数后就要停止往下搜,于是要判断当前局面对自己有利的程度,于是需要一个算法评定一个静态的局面的得分。简单的可以以局面上所有点的得分总和当作局面的得分(考虑攻防的情况)

每一步都选择对自己(相对而言)最有利的情况,于是回到第1步的几种情况,肯定选那种对自己最有利的情况来落子,这个点就不一定是一开始得分最高的那个点了。这种搜索比直接选得分最高的点落子,棋力更高。

整个思维就是这样,至此已经解决了“在哪里下子”这个问题,也是唯一的一个计算的目标。

但是,实际问题冒出来了。

  • 优化

由于搜索这棵树有很多的叶子和分支,每一个叶子要计算局面得分,在计算一次性得分,局面得分,都是计算量很大,再加上树的分支,把这种计算机量放大了很多倍,于是搜索变得很慢。总不能让人机对战的人每次等电脑走一步要等很久吧,比如3分钟,1分钟,如果是你,受得了?所以,人机对战往往花大量精力在优化搜索。前面讲的,挑出几个最高的分作尝试,而不是每一步对所有空位置都尝试,也是一种有效的优化。

剪枝就是剪掉一些分支,从而减少计算机量。如何剪掉分支,而不影响计算机的结果,或影响小到忽略就是值得深入研究。而AlphaBeta剪枝法就是在【最大最小值搜索】中,可以剪掉一些分支,而不影响计算机结果的一种优化算法。

  • Alpha-Beta剪枝

五子棋计算思路

Alpha剪枝

补充一点,棋类的搜索一般是深度优先,也有在深度优先的基础上,再组合深度优先,一步一步加深的。本质上还是深度优先。

如上图,从5,8,4中得到最小值4,然后到了A节点,A的2个孩子已经有结果了,6和2。由于2已经比它的伯伯4小了,所以,不管2的弟弟B节点大小如何,A的值肯定不会大于2,而最高一层是要取最大数(注意左边的MAX和MIN),既然A最大值不会超过2,所以,不再搜索A的第3个孩子B节点以及后面的孩子。
同理,A的弟弟(C节点)的第1个孩子已经是3(比4小),也剪掉。

五子棋计算思路

Beta剪枝,与Alpha刚好相反。如上图,既然2和9的伯伯是7,而2和9之间最大是9,所以2和9的父亲A节点,至少是9,而上层是要取小,肯定取7,所以不用计算9的弟弟(B节点)们的得分。

alpha-beta剪枝搜索 - IThinktan - 博客园  

  • 分数盘的更新优化

    棋盘上每个空点都有一个分数,整个棋盘就是一张2维的分数盘,显然在一个子落子的前后,这个分数盘会变化,但变化范围是有限的,只需要重新计算可能受到影响的点的分数,就可在原有分数表的基础上产生新的分数盘,而不必每个空点都重新计算。而每个点落子后影响范围也是以这个点为中心的“米”字范围。所以只需要重新计算这个米字上的空点即可。


五子棋算法,我基本讲完了。

 

还有一些做法更贴近棋原理的算法,比如空步。我们人算的时候为了简单,假设对方不走,自己能怎样进行。空步可以用来提高局面估值的正确性。

死点进行标记,下次不再搜索。比如脚部,有些棋型永远不能成5,永远成不了5的点不搜索!

 

感谢 为你欢喜为你忧(QQ: 35994468) 为本文提供了多处补充。