“Tree shaping” is an important component of a strong chess program. There are various ways to shape a search tree. One is by extending lines that seem interesting in some way; particularly those that cannot be fully resolved within the search horizon (see https://en.wikipedia.org/wiki/Horizon_effect). Other methods of shaping the search tree include reducing or even pruning lines that seem less promising. The quiescence search is also a form of tree shaping, as the search becomes more selective in which nodes it expands – typically just captures or captures + checks and check evasions.

One of the simplest, and perhaps the most effective extension is the “check extension.” Whenever a move is made, if the move gives check to the enemy, the search depth is increased by one. That is, instead of this:

apply_move(pos, move)
val = -search(pos, depth-1, -beta, -alpha)

Do this:

apply_move(pos, move)
bool gives_check = in_check(pos)
int ext = gives_check ? 1 : 0
val = -search(pos, depth-1+ext, -beta, -alpha)

Disclaimer: that is probably a little too naive, as it doesn’t really guarantee the line will terminate. There are surely positions that would cause the extension as written above to explode the search tree. But, on average, it’s a win.

I implemented the check extension in Prophet4 and indeed it seems to be a big win.

Wins	Losses	Draws	Pct	Elo	Error
331	183	402	58.1%	56.6	16.8

In an effort to add some sort of terminating criteria to it, I also tried limiting the check extension to capturing moves, and while still a win it didn’t work out as well.

Wins	Losses	Draws	Pct	Elo	Error
3206	3119	4505	50.4%	2.8	5.0

I also tried another form of extensions entirely – promoting moves. However, it had no measurable effect at all and may have even been a small loss, so I abandoned it.

After settling on the “naive check extension” I measured P4’s standing against P3.

Wins	Losses	Draws	Pct	Elo	Error
313	929	758	34.6%	-110.6	12.2

The last time I measured, P4 was -164.29 vs P3, so it’s definitely gained some ground.

Next on the list is to take a careful look at move ordering before moving onto another form of tree shaping – reductions. I expect Late Move Reductions (LMR) in particular to give another large jump. But, the algorithm is very sensitive to good move ordering, so it’s worth taking some time to study that first.