A Connect 4 game built with Python and Pygame, featuring an AI opponent powered by the Minimax algorithm with alpha-beta pruning and iterative deepening.
- Minimax AI with Alpha-Beta Pruning — Efficient game tree search with configurable depth
- Iterative Deepening — Progressively deeper search for stronger play within time constraints
- Transposition Table — Caches evaluated positions to avoid redundant computation
- Heuristic Board Evaluation — Scores non-terminal positions based on threats, center control, and blocking potential
- Two Game Modes:
- AI vs AI — Watch two Minimax agents battle it out
- AI vs Human — Play against the AI as Player 2 (Yellow)
- Python 3.8+
- Pygame
pip install pygameAI vs AI (default):
python main.pyAI vs Human:
python main.py --p2 human| Key / Action | Description |
|---|---|
| Mouse click | Drop a piece (Human mode, Player 2 only) |
| R | Restart the game |
| Close window | Quit |
Connect4/
├── main.py # Pygame GUI and game loop
├── engine_C4.py # Game engine: state, legal moves, win detection, board evaluation
├── Minimax_agent.py # Minimax agent with alpha-beta pruning and iterative deepening
└── README.md
The game engine represents the board as a flat tuple of 42 cells (6 rows x 7 columns). Players are encoded as +1 (Red) and -1 (Yellow).
The Minimax agent searches the game tree using:
- Iterative Deepening — Searches depth 1, then 2, ..., up to
max_depth, so the best move found so far is always available - Alpha-Beta Pruning — Cuts off branches that can't influence the final decision, dramatically reducing the search space
- Heuristic Evaluation — At the depth limit, positions are scored by counting threats (2-in-a-row, 3-in-a-row), center column control, and blocking urgency
- Transposition Table — Memoizes evaluated states to skip duplicate subtrees
Player 1 (Red) uses depth 5 and Player 2 (Yellow) uses depth 4 by default.