一维围棋的先手优势

KeyTo9_Fans · 发表于 2023-9-6 14:05:01

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

二维围棋复杂度太高，先手优势的大小无法精确求得，因此本贴讨论复杂度较低的一维围棋。

问题：在1×n的棋盘上对弈，双方都采取最优策略时，先手优势为多少目？

行棋规则：
1、空盘开局，黑先白后，轮流着子，允许虚手（pass）。
2、打劫需隔一手提劫，允许隔虚提劫，允许全局同形再现。
3、连续3虚（pass )终局.
4、如果遇到循环局面，那么双方的最终得分就是一个循环节里所有局面的双方得分的平均值.

胜负计算：采用中国围棋数子规则
1、棋盘上的子每个计1目
2、空属邻子计 1目，公空和无邻子的空双方平分各计0.5目
双方的目数之和等于n。黑方的目数减白方的目数即先手优势A(n)。
=====

如果此题已经完全解决，在OEIS网站应能找到这个数列，那么只需找到数列编号即可。
如果找不到对应的数列编号，可以在此开展讨论A(n)，
得到结果后提交到OEIS，为之提供新的有趣数列。

KeyTo9_Fans · 发表于 2023-9-13 23:14:41

我把博弈树的搜索深度限制在300层以内，堆栈溢出问题和超时问题就没有了，相应的代价是程序输出的局面是这个规则下的最佳进程：

下完300步就强制终局，双方的最终得分按照前300个局面的平均得分计算

而不是这个规则下的最佳进程：

下完m步就强制终局，双方的最终得分按照前m个局面的平均得分计算，m→∞

#####

在“300步强制终局”的规则下，n=9到n=15的最佳策略是这样下的：

9
·········
·●·······
·●·····○·
·●·●···○·
·●·●·○·○·
·●●●·○·○·
·●●●·○○○·
·●●●·○○○·
·●●●·○○○·
·●●●·○○○·
10
··········
·●········
·●······○·
·●····●·○·
·●·○··●·○·
·●·○·●●·○·
·●·○·●●·○·
·●·○·●●·○·
·●·○·●●·○·
11
···········
·●·········
·●·······○·
·●·●·····○·
·●·●···○·○·
·●·●·●·○·○·
·●·●·●·○○○·
·●●●·●·○○○·
·●●●·●·○○○·
·●●●●●·○○○·
·●●●●●·○○○·
·●●●●●·○○○·
·●●●●●·○○○·
12
············
···●········
···●··○·····
·●·●··○·····
·●·●··○···○·
·●·●··○·●·○·
·●·●·○○·●·○·
·●●●·○○·●·○·
·●●●·○○·●·○·
·●●●·○○·●·○·
·●●●·○○·●·○·
13
·············
·●···········
·●·········○·
·●·●·······○·
·●·●·····○·○·
·●·●·●···○·○·
·●·●·●·○·○·○·
·●●●·●·○·○·○·
·●●●·●·○○○·○·
·●●●●●·○○○·○·
·●●●●●·○○○○○·
·●●●●●·○○○○○·
·●●●●●·○○○○○·
·●●●●●·○○○○○·
14
··············
·●············
·●··········○·
·●········●·○·
·●·○······●·○·
·●·○·●····●·○·
·●·○·●·○··●·○·
·●·○·●·○·●●·○·
·●·○·●·○·●●·○·
·●·○·●·○·●●·○·
·●·○·●·○·●●·○·
15
···············
·●·············
·●···········○·
·●·······●···○·
·●·······●·○·○·
·●·····●·●·○·○·
·●·○···●·●·○·○·
·●·○·●·●·●·○·○·
·●·○·●·●·●·○○○·
·●·○·●●●·●·○○○·
·●·○·●●●·●·○○○·
·●·○·●●●●●·○○○·
·●·○·●●●●●·○○○·
·●·○·●●●●●·○○○·
·●·○·●●●●●·○○○·

复制代码

我大致看了一遍，发现双方都很佛系，没有打吃和劫争，下成双活局面就 3 pass 结束了

不知道对于更大的n，双方会不会一直佛系下去呢？

如果会的话，如何证明这种佛系的下法就是最优下法呢？

KeyTo9_Fans · 发表于 2023-9-12 17:35:30

hujunhua 14#：既然有程序，可以多放一些结果出来，现在算到多大的 n 了？

KeyTo9_Fans的回复如下：

目前n<9能出结果

n=9运行了很长时间，都没有停下来，可能是遇到死循环了

n=10运行出错，报“堆栈溢出”错误

#####

n=6他们是这样下的（3 pass 终局，黑白比分3.5比2.5）：

6
······
·●····
·●··○·
·●●·○·
·●●·○·
·●●·○·
·●●·○·

复制代码

n=7他们是这样下的（3 pass 终局，黑白比分4.5比2.5）：

7
·······
·●·····
·●···○·
·●·●·○·
·●·●·○·
·●●●·○·
·●●●·○·
·●●●·○·
·●●●·○·

复制代码

n=8他们是这样下的（3 pass 终局，黑白比分5.5比2.5）：

8
········
·●······
·●·○····
·●·○●···
·●·○·○··
·●·○·○●·
·●·○·○·○
·●●○·○·○
·●●○·○○○
·●●·●···
·●●·●·○·
·●●●●·○·
·●●●●·○·
·●●●●·○·
·●●●●·○·

复制代码

n=6和n=7的最佳下法我勉强能理解，n=8我完全没法理解他们为啥这样下，不排除程序有bug

#####

我接下来尝试理解一下n=8的最佳下法。

首先我认为白的第1步应该下在第7个位置，做成这种局面：

·●····○·

但这个局面会导致这样的结果：

·●····○·
·●··●·○·
·●··●○○·
·●··●··●
·●··●·○·
·●●·●·○·
·●●·●·○·
·●●●●·○·
·●●●●·○·
·●●●●·○·
·●●●●·○·

复制代码

结果白方的最终得分仍然是2.5，看来白1下在7处并没有改善白方的最终得分

其次，我认为白的第1步可以尝试下在第5个位置，做成这种局面：

·●··○···

但这个局面会导致这样的结果：

·●··○···
·●·●○···
·●○·○···
·●○·○·●·
○·○·○·●·
○·○·○●●·
○○○·○●●·
···●·●●·
·○·●·●●·
·○·●●●●·
·○·●●●●·
·○·●●●●·
·○·●●●●·

复制代码

结果白方的最终得分仍然是2.5，看来白1下在5处也没有改善白方的最终得分

此外，我认为在这个局面下：

·●●○·○·○

白可以吃光黑子，做成这种局面：

○··○·○·○

但我被后续的进程啪啪打脸了：

○··○·○·○
○··○·○●·
○··○○○●·
○·●···●·
○·●·○·●·
·●●·○·●·
·●●·○·●·
·●●·○·●·
·●●·○·●·

复制代码

白最终只得了2分，比2.5分还差

hujunhua你觉得还有哪个局面，他们的应对方案欠妥呢？

我可以让程序给出后续的最佳进程

KeyTo9_Fans · 发表于 2023-9-14 15:01:47

二间跳好像很容易陷入吃子之争，对方好像可以强行紧贴二间跳打吃。

例如，当n=11时，白终局落后2分，白如果不满意，想通过二间跳扳平比分，我人工推演了一下，会下出这样的结果：

···········
·●·········
·●·······○·
·●·●·····○·
·●·●··○··○·
·●·●·●○··○·
·●·●○·○··○·
·●·●○·○●·○·
·●○·○·○●·○·
·●○·○●·●·○·
○·○·○●·●·○·
○·○●·●·●·○·
○·○●·●·●○○·
○·○●·●·●··●
○·○·○●·●··●
·●○·○●·●··●
·●○·○·○●··●
·●·●○·○●··●
·●·●○·○·○·●
·●·●·●○·○·●
·●·●·●○·○○·
·●·●·●·●○○·
·●·●·●·●○○·
·●·●·●·●··●
·●·●·●·●·○·
·●·●·●·●·○·
·●·●·●·●·○·
·●·●·●·●·○·

复制代码

白好像很难在吃子之争里得利，因为白把左边的黑子吃完后，自己的棋形有缺陷，黑可以轻易反吃回来

白接不归，无法避免被黑棋反吃

我的程序认为白二间跳被黑打吃后，白应该后退一步，心甘情愿被黑吃，然后打2还1，才能做到最终只落后2分：

11
·●·●··○··○·
·●·●·●○··○·
·●·●·●○○·○·
·●·●·●··●○·
·●·●·●·○·○·
·●●●·●·○·○·
·●●●·●·○○○·
·●●●●●·○○○·
·●●●●●·○○○·
·●●●●●·○○○·
·●●●●●·○○○·

复制代码

白如果贪吃黑子，只会落后更多

#####

根据程序的计算结果，当n等于1到15时，黑方所贴的目数A(n)如下表所示，方可公平对弈：

n A(n)
1 0
2 0
3 3
4 4
5 0
6 1
7 2
8 3
9 0
10 1
11 2
12 1
13 0
14 1
15 2

《在线整数数列百科大全》目前还没有收录这个数列，我们确认无误后，可以申请创建一个新数列。

majer · 发表于 2023-9-7 10:51:53

小时候和好友下围棋。因为一盘用时太久，我们两个人就想到单纯在一条线上行棋。后来又专注于寻找n较小时的必胜走法。等接触网络之后——十多年前——我还特意谷歌了一维围棋（关键词大概是one-dimension one-dimension gomoku？记不清了），当时主要找到了两份相关资料。一个是马丁加德纳关于这种围棋规则的阐述，另一个则是一本在亚马逊书店上售卖的关于一维围棋的专著。刚才又Google了一下，可能是关键词不对，完全没找到之前的信息尤其是那本专著（因为马丁伽德非常有名，所以之后按理说都会用加德纳的命名方式称呼这种围棋。所以找到加德纳的原文，就能知道学术界怎么称呼这个游戏），就找到了下面相关的介绍，但没啥用：https://senseis.xmp.net/?AlakGame1

KeyTo9_Fans · 发表于 2023-9-8 09:20:14

如果遇到循环局面，则该循环里的局面分别计目，取平均值为最终比分，例如1×2棋盘：

❶┤：局面1：黑白比分2:0
├②：白2提，黑白比分0:2
├②：局面3（❸=pass）：黑白比分0:2
├②：局面4（④=pass)：同局面3，黑白比分0:2
❺┤：局面5：黑白比分2:0
❺┤：局面6（⑥=pass）：黑白比分2:0
❺┤：回到局面1(❼=pass)

以上局面1~局面6循环往复，最终比分为(2+0+0+0+2+2)/6：(0+2+2+2+0+0)/6 = 1:1
#####

n=1：唯一空地双方禁入，黑白比分0.5:0.5，A(0)=0
#####

n=3：黑下中间终局，黑白比分3:0，A(3)=3
#####

对于n=4：
├┼┼┤
├❶②┤（②若pass或者├❶┼②，则致├❶❸┤，黑方得４分完胜，白速败）
├❶┼❸
├❶┼❸（④=pass）
├❶❺❸
⑥┼┼┤
⑥┼❼┤
⑥┼❼┤（⑧=pass）
├❾❼┤：终局，黑白比分4:0，A(4)=4
#####

不知道这样的规则对于更大的n，会不会遇到麻烦呢？

mathe · 发表于 2023-9-8 13:34:53

对于稍微大一些的n,计算复杂度还是会非常大。由于可以相互提子，相信对于稍微大一些的n, 不同状态之间的转移已经会比较复杂了，几乎对于大部分状态都需要考虑是否会出现循环局面，选择不同的路径的得分会完全不同，这个计算复杂度会非常大

hujunhua · 发表于 2023-9-10 08:44:30

根本区别在于：二维围棋有真眼假眼之分，而一维围棋没有真眼，全是假眼。

二维围棋中的真眼包括两种情况：一是围成一个眼的四个棋子属于同一个串（相互连通的所有同色棋子），二是两个串合围成两个眼（所谓鸳鸯眼）。
二维围棋中的打劫就是由于假眼的存在造成的，但假眼不多见，并且可以发展为真眼而解决，所以打劫在二维围棋中不是必然出现和普遍存在的。
但在一维围棋中，一个眼两边的棋子不可能连通，所以没有真眼。这就使得打劫是必然出现和普遍存在的。

在二维围棋中，允许隔虚提劫是为了防止假眼赖皮活，像下面这样的棋例：
4 ●●●┓
3 ●┼●○
2 ●●○○
1 ●①┷○
□A B C D
如图，白1提劫，黑棋只能pass，白棋也pass。如果禁全同而不允许隔虚提劫，黑就永远无法提回，双虚终局，白得以假眼活到最后。
在允许全同、可以隔虚提劫的情况下，黑棋可以于C1回提，白棋只有pass，黑D4提净白假眼周围的棋子.

允许隔虚提劫的一个后果是，理论上存在循环棋而不能终局。但在二维围棋中，这种情况极少见，至少比上述假眼赖皮活的情况要少见得多。
所以，在规则上宁愿允许隔虚提劫，也不愿看到假眼活棋。
如果允许隔虚提劫会导致普遍的循环棋，那二维围棋规则必定断然不许。

而在一维围棋中，由于打劫的必然性和普遍性，允许隔虚提劫几乎必然导致循环棋。

hujunhua · 发表于 2023-9-10 11:48:50

遇到循环往复，存在一个局面生存期的概念。

如果一个局面出现后，下一步不是Pass, 它就立即消失，其生存期为0.
如果一个局面出现后，下一步为pass, 下下步非pass, 其生存期为1.
如果一个局面出现后，下二步为pass, 其生存期为2. 这样的局面称为双pass局面或者双停局面。

计分时，只有生存期为2的双停局面被视为阶段性终局分别计目，取平均值为最终比分。
生存期小于2的局面，至少一方有棋可下，被视为未进入到计目状态。
如果循环中没有双停局面，判和。如果这种结果对双方都是最优，那也只能如此。

hujunhua · 发表于 2023-9-11 09:33:03

现行中国围棋规则有“第6条禁止全局同形着子后不得使对方重复面临曾出现过的局面”。
也就是不允许隔虚提劫和全同同形再现。

允许隔虚提劫和全同同形再现只是规则研究者的一种提案，目的在于消除最后阶段可能的假眼活棋。
但后果是可能导致循环棋不能终局。

其实两者可以达成妥协：不允许一个局面出现三次。（注：局面={盘面，轮走方}, 同样的盘面，先后手不同视为不同的局面）

这样可以在避免无限循环的情况下，以最小的许可循环次数最大限度地消除最后阶段可能的假眼活棋。
美中不足的是，似乎会导致早期打劫存在冗余过程，比如：
❶做劫：局面0
②提劫：局面1
❸提劫：局面0第2次
④提劫：局面1第2次
❺找劫：局面2 直接提劫会导致局面0第3次，不允许。
⑥应劫：局面3
❼提劫：局面4
其中❸④是冗余，好在是可以避免的，因为❸提前找劫并不会损失劫材。

国际象棋对于循环棋也是放到全局同形第三次出现，才予判和。

但是对于一维围棋，“不允许一个局面出现三次”与“不允许一个局面出现两次”应该没有差别。

KeyTo9_Fans · 发表于 2023-9-11 12:41:26

局面生存期的概念不用吧，每一个循环都是平等的，均应计分。

hujunhua · 发表于 2023-9-11 20:34:03

A102620
1×n棋盘上一维围棋的合法局面数。

`a_{n+3}= 3a_{n+2} - a_{n+1} + a_n`

1, 5, 15, 41, 113, 313, 867, 2401, 6649, 18413, 50991, 141209, 391049, 1082929, 2998947, 8304961,...

计算了前五项后搜索到的。n>1时，只要开始下棋，就没有空盘，所以我的计算结果本来是1, 4, 14, 40, 112, 一搜空空，于是加上空盘...

hujunhua · 发表于 2023-9-12 08:34:36

结果应该是静态双活： ├●┼○┤，比分2.5：2.5，A(5)=0
如果黑不满意，撞气进攻的话，会导向等价于pass的局面，所以不会更好.

  主变
├┼┼┼┤
├❶┼┼┤
├❶┼②┤ 1变（黑主导）
├❶❸②┤ ❸❶┼②┤ 1.1变（白主导）
④┼┼②┤ ❸❶┼②④  ├┼④②┤
├❺┼②┤ ❸❶❺┼┤  ├❺④②┤
├┼┼┼┤  ├┼┼⑥┤  ⑥┼④②┤
├┼┼┼┤  ├┼┼┼┤  ○┼○○┤
├┼┼┼┤  ├┼┼┼┤  ○⑧○○┤
├┼┼┼┤  ├┼┼┼┤  ├┼┼┼❾
├┼┼┼┤  ├┼┼┼┤  ├┼┼⑩┤

另：❶下在中心并不会更好，结果如下图，主变会导致完败，1变导致后手双活。
  主变
├┼❶┼┤
├┼❶②┤  1变（黑主导）
├┼❶┼❸  ├❸❶②┤
├④❶┼❸  ④┼┼②┤
❺┼❶┼❸  ├❺┼②┤
❺┼❶⑥┤
●┼●○┤（❼=pass)
├⑧┼○┤

账号		自动登录	找回密码
密码			欢迎注册

[提问] 一维围棋的先手优势

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

一维围棋与二维围棋的根本区别

评分

n=5

点评