DOC PREVIEW
Penn CIT 594 - Alpha Beta Search

This preview shows page 1-2-3-4-5-6 out of 18 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Alpha-Beta SearchTwo-player gamesPayoffsZero-sum gamesA trivial “game”MinimaxingHeuristicsPBVsUsing PBVs (animated)Bringing up valuesAlpha cutoffsAlpha cutoffs, in more detailBeta cutoffsUsing beta cutoffsThe importance of cutoffsHeuristic alpha-beta searchingBest game playing strategiesThe EndAlpha-Beta SearchTwo-player games•The object of a search is to find a path from the starting position to a goal position•In a puzzle-type problem, you (the searcher) get to choose every move•In a two-player competitive game, you alternate moves with the other player•The other player doesn’t want to reach your goal•Your search technique must be very differentPayoffs•Each game outcome has a payoff, which we can represent as a number•By convention, we prefer positive numbers•In some games, the outcome is either a simple win (+1) or a simple loss (-1)•In some games, you might also tie, or draw (0)•In other games, outcomes may be other numbers (say, the amount of money you win at Poker)Zero-sum games•Most common games are zero-sum: What I win ($12), plus what you win (-$12), equals zero•Not all games are zero-sum games•For simplicity, we consider only zero-sum games•From our point of view, positive numbers are good, negative numbers are bad•From our opponents point of view, positive numbers are bad, negative numbers are goodA trivial “game”•Wouldn’t you like to win 50?•Do you think you will?•Where should you move?Opponent’s move7 3 -8 50Your moveMinimaxingOpponent’s move7 3 -8 50Your move• Your opponent will choose smaller numbers• If you move left, your opponent will choose 3• If you move right, your opponent will choose -8• Therefore, your choices are really 3 or -8• You should move left, and play will be as shown3 -83Heuristics•In a large game, you don’t really know the payoffs•A heuristic function computes, for a given node, your best guess as to what the payoff will be•The heuristic function uses whatever knowledge you can build into the program•We make two key assumptions:–Your opponent uses the same heuristic function–The more moves ahead you look, the better your heuristic function will workPBVs•A PBV is a preliminary backed-up value–Explore down to a given level using depth-first search–As you reach each lowest-level node, evaluate it using your heuristic function–Back up values to the next higher node, according to the following rules:•If it’s your move, bring up the largest value, possibly replacing a smaller value•If it’s your opponent’s move, bring up the smallest value, possible replacing a larger valueUsing PBVs (animated)YourmoveYourmoveOpponentsmove• Do a DFS; find an 8 and bring it up88• Explore 5; smaller than 8, so ignore it58• Backtrack; bring 8 up another level22• Explore 2; bring it up9• Explore 9; better than 2, so bring it up, replacing 29-3• 9 is not better than 8 (for your opponent), so ignore it• Explore –3, bring it up• Etc.Bringing up values•If it’s your move, and the next child of this node has a larger value than this node, replace this value•If it’s your opponent’s move, and the next child of this node has a smaller value than this node, replace this value•At your move, never reduce a value•At your opponent’s move, never increase a valueAlpha cutoffs•The value at your move is 8 (so far)•If you move right, the value there is 1 (so far)•Your opponent will never increase the value at this node; it will always be less than 8•You can ignore the remaining nodes8 5 2 9 -3 18 9 1881YourmoveYourmoveOpponentsmovealphacutoffAlpha cutoffs, in more detail•You have an alpha cutoff when:–You are examining a node at which it is your opponent’s move, and–You have a PBV for the node’s parent, and–You have brought up a PBV that is less than the PBV of the node’s parent, and–The node has other children (which we can now “prune”)8 5 2 9 -3 18 9 1881YourmoveYourmoveOpponentsmovealphacutoffnode being examinedparent (has PBV of 8)Beta cutoffs•An alpha cutoff occurs where–It is your opponent’s turn to move–You have computed a PBV for this node’s parent–The node’s parent has a higher PBV than this node–This node has other children you haven’t yet considered•A beta cutoff occurs where–It is your turn to move–You have computed a PBV for this node’s parent–The node’s parent has a lower PBV than this node–This node has other children you haven’t yet consideredUsing beta cutoffs•Beta cutoffs are harder to understand, because you have to see things from your opponent’s point of view•Your opponent’s alpha cutoff is your beta cutoff•We assume your opponent is rational, and is using a heuristic function similar to yours•Even if this assumption is incorrect, it’s still the best we can doThe importance of cutoffs•If you can search to the end of the game, you know exactly how to play•The further ahead you can search, the better•If you can prune (ignore) large parts of the tree, you can search deeper on the other parts•Since the number of nodes at each level grows exponentially, the higher you can prune, the better•You can save exponential timeHeuristic alpha-beta searching•The higher in the search tree you can find a cutoff, the better (because of exponential growth)•To maximize the number of cutoffs you can make:–Apply the heuristic function at each node you come to, not just at the lowest level–Explore the “best” moves first–“Best” means best for the player whose move it is at that nodeBest game playing strategies•For any game much more complicated than tic-tac-toe, you have a time limit•Searching takes time; you need to use heuristics to minimize the number of nodes you search•But complex heuristics take time, reducing the number of nodes you can search•Seek a balance between simple (but fast) heuristics, and slow (but good) heuristicsThe


View Full Document

Penn CIT 594 - Alpha Beta Search

Documents in this Course
Trees

Trees

17 pages

Searching

Searching

24 pages

Pruning

Pruning

11 pages

Arrays

Arrays

17 pages

Stacks

Stacks

30 pages

Recursion

Recursion

25 pages

Hashing

Hashing

24 pages

Recursion

Recursion

24 pages

Graphs

Graphs

25 pages

Storage

Storage

37 pages

Trees

Trees

21 pages

Arrays

Arrays

24 pages

Hashing

Hashing

24 pages

Recursion

Recursion

25 pages

Graphs

Graphs

23 pages

Graphs

Graphs

25 pages

Stacks

Stacks

25 pages

Recursion

Recursion

25 pages

Quicksort

Quicksort

21 pages

Quicksort

Quicksort

21 pages

Graphs

Graphs

25 pages

Recursion

Recursion

25 pages

Searching

Searching

24 pages

Counting

Counting

20 pages

HTML

HTML

18 pages

Recursion

Recursion

24 pages

Pruning

Pruning

11 pages

Graphs

Graphs

25 pages

Load more
Download Alpha Beta Search
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Alpha Beta Search and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Alpha Beta Search 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?