Implementing and Comparing Various Dots and Boxes Monte Carlo Tree Search Techniques

Mina Ryumae, Dr. Uta Ziegler, Department of Engineering & Applied Sciences, Western Kentucky University, 1906 College Heights Blvd, Bowling Green KY 42101

The two-person, zero sum, high strategy game Dots and Boxes has a large computational burden, which causes difficulty in using brute force to consider possible board configurations that increase exponentially with the board size. The challenge of the game is introduced when a player is forced to take another move after scoring, which creates a vast number of player move sequences. The Monte Carlo Tree Search (MCTS) algorithm is a machine learning approach that builds a partial game tree of board positions and their moves deemed to be important to the game, rather than using pruning techniques or searching the entire game tree. A large number of simulations is run for each board configuration added to the tree to collect statistical data (such as the number of times each move possible in that configuration was tested and the move’s overall benefit). Each simulation uses data pre-collected to select moves and updates the data after finding the simulation results. 

This work focuses on transpositions, that is, board configurations that can be reached through multiple move sequences, which are quite common in many games. Specifically, the aim is to improve the win/loss/draw ratio and efficiency of the MCTS player by affecting the amount and quality of information learned through simulations. The basic MCTS selection process uses the benefit of the move for selection calculations. The proposed selection process modifies the basic process by using the benefit of resulting board configurations after a move was taken for selection calculations. A framework was developed which allows players utilizing various selection processes to play directly against one another. Win/loss/draw ratio and efficiency comparisons between players using the basic and proposed selection processes will be presented.

Additional Abstract Information

Presenter: Mina Ryumae

Institution: Western Kentucky University

Type: Poster

Subject: Computer Science

Status: Approved

Time and Location

Session: Poster 5
Date/Time: Tue 12:30pm-1:30pm
Session Number: 4017