Back Up Next

Search Extensions

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.

 
Send mail to brucemo@seanet.com with questions or comments about this web site.
Copyright © 2001 Bruce Moreland
Last modified: 12/27/02