Time reduction adding a/b to mini/max?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Michael Sherwin
Posts: 3015
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Time reduction adding a/b to mini/max?

Post by Michael Sherwin » Sun May 05, 2019 1:32 pm

In a material only mini/max search (in debug mode) it takes 30 seconds to complete a 6 ply search. Adding a/b with zero move ordering reduced the time to 14.5 seconds. Does that sound about right?
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

konsolas
Posts: 151
Joined: Sun Jun 12, 2016 3:44 pm
Location: London
Full name: Vincent
Contact:

Re: Time reduction adding a/b to mini/max?

Post by konsolas » Sun May 05, 2019 1:50 pm

With a mean branching factor of 30, minimax should take about 30^6 = 729 million nodes to search to depth 6.

alpha-beta search with random ordering should take around ((30 - 1 + sqrt(30^2+14*30+1)/4)^6) = 305 million nodes.

The expected time taken for alpha-beta given your minimax time of 30 seconds would therefore be (305/729) * 30 = 12.6 seconds.

So your observed time of 14.5 seconds is about right.

Michael Sherwin
Posts: 3015
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Time reduction adding a/b to mini/max?

Post by Michael Sherwin » Sun May 05, 2019 1:56 pm

8-) Thanks!
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

User avatar
xr_a_y
Posts: 454
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: Time reduction adding a/b to mini/max?

Post by xr_a_y » Sun May 05, 2019 5:31 pm

It also says you are crunching around 10/20Mnps ? Of course it will decrease with pruning but seems to be a good perf anyway.

Michael Sherwin
Posts: 3015
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Time reduction adding a/b to mini/max?

Post by Michael Sherwin » Sun May 05, 2019 8:41 pm

xr_a_y wrote:
Sun May 05, 2019 5:31 pm
It also says you are crunching around 10/20Mnps ? Of course it will decrease with pruning but seems to be a good perf anyway.
It is hard to gauge because that is the speed in debug mode with plenty of asserts being tested. This is for the initial position so it searches 125,057,847 pseudo legal moves. Therefore there are a small amount of illegal positions in that number. It is not set up yet to run outside the debugger so I fugged a few things so it could. The x64 release build finished in right about 3 seconds (no time code yet, stopwatch, lol). I am very pleased with that! :D
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

Sven
Posts: 3762
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Time reduction adding a/b to mini/max?

Post by Sven » Sun May 05, 2019 9:07 pm

konsolas wrote:
Sun May 05, 2019 1:50 pm
With a mean branching factor of 30, minimax should take about 30^6 = 729 million nodes to search to depth 6.

alpha-beta search with random ordering should take around ((30 - 1 + sqrt(30^2+14*30+1)/4)^6) = 305 million nodes.

The expected time taken for alpha-beta given your minimax time of 30 seconds would therefore be (305/729) * 30 = 12.6 seconds.

So your observed time of 14.5 seconds is about right.
I can't follow your calculation. sqrt(30^2+14*30+1)/4 = sqrt(1321)/4 = 9.086... so your whole expression is certainly greater than 38^6 which is a lot more than 30^6. Can you explain where that sqrt(...) expression comes from?

I also do not believe that a depth 6 AB search with random ordering could only be twice as fast as minimax. I would expect that AB with reverse move ordering, i.e. trying the worst move first, then the second worst move etc., has the same effort as minimax. But the effective branching factor with random ordering should be significantly small to get something like 1.5 ^ 6 speedup at least (well, that's just a guess).
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

Robert Pope
Posts: 468
Joined: Sat Mar 25, 2006 7:27 pm

Re: Time reduction adding a/b to mini/max?

Post by Robert Pope » Mon May 06, 2019 4:17 pm

Sven wrote:
Sun May 05, 2019 9:07 pm
konsolas wrote:
Sun May 05, 2019 1:50 pm
With a mean branching factor of 30, minimax should take about 30^6 = 729 million nodes to search to depth 6.

alpha-beta search with random ordering should take around ((30 - 1 + sqrt(30^2+14*30+1)/4)^6) = 305 million nodes.

The expected time taken for alpha-beta given your minimax time of 30 seconds would therefore be (305/729) * 30 = 12.6 seconds.

So your observed time of 14.5 seconds is about right.
I can't follow your calculation. sqrt(30^2+14*30+1)/4 = sqrt(1321)/4 = 9.086... so your whole expression is certainly greater than 38^6 which is a lot more than 30^6. Can you explain where that sqrt(...) expression comes from?

I also do not believe that a depth 6 AB search with random ordering could only be twice as fast as minimax. I would expect that AB with reverse move ordering, i.e. trying the worst move first, then the second worst move etc., has the same effort as minimax. But the effective branching factor with random ordering should be significantly small to get something like 1.5 ^ 6 speedup at least (well, that's just a guess).
Isn't the average branching factor for AB with random sorting = sqrt(N) (ignoring odd/even effects). So AB at 6 ply would be somewhere on the order of 6^6 ~ 50K nodes.

Joost Buijs
Posts: 822
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Time reduction adding a/b to mini/max?

Post by Joost Buijs » Mon May 06, 2019 5:38 pm

In the past a friend of mine made a small test searcher with a random evaluation function.
Assuming a branching factor of 30 and a depth of 6 ply mini-max gives 30^6 (729 million nodes).
With a-b enabled (without any sorting) it gives node counts between 500K and 1.5M (this probably depends upon the random function).
It uses the random function from Turbo Pascal, I guess it is not very sophisticated.
I don't know whether the program is correct or not (then I have to look at the Pascal source, but I assume it is correct).
So I would expect at least a 400 fold speed-up at depth 6 with a-b enabled.

Another way to look at it is that with a-b the average branching factor goes down from 30 to 15, even then you would expect a speedup of at least 60.

User avatar
Ajedrecista
Posts: 1376
Joined: Wed Jul 13, 2011 7:04 pm
Location: Madrid, Spain.
Contact:

Re: Time reduction adding a/b to mini/max?

Post by Ajedrecista » Mon May 06, 2019 6:23 pm

Hello:

Not being a programmer, I want to point some things:

------------------------
konsolas wrote:alpha-beta search with random ordering should take around ((30 - 1 + sqrt(30^2+14*30+1)/4)^6) = 305 million nodes.

The expected time taken for alpha-beta given your minimax time of 30 seconds would therefore be (305/729) * 30 = 12.6 seconds.
Already noted by Sven, this expression is greater than 38^6. In fact, the formula gives around 3.0522e+9 = 3052.2M and not circa 305M if I am right. So, using 305M in the next formula has not got sense.

------------------------
Robert Pope wrote:Isn't the average branching factor for AB with random sorting = sqrt(N) (ignoring odd/even effects). So AB at 6 ply would be somewhere on the order of 6^6 ~ 50K nodes.
According to CPW article about Alpha-Beta:
CPW wrote:If a standard minimax search tree has x nodes, an alpha beta tree in a well-written program can have a node count close to the square-root of x.
It says so in a well-written programme, which might not be the average case (assuming that CPW is right).

According to the same article (also at Odd-Even Effect and Node Types articles), the best case in this case (b = 30, n = 6) is 2*(30)^3 - 1 = 53,999 nodes, which is no far from 6^6 = 46,656 nodes.

------------------------
Sven wrote:I can't follow your calculation. sqrt(30^2+14*30+1)/4 = sqrt(1321)/4 = 9.086... so your whole expression is certainly greater than 38^6 which is a lot more than 30^6. Can you explain where that sqrt(...) expression comes from?
Last but not least, I found a typo in the order of the brackets in the expression given by user konsolas. A similar expression is found in the Alpha-beta pruning article of Wikipedia. I use {[()]} brackets to increase the readability:
Wikipedia wrote:When nodes are considered in a random order (i.e., the algorithm randomizes), asymptotically, the expected number of nodes evaluated in uniform trees with binary leaf-values is {[b - 1 + sqrt(b² + 14b + 1)]/4}^d. [Note 11].

[Note 11]: Saks, M.; Wigderson, A. (1986). "Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees". 27th Annual Symposium on Foundations of Computer Science. pp. 29–38.
Digital Object Identifier: 10.1109/SFCS.1986.44
https://ieeexplore.ieee.org/document/4568192
In this case (b = 30, d = 6), the expression is equal to {[30 - 1 + sqrt(30² + 14*30 + 1)]/4}^6 = {[29 + sqrt(1321)]/4}^6 ~ (16.3364)^6 ~ 1.9008e+7 ~ 19M.

------------------------

Am I right in any of my claims?

Regards from Spain.

Ajedrecista.

elpapa
Posts: 194
Joined: Sun Jan 18, 2009 10:27 pm
Location: Sweden
Full name: Patrik Karlsson

Re: Time reduction adding a/b to mini/max?

Post by elpapa » Tue May 07, 2019 3:28 pm

Robert Pope wrote:
Mon May 06, 2019 4:17 pm
Isn't the average branching factor for AB with random sorting = sqrt(N) (ignoring odd/even effects). So AB at 6 ply would be somewhere on the order of 6^6 ~ 50K nodes.
That's with perfect move ordering, IIRC.

Post Reply