三棋先手必胜证明

发布时间:2024年01月13日

目录

创作原因

游戏规则

初始状态图

证明过程

先手必胜的证明

失败的博弈树(三个多小时的成果)


创作原因

这个棋不是网上流行的成三棋,我也不知道这个棋叫什么。由于这个棋是(横竖斜)连成三个就获胜,所以我暂时给它起名叫三棋。至于为什么写这个博客,一是因为这个棋简单,是我见过的第二简单的棋,第一简单的是区字棋,二是这是我小时候赶大集时跟别人学的棋,现在想想也是一个美好的回忆,所以就暂时记录下来,代码实现后面有时间再写。

游戏规则

1、初始状态:棋盘为三乘三的棋盘,双方各三个棋子,分别摆在靠近棋手的一行上。

2、双方交替行子,每次棋子只能上下左右移动一个单位。

3、直至一方棋子连成三个获胜,横竖斜都算,不过不能是自己的初始状态。

初始状态图

XXX
OOO

证明过程

本来我还是想用区字棋的证明方法来证明这个问题,但算了算状态数目,感觉虽然很少,但只是相对于计算机而言,人力列举真的很困难。

状态数eq?C_9%5E3*C_6%5E3%3D84*20%3D1680,即便排除大量等效,状态数也在一百以上。但我代码能力很差,而且也没有学过博弈论相关知识,不知道该怎么解决这类问题。我想既然画状态图不现实,那我可不可以画博弈树呢?但需要代码。而且循环状态怎么解决,我还是不会。所以代码实现这个问题博弈树就算是我挖下的坑吧。

当时在高铁上无聊,就开始手搓博弈树。画了三个多小时,没有结果,状态越花越多,还要检验与之前的状态有没有重复。最后我放弃了,问我旁边的学长。学长说挺简单的,但不要手搓(大哭)。他了解了之后,想了想,说,我根据后手策略,认为这个棋永远和棋,因为可以阻碍对方连成三。先手策略他还没研究。这点倒是提醒了我,为什么不从棋手的角度来考虑问题呢?于是,我放弃了画博弈树,直接以先手的角度代入怎么下棋,结果突然发现原来先手有简单必胜的策略,证明如下。

先手必胜的证明

注:红\Delta为先手,蓝O为后手。先手为必下策略,后手为可能策略,相当于解象棋围棋五子棋的残局。第一和第二个照片是第一步不同。

第一步\Delta走中间:

f9f92eead63b43118ddb21c0c0906d53.png

第一步\Delta走两边:

01c3f3223c75456a9274f456452baab1.png

先手策略总结:前四步连续前冲就可以赢棋。

失败的博弈树(三个多小时的成果)

b0afe74cd77b441e89815b283ae40097.png

文章来源:https://blog.csdn.net/weixin_74746867/article/details/135574549
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。