A Connect Four player
The problem
Build a program that plays Connect Four well, using depth-limited minimax with alpha-beta pruning and an evaluation function, and show how strong it is.
Requirements
- Represent the 6 × 7 board, legal moves, wins and draws
- Search with alpha-beta pruning to a depth that keeps each move under a few seconds
- Score unfinished positions with an evaluation function based on open lines of two and three
- Order moves from the centre outwards and report how many positions each search visits
- Play against a random player and against a shallower version of itself, and record the results
Technologies
- Python
- Recursion
- Alpha-beta pruning
- Evaluation functions
Step by step
- Write the board, move generation and win detection, with tests for every direction of four in a row.
- Add plain minimax at a small depth and check it never misses a win in one move.
- Add alpha-beta pruning and confirm it chooses the same moves while visiting fewer positions.
- Write the evaluation function and tune its weights by playing matches.
- Add move ordering and iterative deepening with a time limit.
- Run matches and write up the results.
Expected result
A Connect Four program that beats a random player every time and explains its search with position counts.
How it is evaluated
- Moves are always legal and wins are detected in every direction
- Alpha-beta and minimax agree on the chosen move in test positions
- The program wins at least 95% of games against a random player
- The write-up shows the effect of pruning and move ordering with numbers
Ways to improve it
- Add a transposition table to reuse evaluated positions
- Use Monte Carlo tree search instead of alpha-beta and compare
- Learn the evaluation weights from self-play