Author: Michael Yee
Date: 08:15:30 10/11/05
Go up one level in this thread
On October 10, 2005 at 23:37:41, chandler yergin wrote: >http://chess.verhelst.org/1997/03/10/search/ > >"Tree search is one of the central algorithms of any game playing program. The >term is based on looking at all possible game positions as a tree, with the >legal game moves forming the branches of this tree. The leaves of the tree are >all final positions, where the outcome of the game is known. The problem for >most interesting games is that the size of this tree is tremendously huge, >something like W^D, where W is the average number of moves per position and D is >the depth of the tree, Searching the whole tree is impossible, mainly due to >lack of time, even on the fastest computers. All practical search algorithms are >approximations of doing such a full tree search." The key sentence in the above is the last observation: "All practical search algorithms are approximations of doing such a full tree search." This means that no programs generate and search all legal moves in every non-leaf node that occurs in the tree. The only exceptions are very simple programs that do strict minimax without even alpha-beta pruning; using this approach will result in very low search depths due to the average branching factor of chess. To complicate matters, consider alpha-beta pruning. With it, you can find the best move (and score) in the root position "as if" you generated all legal moves in all positions in the tree, but *without* necessarily having to generate all legal moves in all positions in the tree. It uses a mathematical property of minimax that allows you to stop searching the child positions of a given position once you can *prove* that searching the rest couldn't possibly change anything (i.e., the best move and score at the root). Now consider what top programs do. On top of alpha-beta (which is totally safe), they add extra non-safe pruning heuristics (e.g., null-move). Here, you might choose not to search some child positions of a given position because you *think* it won't change anything. Most of the time, the programs are correct (that it was safe to prune a branch), but mistakes can happen. The benefit is that you can usually search deeper (since you look at less moves per position) while making occasional errors. So what's the conclusion? Strong programs don't search all legal moves in all positions. It's not just my opinion--it's contained in the information you quoted. Michael
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.