checkmate puzzle solver

solver.ts

import { PrismaClient } from "@prisma/client";
import { Chess } from "chess.ts";
import { Puzzle } from "@prisma/client";

const prisma = new PrismaClient();

interface MoveNode {
  move?: string;
  fen: string;
  children: MoveNode[];
  evalScore?: number; // For move ordering
}

function solvePuzzle(puzzle: Puzzle) {
  function makeMove(move: MoveNode, ply: number = 0): number {
    const game = new Chess(move.fen);

    // if we are at the maximum ply, evaluate the position
    if (ply === puzzle.type * 2 - 1) {
      return game.inCheckmate() ? 1 : 0;
    }

    // otherwise, continue searching
    for (const m of game.moves()) {
      const newGame = game.clone();
      const gameMove = newGame.move(m);

      const child = {
        move: gameMove!.san,
        fen: newGame.fen(),
        children: [],
      } as MoveNode;

      move.children.push(child);
      const score = makeMove(child, ply + 1);
      child.evalScore = score;

      if (ply % 2 === 1 && score === 0) {
        return 0;
      }
    }

    if (ply % 2 === 0) {
      return (move.evalScore = Math.max(
        ...move.children.map((c) => c.evalScore!)
      ));
    } else {
      return (move.evalScore = Math.min(
        ...move.children.map((c) => c.evalScore!)
      ));
    }
  }

  function findWinningPaths(
    node: MoveNode,
    currentPath: string[] = []
  ): string[][] {
    // If no children, this is a terminal node
    if (node.children.length === 0) {
      return [currentPath];
    }

    // Find all children with evalScore of 1
    const winningChildren = node.children.filter(
      (child) => child.evalScore === 1
    );

    // If no winning children, return empty array
    if (winningChildren.length === 0) {
      return [];
    }

    // Recursively find paths through winning children
    return winningChildren.flatMap((child) => {
      const newPath = [...currentPath];
      if (child.move) {
        newPath.push(child.move);
      }
      return findWinningPaths(child, newPath);
    });
  }

  const node = {
    fen: puzzle.fen,
    children: [],
  };

  makeMove(node);
  const solutions = findWinningPaths(node);

  return solutions;
}

async function main() {
  let puzzles;

  // Normal mode: find all puzzles without solutions
  puzzles = await prisma.puzzle.findMany({
    where: {
      solutions: {
        equals: null,
      },
    },
  });

  for (const puzzle of puzzles) {
    const start_time = performance.now();
    const solutions = solvePuzzle(puzzle);
    const end_time = performance.now();
    console.log(`Solved puzzle ${puzzle.id} in ${end_time - start_time}ms`);
    console.log(`Solutions:`);
    solutions.forEach((solution) => {
      console.log("  ", solution.join(" -> "));
    });
    // // Update the puzzle with the solutions
    // await prisma.puzzle.update({
    //   where: {
    //     id: puzzle.id,
    //   },
    //   data: {
    //     solutions: solutions.length > 0 ? solutions.join(";") : null,
    //   },
    // });
  }
}

main().catch((err) => {
  console.error(err);
  prisma.$disconnect().finally(() => process.exit(1));
});