Protector Code

/*
    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/>.

*/

#ifndef _position_h_
#define _position_h_

#include "protector.h"
#include "bitboard.h"
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#define MAX_DEPTH 64
#define POSITION_HISTORY_OFFSET 100

#define DEFAULT_HASHTABLE_EXPONENT   16

#define SEARCHEVENT_SEARCH_FINISHED    1
#define SEARCHEVENT_PLY_FINISHED       2
#define SEARCHEVENT_NEW_PV             3
#define SEARCHEVENT_NEW_BASEMOVE       4
#define SEARCHEVENT_STATISTICS_UPDATE  5

#define DEFAULTVALUE_QUEEN_OPENING       975
#define DEFAULTVALUE_QUEEN_ENDGAME       975
#define DEFAULTVALUE_ROOK_OPENING        465
#define DEFAULTVALUE_ROOK_ENDGAME        500
#define DEFAULTVALUE_BISHOP_OPENING      330
#define DEFAULTVALUE_BISHOP_ENDGAME      325
#define DEFAULTVALUE_KNIGHT_OPENING      330
#define DEFAULTVALUE_KNIGHT_ENDGAME      325
#define PAWN_DEFAULTVALUE_OPENING         75
#define PAWN_DEFAULTVALUE_ENDGAME         90
#define DEFAULTVALUE_BISHOP_PAIR_OPENING  50
#define DEFAULTVALUE_BISHOP_PAIR_ENDGAME  60

extern int VALUE_QUEEN_OPENING;
extern int VALUE_QUEEN_ENDGAME;
extern int VALUE_ROOK_OPENING;
extern int VALUE_ROOK_ENDGAME;
extern int VALUE_BISHOP_OPENING;
extern int VALUE_BISHOP_ENDGAME;
extern int VALUE_KNIGHT_OPENING;
extern int VALUE_KNIGHT_ENDGAME;
extern int PAWN_VALUE_OPENING;
extern int PAWN_VALUE_ENDGAME;
extern int VALUE_BISHOP_PAIR_OPENING;
extern int VALUE_BISHOP_PAIR_ENDGAME;

#define OPENING 0
#define ENDGAME 1

extern int basicValue[16];
extern int pieceSquareValue[16][_64_][2];
extern int pieceCountShift[16];

typedef struct
{
   Piece piece[_64_];
   Color activeColor;
   BYTE castlingRights;
   Square enPassantSquare;
   int moveNumber, halfMoveClock;

   /**
    * Redundant data
    */
   Bitboard allPieces;
   Bitboard piecesOfColor[2];
   Bitboard piecesOfType[16];
   Square king[2];
   int numberOfPieces[2];
   int numberOfPawns[2];
   UINT32 pieceCount;
   int phaseIndex;
   int openingValue[2], endgameValue[2];
   UINT64 hashValue, pawnHashValue;
}
Position;

typedef UINT32 Move;

typedef struct
{
   Square square;
   Bitboard moves;
}
MovesOfPiece;

typedef struct
{
   Bitboard diaAttackers, orthoAttackers, knightAttackers, pawnAttackers[2];
   Square attackedByDia[_64_], attackedByOrtho[_64_];
}
KingAttacks;

typedef struct
{
   Move killerMove1, killerMove2, killerMove3, killerMove4;
   Move currentMove;
   bool currentMoveIsCheck;
   Piece captured, restorePiece1, restorePiece2;
   Square enPassantSquare, restoreSquare1, restoreSquare2, kingSquare;
   BYTE castlingRights;
   int halfMoveClock;
   Bitboard allPieces, whitePieces, blackPieces, hashValue, pawnHashValue;
   int openingValue[2], endgameValue[2];
   bool quietMove;
}
PlyInfo;

typedef struct
{
   Position *position;
   PlyInfo *plyInfo;
   Move hashMove;
   Move moves[MAX_MOVES_PER_POSITION];
   Move badCaptures[MAX_MOVES_PER_POSITION];
   bool killer1Executed, killer2Executed, killer3Executed, killer4Executed;
   MovesOfPiece movesOfPiece[16];
   int numberOfMoves, numberOfBadCaptures;
   int nextMove, currentStage, numberOfPieces;
   UINT16 *historyValue;
}
Movelist;

#define HASHVALUE_LOWER 0
#define HASHVALUE_EXACT 1
#define HASHVALUE_HIGHER 2

typedef struct
{
   UINT64 key;
   UINT64 data;
}
Hashentry;

typedef struct
{
   Hashentry *table;
   unsigned long tableSize, entriesUsed;
   UINT64 hashMask;
   int exponent;
   UINT8 date;
}
Hashtable;

typedef enum
{
   SEARCH_STATUS_RUNNING,
   SEARCH_STATUS_TERMINATE,
   SEARCH_STATUS_ABORT,
   SEARCH_STATUS_FINISHED
}
SearchStatus;

#define HISTORY_SIZE (12*64*64)
#define HISTORY_MAX  16384
#define HISTORY_LIMIT 60        /* (60%) */

typedef struct
{
   UINT16 move[MAX_DEPTH + 2];
   int length, score;
}
PrincipalVariation;

typedef struct
{
   Bitboard hashValue;
   Bitboard pawnProtectedSquares[2];
   Bitboard passedPawns[2];
   Bitboard weakOutpostSquares[2];
   Bitboard pawnAttackableSquares[2];
   bool hasPassersOrCandidates[2];

   int openingPoints[2], endgamePoints[2];
}
PawnHashInfo;

typedef struct
{
   Bitboard hashValue;
   int safetyMalus;
}
KingSafetyHashInfo;

#define PAWN_HASHTABLE_MASK 0xffff
#define PAWN_HASHTABLE_SIZE ((PAWN_HASHTABLE_MASK)+0x0001)
#define KINGSAFETY_HASHTABLE_MASK 0x07ffff
#define KINGSAFETY_HASHTABLE_SIZE ((KINGSAFETY_HASHTABLE_MASK)+0x0001)

typedef struct
{
   int ply, nominalDepth, selDepth;
   int numberOfBaseMoves, numberOfCurrentBaseMove;
   Move currentBaseMove, bestBaseMove;
   Position singlePosition, startPosition;
   PlyInfo plyInfo[MAX_DEPTH + 2];
   PrincipalVariation pv;
   Hashtable *hashtable;
   PawnHashInfo *pawnHashtable;
   KingSafetyHashInfo *kingsafetyHashtable;
   UINT64 positionHistory[POSITION_HISTORY_OFFSET + MAX_DEPTH + 2];
   UINT64 nodes;
   UINT16 *historyValue;
   UINT16 *historyTotalCount;
   UINT16 *historyHitCount;
   long startTime, timeTarget, timeLimit, finishTime, timestamp;
   long startTimeProcess, finishTimeProcess;
   unsigned long tbHits;
   void (*handleSearchEvent) (int, void *);
   SearchStatus searchStatus;
   int drawScore[2];
   bool easyMove, bestMoveChange;
   bool terminate, ponderMode, terminatePondering, failingHighOrLow;
   int previousBest, expectedScore;
   long numPvUpdates;
   unsigned int threadNumber;
}
Variation;

/**
 * Pack the specified move into a 16-bit-uint.
 */
INLINE UINT16 packedMove(const Move move)
{
   return (UINT16) (move & 0xFFFF);
}

/**
 * Construct the specified move.
 */
INLINE Move getMove(const Square from, const Square to,
                    const Piece newPiece, const INT16 value)
{
   return (value << 16) | (newPiece << 12) | (to << 6) | from;
}

/**
 * Construct the specified ordinary move.
 */
INLINE Move getOrdinaryMove(const Square from, const Square to)
{
   return (to << 6) | from;
}

/**
 * Construct the specified packed move.
 */
INLINE Move getPackedMove(const Square from, const Square to,
                          const Piece newPiece)
{
   return (newPiece << 12) | (to << 6) | from;
}

/**
 * Get the from square of the specified move.
 */
INLINE Square getFromSquare(const Move move)
{
   return (Square) (move & 0x3F);
}

/**
 * Get the to square of the specified move.
 */
INLINE Square getToSquare(const Move move)
{
   return (Square) ((move >> 6) & 0x3F);
}

/**
 * Get the new piece of the specified move.
 */
INLINE Piece getNewPiece(const Move move)
{
   return (Piece) ((move >> 12) & 0x0F);
}

/**
 * Get the value of the specified move.
 */
INLINE INT16 getMoveValue(const Move move)
{
   return (INT16) (move >> 16);
}

/**
 * Set the value of the specified move.
 */
INLINE void setMoveValue(Move * move, const int value)
{
   *move = (*move & 0xFFFF) | (value << 16);
}

/**
 * Get the opponent color of the specified color.
 */
INLINE Color opponent(Color color)
{
   return (Color) (1 - color);
}

/**
 * Flip the specified position.
 */
void flipPosition(Position * position);

/**
 * Remove all pieces from the specified position.
 */
void clearPosition(Position * position);

/**
 * Calculate the redundant data of the specified position.
 */
void initializePosition(Position * position);

/**
 * Prepare a search with the specified variation.
 */
void prepareSearch(Variation * variation);

/**
 * Reset history values.
 */
void resetHistoryValues(Variation * variation);

/**
 * Reset history hit values.
 */
void resetHistoryHitValues(Variation * variation);

/**
 * Shrink all history values.
 */
void shrinkHistoryValues(Variation * variation);

/**
 * Shrink all history hit values.
 */
void shrinkHistoryHitValues(Variation * variation);

/**
 * Initialize a variation with the position specified by 'fen'.
 * Prepare a search.
 */
void initializeVariation(Variation * variation, const char *fen);

/**
 * Initialize a variation with the position specified by 'position'.
 * To perform a search, call 'prepareSearch' afterwards.
 */
void setBasePosition(Variation * variation, const Position * position);

/**
 * Set the value of a definite draw.
 */
void setDrawScore(Variation * variation, int score, Color color);

/**
 * Get the direct attackers of 'attackerColor' on 'square'.
 */
INLINE Bitboard getDirectAttackers(const Position * position,
                                   const Square square,
                                   const Color attackerColor,
                                   const Bitboard obstacles)
{
   const Bitboard king = getKingMoves(square) &
      minValue[position->king[attackerColor]];
   Bitboard dia = getMagicBishopMoves(square, obstacles);
   Bitboard ortho = getMagicRookMoves(square, obstacles);
   Bitboard knights = getKnightMoves(square);
   const Bitboard pawns =
      getPawnCaptures((Piece) (PAWN | opponent(attackerColor)),
                      square, position->piecesOfType[PAWN | attackerColor]);

   ortho &= (position->piecesOfType[QUEEN | attackerColor] |
             position->piecesOfType[ROOK | attackerColor]);
   dia &= (position->piecesOfType[QUEEN | attackerColor] |
           position->piecesOfType[BISHOP | attackerColor]);
   knights &= position->piecesOfType[KNIGHT | attackerColor];

   return king | ortho | dia | knights | pawns;
}

/**
 * Get the squares behind targetSquare, seen from 'viewPoint'.
 */
INLINE Bitboard getDiaSquaresBehind(const Position * position,
                                    const Square targetSquare,
                                    const Square viewPoint)
{
   return squaresBehind[targetSquare][viewPoint] &
      getMagicBishopMoves(targetSquare, position->allPieces);
}

/**
 * Get the squares behind targetSquare, seen from 'viewPoint'.
 */
INLINE Bitboard getOrthoSquaresBehind(const Position * position,
                                      const Square targetSquare,
                                      const Square viewPoint)
{
   return squaresBehind[targetSquare][viewPoint] &
      getMagicRookMoves(targetSquare, position->allPieces);
}

/**
 * Get the pieces interested in moving to 'square'.
 */
Bitboard getInterestedPieces(const Position * position, const Square square,
                             const Color attackerColor);

/**
 * Initialize the current plyInfo data structure.
 */
INLINE void initializePlyInfo(Variation * variation)
{
   const Position *position = &variation->singlePosition;
   PlyInfo *plyInfo = &variation->plyInfo[variation->ply];
   const Color activeColor = position->activeColor;
   const Color passiveColor = opponent(activeColor);

   plyInfo->pawnHashValue = position->pawnHashValue;
   plyInfo->enPassantSquare = position->enPassantSquare;
   plyInfo->kingSquare = position->king[activeColor];
   plyInfo->castlingRights = position->castlingRights;
   plyInfo->halfMoveClock = position->halfMoveClock;
   plyInfo->allPieces = position->allPieces;
   plyInfo->whitePieces = position->piecesOfColor[WHITE];
   plyInfo->blackPieces = position->piecesOfColor[BLACK];
   plyInfo->openingValue[activeColor] = position->openingValue[activeColor];
   plyInfo->endgameValue[activeColor] = position->endgameValue[activeColor];
   plyInfo->openingValue[passiveColor] = position->openingValue[passiveColor];
   plyInfo->endgameValue[passiveColor] = position->endgameValue[passiveColor];
}

/**
 * Make the specified move at the current end of the specified variation.
 *
 * @return 1 if the move was an illegal castling move, 0 otherwise
 */
int makeMove(Variation * variation, const Move move);

/**
 * Make the specified move at the current end of the specified variation.
 *
 * @return 1 if the move was an illegal castling move, 0 otherwise
 */
int makeMoveFast(Variation * variation, const Move move);

/**
 * Unmake the last move.
 */
void unmakeLastMove(Variation * variation);

/**
 * Test if a move attacks the opponent's king.
 *
 * @return FALSE if the specified move doesn't attack
 *         the opponent's king, TRUE otherwise
 */
bool moveIsCheck(const Move move, const Position * position);

/**
 * Get the number of non-pawn pieces for the specified color.
 */
INLINE int numberOfNonPawnPieces(const Position * position, const Color color)
{
   return position->numberOfPieces[color] - position->numberOfPawns[color];
}

INLINE bool hasOrthoPieces(const Position * position, const Color color)
{
   return (bool) (position->piecesOfType[ROOK | color] != EMPTY_BITBOARD ||
                  position->piecesOfType[QUEEN | color] != EMPTY_BITBOARD);
}

/**
 * Check if the specified position is consistent.
 *
 * @return 0 if the specified position is consistent
 */
int checkConsistency(const Position * position);

/**
 * Check if the specified variation is consistent.
 *
 * @return 0 if the specified variation is consistent
 */
int checkVariation(Variation * variation);

/**
 * Check if the given position is legal.
 */
bool positionIsLegal(const Position * position);

/**
 * Append the given move to the old pv and copy the new pv to 'new'.
 */
INLINE void appendMoveToPv(const PrincipalVariation * old,
                           PrincipalVariation * new, const Move move)
{
   new->move[0] = packedMove(move);
   new->length = old->length + 1;
   memmove((void *) &new->move[1], (void *) &old->move[0],
           old->length * sizeof(UINT16));
}

/**
 * Calculate the value to be stored in the hashtable.
 */
INLINE INT16 calcHashtableValue(const int value, const int ply)
{
   if (value >= -VALUE_ALMOST_MATED)
   {
      return (INT16) (value + ply);
   }
   else if (value <= VALUE_ALMOST_MATED)
   {
      return (INT16) (value - ply);
   }

   return (INT16) value;
}

/**
 * Calculate the effective value from the specified hashtable value.
 */
INLINE int calcEffectiveValue(const int value, const int ply)
{
   if (value >= -VALUE_ALMOST_MATED)
   {
      return value - ply;
   }
   else if (value <= VALUE_ALMOST_MATED)
   {
      return value + ply;
   }

   return value;
}

/**
 * Check if the specified position are identical (excluding move numbers).
 */
bool positionsAreIdentical(const Position * position1,
                           const Position * position2);

/**
 * Get all ordinary pieces (queens, rooks, bishops, knights) 
 * of the specified color.
 */
INLINE Bitboard getOrdinaryPieces(const Position * position,
                                  const Color color)
{
   return position->piecesOfColor[color] &
      ~(position->piecesOfType[PAWN | color] |
        minValue[position->king[color]]);
}

/**
 * Check if the given moves are equal by ignoring their respective values.
 */
INLINE bool movesAreEqual(const Move m1, const Move m2)
{
   return (bool) ((m1 & 0xFFFF) == (m2 & 0xFFFF));
}

/**
 * Get the population count for the specified piece in the specified position.
 */
INLINE int getPieceCount(const Position * position, const Piece piece)
{
   return (position->pieceCount >> pieceCountShift[piece]) & 0x0F;
}

/**
 * Check if the specified piece is present in the specified position.
 */
INLINE bool pieceIsPresent(const Position * position, const Piece piece)
{
   return (bool) (position->piecesOfType[piece] != EMPTY_BITBOARD);
}

/**
 * Get the history index of the specified move.
 */
INLINE int historyIndex(const Move move, const Position * position)
{
   const int npWhite = min(7, numberOfNonPawnPieces(position, WHITE) - 1);
   const int npBlack = min(7, numberOfNonPawnPieces(position, BLACK) - 1);
   const int nonPawnCountIndex = 64 * (npWhite + 8 * npBlack);

   assert(nonPawnCountIndex >= 0 && nonPawnCountIndex <= 63 * 64);

   return pieceIndex[position->piece[getFromSquare(move)]] +
      nonPawnCountIndex + getToSquare(move);
}

/**
 * Calculate the distance to the next piece of a given type.
 *
 * @return the distance or 8 if no piece was found
 */
INLINE int getMinimalDistance(const Position * position,
                              const Square origin, const Piece piece)
{
   int distance;

   for (distance = 1; distance <= 7; distance++)
   {
      if ((squaresInDistance[distance][origin] &
           position->piecesOfType[piece]) != EMPTY_BITBOARD)
      {
         return distance;
      }
   }

   return 8;
}

/**
 * Calculate the distance to the next piece of a given type.
 *
 * @return the taxidistance or 15 if no piece was found
 */
INLINE int getMinimalTaxiDistance(const Position * position,
                                  const Square origin, const Piece piece)
{
   int distance;

   for (distance = 1; distance <= 14; distance++)
   {
      if ((squaresInTaxiDistance[distance][origin] &
           position->piecesOfType[piece]) != EMPTY_BITBOARD)
      {
         return distance;
      }
   }

   return 15;
}

/**
 * Calculate the weight of the non-pawn-pieces of the specified color.
 *
 * @return a value in the range [0-44]
 */
INLINE int getPieceWeight(const Position * position, const Color color)
{
   const int numNonPawnPieces = numberOfNonPawnPieces(position, color) - 1;
   const int numRooks = getPieceCount(position, (Piece) (ROOK | color));
   const int numQueens = getPieceCount(position, (Piece) (QUEEN | color));

   return 3 * numQueens + numRooks + numNonPawnPieces;
}

#define PHASE_MAX 24

/**
 * Calculate the phase index of the specified position.
 *
 * @return a value in the range [0(initial position)-256(endgame)]
 */
INLINE int phaseIndex(const Position * position)
{
   const int basicPhase = max(0, PHASE_MAX -
                              getPieceWeight(position, WHITE) -
                              getPieceWeight(position, BLACK));

   assert(getPieceWeight(position, WHITE) >= 0);
   assert(getPieceWeight(position, WHITE) <= 44);
   assert(getPieceWeight(position, BLACK) >= 0);
   assert(getPieceWeight(position, BLACK) <= 44);
   assert(basicPhase >= 0);
   assert(basicPhase <= PHASE_MAX);

   return (basicPhase * 256 + (PHASE_MAX / 2)) / PHASE_MAX;
}

/**
 * Initialize this module.
 *
 * @return 0 if no errors occurred.
 */
int initializeModulePosition(void);

/**
 * Test this module.
 *
 * @return 0 if all tests succeed.
 */
int testModulePosition(void);

#endif