How complex is this challenge anyway?

This post is part of ChurrPurr.ai, a challenge to design an online strategy game and the AI to master it. Play the latest version of the game here.

Now that I’ve decided to undertake the challenge of building an AI for Churr-Purr, the strategy game I recently learned, a question’s been on my mind: Just how difficult is this challenge I’m getting myself into?

One way that computer scientists try to quantify the challenge of programming an AI for different games is the idea of “complexity”.

Broadly this asks how many different variations a game may have — because the more possible variations, the more options an AI must theoretically evaluate to decide its best course of action. (This is not strictly true, depending on your AI’s goals and methods of evaluation, but it’s true enough for our purposes.)

For example, in chess the first player (White) has 20 possible opening moves — to move each of its pawns either one or two squares, or to move either knight forward-left or forward-right. The second player (Black) also has 20 possible moves — so there are 400 different variations for the first turn alone.

One of the 200,000 valid board scenarios after four complete turns of chess. Which of the 5,000,000 valid scenarios will occur after turn five?

That’s a lot, but hey, computers are pretty fast, right? Unfortunately the problem compounds over time — and by the end of the 5th complete turn, there are ~5 million different positions. Not ideal.

The game Go — a recent hotbed of AI research, given DeepMind’s success in defeating world champions with its AlphaGo program — is even more complex than chess. Professional Go is played on a 19 x 19 grid, compared with chess’s 8 x 8 grid, and games between experts typically last many more moves in Go than in chess.

Accordingly, whereas evaluating a full game-tree for chess requires a meager 10^123 different branches, Go requires branches on the order of 10^360. Each of these numbers is considerably larger than the estimated number of atoms in the universe.

It might not look it, but there are considerably more ways for Go to play out than there are atoms in the universe. (Of course, there aren’t more endings than there are combinations of *different* atoms in the universe …)

(Given the scale of these numbers, you would be very reasonable in wondering how computer scientists make sense of these enormous game-trees — and we’ll be getting there in further posts.)

How does Churr-Purr compare to these figures? Let’s begin by evaluating only the first stage of the game, in which players take turns placing a token on unoccupied board squares, setting aside the possibility to remove tokens, which would add to the complexity.

The first player plays on one of 24 open squares, with the second player then placing on one of the 23 remaining. The players proceed in turn until they are out of tokens, for 18 moves total. So, by this approach, the complexity of a simplified stage one could be calculated as 24 * 23 * 22 * 21 … * 7, which is roughly 10^21.

After accounting for removals and the game’s stage two, this number could get a bit worse, but at least we don’t seem to trying to crack a new version of chess from scratch. Silver linings. (Note: I wrote this post before my discovery that Churr-Purr may in fact be a solved game, and at minimum is similar to the known game Nine Men’s Morris — 10^50 according to Wikipedia, but with an additional third stage vs. Churr-Purr. I’ll take it.)

To tackle and/or reduce Churr-Purr’s complexity, we have two short-cuts at our disposal: These are symmetry and solved positions.

In the approach I outlined above, I noted that player 1 must choose one of 24 spots for their first play. This is true, but among these 24 spots, there are actually only 4 unique plays: Playing in a corner of the middle ring; playing in a middle-spot of the middle ring; playing in a corner of a non-middle ring; and playing in a middle-spot of a non-middle ring.

For example, we can see how these four red squares are analogous, and how with a ‘simple’ mathematical transformation (a rotation) the board has become the same. This means these four moves can be treated as only one unique move.

It might not be obvious why the above two images — in the inner-ring and outer-most ring — are symmetric. The way I visualize this is to grab the inner ring and, almost as if it were a physical structure, ‘stretch’ it to the outside so that it becomes the new outermost ring. The former outermost ring is now the innermost, and the middle ring is still the middle ring. If this doesn’t convince you, then think about what nodes each point connects to — can you find a difference between being on the outermost and innermost, aside from the label of outermost vs innermost?

In light of the 4 possible first-moves, you might wonder whether player 2 indeed has 23 unique responses to play — and the answer is no. For one of the first-4 moves I mapped out, I calculated ~14 unique responses, so let’s make the assumption that’s roughly the same across the 4.

Assuming no further symmetry after move 2 (probably a dubious assumption), our math then becomes 4 * 14 * 22 * 21 * 20 …. * 7, which is ~6 * 10^19. This change alone means we would have to calculate ~10x fewer branches to exhaustively evaluate stage one. Again, I’ll take it.

Other games also benefit from symmetry in this way. For example, Tic Tac Toe at first blush appears to have 9 first moves, but has only 3 unique ones: playing in the middle; playing in a corner; or playing in a non-corner edge. The opponent does not truly have 8 unique responses, etc.

Still, whereas 10^19 is smaller than 10^21, it remains a massive number — and it’s likely a low estimate on the complexity of Churr-Purr, given the complications of removing pieces and stage two, which could each add orders of magnitude of branches.

So, if we wanted to exhaustively evaluate these branches, what other tools do we have at our disposal? (In addition to heuristics / more sophisticated AI techniques that will help us circumvent this exhaustive evaluation.)

A second tool is solved positions. By a solved position, I mean one in which a player can force a win with a sequence of moves, no matter what their opponent does. Note that a solved game can be very far out from conclusion, or very close to it.

For instance, if a position has player 1 being one move away from winning, and it is player 1's turn, this is a solved position. That much is fairly intuitive.

What’s slightly less intuitive is that a position can be solved well in advance of this direct-win if player 1 can force an arrival at this position. (As a sidenote, some games are entirely solved, meaning that from the outset a player can force a win (or sometimes used synonymously, force a draw) with perfect play [Churr-Purr may even be one of them!]. For example, checkers is technically solved, and the best computers in the world would play to infinite draws. In practice, however, humans make mistakes — so sometimes solved games or positions can still conclude in outcomes contrary to the ‘solution’.)

We can leverage solved positions if we determine that certain positions entail a win well in advance of the game’s actual conclusion. For instance, the below position at the beginning of stage 2 is ‘solved’ for a win for player 1:

If player 1 plays correctly, there is nothing player 2 can do to prevent player 1’s win. (Player 1 can lock in this win by repeatedly shifting in and out of its 3-in-a-row at the top, with Player 2 powerless to prevent this.)

Whereas an exhaustive evaluation would continue going through moves beyond this point, we can cut our search short so long as we can recognize these positions; the conclusion is foregone, so there is no need to parse further branches.

I suspect that finding out the elements of a solved position in Churr-Purr will be a major insight that powers my AI to success. Once the AI has a good idea of what positions are wins vs. losses, it can begin planning moves that best converge upon these won positions.

This will be an interesting sub-puzzle, because while I have decent intuitions for certain positions being solved (for example, P1 having an imminent 3-in-a-row to begin stage two, with P2 having no 3-in-a-rows and no ability to block P1’s 3-in-a-row), I also suspect there are many solved positions that arise in a game but I do not yet recognize with my bounded computational and insight abilities.

Hopefully I can train a computer to excel at these aspects where I sometimes flounder, and then efficiently route its way to these positions. For now I believe this to be toward the core of what I will help the AI evaluate — but that content itself is fodder for another post.

Read the previous post. Read the next post.

Steven Adler is a former strategy consultant focused across AI, technology, and ethics.

If you want to follow along with Steven’s projects and writings, make sure to follow this Medium account. Learn more on LinkedIn.