Subversion Repositories Games.Chess Giants

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. /*
  2.     Protector -- a UCI chess engine
  3.  
  4.     Copyright (C) 2009-2010 Raimund Heid (Raimund_Heid@yahoo.com)
  5.  
  6.     This program is free software: you can redistribute it and/or modify
  7.     it under the terms of the GNU General Public License as published by
  8.     the Free Software Foundation, either version 3 of the License, or
  9.     (at your option) any later version.
  10.  
  11.     This program is distributed in the hope that it will be useful,
  12.     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13.     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14.     GNU General Public License for more details.
  15.  
  16.     You should have received a copy of the GNU General Public License
  17.     along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18.  
  19. */
  20.  
  21. #include <stdio.h>
  22. #include <string.h>
  23. #include <assert.h>
  24. #include "matesearch.h"
  25. #include "io.h"
  26. #include "movegeneration.h"
  27. #include "hash.h"
  28. #include "coordination.h"
  29.  
  30. static int searchMate(Variation * variation, int alpha, int beta,
  31.                       const int ply, const int restDepth,
  32.                       PrincipalVariation * pv)
  33. {
  34.    const int oldAlpha = alpha;
  35.    Position *position = &variation->singlePosition;
  36.    const bool check = activeKingIsSafe(position) == FALSE;
  37.    int best = VALUE_MATED;
  38.    Movelist movelist;
  39.    Hashentry *tableHit = NULL;
  40.    UINT8 hashentryFlag;
  41.    int i, historyLimit;
  42.    Move hashmove = NO_MOVE;
  43.    Move bestMove = NO_MOVE;
  44.    Move currentMove;
  45.    PrincipalVariation newPv;
  46.  
  47.    newPv.length = pv->length = 0;
  48.  
  49.    historyLimit = POSITION_HISTORY_OFFSET + variation->ply -
  50.       variation->singlePosition.halfMoveClock;
  51.  
  52.    assert(historyLimit >= 0);
  53.  
  54.    for (i = POSITION_HISTORY_OFFSET + variation->ply - 4;
  55.         i >= historyLimit; i -= 2)
  56.    {
  57.       if (variation->singlePosition.hashKey == variation->positionHistory[i])
  58.       {
  59.          return 0;
  60.       }
  61.    }
  62.  
  63.    /* Probe the transposition table */
  64.    /* ----------------------------- */
  65.    tableHit = getHashentry(getSharedHashtable(),
  66.                            variation->singlePosition.hashKey);
  67.  
  68.    if (tableHit != NULL)
  69.    {
  70.       const int importance = getHashentryImportance(tableHit);
  71.  
  72.       hashmove = (Move) getHashentryMove(tableHit);
  73.  
  74.       if (hashmove != NO_MOVE)
  75.       {
  76.          if (moveIsPseudoLegal(position, hashmove))
  77.          {
  78.             assert(moveIsLegal(position, hashmove));
  79.  
  80.             appendMoveToPv(&newPv, pv, hashmove);
  81.          }
  82.          else
  83.          {
  84.             hashmove = NO_MOVE;
  85.          }
  86.       }
  87.  
  88.       if (restDepth <= importance)
  89.       {                         /* 99% */
  90.          const int value = getHashentryValue(tableHit);
  91.          const int hashValue = calcEffectiveValue(value, ply);
  92.          const int flag = getHashentryFlag(tableHit);
  93.  
  94.          switch (flag)
  95.          {
  96.          case HASHVALUE_UPPER_LIMIT:
  97.             if (hashValue <= alpha)
  98.             {
  99.                return hashValue;
  100.             }
  101.             break;
  102.  
  103.          case HASHVALUE_EXACT:
  104.             return hashValue;
  105.  
  106.          case HASHVALUE_LOWER_LIMIT:
  107.             if (hashValue >= beta)
  108.             {
  109.                return hashValue;
  110.             }
  111.             break;
  112.  
  113.          default:;
  114.          }
  115.       }
  116.    }
  117.  
  118.    if (ply >= 2)
  119.    {
  120.       variation->plyInfo[ply].killerMove3 =
  121.          variation->plyInfo[ply - 2].killerMove1;
  122.       variation->plyInfo[ply].killerMove4 =
  123.          variation->plyInfo[ply - 2].killerMove2;
  124.    }
  125.    else
  126.    {
  127.       variation->plyInfo[ply].killerMove3 = NO_MOVE;
  128.       variation->plyInfo[ply].killerMove4 = NO_MOVE;
  129.    }
  130.  
  131.    if (restDepth == 1)
  132.    {
  133.       initCheckMovelist(&movelist, position, &variation->historyValue[0]);
  134.    }
  135.    else
  136.    {
  137.       movelist.positionalGain = &(variation->positionalGain[0]);
  138.       initStandardMovelist(&movelist, &variation->singlePosition,
  139.                            &variation->plyInfo[ply],
  140.                            &variation->historyValue[0], hashmove, check);
  141.    }
  142.  
  143.    initializePlyInfo(variation);
  144.  
  145.    while ((currentMove = getNextMove(&movelist)) != NO_MOVE)
  146.    {
  147.       int value;
  148.  
  149.       variation->nodes++;
  150.  
  151.       if (makeMoveFast(variation, currentMove) != 0 ||
  152.           passiveKingIsSafe(&variation->singlePosition) == FALSE ||
  153.           (restDepth == 1 && activeKingIsSafe(&variation->singlePosition)))
  154.       {
  155.          unmakeLastMove(variation);
  156.  
  157.          continue;
  158.       }
  159.  
  160.       if (restDepth > 0)
  161.       {
  162.          if (restDepth == 1)
  163.          {
  164.             if (kingCanEscape(position))
  165.             {
  166.                value = 0;
  167.             }
  168.             else
  169.             {
  170.                value = -(VALUE_MATED + ply + 1);
  171.             }
  172.          }
  173.          else
  174.          {
  175.             value = -searchMate(variation, -beta, -alpha, ply + 1,
  176.                                 restDepth - 1, &newPv);
  177.          }
  178.       }
  179.       else
  180.       {
  181.          value = 0;
  182.       }
  183.  
  184.       unmakeLastMove(variation);
  185.  
  186.       if (value > best)
  187.       {
  188.          best = value;
  189.          appendMoveToPv(&newPv, pv, currentMove);
  190.  
  191.          if (best > alpha)
  192.          {
  193.             alpha = best;
  194.             bestMove = currentMove;
  195.  
  196.             if (ply == 0)
  197.             {
  198.                if (variation->threadNumber == 0 &&
  199.                    variation->handleSearchEvent != 0)
  200.                {
  201.                   getGuiSearchMutex();
  202.                   variation->handleSearchEvent(SEARCHEVENT_NEW_PV, variation);
  203.                   releaseGuiSearchMutex();
  204.                }
  205.             }
  206.  
  207.             if (best >= beta)
  208.             {
  209.                goto finish;
  210.             }
  211.          }
  212.       }
  213.    }
  214.  
  215.    if (best == VALUE_MATED)
  216.    {
  217.       if (check)
  218.       {
  219.          /* mate */
  220.  
  221.          best = VALUE_MATED + ply;
  222.       }
  223.       else
  224.       {
  225.          /* stalemate */
  226.  
  227.          best = variation->drawScore[position->activeColor];
  228.       }
  229.    }
  230.  
  231.  finish:
  232.  
  233.    if (bestMove != NO_MOVE)
  234.    {
  235.       if (position->piece[getToSquare(bestMove)] == NO_PIECE &&
  236.           getNewPiece(bestMove) == NO_PIECE &&
  237.           (getToSquare(bestMove) != position->enPassantSquare ||
  238.            pieceType(position->piece[getFromSquare(bestMove)]) != PAWN))
  239.       {
  240.          Move killerMove = bestMove;
  241.          const Piece movingPiece = position->piece[getFromSquare(killerMove)];
  242.          const int index = historyIndex(bestMove, position);
  243.  
  244.          setMoveValue(&killerMove, movingPiece);
  245.          registerKillerMove(&variation->plyInfo[ply], killerMove);
  246.  
  247.          variation->historyValue[index] = (UINT16)
  248.             (variation->historyValue[index] + (restDepth * restDepth));
  249.  
  250.          if (variation->historyValue[index] > HISTORY_MAX)
  251.          {
  252.             shrinkHistoryValues(variation);
  253.          }
  254.       }
  255.    }
  256.  
  257.    /* Store the value in the transposition table. */
  258.    /* ------------------------------------------- */
  259.    if (best > oldAlpha)
  260.    {
  261.       hashentryFlag =
  262.          (best >= beta ? HASHVALUE_LOWER_LIMIT : HASHVALUE_EXACT);
  263.    }
  264.    else
  265.    {
  266.       hashentryFlag = HASHVALUE_UPPER_LIMIT;
  267.    }
  268.  
  269.    setHashentry(getSharedHashtable(), position->hashKey,
  270.                 calcHashtableValue(best, ply), (INT8) restDepth,
  271.                 packedMove(bestMove), hashentryFlag, 0);
  272.  
  273.    return best;
  274. }
  275.  
  276. static int searchBaseMoves(Variation * variation, const int alpha,
  277.                            const int beta, const int restDepth,
  278.                            Movelist * solutions)
  279. {
  280.    Position *position = &variation->singlePosition;
  281.    const bool check = activeKingIsSafe(position) == FALSE;
  282.    int best = VALUE_MATED, ply = 0;
  283.    Movelist movelist;
  284.    Move hashmove = NO_MOVE;
  285.    Move currentMove;
  286.    PrincipalVariation pv;
  287.  
  288.    if (restDepth == 1)
  289.    {
  290.       initCheckMovelist(&movelist, position, &variation->historyValue[0]);
  291.    }
  292.    else
  293.    {
  294.       movelist.positionalGain = &(variation->positionalGain[0]);
  295.       initStandardMovelist(&movelist, &variation->singlePosition,
  296.                            &variation->plyInfo[ply],
  297.                            &variation->historyValue[0], hashmove, check);
  298.    }
  299.  
  300.    initializePlyInfo(variation);
  301.  
  302.    while ((currentMove = getNextMove(&movelist)) != NO_MOVE)
  303.    {
  304.       int value;
  305.  
  306.       variation->nodes++;
  307.  
  308.       if (makeMoveFast(variation, currentMove) != 0 ||
  309.           passiveKingIsSafe(&variation->singlePosition) == FALSE ||
  310.           (restDepth == 1 && activeKingIsSafe(&variation->singlePosition)))
  311.       {
  312.          unmakeLastMove(variation);
  313.  
  314.          continue;
  315.       }
  316.  
  317.       value =
  318.          -searchMate(variation, -beta, -alpha, ply + 1, restDepth - 1, &pv);
  319.  
  320.       unmakeLastMove(variation);
  321.  
  322.       if (value >= best)
  323.       {
  324.          best = variation->pv[0].score = value;
  325.          setMoveValue(&currentMove, value);
  326.          appendMoveToPv(&pv, &variation->pv[0], currentMove);
  327.  
  328.          if (best > alpha)
  329.          {
  330.             variation->bestBaseMove = currentMove;
  331.             solutions->moves[solutions->numberOfMoves++] = currentMove;
  332.  
  333.             if (variation->threadNumber == 0 &&
  334.                 variation->handleSearchEvent != 0)
  335.             {
  336.                getGuiSearchMutex();
  337.                variation->handleSearchEvent(SEARCHEVENT_NEW_PV, variation);
  338.                releaseGuiSearchMutex();
  339.             }
  340.          }
  341.       }
  342.    }
  343.  
  344.    if (best == VALUE_MATED)
  345.    {
  346.       if (check)
  347.       {
  348.          /* mate */
  349.  
  350.          best = VALUE_MATED + ply;
  351.       }
  352.       else
  353.       {
  354.          /* stalemate */
  355.  
  356.          best = variation->drawScore[position->activeColor];
  357.       }
  358.    }
  359.  
  360.    return best;
  361. }
  362.  
  363. void searchForMate(Variation * variation, Movelist * foundSolutions,
  364.                    int numMoves)
  365. {
  366.    int numSolutions = 0, i;
  367.  
  368.    variation->startTime = getTimestamp();
  369.    variation->startTimeProcess = getProcessTimestamp();
  370.    variation->timestamp = variation->startTime + 1;
  371.    resetHashtable(getSharedHashtable());
  372.    getLegalMoves(variation, foundSolutions);
  373.    variation->numberOfBaseMoves = foundSolutions->numberOfMoves;
  374.    variation->searchStatus = SEARCH_STATUS_RUNNING;
  375.  
  376.    foundSolutions->numberOfMoves = 0;
  377.    resetHistoryValues(variation);
  378.  
  379.    for (variation->iteration = 1; variation->iteration <= numMoves;
  380.         variation->iteration++)
  381.    {
  382.       const int restDepth = 2 * variation->iteration - 1;
  383.       const int beta = -VALUE_MATED - restDepth;
  384.  
  385.       searchBaseMoves(variation, beta - 1, beta, restDepth, foundSolutions);
  386.    }
  387.  
  388.    variation->finishTime = getTimestamp();
  389.    variation->finishTimeProcess = getProcessTimestamp();
  390.    variation->searchStatus = SEARCH_STATUS_TERMINATE;
  391.  
  392.    for (i = 0; i < foundSolutions->numberOfMoves; i++)
  393.    {
  394.       if (getMoveValue(foundSolutions->moves[i]) >=
  395.           -VALUE_MATED - 2 * numMoves + 1)
  396.       {
  397.          numSolutions++;
  398.       }
  399.    }
  400.  
  401.    foundSolutions->numberOfMoves = numSolutions;
  402.  
  403.    getGuiSearchMutex();
  404.  
  405.    if (variation->threadNumber == 0 &&
  406.        variation->handleSearchEvent != 0 &&
  407.        variation->searchStatus == SEARCH_STATUS_TERMINATE)
  408.    {
  409.       variation->handleSearchEvent(SEARCHEVENT_SEARCH_FINISHED, variation);
  410.    }
  411.  
  412.    releaseGuiSearchMutex();
  413. }
  414.  
  415. int initializeModuleMatesearch()
  416. {
  417.    return 0;
  418. }
  419.  
  420. int testModuleMatesearch()
  421. {
  422.    return 0;
  423. }
  424.