楼主: No3676671
2418 3

[学科前沿] 井字棋的最优策略竟是先占角! [推广有奖]

  • 3关注
  • 17粉丝

贵宾

学科带头人

56%

还不是VIP/贵宾

-

威望
2
论坛币
8466 个
通用积分
108.7310
学术水平
91 点
热心指数
97 点
信用等级
78 点
经验
23348 点
帖子
421
精华
3
在线时间
2535 小时
注册时间
2006-2-18
最后登录
2024-3-21

+2 论坛币
k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群
赵安豆老师微信:zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

感谢您参与论坛问题回答

经管之家送您两个论坛币!

+2 论坛币

井字棋可能是最简单的棋类游戏了,它简单到了成年人之间玩几乎总是平局的地步。因此,这个游戏貌似最多只能哄哄小孩子。不过,对井字棋游戏中所有可能的情况进行一番细致的分析,你会发现一个你或许不会料到的惊人结论——先手的最优策略不是稳坐正中央,而是先占一个角!

几年前,果壳网小编曾经自己动手写过一个和人下井字棋的电脑程序,运行之后却发现电脑先走时总爱把第一步棋下在角上;检查程序代码许久后才意识到,电脑程序可能并没有问题。人们往往有一个定势思维,认为由于从正中央出发能够得到的连线最多,因此最优策略必然是先占住正中央这块宝地。然而,经验是一回事,实际上就是另一回事了——这个电脑程序看似很没头脑地往角里下棋,但几乎总是在赢。

无独有偶,国外著名的 Geek 漫画 xkcd 最近画了一幅井字棋最优策略完全图,同样给出了这个违反直觉的结论:第一步走在角上才是最佳的策略。

图片来源:http://xkcd.com/832/

这究竟是为什么呢?不妨让我们看一看,如果第一步真的走角,会发生哪些情况。

先手先占角!

游戏开始后,二话不说先占上一个角(比如左下角吧),那么对方总共有五种本质不同的应对策略:占据靠近你的那条边,占据靠近你的那个角,占据远离你的那条边,占据远离你的那个角(即对角),以及占据正中央的位置。不可思议的是,在这五种策略中,前面四种都是陷阱——如果对方不慎选择了前面四种策略中的任意一种,他就必然输掉。

上图显示了在这四种情况下你可以如何把对方一步步逼上绝路。假设对方走正下方,占据了一个靠近你的边(最左边的那个图),你就可以占据正中央来应对,逼迫对方不得不走右上角。这时,只需要在左上角放下一子,你就赢定了——图中出现了两条只差一子的连线,对方不可能兼顾得了。

右边几个图显示了对方第一步棋的其它几种走法。选择合适的位置应对他,都可以在下一步迫使对方只剩一种走法,接下来你便可以下出“一箭双雕”的棋,让对方无法彻底封杀你。

也就是说,当你占据棋盘一角后,在对方下一步棋的八个可选位置中,其中七个位置都是必输的,陷阱摆满了几乎整个棋盘。在面对“先走一角”的诡异开局时,你的朋友说不准就会慌了手脚,没能冷静地占住中间,决定了必败的命运。

对方要是真的走了正中间,你仍然有赢的机会。你可以占住右上角的位置(如上图)。如果对方不幸走了剩下的两个角中的一个(上图左),你便能故技重施,再次取得胜利。只有对方选择了边上的位置(上图右),才能躲过这一系列的陷阱,最终变成平局。

难怪计算机会把角上的位置当作宝地呢。


后手还是先占角!


作为后行者,你遇到的往往是“先走中间”的经典开局。此时,千万别忘了,先占角仍然是一条金科玉律。如果你不慎走了某条边的位置,对方可就赢定了!对方可以向上面的第一幅图那样,在正右方下子应对,逼迫你把下一步棋落在正左方。此时,对方便可占据右上方的位置,同时产生出两条仅差一子的连线。右边三幅图则显示,如果你在角上应对,最终总会是一盘和棋。


转自果壳
二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

关键词:最优策略 电脑程序 HTTP Geek 程序代码 电脑程序 小孩子 成年人 棋类 游戏

沙发
欧阳晴晴 发表于 2014-10-3 09:39:47 |只看作者 |坛友微信交流群
相当不错                                                                        
                                       
                                                     
                                                     
                                             
                                                                 
                                                                                 

使用道具

藤椅
fjrong 在职认证  发表于 2014-10-3 12:43:46 |只看作者 |坛友微信交流群
长知识了
已有 1 人评分论坛币 收起 理由
No3676671 + 20 鼓励积极发帖讨论

总评分: 论坛币 + 20   查看全部评分

使用道具

板凳
幽蓝木希 发表于 2014-11-5 09:56:40 |只看作者 |坛友微信交流群
有空试试
已有 1 人评分论坛币 收起 理由
No3676671 + 20 热心帮助其他会员

总评分: 论坛币 + 20   查看全部评分

使用道具

您需要登录后才可以回帖 登录 | 我要注册

本版微信群
加JingGuanBbs
拉您进交流群

京ICP备16021002-2号 京B2-20170662号 京公网安备 11010802022788号 论坛法律顾问:王进律师 知识产权保护声明   免责及隐私声明

GMT+8, 2024-5-6 13:41