演算法六子棋

① 我是大一，報名參加我校計算機博弈大賽，項目是六子棋，請各位高手指點啊~~

學習c語言推薦《PROGRAMING C》外國人寫的，世界上經典的C語言入門書籍。另外學習以下數據結構和經典演算法。

② 五子棋先下的人一定贏

五子棋先下的一定贏嗎?有什麼演算法原理可以說明這個問題?下面是有五子棋解法，歡迎參閱。

通常大家玩的五子棋分為帶禁手和不帶禁手兩個版本(前者一般稱之為五子棋Gomoku，後者稱之為連珠Renju)，無論哪一個版本，先手黑棋均必勝。

所謂黑必勝的意思是，只要黑棋按照一定的方式下，白棋選擇棋盤上的任何一個點都不可能贏棋。

其實在電腦出現之前，五子棋的玩家就發現黑棋採取某些開局贏面的極大，也懷疑有先手必勝的方法。但沒有人能夠真正“證明”出來白棋無論怎麼下都是必敗的——這個結論最終還是通關電腦來證明的。

其中不帶禁手是1992年VictorAllis通過編程證明黑必勝的，禁手規則是只針對黑棋的，簡而言之是黑棋只允許使用沖四活三這一種贏法(當然不排除白棋故意沖四不擋這種方法)。設計的目的也是為了限制黑棋的巨大優勢，白棋也多了逼禁手這兒一種贏法。但後來人們也逐步發現帶禁手後，黑棋依然似乎能不敗。直到後來，也有人證明，帶禁手執黑也可以必勝。

帶禁手的是 2001 是 Janos Wagner 第一次證明黑必勝的，這個後面的證明比前面的證明要強很多，因為按照帶禁手的走法，不帶禁手也一定必勝，但倒過來未必。

這還不說，為了進一步削弱黑棋的優勢，國際上推出五手兩打(就是黑棋的第三步需要下兩個點，但由白棋挑選讓其下較弱的哪一個)的規則。可是人們發現黑棋帶禁手依然是必勝。也就是說，黑棋必勝不僅僅有一種方法，而是至少有兩種以上(來回應各種變種的第四步)。

從實踐的角度來講，網上是可以搜索“地毯譜”(尤其是花月和蒲月都是五手兩打必勝)，一般在幾百兆左右，可以用renlib軟體打開，所謂地毯譜的意思就是黑棋會指定下法，但白棋每一步都可以選擇棋盤任意位置，最後黑棋必勝。也就是說，只要按照此棋譜下棋，五子棋世界冠軍都一定會輸給你。

所以正式的比賽才會有三手交換五手兩打，山口規則(五手n打)這些復雜的規則來平衡比賽。但這些規則也是逐漸被人破解，五子棋的比賽已經很大程度不是在考驗自己的臨場發揮，而是考驗選手對於各種開局的記憶情況。

另外針對有人質疑既然五子棋必勝，為什麼還要玩：

必勝並不代表去網上黑先開浦月、花月就一定人擋殺人，佛擋殺佛。必勝的各種分支套路也不是那麼容易記住的，諸位可以和tito2014或者弈心執黑體驗一下(高手繞道)。所以各種對戰平台上，就算是在非禁手區拿到勝率遠超 50%也不是不可能的。

另外不帶禁手的五子棋是屬於一類更為普遍的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是先手必勝。m,n,k游戲只有先手必勝和平局兩種結果。由於每下一個子都一定會對下子一方那一方有優勢，所以可以通過反證法證明m,n,k游戲里不可能有後手勝利的情況。如果後手有勝利的方法，那麼先手可以提前“借鑒”過來實現必勝(Strategy stealing)。

另外除了規定復雜的開局和禁手規則，其實還有一個出路：

除了採取對先手採取各種限制的方法，2003 年被吳毅成教授發明的連六棋(Connect6)也非常類似五子棋，難度很高，但六子棋沒有先手優勢——因為每一步都下兩個子，除了第一步下一個子，這樣保證雙方每次下棋時，都可以比對方多一個子。AI目前計算的結果也是，沒有發現先手比後手有更大的優勢。

既然雙方都沒有優勢，六子棋下滿整個(圍棋19x19棋盤)都沒有分出高低都是有可能的。(這個游戲已經不再是m,n,k游戲了)