Thirty Five vs AI

Type a key 1-9 with a square selected to make a move.

This is an implementation of "35", a board game I created, against an AI opponent. A discussion of general strategy can be found below the rules. Then, I will briefly discuss the algorithm used by the AI.
The rules are as follows:

1. Notice that each square has some squares adjacent to it (including diagonally), called "neighbors". Squares in the middle have 8 neighbors, edge squares have 5 neighbors, and corners have 3. This will be important.
2. During a player's turn, they may place a number from 1 to 9 in an empty square. That number will (usually) be created in that player's color.
3. If the sum of the numbers in all of a non-empty square's neighbors equals exactly 35, all of that square's neighbors will become the same color as it. For example, imagine a red 1 is surrounded by two 9s and an 8. If the blue player placed another 9 next to the 1, the sum of the 1's neighbors would be 9+9+8+9 = 35. Therefore, all of those squares would turn red, because the 1 is red.
4. If a square reaches 35, its empty neighbors will be highlighted in its color.
5. If an empty square is highlighted in red or blue, any number placed there will automatically be created in the highlighted color. Therefore, if blue placed a number in a red-highlighted square, it would have the same effect as if red had placed the same number.
6. Empty squares can also reach 35, but nothing will happen until someone places a number there, since the square must be non-empty.
7. If two squares of opposite colors reach 35 as a result of the same move, no squares change color.
8. Once there are no empty squares remaining, the player with the most squares of their color wins. If both players have the same number of squares, the game ends in a tie.

Since you win by having more squares of your color and there is only one way to change the color of your opponent's squares, the basic goal of the game is simple. You want to surround your squares with 35, and prevent your opponent from surrounding their squares with 35. Here are a few basic strategies for accomplishing this:

• Over-thwarting - This is when you send an opponent's square over 35. Say, for example, that your opponent has a square which is surrounded by 27. At any time, they can place an 8 to get that square to 35. However, if you place a 9 next to it, the square reaches 36. Since numbers can't be deleted, that square will remain over 35 for the rest of the game.
• Under-thwarting - Similarly, you can keep an opponent's square permanently under 35. Imagine an opponent's square is surrounded by 23, with 3 empty neighbors. If you place a 1 in one of those neighbors, it is now at 24 with only 2 empty neighbors. No matter what your opponent tries to put in one of the remaining squares, you can always put a 1 in the last square. This would leave the opponent's square with a sum under 35 and no empty neighbors to increase the sum.
• Setting up your squares - This is when you surround one of your squares with 26. This is very powerful because once you've done it, there's very little your opponent can do to prevent that square from reaching 35. Unless it only has 1 empty neighbor, they can't under-thwart you. They also can't over-thwart you, since a 9 would put your square to 35. If they place a different number, like a 4, you can counter it with another number (5 in this case) to reach 35.
• Countering a set-up - If your opponent has a square which is set up near some of your own squares, you can try to set up one of your squares in the area. This can have several outcomes. First, the move which puts their square to 35 may also put your square to 35. Because of rule 7, no squares would change colors. This may be good for you if you had more squares at risk of changing color. Alternatively, you might be able to flip their set-up square to your color, which would be extremely powerful.
• Exploiting weak borders - As the game goes on, each player typically dominates a section of the board which might be called their "territory". However, if the numbers on the "border" of your opponent's territory are high, you might be able to surprise them by placing a 1 right next to their territory. This 1 would have a high neighbor sum while not giving much to the border squares adjacent to it. This only works if your opponent's border has high numbers and the adjacent cells aren't highlighted in their color.
• Maintaining strong borders - To prevent this happening to you, be wary of the effects a move would have on your borders. A strong territory is surrounded by squares which are highlighted in your color. If there are non-highlighted squares on your border, try to keep the sum around those squares low.

This list isn't comprehensive, and most situations don't fit cleanly into one of these strategies. However, hopefully these give an idea of how the game is played and provide a good starting point. The best way to discover new strategies is to play and experiment with new situations.

The AI

The AI for this game uses an algorithm called Monte Carlo Tree Search, or MCTS. It is the same algorithm used for the AI in my Mega Tic Tac Toe project. I describe it there as well. Essentially, MCTS simulates thousands of random games starting from the current board state, and uses the outcomes of the simulations to estimate the best move. Each simulation is partially guided by the outcomes of previous simulations, so the search is focused on moves which seem promising. MCTS is good for games where there are too many possible moves to find the best one using a brute-force apporach such as minimax. In the case of this game, there are 576 available moves at the beginning of the game and 288 on average. By comparison, the average number of available moves, or "branching factor", of the board games chess and Go are 40 and 250, respectively. There are about 34 million possible board states in Go after 3 moves, and the first time a Go AI beat a human world champion on a full-size board was just in 2016. In this game, there are 182 million different possible board states after 3 moves, five times more than in Go. Thankfully, the algorithm for updating a 35 board is much simpler and faster than that for a Go board, so MCTS can run many simulations. On my laptop, it runs about 60,000 to 80,000 simulations in 30 seconds in Chrome, and 7 times more when running as a standalone program.

So how good is the AI? It's...ok. Running in a browser makes it about 7 times slower, which makes it struggle significantly in the early game when there are tons of moves to investigate. By the time about a third of the board is filled up, though, it becomes significantly better. It typically falls far behind in the early game and often makes a miraculous comeback in the mid-to-late game. It's able to beat me fairly often, though if the game's strategy is as deep as I hope it is, we're both bad players. Overall, it plays really well in the second half of the game, so don't get too confident if you get a huge lead early on. The AI will eventually play perfectly, and with the way the game works, a single good or bad move can completely turn the tables.