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

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

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

分类: 博弈 标签: , ,
  • 这游戏还有这么带感的名字。。。

    • 你管那个游戏叫啥?顺便问一下,你能收得到多说的邮件提醒么?

      • 完全没在意过叫什么,打井 的可能性最高吧邮件有收到

        • 好吧。。收到就好,我还以为最近多说不发邮件了咧。。另,我出差回来了。

          • 。。。你啥时候出差了,我完全不晓得。。话说你去哪儿了

            • 当我没说。。

  • 我们玩的不是这样的,这样的游戏结局基本就是谁先走谁收钱的是吗?

    • 那你们是什么样子的?其实不算是,这个游戏双方都没有必胜的策略,但是都有必然不败的策略。

      • 我们是拿个本子玩的跟玩五子棋一样。

        • 小时候都是上课在本子上玩的。五子棋技术含量显然比这个高很多。。

  • Yu
    • 不是博客上面看到的,查了一下,是这个:http://www.guokr.com/article/4754/

  • 好喜欢博主博客头部那只肥猫....曾一度想给他盖章一下作为logo的... 没成想在博主这又见到它了... 这游戏没有玩过昂.....

    • 这张图的原图,我实验室电脑一直拿来当桌面。。

  • 我们竟然叫他五子棋,哈哈哈

    • 不是应该叫做三子棋么?23333

  • 我只知道叫 井字游戏 ..

    • 好像叫这个名字的人确实比较多。。我lao了。。

      • yuki

        窝也这么叫的,【话说我们肯定玩过。。。】,虽然没仔细分析过,不过小时候玩多了也大概发现了先手下角是最优的。。。

        • 但是直观上怎么理解占有3路的角比占4路的中间更优呢?

  • 不知道怎么玩。

    • 文中前面有讲到规则

  • 数码宝贝和神奇宝贝。。。

    • 我都没看过。。。

      • 我们这一辈的男孩子就基本都了解;

    • 有人问过我这个问题。。。被雷过。。

  • 玩过,井字游戏投票是什么插件matrix67.com我也去过他那里!数学大神分析的有条有理!

    • 投票是WP-Polls

  • OX

    OX怎么了( ´∀`)・ω・) ゜Д゜)・∀・) ̄ー ̄) (我一般管这个叫井字游戏,叫井字过三关多麻烦...(´・ω・`))

    • OX总让人想到圈圈叉叉。。确实是最麻烦的叫法。。主要是我之前一直以为只有这个名字。。。

    • 。。。我刚注意到你的名字。。。

      • OX

        ( ✧≖´◞౪◟≖`) 「OX」这名字多萌啊(其实我以前也一直以为只有「井字游戏」这种叫法..)

        • 读作圈叉还是欧埃克斯?

  • xg

    这个不是叫tic-tac-toe么

    • 额,英文方面,确实没有分歧。。

      • 外国人好像会把所有简单的棋类游戏这么叫。noughts and crosses 是美国的准确叫法,井字过三关,香港和广东叫得最多了~

        • noughts and crosses英语渣表示第一次听,涨姿势了。对,从小在广东长大,周围同学都是这么叫的。。

  • 代码中,getscore中score变量不会增减啊??嵌套调用自己,以curscore作前层score么?确实没有增减的地方呀,这样对么……另外 ,第一个投票能严谨点放个“其他”选项么?我玩过记性不好不确实叫什么了怎么选?

    • score不需要增减啊,它是历遍每一种走法后的分值,用来更新curscore的的啊。“以curscore作前层score么?”这是什么意思?不是有一个“玩过,但不是上面那些名字”么?

      • 怎么更新curscore?遍历每一点都是getscore返回的-9999戓9999即curscore。不需要增减是怎么知道下在哪里得分高呢?投票:我是不记得什么名字,故,不能投你所说那项。那项是否定已列出的那些名字的意思,我既不记得怎么可以否定某个名字呢。。

        • 当然不是,CurScore初始值是±9999只是为了表示正无穷和负无穷而已,然后88和90行会更新它的。为什么你要让我思考这么绕的问题。。。虽然我懂你意思了。。

          • 晕,我感觉我已无法再问下去,死循环了。。。88,90是赋值,所以就回到我第一条评论的话:变量score的值不变(是嵌套的上层返回的curscore即负正无穷)赋给本层curscore仍负正无穷,不增减啊。不明白怎么个意思。

            • 递归啊。GetScore的功能是计算当前棋面game下面所有可行的走法中分值最大或者最小的那一步(最大最小取决于站在玩家角度思考还是对手角度思考);由于score是由GetScore递归而来的,所以其值只可能是0,1,-1,说明return curscore时只可能是0,1,-1啊。

              • 是递归。我没理解错的话你用1表示胜,0平-1负?不是定义了相应表示常量,还用数字有何意义。。另外 ,若先手下00位,下手不论是不是01,先手又定下03……晕了,我脑袋不够用了……递归次数好像没有列出所有可能的情况呀,不足以证明什么啊,感觉。算了,我不想它了,乱了。。

                • 其实比起看代码,你随便去找一本《人工智能》的书籍,看一下里面的极大极小算法就很容易明白了。是枚举了N步之内的全部解法,因为游戏最多进行9步,所以只要思考深度大于9,那么就必然枚举完全部解法。不像下一篇那个变种游戏那样,只能计算一定步数内的全部情况。

  • 我记得,叫做tic tac toe

    • 我程序命名是用这个,不过L_Ls_L说准确的叫noughts and crosses,考证了以下,确实是。。