Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Please, say in few words what can reduce the "branching factor".

Author: Dan Newman

Date: 23:50:55 09/20/99

Go up one level in this thread


On September 21, 1999 at 01:31:01, KarinsDad wrote:

>On September 20, 1999 at 23:07:56, Robert Hyatt wrote:
>
>[snip]
>>
>>
>>It also might not be a bug, but might be caused by poor move ordering,
>>as that can blow up the search similar to what you are seeing..
>
>I guess I do not understand how Alpha Beta works. I thought that it was
>approximately the square root of the number of branches without any special move
>ordering at all. If move ordering is applied, it should (theoretically) get
>lower than the square root of the number of branches. Correct?
>


No.  With perfect move ordering you get the square root.  Luckily you can
get pretty close and can get a branching factor of about 6--it does depend
on position of course.  With the absolute worst move ordering you get
the full tree.  With random move ordering you get something in between.
IIRC, before applying any move ordering to one of my earlier programs I
got a BF of about 10 or so.  Adding null move takes you from a BF of about
6 down to about 3.

-Dan.

>If so (and since I am not using Alpha Beta, I remember next to no details on how
>it works, so I could be way off here), then if you just used Alpha Beta and move
>ordering and you consistently got a good deal higher than the square root of the
>number of branches, then it would seem that you have a bug (either
>implementation or design) in either your Alpha Beta code, or your Move Ordering
>code. Or am I all wet here?
>
>KarinsDad :)



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.