// Iterative Deepening Search
  // Calls mtdf at each depth until we hit the depth limit or run out of time
  List itSearch(Position pos, int timeLimit){
    nodesSearched = 0;
    tpLookups = 0;
    tpScore.clear(); // clear the transposition table for scores but not for moves

    Stopwatch timer = new Stopwatch()..start();
    int startTime = timer.elapsedMilliseconds;
    Move bestMove;
    double f = 0;
    int maxDepthSearched = 0;

    for(int depth = 1; depth <= MAX_SEARCH_DEPTH; depth++){
      int nodesSoFar = nodesSearched;
      tpScore.clear();
      pos.stage = 0;
      maxDepthSearched = depth;
      List _l = mtdf(pos, f, depth, timer, timeLimit);
      f = _l[0];
      if(true) bestMove = tpMove[pos.hash]; // if(_l[1]) -> only uses moves computed by a complete mtdf evaluation

      double timeTaken = (timer.elapsedMilliseconds - startTime) / 1000;
      int nodesHere = nodesSearched - nodesSoFar;
      double nps = nodesHere/timeTaken;
      print("Searched depth $depth: $nodesHere nodes in ${timeTaken.toStringAsFixed(2)}s (${nps.toStringAsFixed(2)} NPS)");
      print("Best move so far is ${bestMove.name}");
      if(timer.elapsedMilliseconds - startTime > timeLimit){
        print("Time limit hit");
        break;
      }
    }

    // This part is just for formatting lines to print to the console
    Map lines = Map();
    for(Move m in pos.moves){
      String mvName = formatMove(m);
      lines[mvName] = [(pos.board[PLAYER_TURN] == WHITE)?"${pos.board[FULLMOVE_COUNTER]} ":"", m.endPosition.eval];
      Position p = m.endPosition;
      Move nextMove = p.bestMove;
      bool first = true;
      while(p != null && nextMove != null){
        String next = formatMoveForList(p.board, nextMove, first);
        first = false;
        lines[mvName][0] += next;
        //print("Checking ${nextMove.name}");
        p = nextMove.endPosition;
        //print(p.bestMove);
        if(p != null) nextMove = p.bestMove;
        if(nextMove == null){
          //print("next move after ${p.previousMove.name} is null");
          break;
        }
      }
    }
    double timeTaken = (timer.elapsedMilliseconds - startTime) / 1000;
    double nps = nodesSearched/timeTaken;
    print("Iterative search terminated at depth $maxDepthSearched, having searched $nodesSearched nodes in ${timeTaken.toStringAsFixed(2)}s (${nps.toStringAsFixed(2)} NPS)");
    print("$tpLookups transposition table lookups");
    return [bestMove, f, lines];
  }

  // Aske Plaat's MTD(f) algorithm
  // Calls abm (Alpha-Beta with Memory) a number of times with a gradually converging search window
  List mtdf(Position pos, double target, int depth, Stopwatch timer, int timeLimit){
    double currentEstimate = target;
    var upper = MATE_UPPER;
    var lower = -MATE_UPPER;
    int pass = 1;
    while(lower < upper){
      double beta = max(currentEstimate, lower + 0.01);
      currentEstimate = -abm(pos, 1-pos.board[PLAYER_TURN], depth, 0, beta - 0.01, beta, true, false);
      print("MTDF pass $pass (currentEstimate: $currentEstimate), beta: ${beta.toStringAsFixed(2)} lower: ${lower.toStringAsFixed(2)}, upper: ${upper.toStringAsFixed(2)}");
      if(currentEstimate < beta) upper = currentEstimate;
      else lower = currentEstimate;
      pass++;
      if(timer.elapsedMilliseconds > timeLimit){
        print("Time limit hit in mtdf");
        return [currentEstimate, false];
        break;
      }
    }
    return [currentEstimate, true];
  }

  // Alpha-Beta with Memory (Negamax)
  double abm(Position pos, int player, int depth, int stage, double alpha, double beta, bool root, [bool allowNull = true]){
    //print("ABM");
    nodesSearched++;

    // Check transposition tables haven't grown too large
    if(tpMove.length > MAX_TRANSPOSITIONS){
      print("Clearing transposition table for moves (${tpMove.length})");
      tpMove.clear();
    }
    if(tpScore.length > MAX_TRANSPOSITIONS){
      print("Clearing transposition table for scores (${tpScore.length})");
      tpScore.clear();
    }

    // retrieve stored values from transposition table
    List _tpScore = tpScore[pos.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]);
      //print("($stage) tp lookup $alpha $beta");
    }else{
      tpScore[pos.dhash] = [-MATE_UPPER, MATE_UPPER];
    }

    double g;
    if(tpMove[pos.hash] == null) tpMove[pos.hash] = pos.moves[0];
    bool qSearch = (depth <= 0); // are we in quiescence search?
                                 // if so, only generate noisy moves (captures)
    List<Move> _moves = (!qSearch)?pos.moves:pos.moves.where((_m) => !_m.quiet).toList();
    //print("Moves: ${_moves.map((x) => x.name).toList()}");

    // Null-Move Heuristic
    // CURRENTLY DISABLED FOR SIMPLIITY / DEBUGGING
    if(allowNull){
      Move _nullMove = Move.nullMove(pos);
      double eval = -abm(_nullMove.endPosition, 1-player, depth - 3, stage + 1, -beta, -beta+0.0001, false, false);
      if(eval >= beta){
        pos.eval = eval;
        return eval;
      }
    }
    // ---------

    // -10 means 10 moves into quiescence search, increasing doesn't change much except massively slowing everything down
    if(_moves.length == 0 || depth <= -10) g = (player != pos.analysisPlayer)?pos.score:-pos.score; // if we've hit the end of the evaluation
    else{
      if(qSearch){ // STAND PAT
        double stand_pat = (player != pos.analysisPlayer)?pos.score:-pos.score;
        if(stand_pat >= beta) return beta;
        if(alpha < stand_pat) alpha = stand_pat;
      }

      g = -MATE_UPPER;
      double a = alpha;

      for(Move m in _moves){
        if(m.valid){
          m.endPosition.eval = -abm(m.endPosition, 1-player, depth - 1, stage + 1, -beta, -a, false, false);

          if(m.endPosition.eval > g){
            tpMove[pos.hash] = m;
            pos.bestMove = m;
            g = m.endPosition.eval;
          }

          if(g > a){
            a = g;
            tpMove[pos.hash] = m;
            pos.bestMove = m;
          }
        }

        // CUTOFF
        //if(a >= beta) break;
      }
    }

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

    return g;
  }