Author: Janosch Zwerensky
Date: 09:24:10 08/02/05
Go up one level in this thread
>These techniques each reduce the average number of branches of the game tree by >2 Alpha-Beta with perfect move ordering reduces the number of branches visited during a brute-force search without hashtables to ply n to the square-root of the corresponding number for a simple minimax search of equal depth. However, it certainly does not necessarily lower the number of nodes visited during the search by an equal amount; for an (admittedly trivial) example, in a game of branching factor one, alpha-beta does nothing to reduce the nodecount of the search. Moreover, even with a nontrivial game (i.e. a game with average branching factor much larger than one) I don't see alpha-beta reducing the number of branches visited during an exhaustive game tree search to the square root of the size of the corresponding minimax tree when duplicate branches of the gametree are removed by hashing. A simple game where the effect of hashing on a minimax vs. alpha-beta comparison is quite obvious might for example be a nim-like game with one heap of straws and a limit on the number of straws that each player is allowed to remove on their turn. Alpha-beta with perfect move ordering will in this case dramatically reduce the size of the unhashed game tree, but do very little to decrease the size of the minimax game tree with hashing. Of course, all of this does not logically rule out the possibility that an alpha-beta searcher need only search a game-tree of tractable size to solve chess because it is logically possible that the starting position is a mate in 20 for white, in which case the solver can prune all subtrees of the chess game tree which are worse than mate in 20, immediately removing probably a larger number of positions than would be suggested by computing the number of positions that can happen in a legal game of chess and taking the square root of that number. As for quantum computers, I doubt they will be of much help in solving chess even in the case that practical quantum computers will in fact be built someday. In this respect I am skeptical mostly because I do not see how to go from unordered database searches, at which indeed quantum computers achieve a quadratic increase in performance versus classical machines, to game tree searches, which simply are a different kind of thing. Regards, Janosch
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.