World Draughts Forum

It is currently Thu Nov 23, 2017 12:09

All times are UTC+01:00




Post new topic  Reply to topic  [ 183 posts ]  Go to page Previous 19 10 11 12 13 Next
Author Message
PostPosted: Wed Sep 20, 2017 22:52 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 806
Location: FRANCE
BertTuyt wrote:
Rebooting of the system is not very helpful when you are doing calculations for days :)

Anyway, after some interrupts, now 4 moves proved as a loss.
23-18, 21-17, 24-20, 23-19
So with the already proved 22-18, 2 moves to go.
And on my other computer I already proved 22-17 as a loss.
So 1 move down only

Very strange that only 1 move is winning, think no-one sees a logical explanation for this (yet).
Maybe in a galaxy far far away......

In the beginning I also thought that black was winning, which I now understand.
Based upon games with random moves ordering, you might come to this wrong conclusion.

I'm also afraid, that we for ages we wont have a clue what the BT 10x10 outcome will be.
My educated guess would be a white win, but for unknown reasons.

Bert


Hi Bert,

I think I have a logical statistic explanation to propose.

Look at the statistics on symmetrics configuration:
1x1 NCW1= 388 NCL1= 306
2x2 NCW1= 56 410 NCL1= 33 269
3x3 NCW1= 2 699 916 NCL1= 1 255 259
4x4 NCW1= 56 865 877 NCL1= 20 714 313
5x5 NCW1= 613 334 701 NCL1= 177 227 198
6x6 NCW1= 3 751 257 816 NCL1= 893 491 452
7x7 NCW1= 14 036 633 965 NCL1= 2 910 252 528
8x8 NCW1= 34 000 336 726 NCL1= 6 522 909 535

You see clearly that NCW1/NCL1 grows regularly to reach more than 5 for 8x8. It is simply a confirmation of a basic fact: when the position looks equal the side to move has the best chance to win!
For a 8x8 position the side to move has really more than 80% chance of winning.

Based on this consideration I would claim without calculation that the starting position (a 12x12 position) is certainly a winning position (more than 80% chance of winning).

Let's go a little farther: after any of the 7 legal white moves from the starting position it is now black to move and the 7 positions looks again quite egal. That means that on average more than 80% of these positions are winning for black point if view.

As a conclusion you see we have to expect two things:
1) The starting position has very good chances to be a winning position
2) The number of winning moves in the starting position is probably very low

Is it still very strange for you to have only one winning move?

My guess is that it is also true for the 10x10 BT game!

_________________
Gérard


Top
   
PostPosted: Thu Sep 21, 2017 07:23 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1559
Gerard's reasoning was first made in 1981 as a statistical property of game trees. Citing Uiterwijk and Van den Herik (2000, see http://citeseerx.ist.psu.edu/viewdoc/su ... 1.109.3661):

Quote:
In 1981, David Singmaster [25,26] proved a rather conclusive and elegant
theorem why first-player wins should abound over second-player wins. The
positions in a game with two outcomes (won, lost) are split up into P-positions
(from which the previous player can force a win) and N-positions (from which
the next player can force a win). For the first player to have a forced win, just
one of the moves needs to lead to a P-position. For the second player to have a
forced win, all of the moves must lead to N-positions. For games with three
outcomes, possible draws can be easily included in this line of reasoning,
stating that first-player wins should abound over draws and second-player
wins.


And let's not forget that 8x8 BT checkers (aka Kingscourt) is a second-player win!


Top
   
PostPosted: Thu Sep 21, 2017 19:05 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Gerard/Rein, thanks for your reactions.
I meant that from a visual point of view, it is for me not clear why there is only 1 winning move 22-18.

I can imagine that moving to the edges is not as optimal.
But (not looking to the statistics) why all other moves fail, is a riddle.
And how to include these nuances in an evaluation function is another challenge.

So I also think that BT 10x10 is winning for white.
But does anyone dare to state (already) that there is only 1 winning move (for example) 32-28

Bert


Top
   
PostPosted: Thu Sep 21, 2017 23:46 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 806
Location: FRANCE
BertTuyt wrote:
Gerard/Rein, thanks for your reactions.
I meant that from a visual point of view, it is for me not clear why there is only 1 winning move 22-18.

I can imagine that moving to the edges is not as optimal.
But (not looking to the statistics) why all other moves fail, is a riddle.
And how to include these nuances in an evaluation function is another challenge.

So I also think that BT 10x10 is winning for white.
But does anyone dare to state (already) that there is only 1 winning move (for example) 32-28

Bert


Hi,

Of course nobody knows what would happen for BT 10x10 but for sure the winning line is very narrow and obviously our programs will make a lot of mistakes in the 30 first moves. The point is the following : when you give your opponent a position which looks equal the probability is very high that your opponent has a winning position!!!
I will not surprise if more than 50% of the first 30 moves played by our programs are really mistakes!

As a consequence I consider the BT 10x10 game far more difficult than the international 10x10 draughts game.

_________________
Gérard


Top
   
PostPosted: Fri Sep 22, 2017 18:56 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Did some-one already try the Scan BT version?
Interesting what a 1000 (or other large number) game match self play (example both programs on 10 Ply, or whatever) would learn.
As we all tend to believe that it is a white win, every black win would than contain at least one error.

In the meantime also 22-17 recognized as a loss.
So when 24-19 is solved, I most likely can confirm the claim that only 22-18 wins.

Bert


Top
   
PostPosted: Sun Sep 24, 2017 11:51 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
It took some time, but also on my side the result is now confirmed that 22-18 remains a win, and all other initial moves are a loss.
I will take now a short break, before restarting.

Bert


Top
   
PostPosted: Sun Sep 24, 2017 17:56 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 806
Location: FRANCE
BertTuyt wrote:
It took some time, but also on my side the result is now confirmed that 22-18 remains a win, and all other initial moves are a loss.
I will take now a short break, before restarting.

Bert


Good confirmation Bert,

In addition, on the 6 losing white move, black has on average 2,5 winning moves which is higher than I expected.
Anyway, on the best defense, the winning line seems very narrow!

After having looked at some other positions I admit I am completly unable to find any clue for deciding between winning and losing position.

Two examples:

Image
White to play : losing position!

Image
white to play
The only winning move here is maybe the most doubtful move 21-17!!

Very strange indeed.
I am just able to make pure statistics reasonning.

_________________
Gérard


Top
   
PostPosted: Sun Sep 24, 2017 19:43 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Gerard, herewith some data.
In below table I have listed at which ply which move was proved.
Keep in mind that due to different ply definitions, extensions or pruning, not all plies are equal, among programs.
Maybe it also gives a clue about the complexity of the path.

Code:
Ply   Move      Score
-----------------------
30   23-19      Loss
32   24-20      Loss
33   23-18      Loss
33   21-17      Loss
35   22-17      Loss
36   24-19      Loss
37   22-18      Win

Bert


Top
   
PostPosted: Sun Sep 24, 2017 21:20 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Hope that Fabien would be able to provide a Scan 8x8 BT with a evaluation based upon ML.
If the Scan 8x8 BT Database is limited (example 6P), we could really learn what the error rate is for the search (as a function of ply).
If Scan 8x8 BT would play white, every lost game would at least contain 1 error (assuming that the other side is the all knowing DB).

Bert


Top
   
PostPosted: Sun Sep 24, 2017 21:23 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Gerard, do you have already an insight for all initial while losing moves (for example 23-19), how many moves on black side are winning.
For 23-19 at least the 12-16 move (which immediately loses 1 man), seems to me already losing for black.

Bert


Top
   
PostPosted: Sun Sep 24, 2017 23:42 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 806
Location: FRANCE
BertTuyt wrote:
Gerard, do you have already an insight for all initial while losing moves (for example 23-19), how many moves on black side are winning.
For 23-19 at least the 12-16 move (which immediately loses 1 man), seems to me already losing for black.

Bert


Hi Bert,

The complete answer to your question is the following:

22-18 winning move
24-20 losing move; 3 black winning moves : 11-16, 11-15, 9-13
23-19 losing move; 4 black winning moves : 11-16, 9-13, 9-14, 11-15
21-17 losing move; 1 black winning move : 9-13
24-19 losing move; 3 black winning moves : 11-16, 10-14, 11-15
23-18 losing move; 3 black winning moves : 12-16, 11-15, 11-16
22-17 losing move; 1 black winning move : 11-15

On average : 2,5 black winning moves on 7 possible moves

You can note some strange results like 24-20? 9-13 and white has a losing position!

_________________
Gérard


Top
   
PostPosted: Mon Oct 09, 2017 08:59 
Offline

Joined: Sun Dec 28, 2003 20:24
Posts: 233
It's nice to see a draughts-like game not ending in a almost-certain draw. I'll do some experiments with it as well.

I created a BT endgame database for 10x10. Can any of you confirm the numbers if you have 10x10 available?

Code:
Solved 1 - 1: wins=         1.148, size=         1.985, rate=0.0 Mpos/sec
Solved 2 - 1: wins=        35.925, size=        42.790, rate=0.1 Mpos/sec
Solved 1 - 2: wins=        13.785, size=        42.790, rate=0.1 Mpos/sec
Solved 2 - 2: wins=       567.700, size=       903.440, rate=0.9 Mpos/sec
Solved 3 - 1: wins=       545.176, size=       600.710, rate=0.9 Mpos/sec
Solved 1 - 3: wins=       137.563, size=       600.710, rate=1.0 Mpos/sec
Solved 3 - 2: wins=     9.794.441, size=    12.416.680, rate=5.8 Mpos/sec
Solved 2 - 3: wins=     5.540.861, size=    12.416.680, rate=5.9 Mpos/sec
Solved 3 - 3: wins=   107.237.253, size=   166.991.800, rate=17.4 Mpos/sec
Solved 4 - 1: wins=     5.811.821, size=     6.175.015, rate=4.3 Mpos/sec
Solved 1 - 4: wins=     1.141.870, size=     6.175.015, rate=6.0 Mpos/sec
Solved 4 - 2: wins=   106.895.851, size=   124.899.950, rate=16.2 Mpos/sec
Solved 2 - 4: wins=    42.802.678, size=   124.899.950, rate=17.1 Mpos/sec
Solved 4 - 3: wins= 1.244.935.203, size= 1.642.957.750, rate=22.9 Mpos/sec
Solved 3 - 4: wins=   822.763.214, size= 1.642.957.750, rate=21.2 Mpos/sec
Solved 4 - 4: wins=10.175.184.347, size=15.802.050.675, rate=14.5 Mpos/sec

Michel


Top
   
PostPosted: Mon Oct 09, 2017 10:49 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 806
Location: FRANCE
MichelG wrote:
It's nice to see a draughts-like game not ending in a almost-certain draw. I'll do some experiments with it as well.

I created a BT endgame database for 10x10. Can any of you confirm the numbers if you have 10x10 available?

Code:
Solved 1 - 1: wins=         1.148, size=         1.985, rate=0.0 Mpos/sec
Solved 2 - 1: wins=        35.925, size=        42.790, rate=0.1 Mpos/sec
Solved 1 - 2: wins=        13.785, size=        42.790, rate=0.1 Mpos/sec
Solved 2 - 2: wins=       567.700, size=       903.440, rate=0.9 Mpos/sec
Solved 3 - 1: wins=       545.176, size=       600.710, rate=0.9 Mpos/sec
Solved 1 - 3: wins=       137.563, size=       600.710, rate=1.0 Mpos/sec
Solved 3 - 2: wins=     9.794.441, size=    12.416.680, rate=5.8 Mpos/sec
Solved 2 - 3: wins=     5.540.861, size=    12.416.680, rate=5.9 Mpos/sec
Solved 3 - 3: wins=   107.237.253, size=   166.991.800, rate=17.4 Mpos/sec
Solved 4 - 1: wins=     5.811.821, size=     6.175.015, rate=4.3 Mpos/sec
Solved 1 - 4: wins=     1.141.870, size=     6.175.015, rate=6.0 Mpos/sec
Solved 4 - 2: wins=   106.895.851, size=   124.899.950, rate=16.2 Mpos/sec
Solved 2 - 4: wins=    42.802.678, size=   124.899.950, rate=17.1 Mpos/sec
Solved 4 - 3: wins= 1.244.935.203, size= 1.642.957.750, rate=22.9 Mpos/sec
Solved 3 - 4: wins=   822.763.214, size= 1.642.957.750, rate=21.2 Mpos/sec
Solved 4 - 4: wins=10.175.184.347, size=15.802.050.675, rate=14.5 Mpos/sec

Michel


Hi Michel,
Good news to see your interesting by this beautitul draughts variant.
As with Bert I have the same difficulty with you : I did not generate the capture positions. Bert managed to add statitistics on non capture position in order to compare our figures but I do not know if it is easy for your implementation to do the same.
FYI my figures are
1x1 NCW1= 1 028 NCL1= 837 NCW2= - NCL2= -
2x1 NCW1= 30 993 NCL1= 6 865 NCW2= 11 268 NCL2= 26 595
2x2 NCW1= 424 883 NCL1= 285 789 NCW2= - NCL2= -
3x1 NCW1= 446 168 NCL1= 55 534 NCW2= 113 391 NCL2= 388 438
3x2 NCW1= 6 778 061 NCL1= 1 948 633 NCW2= 3 775 435 NCL2= 4 952 702
3x3 NCW1= 63 546 643 NCL1= 35 985 469 NCW2= - NCL2= -
4x1 NCW1= 4 518 137 NCL1= 363 194 NCW2= 927 678 NCL2= 3 954 768
4x2 NCW1= 67 423 737 NCL1= 11 426 249 NCW2= 28 548 951 NCL2= 50 312 655
4x3 NCW1= 652 076 102 NCL1= 184 976 683 NCW2= 438 218 089 NCL2= 398 830 286
4x4 NCW1= 4 486 519 068 NCL1= 2 080 557 566 NCW2= - NCL2= -

_________________
Gérard


Top
   
PostPosted: Mon Oct 09, 2017 12:32 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1559
TAILLE wrote:
Hi Michel,
Good news to see your interesting by this beautitul draughts variant.
As with Bert I have the same difficulty with you : I did not generate the capture positions. Bert managed to add statitistics on non capture position in order to compare our figures but I do not know if it is easy for your implementation to do the same.
FYI my figures are
1x1 NCW1= 1 028 NCL1= 837 NCW2= - NCL2= -
2x1 NCW1= 30 993 NCL1= 6 865 NCW2= 11 268 NCL2= 26 595
2x2 NCW1= 424 883 NCL1= 285 789 NCW2= - NCL2= -
3x1 NCW1= 446 168 NCL1= 55 534 NCW2= 113 391 NCL2= 388 438
3x2 NCW1= 6 778 061 NCL1= 1 948 633 NCW2= 3 775 435 NCL2= 4 952 702
3x3 NCW1= 63 546 643 NCL1= 35 985 469 NCW2= - NCL2= -
4x1 NCW1= 4 518 137 NCL1= 363 194 NCW2= 927 678 NCL2= 3 954 768
4x2 NCW1= 67 423 737 NCL1= 11 426 249 NCW2= 28 548 951 NCL2= 50 312 655
4x3 NCW1= 652 076 102 NCL1= 184 976 683 NCW2= 438 218 089 NCL2= 398 830 286
4x4 NCW1= 4 486 519 068 NCL1= 2 080 557 566 NCW2= - NCL2= -


Hi Gerard,

Is it possible for you to modify your routine so as to print the capture positions after the last generation pass? And then drop them for the final compression stage? Or would this be a too invasive change of your generator?

Rein


Top
   
PostPosted: Mon Oct 09, 2017 13:10 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 806
Location: FRANCE
Rein Halbersma wrote:

Hi Gerard,

Is it possible for you to modify your routine so as to print the capture positions after the last generation pass? And then drop them for the final compression stage? Or would this be a too invasive change of your generator?

Rein


I don't quite understand your question.

Basically my routine looks like:

for (db = first db; db < last db; db = following db)
{
for (p = first position of the db; p < last position; p = following position)
{
if (p == capture position) continue;
else {generate successors; evaluate p; save result in memory db}
}
compress memory db and store on disk;
}

Of course I added some complexity in order to have a multithread routine

_________________
Gérard


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 183 posts ]  Go to page Previous 19 10 11 12 13 Next

All times are UTC+01:00


Who is online

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