I have a negascout function within an iterative deepening with aspiration windows framework. The negascout function uses move ordering, transposition tables, killer moves and history heuristics. The game is a nine men's morris (yes.. still working on it in my free time!!)

The problem is that over 70% of the time, the AI is not that aggressive, ie. when the AI has a chance to capture pieces, it doesn't.

This is the function:

private int negaScout(int curDepth, int maxDepth, int alpha, int beta) { if (curDepth >= maxDepth || board.getWon() != 0) return board.getScore(); //Check if the move is in the TT long key = board.getZobristKey(); TTEntry entry = tt.probe(key, curDepth); if (entry != null) { switch (entry.boundType) { case TTEntry.BOUND_EXACT: return entry.score; case TTEntry.BOUND_ALPHA: alpha = Math.max(alpha, entry.score); break; case TTEntry.BOUND_BETA: beta = Math.min(beta, entry.score); break; } if (alpha >= beta) return entry.score; } int val = 0; int bestScore = -INFINITY; Move bestLocalMove = null; boolean foundPV = false; List<Move> moves = sortMoves(board, curDepth, false); for (int i = 0, n = moves.size(); i < n; i++) { Move move = moves.get(i); //PV has been found if (alpha < bestScore) { alpha = bestScore; foundPV = true; } board.make(move, true); if (foundPV) { //Zero window val = -negaScout(curDepth + 1, maxDepth, -alpha - 1, -alpha); if (val > alpha && val < beta) val = -negaScout(curDepth + 1, maxDepth, -beta, -alpha); } else val = -negaScout(curDepth + 1, maxDepth, -beta, -alpha); board.undo(move, true); //Alpha has improved if (val > bestScore) { bestScore = val; bestLocalMove = move; //Beta cut-off if (bestScore >= beta) break; } } //We have the current best move so far at the root if (curDepth == 0) bestMove = bestLocalMove; //Set TT entry flag byte flag = bestScore <= alpha ? TTEntry.BOUND_BETA : bestScore >= beta ? TTEntry.BOUND_ALPHA : TTEntry.BOUND_EXACT; //Store the move in the TT tt.set(key, curDepth, bestScore, flag, bestLocalMove); if (bestLocalMove != null) { //Add to killer moves killers.add(bestLocalMove, curDepth); //Update history heuristics for non-captures if (bestLocalMove.cellRemove == -1) history[bestLocalMove.player][bestLocalMove.cellFrom + 1][bestLocalMove.cellTo + 1] += 1<<(maxDepth-curDepth); } return bestScore; }

This is the transpostion table:

public class TranspositionTable { private TTEntry[] tt; public TranspositionTable(int size) { tt = new TTEntry[size]; } public TTEntry probe(long key, int depth) { TTEntry entry = tt[(int)(key % tt.length)]; if (entry != null && entry.depth <= depth) return entry; return null; } public void set(long key, int depth, int val, byte boundType, Move move) { int pos = (int)(key % tt.length); tt[pos] = new TTEntry(key, depth, val, boundType, move); } }

As you can see in the transposition table, I always do a replace in the 'set' function. However, when I probe, I get the entry only if the entry's depth is smaller than the depth required. By depth here, I mean that depth from the root node, so the smaller the depth the nearer the entry is to the root move.

Is it possible that I'm probing/setting wrong values or could it be the part of the code when the 'Alpha has improved' comment is?

Thanks,

Ivan