• FEATURED
• FEATURED
• FEATURED
• FEATURED
• FEATURED

View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Negascout behaves oddly

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

6 replies to this topic

### #1cryo75  Members

Posted 04 July 2013 - 04:28 AM

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)
{

//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

### #2Álvaro  Members

Posted 04 July 2013 - 05:43 AM

Does the bad behavior go away if you disable the transposition table?

I don't understand the logic of depths you are using. One typically stores the "depth left", or how many moves from the current position were analyzed in the search, and then an entry can be used if the depth stored is greater or equal than the depth required. The distance from the root is a less important number: You may think they encode the same information because their sum is constant, but that goes out the window with iterative deepening or with extensions and reductions.

### #3cryo75  Members

Posted 04 July 2013 - 06:04 AM

I commented out the transposition table code. It is not always playing better. In some games, the AI has a clear win on the next move, however it stays moving other unnecessary pieces. Looks like this happens more often in the endgame.

I use 2 depths because (as you can see from the code above), I do:

1. check if the current depth is the maximum depth (maximum being that of the current iterative of the ID) and if it is, I exit the function, and

2. if current depth == 0, then the search is at the root and I need to save the the move too.

I don't know how I can eliminate one depth variable.

Edited by cryo75, 04 July 2013 - 06:10 AM.

### #4Álvaro  Members

Posted 04 July 2013 - 07:12 AM

You should probably write a separate search function for the root, where you can implement iterative deepening, time control, returning a move, informing the user of the progress of the search...

I have nothing against keeping two depth variables (although my minimax searchers don't typically need both). What I was saying is that the depth stored in the hash table should be the depth left from here to the end of the tree, not the distance from the root.

EDIT: Oh, and you should definitely fix odd behaviors (like not winning right away when it is possible) before you add transposition tables, because transposition tables are hard to get right and make things harder to debug. You may need to make the winning score be something like (LARGE_NUMBER - length_of_the_game).

Edited by Álvaro, 04 July 2013 - 07:14 AM.

### #5cryo75  Members

Posted 04 July 2013 - 07:24 AM

What's the best way to fix the odd behaviors? Playing around with the values of the evaluation function?

Also, should the depth of the killer moves be the depth left (like the tt) or the current depth?

Edited by cryo75, 04 July 2013 - 10:15 AM.

### #6Álvaro  Members

Posted 04 July 2013 - 08:46 PM

The best way to fix the odd behaviors is to eliminate bugs, which you seem to have. The best way to do that is to start with as simple a program as possible and make sure that everything is working great. You then add sophistication one step at a time, making sure you didn't break anything.

It is very hard to find the bugs in a program that has lots of things coded in and where you have no idea which ones are correct and which ones aren't.

### #7Druzil  Members

Posted 04 July 2013 - 11:17 PM

One thing to look for when the AI is not taking the immediate win.  Is to see if the evaluation function discriminates between depth when it finds a win.  For instance, if a win is found at depth 2 and one at depth 5. It might choose the one at depth 5 which looks odd to a human - even if the win is still forced.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.