Author: chandler yergin
Date: 09:04:52 05/20/05
Go up one level in this thread
Lets put things in perspective here. A player is faced with an average of only about 35 legal moves to consider with each turn. Each move and its response is called a ply. The fastest chess programs like Fritz, & Shredder look ahead seven or eight plies into the game at 100Kn's per second, with interesting variations being searched to perhaps depth of 40 - 50 Ply. The result is a densely proliferating tree of possibilities with the branches and twigs representing all the different ways the game could unfold. Looking ahead just seven plies (14 individual chess moves) requires examining 35 to the 14th power (more than a billion trillion) leaves representing all the various outcomes. As the computer tries to look deeper, the number of possibilities explodes. Programmers have learned clever ways to "prune" the trees, so that all but a fraction of the paths can be discarded without plumbing them all the way to the bottom. Even so, a chess-playing computer looking ahead seven plies might consider as many as 50 or 60 billion scenarios with each iteration. Now consider a previous Post by Bruce, which confirms the above. Posted by Bruce Moreland (Profile) on April 11, 2005 at 20:12:00: In Reply to: Re: Chess It is already "solved" posted by chandler yergin on April 10, 2005 at 21:33:19: To min-max chess using alpha-beta would require a horrific tree search. Assuming the branching factor would be about six, and stipulating that the game can be solved in 40 moves (80 plies), which is clearly a horrific under-estimate, the game tree size is on the order of 10^62. Even at a billion billion nodes per second, you could search for a billion billion seconds, and you'd only be a billion billionth of the way to being a billionth of the way done. bruce
This page took 0.01 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.