Building a strategy game — and the AI to master it

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.

Over the weekend, I decided to embark on a new project: Designing a ‘from-scratch’ AI to consistently beat me (or anyone) in a particular strategy game.

What’s the catch? Well, for one, this particular game seems not to already exist anywhere online — so I’m going to build the underlying game as well.

And because the game doesn’t exist online — and frankly, might not exist at scale anywhere — there are no outside rules-of-thumb or commentary for me to follow. Instead, I’m going to be making it up rather on the fly, hoping to build an AI that can outplay me without my teaching it directly how to do this.

I should probably back up here …

Over the weekend I saw an old friend of mine from debate, and he taught me a game he learned while living in India this summer. We think it’s called “Churr-Purr”, though we aren’t quite sure — and likely the transliteration is one of our obstacles in finding information on it.

An example Churr-Purr board. Purple squares are vacant; red and blue squares belong to a particular player. Note that dashes are never squares to occupy or slide into; they just help indicate adjacencies.

Procedurally it’s like a combination of Tic Tac Toe, Go, and Connect Four. We had a lot of fun playing a few rounds and discussing the different strategies and tricks we discovered.

Having been inspired by the rounds of the game with my friend, and wanting a fun excuse for an AI challenge (and honestly, wanting to be able to play this game online, period), I decided to embark on this challenge.

The game is now live, minus some edge-cases, and I encourage you to check it out: http://churrpurrdemo.bitballoon.com

It’s currently player-vs.-player only, and on the same device, so … show your friends? (Note about the edge-cases— what happens if there’s total gridlock? What if there are no valid removals? The fun answer here is, ‘Nobody really knows!’, since there isn’t a proper rulebook to consult. Total gridlock feels like a tie to me … But what about removals? Maybe they should be optional.)

Next up is figuring out how this translates to an AI that can play the game. I have a few intuitions about how this AI ought to work and what information we may need to encode …. But I will leave this for another post.

Here’s how the game works:

• Each player begins with nine tokens, to be placed on a board.
• The game’s objective is to remove all your opponent’s tokens from the board. The game proceeds in two stages: In stage one, players take turns placing their tokens on unoccupied board slots; in stage two, players will slide their tokens to open adjacent spots.
• In both stages, a player is trying to create 3-in-a-row of their own tokens, while defending against the other player’s 3-in-a-rows. When a player achieves 3-in-a-row, they get to remove one of their opponent’s ‘unprotected’ tokens from the board. (Tokens that are part of a current 3-in-a-row are protected and may not be removed. Also note that diagonals do not count as 3-in-a-rows or adjacencies.)

Blue has just achieved 3-in-a-row; they may remove Red’s square at [1,3], but not in the vertical strip, as those are a protected 3-in-a-row.

• Once a token is removed form the board, it is out of play and does not return to the opponent’s stack.
• Once all 9 tokens of the players have been placed, stage 2 begins. In this stage, the players take turns shifting one of their tokens at a time to an adjacent vacant spot on the grid. If the shift forms a 3-in-a-row (even one that was previously 3-in-a-row, but then was disbanded), they remove an opponent’s ‘unprotected’ token, similar to in stage one.

At the beginning of stage 2, Red has selected its square at [1,3] to slide. Its vacant adjacencies are [0,3] and [1,1], but it cannot slide to [1,5] or [2,3], which are occupied; it also may not slide or form 3-in-a-rows diagonally. (Red also cannot slide onto dashes, which are not squares — they just help to indicate adjacencies.)

• Note that in stage 2, unlike stage 1, a 3-in-a-row is not necessarily protected forever. In stage 1, pieces do not slide, so a 3-in-a-row will remain intact until the end of that stage.
• In stage 2, however, a player may be forced or may choose to disband their 3-in-a-row to then reunify it and remove another opponent’s piece. This introduces a risk: That while your 3-in-a-row is disbanded, your opponent can form a 3-in-a-row and remove one of your now-unprotected pieces.

Instead of selecting [1,3] like shown previously, Red may want to select [4,4] and slide it down to [4,3]. Blue doesn’t have a way to prevent Red from sliding this back to [4,4] on its next turn, and thus winning the ability to remove a blue piece.

Currently Blue’s pieces at [2,2], [3,2], [4,2], [3,1], and [3,0] are all protected from removal, but Blue’s move may jeopardize that (e.g., moving from [3,0] to [6,0] leaves two unprotected pieces: at [3,1]. and the new piece at [6,0]). If Red returns from [4,3] to [4,4], it can remove one of these unprotected pieces.

• The game ends, in stage 2, once one player has fewer than 3 tokens remaining on the board (and thus can no longer form 3-in-a-rows), with the other player victorious.

Blue has fewer than 3 pieces remaining; Red is victorious.

That’s it! Now you know how to play Churr-Purr — let me know in the comments if you have questions, and hope to see you on the courts (boards? webpages?) soon.

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.