Some positions are interesting and you want to search all of the successor
positions more deeply.
It's interesting to try to figure out why you might want to do this.
There seem to be some contradictory reasons:
1) Win-seeking extension: If I stop searching now I'll fail low, but I
think there might be something good here if I look a little further.
2) Loss-seeking extension: If I stop searching now I'll fail high, but I
think I'm in trouble.
3) Neutral extension: This is a forcing sequence, and if I stop searching now
I won't know how it ends.
In these cases, you may want to search more deeply, so you can try to resolve
the situation more correctly. You either find out that you have a win, you
find out that you are hosed, or you avoid making a mistake either way.
The goal is more accuracy. The risk is that you'll search even more
garbage than usual, so that gains are drowned in extra nodes. So the best
possible case is that you get the extra accuracy while constraining the
extension so it doesn't make the search tree enormous.
How extensions traditionally work is that rather than decrementing the depth
under a successor node, you use the parent's depth.
So if this node is to be searched to depth 3, you will typically search all
successors to depth 2. The ones you want to extend you'll search to depth
3.
It is dangerous to extend like this, because obviously if you extend
everything, the search will never terminate. Even if the search
terminates, you still run the risk that you'll search a lot of garbage.
Even more dangerous is to increment the depth under the successor
node, so for instance in my example above you might search a successor to depth
4. It's possible to do this, but in practice it is extremely dangerous and
everyone I've spoken to recoils in horror at the thought of doing this.
Another alternative is to search fractional plies, which allows you to use
fractional extensions. I believe that a lot of good programs do this.
You can be more liberal about extending, but you know that eventually the
program will run out of depth and the search will terminate.
I'll now describe some obvious extension ideas. I'm not going to
provide a lot of details of experimental results, since that is for every
program to mess with themselves. This article should serve as a source of
ideas, rather than implementation methods.
Check extension
The idea here is that if you check, the opponent probably has very few
replies, so extend all of them. It is easy to see this as an example of a
win-seeking extension, since checking is related to checkmate. However,
chess programs are great spite-checkers when they are losing, so it's important
to know if that's what is going on. So this is more of a neutral
extension.
My guess is that this is the oldest extension in computer chess. It
seems to be a good idea. I've never figured out a way to constrain it, but
I have heard that others have done this with success.
Single-response extension
The idea here is that if you are in check, and you have one way out of check,
you are in big trouble, so you should extend that one way out of check.
This is definitely a loss-seeking extension.
It is also definitely an extension that needs to be constrained, because it
is possible in some cases to create a sequence of check + single response that
goes on essentially forever. You should not allow this extension
unconditionally. You either need a fractional extension system or some
other means of making sure that many of these are not done in a row.
This extension has been used by commercial programs, and has been the focus
of some advertisements. There were ads in the 1980's for chess programs
that could find mate in 15 in a second or two, and when I looked at the
positions, they all involved a series of checks with one possible response.
This extension will dramatically improve results on checkmate test suites.
Whether or not it has an effect on real games is open to debate, since there is
some tree-size cost in positions where neither side is being mated.
Recapture extension
The idea here is that if I play RxR, you have to take my rook. RxR
isn't something that's apt to cause a cutoff, it's just a trade that I start,
and you have to finish, before I go on to other things.
What this amounts to is a forcing sequence that I can initiate in order to
eat up some depth. This is most likely a case where I am trying to avoid
getting beaten.
So the extension is on the recapture. An obvious way to implement this
is to make the recapture a free ply.
There are problems where a series of forcing captures leads to a winning
situation as well.
Recapture extension is another extension that seems to work well in practice,
without a lot of need to constrain it. It is not a very tricky extension.
Singular extension
This extension is the search heuristic centerpiece of Deep Thought, the
strongest computer chess player of the 1980's, and precursor to Deep Blue.
The idea is that if one move is significantly better than all of the other
moves (a singular move), it should be extended.
This can be interpreted as a more general case of the recapture and single
response extensions. It encompasses these, but also can be used in cases
where the singular move is not a recapture and where the side making the move
isn't in check.
I don't know why it worked in DT, but it seems to me that this is a
loss-seeking extension.
I have never seen anyone claim in an article to be able to get good results
with this extension, so for academic purposes I think this is unproven.
I've played with it myself and had some success in getting it to solve tactical
problems faster.
The down side is that you get less general-case depth when you use this,
because you have to do extra searches to test for singularity.
Mate-Threat extension
This is just a matter of extending responses to a mate threat. It may
be difficult to detect that a mate has been threatened, but there are problems
where one side is down materially and repeatedly threatens mate. It seems
obvious that this is a good win-seeking extension.