-
Board: Quoridor is played on a game board of 81 square cells (9x9) and each player starts with 10 walls. However, the game can be also played in different board sizes with a different number of starting walls.
-
Game setup: Each player is represented by a pawn (black or white) which is placed at the center space of the baseline.
-
Gameplay: The black player starts first, then players alternate turns. Each player in turn, chooses to move his pawn or to put up one of his walls. If he runs out of walls, the player can only move his pawn.
-
Pawn moves: The pawns are moved one square at a time, horizontally or vertically, forwards or backwards. The pawns must get around the walls. When two pawns face each other on neighboring squares which are not separated by a wall, the player whose turn it is can jump the opponent's pawn (and place himself behind him), thus advancing an extra square. If there is a wall behind the said pawn, or the square behind him is out of the board, the player can place his pawn to the left or the right of the other pawn.
-
Positioning of the walls: Walls are flat two-cell-wide pieces which can be placed between 2 sets of 2 squares. The walls can be used to facilitate the player's progress or to impede that of the opponent, however, an access to the goal line must always be left open.
-
End of the game: The first player who reaches any of the squares opposite of his baseline is the winner.
The commands follow the protocol that can be viewed in detail here. In short:
playmove player position
example: playmove white e2 - move white's pawn to E2
playwall player position orientation
examples:
playwall black a3 horizontal(OR h) - black places a horizontal wall starting at A3
playwall white b4 vertical(OR v) - white places a vertical wall starting at B4
genmove player
example: genmove white - engine plays a move for white
showboard
Draw the board.
quit
Exit the game.
undo n
The game goes n moves back.
boardsize n
The board size is changed to n.
walls n
The number of walls for each player is changed to n.
list_commands
List all commands.
-
The engine is based on Alpha-beta pruning that uses iterative deepening in order to search at the maximum depth possible at a fixed, set, time. A transposition table is also used as an enhancement to this idea by saving and using previously found search results when faced with transpositions (positions that can be reached through a different move order).
-
The evaluation uses a system similar to chess's one, where if the evaluation is positive it is believed that white has an advantageous position, if it is negative it's believed that black is the one with the advantage and if it is 0, neither player has an advantage. The way we evaluate positions is by using 3 pieces of information. The first, is the steps both players need in order to win by using a factor of 1. The second, is the number of steps each player needs in order to get to the next row by using a factor of 0.6. The third, and final, is the number of walls each player has remaining (factor 0.7). So, the evaluation comes as follows:
blackDistanceFromWinning-whiteDistanceFromWinning + 0.6*(blackDistanceFromNextRow - whiteDistanceFromNextRow) + 0.7*(whiteWalls - blackWalls)
A referee quoridor_referee.py that allows two programs that follow the protocol mentioned above to play against each other is also provided. Check the makefile for its usage at referee settings section.
maketo compilemake playto compile and playmake clearto clear excess object files created during compilationmake refto use the referee, the settings can be changed at the makefile
The project is based on assignment 4, semester 1, dpt. of Informatics and Telecommunications - UoA (2021), where it won first place at the department's local competition. Other programs, including but not exclusively, from the competition can be found over at the otherProgs folder.