06.Game playing.pdf

Game playing Chapter 6 Outline  Games  Perfect play （最优策略） — minimax decisions — α-β pruning （剪枝）  Resource limits and approximate evaluation  Games of chance （包含几率因素的游戏）  Games of imperfect information 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) Types of games chess, checkers, Backgammon （西洋双 perfect information Go （围棋）, 陆棋） othello monopoly imperfect information battleships, bridge, poker, scrabble( blind tictactoe 拼字游戏) nuclear war Game tree (2-player, deterministic, turns) Minimax Perfect play （最优策略）for deterministic, perfect-information games Idea: choose move to position with highest minimax value = best achievable payoff against best play 在对手也使用最优策略的条件下，能导致至少不比其它策略差的结果 假设两个游戏者都按照最优策略进行，那么节点的极小极大值就是对应 状态的效用值（对于MAX） • MAX优先选择有极大值的状态 • MIN优先选择有极小值的状态 MINMAX - VALUE( n )  UTILITY (n ) 当n 为终止状态  max s Successors ( n ) MINMAX - VALUE( s ) 当n 为MAX 节点  min s Successors ( n ) MINMAX - VA