World Draughts Forum

It is currently Mon Nov 20, 2017 12:39

All times are UTC+01:00




Post new topic  Reply to topic  [ 712 posts ]  Go to page Previous 144 45 46 47 48 Next
Author Message
 Post subject: Re: Search Algorithm
PostPosted: Wed Mar 29, 2017 20:06 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 236
Real name: Fabien Letouzey
Fabien Letouzey wrote:
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 computed it for men only, in cp:
Code:
    +0    +0    +0    +0    +0   
+32   +95   +80   +85   +111   
   +38   +23   +16   +26   -11   
-19    -2   -15   -11   -11   
   -20   -26   -16   -15   -12   
-13   -17    -9   -17   -22   
   -20   -15   -10   -19   -18   
-20   -16   -11   -13   -19   
   -21   -11    -9   -14   -19   
-24    -7    +0    -6    -8   

Let me know if you need kings too.


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Wed Mar 29, 2017 20:41 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 236
Real name: Fabien Letouzey
BertTuyt wrote:
Fabien, it doesnt need to be strong, it only should be different from a performance point of view.

It seems past the midpoint between material-only and patterns, even without balance, king eval, game phase, etc ... In slower time control it should get many draws against much better evals, as you predicted!


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Sun Apr 02, 2017 12:40 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Fabien, thanks for the PST.
Will implement in in the next weeks
I don't need a kings PST yet.
I'm now doing some tests/experiments with right-left balance (including material) evaluation only.
Will post some initial results later today.

Bert


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Sun Apr 02, 2017 17:03 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Herewith the first results with a Scan evaluation with material and left/right balance only.

Attachment:
Table Scan Deep Search 5.png
Table Scan Deep Search 5.png [ 11.24 KiB | Viewed 1315 times ]


Attachment:
Table Scan Deep Search 6.png
Table Scan Deep Search 6.png [ 33.94 KiB | Viewed 1315 times ]


Remark: The match 22 Ply -20 Ply now running.
The exponent seems not in line with the model assumption.
But we need more data points on the low and high Ply sides.

Bert


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Thu Apr 06, 2017 13:13 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Herewith the final (so far) results related to the Scan - Scan match, with an evaluation function with material + left / right balance only.

Attachment:
Table Scan Deep Search LR.png
Table Scan Deep Search LR.png [ 11.65 KiB | Viewed 1218 times ]


Attachment:
Scan Deep Analysis LR.png
Scan Deep Analysis LR.png [ 19.85 KiB | Viewed 1219 times ]


The exponent seems not to be inline with the model, so not impossible (but likely) that the model R = R0(1- f(d)*g(k)) is not valid.
But clearly visible deminshing returns.

I will continue with an eval containing also the king eval-components of Scan, but still excluding patterns.

Hereafter I wil start with the PST based evaluation.
And then a mix match between Scan with different search depth and different eval.

Bert


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Fri Apr 07, 2017 09:28 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Herewith the first result with the Scan eval without patterns, but with the King components and left/right balance.
See below table for some match results.

Attachment:
Table Scan Deep Search 7.png
Table Scan Deep Search 7.png [ 10.96 KiB | Viewed 1175 times ]


In below graph I combined the results from 3 tests.
Blue Line eval with left/right balance and material)
Orange Line, left/right balance, material, and king components.
Grey Line, full Scan Eval.

Attachment:
Scan Deep Analysis DE.png
Scan Deep Analysis DE.png [ 47.39 KiB | Viewed 1175 times ]


Bert


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Fri Apr 07, 2017 12:30 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 236
Real name: Fabien Letouzey
Hi Bert,

BertTuyt wrote:
In below graph I combined the results from 3 tests.
Blue Line eval with left/right balance and material)
Orange Line, left/right balance, material, and king components.
Grey Line, full Scan Eval.

What do you see in this graph?

Fabien.


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Fri Apr 07, 2017 12:38 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Fabien, the honest answer is maybe nothing, as it is too early to draw conclusions.
What is your 5 cents :D

Bert


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Fri Apr 07, 2017 13:49 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 236
Real name: Fabien Letouzey
BertTuyt wrote:
What is your 5 cents :D

I'll take the challenge. The full eval converges quickly to a point of diminishing returns, suggesting that searching deeper will not improve it much. This would not appear as clearly if you only displayed that curve. By contrast, it seems that a weaker eval benefits much more from additional search depth. Random idea: if someone wants to study search heuristics, maybe use a bad eval such as a PST ;)

I don't know what you are after. Since it is your research, I assume that you have something specific in mind; maybe a theory you want to confront with reality :) A suggestion that is in-line with Rein's mention of "knowledge": find different search depths that make various evaluations close in level. Something like PST + 20 plies vs. full eval + 15 plies. I don't like equating "knowledge" with eval though; there is a lot of knowledge in search.

Also I'm not sure how much the "draw black hole" affects your results. I have the feeling that "playing close to perfection" and "entering the dense draw area" are different things. In other words, is the weaker player really making many fewer mistakes, or is it just that we can't observe any progress due to the draws (my theory)? I would consider similar experiments with variants that have fewer draws. If the graph is the same, it would indicate that draws don't overly affect the results. Instead I expect much slower diminishing returns, maybe 3x slower using my simple Elo formula: draughts Elo = killer-draughts Elo (which I claim is comparable to other games) / 3.

Additionally to killer draughts, I intend to compute an eval for the variant where the first player to make a king wins. I don't know if it already has a name (other than king's court), so for now I use the term "race". I'm curious whether the resulting program would still play decent draughts or not. I guess "not", up to a point, because runners will be given too large a score. If, however, the level happened to be acceptable, I would interpret it in this way: draughts is about finding a path to promotion, even if we don't know what happens afterwards.


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Fri Apr 07, 2017 18:03 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Fabien, thanks for your inspiring more as 5 cents thoughts :D
Basically I want to find a model for the strength of a Draughts program.
Especially if we are already near to perfect play, or that we still can gain significant ELO points.

You are right, I also believe that the draw black hole affects results.
Im convinced that we might be able to earn more ELO, but the graphs suggest that this should be based on knowledge, and not deeper search.

Your proposal to do similar tests with killer Draughts make sense.

Im now doing the tests for the PST eval, this weekend I might do a first test with PST versus full eval.

Last but not least, I exactly thought about the same Draughts variant as you, the player who promotes first wins.
My interest was based upon solving this variant.
At least only man-based DBs are required, and this might help.

Bert


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Fri Apr 07, 2017 18:44 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 236
Real name: Fabien Letouzey
BertTuyt wrote:
Last but not least, I exactly thought about the same Draughts variant as you, the player who promotes first wins.
My interest was based upon solving this variant.
At least only man-based DBs are required, and this might help.

I don't think it can be solved, but don't let that stop you :)

I looked at a couple of games, with endgame tables but without a tuned eval, and the scores were small for a long time. Then at some point, the loser has to give away material to (pointlessly) postpone the loss. It snowballs for a few moves before an exact result is announced. The same thing happens in chess with deep mates: they are usually first "announced" as material gains.

Othello is likely solvable thanks to a combination of factors:
1) fixed game length
2) most moves are bad => only 1-3 playable moves in a given position
3) very accurate pattern evaluation, especially late in the game

I don't see 2) in any draughts variant, in particular in the opening; this is a major obstacle to solving. Also, the number of moves before search can see the result seems too large. However a possibility remains: maybe there are many move sequences, but few intermediate positions, say 40 plies from the starting position, with reasonable play from both sides.

I should have a taylored eval in 1-2 weeks; I'll let you know if this changes my view. In any case, it's a variant without draws so every game is exciting. There's also a chance that search plays a more important role; maybe the endgame is chaotic. On the other hand, there is the risk that this variant favours one of the players even without perfection.

Regarding endgame tables, I simply reused my previous code. The builder doesn't know that a draw is not possible. I easily created tables for upto 7 pieces in a few hours, and 8 looks possible. My generator is RAM-only and has no slicing: it won't be able to go further with a normal machine. I guess that, if you can build draughts tables for P pieces, you can do it for P+2 in this variant.


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Fri Apr 07, 2017 20:07 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1559
Fabien Letouzey wrote:
Regarding endgame tables, I simply reused my previous code. The builder doesn't know that a draw is not possible. I easily created tables for upto 7 pieces in a few hours, and 8 looks possible. My generator is RAM-only and has no slicing: it won't be able to go further with a normal machine. I guess that, if you can build draughts tables for P pieces, you can do it for P+2 in this variant.


Could you explain a bit more? How do you solve P+2 pieces when you only save 1 bit per position (so size goes in half only). 10-piece dbs seem a very big stretch at the moment (needs very serious hardware).


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Fri Apr 07, 2017 20:17 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 236
Real name: Fabien Letouzey
Rein Halbersma wrote:
Could you explain a bit more? How do you solve P+2 pieces when you only save 1 bit per position (so size goes in half only). 10-piece dbs seem a very big stretch at the moment (needs very serious hardware).

You win when you make a king, so the game contains only men.


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Sat Apr 08, 2017 00:39 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1559
Fabien Letouzey wrote:
Rein Halbersma wrote:
Could you explain a bit more? How do you solve P+2 pieces when you only save 1 bit per position (so size goes in half only). 10-piece dbs seem a very big stretch at the moment (needs very serious hardware).

You win when you make a king, so the game contains only men.


Ah, yes, silly of me. I only considered that there were 2 results :) This is indeed a major increase in database strength.


Top
   
 Post subject: Re: Search Algorithm
PostPosted: Sat Apr 08, 2017 00:43 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1559
Fabien Letouzey wrote:
I would consider similar experiments with variants that have fewer draws.


There are 4 variants that I can think of:

1) Killer draughts
2) Frisian draughts (orthogonal captures, and a few extra details)
3) Give-away draughts
4) Breakthrough draughts (aka Kingscourt, named by Martin Fierz)

Martin Fierz's blog has a story how he solved 4) and found 3) already very difficult to program well. His give-away program lost against a Russian program (in Russia, give-away is an often played variant for humans as well). I would expects patterns to pay off really well in this game.


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

All times are UTC+01:00


Who is online

Users browsing this forum: No registered users and 6 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