银行 社区服务 每日签到 会员排行 网站地图
  • 3744阅读
  • 7回复

五子棋先下的一定赢吗如何证明五子棋黑棋先手必胜吗

楼层直达
级别: 少校
[棋中红钻2级]发帖数量≥100篇 [棋中黄钻5级]金币数量≥10000枚 [棋中蓝钻1级]乐币数量≥10枚 [棋中粉钻1级]贡献值数量≥1点 [棋中彩钻3级]精华帖数量≥5篇
发帖
407
金币
10387
威望
10
贡献值
1
乐币
11
主题
390

相信大家都听说过五子棋先下的一定能赢,但是如何证明五子棋黑棋先手必胜呢?通常大家玩的五子棋分为带禁手和不带禁手两个版本(前者称之为连珠Renju,后者一般称之为五子棋Gomoku),无论哪一个版本,先手黑棋均必胜。后面还会讲到,26种职业开局一多半都是先手必胜。
所谓黑必胜的意思是,只要黑棋按照一定的方式下,白棋选择棋盘上的任何一个点都不可能赢棋。
——第一次严格的证明——
其实在电脑出现之前,五子棋的玩家就发现黑棋采取某些开局赢面极大,实践中白棋几种很强的防守都无法阻挡黑棋最终赢,也怀疑有先手“绝对”必胜的方法。但这不能保证可能遗漏了某种白棋能赢的方式,所以二十世纪初五子棋的普遍的观点是黑棋应该是必胜,但近百年年都没有人能够真正“证明”出来白棋无论怎么下都是必败的——这个结论最终还是通过电脑来严格证明的。

其中1992年Victor Allis通过编程证明不带禁手的五子棋,黑必胜的。
——然后说说带禁手的五子棋——
禁手规则是只针对黑棋的,简而言之是黑棋只允许使用冲四活三这一种赢法(当然不排除白棋故意冲四不挡这种方法)。设计的目的也是为了限制黑棋的巨大优势,白棋也多了逼禁手这儿一种赢法。但后来人们也逐步发现带禁手后,黑棋依然似乎能不败。直到后来,也有人证明,带禁手执黑也可以必胜。
2001年Janos Wagner第一次证明的带禁手的五子棋,也是黑必胜的。
这个后面的证明比前面的证明要强很多,因为按照带禁手的走法,不带禁手也一定必胜,但倒过来未必。
黑棋的优势到底有多大呢?在26个职业开局里,已经发现有19个是黑棋必胜的(一打必胜)。
——然后说说五手两打——
这还不说,为了进一步削弱黑棋的优势,国际上推出五手两打(就是黑棋的第三步需要下两个点,但由白棋挑选让其下较弱的哪一个)的规则。可是人们发现黑棋带禁手依然是必胜。也就是说,黑棋必胜不仅仅有一种方法,而是至少有两种以上(来回应各种变种的第四步),像浦月、花月这种黑棋超级优势开局都有三种以上的必胜法。
从实践的角度来讲,网上是可以搜索“地毯谱”( 更新:目前花月、浦月、云月、雨月、峡月、溪月、金星、水月、寒星、明星、岚月、新月、名月,山月,残月都是五手两打必胜),一般在几百兆左右,可以用renlib软件打开,所谓地毯谱的意思就是黑棋会指定下法,但白棋每一步都可以选择棋盘任意位置,最后黑棋必胜。也就是说,只要按照此棋谱下棋,五子棋世界冠军都一定会输给你。
——正式比赛怎么玩——
所以正式的比赛才会有三手交换五手两打,山口规则(五手n打)这些复杂的规则来平衡比赛。另外业余的平台有时候还会下一手交换(第一步黑棋不下棋盘中间的天元)。但这些规则的各个分支也是逐渐被人破解,五子棋的比赛已经很大程度不是在考验自己的临场发挥,而是考验选手对于少量黑白平衡 分支的记忆情况。
另外针对有人质疑既然五子棋必胜,为什么还要玩:
必胜并不代表去网上黑先开浦月、花月就一定人挡杀人,佛挡杀佛。必胜的各种分支套路也不是那么容易记住的,诸位可以和tito2014或者弈心执黑体验一下(高手绕道)。所以虽然理论上如果黑棋必胜那么各种对战平台上的胜率应该是50%,但实际情况是,非禁手区/禁手区均有不少胜率超过80%甚至90%的高手。
——广义的“五子棋”——
另外不带禁手的五子棋是属于一类更为普遍的m,n,k游戏(m,n,k-game)的一种特例,既15,15,5。m,n,k游戏是指m行n列,轮流下子,连成k个算赢。这个在数学中专门的研究如果在最理想下法(Perfect Play)的情况下有什么样不同的结果,比如标准的三连棋(Tic-tac-toe)是3,3,3是一个平局,同样只有六路棋盘的五子棋也是平局,当然上面我们已经说明了15,15,5是先手必胜,还有研究发现11,11,5也是先手必胜。m,n,k游戏只有先手必胜和平局两种结果。由于每下一个子都一定会对下子一方那一方有优势,所以可以通过反证法证明m,n,k游戏里不可能有后手胜利的情况。如果后手有胜利的方法,那么先手可以提前“借鉴”过来实现必胜(Strategy stealing)。
——如果不加复杂的开局规则,怎么办——
另外除了规定复杂的开局和禁手规则,其实还有一个出路:
除了采取对先手采取各种限制的方法,2003年被吴毅成教授发明的連六棋(Connect6)也非常类似五子棋,难度很高,但六子棋没有先手优势——因为每一步都下两个子,除了第一步下一个子,这样保证双方每次下棋时,都可以比对方多一个子。AI目前计算的结果也是,没有发现先手比后手有更大的优势。
既然双方都没有优势,六子棋下满整个(围棋19x19棋盘)都没有分出高低都是有可能的。(这个游戏已经不再是m,n,k游戏了)
不得不说的是,虽然有个别比赛(gomocup说你呢)还是在用限定规则的五子棋做ai比赛,但是正经的编程奥赛是没有五子棋的比赛(93年就没了好不好),而被connect6这种简约的规则所取代。Connect6的解决难度几乎与围棋相当。
——有关五子棋AI——
感兴趣传统五子棋和连珠的AI算法的可以参考这个问题:
现在的五子棋AI在职业比赛规则下与人对决是什么水平? - 人工智能
想写一个机器学习类的五子棋,可能么?可能的话需要看什么书,参考什么,求指点
级别: 少校
[棋中红钻5级]发帖数量≥2000篇 [棋中黄钻4级]金币数量≥5000枚 [棋中蓝钻1级]乐币数量≥10枚 [棋中粉钻2级]贡献值数量≥5点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
3021
金币
8320
威望
0
贡献值
7
乐币
29
主题
5

只看该作者 一楼  发表于: 2019-06-21
感觉不一定是先手一定赢吧?
级别: 四级士官
[棋中红钻2级]发帖数量≥100篇 [未点亮棋中黄钻]金币数量<100枚 [未点亮棋中蓝钻]乐币数量<10枚 [未点亮棋中粉钻]贡献值数量<1点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
120
金币
1
威望
0
贡献值
0
乐币
0
主题
0
只看该作者 二楼  发表于: 2019-06-22
感觉不一定是先手一定赢吧
级别: 列兵
[未点亮棋中红钻]发帖数量<10篇 [未点亮棋中黄钻]金币数量<100枚 [未点亮棋中蓝钻]乐币数量<10枚 [未点亮棋中粉钻]贡献值数量<1点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
1
金币
11
威望
0
贡献值
0
乐币
0
主题
0
只看该作者 三楼  发表于: 2020-02-11


级别: 一级士官
[棋中红钻1级]发帖数量≥10篇 [未点亮棋中黄钻]金币数量<100枚 [未点亮棋中蓝钻]乐币数量<10枚 [未点亮棋中粉钻]贡献值数量<1点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
23
金币
3
威望
0
贡献值
0
乐币
0
主题
0
只看该作者 4楼 发表于: 2020-03-08
感觉不一定是先手一定赢吧
级别: 三级士官
[棋中红钻1级]发帖数量≥10篇 [棋中黄钻1级]金币数量≥100枚 [未点亮棋中蓝钻]乐币数量<10枚 [未点亮棋中粉钻]贡献值数量<1点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
87
金币
110
威望
0
贡献值
0
乐币
1
主题
0
只看该作者 5楼 发表于: 2020-06-06
感觉不一定是先手一定赢吧
级别: 少尉
[棋中红钻2级]发帖数量≥100篇 [未点亮棋中黄钻]金币数量<100枚 [未点亮棋中蓝钻]乐币数量<10枚 [未点亮棋中粉钻]贡献值数量<1点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
179
金币
-47
威望
1
贡献值
0
乐币
0
主题
6
只看该作者 6楼 发表于: 2020-07-09
Relay
Nó không phải là một chiến thắng tay đầu tiên.
级别: 三级士官
[棋中红钻1级]发帖数量≥10篇 [棋中黄钻1级]金币数量≥100枚 [未点亮棋中蓝钻]乐币数量<10枚 [未点亮棋中粉钻]贡献值数量<1点 [未点亮棋中彩钻]精华帖数量<1篇
发帖
87
金币
110
威望
0
贡献值
0
乐币
1
主题
0
只看该作者 7楼 发表于: 2020-08-18
先手软件太厉害了啊
快速回复

限56 字节
请不要在回贴只采用字母:“ PP、asdfhjkl、HAO、OK、ddddddd ......”。  请不要在回贴过于简单的内容:“不错、顶、支持、厉害、呵呵、靠、晕........”
 
验证问题: 我们的论坛名字是?
上一个 下一个