Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Chess - Programming - Search - About Searching ======

Many Chess programs view a game of chess as a tree.

  * It starts with a root position, which is the position on the board at the time.
  * From this position, the side to move can choose amongst some number of legal moves.
  * Once one of these moves is made, this results in a position that the opponent can consider to be their root position, and they will choose from amongst their legal moves, and so on.
  * This ends up with a large tree.

Ideally the program needs to choose the best move to make.

  * So it has to evaluate the possible moves to determine which of these moves will result in a better score, for the side to move.
  * The program also has to consider what response move the opponent might make, as the opponent is also trying to get their best move, which results in their score increasing the the initial side to move score decreasing.
  * Ideally, the program should work its way through all of the generations of moves, until it finds a checkmate or a draw, then choose the path that will get it to the best possible outcome.

The challenge is this tree of moves grows exponentially bigger at each level:

  * Each position tends to have about 35 possible moves in chess.
  * After 2 moves, one move for the initial side to move, and then another move from the opponent, means that about 1,225 (35 * 35) moves need to be considered.
  * After 3 moves, this becomes 42,875 moves to consider.
  * After 4 moves,         1,500,625.
  * After 5 moves,        52,521,875.
  * After 6 moves,     1,838,265,625.
  * After 7 moves,    64,339,296,875.
  * After 8 moves, 2,251,875,391,000.

So looking just 8 moves ahead means having to analyze over 2 Trillion combinations.

  * Often a Chess game is only allocated a given time frame, and there would be insufficient time to consider all these combinations.
  * Even with an extremely fast computer this will take a **very** long time.
  * As it is not possible to analyze all possible moves in a reasonable time, the Search function should decide to focus on a subset of the many combinations.
    * But the question is, what moves to consider and what moves to ignore?
    * As not all of the combinations can be searched, this means that the Search function may miss out working out the precise best move to make.
    * But the Search function should try to determine a move resulting in as best improvement in score.

There are lots of ways to write a search function with these considerations in mind.

  * Ordering the moves to try to consider the best ones first.
  * Pruning moves from the search that are deemed to most-likely not result in an improvement in score.
  * With optimum ordering and pruning, can result in a reduction in the effective branching factor, from 35 to as low as 6 for chess.
    * Instead of having to analyze 2 Trillion combinations previously determined at level 8, this becomes only 1,679,616 moves.
    * This is assuming the ideal optimization has been made, but in reality the optimization is dependent on many factors so often the branching factor may not be be as low as possible.

----