World Draughts Forum

It is currently Sat Nov 25, 2017 02:46

All times are UTC+01:00




Post new topic  Reply to topic  [ 9 posts ] 
Author Message
PostPosted: Wed May 08, 2013 01:02 
Offline

Joined: Wed May 08, 2013 00:56
Posts: 4
Real name: Marc Cornet
I don't know if this is already known, but I found that using this bit layout has some nice properties.

Code:
      49      36      23      10      61
   48      35      22      9      60   
      34      21      8      59      46
   33      20      7      58      45   
      19      6      57      44      31
   18      5      56      43      30   
      4      55      42      29      16
   3      54      41      28      15   
      53      40      27      14      1
   52      39      26      13      0   


With 64 bit, it is always rotate 1 or rotate 14 bits.

Furthermore, all the unused bits lay arround the board

Code:
      63      50      37      24      11      62
   62      49      36      23      10      61   
      48      35      22      9      60      47
   47      34      21      8      59      46   
      33      20      7      58      45      32
   32      19      6      57      44      31   
      18      5      56      43      30      17
   17      4      55      42      29      16   
      3      54      41      28      15      2
   2      53      40      27      14      1   
      52      39      26      13      0      51
   51      38      25      12      63      50   


So shifting up right is now possible from every row as it wont overflow to the next row.


Top
   
PostPosted: Wed May 08, 2013 09:34 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1559
Pemrograman wrote:
I don't know if this is already known, but I found that using this bit layout has some nice properties.

Code:
      49      36      23      10      61
   48      35      22      9      60   
      34      21      8      59      46
   33      20      7      58      45   
      19      6      57      44      31
   18      5      56      43      30   
      4      55      42      29      16
   3      54      41      28      15   
      53      40      27      14      1
   52      39      26      13      0   


With 64 bit, it is always rotate 1 or rotate 14 bits.

Furthermore, all the unused bits lay arround the board

Code:
      63      50      37      24      11      62
   62      49      36      23      10      61   
      48      35      22      9      60      47
   47      34      21      8      59      46   
      33      20      7      58      45      32
   32      19      6      57      44      31   
      18      5      56      43      30      17
   17      4      55      42      29      16   
      3      54      41      28      15      2
   2      53      40      27      14      1   
      52      39      26      13      0      51
   51      38      25      12      63      50   


So shifting up right is now possible from every row as it wont overflow to the next row.


Very interesting! It reminds me of http://www.3dkingdoms.com/checkers/bitboards.htm#A1
We have been discussing bitboards for quite a bit on this forum, see. e.g. http://www.laatste.info/bb3/viewtopic.p ... &start=180, but your design never came up.
The overflow property is nice to have, because it means that you can always shift back after you slide of the board. However, the rotate instruction is a bit more expensive than the shift instruction, or do you have access to machines with native rotate instructions?
Are you the author of an international draughts engine by any chance?


Top
   
PostPosted: Wed May 08, 2013 11:39 
Offline

Joined: Wed May 08, 2013 00:56
Posts: 4
Real name: Marc Cornet
This design was inspired by that bitboard tutorial. In a spreadsheet I tried different values for left and right rotating, and found that 1 and 14 worked very nice. I had not read about the ghost square bitboard, and I probably would not have tried this approach if I had known about it. I'm not completely sure if this design offers any advantage? Also, the mscv compiler listed the rotr as an intrinsic and the tutorial mentioned that rotating was nice, so I never even though about a possible speed penalty. It sure is better dan odd and even row, left and right control flow statements.

ALso, after writing just 1000 sloc and not even implementing the king moves, I would not call myself an author of any program just yet. After writing a simple connect-four engine I wanted to experiment with more alpha beta search enhancements. Chess would probably deny me any creativity in designing a move generator. Most of the generators use magic bitboards, but that would just lead to blindly copying what others invented.

So dammen seemed a good alternative to start experimenting on. I thought I could mannage to come up with a acceptable move generator on my own. A bit stuck on a nice king move generator though.

TLDR: I would like to try and build an checkers engine and in the process I found this bitboard representation because I did not know of the ghost squares but did find this alternative.

Ow, and I dont even play checkers. (I had to google for the registration anwer. :) )


Top
   
PostPosted: Wed May 08, 2013 12:28 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1559
Pemrograman wrote:
This design was inspired by that bitboard tutorial. In a spreadsheet I tried different values for left and right rotating, and found that 1 and 14 worked very nice. I had not read about the ghost square bitboard, and I probably would not have tried this approach if I had known about it. I'm not completely sure if this design offers any advantage? Also, the mscv compiler listed the rotr as an intrinsic and the tutorial mentioned that rotating was nice, so I never even though about a possible speed penalty. It sure is better dan odd and even row, left and right control flow statements.

ALso, after writing just 1000 sloc and not even implementing the king moves, I would not call myself an author of any program just yet. After writing a simple connect-four engine I wanted to experiment with more alpha beta search enhancements. Chess would probably deny me any creativity in designing a move generator. Most of the generators use magic bitboards, but that would just lead to blindly copying what others invented.

So dammen seemed a good alternative to start experimenting on. I thought I could mannage to come up with a acceptable move generator on my own. A bit stuck on a nice king move generator though.

TLDR: I would like to try and build an checkers engine and in the process I found this bitboard representation because I did not know of the ghost squares but did find this alternative.

Ow, and I dont even play checkers. (I had to google for the registration anwer. :) )


The "ghost" squares that most people here use also eliminate the Left/Rigth special code, as well as edge-detection. As I said, your complete extra ghost "ring" also around the bottom and top of the board is very nice. I remember that I had once a bug in my capture generation where after landing after the final piece I let it slide until it dropped of the board, and then tried to slide it backwards to find the destination square. With your layout that would actually work.

Now that I think of it, "our" ghost layout here is using the board as a cylinder, so that you can share the ghost column on the left and right edge, whereas your layout uses the board as a torus so that also the bottom and top edges are connected.

Well you certainly made one orginal contribution already! Once you finish the move generator, also make sure to verify it with perft() counts. There are a large number of threads on this topic here, both for correctness and for speed comparisons.


Top
   
PostPosted: Wed May 08, 2013 14:37 
Offline

Joined: Wed May 08, 2013 00:56
Posts: 4
Real name: Marc Cornet
But if you offset the cylinder with a row of ghosts, wouldn't that lead to a donut with wrangled seams and achieving the same goal? It would require the rotate instruction though.

Code:

[57][58][59][60][61][62]
[63]  00, 01, 02, 03, 04,
    05, 06, 07, 08, 09, [10]
[10]  11, 12, 13, 14, 15,
    16, 17, 18, 19, 20, [21]
[21]  22, 23, 24, 25, 26,
    27, 28, 29, 30, 31, [32]
[32]  33, 34, 35, 36, 37,
    38, 39, 40, 41, 42, [43]
[43]  44, 45, 46, 47, 48,
    49, 50, 51, 52, 53, [54]
[55][56][57][58][59][60]



I shift my empty squares towards my targets however, so that I don't need to calculate the from position.


Top
   
PostPosted: Thu May 09, 2013 00:30 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1559
Pemrograman wrote:
But if you offset the cylinder with a row of ghosts, wouldn't that lead to a donut with wrangled seams and achieving the same goal? It would require the rotate instruction though.

Code:

[57][58][59][60][61][62]
[63]  00, 01, 02, 03, 04,
    05, 06, 07, 08, 09, [10]
[10]  11, 12, 13, 14, 15,
    16, 17, 18, 19, 20, [21]
[21]  22, 23, 24, 25, 26,
    27, 28, 29, 30, 31, [32]
[32]  33, 34, 35, 36, 37,
    38, 39, 40, 41, 42, [43]
[43]  44, 45, 46, 47, 48,
    49, 50, 51, 52, 53, [54]
[55][56][57][58][59][60]



I shift my empty squares towards my targets however, so that I don't need to calculate the from position.


We never thought of bitwise rotate, only bitwise shift, and then 64 bits are not enough to wrap all 4 edges :(
Main reason why bitwise rotate is not so much used is that C++ does not have a builtin operator for it. Do you perhaps program in Java?


Top
   
PostPosted: Thu May 09, 2013 12:45 
Offline

Joined: Wed May 08, 2013 00:56
Posts: 4
Real name: Marc Cornet
Rein Halbersma wrote:

[...]

We never thought of bitwise rotate, only bitwise shift, and then 64 bits are not enough to wrap all 4 edges :(
Main reason why bitwise rotate is not so much used is that C++ does not have a builtin operator for it. Do you perhaps program in Java?


C++, I use the vs2012 compiler intrinsics for those functions. I believed it to be already common practice for bitscan and popcount, so I also use it to rotate.


Top
   
PostPosted: Fri May 10, 2013 19:34 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 806
Location: FRANCE
Pemrograman wrote:
Code:
      49      36      23      10      61
   48      35      22      9      60   
      34      21      8      59      46
   33      20      7      58      45   
      19      6      57      44      31
   18      5      56      43      30   
      4      55      42      29      16
   3      54      41      28      15   
      53      40      27      14      1
   52      39      26      13      0   




Hi,
This coding is interesting for a move generator, but I can see some difficulties for the egdb generation: do you have a "magic" function in order to find the most advanced man (for white and for black) ?

_________________
Gérard


Top
   
PostPosted: Sat Jul 29, 2017 15:35 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1559
Pemrograman wrote:
But if you offset the cylinder with a row of ghosts, wouldn't that lead to a donut with wrangled seams and achieving the same goal? It would require the rotate instruction though.

Code:

   [58][59][60][61][62][63]
 [63] 00, 01, 02, 03, 04,
    05, 06, 07, 08, 09,[10]
 [10] 11, 12, 13, 14, 15,
    16, 17, 18, 19, 20,[21]
 [21] 22, 23, 24, 25, 26,
    27, 28, 29, 30, 31,[32]
 [32] 33, 34, 35, 36, 37,
    38, 39, 40, 41, 42,[43]
 [43] 44, 45, 46, 47, 48,
    49, 50, 51, 52, 53,[54]
 [54][55][56][57][58][59]



I shift my empty squares towards my targets however, so that I don't need to calculate the from position.


Small correction in square numbers for future reference.


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 9 posts ] 

All times are UTC+01:00


Who is online

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