Aspiration bug

[Henk]

An example of such a blunder (aspiration enabled). Skipper with black. I haven't seen this kind of blunders when aspiration is disabled.

Does it reproducibly makes this blunder in this position? Then it should be easy to debug, as this seems a big blunder.

At what depth does it first pick this move?

I did not use winboard but my own clumsy web user interface. In winboard it plays Nc6. So not reproducible. When I encounter such a blunder using winboard I can save it and probably will be reproducible. My engine uses random number generator too. So there is no guarantee.

[Henk]

Here I have one. Selects at depth 9 Nf4 for the first time.

[pgn]
[Event "Computer Chess Game"]
[Site "HP"]
[Date "2015.02.13"]
[Round "-"]
[White "gebruiker"]
[Black "SkipperWinb"]
[Result "*"]
[TimeControl "300"]
[Annotator "1... -0.10"]

1. e4 Nf6 {-0.10/11 6} 2. e5 Nd5 {-0.13/10 6} 3. c4 Nf4 {-0.12/10 6} 4. d4
Ng6 {-0.09/10 6} 5. h4 h5 {-0.10/9 6} 6. Bd3 Nf4 {+0.09/9 5}
{Game aborted} *

[/pgn]

Unfortunately not reproducible it selects c5 or d6. Nf4 is never considered. I used edit game in winboard.

[hgm]

I did not use winboard but my own clumsy web user interface. In winboard it plays Nc6. So not reproducible. When I encounter such a blunder using winboard I can save it and probably will be reproducible. My engine uses random number generator too. So there is no guarantee.

For debugging such things you should not try to reproduce the entire game, but just feed it the position where it goofed, and let it calculate from there. As long as you have these bugs you can clear the hash, killer and history arrays (and what else you have) before every move, to make sure all memory of previous searches is erased. In engines that randomize I always print the random seed (usually derived from the start time) in the log, and allow it to be set through a command-line argument, so that I can also reproduce the randomization, when needed.

Once you have a single position that reproducibly makes a blunder, it should always be possible to figure out the cause by judiciously placed conditional print statements. If the blunder occurs only in very deep searches, this can be a bit tedious.

[Henk]

This looks crappy at start of search. I commented out these lines now to be sure. Changing alpha (= lb) while no moves have been played yet.

Code: Select all

 
case TranspEntryType.LB:
                            if (entryValue >= ub)
                            {
                                bestMove = entry.BestMove;
                                return entryValue;
                            }
                            //if (lb < entry.Value)
                            //{
                            //    lb = entry.Value;
                            //}
                            break;

[hgm]

Well, in my experience staring at the code seldomly helps to catch such bugs. The only effective way is to do it interactively: print the score of all moves in a certain node (recognized by the path to it), and check which score you consider in error (either the move it takes has a score higher than it deserves, or the move it should have taken has too low a score), and then repeat the same thing in the node after that move, etc. Until you arrived at the source of the faulty score.

[Henk]

Well, in my experience staring at the code seldomly helps to catch such bugs. The only effective way is to do it interactively: print the score of all moves in a certain node (recognized by the path to it), and check which score you consider in error (either the move it takes has a score higher than it deserves, or the move it should have taken has too low a score), and then repeat the same thing in the node after that move, etc. Until you arrived at the source of the faulty score.

In older versions of a few years ago I got a tree view which showed all nodes and all bounds. After a few hours debugging they should haven taken me away to a mental hospital.

I remember that null move pruning makes the tree a mess.

[hgm]

It shouldn't have to take hours at all, once you have put the right infra-structure in your program. What I always build in the debug version of my engines is something like this:

Code: Select all

Move_t path[MAXDEPTH], viewPath[MAXDEPTH];
int ply, pathLength;

int
OnPath()
{
  int i;
  for(i=1; i<ply && i<pathLength; i++) if(path[i] != viewPath[i]) return 0;
  return 1;
}

int
Search(int depth)
{
  ply++;
  ...
  MakeMove(move);
  path[ply] = move;
  score = -Search(depth-1);
  UnMake(move);
  if(OnPath()) printf("%d:%d %s %d %d\n", ply, depth, MoveToText(move), score, bestScore);
  ...
  ply--;
  return bestScore;
}

where viewPath and pathLength are initialized from the-command line arguments. So that I can invoke the engine like

myengine.exe e2e4 e7e5 g1f3 b8c6 f1c4

to make the engine print stuff in all nodes along the path. Then I just run the engine, load the critical position, see what it prints and which move I consider in error, quit the engine, append that move to the command line, and repeat. This way you arrive in a few minutes to the faulty node. Then I add a few other if(OnPath()) printf(); to figure out what exactly goes wrong in that node, depending on what seems to be the case (and elete those after I fixed the error).

[Sven]

What's wrong with this code. In case of timeout bestMove is skipped in the caller and iterative deepening loop is ended. Also bestMove and it's value is only set when not timeout has occurred. So I don't understand why it sometimes selects a really bad move.

Code: Select all

   public int SearchRoot(int depth, int initVal, out MoveBase bestMove)
        {
            int WINDOW_MARGIN = 2000;

            int factor = 1;
            int lb = initVal - factor * WINDOW_MARGIN;
            int ub = initVal + factor * WINDOW_MARGIN;


            int value = Search(depth, lb, ub, out bestMove, false); ;
            if (Expired())
                throw new TimeoutException();
            factor = factor * 4;
            do
            {

                while (lb >= value)
                {
                    lb = initVal - factor * WINDOW_MARGIN;
                    value = Search(depth, lb, ub, out bestMove, false);
                    if (Expired())
                        throw new TimeoutException();
                    factor = factor * 4;

                }

                while (ub <= value)
                {

                    ub = initVal + factor * WINDOW_MARGIN;
                    value = Search(depth, lb, ub, out bestMove, false);
                    if (Expired())
                        throw new TimeoutException();
                    factor = factor * 4;


                }
            }
            while (!(value > lb && value < ub));

            return value;
        }

This algorithm is a mess, there is absolutely no need for an outer loop containing two inner loops. What you need to do is only one loop where you always increase the window size at one end until the search does not fail low or high any longer. That would look like this:

Code: Select all

public int SearchRoot(int depth, int initVal, out MoveBase bestMove)
    {
        int WINDOW_MARGIN = 2000;

        int factor = 1;
        int lb = initVal - factor * WINDOW_MARGIN;
        int ub = initVal + factor * WINDOW_MARGIN;

        int value = Search(depth, lb, ub, out bestMove, false);
        if (Expired())
            throw new TimeoutException();
        while (value <= lb || value >= ub)
        {
            factor = factor * 4;
            if (value <= lb)
            {
                lb = initVal - factor * WINDOW_MARGIN;
            }
            else
            {
                ub = initVal + factor * WINDOW_MARGIN;
            }
            value = Search(depth, lb, ub, out bestMove, false);
            if (Expired())
                throw new TimeoutException();
        }

        return value;
    }

The other problem is your handling of "bestMove" in combination with your exception handling solution. How do you call your SearchRoot() function? I think you should better save the "bestMove" that is returned by SearchRoot() before starting the next iteration, since there will be a last iteration that stops on timeout, and what will it do with the "out" parameter "bestMove" which is owned by the caller (your iterative-deepening loop)? Will it leave the caller's "bestMove" untouched, or will it cause undefined behaviour, or what else? It is possible that you already take care of this, maybe I did not read carefully enough what you wrote.

Another question is, since "bestMove" is also an "out" parameter of function Search() of which I assume that it is called recursively throughout the whole full-width part of the search tree, do you ensure that Search() changes "bestMove" only when being called at the root node, and also only if the score of the new best move is inside the alpha/beta value? Not considering both restrictions would obviously cause almost random changes of "bestMove" at the root node.

[Henk]

What's wrong with this code. In case of timeout bestMove is skipped in the caller and iterative deepening loop is ended. Also bestMove and it's value is only set when not timeout has occurred. So I don't understand why it sometimes selects a really bad move.

Code: Select all

   public int SearchRoot(int depth, int initVal, out MoveBase bestMove)
        {
            int WINDOW_MARGIN = 2000;

            int factor = 1;
            int lb = initVal - factor * WINDOW_MARGIN;
            int ub = initVal + factor * WINDOW_MARGIN;


            int value = Search(depth, lb, ub, out bestMove, false); ;
            if (Expired())
                throw new TimeoutException();
            factor = factor * 4;
            do
            {

                while (lb >= value)
                {
                    lb = initVal - factor * WINDOW_MARGIN;
                    value = Search(depth, lb, ub, out bestMove, false);
                    if (Expired())
                        throw new TimeoutException();
                    factor = factor * 4;

                }

                while (ub <= value)
                {

                    ub = initVal + factor * WINDOW_MARGIN;
                    value = Search(depth, lb, ub, out bestMove, false);
                    if (Expired())
                        throw new TimeoutException();
                    factor = factor * 4;


                }
            }
            while (!(value > lb && value < ub));

            return value;
        }

This algorithm is a mess, there is absolutely no need for an outer loop containing two inner loops. What you need to do is only one loop where you always increase the window size at one end until the search does not fail low or high any longer. That would look like this:

Code: Select all

public int SearchRoot(int depth, int initVal, out MoveBase bestMove)
    {
        int WINDOW_MARGIN = 2000;

        int factor = 1;
        int lb = initVal - factor * WINDOW_MARGIN;
        int ub = initVal + factor * WINDOW_MARGIN;

        int value = Search(depth, lb, ub, out bestMove, false);
        if (Expired())
            throw new TimeoutException();
        while (value <= lb || value >= ub)
        {
            factor = factor * 4;
            if (value <= lb)
            {
                lb = initVal - factor * WINDOW_MARGIN;
            }
            else
            {
                ub = initVal + factor * WINDOW_MARGIN;
            }
            value = Search(depth, lb, ub, out bestMove, false);
            if (Expired())
                throw new TimeoutException();
        }

        return value;
    }

The other problem is your handling of "bestMove" in combination with your exception handling solution. How do you call your SearchRoot() function? I think you should better save the "bestMove" that is returned by SearchRoot() before starting the next iteration, since there will be a last iteration that stops on timeout, and what will it do with the "out" parameter "bestMove" which is owned by the caller (your iterative-deepening loop)? Will it leave the caller's "bestMove" untouched, or will it cause undefined behaviour, or what else? It is possible that you already take care of this, maybe I did not read carefully enough what you wrote.

Another question is, since "bestMove" is also an "out" parameter of function Search() of which I assume that it is called recursively throughout the whole full-width part of the search tree, do you ensure that Search() changes "bestMove" only when being called at the root node, and also only if the score of the new best move is inside the alpha/beta value? Not considering both restrictions would obviously cause almost random changes of "bestMove" at the root node.

I still think bug was or is in search. Haven't seen it recently but I did not play much.

Code: Select all

 
 public virtual int Search(int depth, int lb, int ub, out MoveBase bestMove, bool researched)
..

 if (entry != null && depth <= entry.Depth)
{
               ..
case TranspEntryType.LB:
                            if (entryValue >= ub)
                            {
                                bestMove = entry.BestMove;
                                return entryValue;
                            }
                            
                            // VVVV  probably the bug  
                            if (lb < entry.Value)
                            {
                                lb = entry.Value;
                            }
                            break;
..
}

[Sven]

I still think bug was or is in search. Haven't seen it recently but I did not play much.

Code: Select all

 public virtual int Search(int depth, int lb, int ub, out MoveBase bestMove, bool researched)
..

 if (entry != null && depth <= entry.Depth)
{
               ..
case TranspEntryType.LB:
                            if (entryValue >= ub)
                            {
                                bestMove = entry.BestMove;
                                return entryValue;
                            }
                            
                            // VVVV  probably the bug  
                            if (lb < entry.Value)
                            {
                                lb = entry.Value;
                            }
                            break;
..
}

Yes, this code looks suspicious, but not just the part you commented with "probably the bug", also the code above it. But I can't tell without seeing more of the Search() function.