1
\$\begingroup\$

I'm currently in the process of writing my own chess engine in java and am having a little trouble with negamax. I've opted for negamax since its easier on the eyes and reduces the number of lines of code. My specific problem is that after making a move (me) the negamax algorithm returns scores of -Infinity and so the moves the AI is making seems illogical.

The problem only happens when I return beta if score>=beta instead of returning score. Here is my function:

private int Search(int side, int depth, int alpha, int beta, long bitBoard, long[][][] allPieces, HashMap<Integer, Pair> pieceInfoTable,boolean allowNull){
    int turn;
    if (side == 1) {
        turn = 0;
    } else {
        turn = 1;
    }   
    long hash = zobrist.getZobristHash(allPieces,pieceInfoTable, turn);

    if (zobristMap.containsKey(hash)) {
        int storedDepth = zobristMap.get(hash).getDepth();
        int score = zobristMap.get(hash).getScore();
        NodeType nodeType = zobristMap.get(hash).getNodeType();
        if (storedDepth >= depth) {
            if(nodeType == NodeType.PV){
                return score;
            }
            if(nodeType == NodeType.CUT_OFF_NODE){
                alpha = Math.max(alpha,score);
            }else if(nodeType == NodeType.ALL_NODE){ 
                beta = Math.min(beta,score);
            }
            if(score >= beta){
                return score;
            }
        }
    }
    MoveTable moveTable = new MoveTable();
    MoveGenerator.updateMoveMoves(bitBoard, moveTable, turn, allPieces);
    if (depth <= 0) {
        int score;
        int quiescenceDepth = 1;
        if(moveTable.pieceCaptureMoves.size() > 0){
            score = quiescenceSearch(side, alpha, beta, quiescenceDepth, bitBoard, allPieces, turn, pieceInfoTable);
        }
        else {
            score = Rating.rate(allPieces, bitBoard,pieceInfoTable);
        }

        NodeType nodeType = getNodeType(score, beta, alpha);
        zobristMap.put(hash,new TranspositionTableEntry(score, depth,nodeType));
        
        return score;
    } 

    int terminal = terminalCheck(turn, side, bitBoard, allPieces,pieceInfoTable,moveTable);

    if(terminal != 0){
        NodeType nodeType = getNodeType(terminal, beta, alpha);
        zobristMap.put(hash,new TranspositionTableEntry(terminal, depth,nodeType));
        return terminal;
    }

    
    int value; 
    int R=2;
    int x = Integer.MIN_VALUE;
    
    if(depth-R-1 >= 0&&allowNull&&!inCheck(turn,bitBoard,allPieces)){
        x = -Search(-side, depth - 1 - R, -beta,-beta+1, bitBoard, allPieces,pieceInfoTable,false);
        if(x >= beta){
            return beta;
        }
    }

    int bestSoFar = Integer.MIN_VALUE;
    moveOrdering(bitBoard, allPieces,moveTable, turn,pieceInfoTable);
    for(Move move : moveTable.pieceMoves){
        
        int pieceTile = move.getPieceTile();

        int targetTile = move.getTargetTile();
        if (BoardAnalyser.checkIfValidMove(pieceTile, targetTile, bitBoard, allPieces, turn,pieceInfoTable)) {

            int capFlag = Utils.getCaptureFlag(bitBoard, targetTile);

            Pair[] z = {null};
            bitBoard = Utils.makeMove_test(pieceTile, targetTile, bitBoard, z, turn, allPieces,pieceInfoTable);

            value = -Search(-side, depth - 1, -beta, -alpha, bitBoard, allPieces,pieceInfoTable,true);
            bitBoard = Utils.unmakeMove_test(pieceTile, targetTile, bitBoard, capFlag, z, turn, allPieces,pieceInfoTable);
            
            if(value > bestSoFar){
                bestSoFar = value;
            }
            if(bestSoFar >= beta){
                history[pieceTile][targetTile][turn] += depth*depth;
                zobristMap.put(hash,new TranspositionTableEntry(bestSoFar, depth,NodeType.CUT_OFF_NODE));
                return beta;
            }
            if(bestSoFar > alpha){
                alpha = value;
            }
        }
    }
    NodeType nodeType = getNodeType(bestSoFar, beta, alpha);
    zobristMap.put(hash,new TranspositionTableEntry(bestSoFar, depth,nodeType));
    return bestSoFar;   
}

I'd appreciate any help/tips that I can get on this issue. If you require more information (code/explanation) then I'd be happy to help you help me :)

Thank you!

\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

I'm not sure if this is what's wrong, but beware that:
(-Integer.MIN_VALUE) == Integer.MIN_VALUE

Because of that I'd suggest using a different integer to represent negative infinity (e.g. -1000000000).

See the Stack Overflow post why does the negative of integer min value give the same value for more information.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for your swift response! I replaced all -inf to and inf to 1000000000 in my code. While that did stop the code from outputting -inf scores, I now after a single move get outputs that contain the occasional inf(s) which doesn't seem right at all. Heres an example output: 0 -10 -10 885 -30 -10 -15 -30 -5 -20 20 5 10 -5 1000000000 1000000000 -25 -30 45 \$\endgroup\$
    – AF_
    Jan 30, 2023 at 8:31
  • \$\begingroup\$ To make the move, the ai chooses the score with the minimum value, but since 2 results are skewed, what are the chances that more (or all) of the results or skewed. As you may have noticed, I've implemented zobrist hashing, null move pruning, and move ordering (history heuristic + MVV/LVA, and quiescence search. Would you be willing to take a look at my implementations? Since I'm confident they are implemented correctly but there could be a small bug that I just haven't picked up on yet. Thanks again! \$\endgroup\$
    – AF_
    Jan 30, 2023 at 8:33
0
\$\begingroup\$

I cant recall exactly what I did. But the biggest change I made was with the evaluation function. I wasn't returning a score respective to the game perspective.

Initially I just returned (sumWhite - sumBlack) but replaced that with:

/*currentScore -> return val -> enemside perspective 
 * score >0 white winning 
 * if turn = 1 return score (bad for black) x -> x -> -x
 * if turn = -1 return -score (good for white) x ->-x -> x
 * 
 * score < 0 black winning
 * if turn = 1 return score (good for black) -x -> -x -> x
 * if turn = -1 return -score (bad for white) -x-> x -> -x
 */
int score = sumWhite-sumBlack;
if(score != 0){
    if(turn == 1){
   
        return score;
    }
    if(turn == -1){
       
        return -score;
    }
}
\$\endgroup\$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .