Backgammon Game Engine and Player AI
For a school project in software engineering, a teammate and I made a game engine and some AI players for the board game Backgammon. Implemented in Python, this project included an internal representation of the board that updates each turn, a rule checker that presents all valid moves, and ensures no player is cheating, multiplayer features, like support for network play and a tournament organizer, and 3 difficulty levels of AI opponents. For those unfamiliar, Backgammon is a turn-based game where players must move their checkers from the “bar” to the “home” at the end of the board. Two dice are rolled and those dice are used to move a checker each. One player can “bop” another player’s piece if they land on a space where their opponent only has one checker. If a player has multiple checkers on a space then that space is protected from bops. Having a single checker on a space is referred to as a “blot”, and having many checkers on a space is referred to as a “candlestick.” The front end and UI for the game is not included in this work. The code can be found on my GitHub: https://github.com/damondamico/backgammon/tree/main
Game Representation
The board is represented by a nested dictionary. The first layer separates the two players, “black” and “white”, and the second layer holds what spaces their checkers are on. The layer of separation between players was included so that on each player’s turn the positions of their pieces can be found quickly, rather than searching the board and sifting between white and black. This can be seen in the file dict_board.py.
Rule Checker
The validity of a player’s move is determined by feeding the dice roll, current board state, and proposed move to the rule checker. This object constructs a set of all valid moves and sees if the proposed move belongs to it. In Backgammon, if the player rolls 2 of the same number, they get to use the dice twice. For example, when rolling two 5s the player can move 4 pieces 5 spaces. This results in two different cases when calculating the set of all valid moves. For non doubles, this operation is straightforward. All possible moves with the first die are calculated, then all possible moves with the second die are calculated based on all states after the first die’s moves. For the case of doubles, this operation is trickier. A recursive algorithm constructs and walks a tree of possible moves, depth first, until a depth of 4 is reached, since the number rolled can be applied 4 times. This can all be seen in the file rule_checker.py.
Opponent AI
Easy
The easy opponent chooses random moves from the set of available moves. It sometimes shows a stroke of brilliance, but often blunders and its actions make no sense.
Medium
The medium opponent is aggressively offensive, trying to mess with the player as much as possible. It will try to advance the game, but will attempt to ‘bop’ or knock a player’s checker back to the bar when possible. The AI chooses its moves by calculating a score for each possible move. For a possible move, the score is the sum of the AI’s opponent’s pieces’ distance from the home, minus the sum of the AI’s pieces’ distance from the home. The move with the highest score is chosen. The medium player will sometimes act against it’s best interest to mess with the player.
Hard
The hard opponent’s move ranking function is similar to the medium opponent’s, but with some added strategies. The score is calculated the same way, except there are penalties for leaving “blots” or undefended single checkers, and making “candlesticks” by having more than 3 checkers on one space. Where the medium player is purely offensive, the hard player knows that defense wins championships.