"pretend solving" 10x10 variants on a 8x8 board

[Fabien Letouzey]

Hi all,

This is mostly for programmers. As some of you know, Scan has recently been extended to support more 10x10 variants, now totalling 5: international draughts (ID), killer draughts (KD), Breakthrough draughts (BT), Frisian draughts (FD), and losing draughts (LD). The last one is also called antidraughts, giveaway, and suicide, among other names.

Last week-end, I initiated a code experiment where I shrank the board size to 8x8. In 2017 I had already introduced a flexible square-numbering module allowing rectangular boards, so this was easy enough. My experience with Othello is that it more or less bypasses the middle game (search + eval), and allows direct connection between the opening book and endgame scores.

While 8x8 variants are probably all candidates for solving, my interest was about what a heuristic program like Scan could find, without spending much time (either in code change, or computation). Scan's opening-book construction uses middle-game searches for the leaves, and min/max values for internal nodes. So, running it for hours or even days represents a giant search only part of which being stored on disk.

---

I started with BT, since Bert and Gérard have already solved it. That gave me something to compare Scan to. After building small endgame tables (10 pieces for BT) and learning an evaluation function, I let opening-book construction run overnight. After about a day, it came up with the following scores for the starting position:

22-18 +581
22-17 -395
23-18 -424
24-19 -432
21-17 -442
24-20 -457
23-19 -469

pv 22-18 10-14 25-22 11-16 22-17 9-13 17x10 6x22 26x17 13x22 30-25 22-26 23x30 7-10 21-17 8-11

Since we know from Bert that 22-18 is actually winning, and from Gérard that all the other moves are losing, it seems to be working. The scores become larger in magnitude with more time. Determining whether they would actually converge to win/loss values was not my objective; with only small endgame tables, it might be difficult to solve this game 100%. Note: I had to force exploration of alternative moves for the test; I assume that Gérard followed a similar procedure.

---

That was a bit easy. A more interesting variant is losing draughts. After a few iterations, the scores are as follows:

21-17 +0
24-20 +0
23-18 -40
22-17 -60
22-18 -108
23-19 -213
24-19 -504

Scan is a heuristic program, so a score of 0 doesn't guarantee a draw. It just means that the deviations have negative scores for both players, but those could change in a deeper search. Indeed after hours of computation, 24-20 gets a positive score and becomes a winning candidate:

24-20 +266
21-17 +0
23-18 +0
22-18 -49
22-17 -140
23-19 -495
24-19 -504

pv 24-20 9-13 28-24 13-17 21x14 10x17 22x13 7-10 25-22 5-9 20-16 12x28 22-18 9-14 18x9

This variant is fairly chaotic with a lot of tactics, so a score of +266 is probably not enough to guarantee a win. I will let the program run and see how things evolve. In any case, this partial result suggests that the variant is not easy (at least with small endgame tables, 7 pieces in this case) and 24-20 in particular might lead to subtleties.

---

I also ran the same computation for Killer draughts and Frisian draughts (on 8x8), but those are extremely boring. Most moves at multiple levels in the tree lead to a draw. Removing the killer rule would make the game exactly Brazilian draughts, and I have no doubt that it would lead to even more draws; I will not pursue this matter.

Fabien.

[Fabien Letouzey]

Hi all,

Just an update on the computation. With the heat wave coming at full strengh, I will probably stop it and consider the project as completed.

Breakthrough:

22-18 +877
22-17 -461
24-19 -464
23-18 -479
21-17 -498
24-20 -510
23-19 -527

Losing draughts:

24-20 +550
23-18 +0
22-18 -148
21-17 -172
22-17 -202
23-19 -495
24-19 -504

24-20 appears to be winning more and more clearly with time.

In both books, I forced exploration of alternative moves. No additional winning candidate has emerged in LD.

Fabien.

[Rein Halbersma]

Interesting stuff! Can you post the PVs for both games?

[Fabien Letouzey]

Interesting stuff! Can you post the PVs for both games?

Yes.

BT: 22-18 11-15 18x11 8x15 21-17 7-11 17-13 9-14 23-19 11-16

LD: 24-20 9-13 28-24 13-17 21x14 10x17 22x13 5-9 20-16 12x28 25-22 8-12 22-18 11-16 18-14 9x18 23x14 6-10 27-23 10x17 13x22 1-5

I stopped showing them, because I think that the losing side is playing increasingly desperate moves in order to postpone the (alleged) inevitable.

[Fabien Letouzey]

(losing draughts only)

Usually a single computation step, expanding a leaf (whose position is displayed), takes about a minute. And, while I was watching the "alternative move" search (which excludes 24-20), many steps in succession only took a second, with long lines (about 40 plies, and normal search is applied beyond that). I think that the book more or less solved 23-18 as a draw. It's now focusing its attention on 22-18 only, although that move has the same score and computation time should be shared between the two moves. I think this indicates that the book is saturated with the "proof" tree for 23-18 and doesn't need to explore it further for now. I don't assume that the proof is complete, however; just more reliable than before.

The current scores are:

24-20 +590
22-18 +0
23-18 +0
21-17 -157
22-17 -202
23-19 -495
24-19 -504

pv 24-20 11-16 20x11 8x15 23-18 12-16 18x20 7-11 28-24 9-13 24-19 4-8

The drawing PVs might be more interesting, although 24-20 is better:

22-18 9-13 25-22 5-9 29-25 1-5 22-17 13x15 26-22 15-18 23x14 10x26 31x22 12-16 24-19 16x23 27x18 11-15 18x11 8x15 28-24 15-19 24x15 7-11 15x8 4x11 32-27 6-10 27-24 2-6 30-26 9-14 26-23 14-18 23x16 5-9 24-19 3-8 16-11 8x24

23-18 9-13 24-20 5-9 18-15 10x19 20-16 11x20 27-24 20x27 32x16 12x19 28-24 19x28 22-17 13x22 25x18 9-13 29-25 13-17 21x14 6-9 14x5 28-32 26-22 32x9 5x14 2-6 14-9 6x13 22-18 7-11 18-15 11x18 31-27 18-23 27x18 3-7 30-26 8-12 26-23 12-16 25-22 (13-17 22x13)

The last 2 plies are not part of the book for some reason. With that addition, both lines end in endgame tables which stop at 7 pieces.

[Rein Halbersma]

In 2010 Martin Fierz used a 180K positions opening book and 8 piece dbs to pseudo-solve 8x8 suicide checkers. https://checker-board.blogspot.com/2010 ... bably.html

How big are your books for BT and LD? With 8 piece dbs you might see to the end of the game.

[Fabien Letouzey]

How big are your books for BT and LD? With 8 piece dbs you might see to the end of the game.

They are tiny in comparison: about 5k for BT and 20k for LD (internal nodes). But I think that it can be misleading: you can compensate for a small book by having a better leaf "evaluation". Last week I actually interrupted the book building and restarted with a larger search depth (for the leaves); the books were smaller, but the general behaviour looked the same. Scan also has search extensions for LD that might make progress much easier (untested on 8x8).

As for endgame tables, 8-piece was the plan; P+2 compared to the 10x10 board. I think I could generate the tables individually, but collectively they wouldn't fit in my 8GB RAM (I predict about 13GB), due to bad compression (naive RLE, because I had to finish Scan 2.0 in a hurry for the 2015 Olympiad). In 10x10, LD has the strange property that larger tables help more and more; the near opposite of the other variants, at least past 4 pieces. So just increasing from 7 to 8 might help a lot indeed.