The current HaQiKi D is a simple mailbox engine, storing piece numbers in the board cells, which are the index of the corresponding piece in the piece list. Xiangqi does not have real promotion, so there can never be more pieces of any type as you have initially, and they are then either present or captured. The only tricky thing compared to Chess is that the moves for some piece types are dependent on their location on the board: Pawns get extra moves on the opponent half ('across the River'). The confinement of King and Advisors to the Palace and Elephants to their own half can also be implemented this way, by not giving them the moves that would step out of their confinement zone in squares at the edge of this zone. So rather than having a single (zero-terminated) list of possible board steps for each piece type, there are now many listst, and a board-sized table for each type indicates which list should be used for each square. E.g. a Rook on a0 would use the list with only a forward and rightward step. This actualy saves some time during move generation, as you would never try moves that would bring you off board immediately. (But at the expense of some L1 cache space, which I minimized by interleaving the tables for pieces with limited board access.)
Due to the success of the incrementally updated attack map in my Tenjiku Shogi engine, (where it gave an incredible speedup), I would like to use a similar scheme now for HaQiKi D. Xiangqi introduces some new aspects, which have to be dealt with, though. Instead of limited-range sliders it has 'lame leapers': Elephants and Horses can be blocked on a square they cannot move to. In addition, the Horse is a 'bifurcating' lame leaper: if it is not blocked, it can go on in two directions from the potential blocking square. Finally there are the Cannons, which do not attack their nearest neighbors, but their second-nearest neighbors. Superficially this is somewhat like the jumping generals of Tenjiku Shogi, but in practice it is very different, as they have to overjump exactly one piece, so that their possible capture target changes by interposing or withdrawing a piece.
The attack map
All bits in the attack map will correspond to individual pieces (rather than piece types or directions). The reason is that both Cannons and Rooks can simultaneously attack the same square from the same direction, and thus need separate bits. For efficient incremental update of the map it will also be necessary to record 'blocking squares', where mutation of the occupancy would affect a real attack elsewhere. These can be the squares adjacent to Horses and Elephants (where they can be blocked, but not go), or the 'mount' of a Cannon (which must be overjumped for capturing). So each Elephant, Horse and Cannon will have two bits in the attack-map word for a given square. This brings the number of bits to 22 (16 real attacks, 6 blocks). In theory this could be economized on, as Pawns could never go where Kings or Advisers can go, but as long as it fits a 32-bit words, there seems no advantage in that. It does imply that the attacks of each player will reside in a different word, but usually you need only one or the other anyway.
The attack map elements will be valid for slider attacks (and blocks) only on occupied squares, and for leaper attacks (and blocks) on all squares. This means that moving a Horse or Elephant wil always involve setting the block bits in 4 of its neighbor squares (or clearing them for the old location). If the square is empty, it will then also set (or clear) the attack bits of the squares that could be reached over it. For a moved Cannon the nearest neighbor is the mount, and will get the block bit for that Cannon set, while the second neighbor in that direction will get the Cannon's attack bit set. because of the use of a second neighbor we must make sure that boundary cells of the neighbor table will point to something sensible even in the off-board directions. (E.g. to a dummy square, or perhaps to themselves.)
When a square gets evacuated, the attack-map element for it then will indicate all moves that are discoverd by this. Leaper attacks can be ignored, but a leaper block will now have to discover the corresponding leaper move (one for an Elephant, two for a Horse), irrespective of whether it goes to an occupied or empty square. Evacuating a Cannon mount will change the downstream attack into the new mount, and displace the attack to the neighbor beyond that. For a Rook we simply have to displace the attack downstream, to the nearest neighbor in that direction. The downstream neighbors will be obtained from the neighbor table. A complicating factor here is that some piece types need modification of two attack-map elements, when discovered, while others only need to modify one.
Discovering moves on square evacuation
The set bits can be extracted from the attack-map element for an evacuated square one by one. As each bit corresponds to a particular piece, we would have to find the location of that piece (from the piece list) in order to know the direction the piece came from. As leaper bits will be already masked off before the bit extraction, we will now have to apply the discovered attacks going over the evacuated square in that direction to the attack map at the target squares. This could of course be done with a switch statement (or branch tree) to identify the type of the involved piece, but such programming constructs are sure to give large numbers of mispredictions. So my first inclination is to use branch-free code for this. That means the code must be able to handle the worst case, which is altering of two attack-map elements (for Cannons and Horses). That means that in some cases (Rooks and Elephants) the second change should be turned into a dummy, and will be wasted effort.
Code: Select all
int todo = attackMap[color][sqr] & ~LEAPER_ATTACKS;
while(todo) {
int n = lowBit[todo]; // extract bit
int piece = nr2piece[n] + color; // index in piece list
int s = location[piece]; // square it is on
int dir = direction[sqr - s] + typeOffset[n]; // (quasi-)direction of blocked move
int target = neighbor[sqr][dir]; // first target to change
attackMap[color][target] ^= change1[n]; // apply change
dir &= 7;
target = neigbor[target][dir]; // second target to change
attackMap[color][target] ^= change2[n]; // apply change
todo -= 1<<n; // done
}
For Rooks and Elephants, the second change is turned into a no-op by having their change2[n] = 0. The kludgy part of the code comes from the way directions are numbered: 8-11 are diagonal directions, 4-7 orthogonal directions. The latter refer to the directions for which we keep true neighbor information in the neighbor table. As Xiangqi has no diagonal sliders, there is no need to keep track of diagonal neighbors! The diagonal part of the neighbor table is only written at startup, as if the adjacent square in the given diagonal direction is the nearest neighbor. Displacing the attack to the nearest neighbor in change1[n] will thus apply it to the Elephant target.
For the Horses we use a similar kludge. But their blocking squares ly in orthogonal directions, like those of Rooks and Cannons. To make the distiction, we added typeOffset[n] to the direction obtained from the table, which is 4 for Horses, and 0 otherwise. This turns the orthogonal direction into the (clockwise most adjacent) diagonal direction, so the first target will be taken to ly one diagonal step away from theblocking square (i.e. a Knight jump away from the Horse). The dir &= 7 then turns directions 8-11 into 0-3. The neighbor table for these directions is initialized (and unchanging) to squares two orthogonal steps away, needed to get from one Horse target to its partner (blocked on the same square), i.e. perpendicular to the original orthogonal direction.
