六子棋詰棋及開局定石之自動產生系統之研究與設計

Abstract

自我們發表全世界第一篇六子棋論文至今僅兩年多，六子棋的歷史與其 他棋種如象棋、圍棋、西洋棋有數百年、甚至上千年歷史相比，仍屬相當 年輕的，因此專家的詰棋題目與開局定石的數量仍相對較為缺乏。 為了加速六子棋的推廣與普及，此計畫除了持續研發新的六子棋搜尋技 術外，我們將研究發展詰棋自動產生及開局定石自動產生之系統與技術。 詰棋產生系統將可用來大量產生詰棋題目，提供六子棋棋士自我練習及自 我評估棋力之用。開局定石產生系統，將可用來大量產生開局定石，提供 六子棋高段棋士研究更深入的各種開局下法。由於開局定石產生系統相當 耗時，我們將發展平行處理技術來加快處理速度。此外，我們亦將研究如 何將Monte-Carlo tree search 應用於六子棋搜尋及六子棋開局定石產生 系統之可行性。相信這對六子棋開局定石產生系統的自動化，尤其重要。 本計畫的工作項目分三年如下： 第一年 1. 收集及分析搜尋技術及高段棋士棋譜等相關資料。 2. 研究設計六子棋之搜尋技術，主要在加入dependency-based search 技術。 3. 研究分析六子棋詰棋的特性，並與現有高段棋士訂出各種不同難度等級 的標準。 4. 研究發展新搜尋技術來設計詰棋自動產生器。 5. 實作詰棋自動產生器之程式。 6. 應用上述程式產生詰棋並分類之，並公佈於網路上。 第二年 7. 收集及分析搜尋技術及高段棋士棋譜等相關資料。 8. 研究設計六子棋之搜尋技術，主要在加入 proof-number search 技術。 9. 研究設計六子棋開局定石產生器之系統架構，含平行處理等。 10. 實作此六子棋開局定石產生器之系統，包含提供棋士產生開局定石的 GUI。 11. 研究設計將六子棋開局定石產生器之平行處理架構，應用於詰棋產生 器。 12. 應用上述程式產生定石，並公佈於網路上。 第三年 13. 收集及分析搜尋技術及高段棋士棋譜等相關資料。 14. 研究設計六子棋之搜尋技術，主要在加入Monte-Carlo tree search 技術。 15. 研究將 Monte-Carlo tree search 技術，加入六子棋開局定石之產生器。 16. 實作這開局定石產生系統，使定石的產生更為自動化。 17. 分析 Monte-Carlo tree search 技術對開局定石產生系統自動化的效能。 由於六子棋，目前極為缺乏足夠的開局定石及詰棋，本計畫所大量產生出 之開局定石及詰棋，將對六子棋的普及與推廣，有相當大的助益。六子棋 是一項由台灣自行研究發展出的棋類遊戲，更深層地普及於全世界，也將 有助於提升國家正面形象及知名度。

When compared with other games, such as Go, Chess, Chinese Chess, the game Connect6 has still been very young, since we presented the first paper about it in the world in 2005. Therefore, the number of puzzles and the number of openings (Josekis) are still relatively small. In addition to the development of Connect6 search techniques, this project will also develop new search techniques for the automation of puzzle generation and opening generation. Generating a large number of puzzles will provide new Connect6 players with exercises and strength estimation on their own. Generating a large number of openings will help players (especially for professionals) understand more about the Connect6 openings and thus learn more skills from these. Finally, we will study the technique of Monte-Carlo tree search, analyze the possibility of applying the technique to Connect6 search and Connect6 opening generation, and compare the performance of the search technique with that of the traditional search techniques. In this project, the research items are separated into three years as follows. First-year project: 1. Collect and analyze the related data, such as papers for search techniques and game records played by professionals. 2. Study and design the new search technique, dependency-based search. 3. Study the features of Connect6 puzzles, and define the difficulty levels of puzzles. 4. Study and develop new search technique for the automation of puzzle generation. 5. Implement the automation system for puzzle generation. 6. Apply the above system to generate puzzles and publicize them in the web. Second-year project: 7. Collect and analyze the related data, such as papers for search techniques and game records played by professionals. 8. Study and design the new search technique, proof-number search. 9. Study and design the system architecture for the automation of opening generation. The system architecture includes the parallelization of search. 10. Implement the automation system for opening generation. 11. Apply the above system to generate openings and publicize them in the web. 12. Also apply the above system to generate puzzles. Third-year project: 13. Collect and analyze the related data, such as papers for search techniques and game records played by professionals. 14. Study and design the new search technique, Monte-Carlo tree search. 15. Study to apply the Monte-Carlo tree search technique to the automation system for opening generation. 16. Implement the above item and make the generation of opening more automatic. 17. Analyze the impact of this technique on the automation of opening generation. Due to short of puzzles and openings for Connect6, the success of this project will result in a great number of puzzles and openings, which are of great help to promote and popularize Connect6. Since Connect6 is a game initiated from Taiwan, popularization of Connect6 will also be of great help to promote the positive image of our country.