# Shared Flashcard Set

## Details

AI day 2
fd
19
Agriculture
Pre-School
10/28/2009

Term
 Turn-based game playing is a well-defined problem. It has:
Definition
 An initial state A set of goal states A set of reachable states 1+ Operators
Term
 Game-playing is what kind of data behavior and why?
Definition
 synthesis - because it generates a game move.
Term
 What data structures and functions are needed to play games?
Definition
 GameState class (contains information about pieces, cards, players, etc) Move class (represents a single move by a player in a game) Terminal function (tells us when the game is over) Evaluation function (tells of the value of the game’s state) - can be overloaded (can tell us who is winning/who does it look like is winning)
Term
 what does the Greedy Method do?
Definition
 picks the move that yields the most immediately valuable game state
Term
 What are the benefits of the Greedy Method?
Definition
 Fast Moderate Memory Moderate CPU time
Term
 What are the drawbacks of the Greedy Method?
Definition
 Ignores opponent’s reaction Short sighted
Term
 What does the Minimax Method do?
Definition
 searches through several levels of moves, assuming the opponent always makes the best move available.
Term
 What are the drawbacks of the Minimax Method?
Definition
 Depth-First Traversal - Goes till the end of the game - takes too long No “Forfeit” Moves - if you can't make a move, your oppoent can go again Unnecessary Branching No random capacity – dice, cards, etc.
Term
 What are the Mitigation Techniques?
Definition
 Depth Limit - look ahead at a certain amount of moves Forfeit Recognition - when a player doesn’t have another move so other player can go again Alpha-Beta Pruning - cut off certain branches in the search tree that we can determine will not yield our answer Chance Nodes - dice and randomness
Term
 What is something we can do to optimize Minimax?
Definition
 Depth Limit : prevent Minimax from running forever Forfeit Recognition : incorporate the loss of a move by a player
Term
 What is Alpha-Beta Pruning?
Definition
 s a branch-and-bound extension to Minimax that “prunes” (eliminates) unnecessary branches of the search tree
Term
 What does Expectiminimax works best when?
Definition
 going only a few ply deep
Term
 What are drawbacks of Expectiminimax?
Definition
 Tree grows even faster than Minimax - become less accurate over a period of time Many games are actually psychological (Poker) Results can vary as based on move that is “likely” good - the more nodes we have the less accurate it is
Term
 What can you use chance nodes for?
Definition
 to predict gameplay by finding expectimax and expectimin values.
Term
 DO: Write pseudocode for the general Minimax Algorithm (without optimizations)
Definition
Term
 DO: Fill out a Minimax search tree - make up your own values
Definition
Term
 DO: Prune a Minimax search tree using Alpha-Beta Pruning (check lab2 doc)
Definition
Term
 Identify Minimax Algorithm optimization techniques most commonly used to speed-up the search process
Definition
 Depth Limit : prevent Minimax from running forever Forfeit Recognition : incorporate the loss of a move by a player
Term
 DO: Fill out an Expectiminimax search tree (see lab2 doc)
Definition
Supporting users have an ad free experience!