六子棋中一個結合迫著搜尋的防禦性策略

A Defensive Strategy Combined with Threat-Space Search for Connect6

劉雲青(Yun-Ching Liu)

指導教授 ： 林順喜

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2009年)

摘要

摘要

k 子棋相關的研究一直有許多有趣的研究成果被發表出來，而其中於2005年所提出的六子棋則格外受到注目。從2006年開始，六子棋一直被列為ICGA電腦奧林匹亞中重要的比賽之一，投入六子棋的研究和參與比賽的團隊逐年增加。

這篇論文裡，從簡介現今應用在六子棋的相關技術和研究成果開始，接著提出六子棋上的一個防禦性策略以及一個策略性的審局方案。迫著搜尋演算法在電腦六子棋中有相當重要的地位，論文裡亦提出提升其實作上效能和精確度的技術。防禦性策略和迫著搜尋的結合也會被探討。

防禦性策略和迫著搜尋的結合的表現足以跟現今的一些頂尖的六子棋軟體分庭抗禮 ，可見其為一個相當有效的方法。我們整合這些技術所實作出的程式Kagami，於第十四屆ICGA 電腦奧林匹亞中獲得第四名。

關鍵字

六子棋 ； k子棋 ； 迫著搜尋 ； 人工智慧

並列摘要

Abstract

The study of k-in-a-row games has produced a number of interesting results,and one of its sub-category Connect6 proposed in 2005 has been of particular interest. Since 2006, Connect6 has been included as one of the major com-
petition in the ICGA Computer Olympiad, and is gaining more popularity every year.

In this thesis, we briefly review current methods applied in Connect6 and related results. A defensive strategy is introduced along with a more strategically sensitive evaluation scheme. Threat-space search is an important algorithm applied in Connect6, some techniques for gaining more efficiency and accuracy will be introduced. The integration of the defensive strategy
and threat-space search will also be investigated.

The combination of the defensive strategy and threat-space search is proved to be effective, and is able to compete with other top Connect6 programs. The program Kagami, which was implemented with these methods, won the fourth place in the 14th Computer Olympiads.

並列關鍵字

Connect6 ； k-in-a-row ； Threat-space Search ； Artificial Intelligence

參考文獻

[1] J. MaCarthy, “Chess as the drosophila of a.i.”

[2] H. van den Herik, J. Uiterwijk, and J. Rijswijck, “Games solved: Now and in the future.” Artificial Intelligence, vol. 134, pp. 277–311, 2002.

[5] L. Allis, H. van den Herik, and M. Hutjens, “Go-moku solved by new search techniques,” Computational Intelligence, vol. 12, pp. 7–23, 1996.

[6] L. Allis, “Searching for solutions in games and artificial intelligence,” Ph.D. dissertation, University of Limburg, Maastricht, 1994.

[8] E. Berlekamp, J. Conway, and R. Guy, Winning ways for your mathematical plays, Volume 2. Academic Press, 1982.