Author: Dann Corbit
Date: 21:23:59 07/13/02
Go up one level in this thread
On July 13, 2002 at 05:03:33, Uri Blass wrote:
>On July 13, 2002 at 04:37:31, Dann Corbit wrote:
>
>>On July 13, 2002 at 04:02:49, Uri Blass wrote:
>>
>>>On July 13, 2002 at 03:39:06, Dann Corbit wrote:
>>>
>>>>On July 13, 2002 at 03:36:54, Uri Blass wrote:
>>>>
>>>>>On July 13, 2002 at 01:38:49, Russell Reagan wrote:
>>>>>
>>>>>>I have a question about alpha-beta. My understanding is that with perfect move
>>>>>>ordering, you can get your branching factor down to the square root of the
>>>>>>min-max branching factor. I did a few walk throughs of small trees using
>>>>>>alpha-beta because I wanted to "see" what the tree looked like (where cutoffs
>>>>>>occured), and I don't find this to be the case. I did a simple ternary tree walk
>>>>>>through, and these are my numbers:
>>>>>>
>>>>>>Depth=1 : 4 nodes
>>>>>>Depth=2 : 9 nodes
>>>>>>Depth=3 : 49 nodes
>>>>>>Depth=4 : 132 nodes
>>>>>>
>>>>>>Using a min-max search the branching factor should be 3. The branching factor
>>>>>>for each of these depths was 2.22, 2.45, and 2.69 (which looks to be approaching
>>>>>>3 with added depth). The square root of 3 is 1.73, so am I misinterpreting what
>>>>>>I heard about the branching factor and alpha-beta?
>>>>>>
>>>>>>In other words...If your min-max branching factor is N, then does using
>>>>>>alpha-beta with perfect move ordering give you the square root of N as the
>>>>>>branching factor, or is that the lowest possible limit of the branching factor?
>>>>>>
>>>>>>If I understand this all correctly, that means that in chess a branching factor
>>>>>>below about 6 is not possible without using forward pruning (using alpha-beta)?
>>>>>
>>>>>You need to assume also that hash tables are not used to prune the tree.
>>>>>
>>>>>I believe that pruning is very important and I exepct 2M nodes per second with
>>>>>recursive null move pruning(R=3) to beat 200M nodes per second with no pruning
>>>>>if you use 120/40 time control.
>>>>>
>>>>>I believe that programs practically can get good branching factor mainly thanks
>>>>>to pruning and not thanks to hash tables(at least I do because I still do not
>>>>>use hash tables to prune the tree).
>>>>
>>>>But you order your moves from the hash table!
>>>>;-)
>>>>
>>>>Which came first, the chicken or the egg?
>>>
>>>This is only better order of moves and we assume perfect order of moves
>>>for calculating the branching factor.
>>
>>I was talking of trying to actually achieve it. Without a hash table, you will
>>have to have some sort of genius evaluation to approach it.
>>
>>>It is clear that hash tables with no pruning means beanching factor of at least
>>>5 in the opening position and 6 in the middle game.
>>
>>I wonder what the best branching factor for a program is.
>>
>>I think Pepito and Chess Tiger are both impressive in that regard.
>
>
>I believe that the latest Movei that is not public has better branching factor
>thanks to doing more pruning.
>I see often branching factor of less than 3.
>
>Branching factor means nothing and the important fact is that the latest movei
>seems to play better at longer time control relative to the public version(I
>hope that the change is real and not only a statistical noise).
Branching factor means nothing if the evaluation is not accurate and the moves
chosen are poor. Branching factor means everything if you pick excellent moves
and still reduce the branching factor. If you have a program with a branching
factor of 1 and it does not make mistakes, then chess will be solved as soon as
you run the program {in one or two seconds, probably}. So I think that
branching factor is rather important.
More than anything else, branching factor is the pure dominator of how deeply
you can search. If everything else is equal and you search more deeply, then
you win.
The only hard part is figuring out what to ignore and what to accept.
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.