The design I have in mind will use a neighbor table, which for each occupied square will hold the square number of the nearest neighbor in each of the 8 principal directions. This nearest neighbor can be an edge guard, when there is nothing between the square and the board edge. So the table will have to contain 10x10 elements, although for any particular direction the final element along that direction (always just beyond the board edge) will not have a further neighbor.
Then there will be an attack map, for each square holding bit flags to indicate attacks on it. There will actually be 4 such board size tables, for white and black attackers each a set of slider and a set of leaper attacks. The slider attacks will be flagged by direction, 1 bit for each direction of movement. The leaper attacks will be flagged by piece for King and Knights, (3 bits, perhaps 4 if we want to allow for a 3rd Knight), but by direction for Pawns (4 bits, one for each diagonal direction).
For the update of the attack map it will be handy to also record attacks on the edge guards, so that these can be treated exactly the same as on-board attacks. This means the slider attack maps will have to be 10x10. For leapers it would also be inconvenient having to test all the time whether a potential attack goes off-board or not, and the map will even have to be 12x12 to make sure it catches all Knight jumps. Leaper attacks will be valid for any square; we will just apply or remove them to the map whenever the leaper resposible for them gets moved or captured. Slider attacks will only be faithfully recorded on occupied squares, to limit the cost of updating (as sliders can attack very many unoccupied squares).
The piece list will be set up as a doubly-linked list, so that captured pieces can be easily removed from them. (And then re-inserted on UnMake().) The neighbor tables are in fact also a collection of doubly-linked lists, one for each ray, so that each occupied square is aware of its two neighbors on the ray through its forward and backward links. Evacuating a square will just remove if from the lists for all 4 rays it is on, and re-occupying it during UnMake will re-insert it, based on its old neighbors, which it still remembers.
Generating captures will be done by running through the piece list, which is kept in order of decreasing piece value. The piece numbers produce the piece locations, the locations produce the set of attacks on it, all through lookup in the appropriate table. The attacks will be extracted from the set also by table lookup. For leapers this would result in a piece number for the attacker (K or N), which finally is used to look up the location of the attacker. This leaves all 4 descriptive elements of the move (fromSqr, toSqr, piece and victim) known, so the capture can be made and searched. A Pawn would result in a recognizably invalid piece number (like negative or beyond the end of the piece table) when its turn comes up to be extracted. In this case the number would be used to index a table that contains the board step of the Pawn capture, which, added to the to-square, would produce the from-square, and finally through lookup on the board the number of the attacking piece (a Pawn).
Code: Select all
victim = nextPiece[victim]; // step through piece list
toSqr = location[victim];
leaps = leaperAttacks[stm][toSqr];
while(leaps) {
piece = set2leaper[leaps]+stm; // extracts in order Pawns, Knights, King
leaps = stripBit[leaps]; // clears lowest set bit, for next iteration
if(piece <= MAXPIECE) {
fromSqr = location[piece];
} else {
step = pawnSteps[piece - MAXPIECE]; // 4-entry table
fromSqr = toSqr + step;
piece = board[toSqr];
}
if(SearchMove()) goto cutoff;
}
// go on with slider attackers
Code: Select all
slides = sliderAttacks[stm][toSqr]; // we already had determined toSqr and victim
attackers = 0;
while(slides) {
direction = set2dir[slides]; // actually we tabulate &neighbor[direction]...
fromSqr = neighbor[direction][toSqr]; // ... so we can do fromSqr = direction[toSqr] here
piece = board[fromSqr];
attackers |= attBit[piece];
slides = stripBit[slides];
}
while(attackers) {
piece = set2slider[attackers]+stm;
fromSqr = location[piece];
attackers = stripBit[attackers];
if(SearchMove()) goto cutoff;
}
Non-capture generation could be done in the usual mailbox way, by running through your own piece list, and for each piece through a list of directions, and for each direction along the ray until you hit a non-empty squere (for a slider) or just one step (when it is a leaper). I am not sure if it would have any benefits to use history to order the non-captures; this would definitely cause a lot of complication. Maintaining a list of a dozen or so 'hot moves', and checking if these are possible in the current position, similar to what is done with killers, and then do them before non-capture generation might be faster than putting all non-captures in a move list, assigning them a history score, and sorting the lot.
I did not like the speed penalty we would suffer when using an interpreter. So I opted for assembly. I have already written an assembler.
What I plan to do is solder a second Y register ('Z') on top of the existing one (as far as inputs are concerned), and wire the outputs of that to the unused high address multiplexer input, so that the modes [const] and [X] become [Z,const] and [Z,X]. This allows relocation of the zero page, so that each instance of a recursive routine can have its own 'direct page'. Main problem is to find (and decode) an opcode to load this Z. Perhaps the highest bit of the data (now unused because there is only 32KB of RAM, so the high part of the address is only 7 bits wide) should be used to decide if the data is written in Y or Z.