Alpha-Beta SearchTwo-player gamesPayoffsZero-sum gamesA trivial “game”Minimaxing IMinimaxing IILarger gamesHeuristicsPBVsUsing PBVs (animated)Bringing up valuesAlpha cutoffsAlpha cutoffs, in more detailBeta cutoffsUsing beta cutoffsThe importance of cutoffsHeuristic alpha-beta searchingBest game playing strategiesThe EndAlpha-Beta Search2Two-player gamesThe object of a search is to find a path from the starting position to a goal positionIn a puzzle-type problem, you (the searcher) get to choose every moveIn a two-player competitive game, you alternate moves with the other playerThe other player doesn’t want to reach your goalYour search technique must be very different3PayoffsEach game outcome has a payoff, which we can represent as a numberBy convention, we prefer positive numbersIn 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)4Zero-sum gamesMost common games are zero-sum: What I win ($12), plus what you win (-$12), equals zeroNot all games are zero-sum gamesFor simplicity, we consider only zero-sum gamesFrom our point of view, positive numbers are good, negative numbers are badFrom our opponents point of view, positive numbers are bad, negative numbers are good5A trivial “game”Wouldn’t you like to win 50?Do you think you will?Where should you move?Opponent’s move7 3 -8 50Your move6Minimaxing I• 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 your expected win is 3 (unless your opponent plays badly)Opponent’s move7 3 -8 50Your move33 -87Minimaxing IIYour opponent always brings up the minimum number she canYou always choose the maximum of these minimaHence, your technique is called minimaxingOpponent’s move7 3 -8 503 -83Your move8Larger gamesIn the preceding game,You and your opponent each got a single moveYou both had full knowledge of the payoffsIn tic-tac-toe (naughts and crosses), there are up to nine choices, with up to nine movesThis is still easy to solve completelyIn chess or checkers, there are many possible choices, and each player makes multiple movesThese games can never be solved completely with an exhaustive search, no matter how fast computers get9HeuristicsIn a large game, you don’t really know the payoffs at the internal nodes (only at the leaves)A heuristic function computes, for a given node, your best guess as to what the payoff will beThe heuristic function uses whatever knowledge you can build into the programWe make two key assumptions:Your opponent uses the same heuristic function as you doThe more moves ahead you look, the better your heuristic function will work10PBVsA PBV is a preliminary backed-up valueExplore down to a given level using depth-first searchAs you reach each lowest-level node, evaluate it using your heuristic functionBack up values to the next higher node, according to the following (minimaxing) rules:If it’s your move, bring up the largest value, possibly replacing a smaller valueIf it’s your opponent’s move, bring up the smallest value, possible replacing a larger value11Using 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.12Bringing up valuesIf it’s your move, and the next child of this node has a larger value than this node, replace this valueIf it’s your opponent’s move, and the next child of this node has a smaller value than this node, replace this valueAt your move, never reduce a valueAt your opponent’s move, never increase a value13Alpha cutoffsThe 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 8You can ignore the remaining nodes8 5 2 9 -3 18 9 1881YourmoveYourmoveOpponentsmovealphacutoff14Alpha cutoffs, in more detailYou have an alpha cutoff when:You are examining a node at which it is your opponent’s move, andYou have a PBV for the node’s parent, andYou have brought up a PBV that is less than the PBV of the node’s parent, andThe node has other children (which we can now “prune”)8 5 2 9 -3 18 9 1881YourmoveYourmoveOpponentsmovealphacutoffnode being examinedparent (has PBV of 8)15Beta cutoffsAn alpha cutoff occurs whereIt is your opponent’s turn to moveYou have computed a PBV for this node’s parentThe node’s parent has a higher PBV than this nodeThis node has other children you haven’t yet consideredA beta cutoff occurs whereIt is your turn to moveYou have computed a PBV for this node’s parentThe node’s parent has a lower PBV than this nodeThis node has other children you haven’t yet considered16Using beta cutoffsBeta cutoffs are harder to understand, because you have to see things from your opponent’s point of viewYour opponent’s alpha cutoff is your beta cutoffWe assume your opponent is rational, and is using a heuristic function similar to yoursEven if this assumption is incorrect, it’s still the best we can do17The importance of cutoffsIf you can search to the end of the game, you know exactly how to playThe further ahead you can search, the betterIf you can prune (ignore) large parts of the tree, you can search deeper on the other partsSince the number of nodes at each level grows exponentially, the higher you can prune, the betterYou can save exponential time18Heuristic alpha-beta searchingThe 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 levelExplore the “best” moves first“Best” means best for the player whose move it is at that node19Best game playing strategiesFor any game much more
View Full Document
Unlocking...