Is this valid iterative deepening code??

   public Move GetBestMove(IBoard board, int depth)
    {        
    	this.maxDepth = 100;
    	this.maxTime = 9000;
    	
        //Set initial window
    	int alpha = -INFINITY, beta = INFINITY;
        
        //The move that will be returned
        Move bestMove = null;      
        List<Move> moves = board.getMoves();
        
        //Get the time search has started
        long startTime = System.nanoTime();
        
        //Iterate through the depths
        for (int i = 0; i < maxDepth; i++)
        {
        	bestMove = negaScoutRoot(board, alpha, beta);
        	int val = bestMove.score;
        	
        	//Time check
        	double curTime = (System.nanoTime() - startTime) / 1e6;
        	if (curTime >= maxTime)
        		return bestMove;
        	
        	//Score missed aspiration window
        	if (val <= alpha || val >= beta)
        	{
        		alpha = -INFINITY;
        		beta = INFINITY;
        		
        		//Go to next iteration
        		continue;
        	}
        	
        	//Set new aspiration window
        	alpha = val - ASPIRATION_SIZE;
        	if (alpha < -INFINITY)
        		alpha = -INFINITY;
        	
        	beta = val + ASPIRATION_SIZE;
        	if (beta > INFINITY)
        		beta = INFINITY;
        }
		
		//Return the move
        return bestMove;
    }
    
    private Move negaScoutRoot(IBoard board, int alpha, int beta)
    {        
        //The move that will be returned
        Move bestMove = null;      
        List<Move> moves = board.getMoves();
        
        for (Move move : moves)
        {
         	//Make the move
        	board.make(move, true);

        	//Search
            int val = -negascout(board, 0, alpha, beta);
               
            //Undo the move
            board.undo(move);
            
            //Keep best move
            if (val > alpha)
            {
                alpha = val;
                
                bestMove = move;
                bestMove.score = alpha;
            }
        }
		
		//Return the move
        return bestMove;
    }

I also added aspiration window. The root always starts searching from the current board state but with a different window.

Setting alpha to -infinity should be done inside the loop over depths. I would combine both functions into one. The division as you have it is a bit odd: Why do both functions have a list of moves?

I implement aspiration search differently, where I try the narrow window only for the first move. If the result is outside the window, I search that first move again with full window. The rest of the moves are explored with null windows to test if they are better than alpha, following the PVS algorithm (I believe NegaScout is essentially the same thing).

The moves variable in the getbestmove() is not required. I forgot it that. I will change the code as you suggest and have just one function that will in turn call the recursive search.

One advantage of having the list of moves persist from iteration to iteration is that you can keep it sorted. Whenever you find a new best move, you move it to the top of the list, sliding down the moves that were before it.

Ok now I have the main deepening loop and inside it the loop to iterate through the moves. Should the aspiration window check be inside the second loop (moves) or move outside to the main loop?

There are several ways of doing aspiration search. You could search the first move before the loop starts, and then it would look something like this:

int score_guess = 0;

for (int depth=1; depth<100 && !out_of_time(); ++depth) {
  board.make_move(moves[0]);
  int alpha = -negamax(board, score_guess - 25, score_guess + 25, depth - 1);
  board.undo_move(moves[0]);
  
  if (alpha <= score_guess - 25 || alpha >= score_guess + 25) {
    board.make_move(moves[0]);
    alpha = -negamax(board, -Infinity, +Infinity, depth - 1);
    board.undo_move(moves[0]);
  }
  
  for (int i=1; i<n_moves; ++i) {
    //...
  }
  
  score_guess = alpha;
}

NOTE: I didn't test this code, so there might be mistakes.

This is the updated code:

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

        	//Set the current best score
        	scoreGuess = alpha;
        }
		
		//Return the move
        return bestMove;
    }

After the 17th move and it's the AI's turn again, the search enters an infinite loop.

I can't figure out why, because the code looks good to me. However, the negascout function has the following checks:

This one at the top:

        //Horizon has been reached
        if (depth == curDepth)
        {
        	t = board.getScore();
        	return t;
        }

And this one when searching deeper (inside the move loop):

            t = -negascout(board, depth + 1, -b, -a, startTime);
            if ((t > a) && (t < beta) && (i > 0) && (depth < curDepth - 1))
            	t = -negascout(board, depth + 1, -beta, -t, startTime);

Could it be that curDepth is wrong here?

	int val = -negascout(board, curDepth - 1, alpha, beta, startTime);

That's clearly wrong: You need to use (-beta, -alpha) as the window, like in every other invocation of negamax.

You also seem to be confused as to what `depth' means. Usually it means how many more moves we are going to explore. So you pass depth-1 in the recursive calls, and when it reaches 0 you return the static evaluation function (or you call quiescence search).

As for the part where your program gets stuck in an infinite loop, you'll have to find your own bugs, sorry.

Ok changed the code you pointed out. As you can see from the snippet above my version of negascout does depth+1 in the recursive function, so I will never hit 0. But I changed 0 to curDepth (which is the current depth of the loop).

The infinite loop resulted from some inconsistencies with the setting up of variables within the ID loop.

I've run a few tests and I noticed that with ID, the moves search are around 4000-6000 compared to over 200000 when using just negascout without ID. Is it possible that there is such a big cut ?

Now the next step is to add history heuristics. If I understand correctly, hh is just a table that increments a counter on every beta cut-off. Then in the next call to the recursive function, the generated moves are sorted by the counter value (or weights depending on the move type) for that index. Am I right?

So in the case of the nine men morris game I'm doing, i will have this hh:

int[color][posFrom][posTo] hh = new int[2][24][24]

During placement stage, I will only have one position, so when incrementing the hh counter, should I check what kind of move it is?