Kindergarten bitboards and Xiangqi move genaration?

[Han Chengye]

Xiangqi has 10*9 board, so i want to use three uint32_t for its bitboards,like this

struct BitBoard {
uint32_t bb[3];
};

the bits in bb[0] from LSB to MSB represent a1, a2, ..., a10, b1, b2, ..., b10, c1, c2, ...,c10, the highest two bits don't use.
bb[1]--> d1, ..., f10
bb[2]--> g1, ..., i10

i want to use Kindergarten bitbaords for move generation

the key point is that i want not only to precalculate the rook attack table like:

BitBoard RookAttacks[squares][rank or file status],

but precalculate the moves table like this:

Moves RookRankMoves[squares][occ_status][max_moves];

the 1st element of RookRankMoves[][][] is RookRankMoves[][][0], which tell how many postion rook can go along this rank, the rest is the moves itself.

this may avoid a lot of bitscan and bitclear.

sorry for poor english, may someone undertand

any suggestion?

[Dann Corbit]

Might be worth a look to see how these guys did it:
http://sourceforge.net/projects/xqwizard/
http://sourceforge.net/projects/ki11egg/
http://sourceforge.net/projects/xiangqi-engine/
http://sourceforge.net/projects/palmxq/

There used to be a program called ChessV that supported lots of chess variants with large boards but I can no longer find it.

[Gerd Isenberg]

Xiangqi has 10*9 board, so i want to use three uint32_t for its bitboards,like this

struct BitBoard {
uint32_t bb[3];
};

the bits in bb[0] from LSB to MSB represent a1, a2, ..., a10, b1, b2, ..., b10, c1, c2, ...,c10, the highest two bits don't use.
bb[1]--> d1, ..., f10
bb[2]--> g1, ..., i10

i want to use Kindergarten bitbaords for move generation

the key point is that i want not only to precalculate the rook attack table like:

BitBoard RookAttacks[squares][rank or file status],

but precalculate the moves table like this:

Moves RookRankMoves[squares][occ_status][max_moves];

the 1st element of RookRankMoves[][][] is RookRankMoves[][][0], which tell how many postion rook can go along this rank, the rest is the moves itself.

this may avoid a lot of bitscan and bitclear.

sorry for poor english, may someone undertand

any suggestion?

Hashing Multiple Bits along a line to index pre-calculated move lists should work, but of course takes some memory. Since the number of moves per list and lists per square varies a lot I would not use max_moves for each list, but a pointer or index inside a heap with concatenated move lists.

Code: Select all

Moves* RookRankMoves[squares][target_index]; // 90 * 512

target_index = collapsedFilesIndex (moveTargetSetOnRank); // 0..511
Moves* movelist = RookRankMoves[sq][target_index];
moveCopy(destPtr, movelist, movelist->nMoves);

[hgm]

There used to be a program called ChessV that supported lots of chess variants with large boards but I can no longer find it.

ChessV nowadays can be obtained here. I don't know why this is so poorly advertized.

Note that the latest version of ChessV includes a WinBoard-compatible version of it!

I don't think ChessV can play Xiangqi, though. The only native WinBoard Xiangqi engines I am aware of are HoiXiangqi, MaxQi, TJxiangqi, XQWLight, and HaQiKi D.

[liuzy]

Han Cheng Ye, who are you? Where are you come from? Do you know UCCI-UNION?

[Han Chengye]

Code: Select all

Moves* RookRankMoves[squares][target_index]; // 90 * 512

target_index = collapsedFilesIndex (moveTargetSetOnRank); // 0..511
Moves* movelist = RookRankMoves[sq][target_index];
moveCopy(destPtr, movelist, movelist->nMoves);

two problems :
1. what is this: movelist->nMoves? i think Moves is just a uint32_t which including from_to squares.
2. how we get just capture moves?

[hgm]

2. how we get just capture moves?

The problem is that bitboards with a pre-stored move list do not really offer any advantage over a mailbox board representation. Bitboards must earn back their efficiency loss from the more cmplex move making by the fact that you can handle move selection in bulk, by simple AND operations, before extracting. With a pre-calculted move list, you must do the selection move by move.

Running through a list of pre-calcuated moves untill you encounter an invalid code (or until a counter reaches the end count) is in itself not any faster than running over the board until you encounter an obstacle, as the inner loop of a trivial mailbox move generator would do.

[Gerd Isenberg]

Code: Select all

Moves* RookRankMoves[squares][target_index]; // 90 * 512

target_index = collapsedFilesIndex (moveTargetSetOnRank); // 0..511
Moves* movelist = RookRankMoves[sq][target_index];
moveCopy(destPtr, movelist, movelist->nMoves);

two problems :
1. what is this: movelist->nMoves? i think Moves is just a uint32_t which including from_to squares.

Ok, sloppy pseudo code, Moves is something like this

Code: Select all

struct Moves 
{
    uint32_t nMoves;
    uint32_t moves[];
};

alá memcpy:

Code: Select all

moveCopy(destPtr, movelist->moves, movelist->nMoves);

2. how we get just capture moves?

Two options

1. The approach is only for serialization of attack sets which need to be determined with the usual bitboard attack getting approaches and intersected with appropriate target sets, like empty squares or opponent pieces for captures. That is, for movegen you don't pass occupancy but the a target (sub) set of to-squares of moves. One safes the bitscans (which are really cheap nowadays) inside a classical serialization loop.

2. You don't fetch attacksets at all, but (probably as intended by you) immediately movelists from square and occupancy. Then, while generating moves or actually making moves one needs to test whether the attacked square is occupied by own piece - which makes the whole approach questionable compared to a mailbox approach as HGM mentioned. One may even apply two movelists, a "unconditional" for quiet moves, and one for captures, where one needs to test blockers are own or opponent pieces. Unfortunately that introduces additional complexity and captures are the more important and only ones in qsearch - and bitboards are intended to generate them fast.

Considering todays fast bitscans, and to find target squares in the set-wise world, e.g. undefended capture targets for a fast cut-off, the whole approach with precalculated movelists likely doesn´t pay off, also considering the huge amount of resources needed for all the tables.

[hgm]

An alternative approach that might have some merit is use 'rotated indices' rather than bitboards. In Xiangqi you would need only two rotations, as there are no digonal sliders.

In this method you would store the occupance of each file and each rank in a different memory word, and have a board x 2 table to indicate which (rank, file) goes through each square. Because words can hold 32 bits even if you only have a 32-bit CPU, and the largest dimension of the Xiangqi board is only 10, you could use up to 3 bits per square in this representation. But 2 bits is actually enough to encode white occupance and blck occupance separately, in the two 16-bit halves of the word (so that you don't have to shift for alignment, but can simply acces the memory with two-byte displcement).

You can then use the white and black occupancy bits of a rank or file to create an index (by magic multiplication) into a table of pointers to move lists that only contain the possible captures of a Rook or a Cannon along that file or rank.

Note, however, that the situation of move-by-move testing is not as disastrus as I first thought: you could construct the pre-clculated move lists such that all the (pseudo-)captures are sorted in front. Or perhaps even have different lists for non-captures and pseudo-captures. The non-captures will always be pseudo-legal, and you could loop through those without additional testing. And you would not do that at all when you are in QS. The pseudo-captures need testing for the validity of the victim, but they are few in number. The big difference with mailbox is that you cannot get to the captures there before first cycling through all non-captures. The sight disadvntge is tht you woud have to pay attention to occupncy bits you would otherwise ignore (the edge squares), because they could decide if the move is a pseudo-capture or a non-capture. But with kindergarten this might be affordable, even on the larger Xiangqi board.

Nevertheless I still have the impression that mailbox in combination with differentially updated attack lists are very much faster, and are the way to go. Especially in Xiangqi, where bitboards exceed the word length even on 64-bit systems.

[Han Chengye]

An alternative approach that might have some merit is use 'rotated indices' rather than bitboards. In Xiangqi you would need only two rotations, as there are no digonal sliders.

In this method you would store the occupance of each file and each rank in a different memory word, and have a board x 2 table to indicate which (rank, file) goes through each square. Because words can hold 32 bits even if you only have a 32-bit CPU, and the largest dimension of the Xiangqi board is only 10, you could use up to 3 bits per square in this representation. But 2 bits is actually enough to encode white occupance and blck occupance separately, in the two 16-bit halves of the word (so that you don't have to shift for alignment, but can simply acces the memory with two-byte displcement).

You can then use the white and black occupancy bits of a rank or file to create an index (by magic multiplication) into a table of pointers to move lists that only contain the possible captures of a Rook or a Cannon along that file or rank.

Note, however, that the situation of move-by-move testing is not as disastrus as I first thought: you could construct the pre-clculated move lists such that all the (pseudo-)captures are sorted in front. Or perhaps even have different lists for non-captures and pseudo-captures. The non-captures will always be pseudo-legal, and you could loop through those without additional testing. And you would not do that at all when you are in QS. The pseudo-captures need testing for the validity of the victim, but they are few in number. The big difference with mailbox is that you cannot get to the captures there before first cycling through all non-captures. The sight disadvntge is tht you woud have to pay attention to occupncy bits you would otherwise ignore (the edge squares), because they could decide if the move is a pseudo-capture or a non-capture. But with kindergarten this might be affordable, even on the larger Xiangqi board.

i should think it more time

Nevertheless I still have the impression that mailbox in combination with differentially updated attack lists are very much faster, and are the way to go. Especially in Xiangqi, where bitboards exceed the word length even on 64-bit systems.

but this paper www.teu.ac.jp/gamelab/RESEARCH/gpw2006revised.pdf
suggest bitboards may be more faster.