Iterative Negascout

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

Iterative Negascout

Postby cryo75 » 21 Mar 2013, 11:16

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
cryo75
 
Posts: 2
Joined: 21 Mar 2013, 10:02

Re: Iterative Negascout

Postby Ron Murawski » 22 Mar 2013, 07:04

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
User avatar
Ron Murawski
 
Posts: 352
Joined: 26 Sep 2004, 21:50
Location: Schenectady, NY, USA

Re: Iterative Negascout

Postby cryo75 » 22 Mar 2013, 10:25

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.
cryo75
 
Posts: 2
Joined: 21 Mar 2013, 10:02


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 1 guest