Time reduction adding a/b to mini/max?
Moderators: hgm, Rebel, chrisw
-
- Posts: 3196
- Joined: Fri May 26, 2006 3: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?
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
- Posts: 182
- Joined: Sun Jun 12, 2016 5:44 pm
- Location: London
- Full name: Vincent
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.
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.
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.
-
- Posts: 3196
- Joined: Fri May 26, 2006 3:00 am
- Location: WY, USA
- Full name: Michael Sherwin
Re: Time reduction adding a/b to mini/max?
Thanks!
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
- Posts: 1871
- Joined: Sat Nov 25, 2017 2:28 pm
- Location: France
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.
-
- Posts: 3196
- Joined: Fri May 26, 2006 3: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!
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
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 3: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 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: 558
- Joined: Sat Mar 25, 2006 8: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 11: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 3: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 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: 1563
- Joined: Thu Jul 16, 2009 10: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 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.
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.
-
- Posts: 1971
- Joined: Wed Jul 13, 2011 9:04 pm
- Location: Madrid, Spain.
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 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.
------------------------
------------------------
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: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.
------------------------
According to CPW article about Alpha-Beta: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 well-written 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 well-written program can have a node count close to the square-root of x.
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.
------------------------
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: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 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
------------------------
Am I right in any of my claims?
Regards from Spain.
Ajedrecista.
-
- Posts: 211
- Joined: Sun Jan 18, 2009 11:27 pm
- Location: Sweden
- Full name: Patrik Karlsson
Re: Time reduction adding a/b to mini/max?
That's with perfect move ordering, IIRC.Robert Pope wrote: ↑Mon May 06, 2019 6: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.