perft function

int perft(Position pos, int depth, { bool shouldLog = false, })

Counts legal move paths of a given length.

Computing perft numbers is useful for comparing, testing and debugging move generation correctness and performance.

Implementation

int perft(Position pos, int depth, {bool shouldLog = false}) {
  if (depth < 1) return 1;

  final promotionRoles =
      pos is Antichess ? [..._promotionRoles, Role.king] : _promotionRoles;
  final legalDrops = pos.legalDrops;

  if (!shouldLog && depth == 1 && legalDrops.isEmpty) {
    // Optimization for leaf nodes.
    int nodes = 0;
    for (final entry in pos.legalMoves.entries) {
      final from = entry.key;
      final to = entry.value;
      nodes += to.size;
      if (pos.board.pawns.has(from)) {
        final backrank = SquareSet.backrankOf(pos.turn.opposite);
        nodes += to.intersect(backrank).size * (promotionRoles.length - 1);
      }
    }
    return nodes;
  } else {
    int nodes = 0;
    for (final entry in pos.legalMoves.entries) {
      final from = entry.key;
      final dests = entry.value;
      final promotions = from.rank == (pos.turn == Side.white ? 6 : 1) &&
              pos.board.pawns.has(from)
          ? promotionRoles
          : [null];
      for (final to in dests.squares) {
        for (final promotion in promotions) {
          final move = NormalMove(from: from, to: to, promotion: promotion);
          final child = pos.playUnchecked(move);
          final children = perft(child, depth - 1);
          if (shouldLog) print('${move.uci} $children');
          nodes += children;
        }
      }
    }
    if (pos.pockets != null) {
      for (final role in Role.values) {
        if (pos.pockets!.of(pos.turn, role) > 0) {
          for (final to in (role == Role.pawn
                  ? legalDrops.diff(SquareSet.backranks)
                  : legalDrops)
              .squares) {
            final drop = DropMove(role: role, to: to);
            final child = pos.playUnchecked(drop);
            final children = perft(child, depth - 1);
            if (shouldLog) print('${drop.uci} $children');
            nodes += children;
          }
        }
      }
    }
    return nodes;
  }
}