Adversarial Search

Although adversarial search is again a problem of moving around state space, it will be no surprise that it differs substantially from ``one-sided'' search. You and an adversary take it in turns to move, and your adversary has his own goal states.

Minimax

This basic game-playing search strategy was devised by Claude Shannon (him of the Hartley-Shannon formula) in 1950. It relies on the ability to describe how good overall a particular state is for a particular player. This is called static evaluation. When you run the evaluator, the higher the score the better the state is for you. The search strategy is based on the assumption that you are intent on maximizng your evaluation score, while your adversary is intent on minimizing it. A search for possible states is opened up for a few moves ahead.

Forward vs backward reasoning

Recall that the object of search is to discover a path through a problem's search from initial state to goal state. So far, we have discussed search in terms of forward motion from the start state. But we could just as well have used backwards search, starting at the goal and working back. For that matter, we could do both at the same time.

Which is it better to choose? Three factors might influence the choice of search direction.

  1. Are there more goal or start states? Move from the smaller to the larger.

  2. In which direction is the branching factor smaller? Proceed in the direction with the lower branching factor.

  3. Will the program have to justify its choices to a user? If so, choose the direction of reasoning which more accurately reflects that used in human reasoning.

Bi-directional search

One can search in both directions at the same time. There are obvious advantages, and obvious pitfalls, both based on tunneling analogies.

<<<Previous Next>>>