And something completely different, that might be a bit off topic at this stage: I just managed to finish a move generator for Janggi (Korean Chess). This is very similar to Xiangqi, in the sense that there is also location-dependent moving. The King and Advisors are also confined to the Palace area. Not the Elephants, though, which are 'elongated' versions of the Horse in Janggi (doing one more diagonal step, so they can be blocked on two squares). And Rooks and Cannons have extra diagonal moves inside the Palace. But the underlying principles are the same, and the move generator I came up with would also work very well for Xiangqi, with only some small modifications. And it actually is quite simple:
Unlike the micro-Max and KingSlayer move generators it supposes a piece list (location[]), which keeps track of where each piece of a given player is. So that it doesn't need to scan the board in the outermost loop to find the pieces, but can scan through the (much smaller) piece list. But that is just a subtle detail.
To allow for the location-dependence of the moves, it tabulates the start of the move list not just by piece type, but also by square. This has an additional advantage that the move lists can omit moves in directions that would immediately fall off board. Which prevents a lot of time wastage. Slider moves will of course eventually fall off board, so there still has to be a rim of 'edge guards' around the board to stop them there.
The moves can also have a location dependency of their range: Rooks and Cannons can move diagonally inside the Palace, but then they cannot leave it, and must stop at the Palace boundary. So for them the range is tabulated squarewise too. All other pieces are leapers (albeit 'lame' leapers), and their range will be set to 1.
After retrieval of a move step and range for a certain direction, three piece types need special treatment: a Cannon would first have to find a piece to jump over. (In Janggi Cannons must always jump, also for non-captures. And they cannot jump each other!) If this is found, without completely exhausting the range, move generation continues from there as if it was a Rook. Horses and Elephants need to test whether the move (which is guaranteed to end on the board) are blocked. Which square(s) they can be blocked is looked up in a table indexed by the step they make to their final destination.
If these tests are successfully passed, there is the normal loop over distances, the number of iterations controlled by the range variable r. Of course an obstacle in the path would break out of the loop earlier. Generated moves are put in the moveStack[] array; depending on whether they are captures or non-captures at the beginning or end of the list. (That saves a lot of time on move sorting later.)
Code: Select all
unsigned char moveLists[] = { // start of move list in steps[], per square
// white King, Advisor, Pawn black King, Advisor, Pawn
0, 0, 0, 28, 6, 34, 0, 0, 0, 42, 13, 13, 13, 13, 13, 13, 13, 48,
0, 0, 0, 17, 1, 22, 0, 0, 0, 41, 12, 12, 12, 10, 12, 12, 12, 47,
0, 0, 0, 40, 12, 46, 0, 0, 0, 41, 12, 12, 39, 12, 45, 12, 12, 47,
29, 6, 6, 6, 6, 6, 6, 6, 35, 41, 12, 12, 12, 12, 12, 12, 12, 47,
29, 6, 6, 6, 6, 6, 6, 6, 35, 41, 12, 12, 12, 12, 12, 12, 12, 47,
29, 6, 6, 6, 6, 6, 6, 6, 35, 41, 12, 12, 12, 12, 12, 12, 12, 47,
29, 6, 6, 6, 6, 6, 6, 6, 35, 41, 12, 12, 12, 12, 12, 12, 12, 47,
29, 6, 6, 27, 6, 33, 6, 6, 35, 0, 0, 0, 28, 6, 34, 0, 0, 0,
29, 6, 6, 6, 4, 6, 6, 6, 35, 0, 0, 0, 17, 1, 22, 0, 0, 0,
30, 7, 7, 7, 7, 7, 7, 7, 36, 0, 0, 0, 40, 12, 46, 0, 0, 0,
// Horse Elephant
63, 62, 61, 61, 61, 61, 61, 86, 56, 113,113,112,111,111,111,136,106,106,
91, 90, 59, 59, 59, 59, 59, 85, 55, 113,113,112,111,111,111,136,106,106,
68, 66, 50, 50, 50, 50, 50, 52, 54, 141,141,140,149,149,149,135,105,105,
68, 66, 50, 50, 50, 50, 50, 52, 54, 118,118,116,100,100,100,102,104,104,
68, 66, 50, 50, 50, 50, 50, 52, 54, 118,118,116,100,100,100,102,104,104,
68, 66, 50, 50, 50, 50, 50, 52, 54, 118,118,116,100,100,100,102,104,104,
68, 66, 50, 50, 50, 50, 50, 52, 54, 118,118,116,100,100,100,102,104,104,
68, 66, 50, 50, 50, 50, 50, 52, 54, 119,119,145,123,123,123,130,131,131,
69, 95, 73, 73, 73, 73, 73, 80, 81, 120,120,146,125,125,125,126,127,127,
70, 96, 75, 75, 75, 75, 75, 76, 77, 120,120,146,125,125,125,126,127,127,
// Rook Cannon
29, 6, 6, 27, 6, 33, 6, 6, 35, 29, 29, 6, 27, 6, 33, 6, 35, 35,
17, 16, 16, 16, 1, 16, 16, 16, 22, 29, 29, 6, 6, 6, 6, 6, 35, 35,
17, 16, 16, 38, 16, 44, 16, 16, 22, 17, 17, 16, 38, 16, 44, 16, 22, 22,
17, 16, 16, 16, 16, 16, 16, 16, 22, 17, 17, 16, 16, 16, 16, 16, 22, 22,
17, 16, 16, 16, 16, 16, 16, 16, 22, 17, 17, 16, 16, 16, 16, 16, 22, 22,
17, 16, 16, 16, 16, 16, 16, 16, 22, 17, 17, 16, 16, 16, 16, 16, 22, 22,
17, 16, 16, 16, 16, 16, 16, 16, 22, 17, 17, 16, 16, 16, 16, 16, 22, 22,
17, 16, 16, 26, 16, 32, 16, 16, 22, 17, 17, 16, 26, 16, 32, 16, 22, 22,
17, 16, 16, 16, 1, 16, 16, 16, 22, 41, 41, 12, 12, 12, 12, 12, 47, 47,
41, 12, 12, 39, 12, 45, 12, 12, 47, 41, 41, 12, 39, 12, 45, 12, 47, 47,
};
signed char rawBlock[] = {
0,-18,-37, 0, 0,-18,-35, 0, 0,0,0,0,0,0,0,0,0,0,
-1,-20,-18,-18,-18,-18, 1,-16, 0,0,0,0,0,0,0,0,0,0,
0, -1, -1, 0, 0, 1, 1, 0, 0,0,0,0,0,0,0,0,0,0,
0, 0, 0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
0, -1, -1, 0, 0, 1, 1, 0, 0,0,0,0,0,0,0,0,0,0,
-1, 16, 18, 18, 18, 18, 1, 20, 0,0,0,0,0,0,0,0,0,0,
0, 18, 35, 0, 0, 18, 37
};
#define blockSqrs (rawBlock + (3*18 + 3))
signed char steps[] = {
// even when using sub-lists several lists are needed to suit all square types
/*
0,
// Queen
17, 19, 18, 1, -1, 0, // 1
-17,-19,-18, 1, -1, 0, // 7
-1, 1, 18,-18, 0, // 13
1, -1,-18, 18, 0, // 18
17,-19,-17, // 23
*/
0,
// Queen
-18,-19,-17, // 1
17, 19, 18, 1, -1, 0, // 4
-17,-19,-18, 1, -1, 0, // 10
-1, 1, 18,-18, 0, // 16
1, -1,-18, 18, 0, // 21
-18, -1, 19, 18, 1, 0, // 26
-18, 1, 17, 18, -1, 0, // 32
18, -1,-17,-18, 1, 0, // 38
18, 1,-19,-18, -1, 0, // 44
// Horse
-16, 20, 37,-35,-37,-20, 35, 16, 0, // 50
-20,-16, 16, 35, 37, 20, 0, // 59
35,-37, 37, 20,-35,-16, 0, // 66
16, 20,-16,-35,-37,-20, 0, // 73
-35,-37,-20, 16, 0, // 80
-20, 35, 37, 16, 0, // 85
35, 37, 20,-16, 0, // 90
20,-37,-35,-16, 0, // 95
// Elephant
-33, 39, 56,-52,-56,-39, 52, 33, 0, // 100
-39,-33, 33, 52, 56, 39, 0, // 109
52,-56, 56, 39,-52,-33, 0, // 116
33, 39,-33,-52,-56,-39, 0, // 123
-52,-56,-39, 33, 0, // 130
-39, 52, 56, 33, 0, // 135
35, 56, 39,-33, 0, // 140
39,-56,-52,-33, 0, // 145
};
char ranges[] = {
0,
1, 1, 1,
1, 1, 9, 8, 8, 0,
1, 1, 9, 8, 8, 0,
8, 8, 8, 8, 0,
8, 8, 8, 8, 0,
7, 3, 2, 9, 8, 0,
7, 3, 2, 9, 8, 0,
7, 3, 2, 9, 8, 0,
7, 3, 2, 9, 8, 0
};
int firstDir[] = {
// R R C C H H E E A A K P P P P P
360,360,369,369,180,180,189,189, 0, 0, 0, 0, 0, 0, 0, 0,
360,360,369,369,180,180,189,189, 9, 9, 9, 9, 9, 9, 9, 9
};
unsigned char mvvCode[] = {
200,200,150,150,100,100, 80, 80, 40, 40,250, 20, 20, 20, 20, 20,
200,200,150,150,100,100, 80, 80, 40, 40,250, 20, 20, 20, 20, 20
};
int moveStack[10000];
