Game Engine

(Northwestern CS348 Lab #2)

Introduction: Konane

Also known as Hawaiian Checkers, Konane is a strategy game played between two players. Players alternate taking turns, capturing their opponent's pieces by jumping their own pieces over them (if you're familiar with checkers, there is a strong structural analogy to be made here, except the jumping is not diagonal but orthogonal, and while multiple jumps are allowed in a turn, all jumps have to occur in the same direction). The first player to be unable to capture any of their opponent's pieces loses.

The full rules can be read here or here, and here's a nice video explaining the rules simply as well.

Here's a (rather terse) version of the rules, though:

1. Black typically starts. They take one of their pieces off the board. Now, the piece shown below as taken off is actually not the one that's taken off. If we imagine a (row, column) coordinate system for the pieces such that the top-left white piece is in position (1, 1), and the top-right black piece is in position (1, 8), then the very first move of the game sees a black piece taken off from the two right in the middle of the board—so, (4, 5) and (5, 4)—or from such a pair in any of the corners of the board. Please make sure your implementation honors that rule.

1. White then takes one of their pieces off the board from a space orthogonally adjacent to the piece that black removed.

1. Each player then alternately moves their pieces in capturing moves. A capturing move has a stone move in an orthogonal direction, hopping over an opponent's piece. Multiple captures may be made in a turn, as long as the stone moves in the same direction and captures at least one piece.

1. The first player to be unable to capture a piece loses. :(

Play the game

This program implements Minimax and Alpha-Beta Pruning for an agent playing Konane. Wait, isn't Alpha-Beta Pruning a variant of Minimax? Yes, it is. It's just that here we're using Minimax and Alpha-Beta Pruning to respectively refer to Minimax WITHOUT Alpha-Beta Pruning and Minimax WITH Alpha-Beta Pruning.

Playing the game interactively may only work on Linux and Mac.

Run the following from your terminal:

python main.py $P1 $P2

By default, main.py will setup a human player versus a random player on a board that is 10x10. During Human mode, move the cursor with the ARROW keys and select the tile with SPACE. When it is a computer's turn, advance the game with the SPACE key. To see the game board in your terminal, you need a minimum terminal size of (rows + 2) x (columns + 2) to see the whole board. To exit the game, kill the process in your terminal (e.g., with CTRL-c).

You can change the game settings by passing in values to python main.py. You need to pass in exactly two arguments. Valid arguments are as follows:

• H (Human)—manually select the tile to move and to where you will move it. Legal moves will be executed.
• D (Deterministic)—the agent will select the first move that it finds (the leftmost option in the tree) during its traversal.
• R (Random)—the agent will pick a random move.
• M (Minimax)—the agent will pick a move using the Minimax algorithm. You will be prompted for a maximum search depth.
• A (Alpha-Beta pruning)—the agent will pick a move using A-B pruning. You will be prompted for a maximum search depth.

Passing in an invalid number or type of arguments will result in the system defaulting to a human vs. a random player.

Notes

On the codebase:

• player.py— contains MinimaxPlayer and AlphaBetaPlayer
• main.py—to play the game (in Human mode) or to watch your agents duke it out, run python main.py. Use the arrow keys and the spacebar to select your actions.
• test.py—run tests with python test.py.
• game_manager.py—holds the board representation and handles turn-taking.
• game_rules.py—code determining available moves, their legality, etc.
• You can change the type of player, the board size, etc. in main.py