Penn CIT 594  Alpha Beta Search (20 pages)
Previewing pages 1, 2, 19, 20 of 20 page document View the full content.Alpha Beta Search
Previewing pages 1, 2, 19, 20 of actual document.
View the full content.View Full Document
Alpha Beta Search
0 0 165 views
 Pages:
 20
 School:
 University of Pennsylvania
 Course:
 Cit 594  Programming Languages and Techniques II.
Programming Languages and Techniques II. Documents

5 pages

19 pages

13 pages

26 pages

17 pages

13 pages

16 pages

13 pages

13 pages

13 pages

20 pages

20 pages

17 pages

29 pages

31 pages

24 pages

11 pages

18 pages

22 pages

17 pages

31 pages

28 pages

21 pages

25 pages

23 pages

23 pages

10 pages

28 pages

13 pages

21 pages

23 pages

29 pages

30 pages

A brief history of XML SOAP and REST
17 pages

11 pages

29 pages

23 pages

30 pages

11 pages

30 pages

13 pages

25 pages

20 pages

22 pages

11 pages

21 pages

14 pages

13 pages

13 pages

24 pages

25 pages

20 pages

24 pages

20 pages

19 pages

29 pages

25 pages

23 pages

12 pages

37 pages

21 pages

28 pages

25 pages

24 pages

24 pages

14 pages

25 pages

12 pages

14 pages

23 pages

30 pages

20 pages

23 pages

25 pages

25 pages

20 pages

10 pages

23 pages

19 pages

25 pages

17 pages

21 pages

19 pages

11 pages

22 pages

13 pages

21 pages

25 pages

15 pages

13 pages

15 pages

15 pages

20 pages

18 pages

24 pages

8 pages

23 pages

29 pages

27 pages

25 pages

32 pages

10 pages

45 pages

25 pages

15 pages

24 pages

19 pages

21 pages

20 pages

18 pages

17 pages

12 pages

25 pages

18 pages

22 pages

23 pages

18 pages

29 pages

Example design of a data structure
20 pages

23 pages

20 pages

19 pages

28 pages

37 pages

20 pages

29 pages

15 pages

12 pages

8 pages

15 pages

15 pages

15 pages

20 pages

11 pages

12 pages

24 pages

15 pages

17 pages

16 pages

19 pages

20 pages

29 pages

8 pages

19 pages

13 pages

17 pages

17 pages

12 pages

18 pages

20 pages

11 pages

18 pages

27 pages

11 pages

24 pages

15 pages

23 pages

21 pages

21 pages

11 pages

12 pages

25 pages

21 pages
Sign up for free to view:
 This document and 3 million+ documents and flashcards
 High quality study guides, lecture notes, practice exams
 Course Packets handpicked by editors offering a comprehensive review of your courses
 Better Grades Guaranteed
Alpha Beta Search Two 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 different 2 Payoffs 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 3 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 good 4 A trivial game Your move Opponent s move 7 3 8 Wouldn t you like to win 50 Do you think you will Where should you move 50 5 Minimaxing I Your opponent will choose smaller numbers If you move left your opponent will choose 3 3 Your move 3 If you move right your opponent will choose 8 8 Opponent s move 7 3 8 50 Therefore your choices are really 3 or 8 You should move left and your expected win is 3 unless your opponent plays badly 6 Minimaxing II 3 Your move 3 8 Opponent s move 7 3 8 50 Your opponent always brings up the minimum number she can You always choose the maximum of these minima Hence your technique is called minimaxing 7 Larger games In the preceding game In tic tac toe naughts and crosses there are up to nine choices with up to nine moves You and your opponent each got a single move You both had full knowledge of the payoffs This is still easy to solve completely In chess or checkers there are many possible choices and each player makes multiple moves These games can never be solved completely with an exhaustive search no matter how fast computers get 8 Heuristics In 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 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 as you do The more moves ahead you look the better your heuristic function will work 9 PBVs 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 minimaxing 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 value 10 Using PBVs animated Do a DFS find an 8 and bring it up Explore 5 smaller than 8 so ignore it Your move Opponents move 8 8 Your move 8 Backtrack bring 8 up another level Explore 2 bring it up Explore 9 better than 2 so bring it up replacing 2 2 9 5 2 9 3 9 is not better than 8 for your opponent so ignore it Explore 3 bring it up Etc 11 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 value 12 Alpha cutoffs 8 Your move Opponents move 8 8 1 9 5 alpha cutoff 8 Your move 2 1 9 3 1 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 nodes 13 Alpha cutoffs in more detail parent has PBV of 8 node being examined 8 Your move Opponents move You have an alpha cutoff when 8 1 alpha cutoff 8 Your move 9 1 8 5 2 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 9 3 1 14 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 considered 15 Using 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 do 16 The 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 time 17 Heuristic 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 node 18 Best 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 For optimum play …
View Full Document