As part of our first year in the engineering school Ecole Centrale de Lyon, we worked, as a team of 6, on creating an application that allows to play the game Blokus (2v2 version) with/against AI or real players.
There are three levels of AI:
Easy : The AI plays randomly
Intermediate : The AI tries to play the hardest pieces to play
Difficult : The AI follows a MinMax using an evluation function
The evaluation function involves three complementary models that are combined together:
Naive : The score is calculated by taking the weighted sum of the the different pieces. The weight is obtained using the following image. It is the ratio between the smallest covering rectangle (Aij) of the piece and the maximum of Aij of the pieces with the same amount of small squares (same i).
Micro : The heuristic here is that by maximizing the amount of moves possible through the placement of a piece, the situation improves. The score is calculated by calculating the amount of corners available.
Macro : The approach is to view the board as a whole and look at the tendency of the pieces. The score is calculated by taking the difference between the barycenters of the pieces of the AI and the closest opponent. If we want the AI to be aggressive, we want the difference to be as little as possible.
