六子棋程式強度改進之研究

我們過去曾發展過一個六子棋程式稱為交大六號(NCTU6)，該程式以及其延伸版本，在所有國內外電腦對局競賽的六子棋項目中均獲得冠軍，也在多次人機競賽中擊敗許多頂尖高段棋士。然而在長時間思考的棋賽中，發現即使每手可計算數小時，卻仍然有些著手明顯不佳，進而造成輸棋。本論文藉由這些不佳著手分析NCTU6與工作層級的弱點，並且提出靜態調整、動態調整、提升走步排序品質與活五處理等改良方法。實驗結果顯示，使用靜態調整、動態調整的版本對原程式勝率達到59.6%。使用提升走步排序品質後，對前面改良過版本勝率達58.95%，且能使NCTU6在某些先前下出不佳著手的盤面中，找出我們認為理想的著手。其它的調整也對不佳著手有所改良。

關鍵字

六子棋；電腦對局；人工智慧

並列摘要

NCTU6 is a Connect6 AI program developed in our lab. NCTU6 and its variations won gold medals in ICGA tournaments many times and also defeated many expert players in Man-Machine Connect6 championships. However, we observed that in a few cases, even if hours are given to play, NCTU6 did not play moves well which led to losing the game. By analyzing these moves, we propose some improvement to solve these problems, which includes dynamic adjustment, static adjustment, improving move ordering quality and live-five method. The result of the experiment shows that a version, named NCTU6_A, which uses dynamic adjustment and static adjustment reaches 59.6% win rate against NCTU6. A version, named NCTU6_MO, which improved move ordering quality, reaches 58.95% win rate against NCTU6_A. Finally, to find the correct moves for the above cases. Other adjustments can also improve our program.

並列關鍵字

Connect6 ； Theory of Computer Games ； Artificial Intelligence

參考文獻

[16] Wu, I.-C, Hsin-Ti Tsai, Hung-Hsuan Lin, Yi-Shan Lin, Chieh-Min Chang, Ping-Hung Lin, "Temporal Difference Learning for Connect6", The 13th Advances in Computer Games Conference (ACG 13), Tilburg, The Netherlands, 20-22 November 2011.

[4] Allis, L.V., van der Meulen, M., van den Herik, H.J.: ”Proof-Number Search”. Artificial Intelligence 66(1), 91–124 (1994)

[5] Cazenave, T., ”A Generalized Threats Search Algorithm”. Computers and Games, Lecture Notes in Computer Science, Vol. 2883, pp. 75–87, 2003.

[6] Chen, J.-C., Wu, I.-C., Tseng, W.-J., Lin, B.-H., Chang, C.-H.: ”Job-Level Alpha Beta Search”. In: IEEE Transactions on Computational Intelligence and AI in Games (in Press, 2014)

[7] Knuth , D.E., Moore, R.W., ”An analysis of alpha-beta pruning”, Artificial Intelligence, pp. 293–326, 1975.

國際替代計量

六子棋程式強度改進之研究

全文下載

主題瀏覽