六子棋之區域證明搜尋

Abstract

西元2005年，吳毅成教授提出了一系列新的K子棋遊戲，在這類遊戲中，六子棋特別引起高度的關注。本論文提出了一種新的迫著證明搜尋方式，稱之為區域證明搜尋（RZOP），以Thomesn所提出的lambda搜尋為基礎，此方法會建構出相關證明區域。區域證明搜尋是一種全新、通用而且優雅的方法。本論文已成功有效的解出許多六子棋盤面的勝敗，其中包含多個開局，例如米老鼠開局，在過去是很受歡迎的一種的開局。除了解題，本論文進一步改進區域證明搜尋的效率，稱之為區域內線段證明搜尋（SRZOP），此方法有效加速證明盤面勝敗所需花費的時間。根據實驗數據中12種開局的統計結果，區域內線段證明搜尋可加快2.04倍的時間。最後，附錄F展示作者和交大六號（六子棋AI程式）的相關比賽成果。例如在2008年第十三屆國際奧林匹亞電腦賽局競賽的六子棋組，交大六號輕量版獲得冠軍，作者也因此榮獲交大98年度（春季）重要學術獎；第二屆人腦對電腦六子棋大賽，交大六號更得到8勝0敗的好成績。

Wu and Huang presented a new family of k-in-a-row games, among which Connect6 (a kind of six-in-a-row) attracted much attention. For Connect6 as well as the family of k-in-a-row games, this thesis proposes a new threat-based proof search method, named Relevance-Zone-Oriented Proof (RZOP) search, developed from the lambda search proposed by Thomsen. The proposed RZOP search is a novel, general and elegant method of constructing and promoting relevance zones. This thesis solved effectively and successfully many new Connect6 game positions, including several Connect6 openings, especially the Mickey-Mouse Opening, which used to be one of the popular openings before we solved it. In addition to solvability, this thesis further improves the RZOP method, named Segmented Relevance-Zone-Oriented Proof (SRZOP) search, which speeds up the time to solve Connect6 game positions. The experimental results show 2.04 speedups in total to solve 12 openings. Finally, this thesis demonstrates records of our Connect6 program, NCTU6, which won the gold in the 13th Computer Olympiads in 2008; and also won eight games and lost none against top Connect6 players in Taiwan in 2009.