Time reduction adding a/b to mini/max?
Moderators: hgm, Harvey Williamson, bob
Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.

 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?
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.
Re: Time reduction adding a/b to mini/max?
With a mean branching factor of 30, minimax should take about 30^6 = 729 million nodes to search to depth 6.
alphabeta 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 alphabeta 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.
alphabeta 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 alphabeta 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.
Topple: https://topple.dev/about

 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?
Thanks!
I hate if statements. Pawns demand if statements. Therefore I hate pawns.
Re: Time reduction adding a/b to mini/max?
It also says you are crunching around 10/20Mnps ? Of course it will decrease with pruning but seems to be a good perf anyway.
Vivien Clauzon
Weini
https://github.com/tryingsomestuff/Weini
Minic
https://github.com/tryingsomestuff/Minic
Weini
https://github.com/tryingsomestuff/Weini
Minic
https://github.com/tryingsomestuff/Minic

 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?
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!
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

 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?
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?konsolas wrote: ↑Sun May 05, 2019 1:50 pmWith a mean branching factor of 30, minimax should take about 30^6 = 729 million nodes to search to depth 6.
alphabeta 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 alphabeta 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 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)

 Posts: 468
 Joined: Sat Mar 25, 2006 7:27 pm
Re: Time reduction adding a/b to mini/max?
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.Sven wrote: ↑Sun May 05, 2019 9:07 pmI 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?konsolas wrote: ↑Sun May 05, 2019 1:50 pmWith a mean branching factor of 30, minimax should take about 30^6 = 729 million nodes to search to depth 6.
alphabeta 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 alphabeta 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 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).

 Posts: 822
 Joined: Thu Jul 16, 2009 8:47 am
 Location: Almere, The Netherlands
Re: Time reduction adding a/b to mini/max?
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 minimax gives 30^6 (729 million nodes).
With ab 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 speedup at depth 6 with ab enabled.
Another way to look at it is that with ab the average branching factor goes down from 30 to 15, even then you would expect a speedup of at least 60.
Assuming a branching factor of 30 and a depth of 6 ply minimax gives 30^6 (729 million nodes).
With ab 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 speedup at depth 6 with ab enabled.
Another way to look at it is that with ab the average branching factor goes down from 30 to 15, even then you would expect a speedup of at least 60.
 Ajedrecista
 Posts: 1376
 Joined: Wed Jul 13, 2011 7:04 pm
 Location: Madrid, Spain.
 Contact:
Re: Time reduction adding a/b to mini/max?
Hello:
Not being a programmer, I want to point some things:


According to the same article (also at OddEven 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.


Am I right in any of my claims?
Regards from Spain.
Ajedrecista.
Not being a programmer, I want to point some things:

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.konsolas wrote:alphabeta 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 alphabeta given your minimax time of 30 seconds would therefore be (305/729) * 30 = 12.6 seconds.

According to CPW article about AlphaBeta: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.
It says so in a wellwritten programme, which might not be the average case (assuming that CPW is right).CPW wrote:If a standard minimax search tree has x nodes, an alpha beta tree in a wellwritten program can have a node count close to the squareroot of x.
According to the same article (also at OddEven 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.

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 Alphabeta pruning article of Wikipedia. I use {[()]} brackets to increase the readability: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?
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.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 leafvalues 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

Am I right in any of my claims?
Regards from Spain.
Ajedrecista.
Re: Time reduction adding a/b to mini/max?
That's with perfect move ordering, IIRC.Robert Pope wrote: ↑Mon May 06, 2019 4:17 pmIsn'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.