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.
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.)
- 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.
- 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.
- 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.
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.