This project was created as a part of a challenge for the Eventbrite Development Academy held in May 2022.
The aim of the project was to create an Artificial Intelligence able to play a mod version of Quoridor developed by the EDA team.
The code has two distinct branches to hold logic for different algorithms to play the game.
The base code consists of a series of classes and functions that serve the purpose of connecting with the socket and managing the state of the game. To that end, the bot has a ConnectionManager that is capable of managing as many Challenges as the player is invited to participate. When the action 'your-turn' is sent by the server, the Challenge object decides whether it will play by moving a pawn on the board or placing a wall. This decision is based on a representation of the state of the game that analises the scores of the players according to the elements of the board.On this branch, it is possible to configure the AI to play with two different approaches.
- Choosing the shortest path towards the opposite end of the board.
- Choosing the best possible move, anticipating the best possible moves of the opponent
As the board gets more complex by the movement of the pawns and the walls that are being built. The pawn faces the problem of getting towards the target position using the shortest path possible. It is implemented a search algorithm that traverses the board looking for valid spots where the user could move, and accounts for the distance of the possible movements.
Minimax on Wikipedia.In order to decide the best possible move, this algorithm helps the game state manager decide anticipating the scores of the board given that all players choose to play the shortest way to the end of the board. It is configured to anticipate up to three moves of each player ahead.
However, this seemed to be the right approach to this problem. It faced performance issues. As every move took 3 secs on average to be decided.
To overcome the performance issues above mentioned, it was set this alternative to not anticipate the shortest path for each pawn, but assessing the score of the board for every possible move of every pawn on the board.
The result of this approach was better in performance, with only 1 second on average per move. Nevertheless, the final score of the AI was lower than using just the Shortest Path Algorithm.
As a part of the project, it was demanded to aim to the best test coverage possible.
I implemented a TDD policy to meet the highest score possible. It was a wise decision as it speed up the debugging process for the development of the most complex scenarios such as getting the valid moves for each pawn, calculating the score of the board, anticipating game states, and looking for the best moves to be done.
Following, there are some screenshots for the testing of the function get_valid_move for the pawns:
These are two examples of the results of the BFS implementation.
