World Draughts Forum

It is currently Wed Sep 20, 2017 21:13

All times are UTC+01:00




Post new topic  Reply to topic  [ 712 posts ]  Go to page Previous 143 44 45 46 47 48 Next
Author Message
 Post subject: Re: Search Algorithm
PostPosted: Tue Mar 21, 2017 19:45 
Offline

Joined: Wed Sep 01, 2004 18:42
Posts: 1292
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)
Attachment:
Table Scan Deep Search.png
Table Scan Deep Search.png [ 6.49 KiB | Viewed 1176 times ]


I also made a graph with the results, and an exponential best fit.
Attachment:
Scan Deep Analysis.png
Scan Deep Analysis.png [ 41.5 KiB | Viewed 1176 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


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Wed Mar 22, 2017 12:53 
Offline

Joined: Sun Dec 28, 2003 20:24
Posts: 225
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


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Wed Mar 22, 2017 19:43 
Offline

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


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Thu Mar 23, 2017 07:58 
Offline

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


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Sat Mar 25, 2017 09:21 
Offline

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


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Sun Mar 26, 2017 21:44 
Offline

Joined: Wed Sep 01, 2004 18:42
Posts: 1292
Herewith the first results of a test between the Scan and Scan Engine with 2 ply difference in search depth.
See below table:
Attachment:
Table Scan Deep Search 3.png
Table Scan Deep Search 3.png [ 6.67 KiB | Viewed 954 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.
Attachment:
Scan Deep Analysis 2.png
Scan Deep Analysis 2.png [ 39.99 KiB | Viewed 954 times ]


Bert


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Mon Mar 27, 2017 12:02 
Offline

Joined: Sun Dec 28, 2003 20:24
Posts: 225
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?


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Mon Mar 27, 2017 12:40 
Offline

Joined: Wed Apr 14, 2004 15:04
Posts: 1549
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.


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Mon Mar 27, 2017 18:26 
Offline

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


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Mon Mar 27, 2017 18:34 
Offline

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

Attachment:
Scan Deep Analysis 3.png
Scan Deep Analysis 3.png [ 41.04 KiB | Viewed 884 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


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Tue Mar 28, 2017 19:24 
Offline

Joined: Wed Sep 01, 2004 18:42
Posts: 1292
The last match has finished.
See below results.
Attachment:
Table Scan Deep Search 4.png
Table Scan Deep Search 4.png [ 7.72 KiB | Viewed 803 times ]


And the graph.
The exponent is slightly different, but (although statistics could fool us) one can clearly recognize diminishing returns.
Attachment:
Scan Deep Analysis 4.png
Scan Deep Analysis 4.png [ 41.34 KiB | Viewed 803 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


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Wed Mar 29, 2017 05:45 
Offline

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


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Wed Mar 29, 2017 10:09 
Offline

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


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Wed Mar 29, 2017 11:18 
Offline

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


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Wed Mar 29, 2017 19:02 
Offline

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


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 712 posts ]  Go to page Previous 143 44 45 46 47 48 Next

All times are UTC+01:00


Who is online

Users browsing this forum: No registered users and 5 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Limited