六子棋與K子棋之研究

Abstract

本計畫主持人在2005 年第十一屆的國際電腦賽局發展研討會發表一篇 論文提出一系列新的k 子棋遊戲。此遊戲被一般化為 Connect(m,n,k,p,q)：黑白兩方玩家各持黑白子，黑方先下q 子，然後輪 流各下p 子在m×n 棋盤上；先連成k 子者獲勝。我們也用Connect(k,p,q) 表示Connect(∞,∞,k,p,q)。 這一系列新的k 子棋中，最重要的就是六子棋：Connect(6,2,1)，並正 式命名為連六棋，英文名稱為Connect6。六子棋的重要特性在於雙方每次 下玩一子後，其盤面子數必然比對方多一子，這平衡優勢的特性有助於其 公平性；傳統五子棋（一般規則）不具有此特性，因而有明顯的不公平現 象。 由於這是全世界第一篇論文提出六子棋及k 子棋的玩法，對研究人員來 說，這新遊戲尚有相當多未解的研究問題(open problems)，是一個相當 值得研究的一系列問題。本計畫就是要來研究探討這些問題，目的如下： .. 在六子棋方面： .. 研究設計達專業棋士棋力之六子棋人工智慧程式。 .. 研究如何證明某些六子棋棋型為必勝的理論，並用之證明新的必勝 棋型（詰棋）。 .. 研究脫離戰場理論，來輔助分析公平性。 .. 用上述程式來產生詰棋及開局定石，提供六子棋初學者學習。 .. 在k 子棋方面： .. 研究設計一般化k 子棋人工智慧程式。 .. 研究如何證明某些k 子棋棋型為必勝的理論，並用之證明一些必勝 棋型。 .. 證明出一些Connect(k,p,q)遊戲是否為必勝。 .. 研究並找尋其他潛在公平的k 子棋。 本計畫的工作項目分三年如下： 第一年 1. 收集及分析相關資料。 2. 研究設計基本的六子棋人工智慧程式。 3. 研究提出適用於六子棋的新null-move heuristics 方法，並以此證明 六子棋一些棋型為必勝棋型。 4. 研究六子棋的脫離戰場問題，並證明Connect(6,2,2)是否為黑必勝。 5. 研究設計適用於更大棋盤或甚至無限大棋盤的六子棋程式。 第二年 6. 提出並設計適用於六子棋的新dependency-based search 技術。 7. 研究設計適用於六子棋的proof-number search 技術。 8. 研究利用程式之大量搜尋，來產生新的六子棋詰棋或開局定石。 9. 研究設計一般化的k 子棋人工智慧程式。 第三年 10. 研究提出適用於k 子棋的一般化null-move heuristics 方法。 11. 證明一些Connect(k,p,q)遊戲的公平性。 12. 研究提出適用於k 子棋的dependency-based search 及proof-number search 技術。 13. 研究並找尋其他潛在公平的k 子棋。 14. 利用程式之大量搜尋，來產生新的k 子棋詰棋或開局定石。 對這些新遊戲尤其是六子棋，由於其規則簡單、遊戲公平、及玩法複雜， 有機會成為一項由台灣研究發展出，並與五子棋一樣普及全世界的遊戲。 這對提升國家形象及知名度亦有相當的助益。