What are search problems?
Search problems are problems that start with an initial state and have a set of actions we can take in any given state to get to the solution. For each action we have a transition model, which is a description of what state we would get by taking that action in each state. A goal test that checks if the problem is solved. Finally, a path function will tell us if the solution is optimal, meaning the one with lowest path cost. In some problems we will need to find the optimal solution, however that is not always necessary. Nodes are the data structure used, they keep track of the state, the parent node (node that generated the current one), action (action applied to parent node to get to current node), path cost (cost to get from initial state to this point). The nodes that we can explore but haven’t yet form the frontier.
Types of Search Algorithms
There exist two types of algorithms to solve search problems: uninformed and informed.
Uninformed algorithms consist of search strategies that don’t use problem specific knowledge. They do not know or care about the structure of the problem and just select from the actions available.
Informed algorithms, instead, use problem specific knowledge to find solutions more efficiently (i.e. if the problem is a maze, being closer to the goal is often better than being far away).
Below are illustrated two algorithms for each type.
1. Depth First Search (DFS) – uninformed
Depth-first search always explores the deepest node in the frontier by using the so-called stack method (a stack is a first-in last-out data type). When it hits a dead end which is not the solution, the algorithm will back up and try something different, still going as deep as possible.
This algorithm is particularly useful as it always finds a solution (granted we don’t have an infinite number of states or nodes); however this solution is not necessarily optimal.
Pseudocode:
2. Breadth First Search (BFS) – uninformed
BFS always expands the shallowest node in the frontier. In this algorithm we use a queue instead of a stack (first-in, first-out). It always finds a solution (given that we don’t have infinite number of nodes or states) which is the optimal one.
Pseudocode:
*Note that the only change from dfs is the choice of node to approach (stack vs queue)
3. Greedy Best-First Search (GBFS) – informed
GBFS expands the node that is closest to the goal state, as estimated by a heuristic function. The heuristic function takes a state and returns an estimate of how close that state is to the goal state. It is important to underline that this algorithm does not always find the optimal solution.
4. A* Search – informed
A* search is similar to the GBFS, however in order to always obtain the optimal solution, another function is added. This function returns the cost of reaching each node. In this way the algorithm when choosing the next node will consider both the distance from the goal and the cost to get to it.
Search Algorithms to Win Deterministic Games: Minimax
To conclude this article, we briefly analyze the interesting use of search algorithms in deterministic games with two players playing against each other: the minimax algorithm.
To use this algorithm, we first need to translate the game into a numerical problem: we assign a value for each possible way the game can unfold to. Then we refer to the two players as a “max player”, who aims to maximize its score (utility) and a “min player”, who does the opposite.
In addition to this, the deterministic games must have a specific structure and set of functions:
- S0: initial state;
- Player(s): takes a state s as input and returns which player’s turn it is;
- Action(s): returns all possible actions at state s;
- Result(s): returns the new state after action a was taken in state s;
- Terminal(s): checks if a state s is a terminal state (game ends);
- Utility(s): mentioned above, returns numerical value of a terminal state.
The pseudocode code for the minimax algorithm:
Pseudocode for the function max_value:
*Note that the function min_value is the same, but v is initially positive infinity and then it is equal to the min(v, max_value(result(board,action))).
