Search Algorithm

[BertTuyt]

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 2-move 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)

Table Scan Deep Search.png (6.49 KiB) Viewed 14031 times

I also made a graph with the results, and an exponential best fit.

Scan Deep Analysis.png (41.5 KiB) Viewed 14031 times

It is to early to draw conclusions (statistics might think different), as self-play 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

[MichelG]

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

[BertTuyt]

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

[Joost Buijs]

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

[BertTuyt]

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 max-rating (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 d-x ply can be expressed as:

deltaR = RMax * ( 1 - g0 * f(d) ) - RMax * ( 1 - g0 * f(d-x) )
deltaR = RMax * g0 * ( f(d-x) - 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 * (d-x)) - 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

[BertTuyt]

Herewith the first results of a test between the Scan and Scan Engine with 2 ply difference in search depth.
See below table:

Table Scan Deep Search 3.png (6.67 KiB) Viewed 13809 times

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.

Scan Deep Analysis 2.png (39.99 KiB) Viewed 13809 times

Bert

[MichelG]

Especially to verify if we really see diminishing returns, or that we see a tail with constant ELO differences.

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 game-theorical value.

A game between infinite search against infinite search+x ply will always reach the game-theoretical value. So the graph must go to zero in its limits.

The question is how fast?

[Rein Halbersma]

Especially to verify if we really see diminishing returns, or that we see a tail with constant ELO differences.

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 game-theorical value.

A game between infinite search against infinite search+x ply will always reach the game-theoretical value. So the graph must go to zero in its limits.

The question is how fast?

If you make a search-knowledge 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 search-knowledge 2D-plane will be at a higher level.

[BertTuyt]

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 non-realistic.
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 near-perfect 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

[BertTuyt]

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:

Scan Deep Analysis 3.png (41.04 KiB) Viewed 13739 times

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

[BertTuyt]

The last match has finished.
See below results.

Table Scan Deep Search 4.png (7.72 KiB) Viewed 13658 times

And the graph.
The exponent is slightly different, but (although statistics could fool us) one can clearly recognize diminishing returns.

Scan Deep Analysis 4.png (41.34 KiB) Viewed 13658 times

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

[Fabien Letouzey]

Hi Bert,

Now I want to study the effect of the evaluation function.

Good timing, I'm available now. Earlier you asked for PST weights?

Fabien.

[BertTuyt]

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

[Fabien Letouzey]

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

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 manually-crafted one, but it should be a good starting point.

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.

[BertTuyt]

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