CS61B Lecture #34Searching by ``Generate and Test''Backtracking SearchGeneral Recursive AlgorithmAnother Kind of Search: Best MoveGame Trees, MinimaxAlpha-Beta PruningCutting off the SearchSome Pseudocode for SearchingStatic EvaluationCoroutines (redone from Lecture #32, slide 10)CS61B Lecture #34Today: Backtracking searches, game trees.Coming Up: Graph Structures:DSIJ,Chapter 12Public Service Announcement: The Student Advocate’s Office is ef-fectively a campus public defender—an executive, non-partis an officeof the student government offering representation, help, and advice toany stude nt or student group i nvolved in a dispute with the Universi ty.For assistance with residency applications and appeals, financial aid ap-plications, withdrawals and enrollment, grade appeals, cheatin g accusa-tions, sexual assault, discrimination, and other University grievances,see their web page at advocate.berkeley.edu.Last modified: Fri Apr 14 16:35:19 2006 CS61B: Lecture #34 1Searching by “Generate and Test”• We’ve been considering the problem of searching a set of data storedin some kind of data structure: “Is x ∈ S?”• But suppose wedon’thave a set S, but know how to recognize whatwe’re after if we find it: “Is there an x such that P (x)?”• If we know how to enumerate all p os sible candidates, can use a p-proach ofGenerate and Test:test all possibilities in turn.• Can sometimes be more clever: avoid tr ying things that won’t work,for example.• What happens if the set of possible candidates is infinite?Last modified: Fri Apr 14 16:35:19 2006 CS61B: Lecture #34 2Backtracking Search• Backtracking search is one way to enumerate all possibilities.• Example:Knight’s Tour.Find all paths a knight can travel on a chess-board such that it touches every square exactly once an d ends upone knight move from where it started.• In the example below, the numbers indicate position numbers (kni g htstarts at 0).• Here, knight (N) is stuck; how to handle this?654 710 28 3 0N 9 1Last modified: Fri Apr 14 16:35:19 2006 CS61B: Lecture #34 3General Recursive Algorithm/** Append to PATH a sequence of knight moves starting at ROW, COL* that avoid s all squares that have been hit already and* that ends up one square away from ENDROW, ENDCOL. B[i][j] is* true iff row i and column j have been hit on PATH so far.* Returns true if it succeed s , else false (with no change to L).* Call initi a l l y with PATH containing the starting square, and* the starti n g square (only) marked in B. */boolean findPath (boolean[][] b, int row, int col,int endRow, int endCol, List path) {if (L.size () == 64) return isKnightMove (row, col, endRow, endCol);for (r, c =all possible moves from(row, col)) {if (! b[r][c]) {b[r][c] = true; // Mark the squarepath.add (new Move (r, c));if (findPa t h (b, r, c, endRow, endCol, path)) return true;b[r][c] = false; // Backtr a c k out of the move.path.remove (path.size ()-1);}}return false;}Last modified: Fri Apr 14 16:35:19 2006 CS61B: Lecture #34 4Another Kind of Search: B est Move• Consider the problem of finding thebestmove in a two-person game.• One way: assign a value to each possible move and pick highest.– Example: number of our pieces - number of opponent’s pieces.• But this is misleadi ng. A move might give us more piece s, but set upa devastating response from the opponent.• So, for each move, look atopponent’spossible moves, assume hepicks the best one for him, and use that as the value.• But what ifyouhave a great response to his response?• How do we organize this sensibly?Last modified: Fri Apr 14 16:35:19 2006 CS61B: Lecture #34 5Game Trees, Minimax• Think of the space of possible continuations of the game as a tree.• Each node is a position, each edge a move.-5-5 -20-5 15 -20 10-30 -5 5 15 -20 -30 9 10*** * * **My moveOpponent’s moveMy moveOpponent’s move• Numbers are the values we guess for the p ositions (larger meansbetter for me). Starred nodes would be chosen.• I always choose child (next position) with maximum value; opponentchooses minimum value (“Minimax algorithm”)Last modified: Fri Apr 14 16:35:19 2006 CS61B: Lecture #34 6Alpha-Beta Pruning• We canprunethis tree as we search it.-5-5≤-20-5 ≥5-20-30 -5 5-20 -30*****My moveOpponent’s moveMy moveOpponent’s move• At the ‘≥ 5’ position, I know that the oppone nt wi l l not choose tomove here (since he already has a −5 move).• At the ‘≤ −20’ position, my opponent knows that I will never chooseto move here (since I already have a −5 move).Last modified: Fri Apr 14 16:35:19 2006 CS61B: Lecture #34 7Cutting off the Search• If you could traverse game tree to the bottom, you’d be able toforce a win (if it’s possible).• Sometimes possible near the end of a game.• Unfortunately, game trees tend to be either infinite or i mpossiblylarge.• So, we choose a maximumdepth,and use a heur istic value computedon the pos i ti on alone (cal l ed astatic valuation) as the value at thatdepth.• Or we might useiterative deepening(kind of breadth-first search),and repeat the search at increasing depths until time is up.• Much more sophisticated searches are possible, however (take CS188).Last modified: Fri Apr 14 16:35:19 2006 CS61B: Lecture #34 8Some Pseudocode for Searching/** A legal move for WHO that either has an estimated value >= CUTOFF* or that has the best estimated value for player WHO, start i ng from* position START, and looking up to DEPTH moves ahead. */Move findBestMov e (Player who, Positio n start, int depth, double cutoff){if (startis a wo n position forwho) return CANT_MOVE;else if (startis a lost position forwho) return C A N T _ MOVE;else if (depth == 0) return guessBestMove (who, start, cutoff);Move bestSoFar = REALLY_BAD_MOVE;for (each legal move,M,forwhofrom positionstart) {Position next = start.makeMove (M);Move response = findBestMove (who.opponent () , next,depth-1, -bestSoFar.value ());if (-respo n s e .value () > bestSoFar.value ()) {SetM’s value to-response.value (); //Value for who = - Value for opponentbestSoFar = M;if (M.value () >= cutoff) break;}}return bestSoFar;}Last modified: Fri Apr 14 16:35:19 2006 CS61B: Lecture #34 9Static Evaluation• This leaves static evaluation, which looks just at the next possiblemove:Move guessBestMo v e (Player who, Position start, double cutoff){Move bestSoFar;bestSoFar = Move.REALLY_BAD_MOVE;for (each legal move,M,forwhofrom positionstart) {Position
View Full Document
Unlocking...