And the Winner is… Solving Triomineering using Combinatorial Game Theory

Student(s): Daniel Brüggemann, Mantas Gagelas, Maarten Weber, Bas Willemse;
Supervisor(s): Dr. Jos Uiterwijk;
Semester: 2015-2016;

Fig 1. – Triomineering 6×6 board. Horizontal starts and wins.

Problem statement and motivation:

Games without randomness and with perfect information normally can only be solved for a specific game environment. Small changes like changing the board size or modifying the pieces used by players usually introduce new challenges for the implementation of the game solver. A precise understanding of the specific game domain and its properties is needed, and extending the domain to new areas might help to improve this understanding and reveal new techniques for a more efficient solver. We look at the combinatorial game Domineering, where one player places vertical and the other places horizontal dominoes on a board, and the player who first cannot place a new domino loses. We extend its rules by using not dominoes, but 3-tile-pieces (Triomineering), and build a solver for this variant of the game. The solver uses a combination of search heuristics and strategies from the field of Combinatorial Game Theory, especially using the representation of a board state as a combinatorial game value. We explain how to calculate these game values of sub-games and how these can be used to make the solver more efficient, meaning how to reduce the number of game tree branches that need to be searched by the solver. The developed results might allow a better insight into the general domain of Domineering and how to solve it efficiently.

Research questions/hypotheses:

  • Is it possible to make a solver for Triomineering using the combination of minimax and Combinatorial Game Theory?
  • Is there a large improvement from combining these techniques in the solver?
  • Are there similarities to be found in solving the game of Domineering and Triomineering?

Main outcomes:

  • Combinatorial Game Values provide useful support in checking the results of the solver throughout development.
  • It has proven to be difficult to combine solver heuristics and CGT values, because certain advantages of e.g. solver pruning seem to not work correctly with CGT values.
  • Move ordering and transposition tables, as in solving Domineering, each provide a great solving speed improvement.

Downloads:

Final report

Leave a Reply

Your email address will not be published. Required fields are marked *