blog.gamesolver.org Open in urlscan Pro
2606:50c0:8000::153  Public Scan

Form analysis
0 forms found in the DOM

Text Content

 * Solving Connect 4: how to build a perfect AI
 * About
 * Connect Four Solver


PASCAL PONS

Follow
 * Email
 * LinkedIn
 * Github

 * Solving Connect Four
   * 1. Introduction
   * 2. Test protocol
   * 3. MinMax algorithm
   * 4. Alpha-beta algorithm
   * 5. Move exploration order
   * 6. Bitboard
   * 7. Transposition table
   * 8. Iterative deepening
   * 9. Anticipate losing moves
   * 10. Better move ordering
   * 11. Optimized transposition table
   * 12. Lower bound transposition table


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

 * Follow:
 * GitHub
 * Feed

© 2019 Pascal Pons. Powered by Jekyll & Minimal Mistakes.