King Domino: How to Build an Intelligent Graph Search?

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:

https://github.com/craigtopia/KingDomino

The premise is to abstract as classes the following components:

• Domino
  • One two-sided carboard piece, replete with nostalgic artwork
• Side
  • Two of which comprise the Domino
• Board
  • The dynamically growing grid comprised of dominos
• Move
  • 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)
myBoard.assign_domino(mv)
myBoard.score_kings()

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:

The white polka-dotted region covers the six tiles that represent unique places the Castle. Adding a seventh position would be redundant!

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:

A 9×9 grid provides a nice square way to think about the space for King Domino tiles. Indeed it’s sufficient and makes the programming easy. But if you’re trying to save processing power, you can use the abridged grid depicted by the shaded checkerboard region above. (Note this graphic indexed at 1 instead of 0)

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:

Local optimum from naive recursive depth-first search of king domino graph. This grid scores 62, and was the forerunner after several hours of searching. That is a very good score and if you built this grid in the game, you’d probably win. You’d do so in spite of only placing 11 dominos.

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:

The grid generated by my 8-year old nephew when he was tasked to build the maximum score grid. It scores a whopping 124! The caves alone nearly beat the local grid search optima of 62. Is this the optimal 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…

Advertisement