Posts Tagged ‘AI Search’

PostHeaderIcon Bidirectional Search

Bidirectional Search

Bidirectional Search, as the name implies, searches in two directions at the same time: one forward from the initial state and the other backward from the goal. This is usually done by expanding tree with branching factor b and the distance from start to goal is d. The search stops when searches from both directions meet in the middle. Bidirectional search is a brute-force search algorithm that requires an explicit goal state instead of simply a test for a goal condition. Once the search is over, the path from the initial state is then concatenated with the inverse of the path from the goal state to form the complete solution path.

Bidirectional search still guarantees optimal solutions. Assuring that the comparisons for identifying a common state between the two frontiers can be done in constant time per node by hashing. The time complexity of Bidirectional Search is O(b^d/2) since each search need only proceed to half the solution path. Since at least one of the searches must be breadth-first in order to find a common state, the space complexity of bidirectional search is also O(b^d/2). As a result, it is space bound in practice.

Advantages

  1. The merit of bidirectional search is its speed. Sum of the time taken by two searches (forward and backward) is much less than the O(bd) complexity.
  2. It requires less memory.

Disadvantages

  1. Implementation of bidirectional search algorithm is difficult because additional logic must be included to decide which search tree to extend at each step.
  2. One should have known the goal state in advance.
  3. The algorithm must be too efficient to find the intersection of the two search trees.
  4. It is not always possible to search backward through possible states.

PostHeaderIcon Quiescence

Quiescence Search

The idea of quiescence is that the static evaluator should not be applied to positions whose values are unstable, such as those occurring in the middle of the piece trade. In those positions, a small secondary search is conducted until the static evaluation becomes more stable. In games such as chess or checkers, this can be achieved by always exploring any capture moves one level deeper. This extra search is called quiescence search. Applying quiescence search to capture moves quickly will resolve the uncertainties in the position.

Related Articles

Tansposition Table

Two-Player Games Search