generate captures from attack table lazily

[tcusr]

by using a special iterator we could look up all the possible captures in MVV/LVA order without even needing a move list.
the iterator has 2 indexes (mvv, lva) and whenever it is "increased" it will change the indexes until all the possible victim/attacker combinations have been tried.
with a few AND instructions we can extract the bits we are interested in and return a move, hoping to cause a cutoff.
the implementation is not a problem, the only obstacle is that we don't know where the captures are so all combinations are always tried, no real solution to this.
this would work pretty well for QS since there the branching factor is very close to 1.

any considerations?

[hgm]

I used such a design in Spartacus. The idea was that eventually the captures on each victim would be obtained from an incrementally updated set of attackers. But in an early stage I used a conventional 0x88 attack test running through the piece list in LVA order, and even that was surprisingly fast. Because so often you cut off on the first capture of the first victim, and never have to do anything else.

Main difficulty is that to get true MVV/LVA you cannot work purely by victim, but still have to merge attacks on the two Rooks or on the four minors. E.g. there could be BxR on the first Rook you examine, but PxR on the second rook. And you should search the latter first.

In the Mailbox Trials I solved this by having attackers sets that only used one of every four bits. So that attackers sets of different pieces could be merged by shifting and adding, before extracting the attackers of the merged 'vaue group' in LVA order.

If you want speed, I think this is the way to go.

[tcusr]

Main difficulty is that to get true MVV/LVA you cannot work purely by victim, but still have to merge attacks on the two Rooks or on the four minors. E.g. there could be BxR on the first Rook you examine, but PxR on the second rook. And you should search the latter first.

that is if you use only one loop. the iterator would contain all possible captures in pairs in the correct order.

pawn -> queen
pawn -> rook
....
queen-> knight
queen ->pawn

but in the worst case it has to loop 30 times. did you exclude this a priori in your early testings?

In the Mailbox Trials I solved this by having attackers sets that only used one of every four bits. So that attackers sets of different pieces could be merged by shifting and adding, before extracting the attackers of the merged 'vaue group' in LVA order.

how does that work? the attack table information could be converted into another kind of map that would solve all of this.

[Ras]

that is if you use only one loop. the iterator would contain all possible captures in pairs in the correct order.

pawn -> queen
pawn -> rook

That's not MVV/LVA, but LVA/MVV.

[tcusr]

that is if you use only one loop. the iterator would contain all possible captures in pairs in the correct order.

pawn -> queen
pawn -> rook

That's not MVV/LVA, but LVA/MVV.

yeah that's right, i got really confused. i meant pair of victim/attackers like these:
(queen, pawn) (queen, knight)....(pawn, queen)

[hgm]

that is if you use only one loop. the iterator would contain all possible captures in pairs in the correct order.

pawn -> queen
pawn -> rook
....
queen-> knight
queen ->pawn

but in the worst case it has to loop 30 times. did you exclude this a priori in your early testings?

In Spartacus I did not use a single loop, but nested loops. The outer loop rust over the value groups (queens, rooks, minors, pawns). Inside of that there is a loop over pieces inside the value group, and the inner loop finds the attackers in LVA order. But I still had to store all captures on a value group in a list, and sort that list at the end of the outer loop to search them.

To avoid that sorting by attacker one can save the captures on a given victim in an 'attackers set': a word where each of 16 bits correspond to an attacker. Ordered in such a way that they would extract in order of ascending value. E.g. bit 0 (the LSB) corresponds to pawn 1, bit 4 to pawn 2, bit 8 to pawn 3, ..., bit 32 to knight 1, ... etc. The bit is set to 1 if the corresponding attacker attacks the given victim. If that victim is the only piece in the value group, you just extract the attackers from its attackers set to get the captures on it in LVA order. If there are multiple pieces in the value group, (e.g. 4 minors) you merge their attackers sets as set[B1] + 2*set[B2] + 4*set[N1] + 8*set[N2], and extracts the bits from there.

how does that work? the attack table information could be converted into another kind of map that would solve all of this.

The code was published here: forum3/viewtopic.php?f=7&t=76773 .

[tcusr]

In Spartacus I did not use a single loop, but nested loops. The outer loop rust over the value groups (queens, rooks, minors, pawns). Inside of that there is a loop over pieces inside the value group, and the inner loop finds the attackers in LVA order. But I still had to store all captures on a value group in a list, and sort that list at the end of the outer loop to search them.

ok i misunderstood that, the iterator does just that in a more fancy way.

thanks for the thread.