國立臺灣師範大學博碩士論文全文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	劉雲青 Yun-Ching Liu
論文名稱：	六子棋中一個結合迫著搜尋的防禦性策略 A Defensive Strategy Combined with Threat-Space Search for Connect6
指導教授：	林順喜 Lin, Shun-Shii
學位類別：	碩士 Master
系所名稱：	資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2009
畢業學年度：	97
語文別：	英文
論文頁數：	73
中文關鍵詞：	六子棋、k子棋、迫著搜尋、人工智慧
英文關鍵詞：	Connect6, k-in-a-row, Threat-space Search, Artificial Intelligence
論文種類：	學術論文
相關次數：	點閱：180 下載：4
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

摘要

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

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

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

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.

Contents

Chapter 1 Introduction  7


  1.1 Connect6    . . . . . . . . . . . . . . . . . . .  8
  1.2 Goal and Motivation . . . . . . . . . . . . . . .  8
  1.3 Thesis Outline . . . . . . . . .. . . . . . . . . 10

Chapter 2 Related  Results     11

  2.1 The Family of k-in-a-row Games . . . .  . . . . . 11
  2.2 Variants of k-in-a-row Games. . . . . . . . . . . 13
      2.2.1 Higher-Dimensional Boards . . . . . . . . . 14
      2.2.2 The Connect(m, n, k, p, q) Family . . . . . 15
  2.3 The Complexity of Connect6 . . .. . . . . . . . . 15

Chapter 3 A Defensive Strategy for Connect6        17

  3.1 Locality in Connect6 . . . . . . . . . . . . . . 17
  3.2 An Evaluation Scheme . . . . . . . . . . . . . . 20
       3.2.1 Influence of a Stone . .  . . . . . . . . 21
       3.2.2 Evaluation of a Half-move . . . . . . . . 22
       3.2.3 Comparison to Current Evaluation Techniques  28
   3.3 A Defensive Strategy . . . . .  . . . . . . . . 29
   3.4 Experimental Results .  . . . . . . . . . . . . 31

Chapter 4 Threat-Space Search              34

   4.1 Threat-Based Strategy . . . . . . . . . . . . . 34
   4.2 Threat-space Search . . . . . . . . . . . . . . 35
   4.3 Implementation Issues . . . . . . . . . . . . . 38
       4.3.1 Defining Threats in Linear Patterns . . . 38
       4.3.2 Finding Defensive Moves . . . . . . . . . 39
       4.3.3 Linear Pattern Table. . . . . . . . . . . 43
       4.3.4 Combining Information . . . . . . . . . . 44
   4.4 Combining Search with Defensive Strategy .  . . 47
   4.5 Experimental Results . . . . . . . . . .  . . . 49

Chapter 5 Conclusions and Further Development

   5.1 Conclusions . . . . . . . . . . . . . . . . . . 53
   5.2 Further Development . . . . . . . . . . . . . . 54

Appendix A Kagami at the 14th Computer Olympiad     55
Appendix B Selected Games  59

Bibliography  68
                                

[1] J. MaCarthy, “Chess as the drosophila of a.i.”
Computers, Chess and Cognition, pp. 227–237, 1990.

[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.

[3] I.-C. Wu and D.-Y. Huang, “A new family of k-in-a-row games,” in the 11th Advances in Computer Games Conference (ACG’11), Taipei, Taiwan, September 2005.

[4] I.-C. Wu, D.-Y. Huang, and H.-C. Chang, “Connect6,” ICGA Journal, vol. 28, no. 4, pp. 234–241, Decemeber 2005.

[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.

[7] D.-Y. Huang, “The study of artificial intelligence programming for gobang-like games,” Master’s thesis, National Chiao Tung University, June 2005.

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

[9] J. Uiterwijk and H. van den Herik, “The advantage of the initiative,”Information Sciences, vol. 122(1), pp. 43–58, 2000.

[10] T. Zetters, “Problem s.10 proposed by r.k. guy and j.l. selfridge,” Amer. Math. Monlthly, vol. 86, solution 87(1980), pp. 575–576, 1979.

[11] L. V. Allis and P. Schoo, “Qubic solved again,” Heruistic Programming in Artificial Intelligence 3: The Third Computer Olympiad, pp. 192–204, 1992.

[12] A. W. Hales and R. Jewett, “Regularity and positional games,” Transactions of the American Mathematical Society, vol. 106, pp. 222–229, 1963.

[13] S. W. Golomb and A. W. Hales, “Hypercube tic-tac-toe,” More Games of No Chance, vol. 42, pp. 167–180, 2002.

[14] S.-H. Chiang, I.-C. Wu, and P.-H. Lin, “On drawn k-in-a-row games,” in the 12th Advances in Computer Games Conference (ACG12), Pamplona, Spain, May 2009.

[15] “Connect6 homepage,” http://www.connect6.org.

[16] S.-Y. Liou, “Design and implementation of computer connective 6 program x6,” Master’s thesis, National Dong Hwa University, July 2006.

簡易檢索 / 詳目顯示

相關論文