This article only describes and compares some search algorithms formally. Each single implementation is linked below. Each search algorithm has its own field of application and the performance may vary with the provided input. Let’s take at first a look at the “requirements” of any search request.
Similar to deterministic final state machines, search algorithms require a 5 tuple to operate properly.
[<Initial-State>, <States>, <Transitions>, <Final-State>, <Goal>]
Initial State represents the state the algorithm starts at
States is a collection of all possible (reachable) states
Transitions Each state is reachable by another state and has, therefore, a connection to other states as well.
Final-State A final state won’t be required in some cases. But basically, a final state represents where the sequence of transitions should end
Goal. The “final”/last or search aborting condition
With the provided information above, search algorithms are able to find one or several solutions for any request. Of course, exceptions acknowledge the rules. For example if the final state isn’t connected to any state; or the algorithm searches endlessly within always the same branch, because one or several states are connected in a cycle.
A Blind Search Algorithm has no knowledge about the path, costs or anything else. Just the goal condition is known. Therefore, no optimization or prediction is possible. Only the way of “how” our search within the path is arbitrary.
On the other hand, a Heuristic Search Algorithm has a global or local knowledge base about the path. With the help of the provided extra information, the algorithms are able to “predict” the best way to the target, without searching within other solution paths. With that said, Heuristic Search Algorithms are less time and space consuming, compared to a Blind Search Algorithm, but do require additional information.
Perfect/Imperfect Game Play
Blind and Heuristic Algorithms search for a goal with static defined data. Game Plays may change the requirements and the database every single move. Therefore, Game Play Algorithms “learn” from the provided input, moves and decisions the other Player or AI has done. Thus, some games deliver not only a local knowledge base; e.g Chess, TicTacToe,… have finite possible game states and therefore, at any given point, the result of the game is already known. (Endgame Database) My favourite quote related to AI Game Players: “The winner is, who never starts the game” – War Game
To compare the single algorithms with each other, we need to define several comparable quality aspects.
Time complexity How much time do we need to actually find a solution?
Space complexity How much space (RAM/HDD) is required?
Complete Is finding a solution guaranteed?
Optimal How “good” is the found solution? (Several solution paths could be possible)
- Perfect Game Plays
- Imperfect plays
- Heuristic Evaluation
- LAED Look-AHead: Endgame Database