This project is the backend component with REST API of well known game Tic Tac Toe.
- There are 2 players
- Every player is represented by a unique symbol, usually it's X and O
- The board consists of a 3x3 matrix. A player wins if they can align 3 of their markers in a vertical, horizontal or diagonal line
- If no more moves are possible, the game should finish
- Person vs Person
- Person vs AI
Tictactoe microservice properties:
- stateless
- asynchronous
- horizontally scalable
- efficient
- thread safe
Backend framework Spring Boot 2.7.5 using with reactive Webflux and reactive MongoDb for persistence.
mvn package -P docker
docker-compose up -d
Simple test suite consists of:
- Unit tests
- REST API tests.
- Engine performance tests
Test scenarios:
- Game AI vs AI leads to draw
- Lost game against AI
- Draw game against AI
- Person_1 vs Person_2 win, lost, draw
mvn test
[INFO]
[INFO] Results:
[INFO]
[INFO] Tests run: 18, Failures: 0, Errors: 0, Skipped: 0
[INFO]
[INFO] ------------------------------------------------------------------------
[INFO] BUILD SUCCESS
[INFO] ------------------------------------------------------------------------
[INFO] Total time: 31.163 s
[INFO] Finished at: 2022-10-24T19:41:03+02:00
[INFO] ------------------------------------------------------------------------
Detailed description of available endpoints is available
http://127.0.0.1:8080/swagger-ui/#/description
There is a Postman collection available for convenience, but it's possible to use CURL via command line to test if environment is up and running.
There is CLI available in test package with very simple interface
Enter x y coordinates
1 1
| O | | |
| | X | |
| | | |
Active turn PLAYER
Game IN_PROGRESS winner: NOT_DEFINED_YET
package challenge.utils.Cli;
{
"id": "6356ac3bdea5660cd0799a9f",
"status": "CREATED",
"winner": "NOT_DEFINED_YET",
"activeTurn": "PLAYER",
"gameType": "AGAINST_AI"
}
curl -X GET http://127.0.0.1:8080/api/v1/tictactoe/person
{
"id": "6356ac8bdea5660cd0799aa0",
"status": "CREATED",
"winner": "NOT_DEFINED_YET",
"activeTurn": "PLAYER_1",
"gameType": "AGAINST_HUMAN"
}
curl -X GET http://127.0.0.1:8080/api/v1/tictactoe/ai
{
"id": "6356d4419589c93abd0f9cd1",
"status": "CREATED",
"winner": "NOT_DEFINED_YET",
"activeTurn": "PLAYER",
"gameType": "AGAINST_AI"
}
Request
curl -X POST http://127.0.0.1:8080/api/v1/tictactoe?gameId=6356d4419589c93abd0f9cd1 \
-H "Content-Type: application/json" \
--data '{"x": 1, "y": 1}
Response player vs ai
{
"id": "6356d4419589c93abd0f9cd1",
"moves": [
{
"x": 1,
"y": 1,
"number": 1,
"playedBy": "PLAYER"
},
{
"x": 0,
"y": 0,
"number": 2,
"playedBy": "AI"
}
],
"status": "IN_PROGRESS",
"winner": "NOT_DEFINED_YET",
"activeTurn": "PLAYER",
"gameType": "AGAINST_AI"
}
Response player vs player
{
"id": "6356e47b4c46f96b890fd420",
"moves": [
{
"x": 2,
"y": 1,
"number": 1,
"playedBy": "PLAYER_1"
},
{
"x": 1,
"y": 1,
"number": 2,
"playedBy": "PLAYER_2"
},
{
"x": 1,
"y": 0,
"number": 3,
"playedBy": "PLAYER_1"
},
{
"x": 1,
"y": 2,
"number": 4,
"playedBy": "PLAYER_2"
},
{
"x": 2,
"y": 2,
"number": 5,
"playedBy": "PLAYER_1"
},
{
"x": 0,
"y": 1,
"number": 6,
"playedBy": "PLAYER_2"
},
{
"x": 2,
"y": 0,
"number": 7,
"playedBy": "PLAYER_1"
}
],
"status": "FINISHED",
"winner": "PLAYER_1",
"gameType": "AGAINST_HUMAN"
}
The essence of the Minimax algorithm is an alternate enumeration of the possible moves of two players, in which we believe that the player "whose turn" will choose the move that brings the maximum number of points. Suppose that we are playing for player "X", then the description of the algorithm will be something like this:
If the game is over, return the score for player "X" Otherwise, get a list of new play area states for each possible move Estimate the possible payoff for each possible state For each of the possible states, add a "Minimax" estimate of the current state If player's move is "X", return the move with the maximum score If the player's move is "O", return the move with the minimum number of points
The algorithm is recursive using BFS, and the calculation is performed for each of the players in turn until the final payoff is calculated.