Most efficient way to generate legal king moves?

[notachessplayer]

.
Instead of a Boolean array, you could use an int array, and write the node count to every square that a slider attacks. Then there is no need to first clear it. I used this technique in my engine CrazyWa to determine the initiative bonus, which is based on the number of attacked squares next to the King of the side that doesn't have the move. So when I generate the moves, I also update this 'attacks board', and immediately afterwards I then examine the squares around the enemy King to determine how many of them were attacked.

Wouldn't you need to still increment/decrement rays when a slider is moved? Or modify the table when a friendly piece moves and doesn't block a slider anymore?
As I understand the idea, which seems like an improvement of mine, you would still need to clear it?

[H.G.Muller]

This is not an incremental technique. When white is to move, CrazyWa generates all white moves from scratch. So blocking and unblocking in previous moves is all accounted for, because these moves have already been performed on the board. I just put one extra statement in the move generator:

Code: Select all

attacksBoard[toSqr] = nodeCount;

where attacksBoard is a global, board-sized array. Immediately after the move generation I then count how many squares around the black King have a value equal to nodeCount in the attacksBoard[]. In fact I count occupied and empty attacked squares separately. These numbers are then used (together with the value of the white pieces in hand) to derive an evaluation bonus for 'initiative', on which the engine tries to stand pat. If the evaluation is below beta, the capturesamongst the generated moves will be searched.

The point is that I don't use a fixed value (like 1 = TRUE) to indicate attacked squares in the attackBoard[], which I would have to clear before I can use it for the next position, in order not to mistake attacks that existed in a previous position for attacks that exist now. By using a value that is different for every position, I can simply test

Code: Select all

if(attacksBoard[toSqr] == nodeCount) ... 

to detect current attacks, and that the values from previous positions are all still there doesn't bother me, as they all have different nodeCount, which is as good as being zero.

[H.G.Muller]

BTW, I am still not convinced that marking attacked squares on a board-size table would be any more difficult than keeping a bitmap of attacked squares in the King neighborhood only (so that it can be byte size).

Code: Select all

unsigned char neighborhood[] = {
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,          0,
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,          0,
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,          0,
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,          0,
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,          0,
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,          0,
  0,  0,  0,  0,  0,  0,128,  2, 64,  0,  0,  0,  0,  0,  0,          0,
  0,  0,  0,  0,  0,  0,  8,  0,  4,  0,  0,  0,  0,  0,  0,          0,
  0,  0,  0,  0,  0,  0, 32,  1, 16,  0,  0,  0,  0,  0,  0,          0,
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,          0,
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,          0,
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,          0,
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,          0,
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,          0,
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,          0,
};

int attacked;

// for marking attacked squares:
    attacked |= neighborhood[toSqr - kingSqr + (7*16+7)]; // instead of attacks[toSqr] = nodeCount;

// when later generating King moves
    if((neighborhood[step + (7*16+7)] & attacked) == 0) { // steps to safe square
      int toSqr = kingSqr + step;
      GenerateOneMove(kingSqr, toSqr);
   }

This method can be more easily combined with checking for contact attacks, because you can indicate all squares attacked by a single leaper in one quantity, rather than spreading them out over different squares of a board array. E.g.:

Code: Select all

int contact_hits[] = {
0, 0, 0, 0,    0,          0,          0,          0,          0,          0,    0, 0, 0, 0, 0,         0,
0, 0, 0, 0,    0,          0,          0,          0,          0,          0,    0, 0, 0, 0, 0,         0,
0, 0, 0, 0,    0,          0,          0,          0,          0,          0,    0, 0, 0, 0, 0,         0,
0, 0, 0, 0,    0,          0,          0,          0,          0,          0,    0, 0, 0, 0, 0,         0,
0, 0, 0, 0,    0,       0x80,       0x02,       0xC0,       0x02,       0x40,    0, 0, 0, 0, 0,         0,
0, 0, 0, 0, 0x80,   0x00800A, 0x80000240, 0x0200C00C, 0x40000280,   0x004006, 0x40, 0, 0, 0, 0,         0,
0, 0, 0, 0, 0x08, 0x80000820, 0x0A000005, 0xC0000C30, 0x06000009, 0x40000410, 0x04, 0, 0, 0, 0,         0,
0, 0, 0, 0, 0xA0, 0x08802003, 0xA0020150,          0, 0x500201A0, 0x04401003, 0x50, 0, 0, 0, 0,         0,
0, 0, 0, 0, 0x08, 0x20080080, 0x09000006, 0x300C00C0, 0x0500000A, 0x10040040, 0x04, 0, 0, 0, 0,         0,
0, 0, 0, 0, 0x20,   0x200009, 0x20010010, 0x0130000C, 0x10010020,   0x100005, 0x10, 0, 0, 0, 0,         0,
0, 0, 0, 0,    0,       0x20,       0x01,       0x30,       0x01,       0x10,    0, 0, 0, 0, 0,         0,
0, 0, 0, 0,    0,          0,          0,          0,          0,          0,    0, 0, 0, 0, 0,         0,
0, 0, 0, 0,    0,          0,          0,          0,          0,          0,    0, 0, 0, 0, 0,         0,
0, 0, 0, 0,    0,          0,          0,          0,          0,          0,    0, 0, 0, 0, 0,         0,
0, 0, 0, 0,    0,          0,          0,          0,          0,          0,    0, 0, 0, 0, 0,         0,
};

int contact_mask[NPIECES];

Init()
{
  contact_mask[WP] = 0xFF00;
  contact_mask[BP] = 0xFF0000;
  contact_mask[N] = 0xFF;
  contact_mask[B] = 0x00FFFF00;
  contact_mask[R] = 0xFF000000;
  contact_mask[Q] = 0xFFFFFF00;
  contact_mask[K] = 0xFFFFFF00;
}

// while running through piece list
  attacked |= contact_hits[vector + (7*16+7)] & contact_mask[piece];

// when generating King moves:
  if((neighborhood[step + (7*16+7)]*0x01010101 & attacked) == 0) {
    ...

The extra multiplication by 0x01010101 is needed to test the biits for all different move types simultaneously, as the attacked squares are split out by move type in 'attacked'.

[notachessplayer]

Ok that is actually a neat little trick, I will try to implement that and give the results.
There is still one problem with it though. You do it during move generation so that you can use it next turn. So you still have to update this table once you move a piece. Say it's a rook, you have to change either the rank or the file. And it might have been in the way of a bishop, so you have to check if it blocked the path of a piece. Still faster, but not as clean as hoped.

As for the king neighborhood technique, did you use/find it yourself? I won't test it because I would have realistically never thought about it, but I'm still curious if it works well.

[H.G.Muller]

No, I do not use it next turn, I use it the same turn. If white is to move, his moves will mark squares around the black King, and this will be used to base the white initiative bonus on (together with the pieces white has in hand). If white is in check the bonus will not help, as he will not be allowed to stand pat while in check, and all evasions will be searched. If white is to move, there is no initiative bonus for black. If you have the initiative, it doesn't matter how safe or unsafe your own King is, as the opponent will be in check all the time and can do nothing to profit from it.

[notachessplayer]

My bad, I was not thinking about giving boni.

I was looking for a way to tell my king which squares are attacked. So, when generating moves for white, I mark each hit square in an array, and use this same array when generating black king moves, to know if I put it in check, but also to know if my castling squares are not attacked.
Here's a new idea:
Since there are max 16 pieces per side, a square can be attacked by only 16 pieces of the same side (impossible, but saves useless calculations). So each ply, the starting mark would be (ply * 17) so no reset is needed. This also allows me to increment a square each time another piece hits the same square and never go passed the ply limit of 17, and easily modify my array after a piece is moved (it still takes 8 directions to verify).
The annoying part is that for every single new hit square, I have to verify:

Code: Select all

if (array[square] == (ply * 17)) {
    array[square]++;
} else {
    array[square] = (ply * 17);
}

This if statement needs to die.

[H.G.Muller]

Note that in an engine you usually do a null move, where you then generate moves for the opponent. An attacks board produced as a side effect of the move generation after null move would be usable to generate King moves in the position before the null move, and vice versa. In QS you would not do any null move, but you would also not need to generate any castling.

Why do you want to count attacks, rather than just record if there is (at least) one? You are just as much in check if you go to / through a square with one attacker as through one with more. It is probably not competitive to try something complex, because clearing the board isnot that expensive. In a 64-bit architecture you can clear 8 bytes in one memory store, so it takes just 8 store operations to clear a board with 64 counters. Even doing a single extra operation each time you want to increment one of the counters may already take longer.

BTW, in CrazyWa I handle castling by always trying it if it is pseudo-legal, but temporarily promote the Rook to a second King. If the move generation in the daughter then captures either King, it aborts the node. If not, the castling was legal, and it changes the extra King back to a Rook. Castlings are not possible for most of the game anyway. This is also one of these issues that can only help perft, and then most likely would just slow down an engine.

[notachessplayer]

True, I didn't think about null moves, as I'm completely obsessed with this move generation atm lol.

Why I wanted to increment/decrement was to be able to update the array when a piece is moved, and not set it to 0 because another piece might be attacking the same square. But it doesn't work anyway.
Instead, during move generation, I tried looping through each enemy piece and set every hit square to the current ply, so that I never have to reset the array. It's slower, though, except when castling moves are possible, in which case it's slightly faster.

By "loop unrolling" manually, as you call it, I went down to 1.25s, but the code is just too ugly and my conscience tells me to not do it.

This king generation depresses me. Your ideas were very helpful, but it seems I always get back to the initial position because of one problem or another. I ended up improving everything but the king generation...

Do you publish your source codes? If so, perhaps you could show me one of your engines that uses a 16x12 representation and legal move generation?

[H.G.Muller]

None of my engines uses legal move generation. Because I want them to be fast, rather than slow. Legal move generation is only useful in the final ply of perft, where you would otherwise get wrong perft counts. But in engines it is just a time waster.

You say you set hit squares to the current ply. But doesn't that leave false markings from sister nodes (which are at the same ply)?

[notachessplayer]

You say you set hit squares to the current ply. But doesn't that leave false markings from sister nodes (which are at the same ply)?

Not if I make my array unique to each ply. It takes some extra memory space but I think it is quite irrelevant with today's machines. Anyway, I gave up with this idea, since it's problematic with null moves.

I fail to see how pseudo-legal is faster? Say your queen is pinned, and has like 20 pseudo-legal moves, but only 5 legal moves. If you keep track of pinned pieces in a legal move generation, you would only generate 5 moves. In pseudo-legal, you generate 20 moves and discard 15 with a costly test. Unless I'm missing something, it is slower?