Iterative Negascout

[cryo75]

Hi all,

I'm new here and also new to AI programming in general. I started writing a simple chess engine and have already implemented move generation and evaluation. I also have a working Negascout search with TT and kill moves. Now I decided to add iterative deepening, so I pasted (more or less) the root function into a loop. This is what I came up with:

Code: Select all

    public Move GetBestMove(IBoard board)
    {       
       //Search limits
       this.maxTime = 2000;
       this.maxDepth = 100;
       
       int alpha = -INFINITY, beta = INFINITY;
       
        Move bestMove = null;     
        List<Move> moves = board.getMoves();
       
        startTime = System.nanoTime();
       
        for (curDepth = 1; curDepth < maxDepth && !outOfTime(); curDepth++)
        {
           alpha = -INFINITY;
           beta = INFINITY;
           
           //Reset the best score position
           int bestPos = -1;
           
            for (int i = 0, n = moves.size(); i < n; i++)
            {
               board.make(moves.get(i), true);
                int val = -negascout(board, 0, -beta, -alpha);
                board.undo(moves.get(i));
               
                //Keep best move
                if (val > alpha)
                {
                    alpha = val;
                    bestMove = moves.get(i);
                }
            }
           
           //Move the best move to the top of the list
           if (bestPos != -1)
           {
              moves.remove(bestPos);
              moves.add(0, bestMove);
           }
        }
      
      //Return the move
        return bestMove;
    }



This is the basic code that I added. However if I get this working, I would like to add aspiration windows to it and also HH to the negascout function.

Back to my problem... when using just Negascout, the search goes through about 300k moves, and when using ID, the search goes through 4-5k moves, which is quite a large cut. So now I don't know if the ID loop is working or there is a bug somewhere and it's just search the same move over and over again till time's up.

Any ideas?

Thanks,
C

[Ron Murawski]

Code: Select all

           //Move the best move to the top of the list
           if (bestPos != -1)
           {
              moves.remove(bestPos);
              moves.add(0, bestMove);
           }


The above code will never be executed because bestPos is initialized to -1 and then never changed.

Ron

[cryo75]

Ahh yes good catch. I now have managed to implement ID, however the root moves are now treated the same as other moves in the negascout function and I keep a global variable bestMove to keep the next move if depth = 0.