Saturday, July 30, 2011

Quiescence Search Trouble

While cleaning up my code base I realized that the quiescence search (qSearch) behaved not the way I intended. In qSearch  I don't want to search captures that lose material. I create all captures for a given position and perform a static exchange evaluation (SEE) on them. If the played exchange reveals that the capture is losing I delete that capture from the list.

But my implementation had an error.

for (i=0; i < ml->moveCnt; i++)
   if ((see(ml->moves[i]) < 0)) ml->deleteElementAt(i);
This code is problematic because the deleteElementAt(idx) function performs the deletion by copying the last element onto the position idx and decrementing the moveCnt property.

So the last element from the list is now at the position of the losing capture, but the move counter i is incremented after that operation and so this element is not checked whether it is maybe also losing. This way the resulting list might include losing captures which makes the qSearch search more moves and therefore nodes than intended.

I fixed that error but to my surprise the fixed version played weaker than the buggy one. Obviously the inclusion of some losing captures (which are selected more or less random) let the engine see some tactics that it otherwise missed and this effect more than countered the effect of the additional nodes.

I run tests where the fixed and the buggy version reported different results and tried to figure out what losing captures might me worth searching but I did not came to a good rule for that. Also searching all losing captures gave a weaker engine.

But I was not willing to keep the buggy code in the engine. So I did a complete rewrite of qSearch and also improved the static exchange evaluation to report more accurate results (it is now aware of king pinned pieces). This version now is a strong as the buggy one, but gives me a better feeling.

So this was obviously the rare exception to the "bugs hurt playing strength" rule.