Author: David Dory
Date: 03:19:53 03/13/03
Go up one level in this thread
On March 13, 2003 at 03:59:13, Steven Chu wrote: >I am doing some research on different search algorithms, in particular: >alpha beta pruning >minimax >minimax with alpha beta cutoff >negamax >negamax with alpha beta cutoff >quiescence search > >I just wanted to know if anyone has any ideas on the comparisons and contrasts >of each of these different algorithmic processes compared with eachother and >humans. Also if anyone knows anywhere where i can obtain such information i >would be most grateful. > >Thank you > >Steven Chu Steven, Just click on Computer Resource Center, and then click on Programming ... There is a great wealth of data, a Google search will be very profitable, as well. Minimax is very useful in two player games of perfect information (ie., all knowledge is available to both players, like chess), but it involves searching thru EVERY leaf of the search tree - much too laborious and time consuming even with fast computers. Alpha-Beta gives the exact same info, while visiting far fewer leaves of the search tree, by pruning off those leaves which can not possibly improve the score for the player. With proper move ordering (best moves first), the savings is very significant. Without good move ordering, the savings can be zip. Quiescence as I use the term is not a search, it is a state of the position on the board, as opposed to dynamic. When quiescence is judged true for a position, an evaluation is done, score returned, and no more searching is made beyond that position, on that branch of the tree. That position is now the search horizon or leaf node, for that branch of the game tree. Naturally, humans play chess very differently than computers. After years of trying to "make the computer play chess like a man", it has been found most effective to let the computer play chess the best way it can - like only a computer would play. Indeed, despite several studies, psychologists are unable to quantify how grandmasters skillfully apply their knowledge to the game. If you have a specific question, please ask away. If you need very broad info on the algorithmic principles used by computers to play chess - please read some of the info on the net. Good luck Dave
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.