UCT Algorithm in Amazons Human-computer Games
作者单位：School of Information EngineeringMINZU University of China
会议名称：《第26届中国控制与决策会议》
会议日期：2014年
学科分类：1305[艺术学-设计学（可授艺术学、工学学位）] 13[艺术学]
基 金：supported by 2013 Beijing university youth talent plan And the granted number is 104-01300614
关 键 词：Artificial Intelligence Computer Games Amazons UCT Algorithm Monte-Carlo
摘 要：The main difficulty of Amazons games is the huge branch factor. Traditional NegaMax Search and Alpha-Beta Search can only search a few layers and can’t improve the games effectively. Monte-Carlo Algorithm can improve the games but it needs a huge amount of computing. This paper studies applying UCT algorithm to the Amazons games to overcome this problem in order to balance the search efficiency and computing load. In UCT mini-max tree search, the algorithm select tree node according to the node’s UCB(Upper Confidence Bound) *** evaluate the selected node and return the optimal moves. Using C++ programming language, we implemented Amazons human-computer games software. The experiments show that UCT algorithm can implement the search work in Amazons human-computer games and get satisfactory search efficiency.