World Draughts Forum

It is currently Thu Oct 19, 2017 03:51

All times are UTC+02:00




Post new topic  Reply to topic  [ 183 posts ]  Go to page Previous 1 2 3 4 5 613 Next
Author Message
PostPosted: Thu Aug 10, 2017 17:23 
Offline

Joined: Sun Sep 13, 2009 23:33
Posts: 116
Real name: Jan-Jaap van Horssen
Location: Zeist, Netherlands
Quote:
If you have position2index and vice versa on this array, you can simply start with the initial position and scan the array repeatedly. It would be handy if you also kept an intermediate bitarray of 7.5 Gb of all positions reached in the previous iteration. Then you can iterate over all 1-bits and compute successors of all positions reached in the last iteration and add those to the base array and the next queue. Essentially this is equal to the 2-bit algorithm for database generation, I think by Wu & Beal, but here you use repeated forward passes instead of retrograde computations. It does require indexing, but if you have already that infractructure in place, it should be similar to building regular databases :)

Yes, I have position<->index so in theory this would be possible. An intermediate array would be a necessary condition for this algorithm to be efficient, and you have two: one for the last iteration (read) and one for the current iteration (write). So the memory requirement would be 15 + 2 x 7.5 = 30 GB, which would not fit on my machine. I guess the read-array could be on disk, but this adds (buffered) I/O and you still need at least 15 + 7.5 = 22.5 GB, leaving less than 1.5 GB for OS, runtime environment, etc. Not sure this would fit either. Or you need to slice the database and work through the slices in a suitable order, just like regular databases.

Anyway, I liked the simplicity of my approach, which also needs less memory (15 GB + node stack, say 100 MB). It doesn't need to scan for positions to process and build them from their index - simply continue with the current node in a flat loop. It is not necessary to keep track of the (max.) depth, this is just a fun fact. Still it would be interesting to know how many iterations your method would take, i.e., what is the minimum depth to reach all positions?


Top
   
PostPosted: Thu Aug 10, 2017 22:46 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1557
jj wrote:
Anyway, I liked the simplicity of my approach, which also needs less memory (15 GB + node stack, say 100 MB). It doesn't need to scan for positions to process and build them from their index - simply continue with the current node in a flat loop. It is not necessary to keep track of the (max.) depth, this is just a fun fact.


IIRC, the Wu-Beal algorithm only required 2 bits per position in memory at any time. It does do a lot of disk swapping, but only sequentially, never randomly. Of course, if you do database generation of "reachability" , you could also slice them by number of pieces, and then it would certainly fit into memory. However, that would complicate the computation of the distances. I like your approach also!

Quote:
Still it would be interesting to know how many iterations your method would take, i.e., what is the minimum depth to reach all positions?


My guess is that it is 1000x smaller than the 400K depth that you find for depth-first search :)


Top
   
PostPosted: Fri Aug 11, 2017 10:53 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 805
Location: FRANCE
BertTuyt wrote:
Herewith a pv I replayd, hope that Gerard can confirm the end result.

22-18 10-14 26-22 11-16 22-17 9-13 18x9 13x22 25x18 6x13 29-25 8-11 24-20 16-19 23x16 12x19 31-26 1-6 25-22 4-8 30-25 8-12 27-24 ...

Bert


Hi Bert,

Damy is now able to prove (in about 15') that the position after 22-18 10-14 26-22 11-16 22-17 9-13 18x9 13x22 25x18 6x13 29-25 is a losing one.
My db seems now to work properly and it remains rooms for improvment and tuning.
For the time being I have built the 11 pieces db.
The 12 pieces db is under building.

_________________
Gérard


Top
   
PostPosted: Fri Aug 11, 2017 12:20 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Gerard, interesting progress.
What is the built time for your DBs.
Think you also compress, not sure you also do a verification step.

Bert


Top
   
PostPosted: Fri Aug 11, 2017 14:18 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
TAILLE wrote:
BertTuyt wrote:
Herewith a pv I replayd, hope that Gerard can confirm the end result.

22-18 10-14 26-22 11-16 22-17 9-13 18x9 13x22 25x18 6x13 29-25 8-11 24-20 16-19 23x16 12x19 31-26 1-6 25-22 4-8 30-25 8-12 27-24 ...

Bert


Hi Bert,

Damy is now able to prove (in about 15') that the position after 22-18 10-14 26-22 11-16 22-17 9-13 18x9 13x22 25x18 6x13 29-25 is a losing one.
My db seems now to work properly and it remains rooms for improvment and tuning.
For the time being I have built the 11 pieces db.
The 12 pieces db is under building.

Gerard, I assume this is seconds (in about 15')

Bert


Top
   
PostPosted: Fri Aug 11, 2017 14:29 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 805
Location: FRANCE
BertTuyt wrote:
Gerard, interesting progress.
What is the built time for your DBs.
Think you also compress, not sure you also do a verification step.

Bert

It's difficult to answer you question concerning time due to the debugging process. In particular the 10 pieces db reveals some bugs due to the number of positions which went above 4G (bugs in the handling of index positions which cannot fit in 32 bits). Now it is fixed.
This morning I generated the 6x6 db (about 3 hours, I do not know if it is a good result ?!).
With this new db it takes now less than 3' to prove the loss after 22-18 10-14 26-22 11-16 22-17 9-13 18x9 13x22 25x18 6x13 29-25.
The verification step has been made up to the 10 pieces db.

_________________
Gérard


Top
   
PostPosted: Fri Aug 11, 2017 15:17 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Gerard, in my case the 6x6 DB (so only this one) took 2029 seconds to generate.

Bert


Top
   
PostPosted: Fri Aug 11, 2017 15:28 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 805
Location: FRANCE
BertTuyt wrote:
Gerard, in my case the 6x6 DB (so only this one) took 2029 seconds to generate.

Bert


Very good indeed.
Could you tell me if you have a multithreads generation ?

_________________
Gérard


Top
   
PostPosted: Fri Aug 11, 2017 15:51 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Gerard, yes it is multithreaded
On my 8 core system I use 16 threads

Bert


Top
   
PostPosted: Fri Aug 11, 2017 16:27 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 805
Location: FRANCE
BertTuyt wrote:
Gerard, yes it is multithreaded
On my 8 core system I use 16 threads

Bert


Oops in this case I am quite happy with my result for two reasons:
1) my generation is currently a monothread generation
2) the compression process needs some time and the decompression takes far more time because when evaluating the successors of a given position I need very often to access the "normal" db (I mean not in the current memory buffer) and I need to do a lot of decompression.

Thank you for your answer Bert

_________________
Gérard


Top
   
PostPosted: Sat Aug 12, 2017 22:18 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 805
Location: FRANCE
TAILLE wrote:
BertTuyt wrote:
Gerard, interesting progress.
What is the built time for your DBs.
Think you also compress, not sure you also do a verification step.

Bert

It's difficult to answer you question concerning time due to the debugging process. In particular the 10 pieces db reveals some bugs due to the number of positions which went above 4G (bugs in the handling of index positions which cannot fit in 32 bits). Now it is fixed.
This morning I generated the 6x6 db (about 3 hours, I do not know if it is a good result ?!).
With this new db it takes now less than 3' to prove the loss after 22-18 10-14 26-22 11-16 22-17 9-13 18x9 13x22 25x18 6x13 29-25.
The verification step has been made up to the 10 pieces db.


Damy has now completed the 12 pieces db and is able to prove the loss (in 17') after 22-18 10-14 26-22 11-16 22-17
In addition Damy is able to make the full analysis of position after 22-18 10-14 26-22 11-16 : in 1h22' Damy proves that 22-17 and 24-19 are the only two winning moves.

7x6 db is under generation.

_________________
Gérard


Top
   
PostPosted: Sun Aug 13, 2017 00:20 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Gerard, hope that Damy can agree with the whole move sequence, so that it is confirmed that white wins.
My holiday ends, so I will have less time in the next months for BT Draughts.

I will at least do a verification step for all DBs, and evaluate if the generate proces can be improved (so faster), as with the current speed it still takes too long to strongly solve 8x8 BT draughts (although from a scalability point of view it would be possible if I have a 5 TByte HD, as the current implementation does not compress).

For really fast analysis of all moves in any position, I guess I most likely need to generate the 15P and 16P DBs (as Rein predicited).

Bert


Top
   
PostPosted: Sun Aug 13, 2017 09:47 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1557
BertTuyt wrote:
Gerard, hope that Damy can agree with the whole move sequence, so that it is confirmed that white wins.
My holiday ends, so I will have less time in the next months for BT Draughts.

I will at least do a verification step for all DBs, and evaluate if the generate proces can be improved (so faster), as with the current speed it still takes too long to strongly solve 8x8 BT draughts (although from a scalability point of view it would be possible if I have a 5 TByte HD, as the current implementation does not compress).

For really fast analysis of all moves in any position, I guess I most likely need to generate the 15P and 16P DBs (as Rein predicited).

Bert


Based on the postings by Fabien and Jan-Jaap, I now suspect the best time investment would be to write a Proof-Number search algorithm for the forward search of your project. Joost's PN search was 100x to 1000x faster than my plain alpha-beta in solving 6x6 draughts.


Last edited by Rein Halbersma on Sun Aug 13, 2017 18:20, edited 1 time in total.

Top
   
PostPosted: Sun Aug 13, 2017 12:24 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 805
Location: FRANCE
BertTuyt wrote:
Gerard, hope that Damy can agree with the whole move sequence, so that it is confirmed that white wins.
My holiday ends, so I will have less time in the next months for BT Draughts.

I will at least do a verification step for all DBs, and evaluate if the generate proces can be improved (so faster), as with the current speed it still takes too long to strongly solve 8x8 BT draughts (although from a scalability point of view it would be possible if I have a 5 TByte HD, as the current implementation does not compress).

For really fast analysis of all moves in any position, I guess I most likely need to generate the 15P and 16P DBs (as Rein predicited).

Bert


The 7x6db is now completed but, as expected, it does not really improve the picture in order to solve the starting position. We all now that the far most time consuming variants are those with balance material between white and black. I made great progress with the 6x6 db but not with the 7x6 db. The decisive db will certainly be the 7x7 db.
If you want to go farther than the 14P db your goal should be to generate the 8x7 db and then immediatly the 8x8db, ignoring 9x6, 10x5 etc db.

Anyway my intention is to complete the 13p pieces db; 8x5 is under generation.

BTW I continue in a monothread configuration because I suspect I will be able to generate the 7x7db BEFORE coding and debugging a multithread generation!

_________________
Gérard


Top
   
PostPosted: Sun Aug 13, 2017 17:08 
Offline

Joined: Sun Sep 13, 2009 23:33
Posts: 116
Real name: Jan-Jaap van Horssen
Location: Zeist, Netherlands
Rein Halbersma wrote:
Based on the postings by Fabien and Joost, I now suspect the best time investment would be to write a Proof-Number search algorithm for the forward search of your project. Joost's PN search was 100x to 1000x faster than my plain alpha-beta in solving 6x6 draughts.

Did Joost also solve 6x6 using PNS or do you mean me? :)
Jan-Jaap


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 183 posts ]  Go to page Previous 1 2 3 4 5 613 Next

All times are UTC+02:00


Who is online

Users browsing this forum: No registered users and 6 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:  
cron
Powered by phpBB® Forum Software © phpBB Limited