Transcript States
State-Space Searches The states of Pac-Man The ghosts in Pac-Man Other uses of states The Pac-Man game as a whole can be described by a state machine States are: Title screen, instructions screen, various game levels, high scores screen Designing "by states" is a useful techinque for all kinds of programs, not just games State-space searches Many problems in Artificial Intelligence can be describes as a search through a space of states There is a start state and one or more goal states; the object is to navigate a path from the start state to some goal state If you have an opponent, this isn't just a matter of finding a path Rules control the transition from one state to the next Tic-Tac-Toe (Naughts and Crosses) Basic searches There are two fundamental kinds of search: Breadth-first search Depth-first search There are many variations on search methods The most important in AI is the A* search When alternating moves with an opponent, a different kind of search is needed The most important kind is the alpha-beta search Breadth-first search Depth-first search The basic search algorithm Initialize: put the start node into OPEN while OPEN is not empty take a node N from OPEN if N is a goal node, report success put the children of N onto OPEN Report failure If OPEN is a stack, this is a depth-first search If OPEN is a queue, this is a breadth-first search OPEN may be a fancier structure Breadth-first searching queue: 1 2, 3, 4 3, 4, 5, 6, 7, ... Put 1 on queue Take 1 off queue; not a goal Put 2, 3, 4 on queue Take 2 off queue; not a goal Put 5, 6, 7 on queue Take 3 off queue... search order: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 Depth-first searching stack: 1 4, 3, 2 13, 12, 11, 3, 2, ... Put 1 on stack Take 1 off stack; not a goal Put 2, 3, 4 on stack Take 4 off stack; not a goal Put 11, 12, 13 on stack Take 13 off stack... search order: 1, 4, 13, 12, 11, 3, 10, 9, 8, 2, 7, 6, 5 Depth-first searches and stacks A breadth-first search uses a queue; a depth-first search uses a stack Recursive routines automatically use a stack It is possible (and easy) to write a depth-first search using the automatic stack If you do a breadth-first search, you have to implement the queue yourself Recursive depth-first search boolean search (node N) if N is a goal node, return true for each child C of N if search(C) succeeds, return true return false Advantages/disadvantages If a breadth-first search succeeds, it finds the nearest possible goal If a depth-first search succeeds, it may find an arbitrarily bad path to a goal A depth-first search requires an amount of memory that is linear in the search depth A breadth-first search requires an amount of memory that is exponential in the search depth Best-first searches Initialize: put the start node into OPEN while OPEN is not empty take a node N from OPEN if N is a goal node, report success put the children of N onto OPEN Report failure If OPEN is neither a stack nor a queue, but is sorted according to most promising, we have a best-first search Heuristic searches How do we know which nodes are most promising? Answer 1: it depends on the problem Answer 2: we don't; we have to guess A heuristic is a "rule of thumb" It uses incomplete information to evaluate our possible choices Algorithms guarantee a solution; heuristics don't It's (almost) always better to have an algorithm The A* search The A* search combines the advantages of breadth-first search (good solutions) with the advantages of depth-first search (low memory requirements) A* is a kind of heuristic search We won't get to it today The End