Pascal Pons

Pascal Pons

Solving Connect Four

Part 1 – Introduction

Solving Connect Four: history, references and tutorial goals.

Part 2 – Benchmarking solvers

Notation and score of Connect 4 positions

Part 3 – MinMax algorithm

First version using basic algorithm

Part 4 – Alpha-beta algorithm

Pruning the search tree

Part 5 – Move exploration order

Alpha-beta is more efficient when you explore best move first

Part 6 – Bitboard

Compact and efficient binary representation of Connect 4 positions

Part 7 – Transposition Table

Caching intermediate results to avoid computing many times the same score

Part 8 – Iterative Deepening & Null Window

Increase progressively the depth of exploration

Part 9 – Anticipate direct losing moves

Do not explore moves allowing the opponent to win directly

Part 10 – Better move ordering

Explore first move creating alignment opportunities

Part 11 – Optimized transposition table

Saving some space using chineese remainder theorem

Part 12 – Lower bound transposition table

Keeping lower bound of score in addition to upper bounds