對圍棋和日本將棋而言，有哪些構造超長棋局或詰棋的方法？

12-07

從圍棋說起。眾所周知因禁止全局同型，N路棋盤棋局最大長度不超過O(3^(N^2))，但如何構造儘可能長的符合圍棋規則的棋局則很可能是非平凡的。
問題一：能構造出、符合圍棋規則的對局的最大長度是多少？

如果我們只考慮詰棋，即雙方的每一步都是為達成某一目標的必然選擇，問題無疑會更加困難。一個著名的長詰棋見Q-41011 - 題庫，其中黑方意圖殺死白大塊而白方則相反。棋局共3603手；用同樣的思路很容易構造出N路棋盤中長O(N^3)的詰棋。
問題二：能否構造出的圍棋詰棋的最大長度是多少？上述實例能否改進？

日本將棋似乎有著更多也更長的詰棋，例如「龍の顎」補足情報，其中列出的最長詰棋為49909手。題主不懂日本將棋，但有趣的是以下網址對其中某一詰棋的手數計算：壽限無の完全限定化案を漸化式で: まんようてい，其中竟然出現了指數函數。從遞歸關係上來看，可能是該詰棋的結構內含了某些指數增長的模型如Hanoi塔(只是猜測)。
問題三：上列詰將棋超長手數的原理是什麼？對N路棋盤可以構造出指數長度的詰將棋嗎？其思路可能被應用到圍棋中嗎？

強答一個。
閱讀時可以跳過下劃線的部分，不影響理解。

先說問題一。

首先明確規則。傳統的圍棋規則在數學上各有不明之處，因此約定採用以下規則:
1.PSK(Positional Superko), 即禁止使對方面對已經出現過的局面(Position),簡稱禁全同。禁全同規則保證了棋局長度的有限。這個規則區別於另一種禁全同， SSK（Situational Superko). 換句話說，如果我們把出現局面p，且輪到黑方下的情形(Situation)記作(p,B), 那麼在PSK規則下，在一盤已經出現過(p,B)的棋局中，下出一步造成(p,W)的棋是犯規的，而在SSK規則下，這步棋不犯規。
採用PSK的好處是，我們只需要局面就可以了，省去了討論(p,B)和(p,W)的麻煩。
2.允許棄手（停一招），且兩棄終局。但停手不計入總手數。
3.允許塊子自盡（顆子自盡違反PSK）。

在此規則下，我們可以把不同的局面看作節點（node），並建立一個有向圖G(m,n) (m, n為棋盤邊長）。根據設定，V(G)是所有可能局面的集合。方便起見，定義L(m,n)=|V(G(m,n)|.
John Tromp已經證明 L(19,19)=2081681993819799846994786333448627702865224538845305484256394
5682092741961273801537852564845169851964390725991601562812854
6089888314427129715319317557736620397247064840935 ~2.08*10^170.
同一篇論文里有更為一般性的漸近結果的討論，在此按下不表。

根據設定，對於 $forall p,qin V(G), {pq} leftrightarrow$ 對局任意一方的一次行動能把局面p變為局面q。
那麼尋找最長棋局的問題就轉化成了在G 中尋找最長簡單道路(simple path, 即沒有重複節點的path)的問題。
這個問題「顯然」是非平凡的。我們先從相對簡單的情形開始考慮。
考慮m=n=2的情況，即2*2棋盤。

L(2,2)=57。可以把57個局面分成13個symmetry class，然後得到上面的簡化圖。
一個相對簡單的問題是，G(2,2)中是否存在Hamiltonian path?換句話說，是否存在一個棋局可以遍歷這57個局面？
答案是否定的。考慮第一行第二個和第三行第一個這兩個symmetry class。將這兩者看成一個整體，它們一共有10種局面，但是總的outdegree=8，即出路只有8條。那麼一個Hamiltonian path 就不可能實現了。
據此，我們也可以證明，當m,n&>=2時，不存在能夠遍歷所有局面的棋局。

通過窮舉，John Tromp證明了2*2棋盤上的最長棋局是48步，即longest path最多可以經過49個節點。(這也是很不容易的，2*2棋盤上的總棋局數達到了~4*10^11）。
我嘗試在棋盤上擺了一下，暫時還沒有擺出48步的。。

然而，3*3棋盤上的相同問題的難度立即大增。L(3,3)=12675. 窮舉幾乎變得不可能。實際上這還是一個未解問題。John Tromp通過隨機採樣得到的最長棋局是521步，他因此猜測實際上的最長棋局應當不超過1000步。

對於n*n的棋盤，可以說這是longest path problem的一個並沒有什麼特殊性的特殊情況。Longest path problem。longest path problem 不僅本身是NP-Complete, 而且甚至難以估計一個漸近的結果，因此對於19路棋盤，這實在是一個很難解的問題。不過，我們仍然可以通過構造得到一個確定的下界 $O(n^22^{n^2})$ .（此處待更新）

對於問題二和三，看了問題描述里的那個死活題。。雖然以前見過，然而在下真的輸了。。能構造出一個O(n^3)長度的死活題真的是腦洞開得夠大了。。
因為「死活題」這個概念很難被良好定義，「最長死活」這個問題實在是無法透過數學辦法去解決了。
（參考文獻：
J. Tromp G. Farnerback, Combinatorics of Go http://tromp.github.io/go/gostate.pdf）

王手，等同於中國象棋里的將軍。
詰み，等同於中國象棋里的將死。
必至，表示某個局面存在一種情況，即其中一方連續王手，另一方不論如何應對，最終都會被詰死。此時這個局面叫做詰棋。而找到這一系列手數最多的王手與應對，叫做這個詰棋的解。

相比其他棋類，將棋里的打入機制，能令詰棋變的非常複雜。而將棋中的千日手規則（即不能同一棋盤局面出現三次）對於構造詰棋來說是一個主要的約束條件。

而構造詰棋的關鍵在於，
1. 先手方每手都是王手
2.後手方的應對讓自己盡量晚死
3.每一局面都是必至

構造超長詰棋主要需要考慮三個部分，循環部，計數部以及結束部。

循環部
是步數的主要構成部分，循環部需要能在經歷一系列過程後恢復原樣。

計數部
由於千日手規則，循環部在循環之後需要棋盤局面不同，計數部的作用就是在循環部循環之後，作出變化。並為最後過渡到結束部做準備。

結束部
在計數部計滿之後，結束整個詰棋過程。

目前最長的例子是ミクロコスモ(microcosmos)以後有時間更新。

將棋的循環往複（將棋稱「千日手」）分兩種，一種是不關乎將軍（將棋稱「王手」）的，另一種是關乎將軍的，前者如果雙方都不想改變下法，此局平局，後者將軍方（將棋稱「攻方」）必須先行改變下法，否則判負。可見這兩種都無法應用到詰將棋中來延長手數。
然而無論圍棋還是將棋都沒有不允許在不同地方下相似下法的規定，可見不論是你題中的101圍棋網的Q41011還是韓花花說的橋本先生的詰將棋用的都是這樣的方法（在不同的地方下相似下法）。然而不同的是，橋本的詰將棋已經（至少是行動範圍上）用到了整個棋盤，而Q41011並沒有用到整個棋盤，所以我覺得如果後者黑棋的大龍能再折兩下似乎是能做的更長的（當然我並不想嘗試，畢竟我懶捂臉）

什麼意思啊，圍棋三劫連環算是無窮步？