xvi CONTENTS
CHAPTER
9
BOARD GAMES 741
9.1 Game eory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 742
9.1.1 Types of Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 742
9.1.2 e Game Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 744
9.2 Minimaxing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 747
9.2.1 e Static Evaluation Function . . . . . . . . . . . . . . . . . . . . . 747
9.2.2 Minimaxing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 749
9.2.3 e Minimaxing Algorithm . . . . . . . . . . . . . . . . . . . . . . . 750
9.2.4 Negamaxing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753
9.2.5 AB Pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 755
9.2.6 e AB Search Window . . . . . . . . . . . . . . . . . . . . . . . . . 759
9.2.7 Negascout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 761
9.3 Transposition Tables and Memory . . . . . . . . . . . . . . . . . . . . 764
9.3.1 Hashing Game States . . . . . . . . . . . . . . . . . . . . . . . . . . 764
9.3.2 What to Store in the Table . . . . . . . . . . . . . . . . . . . . . . . . 767
9.3.3 Hash Table Implementation . . . . . . . . . . . . . . . . . . . . . . . 768
9.3.4 Replacement Strategies . . . . . . . . . . . . . . . . . . . . . . . . . 769
9.3.5 A Complete Transposition Table . . . . . . . . . . . . . . . . . . . . 770
9.3.6 Transposition Table Issues . . . . . . . . . . . . . . . . . . . . . . . . 771
9.3.7 Using Opponent’s inking Time . . . . . . . . . . . . . . . . . . . . 771
9.4 Memory-Enhanced Test Algorithms . . . . . . . . . . . . . . . . . . . 772
9.4.1 Implementing Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . 772
9.4.2 e MTD Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 774
9.4.3 Pseudo-Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 775
9.5 Monte Carlo Tree Search (MCTS) . . . . . . . . . . . . . . . . . . . . . 776
9.5.1 Pure Monte Carlo Tree Search . . . . . . . . . . . . . . . . . . . . . . 776
9.5.2 Adding Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . 782
9.6 Opening Books and Other Set Plays . . . . . . . . . . . . . . . . . . . 783
9.6.1 Implementing an Opening Book . . . . . . . . . . . . . . . . . . . . 783
9.6.2 Learning for Opening Books . . . . . . . . . . . . . . . . . . . . . . 784
9.6.3 Set Play Books . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785
9.7 Further Optimizations . . . . . . . . . . . . . . . . . . . . . . . . . . . 785
9.7.1 Iterative Deepening . . . . . . . . . . . . . . . . . . . . . . . . . . . 786
9.7.2 Variable Depth Approaches . . . . . . . . . . . . . . . . . . . . . . . 787
9.8 Game Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 788
9.8.1 Creating a Static Evaluation Function . . . . . . . . . . . . . . . . . . 791
9.8.2 Learning the Static Evaluation Function . . . . . . . . . . . . . . . . 794
9.9 Turn-Based Strategy Games . . . . . . . . . . . . . . . . . . . . . . . . 797
9.9.1 Impossible Tree Size . . . . . . . . . . . . . . . . . . . . . . . . . . . 798
9.9.2 Real-Time AI in a Turn-Based Game . . . . . . . . . . . . . . . . . . 799