Rotor uses Rookie's attack table!

[Jan Brouwer]

So lately I have been refactoring Rotor's source code to reduce the complexity, introduce some classes etc.
I also decided to redesign the attack table, the old one used 32 bits per (occupied) square per color and I wanted something more compact.
After a few design iterations I settled on 16 bits per square per color (also for unoccupied squares):

• 8 bits for the 8 slider attack directions
  2 bits for the number of pawn attacks
  4 bits for the number of knight attacks
  1 bit for the number of king attacks
  (1 bit unused)

So far I have been quite happy with this format.
Yesterday I happened to be reading Marcel Kervinck's thesis on his program Rookie and I discovered that Rookie uses exactly this same format for its attack table!
Just wanted to let you know

[hgm]

I have started building an engine using attack tables too. It is kind of expensive to (differentialy) update them, though. Rather than bitmaps I was thinking in the direction of (doubly) linked lists. That would make it easier to remove the attacks of a piece that is moved or captured from the table.

When do you update the table? In an attempt to make this efficient, i.e. only do it when going to a node that will really search moves, and not for nodes where I will immediately return without further search due to a stand-pat, and thus would have to immediately undo the update without the tble having been used, leads to quite inconventional design. For instance I would be forced to call Eval() before doing the recursive call to search the target node of a move, to figure out if there will be a stand pat, and if not, if there will be any non-futile moves when the replyDepth <= 1. And when replyDepth<=3, I would have to test for the current stm to have non-futile captures in the QS reply to null-move, to decide if it is worth updating the attack table and making the move, or that I might as well take the fail low immediately.

So I get a main loop in my search like:

Code: Select all

While(NextMove()) {
  key = CalculateHashKey();
  if(Repetition(key)) score = 0; else
  if(HashProbe(key) != HASH_CUT) {
    MakeMoveOnBoard();
    cnt = CountMobilityChangeAndPutNewCapturesOnTempStack();
    eval = Evaluate(cnt);
    if(firstVictim = RepliesWillBeSearched(depth, eval, alpha, beta)) {
      UpdateAttackTable(tempStack);
      score = -Search(depth-1, -eval, -beta, -alpha, firstVictim);
      DowndateAttackTable();
    }
    UnMake();
  }
  MiniMaxScore();
}

RepliesWillBeSearched would have to distinguish the cases eval<=alpha and eval>=beta. In the first case it would have to figure out if the current stm has (existing or newly created) non-futile captures when 1 < depth <= 4, for if he hasn't, the opponent's null move will fail high without further search. And if depth <= 1, it can even take the fail low without further ado, anticipting the stand-pat (futility). In the eval >= beta case it could take an immediate beta cutoff if the opponent has no non-futile captures amongst his (existing or newy created) moves.

This kind of upsets the node counting compared to conventional designs, where you would increment the counter at the beginning of Search(), and call Evaluate() from within it, rather than in stead of it.

[Jan Brouwer]

I also try to avoid updating the attack table. At the moment I only use the attack information for generating capture moves in MVV/LVA order
(actually I don't anymore since the refactoring, but I will again). Only when I need the attack information do I update it with the move which
has already been played. In about 50% of the nodes I don't need this information so the attack table is only updated in about 50% of all nodes.
When in the future I want to use attack information in eg the evaluation function, this % will increase, so there is still a barrier to use the attack information.
Perhaps I should just accept the attack-tax, update in all nodes, merge attack update with move execution (there is some potential performance gain there),
and never worry about using attack information or not again.

[hgm]

I have the hope to reduce the effort in attack-table update to even much lower. Not only on a stand pat cutoff, but also when all existing captures are futile. Normally, the existing captures would be extracted from the table, in MVV order (just like you are doing). By extracting them from a table that is not yet updated, I would miss the moves that have become possible because of the previous move, for which I still have to do the update. But this is a move of the opponent, and I am only interested in new moves of my own. So the only new moves can be due to unblocking at the from square.

So in cases where stand-pat fails low, I want to do quick check for unblocking, and figgre out the new capture targets (if any) of the unblocked sliders. The common case is that the moved piece did not unblock anything, so this should be quite cheap. In fact it might be so much cheaper than evaluation, that I would do it even before the latter, to catch moves with pieces pinned on the King.

By first identifying unblocked captures I can defer updating the attack table if there were no non-futile new captures, and then check in the old attack table if there are captures to non-futile victims. If I find one, I would have to do the additional check if the move is still possible (i.e. not with a captured piece, or not blocked in case of a non-capture). Again, the common case is that moves that were possible remain possible, so you would have to do those tests only once, on the first non-futile capture you encounter, to conclude that you have non-futile captures.

Only then you would have to update the attack table, and you could still reap most of the work that has already been done: if you put futile unblocked new captures on a small stack, you could starting to incorporate those in the table. And in the reply node, you would already know what the MVV is, and there would be no need to test higher pieces if you pass on that info.

And when you don't have a capture against any non-futile victim, you can fail low without having touched the attack table, and very few extra work done. That means you would not update the attack table in any end leaf, neither the fail high or the fail low leaves. That would be the bulk of the tree.

[hgm]

Some stats, taken from just a single prosition, so not to be taken too seriously, but just to get a feel:

Code: Select all

10 ply search,:
2536k QS nodes (all d=0 count)
1103k of these were called from another QS node
1152k of these were reached through a capture
 506k of these were reached by a null move
1231k of these had a stand-pat cutoff
 388k of the stand-pat cutoffs was reached through a capture
 832k of the stand-pat cutoffs was reached through a non-capt
  11k of the stand-pat cutoffs was reached through a null move

Some arithmetic: 2536k - 1152k - 506k = 878k were reached through a non-capture. Only in 878k - 832k = 46k cases a QS reached by a non-capture did not have a stand-pat cutoff. In 764k cases a QS reached by a capture did not have a stand-pat cutoff.

So it seems that the cases where the attack table would have to be updated (no stand-pat cutoff) for a large majority (>90%) are reached by captures.

[marcelk]

So lately I have been refactoring Rotor

So far I have been quite happy with this format.
I discovered that Rookie uses exactly this same format for its attack table!
Just wanted to let you know :)

That is good to hear. I have been working on a new Rookie version 3 as well for a couple of months now, I expect to have an online playing version before summer. It is a 100% rewrite from scratch.

The attack tables have survived in their exact form because they are great for SEE and evaluation. There is one new twist in the piece lists: I now keep the knights sorted right after the king, and then all other pieces. When generating captures by scanning the opponent pieces, I found myself knowing that there is a knight, but then having to look around at 8 squares to find its square. That is eliminated with the piece list constraint.

[Jan Brouwer]

I have the hope to reduce the effort in attack-table update to even much lower. Not only on a stand pat cutoff, but also when all existing captures are futile. Normally, the existing captures would be extracted from the table, in MVV order (just like you are doing). By extracting them from a table that is not yet updated, I would miss the moves that have become possible because of the previous move, for which I still have to do the update. But this is a move of the opponent, and I am only interested in new moves of my own. So the only new moves can be due to unblocking at the from square.

So in cases where stand-pat fails low, I want to do quick check for unblocking, and figgre out the new capture targets (if any) of the unblocked sliders. The common case is that the moved piece did not unblock anything, so this should be quite cheap. In fact it might be so much cheaper than evaluation, that I would do it even before the latter, to catch moves with pieces pinned on the King.

By first identifying unblocked captures I can defer updating the attack table if there were no non-futile new captures, and then check in the old attack table if there are captures to non-futile victims. If I find one, I would have to do the additional check if the move is still possible (i.e. not with a captured piece, or not blocked in case of a non-capture). Again, the common case is that moves that were possible remain possible, so you would have to do those tests only once, on the first non-futile capture you encounter, to conclude that you have non-futile captures.

Only then you would have to update the attack table, and you could still reap most of the work that has already been done: if you put futile unblocked new captures on a small stack, you could starting to incorporate those in the table. And in the reply node, you would already know what the MVV is, and there would be no need to test higher pieces if you pass on that info.

And when you don't have a capture against any non-futile victim, you can fail low without having touched the attack table, and very few extra work done. That means you would not update the attack table in any end leaf, neither the fail high or the fail low leaves. That would be the bulk of the tree.

Ouch, it hurts my brain trying to follow this I am now going in the opposite direction of trying to simplify my code.
It will be interesting to see how this works out for you performance-wise. If you manage to increase your NPS significantly
I may have a second look at this. One of the fun aspects of computer chess for me is trying make the thing go faster NPS-wise.

[Jan Brouwer]

Good luck with new Rookie! Did the dynamic piece-square tables survive?

The attack tables have survived in their exact form because they are great for SEE and evaluation. There is one new twist in the piece lists: I now keep the knights sorted right after the king, and then all other pieces. When generating captures by scanning the opponent pieces, I found myself knowing that there is a knight, but then having to look around at 8 squares to find its square. That is eliminated with the piece list constraint.

Nice trick, there are only two piece types for which you count the number of attacks, K and N, and both can start at a fixed location in the piece list.
I use separate move lists for all piece types (something like

Code: Select all

m_square&#91;&#40;type << 4&#41; + i&#93;&#91;color&#93;

) , so this also maps well on the new attack table format.