適用於六子棋之平行PNS研究

Parallel Proof Number Search for Connect6

詹宜智(Yi-Chih Chan)

指導教授 ： 吳毅成

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2009年)

https://doi.org/10.6842/NCTU.2009.00858

摘要

六子棋是在 2005 年所發表的新棋類遊戲，由於六子棋是很新的遊戲，需要更多的開局庫和詰棋題目。本論文發展了一套六子棋證明系統，結合阿法貝塔搜尋(Alpha-Beta Search)和證明數之搜尋(Proof Number Search)，能展開較少節點，並快速證明兩人對局遊戲之勝負。同時，此系統亦可在網格運算系統上，加快計算速度。本系統所產生的盤面勝負結果，除了能提供開局庫參考，還能提昇六子棋電腦程式的強度。

關鍵字

六子棋 ； 阿法貝塔搜尋 ； 證明樹之搜尋 ； 開局庫

並列摘要

Connect6 was introduced in 2005. We need to develop more openings and puzzles since Connect6 is a very young game. This thesis develops a proof system for Connect6. It combines alpha-beta search and proof number search to expand less nodes and prove two-person games more quickly. Grid systems are also used to accelerate computation. The results of proof system are not only put into the opening database but also improve the strength of Connect6 program.

並列關鍵字

Connect6 ； Alpha-Beta Search ； Proof Number Search ； Opening DataBase

參考文獻

[7] Allis, L. V. “Proof-Number Search” Artificial Intelligence

[10] Little Golem, available at http://www.littlegolem.net/jsp/

[15] Pente, available at http://pente.org/

[16] Saito, J-T., Winands M. H.M., and van den Herik, H.J., “Randomized Parallel Proof-Number Search”, ACG12-2009

[17] Seo, M., Iida, H., Uiterwijk, J.W.H.M. “The PN*-Search Algorithm: Applications to Tsume-Shogi” Artificial Intelligence