Search Algorithm

Discussion about development of draughts in the time of computer and Internet.
Post Reply
BertTuyt
Posts: 1328
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Tue Mar 21, 2017 19:45

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
Table Scan Deep Search.png (6.49 KiB) Viewed 4943 times
I also made a graph with the results, and an exponential best fit.
Scan Deep Analysis.png
Scan Deep Analysis.png (41.5 KiB) Viewed 4943 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
Posts: 244
Joined: Sun Dec 28, 2003 20:24
Contact:

Re: Search Algorithm

Post by MichelG » Wed Mar 22, 2017 12:53

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
Posts: 1328
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Wed Mar 22, 2017 19:43

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
Posts: 317
Joined: Wed May 04, 2016 11:45
Real name: Joost Buijs

Re: Search Algorithm

Post by Joost Buijs » Thu Mar 23, 2017 07:58

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
Posts: 1328
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Sat Mar 25, 2017 09:21

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 :D )

Bert

BertTuyt
Posts: 1328
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Sun Mar 26, 2017 22:44

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
Table Scan Deep Search 3.png (6.67 KiB) Viewed 4721 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
Scan Deep Analysis 2.png (39.99 KiB) Viewed 4721 times
Bert

MichelG
Posts: 244
Joined: Sun Dec 28, 2003 20:24
Contact:

Re: Search Algorithm

Post by MichelG » Mon Mar 27, 2017 13:02

BertTuyt wrote: 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
Posts: 1635
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Search Algorithm

Post by Rein Halbersma » Mon Mar 27, 2017 13:40

MichelG wrote:
BertTuyt wrote: 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
Posts: 1328
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Mon Mar 27, 2017 19:26

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 :D

Bert

BertTuyt
Posts: 1328
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Mon Mar 27, 2017 19:34

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
Scan Deep Analysis 3.png (41.04 KiB) Viewed 4651 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
Posts: 1328
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Tue Mar 28, 2017 20:24

The last match has finished.
See below results.
Table Scan Deep Search 4.png
Table Scan Deep Search 4.png (7.72 KiB) Viewed 4570 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
Scan Deep Analysis 4.png (41.34 KiB) Viewed 4570 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
Posts: 285
Joined: Tue Jul 07, 2015 07:48
Real name: Fabien Letouzey

Re: Search Algorithm

Post by Fabien Letouzey » Wed Mar 29, 2017 06:45

Hi Bert,
BertTuyt wrote: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
Posts: 1328
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Wed Mar 29, 2017 11:09

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
Posts: 285
Joined: Tue Jul 07, 2015 07:48
Real name: Fabien Letouzey

Re: Search Algorithm

Post by Fabien Letouzey » Wed Mar 29, 2017 12:18

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
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
Posts: 1328
Joined: Wed Sep 01, 2004 19:42

Re: Search Algorithm

Post by BertTuyt » Wed Mar 29, 2017 20:02

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

Post Reply