Developing an Algorithm for Efficient Nim-Value Calculation in Dots and Boxes
Mentor:Kerstin Voigt, Director of the School of Computer Science and Engineering, California State University, San Bernardino
The impartial game of Dots and Boxes is an important one within the field of Combinatorial Game Theory. It is a relatively simple children's game, but the complexity of the play space and wide variety of emergent structures makes it ripe for combinatorial analysis. It also lacks a proven winning strategy, and includes game states with indeterminate optimal solutions. As an impartial game, Dots and Boxes may be analyzed using the Sprague–Grundy theorem, allowing the application of nim-values to positions within the game. In the context of Dots and Boxes these values allow for increased control of chains (a major emergent structural component of the play space). However, a naïve algorithm for nim-value calculation runs in O(2^n) time, making their calculation impractical until late game, when fewer potential moves are available and the usefulness of the counting itself is diminished. In this paper I work to develop a more efficient algorithm, defined as one with a upper bound of O(n^2) or better. I address certain potential methods for improving the efficiency of nim-value calculations, and the proper data structures for both containing board states and operating on those states to find nim-values. I will also discuss the application of a nim-value calculation algorithm in the context of a general Dots and Boxes player AI.