Fabien Letouzey wrote:
For Killer draughts I now have data that confirms this. I can learn evaluation weights using Killer-draught games and use them in normal draughts; the level is the same as a more taylored eval, at least with logistic regression; this wasn't the case in 2015.
Wow, I remember formulating that as a hypothesis 2 years ago. Nice result! Do you have any idea why it works now but didn't then?
I had interest in Frisian draughts in 2015. During the man-machine match the same year, a proponent of the game even had leaflets in English; kudos to him! Unfortunately I was unable to understand the capturing rules on my way back (...); something about a king being worth "between one and two men" for captures. It looked ambiguous to me, and I couldn't translate it to maths (other than picking 1.5 at random). However I'm looking for information again and it looks much clearer in two stages:
- majority rule
- "king majority" as a secondary rule
If only I had seen that in 2015 ...
The capture rules of Frisian are a bit exotic, but they can be computed in a very straightforward matter. The value of N kings is more than 2N-1 men, but less than 2N men. Hypothetically, if you were using floating point eval weights, you would put the value of a king at 1.999... men. But for integer weights, just use 2 - 1/64 since you can't ever capture more than 64 pieces. The total value of capturing M men and K kings is then: V = M + (2 - 1/64) K or 64 V = 64 * (M + 2 K) - K = (P + K) << 6 - K where P = M + K is the total number of captured pieces. So when comparing two moves for precedence, you only have to compute (P+K)<<6 -K for each move. For equal values, there is also a tie-breaker rule: capturing with a king takes precedence.
Other rules of Frisian draughts are a show stopper, though. I was only considering othogonal captures, with the smaller draw rate as a bonus. At most 3 moves by a wolf/king (as I recall) will destroy the best-designed endgame table builder in no time. Nonetheless apparently an old game with a lot of tradition; interesting that it's still played.
The rule you quoted is: you can't move with the same king more than 3 moves in a row if and only if you have both at least one king and at least one man. After the 3rd consecutive move with the same king, you either have to make a man move, or a capture (possibly with that same king).
With this rule, databases for Frisian draughts are also exotic but not impossible. You just need to multiply the state space by a pair of indices (index of king in the number of kings, number of consecutive moves). So for the endgame of 2 kings + 1 man vs 1 king e.g., this multiplies the number of states by 8 (2 values for the king index, times 4 for the number of moves). So this is a database in a generalized state space with 2 virtual pieces which take on special values (not board squares). Move generation in this state space is then straightforward: just reset the number of consecutive moves after any move with another piece.
See also this thread: viewtopic.php?t=2911
For evaluation, my only thought was that 4x4 patterns might not be enough for top-level performance: line of 3 squares don't fit anywere. So maybe 5x5 patterns (13 squares), which are difficult to learn => probably not worth the effort. Regardless of eval quality, I don't expect humans to resist the tactical precision of programs however.
Frisian draughts is probably the easiest game to solve (for a given board size, I am not claiming that on a 10x10 it is feasible), since it converges much faster to the endgame than international or Killer draughts. The number of captures are just enormous. You can be in a 6 vs 6 piece endgame within 20 moves of the opening.
3) Give-away draughts
I haven't considered that variant. Already the concept of material-only search breaks down (guess), so I would have to start with a manual eval that plays decently. Or fully-random games, pure-MC style. I doubt that the strategy would be relevant in any other variant, but am confident that the usual techniques would do well: endgame tables -> generating games -> learning patterns -> tuning pruning -> opening book. There is order in this chaos.
I'm not sure why you're expecting pattern evaluation to be especially adapted to this variant. Maybe you're referring to the fact that they (more or less) automate feature construction like neural networks. In my view, patterns should do well in all draughts variants. They might collapse on very large boards if long-distance strategy is important (as in Go).
The point that Martin makes in his blog is that a regular material-only eval didn't do anything. So patterns are not just nice to have, but need to have. Maybe you can have a good PST as well. But it's an extremely non-intuitive game. E.g. this position:
White to move
is a win for white! Think about that