ames vs.search problems GAME PLAYIN 雷 疆 用用用用用用 Game tree (2-player,deterministic,turns)Game playing Chapter 6 Chapter 6 1 Outline ♦ Games ♦ Perfect play – minimax decisions – α–β pruning ♦ Resource limits and approximate evaluation ♦ Games of chance ♦ Games of imperfect information Chapter 6 2 Games vs. search problems “Unpredictable” opponent ⇒ solution is a strategy specifying a move for every possible opponent reply Time limits ⇒ unlikely to find goal, must approximate Plan of attack: • Computer considers possible lines of play (Babbage, 1846) • Algorithm for perfect play (Zermelo, 1912; Von Neumann, 1944) • Finite horizon, approximate evaluation (Zuse, 1945; Wiener, 1948; Shannon, 1950) • First chess program (Turing, 1951) • Machine learning to improve evaluation accuracy (Samuel, 1952–57) • Pruning to allow deeper search (McCarthy, 1956) Chapter 6 3 Types of games deterministic chance imperfect information perfect information go, othello chess, checkers, nuclear war bridge, poker, scrabble monopoly backgammon blind tictactoe battleships, Chapter 6 4 Game tree (2-player, deterministic, turns) X X X X X X X X X MIN (O) MAX (X) X X O O O X O O O O O O O MAX (X) X O X O X O X X X X X X X MIN (O) X O X X O X X O X . . . . . . . . . . . . . . . . . . . . . TERMINAL X X −1 0 +1 Utility Chapter 6 5 Minimax Perfect play for deterministic, perfect-information games Idea: choose move to position with highest minimax value = best achievable payoff against best play E.g., 2-ply game: MAX 3 12 8 6 4 2 14 5 2 MIN 3 A 1 A 3 A 2 A 13 A 12 A 11 A 21 A 23 A 22 A 33 A 32 A 31 3 2 2 Chapter 6 6