The Power of Recursion: Brute forceBacktracking, Search, HeuristicsBacktracking with BoggleClassic problem: N queensBacktracking idea with N queensBasic ideas in backtracking searchComputer v. Human in GamesBacktracking, minimax, game searchMinimax for tic-tac-toeRecasting the problemLoop InvariantsBean Can gameBean Can AlgorithmBean Can AnalysisThe Game of NimNim AnalysisNim AlgorithmNumbers from EndsPatternsWhat is a pattern?Patterns are discovered, not inventedProgramming ProblemsRemoving DuplicatesOne loop for linear structuresCoding PatternCompSci 100e7.1The Power of Recursion: Brute forceConsider the TypingJob APT problemn: What is minimum number of minutes needed to type n term papers given page counts and three typists typing one page/minute? (assign papers to typists to minimize minutes to completion)Example: {3, 3, 3 ,5 ,9 ,10 ,10} as page countsHow can we solve this in general? Suppose we're told that there are no more than 10 papers on a given day.How does this constraint help us?What is complexity of using brute-force?CompSci 100e7.2Backtracking, Search, HeuristicsMany problems require an approach similar to solving a mazeCertain mazes can be solved using the “right-hand” ruleOther mazes, e.g., with islands, require another approachIf you have “markers”, leave them at intersections, don’t explore the same place twiceWhat happens if you try to search the web, using links on pages to explore other links, using those links to …How many web pages are there?What rules to webcrawlers/webspiders follow? •Who enforces the rules?Keep track of where you’ve been don’t go there againAny problems with this approach?CompSci 100e7.3Backtracking with BoggleBoggletm played on 4x4 boardOther sizes possibleForm words by connecting letters horizontally, vertically, diagonallyCannot re-use letters (normally)Two approachesBuild words from connections, find partial words in dictionaryLook up every word in the dictionary on the boardWhich is better? How is backtracking used?CompSci 100e7.4Classic problem: N queensCan queens be placed on a chess board so that no queens attack each other?Easily place two queensWhat about 8 queens?Make the board NxN, this is the N queens problemPlace one queen/column# different tries/column?BacktrackingUse “current” row in a colIf ok, try next colIf fail, back-up, next rowCompSci 100e7.5Backtracking idea with N queensTry to place a queen in each column in turnTry first row in column C, if ok, move onto next columnIf solved, great, otherwise try next row in column C, place queen, move onto the next column•Must unplace the placed queen to keep goingWhat happens when we start in a column, where to start?If we fail, move back to previous column (which remembers where it is/failed)When starting in a column anew, start at beginning•When backing up, try next location, not beginningBacktracking in general, record an attempt go forwardIf going forward fails, undo the record and backupCompSci 100e7.6Basic ideas in backtracking searchWe need to be able to enumerate all possible choices/movesWe try these choices in order, committing to a choiceIf the choice doesn’t pan out we must undo the choice•This is the backtracking step, choices must be undoableProcess is inherently recursive, so we need to know when the search finishesWhen all columns tried in N queensWhen all board locations tried in boggleWhen every possible moved tried in Tic-tac-toe or chess?•Is there a difference between these games?Summary: enumerate choices, try a choice, undo a choice, this is brute force search: try everythingCompSci 100e7.7Computer v. Human in GamesComputers can explore a large search space of moves quicklyHow many moves possible in chess, for example?Computers cannot explore every move (why) so must use heuristicsRules of thumb about position, strategy, board evaluationTry a move, undo it and try another, track the best moveWhat do humans do well in these games? What about computers?What about at Duke?CompSci 100e7.8Backtracking, minimax, game searchWe’ll use tic-tac-toe to illustrate the idea, but it’s a silly game to show the power of the methodWhat games might be better? Problems?Minimax idea: two players, one maximizes score, the other minimizes score, search complete/partial game tree for best possible moveIn tic-tac-toe we can search until the end-of-the game, but this isn’t possible in general, why not?Use static board evaluation functions instead of searching all the way until the game endsMinimax leads to alpha-beta search, then to other rules and heuristicsCompSci 100e7.9Minimax for tic-tac-toePlayers alternate, one might be computer, one human (or two computer players)Simple rules: win scores +10, loss scores –10, tie is zeroX maximizes, O minimizesAssume opponent plays smartWhat happens otherwise?As game tree is explored is there redundant search?What can we do about this?XOXXOXXOXXXOXOXOXOXOXOXOXXOXOCompSci 100e7.10Recasting the problemInstead of writing this function, write another and call it// @return min minutes to type papers in pagesint bestTime(int[] pages){}What cases do we consider in function below? int best(int[] pages, int index, int t1, int t2, int t3)// returns min minutes to type papers in pages// starting with index-th paper and given// minutes assigned to typists, t1, t2, t3{}return best(pages,0,0,0,0);CompSci 100e7.11Loop InvariantsWant to reason about the correctness of a proposed iterative solutionLoop invariants provide a means to effectively about the correctness of codewhile !done do // what is true at every step // Update/iterate // maintain invariantodCompSci 100e7.12Bean Can gameCan contains N black beans and M white beans initiallyEmptied according the following repeated processSelect two beans from the canIf the beans are:•same color: put a black bean back in the can•different colors: put a white bean back in the canPlayer who chooses the color of the remaining bean wins the gameAnalyze the link between the initial state and the final state Identify a property that is preserved as beans are removed from the canInvariant that characterizes the removal processCompSci 100e7.13Bean Can Algorithmwhile (num-beans-in-can > 1) do pick 2 beans randomly if bean1-color ==
View Full Document
Unlocking...