0
\$\begingroup\$

I'm trying to implement negamax in my checkers game. Sometimes the IA does the appropriate move, sometimes don't. Here is my code:

private int evalPawns(ArrayList<Pawn> pawns, int turn){
    int whiteCount=0;
    int blackCount=0;
    int who2move;
    if(turn == GameData.PLAYER1)
        who2move = -1;
    else
        who2move = 1;
    for(Pawn pawn:pawns){
        if(pawn.getPlayer() == GameData.PLAYER1){
            whiteCount++;
        } else {
            blackCount++;
        }
    }
    return  (whiteCount-blackCount) * who2move;
}

public int negaMax(ArrayList<Pawn> pawns, int depth, int turn){
    ArrayList<Pawn> pawnTemp;
    pawnTemp = copyPawns(pawns);

    Move[] legalMoves = getLegalMoves(turn, pawnTemp);
    int maxScore = Integer.MIN_VALUE;

    if(depth == 0 || legalMoves == null) 
        return evalPawns(pawns, turn);

    for(Move move:legalMoves){
        makeMove(move, pawnTemp);
        int score = -negaMax(pawnTemp, depth-1, opponent(turn));
        maxScore = Math.max(maxScore, score);
    }
    return maxScore;
}


public Move findMaxMove(Move[] legalMoves, ArrayList<Pawn> pawns){
    int maxScore = Integer.MIN_VALUE;
    Move bestMove = null;
    for (Move move:legalMoves){

        makeMove(move);

        int newScore = -negaMax(pawns, 5, GameData.PLAYER2);
        if (newScore > maxScore){
            maxScore = newScore;

            bestMove = element;
        }

    }
    return bestMove;
}

Here are 2 moves examples: 1st Move 2nd Move

\$\endgroup\$
  • \$\begingroup\$ This will be much easier to debug if you can exhibit one or more illustrated examples of the form "Here is the configuration before the AI moves; here is the expected move; here is the move the AI takes instead" otherwise you're basically asking the Internet to debug your code for you. \$\endgroup\$ – DMGregory Apr 16 '14 at 15:10
  • \$\begingroup\$ Edited and added examples \$\endgroup\$ – spellz Apr 17 '14 at 10:08
0
\$\begingroup\$

At first glance, it looks like you have the algorithm correct. The part that jumps out as possibly wrong is this:

if(maxScore == 0){
    bestMove = moves[rand.nextInt(moves.length)];
}

maxScore of 0 means that the best move the AI can make will lead to no change in the relative number of pieces per player (assuming both sides continue to play correctly). I would expect that to happen a lot in checkers. Choosing a random move in that situation seems like a bad idea.

The other thing you haven't covered is what happens when there is no legal move to make. That should be scored as a game loss for the player whose turn it is.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Edited in order to show an example \$\endgroup\$ – spellz Apr 18 '14 at 8:48
0
\$\begingroup\$

For any adversarial search you need to be sure your evaluation function is consistent with the implementation, the move iteration is correct for each turn, that you are reversing any applied moves properly, and that your initial invocation is correct.

It looks to me as if you are not calling it properly for the second player, for the first player the invocation is normally negamax(node, depth, 1), but for the second player it is normally -negamax(node, depth, 1).

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ If I check what turn is before calling the recursion(if is Player1 turn, then -Negamax(..) else Negamax(..)) the move it makes is the same, except the fact thet the evaluation gives 0 instead of 1 \$\endgroup\$ – spellz Apr 17 '14 at 15:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.