人智导PA3实验报告

notes › iAi

四子棋实验报告

郭高旭 ggx21@mails.tsinghua.edu.cn 2021010803

最终版本的对抗结果

胜率稳定在93%以上。

实验方法

实现了α-β剪枝算法。

原理

α-β剪枝算法是基于max-min算法实现的。与蒙特卡洛对棋局随机模拟不同，max-min算法需要对棋局进行形势判断,由此给出max-min决策树上每一点的分值.

所以max-min算法的成功率不仅取决于计算量,也取决于形势判断函数的精度.

α-β剪枝的作用是:对方已经有了更好的选择，不需要再继续搜索，因为对方会选择让我方分数最小的点.

所以整个α-β剪枝算法相比于蒙特卡洛而言更加类似于人类棋手的思维模式:

  1. 拓展决策树到目的深度(实际上是dfs的过程)

  2. 给出叶子结点的形势判断

  3. 上层的opponent选择对当前层player最不利的下法(返回分值)

  4. 其中进行a-b剪枝,如果祖父层的player发现下过某一步后,opponent给出了比祖父player目前最优选择的结果更差的一步,祖父player不需要知道自己走的这一步究竟多差,放弃选择这一步.

具体实现

max-min算法

原理1-3部分实际上就是算法的基本实现过程，其中player（我）是max结点，会选择对我最有利的局面；opponent是min结点，会选择对我最不利的结点。

α-β剪枝

  • player结点：更新alpha = max(alpha, temp_score);如果发现alpha超过了父opponent结点已知的分分数上界beta,由于opponent一定不会选择下这一步,故放弃搜索

  • opponent结点：更新beta = min(beta, temp_score);如果发现beta小于了父player结点已知的分分数下界alpha,由于player一定不会选择下这一步,故放弃搜索

形势判断

  • 最naive的版本是，遍历每一个空点，计算这个点八个方向能够连成的最大长度。給（1，2，3，4）分别一个分数例如（1，10，100，1000）最终这个点的得分是player的长度分-opponent的长度分。整个盘面的形势分就是所有点的得分之和。

  • 这样可以简单地看到，如果对手有更多马上能够连成4个的点，那么局面对我不利，否则对我有利。

  • 这样的形势判断大概能获得50+%的得分

补丁

如果发现自己能连成4个子，则直接落子。

接下来，如果发现对手能连成四个子，则堵住。

创新部分

本次实验完全自己完成，所以尝试了各种正常的不正常的创新方法提升我的胜率。

但是对于α-β剪枝来说，若想提升胜率，我尝试引入一些专家知识，所以我学习了四子棋的一些基本下法

四子棋小知识

  • 迫手：类似于五子棋连成4个子，如果四子棋下一步可以连成四个子，则称形成了迫手（逼迫对手一定要走这里）

    • 无效迫手：如果有player在棋盘较底部形成迫手，则其上的opponent迫手实际上是无效迫手，因为opponent若想获得迫手，必须要填满其下的格子，但是player已经获胜了
    • 双迫手，如果player形成双迫手，则opponent无论堵哪个，都可以获胜。

  • 劣招：容易发现，如果ai实力相当的话，实际上最后胜利总是有一方下满棋盘所有可能的位置后，不得不走在敌方迫手的下一格，导致对手下到自己的迫手而获胜。我们把这种被迫失败的招数称为劣招

    • 安全运转：如果棋盘剩下的列剩下的格子均为偶数，则后手方可以通过安全运转的方式控制先手方只能获得奇数格.这是7-6棋盘四子棋先手必胜的重要原因

    • 奇偶迫手:根据上面的内容可以简单地推出下面的结论,如果局面仅剩的最后两列，白棋和黑棋在分别在不同列有且仅有一个迫手，且不会形成更多的迫手。
      1、白奇黑偶，那么白胜。
      2、白偶黑偶，那么黑胜。
      3、白偶黑奇，那么平。
      4、白奇黑奇，那么平。

      其中黑棋表示后手方.奇/偶表示在某一列的从下往上数的奇/偶行存在迫手

  • 追胜:这里引入五子棋的概念.可以通过一系列的迫手,让对手不停被迫落子,直到自己获得双迫手,或者对手被迫落子后自己连成四子.

学习过上面的四子棋小知识后引入我的创新尝试.

计算(可能的)长度

  • 希望如果这个点和周围自己的棋子之间即使有空位,比如[黑][白][-][+][白][黑] 这时[+]应该记为3而不是2

  • 希望给出可能的长度,如果某一方向不可能形成4个字,返回-1比如[黑][白][+][白][黑] [+]不可能横向成4子横向长度记为-1

  • 实现方案:

    • 采取窗口滑动来计算某一点的大小,用一个长度为4的窗口在包含[+]的四个方向滑动,如果中间有禁入点或者对手棋子,则这个窗口长度记为0,最后找到含有最多本方棋子的窗口.

新的形势判断函数

  • naive的修改:不再对全局的点进行判断,而只是选择那些对局面有影响的点.具体来说只判断该点下面三个位置有棋子的点(只是为了减小计算量)

  • 如果这个局面轮到某一player,且这个player可以连成4个,则返回无限大INT-MAX或者intmin,这方便剪枝,并且是合理的,因为无论能形成多少迫手,价值都不会比取得胜利大.

  • 无效迫手:考虑到四子棋小知识中的无效迫手环节.如果棋盘底部有player的迫手,则迫手上方opponent的分数除以10(价值降低)

新的问题

  1. 不知道双迫手,常常被对手形成两个迫手而输掉

  2. 赢了开浪,判断自己要获胜后(得分为’INT-max’)不会选择最简明的取胜方法,而是认为自己下哪里都能赢.可是由于我不能保证我的算法永远work,常常浪输比赛

  3. 输了开摆,当判断自己无论走哪里都会输时(无论走哪里得分都是int-min),不会挣扎

因此我引入了更多专家知识,比如追胜

如果我落子时,判断对方可以通过追胜的方法取得胜利,则禁止下到这一点.

如果我落子时,发现自己可以通过追胜取得胜利,则直接追胜.

追胜的实现

简单来说就是递归地模拟落子

  1. 遍历棋盘上所有可能的落子点

  2. 如果可以取得胜利，返回胜利

  3. 否则如果可以形成迫手,则落子

    • 如果对手能直接取得胜利,不考虑这个落子点
    • 否则对手必然要堵住我的迫手,继续模拟落子,直到胜利/不能形成新的迫手

上面的过程看似会递归爆炸,其实几乎是一本道(棋类术语,大意为只能这么下)的,所以实际上开销很低

对于追胜来说还有更多的边界条件,写在我的代码注释里.

在每次模拟落子时，首先检测自己是否能够追胜，这样大大提高了剪枝效率

经过实验我发现,仅仅使用追胜判断+形势判断(如果能追胜就追胜,如果对手追胜则禁止,其余情况下使得自己局面分数最高的点)已经可以实现70%的胜率

补丁

对于输了开摆,我采取的方式是,降低搜索深度,选择比较低深度下最佳的点,这样ai不知道自己要输,就会认真下.

如果还是输,则继续降低深度,

(如果看一眼就知道走哪都要输了,那就开摆吧…随机下一个)

时间控制

首版本的α-β剪枝用时几乎都在500ms以内，虽然能够达到90%左右胜率，但是我难以控制搜索深度，深度为6（每人走三步）.时经常超时,深度为5,则用时太少,而且由于我使用了递归,棋盘大小对我用时的影响非常大

所以最终采取的方案是,初始深度限制为7(一个较大的数)如果到了50%的time-limit,则深度限制减一,80%的limit,继续减一.95%的limit,不再继续搜索,直接返回形势判断值.

但是这样其实也有问题,就是前面几列搜索深度较深,后面较浅,不平衡.

开局落子可能性多,中局落子可能性少,因而每步用时基本是下降趋势,但有时中局的决策更加重要

内存控制

我的算法根本不需要额外内存开销（完全是在同一个棋盘上模拟），所以根本不需要控制内存。感觉很吃亏，但也没有想到好方法用上内存

致谢与实验感想

本次实验代码完全是自己完成，没有参考任何往年代码。

四子棋的知识来源于百度贴吧的分享【图片】屏风式四子棋获胜诀窍（先手必胜？）！【新棋吧】_百度贴吧 (baidu.com)

  • 算法实际上有相当多的妥协,如果在每一步想要更多精度,就会损失搜索深度

  • 我本来想引入更多专家知识,但是胜率越来越低.一方面我不能保证我的代码正确性,另一方面如果我已经下不过ai,我教他下棋只会越教越菜.

  • 但是蒙特卡洛根本没这么多事情,它不需要形势判断,而且可以控制计算时间.我真的后悔为什么要写α-β剪枝(为什么要推荐我写)

  • 我认为本实验最大的创新点是引入了追胜的概念，它确实有效，但是耗费了我大量时间考虑边界条件和debug。最终版本的追胜算法实际上是在我改了很多版之后改回了较为原始的版本。一方面，胜利的判断是很难的，比如加入认为自己一列上有连续两个迫手则宣称获胜，很可能对手在另一列通过追胜直接获胜；另一方面，追胜导致了更为激进的剪枝，这很容易使得ai对形势出现误判；再者，认为自己获胜或失败非常容易导致赢了开浪,输了开摆的结果,所以最终我限制了追胜的搜索深度.



本文总阅读量次