Author: Dann Corbit
Date: 18:14:21 01/17/06
Go up one level in this thread
On January 17, 2006 at 20:42:25, Joseph Ciarrochi wrote: >thanks for your excellent response Dan. > >Please excuse my simple questions. I get the gist of what you are saying but... > >When you talk about branching factor, do you mean how broadly the program >searches. e.g., does it simultanously search two lines if it has a branching >factor of 2. What does it do with 1.5 branching factor. > >Also, concerning the 64 bit question, i was thinking more of relative boost to >strength. so is it possible for a new search to increase the *difference* >between the 32 two bit and the 64 bit, even if they both have the same new >search. Based on your answer to my first question, it sounds like the answer is >"yes" to this question as well. I think? Chess is an exponential problem. On average, there are about 35 possible moves (according to some estimates). If we use pure brute force, then, each subsequent move will take about 35 times longer to calculate than the previous move. But that would really stink. There is an algorithm called alpha-beta that goes like this: If I make a move, and then I want to examine the alternatives, if I see that I have lost a queen and another move I have already examined only loses a pawn, I do not have to keep searching down this trail. It turns out that this method only searches the square root of as many nodes as a pure brute-force minimax search. So our branching factor (how much time we spend going from one level to the next) goes to about 6 (the square root of 35, approximately). You will have noticed that most chess programs do not take 6 times as long to go from ply k to ply k+1. Other things reduce the branching factor. Null move says that if a move is so bad that it is worse than doing nothing at all, I probably do not have to search it as deeply as the others. Programs that use null move will reduce the branching factor to 3 or 4. There are other things that you can do to reduce the branching factor further and further. The best current programs like Rybka, Shredder, and Fruit will search with a branching factor of about 2. That means that ply k+1 takes about twice as long as ply k did to search. If you can reduce the branching factor to 1, you can search 12000 ply in a fraction of a second. But that would mean that you only examine the best possible move at each ply. So reducing the branching factor is not such an easy trick. We have to be very judicous about what we keep and what we throw away.
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.