mtdf / negamax

engine.dart

// Aske Plaat's MTD(f) algorithm
  // Calls findBestMove a number of times with a gradually converging search window
  List mtdf(PositionN pos, int target, int depth) {
    int g = target;
    //pos.moves[0].score;
    int upper = MATE_UPPER;
    int lower = -MATE_UPPER;
    String bestMove = "";
    int pass = 1;
    while (lower < upper) {
      print("MTDF pass $pass");
      pass++;
      int beta = (g == lower) ? g + 1 : g;
      List result = findBestMove(pos, depth, beta - 1, beta);
      g = result[1];
      bestMove = result[0];
      if (g < beta)
        upper = g;
      else
        lower = g;
    }
    return [bestMove, g];
  }

  // top level function
  List findBestMove(PositionN pos, int depth, [int alpha = -MATE_UPPER, int beta = MATE_UPPER]) {
    nodesSearched = cutoffs = qNodes = nullCutoffs = tpLookups = 0;
    Stopwatch timer = new Stopwatch()..start();
    int startTime = timer.elapsedMilliseconds;
    List moves = pos.moves; // move generation function is in here
    //print(moves.map((e) => [e.name, e.score]).toList());
    List moveValues = [];
    List best = ["", -MATE_UPPER];

    for (MoveN move in moves) {
      PositionN newPos = pos.makeMove(move);
      String moveName;
      // if the position is null it means the move is invalid (i.e. it leaves the king in check, pins etc)
      if (newPos != null) {
        moveName = move.name;
        int value = -negamax(newPos, depth, 0, alpha, beta);
        moveValues.add([moveName, value]);
        if (value > best[1]) best = [moveName, value];
      }
      nodesSearched++;
      double elapsed = (timer.elapsedMilliseconds - startTime) / 1000;
      double nps = nodesSearched / elapsed;
      print(
          "$nodesSearched nodes searched so far, in ${elapsed.toStringAsFixed(2)}s (${nps.toStringAsFixed(2)} NPS) [cutoffs: $cutoffs, qNodes: $qNodes, nullCutoffs: $nullCutoffs, tpLookups: $tpLookups] {$moveName}");
    }

    moveValues.sort((a, b) => b[1].compareTo(a[1]));
    print(moveValues);
    return best;
  }

  int negamax(PositionN pos, int depth, int stage, int alpha, int beta, {bool allowNull = true}) {
    // Check transposition table hasn't grown too large
    if (tpScore.length > MAX_TRANSPOSITIONS) {
      print("Clearing transposition table for scores (${tpScore.length})");
      tpScore.clear();
    }

    // transposition table lookup
    int dhash = pos.dhash;
    List _tpScore = tpScore[dhash];
    if (_tpScore != null) {
      tpLookups++;
      if (_tpScore[0] >= beta) return _tpScore[0];
      if (_tpScore[1] <= alpha) return _tpScore[1];
      alpha = max(alpha, _tpScore[0]);
      beta = min(beta, _tpScore[1]);
    } else {
      tpScore[dhash] = [-MATE_UPPER, MATE_UPPER]; // default value is infinity window
    }

    bool qSearch = (depth <= 0);

    int value = -MATE_UPPER;
    List moves = (qSearch) ? pos.noisyMoves : pos.moves;
    if (depth < -QS_DEPTH) moves = [];
    int validMoves = 0;

    // stand pat
    if (qSearch && !pos.inCheck) {
      int standPat = engine.materialValue(pos.board, pos.player);
      if (standPat >= beta) return beta;
      if (alpha < standPat) alpha = standPat;
    }

    // null move heuristic
    if (allowNull && !pos.inCheck) {
      PositionN nullPos = pos.makeNullMove();
      nodesSearched++;
      if (nullPos != null) {
        int eval = -negamax(nullPos, depth - 3, stage + 1, -beta, -beta + 1, allowNull: false);
        if (eval >= beta) {
          nullCutoffs++;
          return eval;
        }
      }
    }

    // search moves
    if (moves.length > 0) {
      //if (tpMove[pos.hash] == null) tpMove[pos.hash] = moves[0];
      int a = alpha;
      for (MoveN move in moves) {
        PositionN newPos = pos.makeMove(move);
        nodesSearched++;
        if (qSearch) qNodes++;
        // if the position is null it means the move is invalid (i.e. it leaves the king in check, pins etc)
        if (newPos != null) {
          validMoves++;
          int eval = -negamax(newPos, depth - 1, stage + 1, -beta, -a);
          value = max(value, eval);
          a = max(a, value);
          //if (eval > value) tpMove[pos.hash] = move;
          if (a >= beta) {
            cutoffs++;
            break;
          }
        }
      }
    }

    // if we had no valid moves in this position
    if (validMoves == 0) {
      // if this is just a qSearch then we need to check no quiet nodes exist before
      // declaring this the end
      bool terminal = (qSearch) ? pos.isTerminal(!(depth < -QS_DEPTH)) : true;
      if (terminal) {
        if (pos.inCheck)
          value = -MATE_UPPER + ((stage + 1) ~/ 2); // checkmate
        else
          value = 0; // stalemate
      } else
        value = engine.materialValue(pos.board, pos.player);
    }

    // we need to do this again because the table can get cleared in a child node
    if (tpScore[dhash] == null) tpScore[dhash] = [-MATE_UPPER, MATE_UPPER];

    if (value <= alpha) tpScore[dhash][1] = value; // fail low implies an upper bound
    if (value > alpha && value < beta) {
      // found an accurate minimax value
      tpScore[dhash] = [value, value];
    }
    if (value >= beta) tpScore[dhash][0] = value; // fail high implies a lower bound

    return value;
  }