Search Algorithm

[Fabien Letouzey]

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: Select all

    +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.

[Fabien Letouzey]

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!

[BertTuyt]

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

[BertTuyt]

Herewith the first results with a Scan evaluation with material and left/right balance only.

Table Scan Deep Search 5.png (11.24 KiB) Viewed 12502 times

Table Scan Deep Search 6.png (33.94 KiB) Viewed 12502 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

[BertTuyt]

Herewith the final (so far) results related to the Scan - Scan match, with an evaluation function with material + left / right balance only.

Table Scan Deep Search LR.png (11.65 KiB) Viewed 12405 times

Scan Deep Analysis LR.png (19.85 KiB) Viewed 12406 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

[BertTuyt]

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.

Table Scan Deep Search 7.png (10.96 KiB) Viewed 12362 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.

Scan Deep Analysis DE.png (47.39 KiB) Viewed 12362 times

Bert

[Fabien Letouzey]

Hi Bert,

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.

[BertTuyt]

Fabien, the honest answer is maybe nothing, as it is too early to draw conclusions.
What is your 5 cents

Bert

[Fabien Letouzey]

What is your 5 cents

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.

[BertTuyt]

Fabien, thanks for your inspiring more as 5 cents thoughts
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

[Fabien Letouzey]

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.

[Rein Halbersma]

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).

[Fabien Letouzey]

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.

[Rein Halbersma]

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.

[Rein Halbersma]

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.