Solving Connect 4: how to build a perfect AI You are using an outdated browser. Please upgrade your browser to improve your experience.

Pascal Pons

Follow Email<br>LinkedIn<br>Github

Solving Connect Four<br>Part 1 – Introduction<br>Solving Connect Four: history, references and tutorial goals.

Part 2 – Benchmarking solvers<br>Notation and score of Connect 4 positions

Part 3 – MinMax algorithm<br>First version using basic algorithm

Part 4 – Alpha-beta algorithm<br>Pruning the search tree

Part 5 – Move exploration order<br>Alpha-beta is more efficient when you explore best move first

Part 6 – Bitboard<br>Compact and efficient binary representation of Connect 4 positions

Part 7 – Transposition Table<br>Caching intermediate results to avoid computing many times the same score

Part 8 – Iterative Deepening & Null Window<br>Increase progressively the depth of exploration

Part 9 – Anticipate direct losing moves<br>Do not explore moves allowing the opponent to win directly

Part 10 – Better move ordering<br>Explore first move creating alignment opportunities

Part 11 – Optimized transposition table<br>Saving some space using chineese remainder theorem

Part 12 – Lower bound transposition table<br>Keeping lower bound of score in addition to upper bounds