Application of UCT Search to the Connection Games of Hex, Y, *Star, and Renkula!
Tapani Raiko, Jaakko Peltonen · 2008
Play-out analysis has proved a succesful approach for artificial intelligence (AI) in many board games. The idea is to play numerous times from the current state to the end, with randomness in each play-out; a good next move is then chosen by analyzing the set of play-outs and their outcomes. In this paper we apply play-out analysis to so-called ‘connection games’, abstract board games where connectivity of pieces is important. In this class of games, evaluating the game state is difficult and standard alphabeta search based AI does not work well. Instead, we use UCT search, a play-out analysis method where the first moves in the lookahead tree are seen as multi-armed bandit problems and the rest of the play-out is played randomly using heuristics. We demonstrate the effectiveness of UCT in four different connection games, including a novel game called Renkula!.