DarkThought sorts MVV/LVA without looking at any moves?

[rob]

Here's a concrete example:

FEN: 4k3/1q6/P2q4/4B3/8/8/8/1R2K3 w - - 0 1

Code: Select all

Chessboard:
8         k       
7   q             
6 P     q         
5         B       
4                 
3                 
2                 
1   R     K       
  a b c d e f g h

Black has two queens, one on b7 and one on d6. If I start my incremental capture generation with black's queens (MVV), I either generate one of two capture sequences for black's queen on b7:

Sequence 1:
a6xb7 Wpawn captures BQueen
b1xb7 WRook captures BQueen

Or,

Sequence 2:
b1xb7 WRook captures BQueen
a6xb7 WPawn captures BQueen

Either way, if I next generate the capture of black's second queen on d6, I violate the LVA sorting requirement.

This example fails identically (violates the LVA sorting requirement) if I generate the capture of black's second queen on d6 first before next generating the two captures of black's queen on b7.

Yet, Heinz states that he has solved this problem and sorts *both* MVV and LVA without generating a list of moves in advance. Further, he states that virtually all performant chess engines in the world use the well-known method of solving this problem.

I just can't see any way that the concrete example above could be solved through incremental generation of captures proceeding one piece at a time. I can see that it can be solved if, for example, all queen captures were placed in a list and the list was subsequently sorted. But that would be making a list, which Heinz says is not necessary.

I'm very surprised by this statement.

Rob

[hgm]

The point is that you should invert the nesting of the loop over victims within the victim group and over attackers. So when you get to the Queen victim group, containing Q1 and Q2, you first start trying PxQ1, PxQ2 before trying BxQ1, BxQ2 and then RxQ1, RxQ2.

The O(n^2) is not really a problem, as n is small. You would have to compare it to something like 4*n, (n pieces that have 4 potential captures each), while n~8 on a full board and goes down during the game. So the pre-factor can easily compensate the number of executions.

The 0x88 alignment tests are pretty cheap. When you do mailbox generation, you would have to do a ray scan for each of the directions a slider moves in, before you know what is at the end of it, and if that gives you a capture. (Or test the target square for each of the 8 steps a Knight or King can make.) With 0x88 testing you test alignment first, and only in the rare case there is alignment you would need to do the ray scan. On average that is much cheaper.

[Aleks Peshkov]

DarkThought had incrementally precomputed bitboards of all pieces attacking a given square. It is trivial to get MVV/LVV without sorting with such attack table.

[Henk]

DarkThought had incrementally precomputed bitboards of all pieces attacking a given square. It is trivial to get MVV/LVV without sorting with such attack table.

When pieces are changing with each move on the squares between victim and attacker how can it be pre computed.

[hgm]

Incrementally!

That means that for each move that blocks or unblocks the attack, you would update the affected bitboards in MakeMove().