If you’re lucky, you had a chance to play this tight and quick gem called King Domino. Don’t take my word for it, take Germany’s: https://arstechnica.com/gaming/2017/07/board-game-of-the-year-goes-to-kingdomino/
I won’t waste time teaching you the rules here, as you can find them on YouTube. But to score a grid, for each connected component, multiply its size by the number of kings.
So now, I assume you know the rules, you love the game, and you’re as curious as I am about how to algorithmically think about it. Well, you’re in good company. I’m really excited about the simplicity of the rules and the path-dependent nature of the grid building. So excited in fact, that I built out a platform to play the game in Python:
The premise is to abstract as classes the following components:
- One two-sided carboard piece, replete with nostalgic artwork
- Two of which comprise the Domino
- The dynamically growing grid comprised of dominos
- The choice of placing a given domino to expand the existing board
- This is of course what we want to be smart about using Artificial Intelligence
Theese classes have nice features implemented like __hash__, __eq__, __ne__, __repr__. This allows for a lot of convenience, and one can work with Python sets of Moves or Dominos and so forth. Then, the game can simply be played by choosing dominos and adding Dominos to a Board via the Move object.
Note this is single-player King Domino (for now).
The King Domino Board is simply a 9×9 grid with the Castle in the center. It doesn’t feel this way when you’re playing the game, but a moment’s reflection will ensure you this is a safe way to think about it Since this is coded in Python, we will begin indexing at 0 and so the center castle is placed at (4,4). An acceptable Move is then anything adjacent to that. Moves are instanced by specifying a side and a coordinate (i, j) for that side. Then the rotation is specified via (Di, Dj) so that the second side is placed at (i + Di, j + Dj).
Example code to place a Domino at (4,5 / 5,5) would be:
import kingDomino as kD
myBoard = kD.Board()
d = Domino(Side(kings=0, terrain='wheat'), Side(kings=0, terrain='wheat'), 1)
mv = Move(domino=d, first_side=0, i=4, j=5, Di=1, Dj=0)
Now, as you may have noticed, the 9×9 grid representation is actually more than we need. There is a lot of symmetry one can exploit to remove squares. For example, a grid in the upper left of the 5×5 grid can be rotated to be in the upper right, lower right, or lower left. Really, those are all just grids where the Castle is in the corner. It turns out there are only six positions for the Castle to be, as shown here:
So in fact, a computer really only has to think of a subset of the 9×9 grid with a staircase carved out of it. Something like this:
In the github link above, the simpler 9×9 grid is used. One can also imagine a computer intelligence that considers 6 separate 5×5 grids at the beginning of the game. For each, it chooses an optimal move and then applies a supervisory choice to discard grids when they appear to be suboptimal. Ultimately, the computer will have a single 5×5 grid to consider.
One interesting question that arises is: What is the Optimal board? You can try to work it out yourself if you have the game handy. Take a minute or two and give yourself full authority to choose any tile. What’s your score?
Now, in the github link above, you can try your luck at the most naive and computationally slow strategy conceivable to answer that question: a Depth-First Grid Search of all possible King Domino Boards given the 48 tiles. Simply clone and run depth_first_brute_force.py (Python 3). The good news is that the algorithm is only 12-lines of code, a recursive depth-first search. We don’t have to worry about recursive runaway because the max-depth is obviously limited (you can only place 12 dominos). Let’s see what the board looks like when I run this on my machine and choose an intermediate result:
It is intermediate of course, because the naive implementation of grid-search is too slow. It’s in fact much worse than the grid my 8 year-old nephew was able to generate using his intuition rather than searching every grid:
Is there a better way to grid-search algorithmically? What do you suggest?
Stay tuned for a much smarter approach to answer the simple max-scoring grid question. For the more nuanced challenge of how to play against intelligent competition – ie: how to optimally auction for tiles and build the grid, can we look to Tensorflow? Can deep learning outmaneuver an amateur human contender?
The conquest continues…