/* matefinder.c -- find forced checkmates up to a given number of
 * moves (default 4), starting from an arbitrary FEN position, using
 * the SAN Kit library.
 *
 * Usage:
 *   matefinder [-d MAXMOVES] [-t SECONDS] "FEN"
 *
 * "Mate in N moves" means the side to move can force checkmate
 * within N moves of their own, however Black replies in between --
 * i.e. up to 2N-1 plies (N of the attacker's, N-1 of the
 * defender's). This is a different, much harder question than
 * "does any single move deliver mate right now" (see
 * demos/xboard-engine-tactical, which only ever looks one move
 * ahead): proving a forced mate in N requires that EVERY legal
 * defensive reply, at every intermediate step, still allows the
 * attacker to complete the mate within the remaining budget. This
 * is a two-player AND/OR search: OR over the attacker's own move
 * choices (only one needs to work), AND over the defender's
 * replies (every one of them must fail to escape).
 *
 * How the search works
 * ---------------------
 * SolveMate() below tries increasing move budgets, one move at a
 * time (a mate in 1 is checked before ever trying for a mate in 2,
 * and so on), so the shortest forced mate is always the one
 * reported.
 *
 * At each node it is the attacker's turn to move. For each of the
 * attacker's legal moves (SANGenMoves() already flags any of them
 * that deliver immediate mate, via SANMLScanMate() -- see
 * sanmlm.c -- so an immediate mate needs no further search at all):
 *
 *   - if the move mates outright, that's a solution for this budget;
 *   - otherwise, if there's more than one move of budget left, try
 *     the move and recursively check *every* legal reply the
 *     defender has: if even one of them lets the defender avoid
 *     mate within the remaining budget (or if the defender has no
 *     legal moves at all but isn't in check, i.e. stalemate), this
 *     attacker move is rejected and the next one is tried instead.
 *
 * Moves are tried in "checks and captures first" order, since a
 * checking move sharply limits the defender's replies (fewer
 * branches to verify) and is simply far more likely to be part of
 * an actual mating sequence than a quiet one -- this is what keeps
 * the search fast enough for a simple demo tool on typically
 * forcing positions, without any real evaluation function or
 * transposition table.
 *
 * Moves are simulated with SANExecute()/SANRetract() (the same
 * lightweight, history-free primitive pair SANEnumerate() and
 * demos/xboard-engine-tactical's own 1-ply safety check use), never
 * SANPlayMove(), so none of this touches the real game history --
 * only the final, verified solution line is ever actually "played"
 * (see main(), for the replay-and-display step at the end).
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>

#include "sandef.h"
#include "sanvar.h"

#include "sanint.h"
#include "sangen.h"
#include "sanmer.h"
#include "sanmpu.h"
#include "sanmne.h"
#include "sanmsc.h"
#include "sanfen.h"
#include "sanrst.h"
#include "sandsp.h"

/* a solution line for "mate in MAXMOVES" needs at most
   2*MAXMOVES - 1 moves; this generous fixed bound comfortably
   covers any MAXMOVES this tool would reasonably be asked for */
#define LINE_MAX 64

/* search node accounting, purely to let a time budget be enforced
   without calling clock() on every single node (which would be
   needlessly expensive) */
static unsigned long nodes;
static clock_t deadline;
static siT timed_out;

/*--> OrderKey: sort key used to try checks, then captures, then
      everything else -- see the file header comment for why */
static siT
OrderKey (mptrT mptr)
{
  if (mptr->m_flag & mf_chec)
    return (0);
  if (cv_p_scmvv[mptr->m_scmv] != p_x)     /* a promotion */
    return (1);
  if (valcpv[mptr->m_tocp] > 0)            /* a capture */
    return (2);
  return (3);
}

/*--> OrderMoves: sort curr_g.g_base[0..n) in place by OrderKey();
      a plain insertion sort is more than fast enough here since n
      is at most a few dozen */
static void
OrderMoves (siT n)
{
  siT i, j;
  mT tmp;

  for (i = 1; i < n; i++)
    {
      tmp = curr_g.g_base[i];
      j = i;
      while ((j > 0) && (OrderKey (&curr_g.g_base[j - 1]) > OrderKey (&tmp)))
        {
          curr_g.g_base[j] = curr_g.g_base[j - 1];
          j--;
        };
      curr_g.g_base[j] = tmp;
    };

  return;
}

/*--> SolveMate: look for a forced mate within "budget" moves of the
      side currently to move; on success, fills "line" with the
      winning sequence (budget's own move, a defensive reply,
      budget-1's move, another reply, ... the final mating move) and
      sets *linelen to its length; returns 1 on success, 0 if no
      such forced mate exists (or the search was abandoned early --
      see "timed_out", which the caller must check separately, since
      a plain 0 return alone can't distinguish "proven impossible"
      from "search cut short") */
static siT
SolveMate (siT budget, mT *line, siT *linelen)
{
  siT i, j, n, m2;
  mptrT cand, reply;
  mT save_cand;

  if (timed_out)
    return (0);
  if ((++nodes % 4096) == 0 && (clock () >= deadline))
    {
      timed_out = 1;
      return (0);
    };

  SANGenMoves ();
  n = curr_g.g_gmvc;
  OrderMoves (n);

  for (i = 0; i < n; i++)
    {
      cand = &curr_g.g_base[i];

      if (cand->m_flag & mf_chmt)
        {
          line[0] = *cand;
          *linelen = 1;
          return (1);
        };

      if (budget == 1)
        continue;               /* no budget left to search deeper */

      save_cand = *cand;
      curr_g.g_curr = cand;
      SANExecute ();

      SANGenMoves ();
      m2 = curr_g.g_gmvc;

      if (m2 == 0)
        {
          /* the defender has no legal move at all here; since this
             candidate wasn't flagged mf_chmt above, that means it's
             stalemate, not mate -- a failure for the attacker */
          SANRetract ();
          continue;
        };

      {
        siT all_ok = 1;
        siT have_reply = 0;
        mT chosen_reply = *curr_g.g_base;      /* placeholder */
        mT sub_line[LINE_MAX];
        siT sub_len = 0;

        for (j = 0; (j < m2) && all_ok && !timed_out; j++)
          {
            mT this_sub[LINE_MAX];
            siT this_len = 0;
            siT ok;

            reply = &curr_g.g_base[j];
            curr_g.g_curr = reply;
            SANExecute ();
            ok = SolveMate (budget - 1, this_sub, &this_len);
            SANRetract ();

            if (!ok)
              all_ok = 0;
            else if (!have_reply)
              {
                chosen_reply = *reply;
                memcpy (sub_line, this_sub, sizeof (mT) * this_len);
                sub_len = this_len;
                have_reply = 1;
              };
          };

        SANRetract ();          /* undo save_cand / cand */

        if (timed_out)
          return (0);

        if (all_ok)
          {
            line[0] = save_cand;
            line[1] = chosen_reply;
            memcpy (line + 2, sub_line, sizeof (mT) * sub_len);
            *linelen = 2 + sub_len;
            return (1);
          };
      };
    };

  return (0);
}

static void
Usage (const char *progname)
{
  fprintf (stderr, "usage: %s [-d MAXMOVES] [-t SECONDS] \"FEN\"\n",
           progname);
  fprintf (stderr, "  searches for a forced checkmate in at most "
                    "MAXMOVES moves (default 4)\n");
  fprintf (stderr, "  of the side to move, giving up after SECONDS "
                    "seconds (default 10)\n");

  return;
}

int
main (int argc, char *argv[])
{
  int i;
  char *fen;
  siT maxmoves, seconds, d, linelen;
  mT line[LINE_MAX];
  cT solver_side;

  fen = NULL;
  maxmoves = 4;
  seconds = 10;

  i = 1;
  while (i < argc)
    {
      if ((strcmp (argv[i], "-d") == 0) && (i + 1 < argc))
        {
          maxmoves = (siT) atoi (argv[i + 1]);
          i += 2;
        }
      else if ((strcmp (argv[i], "-t") == 0) && (i + 1 < argc))
        {
          seconds = (siT) atoi (argv[i + 1]);
          i += 2;
        }
      else if ((strcmp (argv[i], "-h") == 0) ||
               (strcmp (argv[i], "--help") == 0))
        {
          Usage (argv[0]);
          return (0);
        }
      else
        {
          fen = argv[i];
          i++;
        };
    };

  if ((fen == NULL) || (maxmoves < 1))
    {
      Usage (argv[0]);
      return (1);
    };

  SANInit ();
  optnv[optn_nabd] = 1;
  optnv[optn_namd] = 1;

  if (!SANFENSet (fen))
    {
      fprintf (stderr, "%s: not a valid FEN: %s\n", argv[0], fen);
      return (1);
    };

  if (SANStatus () != gs_norm)
    {
      printf ("Position: %s\n", fen);
      printf ("This position is not ongoing (checkmate, stalemate, "
              "or a draw already) -- nothing to search for.\n");
      return (0);
    };

  solver_side = curr_e.e_actc;

  printf ("Position: %s\n", fen);
  printf ("Side to move: %s\n", (solver_side == c_w) ? "White" : "Black");
  printf ("Searching for a forced mate in 1..%d move%s "
          "(time budget: %ds)...\n",
          maxmoves, (maxmoves == 1) ? "" : "s", seconds);

  for (d = 1; d <= maxmoves; d++)
    {
      nodes = 0;
      timed_out = 0;
      deadline = clock () + ((clock_t) seconds * CLOCKS_PER_SEC);

      if (SolveMate (d, line, &linelen))
        {
          siT k;
          siT fmvn;
          cT actc;

          printf ("\nMate in %d found (%lu nodes):\n\n", d, nodes);

          /* replay the solution on a fresh copy of the position so
             the moves can be shown in proper SAN, with the library's
             own move-numbering conventions, exactly as if they had
             really been played */
          SANFENSet (fen);
          fmvn = curr_e.e_fmvn;
          actc = curr_e.e_actc;

          for (k = 0; k < linelen; k++)
            {
              sanT san;
              mptrT played;

              SANGenMoves ();
              played = SANFindMove (&line[k]);
              if (played == NULL)
                {
                  fprintf (stderr,
                           "%s: internal error replaying the "
                           "solution (move %d)\n", argv[0], k + 1);
                  return (1);
                };

              SANEncode (played, san);

              if ((k == 0) && (actc == c_b))
                printf ("%d... %s ", fmvn, san);
              else if (actc == c_w)
                printf ("%d. %s ", fmvn, san);
              else
                printf ("%s ", san);

              SANPlayMove (played);

              if (actc == c_b)
                fmvn++;
              actc = (actc == c_w) ? c_b : c_w;
            };

          printf ("\n\nFinal position: %s\n", SANFENGen ());

          return (0);
        };

      if (timed_out)
        {
          printf ("\nSearch abandoned after the %ds time budget "
                  "while still looking for a mate in %d -- no "
                  "conclusion below this depth (increase -t to "
                  "search longer).\n", seconds, d);
          return (1);
        };

      printf ("  no mate in %d (%lu nodes)\n", d, nodes);
      SANFENSet (fen);           /* restore, in case anything drifted */
    };

  printf ("\nNo forced mate in %d move%s or fewer.\n",
          maxmoves, (maxmoves == 1) ? "" : "s");

  return (1);
}
