BlowWar AI | Ensimag's Project
The game
Blobwar is played on an 8x8 chessboard where two players (blue and red) compete. Each player has a set of pieces called blobs. The game is played turn by turn. Each turn, whenever possible, the current player chooses a blob and moves it. Any move to an adjacent square (including diagonally) sees the blob duplicated on the target square. It is also possible to jump to a distance of 2 squares, but in this case the blob moves from the starting square to the target square (so there is no duplication). After the move, you look at the squares directly next to the arrival square and all the opposing blobs on these squares change color.
The AI for BlobWar
Greedy algorithm
The first idea was to create the most simple bot for the game using a greedy algorithm. This kind of algo chose the move that will give the best instantaneous result. Since this is the most simple solution possible, every self-respecting developer has to explore other solutions
MinMax algorithm
The MinMax algorithm is quite simple but it still compute the best move that minimize the worst possible score.
More precisely, it computes the minimax value. It represents the smallest score that we can expect without knowing the move of the enemy player. Thus, even if the enemy chose the best move, we can be sure that we will get at least a score of the minimax value.
The minimax value is defined as follows:
$$minimaxvalue = \min_{a_{-i}}\max_{a_i}v_i(a_i, a_{-i})$$
where :
- $i$ is the index of the player of interest.
- $-i$ denotes all other players except player $i$.
- $a_{i}$ is the action taken by player $i$.
- $a_{{-i}}$ denotes the actions taken by all other players.
- $v_{i}$ is the value function of player $i$
The real issue with this algorithm is that is needs to explore every single possibility to find the best move. However, we want a fast algorithm…
Alpha-Beta pruning
Alpha–Beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the MinMax algorithm in its search tree.
It stops evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further.
When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.
I used this algorithm to make the bot faster. When considering a max depth of 5 for the search tree, the Alpha-Beta pruning is 10x faster than the MinMax algorithm
Parallel version
MinMax parallel algorithm
Since the evaluation of the value of each child of a node is independent of the value of the value of the other children, we can compute the value of each child in parallel.
We can then create a parallel version of the Min-Max algorithm.
I implemented this version using the rayon library for rust.
Alpha-Beta pruning in parallel
The Alpha-Beta algorithm is, by its structure, sequential. We can have several approaches to try to make a parallel version:
- We can imagine using mutex to ensure valid writes and reads of the values 𝛼 and 𝛽. We could then in a similar way to the parallel Min-Max algorithm compute the value of each state in parallel up to a given depth and terminate sequentially (still using mutexes). However, using mutexes necessarily involves threads that would be blocked and queued, and thus performance will be reduced.
- Another approach would be to compute a value of 𝛼 and 𝛽 on a few first threads of the initial state sequentially and use these values as initializations for the other threads, for which, this time, we could evaluate their value in parallel considering that each thread has its own 𝛼 and 𝛽 which already have a large enough value to hope to prune the subtrees faster.
- Finally, the version implemented for lack of time and simply exploring each child to a given depth and then initialize a sequential Alpha-Beta
More details
A more precise report of this project with peformance analysis is available here in french