It’s not very often that you can make a change that will net your program 350 Elo, but that’s exactly what I just did! A quiescence search was added to chess4j and Prophet4, resulting in a dramatic increase in playing strength.

The main issue with a fixed depth search that simply calls a static evaluation at the leaves is the horizon effect. A quiescence search attempts to minimize this issue by performing a more limited (highly selective) search at the leaves, until the position becomes quiet. There is some variability between programs as to what moves to expand, but typically they would be capturing moves, check evasions and possibly checking moves. Promotions or other threatening moves may also be considered. The danger is search explosion – expanding too many moves will cause the subtree to be too big and take too much time to resolve, possibly at the expense of starting a new iteration of the full width search. Therefore, it may become necessary to limit the quiescence search in some way, such as a maximum depth.

My programs are currently only considering captures, though I do plan to experiment with checks at some point. Captures seemed to be a safe starting point, sort of a “base line,” and minimize the chance of a search explosion since capture sequences tend to “fizzle out” at some point (though I’m sure there are some pathological positions out there that would cause problems).

Results of a chess4j self play match: with a quiescence search vs without:

Wins	Losses	Draws	Pct	Elo	Error
1683	160	157	0.881	347.36	21.23

… and the latest Prophet4 vs Prophet3:

Wins	Losses	Draws	Pct	Elo	Error
83	1661	256	0.105	-371.33	20.18

Still a long way to go to catch P3, but considering that before the quiescence search was added the results were more like 5 wins, the needle has moved quite a lot.

The next planned addition – hash tables – should net another large gain. I’m not sure that I’ll ever see this kind of increase again, but I expect it will be significant.

I’m also starting to do some experimentation to devise a testing strategy. I’ll write about that in another post when I have some results to share.