1

I've recently been improving my Negamax algorithm for chess, adding a transposition table. The algorithm was working well before this addition. After this addition I can't see no big improvements in speed, and sometimes I even see some regressions. I tested it with a depth of 5 and 6.

Is there any error in my code?

Here's the code, the new pieces are the commented lines at the top and at the bottom:

private int negaMax(Board board, Move[] legalMoves, int depth, int turnMultiplier, int alpha, int beta) {

    //Search in transposition table
    /*int initialAlpha = alpha;
    int transpositionDepth = 0;
    String transpositionFlag = "";
    int transpositionEvaluation = 0;
    String fenString = board.GetFenString().Split(" ")[0];
    if (transpositionTable.ContainsKey(fenString)) {
        transpositionDepth = Int32.Parse(transpositionTable[fenString].Split(" ")[0]);
        transpositionFlag = transpositionTable[fenString].Split(" ")[1];
        transpositionEvaluation = Int32.Parse(transpositionTable[fenString].Split(" ")[2]);

        if(transpositionDepth >= depth) {
            if(transpositionFlag.Equals("Exact")) { return transpositionEvaluation; }
            else if (transpositionFlag.Equals("Lowerbound")) { alpha = Math.Max(alpha, transpositionEvaluation); }
            else if (transpositionFlag.Equals("Upperbound")) { beta = Math.Min(beta, transpositionEvaluation); }

            if(alpha >= beta) { return transpositionEvaluation; }

        }
    }*/

    //Base case
    if (depth == 0) { return evaluatePosition(board) * turnMultiplier; }

    //Recursion
    int bestEvaluation = -infinity;

    foreach(Move move in board.GetLegalMoves()) {

        board.MakeMove(move);
        legalMoves = board.GetLegalMoves();
        orderMoves(legalMoves);
        int evaluation = -negaMax(board, legalMoves, depth - 1, -turnMultiplier, -beta, -alpha);

        if(evaluation > bestEvaluation) {
            bestEvaluation = evaluation;
            if (depth == searchDepth) { bestMove = move; }
        }

        board.UndoMove(move);

        //Pruning
        alpha = Math.Max(alpha, bestEvaluation);
        if(alpha >= beta) {
            break;
        }
    }

    //Transposition table update
    /*transpositionEvaluation = bestEvaluation;
    if (bestEvaluation <= initialAlpha) { transpositionFlag = "Upperbound"; }
    else if (bestEvaluation >= beta) { transpositionFlag = "Lowerbound"; }
    else { transpositionFlag = "Exact"; }
    transpositionDepth = depth;
    if (!transpositionTable.ContainsKey(fenString)) {
        transpositionTable.Add(fenString, transpositionDepth + " " + transpositionFlag + " " + transpositionEvaluation);
    }*/

    return bestEvaluation;
}
SecretAgentMan
  • 3,467
  • 2
  • 12
  • 44
SKAE
  • 11
  • 1

1 Answers1

2

I did not check the entire code in detail, however, two things that I noticed are: You seem to be using a generic hash map with a string as key and value. That seems very slow in my eyes, usually one uses a long as key instead which takes less space and is in general better to handle for the hash map. For the value, you can also stuff everything into a long, or, to stay more true to Java I suppose, you can create a class that has as members an integer for evaluation, a short for depth and an Enum (probably? Not a Java expert) for the bound type. On a more advanced level you would also write your own hash map since the generic one is not very good for this purpose, but that's something for another day I think.

Another thing I notice is you only add an entry if it is not already contained. However, even if the entry already exists you would still want to modify it if you improved the bounds with your search. And if you did a search then often you will have improved the bound because otherwise you would have already gotten a transposition table cutoff further up.

koedem
  • 3,285
  • 9
  • 22