Game-Tree Simplification by Pattern Matching and Its Acceleration Approach using an FPGA

Authors: Suguru Ochiai, Toru Yabuki, Yoshiki Yamaguchi, Yuetsu Kodama

Abstract:

In this paper, we propose a Connect6 solver which adopts a hybrid approach based on a tree-search algorithm and image processing techniques. The solver must deal with the complicated computation and provide high performance in order to make real-time decisions. The proposed approach enables the solver to be implemented on a single Spartan-6 XC6SLX45 FPGA produced by XILINX without using any external devices. The compact implementation is achieved through image processing techniques to optimize a tree-search algorithm of the Connect6 game. The tree search is widely used in computer games and the optimal search brings the best move in every turn of a computer game. Thus, many tree-search algorithms such as Minimax algorithm and artificial intelligence approaches have been widely proposed in this field. However, there is one fundamental problem in this area; the computation time increases rapidly in response to the growth of the game tree. It means the larger the game tree is, the bigger the circuit size is because of their highly parallel computation characteristics. Here, this paper aims to reduce the size of a Connect6 game tree using image processing techniques and its position symmetric property. The proposed solver is composed of four computational modules: a two-dimensional checkmate strategy checker, a template matching module, a skilful-line predictor, and a next-move selector. These modules work well together in selecting next moves from some candidates and the total amount of their circuits is small. The details of the hardware design for an FPGA implementation are described and the performance of this design is also shown in this paper.

Keywords: Connect6, pattern matching, game-tree reduction, hardware direct computation

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1084226

References:

[1] Murray Campbell, A. Joseph Hoane Jr., and Feng hsiung Hsu. Deep Blue. Artificial Intelligence, 134:57-83, 2002.
[2] Michael Buro. Entertainment Computing - Technology and Applications, volume 112 of IFIP Advances in Information and Communication Technology, chapter The Evolution Of Strong Othello Programs, pages 81-88. Springer, 2002.
[3] Remi Coulom, Computing Elo Ratings of Move Patterns in the Game of GO, in Proceedings of the Computer Games Workshop, pp1-11, 2007.
[4] Helmut A. Mayer and Peter Maier. Coevolution of neural go players in a cultural environment. In The 2005 IEEE Congress on Evolutionary Computation, volume 2, pages 1017-1024, 2005.
[5] I-Chen Wu and Ping-Hung Lin. Relevance-Zone-Oriented Proof Search for Connect6. IEEE Transactions on Computational Intelligence and AI in Games, 2(3):191-207, 2010.
[6] Takahiro Watanabe, Retsu Moriwaki, Yuichiro Yamaji, Yuki Kamikubo, Yuki Torigai, Yuki Nihira, Takashi Yoza, Yumiko Ueno, Yuji Aoyama, and Minoru Watanabe. An FPGA Connect6 Solver with a Two-Stage Pipelined Evaluation. In Proceedings of the International Conference on Field-Programmable Technology, pages 1-4, 2011.
[7] Kentaro Sano. SW and HW Co-design of Connect6 Accelerator with Scalable Streaming Cores. In Proceedings of the International Conference on Field-Programmable Technology, pages 1-4, 2011.
[8] Kizheppatt Vipin and Suhaib A. Fahmy. A Threat-based Connect6 Implementation on FPGA. In Proceedings of the International Conference on Field-Programmable Technology, pages 1-4, 2011.
[9] Tobias Ziermann, Bernhard Schmidt, Moritz Muhlenthaler, Daniel Ziener, Josef Angermeier, and Jurgen Teich. An FPGA Implementation of a Threat-based Strategy for Connect6. In Proceedings of the International Conference on Field-Programmable Technology, pages 1-4, 2011.
[10] I-Chen Wu and Dei-Yen Huang. A New Family of k-in-a-row Games. In Proceedings of the International Conference on Advances in Computer Games, pages 180-194, 2006.
[11] I-Chen Wu, Dei-Yen Huang, and Hsiu-Chen Chang. Connect6. ICGA Journal (SCI), 28(4):234-241, 2005.
[12] AtlysTM Board Reference Manual, Dec 2012. Rev. C.
[13] The 2011 International Conference on Field-Programmable Technology, 2011. http://www.cse.iitd.ac.in/ icfpt11/.
[14] The 2012 International Conference on Field-Programmable Technology, 2012. http://icfpt2012.blogspot.jp/.