一维围棋的先手优势

hujunhua · 发表于 2023-9-12 10:10:09

金角银边草肚皮，对一维围棋也有效。├❶┼┼ 总是不错的开局。
相应地，白也应该尽快占领(n-1)位，得到右端 1 目空。

mathe · 发表于 2023-9-12 10:31:32

除了一方控制所有格子的情况，还存在其它不会继续循环的局面吗？

hujunhua · 发表于 2023-9-12 10:55:15

mathe 发表于 2023-9-12 10:31
除了一方控制所有格子的情况，还存在其它不会继续循环的局面吗？

依行棋规则不存在，但考虑胜负，决策取舍，就可能存在。比如10#的双活。

KeyTo9_Fans · 发表于 2023-9-12 13:00:10

hujunhua 发表于 2023-9-12 08:34
结果应该是静态双活： ├●┼○┤，比分2.5：2.5
如果黑不满意，撞气进攻的话，会导向等价于pass的局面，所 ...

我用程序暴力枚举出来的策略和你这里的分析结果一样，

唯独1.1变（白主导）里的这个局面：

├┼┼┼❾

我的程序认为白⑩应该这样下：

├⑩┼┼❾

才是白方的最佳策略。

如果双方都采用最佳策略继续下下去，完整的变化如下表所示：

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

复制代码

这个循环节的长度是16

由于黑方在这个循环节里的平均得分低于2.5，实战时黑方不会主动进入这个循环

hujunhua · 发表于 2023-9-12 13:35:28

KeyTo9_Fans 发表于 2023-9-12 13:00
我用程序暴力枚举出来的策略和你这里的分析结果一样，
唯独1.1变（白主导）里的这个局面：├┼┼┼❾
我的程序认为 ├⑩┼┼❾ 才是白方的最佳策略。

这不否定15#的分析过程。
15#的推演结果表明黑若撞气进攻，白至少能反转局面。至于使局面反转是不是最优策略，暂且不论。
黑若在白反转前没有获利，就不应该进攻，因为白反转后pass, 可以不蹈黑的覆辙，黑有损无益。
黑若在白反转前有所获利，也会在被反转后如法索还，最终仍然一无所获。
所以，黑应该pass保持双活局面。
如果存在比反转局面更优的白方策略，黑就更不应该挑战双活了。

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你觉得还有哪个局面，他们的应对方案欠妥呢？

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

hujunhua · 发表于 2023-9-13 02:30:02

【定义】（公活终局）双方棋子最大限度地占满棋盘又都有2气的局面。
【公活终局定理】在公活终局下不存在比pass更优的策略。(直觉，未经证明

)

n≥5时，1×n棋盘上的公活终局数`a_n=2C_{n-4}^1+2C_{n-5}^2+\cdots+2C_{n-3-k}^k+\cdots+2C_1^{n-4}=2F_{n-2}-2`
OEIS序列号A019274，F_n为斐波那契数。
这些公活终局覆盖了从2：n-2到n-2：2的各种半整数比分。

既然存在任意半整数比分的公活终局和一个最优策略比分，
那么假定双方都力图避免使棋局陷入无穷循环，
都以达到最优策略比分的某个公活终局为目标，
但在有机会时不惜导致无穷循环也要争取更好的比分。
这样是否足以导向一个最优策略比分的公活终局？

诚如是，则耿耿于循环不得终局如我者稍可释怀。

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，双方会不会一直佛系下去呢？

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

hujunhua · 发表于 2023-9-14 12:18:16

这种佛系策略里这么多一间跳可能有问题。
一维围棋的高效棋形应该是二间跳。
大于二间跳不会更有效，因为产生了双活空间，能被打入、掏空。
比如 n=9 的佛系下法
·❶❺❸·④⑥②·
·●●●·○○○·
·●●●·○○○·
·●●●·○○○·

❸一间跳留给④一间跳的空间，导致和棋。
❸应该二间跳，佛系应对如下：
•❶❺•❸•④②•
•●●•●•○○•
•●●❼●•○○•
验证一下？白若不甘被压缩，进行抗争
•●++●④+○•
•●⑥+●+❺○•
•●⑥+●+❺+❼
⑧+⑥❾●+❺+❼
⑧+⑥++⑩❺+❼
⑧+⑥+❶+❺+❼
⑧+⑥+❶+❺②•
•❸⑥+❶+❺②•
•❸⑥+❶④+②•
•❸+❺❶④+②•
•❸⑥++④+②•
•❸+❼+④+②•
⑥借劫打入二间跳，抗争成功！

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

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

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

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

点评

公活终局定理与公活终局猜想

评分