Bitboard techniques in Xiangqi

[hgm]

Xiangqi has a 10x9 board, making conventional bitboards rather inefficient even on 64-bit machines. But in Xiangqi a lot of pieces are confined to a subset of their own half of the board: King and to the 9-square palace, and the Advisers even to 5 squares in that palace (because they are color-bound), while Elephants only have access to 7 squares in total (1 in the palace, 6 outside of it). Unpromoted Paws can only occur on 10 squares, as Pawns promote as soon as they cross the 'river' separating the board halfs. And before that, they stick to their file (even when they capture), and not all files contain Pawns in the opening array.

When I add it all up, this gets to 9 + 5 + 7 + 10 = 31 (piece,square) combinations, which would comfortably fit in a 32-bit integer. This bitmap would fully take care of the positions of 4 piece types! It could be profitably used for selectively generating captures in QS: if a would-be victim is positioned on enemy turf, it could load a 32-bit mask from a (9x10) board table which indicated to which pieces on which squares it would be sensitive. Any matching bit would reveal such an attack possibility. For the King, Advisers and Pawns this would mean an actual attack immediately, for the Elephants a single board square would have to be tested for emptiness . (Xiangqi Elephants do not jump, so their (2,2) leap can be blocked.)

To avoid mis-predictable branches, it would probably be best to list two square numbers for each bit: the toSquare and a square to be tested for emptiness, where you would set the latter to a an off-board dummy square that is kept empty for the King, Advisers and Pawns. Or you could separate out the Elephant bits by ANDing, and extract them in a separate loop doing the emptiness test. How exactly you do this does not have a real impact on performance anyway; the main savings would be that you almost never get a match in the first place, ruling out attack by (possibly) 10 pieces with a single AND operation. The probability that you are actually under attack by any of these pieces is rather small, as they are all very weak pieces.

In fact it turns out that the 5 most-foreward Pawn squares are not really needed: Pawns there cannot attack any square on their own half. When a potential victim is on its own half of the board, it can be attacked by promoted Pawns from the side, and in general the most efficient way to test for Pawn attackers is to check these squares, and the one in front of you, for enemy Pawns in the mailbox board. This procedure would automatically take care of attacks by unpromoted Pawns on the enemy territory too. One of the unused bits in the mask could be used to indicate if the board half of the victim matches your color, and depending on that, you would either do the three-pronged Pawn-attack test or the bitmap test for the confined pieces.

[Matthias Gemuh]

... Xiangqi Elephants do not jump, ...

I think this applies to all elephants. Their ankles would suffer damage.


Matthias.

[Stan Arts]

http://www.youtube.com/watch?v=TK27aknWVI4

Stan

[Greg Strong]

... Xiangqi Elephants do not jump, ...

I think this applies to all elephants. Their ankles would suffer damage.


Matthias.

Actually, Elephants in Shatranj do jump

[Matthias Gemuh]

... Xiangqi Elephants do not jump, ...

I think this applies to all elephants. Their ankles would suffer damage.


Matthias.

Actually, Elephants in Shatranj do jump

I admit I was wrong ! Stan's youtube link offers convincing visual proof .

Matthias.

[Han Chengye]

I try to write a XiangQi engine, and wonder whether bitboard be a good choice or magic bitboard be possible......
or just mailbox?





PS: i'm not a english native speaker

and after a long trying and waiting i can talk here finally

[hgm]

My normal Chess engines are all mailbox, so I am probably biased against bitboard. Rotated bitboards would seem a more obvious choice than magic bitboards, as in Xiangqi there are no diagonal sliders. So you would only need two orientations of the board.

The main disadvantage of mailbox is that it is difficult to selectively generate capture moves. But looping through all possible attackers in the piece list (after having taken care of all the 'confined' pieces through the bitmap technique described above) to determine alignment with the intended victim through a 0x88-like table lookup seems bearable, as there are at most 6 attackers for which you have to do this. (2R, 2C, 2H). If R or C produce an alignment, having to scan the board for obstructions is a pain, but the typical case is that there is no alignment.

[hgm]

I should add that the advantage of generating the captures victim by victim, starting with the most-vallued victim, eliminates the need for move sorting, and indeed the need to generate all captures: if there exists a capture of a high piece that causes a cutoff, it will be amongst the first moves generated, and you don't have to generate captures for the lower victims after the cutoff. On the other hand, in alpha nodes, you can refrain from generating captures of futile victims.

So generating captures in MVV/LVA order through 0x88-like mailbox techniques, and then immediately searching them as they are generated, can actually be quite competative. And you can always refine it by postponing dubious caputures (High x defended Low, or captures with a bad SEE if you use SEE). You could push those on a capture stack, for later examination.

[Han Chengye]

yes,i plan to use mailbox, but your bitmap approach seems attractive.
Just using a word to represent the attack-sets of the king,advisers,pawns and elephants in the half part of board, am i right?

[bob]

I would personally not call them "inefficient" just because they need more than 64 bits. The original chess 4.x used 64 bit values on a 60 bit (CDC) computer. Tom Truscott developed a bitboard version of Duchess in 1977 and used a 32 bit IBM mainframe to do 64 bit operations (there were no 64 bit values on that box either).

Their "data density" makes up for the extra instruction or two needed to deal with longer word sizes...

I suppose one could use newer boxes with 128 bit SSE operations if need be...