Hi people! I'm working on a project for the university and the project is to develop an algorithm to play an othello game against another algorithm. I've already done a minimax + alpha beta pruning version with a quite good evaluation function. I'm trying to develop a negascout version using the same evaluation function. However it doesn't work as expected. I've implemened the algorithm in java after seeing several pseudocodes of negascout on wikipedia. I'm doing more or less like this (pseudocode): iterative deepening search{ if depth is even score = negascoutEven(rootNode, -10000, 10000, myplayer, currenthDepth) else score = negascoutOdd(rootNode, -10000, 10000, myplayer, currenthDepth) currenthdepth++; } double negascoutOdd(node, alpha, beta, playerToMove, depth): if depth == 0 return -EvaluationFunction(); then there's the normal negascout algorithm with negated recursive calling to negascoutOdd, swapping every time the player double negascoutEven(node, alpha, beta, playerToMove, depth): if depth == o return EvaluationFunction(); then there's the normal negascout algorithm with negated recursive calling to negascoutEven, swapping every time the player The evaluation function is always evaluated wrt my algorithm (i evaluate always for myplayer, instead for playertomove) I don't understand why it doesn't work even if the evaluation function is the same for both minimax versin and this one. If someone wants, i can provide some more code. Thanks for ur help

It's hard to debug your code from a vague description. Set up a very simple example and see what your code does by executing it step by step.

Why are you using two negascout functions? The best part of using the negamax convention of always considering scores from the point of view of the player to move is that you can write just one function. A simple if-statement at the top of the function will take care of the sign change, or you could just change the interface to your evaluation function so it returns a value with the negamax convention.

Well,you're right for that thing of the advantages of negamax of having just one function, but i found it harder to debug. But for sure i'd like to have just one function at the end.
Here's the code of the calling method:
public void run() {
int currentDepth = 1;
int maxDepth = startState.getMarkCount(-1) >= 10? 11 : startState.getMarkCount(-1) + 1;
running = true;
if (startState.getPossibleMoveCount(myPlayer) == 0) {
selectedMove = null;
} else {
double alpha = -1000000;
double beta = 1000000;
double score;
while(running && currentDepth < maxDepth) {
if(currentDepth % 2 == 0){
score = negascoutPar(startState, alpha, beta, currentDepth, myPlayer, currentDepth, startState);
}else{
score = negascoutDis(startState, alpha, beta, currentDepth, myPlayer, currentDepth, startState);
}
currentDepth += 1;
}
}
if (running) {
controller.doMove(selectedMove);
}
}

And here is the negascout function:
@SuppressWarnings("unchecked")
private double negascoutDis(GameState g, double alpha, double beta,
int currentDepth, int player, int maxDepth, GameState old) {
if(currentDepth == 0) return -Evaluator.evaluateBoard(g, myPlayer, old, endgame);
Vector<Move> moves = g.getPossibleMoves(player);
if(moves.size() == 0) return g.getMarkCount(myPlayer) > g.getMarkCount(1-myPlayer) ? -50000 : 50000;
double a, b, score, bestScore = -1000000;
a = alpha;
b = beta;
for(int i=0; i<moves.size() && running; i=i+1){
MoveF move= new MoveF(moves.elementAt(i));
score = -negascoutDis(g.getNewInstance(move), -b, -a, currentDepth-1, 1-player, maxDepth, g);
if(score > a && score < beta && i > 0){
a = -negascoutDis(g.getNewInstance(move), -beta, -score, currentDepth-1, 1-player, maxDepth, g);
}
a = a > score ? a : score;
if(currentDepth == maxDepth){
if(a > bestScore){
selectedMove = move;
selectedMove.setScore(a);
bestScore = a;
}
}
if(a >= beta) return a;
b= a+1;
}
return a;
}
The negamaxEven is similar except when it return for depth == 0 there isn't the minus sign in front of the function.
Then the part of bestScore and selectedMove is there because the function retuns a double, but i need to save the corresponding move.
Actually, i've done a test version of this thing using simple nodes and not the real game, and the test version works (it's done too with the double functions).
I'm really loosing my patience here, it's more than 2 weeks that i'm on this function and i cannot understand what's wrong.
Is it right to have the check of currentDepth == maxdepth and then if a > bestscore in that way so i can save the best move? or should if be done outside the for loop (even though then i'd not know how to save the move...)

Your code was quite illegible the way you posted it. Please use [ source ] [ / source ] tags.

While I havent really studied your code, I have worked on an othello tree searcher and one thing stands out immediately:

The lack of legal moves is not an indication that the game is over, and the ply is probably not an indication of whos move it is unless you are counting passes as a ply (which you dont seem to be doing because you arent even handling passes)

While this probably doesnt solve the issue you raised, it is definately an issue you will need to tackle.

I have never implimented pvs (aka scout) .. I figure if I am going to be using null window alphabeta's I might as well go all out and use MTF(f)

edited to add:

Additionally, you had said that your eval() doesnt care whos move it is and returns a score based on a specific player, but it appears like you are actualy treating it like a nega* eval which returns a score based on whos move it is. I am assuming that it must be the later case and if that is so, why are you negating its return value?