Algo minimax + board game
Project 17
Caracteristics
- Date : October 2020
- State : Finished
- Download link
- Themes : board game, AI using the minimax algorithm
- Tags : Programmation, Processing, Video game
Description
In semester 3 at the IUT (computing science), we had courses on advanced algorithms To illustrate the course, we had the presentation of a board game that I found interesting. First, I wanted to remake this game using Processing. Two reasons for this choice, it is very fast to obtain a result, and we have access to interesting graphic features, like a lot of drawable shapes or shaders. The principle of the board game is simple, there are connected squares and black and white pieces placed randomly. When it is the turn of one of the two players, he can move his piece to eat the opponent's piece if his square is connected to a square occupied by this enemy piece. He moves it forward and eats the opponent's piece. Then it's the other player's turn to play. In the end, the one who can't play anymore has lost.
When I finished coding the game, I had fun adding little features like the dark theme, which I activated by default. The dark mode is life... if you like to take care of your eyes. I also added two boards and I added the ability to play against an AI. Before talking about the AI, I also used a feature that Processing has and that I just talked about, the shaders. I wanted to see the game played (and finished), on the end of game screen. That is, taking a screenshot of the end of the game and drawing it in the background of the end game screen The background image of the game didn't work too well. The background image was too sharp. So I added a shader that renders a blurred image before displaying it.
During the course we had, the board game was used to illustrate an example of a minimax algorithm So I wanted to code an AI that would make its decisions based on a value tree constructed from the moves potentially played. The AI would make its decisions with the best moves while taking into account what are the best moves for the opponent. However, to have a tree of values, you still need to have the value of a board. I wrote some rules hidden to the player to establish a score associated with each game state. Our victory is the minimum value, the AI's victory is the maximum value. For example, chains of pieces bring much more score, for the one we calculate the score, because piece can revenge. In the end, the AI works quite well but performs its calculations over 5 moves, more depth causes a significant slowdown of the AI. Another alternative calculation that could be implemented is the calculation of the number of capturable pieces. If there is an even number of pieces that are capturable, it is not good for the player. For two capturable pieces, we play, then the opponent plays, finally we can't play anymore; we have lost.
Visuals (Click on one pick to enlarge it)
Hey test test