Unformatted text preview:

Chess Match Kasparov 1 Deep Junior 1 Draws 3 CS 416 Artificial Intelligence Lecture 7 Informed Searches Chess Article Chess Article You can buy Deep Blue for 50 maybe not tweaked to beat Kasparov Style and strategy vs knowledge depth vs breadth Have we been down this road before The Road to Wigan Wier 1900s George Orwell machines are moving in and polluting the spiritual landscape not on purpose but because they can t help it 1 000 top quality games played each week and broadcast on internet People don t experiment anymore Kasparov pays a team of grandmasters to scour the web daily looking for new opening strategies David Gelernter Yale This is the machine age and no one uses a pump when you can turn on the tap But don t think that won t cost us Computers are opening the game up people are more likely to follow a range of published strategies http www nytimes com 2003 02 06 nyregion 06CHES html New Horizons Another article Hans Berliner CMU SongPro You don t have to be really good anymore to get good results Chess is winding down Bobby Fisher randomize pieces behind row of pawns Kasparov The inventor Ronald Jones left with venture capitalist Mark Bush computer human vs computer human Play the Asian game Go no human player would dare depend on computer for advice http www nytimes com 2003 02 06 technology circuits 06song html Page 1 Tough Going Tough Going Lucky to do contract for Rainbow Coalition and met Jesse Jackson who could help out 3 years ago Ron had 800 left and an idea Grew up the son of a maid and one of six black students in a high school of 1400 love of math and engineering dropped out of college learned on the job one lucky break got him a contact and 11 000 for debts 2 years ago Ron had lived with friends and family and lived off of 5 a day he knew how to get free food at bars with happy hours Last year the device was released Encountered resistance when finding funding opps Who does this technology really belong to Is this yours He still lives cheaply Marc Hannah a founder of Silicon Graphics and one of the richest black scientists in Silicon Valley Subproblems Genetic Algorithms GAs Is 4 piece subproblem an admissible heuristic Another randomized search algorithm Start with k initial guesses it can never overestimate the true cost Is it consistent they form a population each individual from the population is a fixed length string gene each individual s fitness is evaluated successors are generated from individuals according to fitness function results h n c n a n h n What s bad about evolution think inbreeding What s good about evolution Think about mother nature Page 2 Genetic Algorithms Crossover Reproduction Early states are diverse Reuse Crossover Crossover explores state broadly Later stages are more similar Mutation Crossover fine tunes in small region Mutation Like simulated annealing GA Analysis Could screw up a good solution Combines Like metropolis step in simulated annealing uphill tendency random exploration exchange information between multiple threads Could explore untapped part of search space like stochastic beam search Crossover is not needed theoretically if starting states are sufficiently random GA Analysis Continuous Spaces What does continuous mean to you A function is continuous if its graph can be drawn without lifting the pencil from the paper Descarte It s all in the representation GA works best if representation stores related pieces of the puzzle in neighboring cells of string Not all problems are amenable to crossover TSP Page 3 In terms of searching Derivative directs future steps Continuous search spaces have neighbors for all states One dimensional function Left or right Two dimensional function That means they have derivatives Direction in 3 space N dimensional function Gradient Can the derivative help out here f An Example f f f x1 x2 xn Airport Example Simulated Annealing Place three airports Trial and error experimentation with six values minimize sum of squared distances from each city to closest airport f x find x1 y1 x2 y2 x3 y3 Genetic Algorithms Create a gene with six values and crossover mutate Discretize some slight change in position each of six parameters has three values same branching factor of 18 A search Airport Example Computing the Gradient Difficult to solve in closed form Derivatives compute f x y that works for all x For given f a b c d e f compute gradient We can usually compute locally change in f in response to small change in a then b r r Update the vector x xnew xold f xold Beware of jumping too far if too large Beware of local min compute f x y that works for only x near z We can also compute empirically pick some small offset to add to each element of x and compute difference beween f x and f x each parameter may settle in its own local min Page 4 Derivative 0 at Max Min Newton Raphson Newton Raphson Find the zero of an equation where it crosses x axis set p p0 f p0 f p0 if p is close to p0 then return p else set p0 p and repeat Why set p p0 f p0 f p0 y intercept equation of line y mx b let y intercept b f p0 let slope m f p0 we want to find x value where y value 0 let y 0 0 f p0 x f p0 Draw picture But we re not finding Zero of f x solve for x f p0 f p0 Hessian We re finding zero of gradient x Second derivative of a multivariable function So replace f x with gradient of x replace f x with second derivative of x 2f 2 x1 2 f x x 22 1 f x x 3 1 Hf x Hessian Hessian 2f x1 x2 2f x2 2 2f x3 x2 2f x1 x3 2 f x2 x3 2f x3 2 Newton Raphson Final Equation r r r 1 r x x H f x f x Online Searches Page 5 Online Searches Online Searches States and Actions are unknown apriori before Difficult to skip around when using A Potential of irreversible dead end with depth first search Local search is perfect for online searches A real robot finding its way through a maze State is difficult to change A real robot cannot jump across state space at will to explore best potential paths stop when you cannot improve any further chances are high of stopping at local solution add memory to permit continued exploration with ability to return to best solution the Brady Bunch again State is difficult impossible to reverse Can you ride your bike backwards Do you have space to turn around When spelunking do you send the smallest person through the tunnel first Learning in Online Search Online agents must resolve ignorance explore the world build a map mapping of state action to results also called a model relating state action to results


View Full Document
Download Informed Searches
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 Informed Searches 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 Informed Searches 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?