In micro-Max I take the lazy approach, and rely on the duplicats causing a hash hit on their initial search result. That leads to redundant make/unmake and hash probe for one move (micro-Max doesn't use killers), but make/unmake is very fast (mailbox without piece list), and the hash entry should still be cached from the previous search of the move. So you won't lose much compared to doing a simpler test (than a hash probe) on all the moves.
But this starts to fail under large hash pressure. And it would of course not work at all without hash tables. (Where this is still an issue, because the move of a previous IID iteration will serve as 'hash move' in the next iteration, and you still have to deal with killers.)
Another problem is that I often use an IID scheme that first verifies if a beta cutoff in a non-final iteration will hold all the way up to the requested depth, before stepping up the iteration depth. (So that when the move fails low after all, the search for an alternative can continue at the lower depth, preserving the advantages of IID.) This creates another situation where a move has already been sufficiently searched. E.g. in the d=2 iteration of a d=6 node, where the move still seemed to cut at d=5, but then failed low at d=6. The IID then resumes the d=2 iteration, and after that finishes without a cutoff, it will revisit the move for d=6 (or perhaps d=4), while redoing searches at those depth is pointless, as the d=6 result was already obtained. Again, you can hope for the hash hit on the 'over-deep' result to save the day.
But now I am programming for a machine where hash tables are unaffordable (32KB RAM). So I cannot ignore the problem anymore. Move lists are still affordable, though. So the IID problem could be solved by keeping a depth and score with each move in the move list, to hold the deepest result obtained for it so far. This acts as a sort of private cache for the hash entries of all daughters, which canot be overwritten, and the parent could cheaply probe that table before embarking on a search of the move. It would not help against moves that are in the list twice. And of course it makes some overhead to initialize the extra info in the move list.
This consideration, plus the fact that the machine I am writing for has difficulty crossing (256-byte) memory page boundaries, and handling data types longer than 8 bits, made me look for a more compact idea than a move list. Finally I came up with the following:
In a give position, each move can be encoded in a single byte. This can be done reasonably efficiently, if from-square, to-square and the piece number (the index in the piece table) of the moved piece are all known. (As they must be at the start of MakeMove.) It just requires two lookups in small tables:
moveCode = stepCode[fromSqr - toSqr] + pieceCode[pieceNr];
A move along (say) a file needs only 7 codes to be unique, although the distance moved can range from -7 to +7, because for any location at most 7 of these 14 possible targets can be on the board. So a Queen needs 4*7 = 28 codes to unambiguously identify her move, and a Rook or Bishop only 14. Pawns need 4 (because of the double push), and Knights and King 8. The numbering of the step vectors can be done such that all the codes for Knight jumps, as well as white and black Pawn moves are contiguous, and the King moves only have a single hole (so it spans 9 codes). Rooks and Bishops are perfectly complementary, so no matter how you assign the stepCodes, a Rook and Bishop with the same pieceCode will never have any of their moves collide; it is just encoded like a Queen, and depending on whether the described move is orthogonal or diagonal you kow if the Rook or Bishop was meant. A full FIDE army needs only 141 codes, and even allowing an extra Queen gives only 169.
So a 256-byte page could hold this no problem. But memory is not that abundant, and I would need to hold at least a two-byte score and a depth. And usually there would be only 30-40 moves in the position, and usually only a small fraction of those would have been searched deeper than the current depth iteration requested. (And at most 3 would be hash or killer.) So it seems better to map the move code into a 128-entry table. Only 13 entries then could suffer a collision, and by picking the codes in a clever way it can be arranged that Pawn moves collide with distant (4-step) slider moves. Pawns only rarely have their capture moves, and on a board full of Pawns sliders usually do not move very far.
Still, there must not be any ambiguity, so the collisions must be resolvable by a signature in the table, for which we could use the from-square. Perhaps we can even afford to use a 64-byte table that way. This would typically map 2 (and rarely 3) moves to the same entry. One memory page could then hold 64 entries consisting of from-square, depth and 2-byte score.
Such a table could have another interesting application, namely storing counter moves. When we immediately deepen cut moves until they fail low or reach final depth, the first IID iteration will either fail high (to full depth), in which case we are done, or fail low after searching all moves (some possibly to higher depth). In the latter case each move would have been refuted by a cut move in the respective daughter. We could make the daughter return that cut move, and store it in the table. And then, in the next IID iteration, pass it to the daughter as hash move.
This would require us to add a fifth byte to the table entries, though. (The packed move encoded in the daughter position could be stored there.) This is a bit awkward. But each ply level would need some local variables anyway, in addition to this private hash cache, and there should be 64 spare bytes in that second page. Then each ply level would use two 256-byte memory pages, which is affordable.
Note that on entering the node, it would find the table as another node at the same ply level would have left it. We'd rather not spend time on clearing the table. This seems to be possible through the following code:
Code: Select all
Search(alpha, beta, depth, hashMove)
{
int8 moveDepth[256]; int16 moveScore[256];
int mCode, hCode;
iterDepth = 0;
keyMove = 64;
moveDepth[hCode] = 0; // clear any hash move we might have inherited
while(iterDepth++ < depth) { // IID
if(hashMove) { // we have a 'hash move' (from previous iter, or PV)
MakeMove(hashMove);
d=iterDepth-1;
while(d++ <depth) {
score = -Search(-beta, -alpha, d-1, NOMOVE);
depthReached = d;
if(score < beta) break;
}
UnMake();
if(score > alpha) {
alpha = score;
if(score >= beta) return beta;
} else hashMove = NOMOVE; // it failed low, don't keep it
mCode = hCode = Pack(hashMove);
moveDepth[mCode] = depthReached + keyMove; // label as hash move; d could be > iterDepth
moveScore[mCode] = score;
}
for(ALL_MOVES) {
mCode = Pack(move);
oldDepth = moveDepth[mCode];
if(oldDepth >= keyMove) { // in first iter, keyMove = 64 and only the hash move can beat that
moveDepth[mCode] &= ~64; // clear the hash marker, but leave its depth
score = moveScore[mCode]; // use the previously calculated result for the duplicat or previously over-deep searched move
} else { // on first iter, all other moves than hash go here
MakeMove(move);
d = iterDepth-1;
while(d++ < depth) {
score = -Search(-beta, -alpha, d-1, NOMOVE);
depthReached = d;
if(score < beta) break;
}
UnMake();
if(depthReached > iterDepth) { // move has had an extra deep 'preview'
moveDepth[mCode] = depthReached; // remember that for next iter
moveScore[mCode] = score;
} else
moveDepth[mCode] = 0; // this makes sure we overwrite any uninitialized stuff
}
if(score > alpha) {
alpha = score;
if(score >= beta) return beta; // stop iterating after cutoff
hashMove = move; // found new best move
}
} // iteration failed low
keyMove = 0; // all data in table is now from this node; allow its use
}
}
