After the killers:bob wrote:I do not understand your "move ordering search" then. It appeared, based on the terminology, to be a real search that somehow gets a score back for each move, which would imply a wide window. In any case, I don't see how one can do a search to order _all_ nodes inside the tree by doing a search, since internal iterative deepening on all nodes would be horribly expensive, particularly since the ALL nodes have no best order anyway...Michael Sherwin wrote:Here are some numbers for RomiChess in the original position for a 16 ply search on a Q6600, 2.4 GHz using only one core.bob wrote:I tried that (higher count while searching null-move) as well as a dozen other ideas over the last few weeks. No improvement for me at all. Most ideas I have tried were "zero effect" in fact, although an occasional idea would be a small negative change. Your idea about searching to order moves sounds impossibly expensive...Michael Sherwin wrote:I am not sure that complementary is the right word.bob wrote:I ran this test a couple of months ago. If you have null-move already, it is worth about +40 Elo in Crafty. If I don't use null-move and add LMR it is worth about +80. Interestingly, if you don't have LMR, null-move adds about +80 also, and if you already have LMR then null-move is worth about +40. I was surprised at first, but when you think about it, the two ideas are complementary.Don wrote:I would like to add that LMR does result in a major improvement in the strength of my chess program. I think most people have found that too, but I have heard some claim there was little strength gain.
Null move suffers some tactical shortcomings because of a more shallow search. However, Null move is much stronger overall.
LMR suffers some tactical shortcomings because of a more shallow search. However, LMR is much stronger overall.
When Null move and LMR reductions are both active at the same time the combined reductions IMO reduces the total benefit.
Using a higher move count before allowing LMR, while in null move, seems to improve strength. And is stronger than making them mutually exclusive. Except at shallower depths when mutual exclusion seems stronger.
Edit: In RomiChess the remaining moves are first scored with a very shallow search that has an open window if remaining depth is greater than three. This allows for very good move ordering of the remaining moves which in turn improves LMR.
These numbers just reflect how the 'remaining' moves are ordered.
No changes:
47,035,963 nodes, 18,919 msec, 2,486,175 nodes/sec
Not counting the nodes of the move ordering searches:
31,062,742 nodes, 18,778 msec, 1,654,209 nodes/sec
Not doing the move ordering searches, only using piece-square table (fs - ts) move ordering:
195,685,842 nodes, 76,736 msec, 2,553,445 nodes/sec
No ordering of remaining moves:
326,677,020 nodes, 117,960 msec, 2,769,387 nodes/sec
This looks to me as though move ordering searches are cheap.
And N then becomes very relevant for LMR.
Code: Select all
case ADDMOVES:
h->phase = NEXTMOVE;
AddMoves(h->node, depth);
if(h->node == (h+1)->t) return FALSE;
if(depth > 3) {
for(node = h->node; node < (h+1)->t; node++) {
Sort(node, (h+1)->t);
MakeMove((moves *)&node->m);
if(GetReps())
node->score = 0;
else {
inShort++;
node->score = -Search(-beta - 100, -alpha + 100, depth > 9 ? 3 : 1, extendBy);
inShort--;
}
ClrReps();
TakeBack();
}
}
case NEXTMOVE:
if(h->node + 1 == (h+1)->t) {
h->phase = NOMOVES;
return TRUE;
}
Sort(h->node, (h+1)->t);
}
return TRUE;
Code: Select all
reduce = 1;
if(depth > 3 && h->phase == NEXTMOVE) {
count++;
if(h->node->score <= alpha) {
if(didNull) reduce += 2; else
if(count > 1 + ((inNull != 0) << 1) && board[ts] == EMPTY) {
s32 g = histTblg[fig][fs][ts];
s32 n = histTbln[fig][fs][ts];
if(n > 99 && g / n < 12) {
reduce += 2;
}
}
}
}