raynormj 发布于三月 27, 2021 分享 发布于三月 27, 2021 (已修改) · 只看该作者 这个经典游戏都被破解了的时代——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修改 注释 雪染 150.00节操 6分 1 链接到点评
星落OFFICIAL 发布于三月 28, 2021 分享 发布于三月 28, 2021 · 只看该作者 哇这个游戏真的是童年经典了竟然被破解了么 而且原来这个游戏还是能算出来必胜法则的么惊了 不过可能还是这个游戏太简单，规则限制的太死的原因才能被破解吧？要是难度再高一点，规则限制没那么死应该就没有必胜法则了吧？ 链接到点评
乱跑的泰兰德 发布于三月 28, 2021 分享 发布于三月 28, 2021 · 只看该作者 95年暴力破解也不是真正的暴力破解。而是剪枝暴力破解（这里用的Alpha-Beta pruning，其实是很笨的裁剪方法了）。 剔除完全不合理步骤后的暴力破解法。已经极大幅度去除了无用的步骤。 10 小时前, raynormj 说道: 行列和15实际上也只比原来的13多了一点点，所以如果以现在的计算机性能来说的话，更大的问题应该也是能暴力解决的。 这游戏就是因为规则简单，可以大幅度剪枝运算，才可以暴力破解。 而且15和13可不是“多一点点”的问题，举个最简单的例子。 15的阶乘和13的阶乘，差的是“一点点”么？显然不是。 更何况这已经是 7*6！和7*8！的区别了。 10 小时前, raynormj 说道: 最后我想说，现在已经没有几个游戏是没有被解法给霍霍的了啊，悲—— 没办法，只要是人玩的游戏，全都可以用“强化学习”来完美模拟，最终目的太明确了，机器完全可以模拟进行。 不过如果中间的变化性太多，强化学习难度还是很大的，比如星际争霸2。理赔难Time对战起源AI。 AI赢是赢了，怎么赢的？靠人类无法复现的操作碾压完成的，比如屏幕外进行多线运营操作。 举个最简单的例子，人家谷歌AI的APM（每分钟操作次数） 10000，人类巅峰才300-400左右的平均，你怎么赢？ 这玩意还得加好多限制条件，学习上好久，才能达到人类想要的目的。 1 链接到点评
在下东方大雕 发布于三月 28, 2021 分享 发布于三月 28, 2021 · 只看该作者 我还真是第一次听说Connect Four 不过这种连子类的棋牌游戏基本都存在必胜法或者优势玩法吧 链接到点评
hentai14 发布于三月 28, 2021 分享 发布于三月 28, 2021 · 只看该作者 這種時候, 漫畫裡那些第一次玩遊戲就能看出必勝法的主角真是太神啦~ (比方說拿這個遊戲去挑戰武藤遊戲看看... ) 定式跟棋譜這種死記的固定走法, 就是讓我沒繼續下象棋的原因~ 最近都沒什麼好的回合制SLG... 链接到点评
raynormj 发布于三月 29, 2021 作者 分享 发布于三月 29, 2021 · 只看该作者 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 发布于三月 29, 2021 作者 分享 发布于三月 29, 2021 · 只看该作者 14 小时前, 在下东方大雕 说道: 我还真是第一次听说Connect Four 不过这种连子类的棋牌游戏基本都存在必胜法或者优势玩法吧 咦，我跟久帝都有印象，小时候玩过实物的这种。现在桌游吧里面应该也都有吧。还是说英文名头一次听说？ 完全信息的最困难的也就是围棋了。主要还是搜索树太大的问题。最优玩法是必然的。 要是能搞定围棋的搜索树根本不需要AI神经网络什么的。说白了AI的这种构型，就是不需要休息不会出错的人脑功能的升级版而已，肯定不是最优的。 链接到点评
raynormj 发布于三月 31, 2021 作者 分享 发布于三月 31, 2021 · 只看该作者 16 小时前, 久帝 说道: 嘛啊这种棋必胜很正常啊 其实我觉得找这种幼儿游戏的最优解的研究人员还是很无聊的.jpg raynormj得到了穿越资格，兴奋过度从而砸坏了键盘.-3节操 链接到点评
推荐贴