Challenge

[Wieger Wesselink]

On https://toernooibase.kndb.nl/opvraag/ap ... 4979&taal= Martin Dolfing explains that he missed a very good opportunity on the 8-th move: 8. ... 21-27 9. 32x21 17x37 10. 41x32 20-24 11. 29x20 15x24. This seems like a nice challenge for computer draughts programmers: is the resulting position winning for black? The opening of the game was 1. 35-30 20-25 2. 33-29 15-20 3. 29-23 19x28 4. 32x23 18x29 5. 34x23 25x34 6. 40x29 16-21 7. 37-32 10-15 8. 44-40.

[FrankMesander]

I did a 60 ply search from move 12 and I dit not find an absolute win for black.

[Joost Buijs]

I have the impression that it might be winning for black, but it ain't easy, it needs at least another 30 moves.
To really find out will take many hours of analysis with the help of a program.

[Ed Gilbert]

I let kingsrow play it out in autoplay at 2min/move, 16 search threads, and it ended in a black win. Of course that's not definitive. A better way to analyze it is using dropout expansion, to automatically explore all reasonable lines of play and build a db. It would probably take days or even weeks to get a propagated score that you could consider definitive.

[FrankMesander]

I let kingsrow play it out in autoplay at 2min/move, 16 search threads, and it ended in a black win. Of course that's not definitive. A better way to analyze it is using dropout expansion, to automatically explore all reasonable lines of play and build a db. It would probably take days or even weeks to get a propagated score that you could consider definitive.

If you only want to know if it is a definitive win for black, without determining the path to win, you can do a 100 ply minimal window search in move 12 for white. Depending on your score for definite win, one can use a window such as -1000 .. -999. If it fails low, you are sure that black wins.
This will take less time I presume.

Am I right?

Frank.

[Ed Gilbert]

If you only want to know if it is a definitive win for black, without determining the path to win, you can do a 100 ply minimal window search in move 12 for white. Depending on your score for definite win, one can use a window such as -1000 .. -999. If it fails low, you are sure that black wins.
This will take less time I presume.

Am I right?

I don't know. Kingsrow is only getting to a 30-ply search depth at 2 minutes, search speed of ~120 Mnodes/sec. It's an MTD search, so it's doing a few null window searches at each depth iteration. At least for kingsrow, a single null window search with a large negative beta for a very long time is unlikely to get to even 50 ply. My experience is that very long searches become very inefficient, as the hashtable quickly fills and becomes a lot less effective, move ordering techniques like history table don't seem to work as well with a mixture of data from a wide range of depths, etc. My guess is that the only way to get 100-ply search depths is with extremely aggressive search reductions, so a very narrow tree. Wouldn't this affect the reliability of the result?

[Rein Halbersma]

On https://toernooibase.kndb.nl/opvraag/ap ... 4979&taal= Martin Dolfing explains that he missed a very good opportunity on the 8-th move: 8. ... 21-27 9. 32x21 17x37 10. 41x32 20-24 11. 29x20 15x24. This seems like a nice challenge for computer draughts programmers: is the resulting position winning for black? The opening of the game was 1. 35-30 20-25 2. 33-29 15-20 3. 29-23 19x28 4. 32x23 18x29 5. 34x23 25x34 6. 40x29 16-21 7. 37-32 10-15 8. 44-40.

At least the position that Martin showed after 35 moves seems a draw according to Kingsrow.

[pontel]

On https://toernooibase.kndb.nl/opvraag/ap ... 4979&taal= Martin Dolfing explains that he missed a very good opportunity on the 8-th move: 8. ... 21-27 9. 32x21 17x37 10. 41x32 20-24 11. 29x20 15x24. This seems like a nice challenge for computer draughts programmers: is the resulting position winning for black? The opening of the game was 1. 35-30 20-25 2. 33-29 15-20 3. 29-23 19x28 4. 32x23 18x29 5. 34x23 25x34 6. 40x29 16-21 7. 37-32 10-15 8. 44-40.

Indeed, this is a position that favors Black. An interesting idea to test this and other complex positions is to create a PDN file so that programs can continue them in a DXP match, alternating sides—sometimes with White, sometimes with Black—ideally with a long reflection time, around 3 hours per player.

I did this with the following position, which I initially thought was lost for White:

01. 34-30 20-25
02. 30-24 19x30
03. 35x24 18-23
04. 32-28? 23x32


On that occasion, Kingsrow managed to draw with White and to win with Black against all the programs I tested.

[Wieger Wesselink]

On https://toernooibase.kndb.nl/opvraag/ap ... 4979&taal= Martin Dolfing explains that he missed a very good opportunity on the 8-th move: 8. ... 21-27 9. 32x21 17x37 10. 41x32 20-24 11. 29x20 15x24. This seems like a nice challenge for computer draughts programmers: is the resulting position winning for black? The opening of the game was 1. 35-30 20-25 2. 33-29 15-20 3. 29-23 19x28 4. 32x23 18x29 5. 34x23 25x34 6. 40x29 16-21 7. 37-32 10-15 8. 44-40.

At least the position that Martin showed after 35 moves seems a draw according to Kingsrow.

Yes that variant is a draw after 32 moves. However, if black plays 30... 11-17! in Martin's variant, then black will almost surely win the game (Scan evaluates it to +1.82 for black after a couple of hours).

The black plan is very simple: attack the white outpost 5 or 6 times until the piece is secured. I don't think white has a serious plan to defend the piece. From a human point of view it seems best for white to defend the piece at least four times, in order to weaken the black position as much as possible. When those two plans are combined, there is only a limited number of positions that need to be considered, and those positions might be close enough to the endgame database to get a definitive result. But even if black would be winning in all of those positions, this is still far from a proof that black is winning in the position after 11 moves.

[gwiesenekker]

The latest version of GWD would play 21-27 with an evaluation of 0.29 after 30 seconds. GWD has a drop-out expansion feature to generate an opening book, it can recursively expand the two best moves in a position with a maximum absolute evaluation of less than or equal to +0.25 to avoid expansion of positions that already are quite bad. I had to increase the maximum absolute evaluation to +0.50 for this position in order to expand 21-27, the drop-out expansion is running now. If after say 10 iterations the evaluation of moves is +/- 0.50 the drop-out expansion will die off, but if it stays around +0.30 at some point it will just take too much time for the next iteration. After two iterations the drop-out expansion tree with 30 seconds/move looks like:

21-27[29, 37] 31x22x27(--, --) 17x37x22x32(--, --) 41x32x37(--, --) 20-24[28, -30000] 29x20x24(--, --) 15x24x20(--, --) !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 31x22x27(--, --) 17x37x22x32(--, --) 41x32x37(--, --) 20-24[28, -30000] 29x20x24(--, --) 14x25x20(--, --) !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 31x22x27(--, --) 17x37x22x32(--, --) 41x32x37(--, --) 05-10[37, -30000] !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 31x22x27(--, --) 17x37x22x32(--, --) 42x31x37(--, --) 20-24[48, -30000] 29x20x24(--, --) 15x24x20(--, --) !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 31x22x27(--, --) 17x37x22x32(--, --) 42x31x37(--, --) 20-24[48, -30000] 29x20x24(--, --) 14x25x20(--, --) !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 31x22x27(--, --) 17x37x22x32(--, --) 42x31x37(--, --) 05-10[37, -30000] !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 32x21x27(--, --) 17x37x21x31(--, --) 41x32x37(--, --) 20-24[28, -30000] 29x20x24(--, --) 15x24x20(--, --) !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 32x21x27(--, --) 17x37x21x31(--, --) 41x32x37(--, --) 20-24[28, -30000] 29x20x24(--, --) 14x25x20(--, --) !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 32x21x27(--, --) 17x37x21x31(--, --) 41x32x37(--, --) 05-10[37, -30000] !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 32x21x27(--, --) 17x37x21x31(--, --) 42x31x37(--, --) 20-24[48, -30000] 29x20x24(--, --) 15x24x20(--, --) !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 32x21x27(--, --) 17x37x21x31(--, --) 42x31x37(--, --) 20-24[48, -30000] 29x20x24(--, --) 14x25x20(--, --) !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 32x21x27(--, --) 17x37x21x31(--, --) 42x31x37(--, --) 05-10[37, -30000] !(flags & FLAG_POSITION_MOVES_EVALUATED)
11-16[13, 9] 31-26[-9, -30000] !(flags & FLAG_POSITION_MOVES_EVALUATED)
11-16[13, 9] 41-37[-12, -30000] !(flags & FLAG_POSITION_MOVES_EVALUATED)

The numbers between angle brackets are the static evalution (29 for 21-27) and the mini-max evaluation (37) based on the drop-out expansion tree, so the mini-max evaluation will get better and better as the drop-out expansion proceeds. An evaluation of -30000 means that the mini-max evaluation is not available because the position has not been evaluated yet 1(flags & FLAG_POSITION_MOVES_EVALUATED) but after some time it can also happen because all moves exceed the expansion threshold of 0.50.

Regards,
GW

[gwiesenekker]

Based on the first 8 iterations we will reach depth 50 in 1M years..

GW

[Krzysztof Grzelak]

The latest version of GWD would play 21-27 with an evaluation of 0.29 after 30 seconds. GWD has a drop-out expansion feature to generate an opening book, it can recursively expand the two best moves in a position with a maximum absolute evaluation of less than or equal to +0.25 to avoid expansion of positions that already are quite bad. I had to increase the maximum absolute evaluation to +0.50 for this position in order to expand 21-27, the drop-out expansion is running now. If after say 10 iterations the evaluation of moves is +/- 0.50 the drop-out expansion will die off, but if it stays around +0.30 at some point it will just take too much time for the next iteration. After two iterations the drop-out expansion tree with 30 seconds/move looks like:

21-27[29, 37] 31x22x27(--, --) 17x37x22x32(--, --) 41x32x37(--, --) 20-24[28, -30000] 29x20x24(--, --) 15x24x20(--, --) !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 31x22x27(--, --) 17x37x22x32(--, --) 41x32x37(--, --) 20-24[28, -30000] 29x20x24(--, --) 14x25x20(--, --) !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 31x22x27(--, --) 17x37x22x32(--, --) 41x32x37(--, --) 05-10[37, -30000] !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 31x22x27(--, --) 17x37x22x32(--, --) 42x31x37(--, --) 20-24[48, -30000] 29x20x24(--, --) 15x24x20(--, --) !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 31x22x27(--, --) 17x37x22x32(--, --) 42x31x37(--, --) 20-24[48, -30000] 29x20x24(--, --) 14x25x20(--, --) !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 31x22x27(--, --) 17x37x22x32(--, --) 42x31x37(--, --) 05-10[37, -30000] !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 32x21x27(--, --) 17x37x21x31(--, --) 41x32x37(--, --) 20-24[28, -30000] 29x20x24(--, --) 15x24x20(--, --) !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 32x21x27(--, --) 17x37x21x31(--, --) 41x32x37(--, --) 20-24[28, -30000] 29x20x24(--, --) 14x25x20(--, --) !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 32x21x27(--, --) 17x37x21x31(--, --) 41x32x37(--, --) 05-10[37, -30000] !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 32x21x27(--, --) 17x37x21x31(--, --) 42x31x37(--, --) 20-24[48, -30000] 29x20x24(--, --) 15x24x20(--, --) !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 32x21x27(--, --) 17x37x21x31(--, --) 42x31x37(--, --) 20-24[48, -30000] 29x20x24(--, --) 14x25x20(--, --) !(flags & FLAG_POSITION_MOVES_EVALUATED)
21-27[29, 37] 32x21x27(--, --) 17x37x21x31(--, --) 42x31x37(--, --) 05-10[37, -30000] !(flags & FLAG_POSITION_MOVES_EVALUATED)
11-16[13, 9] 31-26[-9, -30000] !(flags & FLAG_POSITION_MOVES_EVALUATED)
11-16[13, 9] 41-37[-12, -30000] !(flags & FLAG_POSITION_MOVES_EVALUATED)

The numbers between angle brackets are the static evalution (29 for 21-27) and the mini-max evaluation (37) based on the drop-out expansion tree, so the mini-max evaluation will get better and better as the drop-out expansion proceeds. An evaluation of -30000 means that the mini-max evaluation is not available because the position has not been evaluated yet 1(flags & FLAG_POSITION_MOVES_EVALUATED) but after some time it can also happen because all moves exceed the expansion threshold of 0.50.

Regards,
GW

Very nice analysis of the program.