ML Student Projects: Dots-and-Boxes

This games was explored in the course “Machine Learning: Project” (Prof. Hendrik Blockeel, Dr. Wannes Meert). Students developed agents that are able to play the Dots-and-Boxes game.

The game implementation is available at https://github.com/wannesm/dotsandboxes (and can be played interactively).

Rules of the game

Starting with an empty grid of dots, two players take turns adding a single horizontal or vertical line between two unjoined adjacent dots. The player who completes the fourth side of a 1×1 box earns one point and takes another turn. (A point is typically recorded by placing a mark that identifies the player in the box, such as an initial.) The game ends when no more lines can be placed. The winner is the player with the most points. The board may be of any size. When short on time, a 2×2 board (a square of 9 dots) is good for beginners. A 5×5 is good for experts. ( Wikipedia)

While the game has very simple rules, it has a large number of possible states (more specifically, $|S| = 2^{r(c+1)+(r+1)c}$ states for an $r \times c$ game), and an even larger number ($\log_2(|S|)!$) of unique games can be played. No general strategy for optimal play is known. Currently, a 4 × 5 game is the largest game that is solved. (Barker, J. K. and Korf, R. E. Solving dots-and-boxes. AAAI 2012)

Agents

The agents available in the Dots and Boxes demo are developed by students from the Master of Computer Science at KU Leuven as part of the 2017-2018 course Machine Learning Project, taught by Prof. Hendrik Blockeel and Wannes Meert.

The machine learning technologies used in the agents are:

• Monte-Carlo Tree Search to simulate game-play
• Q-learning to learn about good actions
• Artificial Neural Net / Deep learning to learn about good board states
• Logic rules to reason about domain specific concepts such as ‘chains’ and ‘sacrificing'

Credits

Hendrik Blockeel, Wannes Meert, Pieter Robberechts, Arne De Brabandere and Sebastijan Dumančić contributed to this course.