GetSmallestAttacker() in 16x12 board representation

[metax]

I'd like to implement SEE in my chess engine, but I have a 16x12 board representation, so no bitboards. Therefore my GetSmallestAttacker() function is rather slow as I have to look in every direction from the square to find possible attackers. Does anyone have an idea for a faster GetSmallestAttacker function (I'm going to test if the loss in nodes searched compensates for the lower NPS with my current function though)?

[Teemu Pudas]

Piece lists.

[hgm]

To elaborate a bit on Teemu's answer:

For efficiency in mailbox representations it is essential to maintain not only a board, but also a piece list, which tabulates for each piece on what square it is (and holds some invalid square number like -1 when the piece is captured). This takes a bit of extra time for updating on MakeMove and UnMake, but you easily earn that back already in the move generator, because you don't have to scan the board to find your pieces, but can simply run through the piece list.

If you arrange the piece list such that the pieces are ordered by value, you can run through it low to high to make a quick test if the piece might attack a given square for SEE. For Pawns it is still quicker to look on the board, because there are only 2 squares where a Pawn attack can come from, while the piece list might hold 8 Pawns. So you only run through the piece part of your piece list, low to high. That way you will automatically find the LVA capture first.

[JVMerlino]

To elaborate a bit on Teemu's answer:

For efficiency in mailbox representations it is essential to maintain not only a board, but also a piece list, which tabulates for each piece on what square it is (and holds some invalid square number like -1 when the piece is captured). This takes a bit of extra time for updating on MakeMove and UnMake, but you easily earn that back already in the move generator, because you don't have to scan the board to find your pieces, but can simply run through the piece list.

If you arrange the piece list such that the pieces are ordered by value, you can run through it low to high to make a quick test if the piece might attack a given square for SEE. For Pawns it is still quicker to look on the board, because there are only 2 squares where a Pawn attack can come from, while the piece list might hold 8 Pawns. So you only run through the piece part of your piece list, low to high. That way you will automatically find the LVA capture first.

I want to add SEE to Myrddin as well, and I'm having the same problem trying to work out a good way to do it as Myrddin also uses a mailbox system (16x8). On top of the piece list that you suggest, would keeping updated attack tables be more or less efficient than just using the piece list?

Thanks!

jm

[hgm]

Keeping attack tables up to date is usually very expensive compared to updating board + piece list. It will critically depend on if you can be smart in choosing the moment of update, (I.e. avoid update in nodes where you would not or hardly use the information, such as stand pat and immediate restore), and if you can use the data in the attack table to make the update itself more efficient. Up to now I never could make it competative, but I have designed a very promising new way to do it. But I must still try it out...