Time reduction adding a/b to mini/max?

[Michael Sherwin]

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?

[konsolas]

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]

Thanks!

[xr_a_y]

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]

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!

[Sven]

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).

[Robert Pope]

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]

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.

[Ajedrecista]

Hello:

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

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

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.

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

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:

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.

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

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:

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]

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.