Noob: Problem extending the search for captures

[mike_bike_kite]

I'm trying to avoid horizon effect problems in my little chess program so I added IID (Internal Iterative Deepening) which seems to work. I then changed the code a little so it would continue searching if there was a capture for the current side.

I wanted to use the existing code which looks a bit like the pseudo code below. It's making horrible mistakes now but I can't see why. Is this roughly how it should work?

Code: Select all

init best score for level

while moves left
      if level >= max and move not a capture
            skip this move
      put it on
      swap sides
      score = go up a level
      swap sides
      is this a better score

if level >= max
      score = board evaluation
      is this a better score

return best score for level

I get a nasty feeling it's just considering random captures around the board and ignoring sensible moves. If this does ever get working then should I add checks and escapes from check into the mix? Should I limit the captures considered to only those made on the last square?

It could of course have a brilliant series of sacrifices planned but somehow I doubt it.

Mike

PS It's quite difficult this chess programming lark isn't it.

[tpetzke]

1. I think you confuse IID with quiescence search, IID helps to order subtrees before you search them or to get you a good move when you don't have a hash move. It cannor help in preventing horizon problems as the IID depth is even less than normal search depth.

2. From your code syntax it is a bit hard to tell

Possible sources of error

- you don't take the move back after search ("put it on" has no "put it back" statement), you however swap sides twice

- how do you init the best score for that level, you should get it as a parameter (alpha)

- when you don't do a move you return best score, but if you had no move you should return draw or checkmate.

- you always force the side to move to do a capture, no matter how stupid that capture is. You should allow the side to move to just accept the current score and don't capture anything (standing pat)

- the current implementation will search very deep beyond your max level, you won't reach a good general search depth that way

Thomas...

[Sven]

Hi Mike,

welcome to CCC

Have you checked the chess programming wiki?

Avoiding the horizon effect is usually not accomplished by using IID (which is mainly about improving the move ordering) but by introducing quiescence search (capture search, exactly your topic) and/or adding extensions.

Regarding your algorithm, it is difficult for me to understand what it does, where one possible reason for that might be that it includes both parts of the search in one. Most people use two separate functions, one for the full search ("level < max" in your case) and one for the quiescence search.

One point that might be missing in your algorithm is the proper handling of the "stand pat" principle in quiescence search, i.e. the moving side can choose whether it makes a capture (if that improves its evaluation) or does "nothing" and sticks with the static evaluation of the current node, assuming that at least one "quiet" move exists that would return >= this static eval. To achieve this you need to call the evaluation first, before expanding any possible capture, since you need it for comparison. I am not sure whether your algorithm works like this (it seems it doesn't).

EDIT: Regarding your questions, I propose that you
a) get the basic stuff running perfectly first before you try to add checks (and check escapes) to the quiescence search (it is not even necessary, and if you do it you would also need to restrict this to the first one or very few plies of qsearch),
b) do NOT restrict your quiescence search to recaptures on the same square, since that will overlook a lot of tactics.

Sven

[mike_bike_kite]

I think you confuse IID with quiescence search : Yes, you're right but I'm adding both features to my little program at the moment. It currently uses fixed depth but obviously this runs into horizon problems. The IID would allow it to search further if there was time. The quiescence idea helps it evaluate all possible captures.

Most people use two separate functions : sadly I didn't read the wikis before coding this and hate the idea of rewriting working code.

"stand pat" ... need to call the evaluation first, before expanding any possible capture, since you need it for comparison. I am not sure whether your algorithm works like this (it seems it doesn't) : Oops - I'll move this part to the front and see how that might affect things.

get the basic stuff running perfectly : My chess program plays fine at the moment but I just want it playing a little stronger.

the current implementation will search very deep beyond your max level, you won't reach a good general search depth that way : So should I limit how far it can extend? how many ply would be typical?

Thank you both for replying so quick.
Mike

[hgm]

It does not do any harm to use the same function for both QS and full-width search; micro-Max has that too. When in full-width search you initialize the bestScore at -INFINITY, and in QS you initialize it to the current evaluation in stead. That is all.

It is very important you do the latter before searching any moves, though, and then testing for a beta cutoff. Because if you have one, you save yourself the trouble of searching any captures at all, and you can even skip move generation.

A second point that is really important in QS is that you order the moves such that you will always try to capture the most valuable piece first. If you don't do that, you will run into one or two position where QS 'explodes' in almost any game. This happens in particular when both sides have Queens, and they both go on a plunder raid. The program will then try to figure out in how many hundred-thousand dfferent ways they can clear the board through unsound captures. If you make it capture the Queen at the earliest possible opportunity, this will put an early stop to it, because non-sensical variants will be immediately recognized as such.

[tpetzke]

The IID would allow it to search further if there was time.

No, it would not. I guess you mean iterative deepening (ID), which stands for searching the root position with increasing depths. IID (Internal Iterative Deepening) is used in inner nodes (PV and sometime CUT nodes) of the tree for move and tree ordering.

the current implementation will search very deep beyond your max level, you won't reach a good general search depth that way : So should I limit how far it can extend? how many ply would be typical?

I let it finish, when you implement standing pat and a good move ordering (capture the queen as early as possible, try winning captures before equal ones, skip losing ones) qSearch does not go very deep. But as it is called from the horizon nodes your program will spend a lot of time there.

Using a different function helps if your search gets a bit more advanced. You usually do different tricks in search and qSearch (IID, Null Move, Hash Table Access, Futility Pruning, Move Ordering...)

Thomas...

[hgm]

Oh, apart from null move, which takes the place of stand pat, I do all of that in QS too. Of course the IID never gets the chance to do a second iteration in a QS node, as it already starts at target depth, but that doesn't cost you anything.

[mike_bike_kite]

All good points. Hadn't thought about ordering within the set of captures. I'll try and get the basic design working first and then add performance enhancements afterwards.

... and sorry about using the wrong acronyms, hopefully as I code them then I'll also learn to use the correct terms.

Mike

[tpetzke]

Yes, in some way I do most of the stuff in qSearch too, but differently. Take move ordering, it is present in search and qSearch but applying a different order to the moves.

In normal search I have a hash move, tactical moves, killers and non tactical. I use SEE to order the captures and another function to order the non tactical moves.

In qSearch I don't have a hash move and killers. I have only tactical moves and order them on a MVV/LVA scheme, I apply SEE only for the decision whether it is safe to prune that move.

So it is possible to write everything in a single function but it creates easier to read and maintain code to split it, at least for me (on the other side I don't care about the number of source code characters that much at the moment

Thomas...

[hgm]

Why would you not order the captures ing QS by SEE, if you do the SEE anyway? Is there any reason to assume optimal order for captures is different in QS as in full-width search?

I order captures by MVV/LVA, (I am not talking about micro-Max, which does not have any real move ordering at all), and then use BLIND rather than SEE to weed out bad and dubious captures. I then use the move order:

null/stand pat, hash, good & equal captures, dubious captures, killers, non-captures, bad captures.

In QS I bail out after the dubious captures (as killers are by definition non-captures), which then automatically prunes the bad captures. I also see no reason to skip the hash move in QS.