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
|
|
