转跳到内容

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


raynormj

推荐贴

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

 

 

Connect_4_Board_and_Box.jpg

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

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

Connect_Four.gif

由于游戏实在是太过简单,但是“必胜策略”又太过机械,或许在后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步必胜。

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

 

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

 

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

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

 

 

召唤聊过棋类游戏的

 

,由raynormj修改
注释
雪染 雪染 150.00节操 6分
链接到点评

:a1:95年暴力破解也不是真正的暴力破解。而是剪枝暴力破解(这里用的Alpha-Beta pruning,其实是很笨的裁剪方法了)。

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

10 小时前, raynormj 说道:

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

这游戏就是因为规则简单,可以大幅度剪枝运算,才可以暴力破解。

而且15和13可不是“多一点点”的问题,举个最简单的例子。

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

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

10 小时前, raynormj 说道:

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

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

:wn005:不过如果中间的变化性太多,强化学习难度还是很大的,比如星际争霸2。理赔难Time对战起源AI。

AI赢是赢了,怎么赢的?靠人类无法复现的操作碾压完成的,比如屏幕外进行多线运营操作。

举个最简单的例子,人家谷歌AI的APM(每分钟操作次数) 10000,人类巅峰才300-400左右的平均,你怎么赢?

这玩意还得加好多限制条件,学习上好久,才能达到人类想要的目的。

链接到点评
20 小时前, 乱跑的泰兰德 说道:

:a1:95年暴力破解也不是真正的暴力破解。而是剪枝暴力破解(这里用的Alpha-Beta pruning,其实是很笨的裁剪方法了)。

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

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

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

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

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

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

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

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

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

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

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

链接到点评
14 小时前, 在下东方大雕 说道:

:mx016:我还真是第一次听说Connect Four

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

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

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

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

链接到点评
×
×
  • 新建...

重要消息

为使您更好地使用该站点,请仔细阅读以下内容: 使用条款