Game PlayingChapter 6课件.ppt

Two-ply minimax and one of two possible second MAX moves (Nilsson, 1971) Pruning the search tree The technique is called alpha-beta pruning Basic idea: if a portion of the tree is obviously good (bad) don’t explore further to see how terrific (awful) it is Remember that the values are propagated upward. Highest value is selected at MAX’s level, lowest value is selected at MIN’s level Call the values at MAX levels α values, and the values at MIN levels β values * Game Playing Chapter 6 Additional references for the slides: Luger’s AI book (2005). Robert Wilensky’s CS188 slides: /~wilensky/cs188/lectures/index.html Tim Huang’s slides for the game of Go. Game playing Games have always been an important application area for heuristic algorithms. The games that we will look at in this course will be two-person board games such as Tic-tac-toe, Chess, or Go. Types of Games Deterministic Chance Perfect information Chess, Checkers Go, Othello Backgammon Monopoly Imperfect Information Battleships Blind tictactoe Bridge, Poker, Scrabble, Nuclear War Tic-tac-toe state space reduced by symmetry (2-player, deterministic, turns) A variant of the game nim A number of tokens are placed on a table between the two opponents A move consists of dividing a pile of tokens into two nonempty piles of different sizes For example, 6 tokens can be divided into piles of 5 and 1 or 4 and 2, but not 3 and 3 The first player who can no longer make a move loses the game For a reasonable number of tokens, the state space can be exhaustively searched State space for a variant of nim Exhaustive minimax for the game of nim Two people games One of the earliest AI applications Several programs that compete with the best human players: Checkers: beat the human world champion Chess: beat the human world champion Backgammon: at the level of the top handful of humans Go: no competitive programs (? In 2008) Othello: good programs Hex: good programs Search techniques for 2-person games The search