/*
    Protector -- a UCI chess engine

    Copyright (C) 2009-2010 Raimund Heid (Raimund_Heid@yahoo.com)

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.

*/

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include "matesearch.h"
#include "io.h"
#include "movegeneration.h"
#include "hash.h"

static int searchMate(Variation * variation, int alpha, int beta,
                      const int ply, const int restDepth,
                      PrincipalVariation * pv)
{
   const int oldAlpha = alpha;
   Position *position = &variation->singlePosition;
   const bool check = activeKingIsSafe(position) == FALSE;
   int best = VALUE_MATED;
   Movelist movelist;
   Hashentry *tableHit = NULL;
   UINT8 hashentryFlag;
   int i, historyLimit;
   Move hashmove = NO_MOVE;
   Move bestMove = NO_MOVE;
   Move currentMove;
   PrincipalVariation newPv;

   newPv.length = pv->length = 0;

   historyLimit = POSITION_HISTORY_OFFSET + variation->ply -
      variation->singlePosition.halfMoveClock;

   assert(historyLimit >= 0);

   for (i = POSITION_HISTORY_OFFSET + variation->ply - 4;
        i >= historyLimit; i -= 2)
   {
      if (variation->singlePosition.hashValue ==
          variation->positionHistory[i])
      {
         return 0;
      }
   }

   /* Probe the transposition table */
   /* ----------------------------- */
   tableHit = getDatedEntry(variation->hashtable,
                            variation->singlePosition.hashValue);

   if (tableHit != NULL)
   {
      const int importance = getHashentryImportance(tableHit);

      hashmove = (Move) getHashentryMove(tableHit);

      if (hashmove != NO_MOVE)
      {
         if (moveIsPseudoLegal(position, hashmove))
         {
            assert(moveIsLegal(position, hashmove));

            appendMoveToPv(&newPv, pv, hashmove);
         }
         else
         {
            hashmove = NO_MOVE;
         }
      }

      if (restDepth <= importance)
      {                         /* 99% */
         const int value = getHashentryValue(tableHit);
         const int hashValue = calcEffectiveValue(value, ply);
         const int flag = getHashentryFlag(tableHit);

         switch (flag)
         {
         case HASHVALUE_UPPER_LIMIT:
            if (hashValue <= alpha)
            {
               return hashValue;
            }
            break;

         case HASHVALUE_EXACT:
            return hashValue;

         case HASHVALUE_LOWER_LIMIT:
            if (hashValue >= beta)
            {
               return hashValue;
            }
            break;

         default:;
         }
      }
   }

   if (ply >= 2)
   {
      variation->plyInfo[ply].killerMove3 =
         variation->plyInfo[ply - 2].killerMove1;
      variation->plyInfo[ply].killerMove4 =
         variation->plyInfo[ply - 2].killerMove2;
   }
   else
   {
      variation->plyInfo[ply].killerMove3 = NO_MOVE;
      variation->plyInfo[ply].killerMove4 = NO_MOVE;
   }

   if (restDepth == 1)
   {
      initCheckMovelist(&movelist, position, &variation->historyValue[0]);
   }
   else
   {
      initStandardMovelist(&movelist, &variation->singlePosition,
                           &variation->plyInfo[ply],
                           &variation->historyValue[0], hashmove, check);
   }

   initializePlyInfo(variation);

   while ((currentMove = getNextMove(&movelist)) != NO_MOVE)
   {
      int value;

      variation->nodes++;

      if (makeMoveFast(variation, currentMove) != 0 ||
          passiveKingIsSafe(&variation->singlePosition) == FALSE ||
          (restDepth == 1 && activeKingIsSafe(&variation->singlePosition)))
      {
         unmakeLastMove(variation);

         continue;
      }

      if (restDepth > 0)
      {
         if (restDepth == 1)
         {
            if (kingCanEscape(position))
            {
               value = 0;
            }
            else
            {
               value = -(VALUE_MATED + ply + 1);
            }
         }
         else
         {
            value = -searchMate(variation, -beta, -alpha, ply + 1,
                                restDepth - 1, &newPv);
         }
      }
      else
      {
         value = 0;
      }

      unmakeLastMove(variation);

      if (value > best)
      {
         best = value;
         appendMoveToPv(&newPv, pv, currentMove);

         if (best > alpha)
         {
            alpha = best;
            bestMove = currentMove;

            if (ply == 0)
            {
               if (variation->handleSearchEvent != 0)
               {
                  variation->handleSearchEvent(SEARCHEVENT_NEW_PV, variation);
               }
            }

            if (best >= beta)
            {
               goto finish;
            }
         }
      }
   }

   if (best == VALUE_MATED)
   {
      if (check)
      {
         /* mate */

         best = VALUE_MATED + ply;
      }
      else
      {
         /* stalemate */

         best = variation->drawScore[position->activeColor];
      }
   }

 finish:

   if (bestMove != NO_MOVE)
   {
      if (position->piece[getToSquare(bestMove)] == NO_PIECE &&
          getNewPiece(bestMove) == NO_PIECE &&
          (getToSquare(bestMove) != position->enPassantSquare ||
           pieceType(position->piece[getFromSquare(bestMove)]) != PAWN))
      {
         Move killerMove = bestMove;
         const Piece movingPiece = position->piece[getFromSquare(killerMove)];
         const int index = historyIndex(bestMove, position);

         setMoveValue(&killerMove, movingPiece);
         registerKillerMove(&variation->plyInfo[ply], killerMove);

         variation->historyValue[index] = (UINT16)
            (variation->historyValue[index] + (restDepth * restDepth));

         if (variation->historyValue[index] > HISTORY_MAX)
         {
            shrinkHistoryValues(variation);
         }
      }
   }

   /* Store the value in the transposition table. */
   /* ------------------------------------------- */
   if (best > oldAlpha)
   {
      hashentryFlag = (best >= beta ? HASHVALUE_LOWER_LIMIT : HASHVALUE_EXACT);
   }
   else
   {
      hashentryFlag = HASHVALUE_UPPER_LIMIT;
   }

   setDatedEntry(variation->hashtable, position->hashValue,
                 calcHashtableValue(best, ply), (INT8) restDepth,
                 packedMove(bestMove), hashentryFlag);

   return best;
}

static int searchBaseMoves(Variation * variation, const int alpha,
                           const int beta, const int restDepth,
                           Movelist * solutions)
{
   Position *position = &variation->singlePosition;
   const bool check = activeKingIsSafe(position) == FALSE;
   int best = VALUE_MATED, ply = 0;
   Movelist movelist;
   Move hashmove = NO_MOVE;
   Move currentMove;
   PrincipalVariation pv;

   if (restDepth == 1)
   {
      initCheckMovelist(&movelist, position, &variation->historyValue[0]);
   }
   else
   {
      initStandardMovelist(&movelist, &variation->singlePosition,
                           &variation->plyInfo[ply],
                           &variation->historyValue[0], hashmove, check);
   }

   initializePlyInfo(variation);

   while ((currentMove = getNextMove(&movelist)) != NO_MOVE)
   {
      int value;

      variation->nodes++;

      if (makeMoveFast(variation, currentMove) != 0 ||
          passiveKingIsSafe(&variation->singlePosition) == FALSE ||
          (restDepth == 1 && activeKingIsSafe(&variation->singlePosition)))
      {
         unmakeLastMove(variation);

         continue;
      }

      value =
         -searchMate(variation, -beta, -alpha, ply + 1, restDepth - 1, &pv);

      unmakeLastMove(variation);

      if (value >= best)
      {
         best = variation->pv.score = value;
         setMoveValue(&currentMove, value);
         appendMoveToPv(&pv, &variation->pv, currentMove);

         if (best > alpha)
         {
            variation->bestBaseMove = currentMove;
            solutions->moves[solutions->numberOfMoves++] = currentMove;

            if (variation->handleSearchEvent != 0)
            {
               variation->handleSearchEvent(SEARCHEVENT_NEW_PV, variation);
            }
         }
      }
   }

   if (best == VALUE_MATED)
   {
      if (check)
      {
         /* mate */

         best = VALUE_MATED + ply;
      }
      else
      {
         /* stalemate */

         best = variation->drawScore[position->activeColor];
      }
   }

   return best;
}

void searchForMate(Variation * variation, Movelist * foundSolutions,
                   int numMoves)
{
   int iteration, numSolutions = 0, i, result = 0;

   variation->startTime = getTimestamp();
   variation->startTimeProcess = getProcessTimestamp();
   variation->timestamp = variation->startTime + 1;
   resetHashtable(variation->hashtable);
   getLegalMoves(variation, foundSolutions);
   variation->numberOfBaseMoves = foundSolutions->numberOfMoves;
   variation->searchStatus = SEARCH_STATUS_RUNNING;

   foundSolutions->numberOfMoves = 0;
   resetHistoryValues(variation);

   for (iteration = 1; iteration <= numMoves; iteration++)
   {
      variation->nominalDepth = 2 * iteration - 1;

      result = searchBaseMoves(variation, -VALUE_MATED - 2 * iteration,
                               -VALUE_MATED - 2 * iteration + 1,
                               variation->nominalDepth, foundSolutions);
   }

   variation->finishTime = getTimestamp();
   variation->finishTimeProcess = getProcessTimestamp();
   variation->searchStatus = SEARCH_STATUS_TERMINATE;

   for (i = 0; i < foundSolutions->numberOfMoves; i++)
   {
      if (getMoveValue(foundSolutions->moves[i]) >=
          -VALUE_MATED - 2 * numMoves + 1)
      {
         numSolutions++;
      }
   }

   foundSolutions->numberOfMoves = numSolutions;

   if (variation->handleSearchEvent != 0 &&
       variation->searchStatus == SEARCH_STATUS_TERMINATE)
   {
      variation->handleSearchEvent(SEARCHEVENT_SEARCH_FINISHED, variation);
   }
}

int initializeModuleMatesearch()
{
   return 0;
}

int testModuleMatesearch()
{
   return 0;
}
