AI technology: a lawyer's guide
Search algorithms
Search algorithms retrieve information stored in a particular search space that meets set criteria. They are used in AI to find the path of least resistance from a start state to a defined end state, that path being via certain allowed states only.
This is well illustrated by the use of this AI technique in a board game: the start state is the allowed configuration of pieces on a board, and the end state is a configuration of pieces that is considered victorious under the rules of the game. A search algorithm will map out all possible board states, with each transition between states corresponding to a legal board move, and then find the quickest path from the start state to the end victorious state.
This method is simple in principle, but can soon run into problems: chess has a potential number of board states that is estimated to be around 10120, whereas the number of particles in the observable universe is a comparatively tiny 1080. So it’s well beyond the processing power of computers to evaluate every single board state to find the best path to victory. As a result, search algorithms are used in conjunction with the other AI techniques. This combination of techniques allows the program to take effective shortcuts, like using probability or machine learning to approximate the best move at any time, considering only a limited number of board states ahead.
Games are a good illustration of search algorithms, but this AI technique is also used in more significant real-world cases. A simple example is searching a database – perhaps not something we usually consider to be AI. Search algorithms also underpin more complex programs, like Google Maps.
Author
-
Giles Pratt Partner
London