CS 416 Artificial Intelligence Lecture Lecture 77 Informed Informed Searches Searches Chess Match Kasparov Kasparov 1 1 Deep Deep Junior Junior 1 1 Draws Draws 33 Chess Article You You can can buy buy Deep Deep Blue Blue for for 50 50 maybe maybe not not tweaked tweaked to to beat beat Kasparov Kasparov Style Style and and strategy strategy vs vs knowledge knowledge depth depth vs vs breadth breadth 1 000 1 000 top quality top quality games games played played each each week week and and broadcast broadcast on on internet internet Peopl Peoplee don t don t experiment experiment anymore anymore Ka Kasparov sparov pays pays aa team team of of grandmasters grandmasters to to scour scour the the web web daily daily looking looking for for new new opening opening strategies strategies Computers Computers are are opening opening the the game game up up people people are are more more likely likely to to follow follow aa range range of of published published strategies strategies http www nytimes com 2003 02 06 nyregion 06CHES html http www nytimes com 2003 02 06 nyregion 06CHES html Chess Article Have Have we we been been down down this this road road before before The The Road Road to to Wigan Wigan Wier Wier 1900s 1900s George George Orwell Orwell machines machines are are moving moving in in and and polluting polluting the the spiritual spiritual landscape landscape not not on on purpose purpose but but because because they they can t can t help help it it David David Gelernter Gelernter Yale Yale This This is is the the machine machine age age and and no no one one uses uses aa pump pump when when you you can can turn turn on on the the tap tap But But don t don t think think that that won t won t cost cost us us New Horizons Hans Hans Berliner Berliner CMU CMU You You don t don t have have to to be be really really good good anymore anymore to to get get good good results results Chess Chess is is winding winding down down Bobby Bobby Fisher Fisher randomize randomize pieces pieces behind behind row row of of pawns pawns Kasparov Kasparov computer human computer human vs vs computer human computer human Play Play the the Asian Asian game game Go Go no no human human player player would would dare dare depend depend on on computer computer for for advice advice Another article SongPro SongPro The inventor Ronald Jones left with venture capitalist Mark Bush http www nytimes com 2003 02 06 technology circuits 06song html Tough Going Grew Grew up up the the son son of of aa maid maid and and one one of of six six black black students students in in aa high high school school of of 1400 1400 love love of of math math and and engineering engineering dropped dropped out out of of college college learned learned on on the the job job Encountered Encountered resistance resistance when when finding finding funding funding opps opps Who Who does does this this technology technology really really belong belong to to Is Is this this yours yours Tough Going Lucky Lucky to to do do contract contract for for Rainbow Rainbow Coalition Coalition and and met met Jesse Jesse Jackson Jackson who who could could help help out out 33 years years ago ago Ron Ron had had 800 800 left left and and an an idea idea one one lucky lucky break break got got him him aa contact contact and and 11 000 11 000 for for debts debts 22 years years ago ago Ron Ron had had lived lived with with friends friends and and family family and and lived lived off off of of 5 5 aa day day he he knew knew how how to to get get free free food food at at bars bars with with happy happy hours hours Last Last year year the the device device was was released released He He still still lives lives cheaply cheaply Marc Marc Hannah Hannah aa founder founder of of Silicon Silicon Graphics Graphics and and one one of of the the richest richest black black scientists scientists in in Silicon Silicon Valley Valley Subproblems Is Is 4 piece 4 piece subproblem subproblem an an admissible admissible heuristic heuristic itit can can never never overestimate overestimate the the true true cost cost Is Is itit consistent consistent h n h n c n c n a a n n h n h n Genetic Algorithms GAs Another Another randomized randomized search search algorithm algorithm Start Start with with kk initial initial guesses guesses they they form form aa population population each each individual individual from from the the population population is is aa fixed length fixed length string string gene gene each each individual s individual s fitness fitness is is evaluated evaluated successors successors are are generated generated from from individuals individuals according according to to fitness fitness function function results results What s good about evolution Think Think about about mother mother nature nature What s bad about evolution think West Virginia Genetic Algorithms Reproduction Reproduction Reuse Reuse Crossover Crossover Mutation Mutation Crossover Early Early states states are are diverse diverse Crossover Crossover explores explores state state broadly broadly Later Later stages stages are are more more similar similar Crossover Crossover fine fine tunes tunes in in small small region region Like simulated annealing Mutation Could Could screw screw up up aa good good solution solution Like Like metropolis metropolis step step in in simulated simulated annealing annealing Could Could explore explore untapped untapped part part of of search search space space GA Analysis Combines Combines uphill uphill tendency tendency random random exploration exploration exchange exchange information information between between multiple multiple threads threads like like stochastic stochastic beam beam search search Crossover Crossover is is not not needed needed theoretically theoretically ifif starting starting states states are are sufficiently sufficiently random random GA Analysis It s It s all all in in the the representation representation GA GA works works best best ifif representation representation stores stores related related pieces pieces of of the the puzzle puzzle in in neighboring neighboring cells cells of of string string Not Not all all problems problems are are amenable amenable to to crossover crossover TSP TSP Continuous Spaces What What does does continuous continuous mean mean to to you you A A function function is is continuous continuous ifif its its graph graph can can be be drawn drawn without without lifting lifting the the pencil