Five In A Row, also known as Caro, is a popular Vietnamese logic game. The game rule is similar to Tic-Tac-Toe; however, a player needs 5 move in a row to win instead of 3. The board size is 20-by-20, much larger than the Tic-Tac-Toe board. Players take turn placing moves on available spaces on a grid, and whoever reach 5 moves in a row first win the game.
In this project, I developed a web-based version of the game. Users can sign up, and then log into the web app to play games against other players or against an AI.
Project deployed here.
User can sign up for an account, then use that account to log-in and play a game! If you don't want to sign up, you can use this credentials to log in:
Username: guest
Password: 12345
After logging in, you can start a Player-versus-Player game and wait for another player to join with the provided game Id. Alternatively, you can play a game against the game AI.
I initially built a console-based version of the game in Java to practice Object-Oriented Design and to have a try at implementing a game AI. Once I decided to deploy the game onto the web, Spring Boot is a logical solution to building the back-end using my existing code.
Game API is implemented at endpoint /game :
- POST to
/start: start a game given the first player PlayerX - POST to
/connect: connect to a game given the game ID and second player PlayerO - POST to
/connect/random: connect to a random game as second player PlayerO - POST to
/connect/computer: connect to an AI game as second player PlayerO - POST to
/gameplay: add a move to game with given ID - GET to
/gameplay/computer: get game state after a move is made by game AI
User API is implemented at endpoint /users:
- POST to
/register: register user with given credentials - POST to
/login: verify user with given credentials
A WebSocket server is set up at STOMP endpoint /gameplay to allow for two-way communication between the client and server for real-time game updates. Every time a new game is started by the client, it automatically established WebSocket connection to the server and subscribe to listen at /topic/game-progress/<GAMEID>.
Whenever a request is made to /connect, /connect/computer, /gameplay and /gameplay/computer, the REST controller automatically sends an updated version of the game object to /topic/game-progress/<GAMEID>. The subscribers (clients) can obtain this and display an updated version of the game. Using WebSocket, playerX can get updated whenever playerO makes a move, and vice versa.
MongoDB is chosen for this project due to its ease in storing complex Java objects.
- Each document within this collection is composed of a
username,passwordand unique_id. - Mongo Repository implements CRUD functionality, as well as querying by username and by credentials.
- Mongo Repository implements CRUD functionality.
- Each document composes of:
statusrepresents game status as 'NEW', 'IN-PROGRESS', or 'FINISHED'playerXstores a User object representing player XplayerOstores a User object representing player Owinnerstores a User object representing winner (initialized to NULL)boardstores a GameBoard object representing current board state
-
Gameclass represents an instance of a game. -
userpackageUserclass represents a user of the web app.AIPlayerimplements the Singleton design pattern to prepresent one single AI player across all games
-
GamePlayrepresents a move (with row and column coordinates, as well as gameID the move belongs to) -
Symbolenum represents X, Y, or EMPTY (valid contents of each cell on the board) -
boardpackageGameBoardrepresents the game board as a 2D matrix of Symbol objects and have methods to extract certain information from current board state, such as checking for consecutive streaks
-
streakpackageStreakclass stores count of unblocked and blocked-on-one-side streaks of a certain length. It does not store count of streaks that are blocked on both sides, since that streak cannot be added to on either side and is therefore useless in terms of gameplayStreakListstores a list of Streak object with different lengths (from 1 to 5)
-
MinimaxAIclasse represents the brain of the AI, helping to find the optimal move for the AI to make given a board state
Five In A Row is essentially a more complex version of Tic Tac Toe, since more moves are needed to win and the board is much larger. Minimax algorithm is commonly used to create AI player for two player games, including Tic Tac Toe. The minimax algorithm works backwards from the end of the game, and at each step assuming either that the opponent will make a move to minimize the probability of winning for the current player or that the current player will make a move to maximize their chances of winning.
As seen from the image above, this algorithm considers all possible moves until game is terminated. This is manageable for Tic Tac Toe, but for games with larger dimension, it is evident to be very computationally intensive to consider all possible legal moves on the board. I made two modifications to adapt the algorithm for this game.
At each step along the algorithm, original minimax considers all possible legal moves. However, in Five In A Row, an observation can be made that you should only make a move that is adjacent to another existing move, either to block an opponent or add to s streak of your own. If we reduce the action set to only moves that are adjacent to at least another existing move on the board, we can reduce computation effort significantly.
GameBoard class offers method isDisconnected to check if a move is adjacent to any other moves. MinimaxAI can use this public method to only add a potential move to action set if it is not disconnected.
Left: disconnected move, Right: connected move
Original Minimax algorithm would explore moves until the game is terminated. This can be exponentially intensive in Five In A Row, as it is strategically more complex and more moves are made before the game is terminated. It is not possible to consider all moves until termination, so I implemented a depth-limited algorithm that use a utility function to score how optimal a move is.
The utility scoring/estimating function utilizes heuristic/knowledge of the game to minimize the depth needed to make a quality decision. Utility scores range from 1 (AI player is winning) to -1 (opponent player is winning). A list of streaks of varying length (1-5) is compiled from a board state, and each streak is scored differently based on how favorable they are. Since the objective is to make 5-in-a-row, it is favorable to make streaks as long as possible, so streaks with longer length are scored higher than shorter lengths. Since an unblocked streak offers more potential for expanding, unblocked streak are scored higher than blocked ones with the same length.
Certain board states are win-adjacent, in which no winning streak can be detected but streaks that will result in a win condition is detected. One such example is an unblocked streak-of-4, it is not 5-in-a-row, but there is no way an opponent can block both side to prevent this from expanding to 5-in-a-row. These win-adjacent streak are scored at 1.0 in the utility function.
Opponent cannot prevents current player from winning with win-adjacent moves: unblocked 4-in-a-row, two connected 3-in-a-row, or connected 4-in-a-row and 3-in-a-row
I incorporated scoring of both the AI moves and opponent moves. By using knowledge of the game, I was able to created a game AI needing to only consider all moves within a depth of 2.
Utility of a board state = Utility of all streaks by AI - Utility of all streaks by opponent
- The server programs the AI to be the starting player of the game in a game against computer. As with most 2-player game of similar character (chess, Tic Tac Toe), first player has a game advantage. In the future, I want to work on adapting the back-end to support AI player playing second.
- I also want to explore implementing other AI algorithm, such as Q-learning, etc.
- Configure the project for HTTPS requests and re-deploy the web app over HTTPS protocol for better security.
- Back-end REST API based upon this tutorial on implementing Server and WebSocket in SpringBoot
- Web Development Course by Professor Jose Annunziato
- README template
- Artificial Intelligence course by Harvard University
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent