This blog explains my approaches to a game contest hosted by HackerEarth. The contest asked programmers to put forward their bots to play games of Chain Reaction. You can find the source code here.
In case you haven't played Chain Reaction, this post should be a treat for you.
Let me warn you that the following will involve some heavy technical words. But all of them are easier to learn than they sound. In my limited experience of developing game playing AI, I have found the following approaches to be most useful.
- Min-Max tree generation
- Heuristic Improvements
- Iterative deepening
- Alpha-Beta Pruning
- Program Optimization
Min Max tree generation
A Min Max tree mimics natural human thinking. When playing tic tac toe, our thinking goes like this:
What you see above is exactly what a min max strategy is. It considers your move, your opponent's possible responses, and your subsequent responses. The loop goes on till we find a terminal game state, in which case we return the terminal node's value.
Every possible board position maps to a value. The value is directly proportional to how much X favors the position. If X wins (green position), the position has +? value. For a loss (circled in red), it evaluates to -?.
Each layer in the tree contains all possible positions for that move number. If X was playing first, the second layer is O's turn. The third is X's, and so on. When a terminal value reaches the parent, it tries to maximize (if X) or minimize (if O) the score from all its available branches.
Generating the entire min-max tree from move 1 for all moves is infeasible. We need a method of guessing how good a position is without looking at every possibility from it.
Heuristic Evaluation
If you have played any sport, you have had moments when your instinct wakes up. Danger, opportunity, momentum... all these feelings rise from an acute understanding of game positions.
So, play a few games in the competition. Try to get a sense of a given position. If a position feels good, then ask yourself “why”. What are the elements on the board which are key factors to this assessment?
instinct(game_position, player_to_move) = feeling
Heuristics are instinct functions for computers. Since generating the entire min max tree is infeasible, we cut off search depth and treat the position as terminal, returning a heuristic value.
f(game_position, player_to_move) = evaluation
Note down the factors you use for assessing a position and assign a weight to each. Then design a heuristic. Avoid making it too fancy. I used:
f(position, player) = (player == 1 ? 1 : -1) * (cell_diff() + explosive_diff())
This simple function performed better than several more complex attempts I tried during the competition.
Iterative deepening
The problem with fixed depth cutoffs is that they are too rigid. Early-game positions have many possibilities; late-game positions have fewer. We need a flexible way to search as deeply as time allows.
Iterative deepening builds min max trees of increasing depth. Start with depth 2–3, then increase by 1 in each iteration. The best result before the timeout is returned.
This way, the algorithm adapts. If many moves exist, it searches shallow. If few moves exist, it searches deeper. This technique is essential for competitive game AI.
Alpha Beta Pruning
It isn’t α–β itself that sets the top entries apart, but most of them surely use it.
In competitions, move prediction is everything. We assume the opponent will always optimize their move. A lot of nodes in a min max tree are wasteful and can be proven suboptimal early.
α and β are bounds for each node. α is the minimum X will accept; β is the maximum O will allow. X tries to maximize α, and O tries to minimize β.
An excellent explanation of implementing α–β pruning is available here.
Each additional move you can predict makes your bot stronger. Without pruning, 1000 evaluations with branch factor 4 allows depth = 5. With α–β pruning, you can reach depth = 6 with a reasonable heuristic.
Program Optimization
Optimization is the most advanced and complex part of developing game AI. But please, DO NOT optimize prematurely. Do it only when:
- Your program is bug-free
- You've avoided repeated calculations by caching values
- Your program fails test cases only due to insufficient evaluation time
Here are some advanced optimization concepts with their complexity and effectiveness:
| Technique | Effectiveness | Implementation | |
|---|---|---|---|
| 1. | Position Cache | Moderate | Moderate |
| 2. | Killer Move Heuristic | Moderate | Easy – Moderate |
| 3. | Symmetry Analysis | Low–Moderate | Moderate – Difficult |
| 4. | Concise Representations | High | Very Difficult |
| 5. | Object Pooling and Reuse | High | Difficult |
| 6. | Parallelization | Low–Moderate | Difficult – Very Difficult |
| 7. | Heuristic Improvement | High | Moderate – Difficult |
A great way to generate test positions is to let your bot play against itself with different heuristic weights. Store decisive positions and optimize based on performance.
Use static objects for classes like “Move”. If you can implement “undo” in O(1), avoid copying boards. Otherwise, pool board objects instead of constant reallocation.
One excellent paper I found for game development is on Othello—highly recommended for crunch-time competitions.
Participate here in HackerEarth's AI challenge, Battle of the Bots.
