Well, one of the problems with programming in assembler is that it is quite error prone, and that there is an appreciable chance that you will make errors even when entering code for a trivial task. So even when you have something simple that works, it will be a poor stepping stone to the more complex thing you eventually want, if that requires replacing
code that does things in a simple way by the complex code. In a sense you are starting from scratch all over.
So I want to have a road map along an evolutionary
development, which can improve sophistication by adding
code to something that is already working, with only minimal changes (if any) required in that working stuff. So if my eventual goal is to do staged capture generation from an incrementally updated attack map, I think it would be a waste of time to first write something that generates captures by making ray scans over the board, put them in a move list, and extract them MVV/LVA order. Even if you had the latter, and it worked perfectly with perft and all, it would not have brought you an inch closer to the final goal. What would make sense is to write code that does generate an attack map from scratch, for the current position, and initially run the staged move generation from there. Then you can later add code in MakeMove/UnMake to keep an incrementally updated attack map of the same format, and add code to compare the two in every node. And when all obvious bugs in the incremental update are cured, switch to using the incrementally updated map for capture generation, and after that limit from-scratch generation and comparison only to the root, and when the engine is fiished, throw it away altogether.
That means that in any case I want my loop over moves in Search() to look similar to what it should look eventually; this wil be the core of the engine, and I don't want to have to completely replace that later. The C code I presented above isn't especially complex. It relies on tables, which should be initialized without errors, though, in particullar stripBit, which would hold stripBit[index] = index & (index-1), and set2dir[(1<<d) + n*(2<<d)] = (&neighbor[d]) >> 8 (with d=0 to 7 and n all possible integer values that keep the table index in the range 0 to 255). And consistency between the attBit[piece] and set2slider[attackersSet].
But it definitely is a good plan to start by making a version that is stripped of almost everyting that is not absolutely essential. That would indeed be a perft-like thing, as that would do away with everything that has to do with evaluation and alpha-beta pruning. Initially I also don't want to bother with the complications of e.p. capture, castling and promotion, so the perft numbers would not be correct, but who cares? Then material evaluation, minimaxing of scores and alpha-beta pruning can be added. Then best-move tracking and IID, using the best move of the previous iteration as 'hash move'. Then tracking of the PV, using the PV move (when available) as hash move.
The thing that is still most unclear to me is how to best handle promotion. Because the design at various stages uses bit sets to represent a collection of leapers or sliders, the number of these cannot be allowed to exceed 8. For the sliders that would leave room for 3 extra Q, R or B, (as you start with only 5 of those), and for the leapers 3 extra Knights (after K, N, N, left-P, right-P). The sets will be used in the lookup tables set2leaper and set2slider to find their index in the piece table. Eventually the value in this index will have a meaning in itself, because although the piece list is traversed as a linked list, following the links, and thus potentially visiting them in any order, I want to detect whether futile victims are reached just from that index, rather than having to consult a lookup table for the piece value to see if the piece at that index is below the futilityThreshold, for every potential victim. Instead I want to translate the (high byte of the) eval-alpha difference to a piece index through a lookup table at the top of Search(), which tabulates the index of the first piece capture of which would not exceed the futility threshold. So it is important that the indexes represent the pieces in order of descending value, and that the linked piece lists respect this order.
So I have to reserve some entries early in the piece list for extra Queens, which can be done directly behind the King. As the King is always present, it would also be easy to insert such a Queen in the piece list (and take out the Pawn that promoted to it) on promotion moves. But since there is only room for 3 extra Queens in the bit sets, that means I cannot reserve a 'promotion Queen' slot for every Pawn, so that the promotion slots should be organized in a way that makes it easy to assign a slot to the Pawn that happens to promote. I guess this can be done by linking the spare slots into a list (using the same links as normally used to make them part of the piece list), and just unlinking the first element of that list on promotion.
For underpromotions it is more trick, however. I am not sure I want to allow those, and even if I do, they would only come at the latest stage of development. But since the way they would be handled would affect the design of the piece list, I want to reserve
the required assets for them now, so that I wouldn't have to change the handling of the piece lists for the other pieces later. Ideally pieces from under-promotion would be assigned indexes between Rook and Bishop, so that they are in the right place irrespective of whether they are Knight, Bishop and Rook. (I don't care about the order of Bishops and Knights). It would be difficult to insert them there in the doubly-linked list, however, as you don't know what the intended closest neighbor is that is still on the board. That would require you to run through the piece list, looking for pieces in the middle. (Well, perhaps not a big deal. Under-promotions will be very rare, not considered in QS. So who cares if their MakeMove is slow and cumbersome?)
An alternative is to put an always-present dummy cell in the piece lists, (linked) between Knights and Pawns. If the index of that cell is the highest of all, then even when Pawn capture is not futile, the futilityThreshold would be set to this dummy cell, so that the loop generating their capture would automatically terminate after the last minor. We then would have to test if Pawn capture was really futile (a simple compare between the futilityThreshold and the idex of the dummy cell), and if not enter a loop for the capture of the Pawns, starting with the successor of the dummy cell. A later advantage of doing capture of Pawns and pieces in a different loop is that a simplified MakeMove() could then be used for the latter, as capture of a Pawn will have ramifications for the passer accounting.
Such a dummy cell in the piece list creates the possibility to easily insert pieces just before or just after the cell. Before it the under-promoted pieces can be inserted. That would short-change a Rook obtained by under-promotion, as it would now be behind the minors, so that its capture in some cases could be considered futile, while in fact it isn't. Well, tough luck. In the root you could correct this on the next move. I am not even sure I would want to make the program ever search
under-promotion to Rook. (Although you can bungle a drawn KBPK if you are unaware of it.)
It is also easy to insert pieces directly behind the dummy cell. This could be used by considering 7th-rank passers a different piece type from other Pawns. So 'pre-promote' Pawns already when they reach 7th rank, delete their original entry from the piece list, and insert a new entry for them just behind the dummy cell. This does justice to the fact their value is around 200cP, and futility pruning could then take heed of their elevated status. I this case it is possible to reserve a cell for every Pawn, as individual Pawns are never indicated by a bit in a set; they are included in the set of leaper attackers by the direction from which they attack, and in this respect there is no reason to distinguish pre-promoted Pawns from ordinary ones. Allocatig a cell in case of pre-promotion then ivolves simply subracting a constant to the piece-list index.
The dummy cell also offers a starting point for running through the Pawn list for the purpose of generating promotions. You could just run through the list until you encounter a Pawn with an index in the range of unpromoted Pawns. Every pre-promoted Pawn you encounter that way only has promotion moves. Typlically there would not be any, of course, but it is nice to have a quick way for establishing that (namely that next[DUMMY] >= ORDINARY_PAWN).
This leads to the following assigment of piece-list indexes:
Code: Select all
index piece type next attBit
0x10 King 0x12 0xC0 start of piece list
0x12 Queen 0x1A 0x10
0x14 promo-Queen 0x14 0x20 <- qSlots
0x16 promo-Queen 0x16 0x40
0x18 promo-Queen 0x80 0x80
0x1A Rook 0x1C 0x08
0x1C Rook 0x34 0x04
0x30 under-promotion slot 0x32 0xA0 <- nSlots
0x32 under-promotion slot 0x80 0x90
0x34 Bishop 0x38 0x02
0x38 Bishop 0x3A 0x01
0x3A Knight 0x3C 0x88
0x3C Knight 0x7F 0x84
0x3E pre-promoted Pawn (for 0x5E)
0x50 " "
0x52 " "
0x54 " "
0x56 " "
0x58 " "
0x5A " "
0x5C pre-promoted Pawn (for 0x7C)
0x5E Pawn 0x70 ORDINARY_PAWN
0x70 " 0x72
0x72 " 0x74
0x74 " 0x76
0x76 " 0x78
0x78 " 0x7A
0x7A " 0x7C
0x7C Pawn 0x80
0x7E DUMMY 0x5E
Note they are all even: the corresponding odd values will be for the opponent pieces. Also note they all have the 0x10 bit set; this is a kludge for facilitating calculation of mobility. At some point we will want to count how many of the moves of a given piece will hit occupied squares with friends or foes. (The friends should not be counted towards the piece mobility, the foes give valid captures.) This can now be done by ANDing the index of the occupant with 0x11, and adding the lot. The upper nibble will then count total number of occupied target squares, and the lower nibble the number of white ones. This total can then be used in a lookup table to get the the number of captures amongst them, and add that to the mobility. The edge guards would mimic empty squares here (use code 0x80, with both the 0x10 and 0x01 bit at 0).
Also note that the MSB of the leaper set is reserved for indicating the tabulated attBit represents a piece, and not the direction of a Pawn attack. This limits the number of representable leapers to 7, and thus the number of Knight under-promotions to 2 (if no other Knights are captured).