六子棋時序差異學習之研究

Temporal Difference Learning in Connect6

蔡心迪(Hsin-Ti Tsai)

指導教授 ： 吳毅成

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

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

摘要

六子棋是吳毅成教授2005年發表的一個棋類遊戲，近年來已經發展成為世界性的遊戲。而NCTU6則是一個六子棋的AI程式，曾獲得兩屆電腦奧林匹亞賽局競賽六子棋組金牌，以及在人機賽中擊敗許多棋士。
這篇論文的目的是研究如何應用時序差異學習(Temporal Difference Learning)於六子棋程式上。由於六子棋的一些遊戲特性和其他遊戲不同，因此這篇同時也討論了時序差異學習在六子棋上有哪些值得注意的議題。
根據我們的實作經驗，時序差異學習演算法能讓新的程式對上原本的程式NCTU6有57.95% 的勝率，顯示NCTU6確實增加了棋力。新的程式也在2011 TCGA六子棋組獲得了金牌的好成績。

關鍵字

六子棋 ； 時序差異學習 ； alpha-beta搜尋 ； 迫著空間搜尋

並列摘要

The Connect6 game, first introduced by Professor I-Chen Wu in 2005, now becomes one of the popular games in the world. NCTU6 is a Connect6 AI program developed by our team, has won gold medal in ICGA tournaments twice and defeated many professional players in Man-Machine Connect6 championship.
The main purpose of this thesis is to research temporal difference learning in Connect6. Some characteristics of Connect6 are different from other games, so we also discuss the issues of temporal difference learning in Connect6.
According to our practical experience, the new program with temporal difference learning reaches a 57.95% win percentage against original program. This shows that the new method successfully improves NCTU6. The new program has also won gold medal in 2011 TCGA tournaments.

並列關鍵字

Connect6 ； temporal difference learning ； alpha-beta search ； threat-space search

參考文獻

[2] D.E. Knuth and R.W. Moore, “An analysis of alpha-beta pruning,“ Artificial Intelligence, 6:293–326, 1975.

[4] H.J. van den Herik, J.W.H.M. Uiterwijk and J.V. Rijswijck, “Games solved: Now and in the future,” Artificial Intelligence, vol. 134 (1-2), pp. 277–311, 2002.

[5] I.-C. Wu and D.-Y. Huang, “A New Family of K-in-a-row Games,” Advances in Computer Games Conference (ACG2005), Taipei, Taiwan, 2005.

[8] J.R. Slagle and J.K. Dixon, “Experiments with some programs that search game trees,” JACM 16, 2 189-207, 1969.

[12] Ludoteka website. Available at http://www.ludoteka.com/