AdversarialSearchandGamePlaying.pptVIP

Adversarial Search and Game Playing;Topics;What Why;Game-Playing Agent;Relation of Games to Search;Types of games;Types of games;Typical case;Nim;NIM(2,2);Game Search Formulation;Partial Game Tree for Tic-Tac-Toe;Game Tree for NIM(2,2);Optimal strategies;Optimal Play;Minimax Tree;Two-Ply Game Tree;Two-Ply Game Tree;Two-Ply Game Tree;Two-Ply Game Tree;Min-Max Game Tree for NIM(2,2);What if MIN does not play optimally?;Minimax Algorithm;MiniMax Example;Properties of Minimax;Properties of Minimax;Problem of minimax search;Alpha-beta pruning;Alpha-Beta Example;Alpha-Beta Example (continued);Alpha-Beta Example (continued);Alpha-Beta Example (continued);Alpha-Beta Example (continued);Alpha-Beta Example (continued);Alpha-Beta Example (continued);Alpha-Beta Example (continued);Alpha-Beta Example (continued);Alpha-Beta Algorithm;Alpha-Beta Algorithm;General alpha-beta pruning;Alpha-Beta Example;Alpha-Beta Example;Comments: Alpha-Beta Pruning;In general the search tree is too big to make it possible to reach the terminal states! Examples: Checkers: ~1040 nodes Chess: ~10120 nodes SHANNON (1950): Cut off search earlier (replace TERMINAL-TEST by CUTOFF-TEST) Apply heuristic evaluation function EVAL (replacing utility function of alpha-beta) ;Cutting off search;Evaluation function;Evaluation function examples;Issues;Adaptive Search;Games that include chance;Games that include chance;Games that include chance;Games that include chance;Expected minimax value;Position evaluation with chance nodes;Some examples….;Checkers;Chinook vs. Tinsley;Chinook;Backgammon;Chess;Man vs. Machine;Chess;Several versions of the story…;Reversi/Othello;Othello;Go: On the One Side;Go: And on the Other;Perspective on Games: Pro;Perspective on Games: Con;Summary;Additional Resources;Alpha-Beta Example;Alpha-Beta Example;Alpha-Beta Example;Alpha-Beta Example;Alpha-Beta Example;Alpha-Beta Example;Alpha-Beta Example;Alpha-Beta Example;Alpha-Beta Example;Alpha-Beta Example;Alpha-Beta Example;Alpha-Beta Ex