桌游推荐 这个经典游戏都被破解了的时代——Connect Four

[raynormj]

这个经典游戏都被破解了的时代——Connect Four

 

 

Connect Four，中文又叫四子棋，屏风四子棋，四子连珠，等等，在我的印象里，虽然游戏极其简单易懂，但是复杂度也是有的，哪怕是作为完全信息对抗博弈问题。

最基本的形式是长7高6的长方形屏风区域内，两玩家依次落子，只要有一方先获得同色的相邻四子连成一条直线则获胜。

由于游戏实在是太过简单，但是“必胜策略”又太过机械，或许在后AlphaGo时代，随便训练个AI似乎都能够实现必胜吧。

然而当我机缘巧合碰上需要了解这个游戏的时候，翻看维基百科，居然查到了令我有点惊讶的游戏破解情况，摘录如下

引用

Mathematical solution

Connect Four is a two-player game with perfect information for both sides. This term describes games where one player at a time plays, players have all the information about moves that have taken place and all moves that can take place, for a given game state. Connect Four also belongs to the classification of an adversarial, zero-sum game, since a player's advantage is an opponent's disadvantage.

One measure of complexity of the Connect Four game is the number of possible games board positions. For classic Connect Four played on 6 high, 7 wide grid, there are 4,531,985,219,092 positions[5] for all game boards populated with 0 to 42 pieces.

The game was first solved by James Dow Allen (October 1, 1988), and independently by Victor Allis (October 16, 1988).[6] Allis describes a knowledge-based approach,[7] with nine strategies, as a solution for Connect Four. Allen also describes winning strategies[8][9] in his analysis of the game. At the time of the initial solutions for Connect Four, brute-force analysis was not deemed feasible given the game's complexity and the computer technology available at the time.

Connect Four has since been solved with brute-force methods, beginning with John Tromp's work in compiling an 8-ply database[6][10] (February 4, 1995). The artificial intelligence algorithms able to strongly solve Connect Four are minimax or negamax, with optimizations that include alpha-beta pruning, move ordering, and transposition tables. The code for solving Connect Four with these methods is also the basis for the Fhourstones[11] integer performance benchmark.

The solved conclusion for Connect Four is first player win. With perfect play, the first player can force a win,[6][7][8] on or before the 41st move[12] by starting in the middle column. The game is a theoretical draw when the first player starts in the columns adjacent to the center. For the edges of the game board, column 1 and 2 on left (or column 7 and 6 on right), the exact move-value score for first player start is loss on the 40th move,[12] and loss on the 42nd move,[12] respectively. In other words, by starting with the four outer columns, the first player allows the second player to force a win.

注意红字部分，

1988年，connect four的解法就已经出来了。而且哪怕是暴力求解也是1995年就已经做到了的事情。而中文版维基则提到

引用

也有一些计算机程序懂得以完美玩法下棋，Tromp则破解所有行和列总和最大为15的棋盘。

行列和15实际上也只比原来的13多了一点点，所以如果以现在的计算机性能来说的话，更大的问题应该也是能暴力解决的。

而1988年的理论求解，应该是基于更数学的构造解法或者递归方法吧，毕竟运算力在当年是真正的瓶颈。

 

那么继续翻译的话，以1到7依次给棋盘的七列编号，那么对于完美手法的玩家，先手

• 从第4列行棋，能在41步必胜；
• 从第3或5列行棋，能守和；
• 从第2列行棋，后手能在42步必胜；
• 从第1列行棋，后手能在40步必胜。

毫无随机与悬念的必胜、负游戏。

 

当然，这个游戏也有各种各样的变体，比如更宽更高的棋盘则会拖长游戏进程；而对于一般或许连用眼观察四连都有可能出错的老年人而言，或许应该牢记的就是先手抓住中心列了。

 

那么，学会了的小盆友，赶紧去运用“必胜策略”霍霍更小的小盆友吧——

最后我想说，现在已经没有几个游戏是没有被解法给霍霍的了啊，悲——

 

 

召唤聊过棋类游戏的

剧透

@久帝 @乱跑的泰兰德 @雪染 @NianRuoshui @在下东方大雕 

 

三月 27, 2021，由raynormj修改

[raynormj]

20 小时前, 乱跑的泰兰德 说道:

95年暴力破解也不是真正的暴力破解。而是剪枝暴力破解（这里用的Alpha-Beta pruning，其实是很笨的裁剪方法了）。

剔除完全不合理步骤后的暴力破解法。已经极大幅度去除了无用的步骤。

我去看了看，alpha-beta pruning看起来已经挺完备了呀，这种暴力破解挺机械的，但还是好用的？

20 小时前, 乱跑的泰兰德 说道:

15的阶乘和13的阶乘，差的是“一点点”么？显然不是。

更何况这已经是 7*6！和7*8！的区别了。

这种问题充其量就是阶乘吧？阶乘已经是super exponential了，这种简单游戏不可能更复杂了吧13到15估计也就是乘以200多，对当时的机器可能是搜索树的内存问题。

20 小时前, 乱跑的泰兰德 说道:

没办法，只要是人玩的游戏，全都可以用“强化学习”来完美模拟，最终目的太明确了，机器完全可以模拟进行。

其实我还是觉得棋类更能测试AI的水平，没有什么人的物理上的操作的瓶颈。那种复杂度高的非完全信息问题还是挺多的，只不过没有星际这么吸引眼球。。。

我现在完全不相信“强化学习”能达到最优解，但是能比人强还是很容易的，人也只能玩一个游戏玩几年而已。

而且google这么烧钱实际上就是为了显得项目上花的钱没白花吧。。。AlphaGo的构建报道里我就有这个印象。

[raynormj]

14 小时前, 在下东方大雕 说道:

我还真是第一次听说Connect Four

不过这种连子类的棋牌游戏基本都存在必胜法或者优势玩法吧

咦，我跟久帝都有印象，小时候玩过实物的这种。现在桌游吧里面应该也都有吧。还是说英文名头一次听说？

完全信息的最困难的也就是围棋了。主要还是搜索树太大的问题。最优玩法是必然的。

要是能搞定围棋的搜索树根本不需要AI神经网络什么的。说白了AI的这种构型，就是不需要休息不会出错的人脑功能的升级版而已，肯定不是最优的。

[raynormj]

16 小时前, 久帝 说道:

嘛啊这种棋必胜很正常啊

其实我觉得找这种幼儿游戏的最优解的研究人员还是很无聊的.jpg