Impasse — Alpha-Beta Game-Playing Agent

A C++ implementation of the board game Impasse with an advanced alpha-beta search agent.

About the Game

Impasse is a two-player abstract strategy game, played on a standard checkers set. Singles slide diagonally forward, doubles slide diagonally backward, and the goal is to remove all your checkers from the board. If you have no moves, you're at an "impasse" and must remove one of your own pieces, which is also how the final winning move happens. Draws cannot occur.

The Agent

The agent uses alpha-beta pruning with several enhancements to achieve strong play:

• Transposition table for caching previously evaluated positions
• Move ordering heuristics to improve pruning efficiency
• Iterative deepening for anytime search behavior
• Custom evaluation function incorporating piece positioning, stack control, and board advancement

A full list of implemented features is available in Features.txt.

Project Structure

├── Board.cpp / Board.h           # Board representation
├── BoardState.cpp / BoardState.h # Game state management
├── Game.cpp / Game.h             # Game loop and rules
├── Move.cpp / Move.h             # Move generation and representation
├── Agents/                       # Agent implementations (alpha-beta + baselines)
├── evalTest.cpp                  # Evaluation function tests
├── gameValidator.cpp             # Rule validation
└── main.cpp                      # Entry point

Build & Run

mkdir build && cd build
cmake ..
make
./Impasse

Tech Stack

C++ · CMake · Alpha-Beta Search · Game Tree Search