Alchemize is a strategy board game, inspired by games like Reversi and Hexxagon, originally built by for Ludum Dare 42 . We recently released an updated version with several improvements, including the ability to play vs AI.

In this post I will talk about how I created the AI player of Alchemize. I'll tell about the challenges and the solutions I chose, taking into account strategy, speed and player experience. Enjoy!

Game Rules

If you have not played the game, please give it a try. After a short tutorial and a minute or two playing, the game rules should be very clear. For those who are unable to play now, I'll go over the basics.

Basically, each player places a potion. The potion can create new gems (in adjacent squares that also touch a potion of the other player), or collapse squares (in adjacent squares that touch a potion of the same color). If a square containing a gem collapses, then the gem is destroyed.

These simple rules lead to very deep game dynamics (Kudos to Stav and Yakier who invented this game from scratch in the original Ludum Dare jam!). On each move, the player must consider the following:

• Will my potion produce any gems?
• Will my opponent be able to use my potion to produce gems? (remember that you must touch the other player's potion to create gems)
• Can I use my turn to destroy the opponent's gems?
• Can I block my opponent from destroying my gems?

... and we can go as deep as we want. For example, a good move can be one that forces your opponent to destroy your gems in a way that will allow you to create more gems, et cetra. Anyone who played a bit of chess is familiar with such kind of strategies.

Writing an AI player

Board Games AI 101

So I needed to write an AI player that would take this depth into account. The natural choice was Minimax Algorithm, a standard algorithm for two-player games. In a nutshell, Minmax algorithm decides the next move by peeking into the near future of the game. For each of the player's possible moves, it takes into account all of the opponent's possible reactions; for each it takes into account the player's reactions; and so on. The chosen move is the one that promises the best result for the player.

For short games (e.g. Tic Tac Toe), the computer can calculate the outcomes of all possible moves and reactions, resulting in a perfect player, that is actually not that fun to play against. However, for longer games with many possible moves in each turn, this becomes unfeasible, as the number of calculations increases drastically on every extra turn you try to predict. For example, in Chess, there are, on average, 20 possible moves for each turn, for which the opponent has 20 possible reactions etc. This results in 400 moves to calculate for depth 2 (i.e. peeking 2 turns into the future); over 3 million moves for depth 5, and over a billion for depth 7, and so forth.

So in games like chess (and Alchemize is indeed, like chess in this matter), we need to use this algorithm with a heuristic - that is a way to evaluate and how a specific board setting is good for you, compared to other boards, by giving it a certain score value. Minimax algorithm takes this score into account, and tries to maximize it (actually that's the origin of the name - it chooses the move that maximizes the board's score, given an opponent's move that will minimize your score, and so on).

I will describe the heuristics I chose for Alchemize AI player, then I'll talk about how I optimized the game to work fast on all platforms.

The Heuristic

I started with the following, very simple heuristic:

[number of your gems] minus [number of your opponent's gems]

This heuristic simply tries to maximize your player's gems, and minimize your opponent's gems. For example, it will prefer a board in which you have 5 gems and your opponent has 2 (final score is 3), over a board where you have 10 gems and your opponent has 9 (score is 1). And of course, will try to avoid a board in which your opponent has more gems than you (and a negative score).

This board's heuristic score (for the blue player), is 3:

3 = 5 - 2 = [number of blue gems] - [number of red gems]

In this board, the blue's heuristic score is  -2.

This simple actually heuristics worked quite well! Given a large enough depth (i.e. the number of moves it "peeks" into the future), it can produce quite good moves. Another benefit of this algorithm is that it is perfectly correlated with winning the game. If it happens to succeed peeking until the end of the game (by having a large enough depth, or when the actual game is near its end), then it will indeed produce that desired "perfect player".

Phase 1 - simple heuristic, different depth

1. Easy - simple heuristic, depth 1
2. Medium - simple heuristic, depth 2
3. Hard - simple heuristic, depth 3
4. Insane- simple heuristic, depth 4

I used the same heuristic for all players, with different depths. This produced nice and diverse difficulties!

• Easy was a simple, reactionist player that tried to maximize score in the next move only, but not taking the following moves into account. Players that got familliar with the game's rules and developed a simple strategy could beat this one easily.
• Medium is predicting a single response. Meaning that the you needed some skill to win this, but it was still possible.
• Hard was actually hard! Much harder than Medium, for that matter. It required a firm hold of this game, and long-term strategies. For me, it was really hard to beat and required a lot of training. 
• Insane was, again, much harder than Hard, and required ruling this game, exploiting each of your moves to dominate the board and think about end-game strategies from the very first move.

So regarding player experience, I think this worked quite well. However, there were two main issues:
One, it was too slow. Hard took 5-6 seconde, but Insane could take up to 20 seconds. Two, I found that I can win Hard and sometimes even Insane quite easily if I focused on a specific strategy.

Phase 2 - advanced heuristic - "secured gems"

In Alchemize, you need to produce the largest number of gems. But more importantly, you need to destroy your opponent's gems! It is not uncommon, that in the end of a game, each player has very few gems.  See the following typical end-game board, where each player has only 2 gems:

It makes a lot of sense when you think about it; gems are very easily destroyed. If you place a potion near an existing gem it will always be destroyed , regardless of its color (because it must have both a blue and a red potions nearby, which will produce a hole once another potion is placed).

This means that every gem counts. And if a gem has all of its adjacent cells occupied (i.e. either collapsed or with another gem or potion), it means that it cannot be destroyed! That what I call - a secured gem (or a "blocked" gem).

In the board above, the gems marked in yellow cannot be destroyed, whereas the ones marked in green ("Loose" gems) can, and will most likely, be destroyed.

I found that when I focus my efforts on blocked gems, I could beat the computer. So I thought - why not add it to the AI strategy?

So I came up with in improved heuristic: 

100*([num of your blocked gems] - [num of your opponent's blocked gems]) + [num of your gems] - [num of your opponent's gems]

This heuristic means that the AI will always try to maximize the number of blocked gems, and only in case of a blocked-gems-tie will try to maximize the total number of gems in general.

So I used these configs:

1. Easy - simple heuristic, depth 1
2. Medium - simple heuristic, depth 2
3. Hard - blocked-gems heuristic, depth 2
4. Insane- blocked-gems , depth 3

I applied "blocked-gems heuristic"  to Hard and Insane, and reduced their depth by 1.
In AI-vs-AI matches, I found out that the new Hard beat the old Hard, meaning that in less depth (2 instead of 3, and therefore, much faster), I could make a better player! I also found out that the new Insane was about the same as the old Insane, again, with less depth (3 instead of 4), which was definitely a win for me. Now the hardest player CPU turn takes only a few seconds! Hurray!

Another thing that's good about it, is that in the end, all gems are blocked. Meaning that near the end of the game, this player can still play optimally, just like the simple player above.

And that's how I released the game - with a small tweak:

Phase 3 - randomized "Easy"

I found that the easy player was very predictable and stale. It was simply trying to maximize their score in a single turn, meaning you could win it by luring it into making bad moves. This missed the purpose of the game as I saw it - "Easy" was the gateway of new players to the game, and a place for them to practice and try different strategies; while the current Easy was felt more like a puzzle where you can win by learning a specific sequence.

So I added randomization to its heuristic - meaning that the AI has a chance of making a move that was not optimal. This had an awesome effect! First, the Easy player was no longer predictable, and made it more challenging for the player. Second, it made a mistake once in a while, which allowed the still-ramping-up players to take advantage of it and win. Much more fun than playing vs a bulletproof, always-optimal CPU!

This change created a much better experience for players playing against Easy - which was important to make a good first impression on players!

And the funny thing is, that this randomization did not necessarily made this player worse! In regular-Easy vs randomized-Easy matches, each of them won an equal number of games. I guess that since the depth-1 was not very optimal to begin with, adding some noise did not really make it less optimal. It just made it more interesting.

So finally. I released the game with the following AI player configs:

1. Easy - simple heuristic with randomization, depth 1
2. Medium - simple heuristic, depth 2
3. Hard - secured-gems heuristic, depth 2
4. Insane- secured-gems , depth 3

See this demonstration of Hard (red) and Insane (blue) AI players playing against each other. They both seem very abstract and unpredictable, but still Insane makes better moves and eventually wins the game:

Future

There are many other AI efforts I could try. Here are some of them:

• Do not count "worthless gems". These are gems that will always be destroyed, in every possible outcome. These are completely worthless. Try to think of examples yourself. An AI player could identify these in a different calculations.
• Prefer "blocked potions" over "exposed potions".If a potion has an empty square near it, it means that the opponent may be able to use it to produce gems. An AI that tries to keep their potions "hidden", may be a better player.

I bet that after a while playing, you could think about applying your own strategy.

However, I chose not to implement these - mainly because the existing players were good enough and I did not want to make them slower (even if better) by adding more heuristics. But also, I think it's nice to leave a way for the player to win, by making the AI players hard but not bullet-proof. Because after all, this is not about making the best AI players, it's about making the best experience for the player.

Please let me know what you think of these post! This is the first of its kind, so tell me if you want to see more like these.

That's it! Now go play Alchemize!