Opinions requested for new move gen idea

[Michael Sherwin]

What I want to do does not require a bitboard engine. I just need speed so this board[64] approach is what I have come up with.

IN PSEUDO CODE

Code: Select all

constexpr auto u32 = unsigned __int32;

typedef struct {
    u32    nxtTs;
    u32    nxtDr;
    u32    ts;
} tss;

u32 idxB[64] = { 0, 7, 14};

tss toSq[] = {
  { 1,  0,  9},
  { 2,  0, 18},
  { 3,  0, 27},
  { 4,  0, 36},
  { 5,  0, 45},
  { 6,  0, 54},
  { 0,  0, 63},
  { 8, 13, 10},
  { 9, 13, 19},
  {10, 13, 28},
  {11, 13, 37},
  {12, 13, 46},
  {13, 13, 55},
  { 0,  0,  8},
}

case bishop:
  i = idxB[fs]; // fs = 1, i = 7
  do {
    ts = toSq[i].ts;
    type = action[board[ts]].type;
    switch (type) {
      case EMPTY:
        AddMove(fs, ts);
        i = toSq[i].nxtTs;
        break;
      case ENEMY:
        AddCapture(fs, ts);
        i = toSq[i].nxtDr;
        break;
      case FRIEND:
        i = toSq[i].nxtDr;
        break;
    }
  } while (i);

Assuming the fs is b1 = 1 then the data to generate bishop moves starts at index 7. After that the code is simple enough to understand. My questions are will this approach be fast and what is the simplest way to initialize the data structure? The advantages would seem to be no edge test needed and one loop instead of two.

Thanks in advance!

[hgm]

Isn't this how GNU Chess 4 did it? Effectively for each from-square and piece type you have a binary tree of to-squares, one branch for when the square was empty, the other for when the square was occupied. For leapers both branches are the same, for sliders the 'empty' branch might continue (if it hasn't hit the board edge yet).

Avoid the switch on piece type; instead if idxB[], idxN[] etc, just take a single 2d array idx[type][].

I am not sure whether with modern CPUs this approach is still competitive. You save some time on never having to test off-board squares. (For which you would have to extend the square number range with invalid 'rim squares', and either throw a 0x88-type test on the square number directly, or occupy those with 'boundary guards' that always test as 'friends'. These tests would be pretty cheap.) But the toSqr table will be several kB, as the trees cannot be merged. (Even coinciding rays would have different continuation when blocked.) So it would cause a lot of level-1 cache pressure, which might offset the advantage of fewer instructions.

[Michael Sherwin]

Isn't this how GNU Chess 4 did it? Effectively for each from-square and piece type you have a binary tree of to-squares, one branch for when the square was empty, the other for when the square was occupied. For leapers both branches are the same, for sliders the 'empty' branch might continue (if it hasn't hit the board edge yet).

Avoid the switch on piece type; instead if idxB[], idxN[] etc, just take a single 2d array idx[type][].

Thanks for the optimization! GNU chess 4 and below did it a little different. It would look up the next ts in one of two 64 element arrays like newTs = arrayNxtTs[ts] or arrayNxtDir[ts]. The data arrays were quite large with tons of unused elements. The method in this post compresses the data to use less space.

[Hrvoje Horvatic]

(1) This is "classical" table-based move generation, you might check chessprogramming wiki for more information... HGM correctly notices that this approach was implemented in GnuChess (version 5 was bitboard-based, so you have to look for version 4).

there are different ways of organizing data inside tables. I tried a few and it doesn't matter too much speed-wise...

(2) yes, it's fast, somewhat faster than bitboard-based approach, but only for move generation, and not as fast as you might hope... you still need other methods for other problems, like testing whether king is in check, etc.

(3) you initialize table by putting piece on a square on an empty board and enumerate all available squares for that piece... you can use bitboard attacks for that, or any other method... a few years ago Diepeveen posted a code which uses 10x12 board (actually 12x12 board) with guard squares around central 8x8 board, also an ancient trick to detect board edge... there is no problem in using 16x8 board for initialization also...

In general, you can squeeze out a few more cycles, but it's not worth the effort... unless you are looking for a new adventure in coding, in which case I can recommend it wholeheartedly...

[Michael Sherwin]

(1) This is "classical" table-based move generation, you might check chessprogramming wiki for more information... HGM correctly notices that this approach was implemented in GnuChess (version 5 was bitboard-based, so you have to look for version 4).

there are different ways of organizing data inside tables. I tried a few and it doesn't matter too much speed-wise...

(2) yes, it's fast, somewhat faster than bitboard-based approach, but only for move generation, and not as fast as you might hope... you still need other methods for other problems, like testing whether king is in check, etc.

(3) you initialize table by putting piece on a square on an empty board and enumerate all available squares for that piece... you can use bitboard attacks for that, or any other method... a few years ago Diepeveen posted a code which uses 10x12 board (actually 12x12 board) with guard squares around central 8x8 board, also an ancient trick to detect board edge... there is no problem in using 16x8 board for initialization also...

In general, you can squeeze out a few more cycles, but it's not worth the effort... unless you are looking for a new adventure in coding, in which case I can recommend it wholeheartedly...

Thanks! I just want something simple and very fast for an experiment. About 15/16 years ago I did write a 1600 elo engine named Carnivor that used the GNU chess 4 move generator, much improved though. Here is a snippet.

case BISHOP:
sbns=bns+bol[fs];
sbnd=bnd+bol[fs];
ts=*(sbns+fs);
while(ts<64)
{
switch(wtrgt[brd[ts]])
{
case VACANT:
link(MOVE);
ts=*(sbns+ts);
continue;
case FRIEND:
ts=*(sbnd+ts);
continue;
case ENEMY:
link(CAPTURE);
ts=*(sbnd+ts);
continue;
default:
return FALSE;
}
}
continue;

I also wrote a move generator in assembly in pure jump table style.

wmg: push ebp
push edi
push esi
mov ebp,[ply]
mov eax,[first+ebp*4]
mov [lis+ebp*4],eax
mov edi,[nxt]
jmp [ptmf+edi*4]

wnxtm: mov edi,[nxt+edi*4]
jmp [ptmf+edi*4]

wqm: mov ecx,[ps+edi*4]
mov esi,[qol+ecx*4]
movsx ebx,[qns+esi+ecx]
mov edx,[brd+ebx*4]
jmp [wqmf+edx*4]

wqmrm: mov [tree.fsq+eax*8],cl
mov [tree.tsq+eax*8],bl
mov [tree.typ+eax*8],QMOV
inc eax
movsx ebx,[qns+esi+ebx]
mov edx,[brd+ebx*4]
jmp [wqmf+edx*4]

wqmrc: mov [tree.fsq+eax*8],cl
mov [tree.tsq+eax*8],dl
mov [tree.typ+eax*8],QCAP
inc eax
wqmnd: movsx ebx,[qnd+esi+ebx]
mov edx,[brd+ebx*4]
jmp [wqmf+edx*4]

Stockfish x64 popcount single thread bench 6 as reference on my system.
2,004,571 nodes per second

Carnivor bench 6
41,270,402 nodes per second

Godzilla (in assembly) bench 6
75,604,183 nodes per second

I can get Godzilla to compile using Visual Studio 17 but it crashes after a few milliseconds and I can't find the error or i'd use it. It is way to huge an endeavor to rewrite and I am not happy with the large data of GNU chess 4. So I thought i'd try this modification.

[xr_a_y]

Are you sure you are comparing something comparable here ? Be sure not to compare search benchmark with perft or even worst with pseudo perft.

[Michael Sherwin]

Are you sure you are comparing something comparable here ? Be sure not to compare search benchmark with perft or even worst with pseudo perft.

SF bench 6 was just for a scaling reference. If my system runs SF bench 6 at 2M nodes per second and someone else's system runs SF bench 6 at 4M nodes per second then they can know how fast my bench 6 would run on their system. Also I should mention that my bench 6 makes and unmakes all moves generated and does not do any kind of bulk counting by look up.

EDIT: In Godzilla only the move generator is in assembler and all other code is in C. Here are the bench functions.

Code: Select all

void wbench(int depth)
{
  if(!wmg())return;
  while(movew())
  {
	if(depth > 1)
	  bbench(depth-1);
    unmvw();
    z++;
  }
}

void bbench(int depth)
{
   if(!bmg())return;
   while(moveb())
   {
	 if(depth > 1)
      wbench(depth-1);
     unmvb();
     z++;
   }
}