Solving 4x5 Dots-And-Boxes

Authors

  • Joseph Barker University of California, Los Angeles
  • Richard Korf University of California, Los Angeles

Abstract

Dots-And-Boxes is a well-known and widely-played combinatorial game. While the rules of play are very simple, the state space for even small games is extremely large, and finding the outcome under optimal play is correspondingly hard. In this paper we introduce a Dots-And-Boxes solver which is significantly faster than the current state-of-the-art: over an order-of-magnitude faster on several large problems. We describe our approach, which uses Alpha-Beta search and applies a number of techniques—both problem-specific and general—to reduce the number of duplicate states explored and reduce the search space to a manageable size. Using these techniques, we have determined for the first time that Dots- And-Boxes on a board of 4x5 boxes is a tie given optimal play. This is the largest game solved to date.

Downloads

Published

2011-08-04

How to Cite

Barker, J., & Korf, R. (2011). Solving 4x5 Dots-And-Boxes. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 1756-1757. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/8046