Search Algorithm
Re: Search Algorithm
As shared before I'm working on the Tournament implementation of the Damage GUI.
I now have an initial version, which seems to work.
At least during tests I did not encounter any crash so far.
With this setup I played several 2move ballot matches (158 games each) between 2 versions of Scan.
Both were identical, the only difference was the fixed search depth.
Starting with 16 Ply (strongest version), with 1 ply search increment for following matches.
The weaker opponent always had a 4 ply reduced fixed search depth.
In the table below the first results:
W = Win, D = Draw, L = Lost, U = Unknown, E = ELO difference (excluding the unknown results in the count) I also made a graph with the results, and an exponential best fit. It is to early to draw conclusions (statistics might think different), as selfplay extrapolation seems to be tricky.
But at least for the Scan  Scan system, there seems to be a clear indication of diminishing returns, and also there seems to be an ELO limit.
For more insights I need my faster machine (to go deeper) , or a little help from my friends
Bert
I now have an initial version, which seems to work.
At least during tests I did not encounter any crash so far.
With this setup I played several 2move ballot matches (158 games each) between 2 versions of Scan.
Both were identical, the only difference was the fixed search depth.
Starting with 16 Ply (strongest version), with 1 ply search increment for following matches.
The weaker opponent always had a 4 ply reduced fixed search depth.
In the table below the first results:
W = Win, D = Draw, L = Lost, U = Unknown, E = ELO difference (excluding the unknown results in the count) I also made a graph with the results, and an exponential best fit. It is to early to draw conclusions (statistics might think different), as selfplay extrapolation seems to be tricky.
But at least for the Scan  Scan system, there seems to be a clear indication of diminishing returns, and also there seems to be an ELO limit.
For more insights I need my faster machine (to go deeper) , or a little help from my friends
Bert
Re: Search Algorithm
Hi Bert,
How long did it take to produce up til 22 ply? It would be nice to see the datapoints at higher ply as well
I don't think you can conclude there is an exponential fit here. Any other curve would fit as well, even a strait line would fit.
At a later time, i will play dragon against scan at various time settings. I rewrote it's search engine, and it needs to be parallalised first.
Michel
How long did it take to produce up til 22 ply? It would be nice to see the datapoints at higher ply as well
I don't think you can conclude there is an exponential fit here. Any other curve would fit as well, even a strait line would fit.
At a later time, i will play dragon against scan at various time settings. I rewrote it's search engine, and it needs to be parallalised first.
Michel
Re: Search Algorithm
Michel, the 22 Ply took 1 1/2 days on my older computer ( Intel i7 940 at 2.93 Ghz).
I used 4 threads (cores) for the search.
So with the faster machine in Holland ( 8 core at 4 Ghz) I'm certainly able to produce the 23 and 24 Ply results.
Maybe Joost can step in with his 10 core machine.
You are right, any curve would fit, but as I expect diminishing returns when depth grows to larger numbers, I started with an exponential curve.
But basically any curve with asymptotic behavior would work.
Bert
I used 4 threads (cores) for the search.
So with the faster machine in Holland ( 8 core at 4 Ghz) I'm certainly able to produce the 23 and 24 Ply results.
Maybe Joost can step in with his 10 core machine.
You are right, any curve would fit, but as I expect diminishing returns when depth grows to larger numbers, I started with an exponential curve.
But basically any curve with asymptotic behavior would work.
Bert

 Posts: 317
 Joined: Wed May 04, 2016 11:45
 Real name: Joost Buijs
Re: Search Algorithm
Bert,
Right now both my machines (8 and 10 core) are busy producing a huge number of games of considerable depth, if you wish I can run your experiment at a larger depth when this job is finished. As an alternative I am willing to give you a remote login to my 8 core machine (which is on a separate IP) to enable you to do the experiment yourself.
Joost
Right now both my machines (8 and 10 core) are busy producing a huge number of games of considerable depth, if you wish I can run your experiment at a larger depth when this job is finished. As an alternative I am willing to give you a remote login to my 8 core machine (which is on a separate IP) to enable you to do the experiment yourself.
Joost
Re: Search Algorithm
In another post I already pointed out possible strength models for a Draughts program.
All empirical, and not based upon underlying mathematical principles.
However one can always start with a model, and check what can be derived from this.
Than practice will most likely reveal that the assumptions were wrong, so back to the drawing board.
So one can start with the next model: R = RMax * ( 1  f(depth)*g(knowledge) )
RMax and R is rating and maxrating (could be in ELO)
f(depth) is a function which describes the impact of search (depth in ply), and f(0) = 1 and f(infinite) = 0
g(knowledge) is a function which describes the impact of knowledge (difficult to quantify), and g(0) = 1 and g(infinite) = 0
If the Rating function can be split this way remains to be seen, most likely a more complex relation holds.
In any case if depth or knowledge grow to infinite the max rating is reached.
If one studies engines with equal evaluation function, one could also write: R = Rmax * ( 1  g0 * f(depth))
The rating difference between an engine which searches d ply and another engine which searches dx ply can be expressed as:
deltaR = RMax * ( 1  g0 * f(d) )  RMax * ( 1  g0 * f(dx) )
deltaR = RMax * g0 * ( f(dx)  f(d)
As we don't have a model (yet) which yields a function f(d), we could start with just choosing one.
The boundary conditions are: f(0) = 1 f(infinite) = 0.
A candidate could be (but there are zillions): f(d) = exp(d0 * d), with d0 negative.
So:
deltaR = RMax * g0 * ( exp(d0 * (dx))  exp(d0 * d) )
deltaR = RMax * g0 * ( exp(d0 * x) * exp (d0 * d)  exp (d0 * d) )
deltaR = RMax * g0 * ( exp(d0 * x)  1 ) * exp(d0*d)
In a previous experiment with x=4, the next exponential fit was found (preliminary results, as we need more data points in the tail):
deltaR = 2384.7 * exp (0.198 * d)
I will do some tests with x=2, and see what happens (most likely back to the drawing board )
Bert
All empirical, and not based upon underlying mathematical principles.
However one can always start with a model, and check what can be derived from this.
Than practice will most likely reveal that the assumptions were wrong, so back to the drawing board.
So one can start with the next model: R = RMax * ( 1  f(depth)*g(knowledge) )
RMax and R is rating and maxrating (could be in ELO)
f(depth) is a function which describes the impact of search (depth in ply), and f(0) = 1 and f(infinite) = 0
g(knowledge) is a function which describes the impact of knowledge (difficult to quantify), and g(0) = 1 and g(infinite) = 0
If the Rating function can be split this way remains to be seen, most likely a more complex relation holds.
In any case if depth or knowledge grow to infinite the max rating is reached.
If one studies engines with equal evaluation function, one could also write: R = Rmax * ( 1  g0 * f(depth))
The rating difference between an engine which searches d ply and another engine which searches dx ply can be expressed as:
deltaR = RMax * ( 1  g0 * f(d) )  RMax * ( 1  g0 * f(dx) )
deltaR = RMax * g0 * ( f(dx)  f(d)
As we don't have a model (yet) which yields a function f(d), we could start with just choosing one.
The boundary conditions are: f(0) = 1 f(infinite) = 0.
A candidate could be (but there are zillions): f(d) = exp(d0 * d), with d0 negative.
So:
deltaR = RMax * g0 * ( exp(d0 * (dx))  exp(d0 * d) )
deltaR = RMax * g0 * ( exp(d0 * x) * exp (d0 * d)  exp (d0 * d) )
deltaR = RMax * g0 * ( exp(d0 * x)  1 ) * exp(d0*d)
In a previous experiment with x=4, the next exponential fit was found (preliminary results, as we need more data points in the tail):
deltaR = 2384.7 * exp (0.198 * d)
I will do some tests with x=2, and see what happens (most likely back to the drawing board )
Bert
Re: Search Algorithm
Herewith the first results of a test between the Scan and Scan Engine with 2 ply difference in search depth.
See below table: The 22 Ply  20 Ply Match is running.
Here the next result(s) are quite important.
Especially to verify if we really see diminishing returns, or that we see a tail with constant ELO differences. Bert
See below table: The 22 Ply  20 Ply Match is running.
Here the next result(s) are quite important.
Especially to verify if we really see diminishing returns, or that we see a tail with constant ELO differences. Bert
Re: Search Algorithm
Diminishing returns are mathemaically inevatable. Draughts games have a finite length. Even with LMR en propcut, you can prove that infinite search will reach the gametheorical value.BertTuyt wrote: Especially to verify if we really see diminishing returns, or that we see a tail with constant ELO differences.
A game between infinite search against infinite search+x ply will always reach the gametheoretical value. So the graph must go to zero in its limits.
The question is how fast?

 Posts: 1643
 Joined: Wed Apr 14, 2004 16:04
 Contact:
Re: Search Algorithm
If you make a searchknowledge diagram, Bert's experiment is for a fixed level of knowledge. Of course there are diminishing returns for search. But that does not mean that the limit is equal to the ultimate ELO. At some point, it pays to invest more in knowledge and the entire curve in the searchknowledge 2Dplane will be at a higher level.MichelG wrote:Diminishing returns are mathemaically inevatable. Draughts games have a finite length. Even with LMR en propcut, you can prove that infinite search will reach the gametheorical value.BertTuyt wrote: Especially to verify if we really see diminishing returns, or that we see a tail with constant ELO differences.
A game between infinite search against infinite search+x ply will always reach the gametheoretical value. So the graph must go to zero in its limits.
The question is how fast?
Re: Search Algorithm
Rein,
Based upon the(unproven, and most likely wrong) model: R = RMax * ( 1  f(depth)*g(knowledge) )
and the candidate for f(d): f(d) = exp(d0 * d), with d0 negative.
The deltaR between programs with equal evaluation function but different search depth could be expressed as:
deltaR = RMax * g0 * ( exp(d0 * x)  1 ) * exp(d0*d) , which is also deltaR = RMax * f(depth) * g(knowledge) * ( exp(d0 * x)  1 )
so: DeltaR / ( exp(d0 * x)  1 ) = RMax * f(depth) * g(knowledge)
This way we can calculate from the previous results (if the model holds, which is a fairy tale) what the maximum rating gain is (which is RMax * f * g).
For the curve with delta depth = 4, and for depth = 22, this yields 21.5, which is unbelievable small, and nonrealistic.
So most likely the curve grows to zero, but not as fast as the model indicates.
Or with the current evaluation implementation, we already have a nearperfect knowledge, so g(knowledge) close to 0, which I also don't believe.
The only way to find out, is to do test with other evaluation functions...
Never a dull moment
Bert
Based upon the(unproven, and most likely wrong) model: R = RMax * ( 1  f(depth)*g(knowledge) )
and the candidate for f(d): f(d) = exp(d0 * d), with d0 negative.
The deltaR between programs with equal evaluation function but different search depth could be expressed as:
deltaR = RMax * g0 * ( exp(d0 * x)  1 ) * exp(d0*d) , which is also deltaR = RMax * f(depth) * g(knowledge) * ( exp(d0 * x)  1 )
so: DeltaR / ( exp(d0 * x)  1 ) = RMax * f(depth) * g(knowledge)
This way we can calculate from the previous results (if the model holds, which is a fairy tale) what the maximum rating gain is (which is RMax * f * g).
For the curve with delta depth = 4, and for depth = 22, this yields 21.5, which is unbelievable small, and nonrealistic.
So most likely the curve grows to zero, but not as fast as the model indicates.
Or with the current evaluation implementation, we already have a nearperfect knowledge, so g(knowledge) close to 0, which I also don't believe.
The only way to find out, is to do test with other evaluation functions...
Never a dull moment
Bert
Re: Search Algorithm
And after 88 games (so a little more as half way), the next result for the delta depth = 2 match.
W D L U = 3 82 1 2 , which yields an ELO difference of 8.
This results in the next curve:
And with a remarkable exponent of 0.197 compared with the 0.198 for the delta depth = 4 search.
Tomorrow this will be completely different, but for now I can enjoy the moment
Bert
W D L U = 3 82 1 2 , which yields an ELO difference of 8.
This results in the next curve:
And with a remarkable exponent of 0.197 compared with the 0.198 for the delta depth = 4 search.
Tomorrow this will be completely different, but for now I can enjoy the moment
Bert
Re: Search Algorithm
The last match has finished.
See below results. And the graph.
The exponent is slightly different, but (although statistics could fool us) one can clearly recognize diminishing returns. Now I want to study the effect of the evaluation function.
And in a later stage I will add the data points with ply 23 , 24 , and hopefully 25.
Bert
See below results. And the graph.
The exponent is slightly different, but (although statistics could fool us) one can clearly recognize diminishing returns. Now I want to study the effect of the evaluation function.
And in a later stage I will add the data points with ply 23 , 24 , and hopefully 25.
Bert

 Posts: 288
 Joined: Tue Jul 07, 2015 07:48
 Real name: Fabien Letouzey
Re: Search Algorithm
Hi Bert,
Fabien.
Good timing, I'm available now. Earlier you asked for PST weights?BertTuyt wrote:Now I want to study the effect of the evaluation function.
Fabien.
Re: Search Algorithm
Fabien, yes if available.
I want to start with a material only test, and then process with a PST based eval, and also strip parts of the current Scan eval.
Bert
I want to start with a material only test, and then process with a PST based eval, and also strip parts of the current Scan eval.
Bert

 Posts: 288
 Joined: Tue Jul 07, 2015 07:48
 Real name: Fabien Letouzey
Re: Search Algorithm
OK. I don't have a PST handy, but there is code for it. There's no guarantee that it will be stronger than a manuallycrafted one, but it should be a good starting point.BertTuyt wrote:Fabien, yes if available.
I want to start with a material only test, and then process with a PST based eval, and also strip parts of the current Scan eval.
Bert
I can easily relaunch learning for any subset of Scan's features; that's how the development code is organised. Even game phase is considered as a feature. So just say the words. Scan 1.0, whose eval Michel tested, has no balance, 3x6 patterns, or game phase for instance; it's almost only material + 4x4. For additional features, I would need to implement them first.
Re: Search Algorithm
Fabien, it doesnt need to be strong, it only should be different from a performance point of view.
So anything is welcomed which you can share..
Bert
So anything is welcomed which you can share..
Bert