3

I've read (for example, http://radagast.se/othello/Help/order.html) that searching on the best moves at each level first (which can be found using iterative deepening) makes the search go much faster.

How would one go about searching on the best moves possible without using too much additional memory and cpu time?

weeb
  • 1,939
  • 4
  • 18
  • 29

2 Answers2

2

There are basically two strategies:

  1. Static move ordering
  2. Dynamic move ordering

Dynamic move ordering uses information from previous searches, either because you transpose into the same position again, or you have already reached the position in a previous less thorough search. That is the idea of iterative deepening that you mentioned, which continuously increases the search distance.

Dynamic move ordering is very powerful. There are many ways to do it but the two most common ones are transposition tables and killer moves:

  • Transposition tables cache information about previous searches, especially the best move that was found. When the same position is reached again, you can immediately search the best move from the previous search. Very often, it be confirmed as the best move by the deeper search.

  • Killer moves use a similar approach and have the additional advantage that they can use knowledge from similar but not identical positions. However, the quality of the killer moves for move ordering is generally worse than for moves from the transposition tables. That is why they are generally searched after the transposition move.

But what to do if there are no information from previous searches? Often you have some domain specific knowledge that you can use for static move ordering. For example, in chess there are many rules of thumb. One is that capture moves are more likely to be the best move than non-captures. There are more sophisticated strategies (e.g., static recapture analysis) but you have to be careful as more complicated computations will also slow down the search.

By combining both static and dynamic move ordering, chess engines can often guess the best move in the position with hit rates of more than 90%.

Philipp Claßen
  • 41,306
  • 31
  • 146
  • 239
0

If you know, a priori, how to search on the best moves, you wouldn't need to do the search in the first place. What you can do often requires some expertise in the game you are trying to solve. For instance, in checkers, you might try evaluating all moves that result in a king before moves that don't.

Novak
  • 4,687
  • 2
  • 26
  • 64
  • Ok, well how would you exactly go about "evaluating all moves that result in a king before moves that don't". – weeb Jan 18 '12 at 18:12
  • Well, the full development of the idea I've described is called a board evaluation function, meaning, there is some function (in the mathematical sense as well as the computer sense) that takes a board position as input, and returns a number as the ouptut. Say, a high number for a suspected "good" move, like a king, and a low number for an expected bad move. You might think about evaluating to a depth of n, and using a priority queue or some such similar structure to choose the order of the next level of evaluation. – Novak Jan 18 '12 at 19:37