一维围棋的先手优势

KeyTo9_Fans

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

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

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

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

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

majer

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

KeyTo9_Fans

如果遇到循环局面，则该循环里的局面分别计目，取平均值为最终比分，例如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

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

hujunhua

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

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

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

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

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

hujunhua

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

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

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

hujunhua

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

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

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

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

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

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

KeyTo9_Fans

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

hujunhua

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

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

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

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