首页 > 博弈 > 所以这个世界就没人知道井字过三关了么?!

所以这个世界就没人知道井字过三关了么?!

2014年3月2日 发表评论 阅读评论

之前忘了是什么事儿,看到一道博弈题,然后想着想着就想到了井字过三关,然后又想到了以前有人跟我说过:其实很多人并不清楚井字过三关的正确走法。。于是我就想问一下实验室的人验证一下这句话,对L某说:“你玩井字过三关一般是怎么玩的?”;

L某回答说“井字过三关是啥?”

“什么,你居然不知道井字过三关?!!”

“你说一下规则来听听?”

于是我简单讲了一下“就是那个XXXXXX的游戏啊!!”

然后L某还是很冷漠的说“没听过。。”;

这个时候我对有人不知道井字过三关表示高度震惊!!正在说着“你没童年”的时候,实验室Q某装完水走进来了,为了扳回一局,我马上问到“你玩过井字过三关没”,之后。。标准结局。。。在我解释完规则后Q某终于表示:“啊,这个啊,听过,没玩过。。”,然后L某很得意的对我嘲讽地说“打脸了吧~”。。

之后我又问了实验室Z某。。。然后晚上回来问舍友。。。。结局就是。。。难道就没人玩过井字过三关么!!!这不科学!!经过再三地跟不同的人打听,得知除了好一部分人真的不知道这个游戏,还有一些人是把井字过三关叫做别的名字,比如冰果游戏,打井(游戏),OX游戏,圈叉游戏【这两个名字。。。】。。。

所以我很想统计一下。。。究竟有多少人知道井字过三关的。。。你们是怎么称呼这个游戏的。。。【虽然来我这里的读者人不多。。。所以我也不指望有多少人投票。。

顺便,为了正义与道德。。。我决定说一下井字过三关的规则。。。

规则:两个玩家,一个打圈O,一个打叉X,轮流在3乘3的格上打自己的符号,最先以横、直、斜连成一线则为胜。

游戏调查

Loading ... Loading ...

然后是正题,请告知一下,你如果先手的话,你一般是先下哪里。

游戏策略调查

Loading ... Loading ...

嗯,希望大家投个票让我了解一下状况,即便没听过这个游戏的,你也可以凭直觉选一个位置下。。

虽然我估计有些人大概知道我的意图是啥了,甚至有些人知道我后面的东西会写什么了,所以后文我就不设成投票后可见了。。但是我坚信还是有些人不知道的,嗯。。。应该吧。。



























好吧,其实只是调查一下有多少人觉得井字过三关应该走中间一步的。。事实上,早在3,4年前,Matrix67大神在忘了是果壳还是科学松鼠会上就发过文章说井字过三关的最优策略是先走角的!

结论说完,下文是我自娱自乐。。【不想听废话的可以直接空降至后文红字处!直接右上角也行。。我刚刚也想好了一大串理由来掩饰我为什么会蛋疼到无聊写程序去分析这种游戏了,但还是把那些理由删掉了,因为等那个理由被我实现后(还是蛋疼的编程),我会再写一篇博文来解释的。。。】

这个结论的推导其实也不难,你只要拿起手上的,然后准备N张草稿纸,自己手推一下各种情况就大概会明白了;

好,写程序分析这个游戏和上面提到的手写推算的方法的区别就是,你可以花差不多的时间,来省下很多草稿纸。。。。。【好吧,编程其实慢很多。。】

程序的思路很简单,就是博弈里面的极小化极大算法(维基百科请戳我),了解这方面算法的请不要吐槽为什么没用α-β剪枝算法,原因很多,比如。。我懒。。【好吧,其实是这个问题规模很小,没必要】

争取在140×n个字内简单解释一下这个算法吧:

寻找策略的方法就是历遍全部可能,然后选择最优的,那么怎么判断某一决策是最优的呢?就是假设走了这一步后,要让对手所能做出的反抗的最大值要尽可能的小,也就是要假设对手一定会做出最大反抗,而你的这一步造成的最大反抗值最小,那么这就是你的最优策略了,说白了就是极小化对方的极大值

然后就是要思考怎么去算对方的最大反抗值,那么自然需要历遍各种反抗方法,找到最大反抗值的方法,那么每种方法的反抗值怎么算?自然就是站在对方的角度,历遍你的各种走法。。。。好吧,不晕的人大概应该懂了,晕的人我再讲你也是晕。。所以就到这里为止了。。。

回到这个问题,如果存在必胜的方法,那么就是不管对方怎么走,你都有办法将局面引导至自己胜利的情况;必败情况相反,不管你怎么挣扎,对方都可以nen死你。

代码缩进了,反正你们也不会感兴趣的。。。

代码

下面就用程序的结果,简单解释一下为什么走角是最优的!!
第一幅图:
jing1
意思就是说,如果无限聪明的对方走了角,也就是位置1,那么你只有走中间才有可能逼成平局,你走其余任何一个地方,都是作死,必败的。

不信?假如你走了下图的位置2,那么对方走感叹号的位置,都是必胜的!而横线位置,可以认为对方是在放水。。【为什么感叹号位置的走法必胜,你脑中随便脑补一下对局,不用动笔都可以想明白的!后文也是,不多做解释。】
jing3

如果你走了下图的位置2,那么对方只有脑残走了红X的位置才有可能被你反败为胜!只要对方走白色感叹号位置,你就输定了。
jing4

下面是剩余的两种情况!
jing5
jing6

上面四幅图其实意思就是说,只要你第二步不走中间那个位置,对方一定存在必胜的策略!!

我们再来对比一下很多人心目中的最优走法————走中间的情况,你面临的胜负可能是:
jing7

也就是说,面对智商无穷大的对手,你走四个红X的位置,对方才必胜,你走角,就可以逼平;

总之上面的分析得到两个结论:

  • 先手的话,应该走角,因为对方只有一个位置可以逃开必败的下场。
  • 后手的话,如果对方走中间,你就一定要走角;如果对方走角,你就应该。。。

后话,第一步你走了角,对方第二步走了中间,第三部你只要走另一个对角,对方还是有必败的可能的,虽然我不觉得他会这么脑残走下图红X的地方

jing2

真正的后话:这篇东西其实我只是想说,不要认为你所认为是对的东西,就一定是对的,更加不要以为你认为对方应该知道的东西,对方就应该知道,有可能你自己就是错的。。。

所以。。。。。千万不要认为你的同龄人。。都分得清数码宝贝和神奇宝贝。。。


【完】

本文内容遵从CC版权协议,转载请注明出自http://www.kylen314.com

分类: 博弈 标签: , ,