Subversion Repositories Games.Chess Giants

/*

  Copyright (c) 2013 Ronald de Man

  This file may be redistributed and/or modified without restrictions.

  tbprobe.cpp contains the Stockfish-specific routines of the

  tablebase probing code. It should be relatively easy to adapt

  this code to other chess engines.

*/

#define NOMINMAX

#include <algorithm>

#include "../position.h"

#include "../movegen.h"

#include "../bitboard.h"

#include "../search.h"

#include "../bitcount.h"

#include "tbprobe.h"

#include "tbcore.h"

#include "tbcore.cpp"

namespace Zobrist {

  extern Key psq[COLOR_NB][PIECE_TYPE_NB][SQUARE_NB];

}

int Tablebases::MaxCardinality = 0;

// Given a position with 6 or fewer pieces, produce a text string

// of the form KQPvKRP, where "KQP" represents the white pieces if

// mirror == 0 and the black pieces if mirror == 1.

static void prt_str(Position& pos, char *str, int mirror)

{

  Color color;

  PieceType pt;

  int i;

  color = !mirror ? WHITE : BLACK;

  for (pt = KING; pt >= PAWN; --pt)

    for (i = popcount<Max15>(pos.pieces(color, pt)); i > 0; i--)

      *str++ = pchr[6 - pt];

  *str++ = 'v';

  color = ~color;

  for (pt = KING; pt >= PAWN; --pt)

    for (i = popcount<Max15>(pos.pieces(color, pt)); i > 0; i--)

      *str++ = pchr[6 - pt];

  *str++ = 0;

}

// Given a position, produce a 64-bit material signature key.

// If the engine supports such a key, it should equal the engine's key.

static uint64 calc_key(Position& pos, int mirror)

{

  Color color;

  PieceType pt;

  int i;

  uint64 key = 0;

  color = !mirror ? WHITE : BLACK;

  for (pt = PAWN; pt <= KING; ++pt)

    for (i = popcount<Max15>(pos.pieces(color, pt)); i > 0; i--)

      key ^= Zobrist::psq[WHITE][pt][i - 1];

  color = ~color;

  for (pt = PAWN; pt <= KING; ++pt)

    for (i = popcount<Max15>(pos.pieces(color, pt)); i > 0; i--)

      key ^= Zobrist::psq[BLACK][pt][i - 1];

  return key;

}

// Produce a 64-bit material key corresponding to the material combination

// defined by pcs[16], where pcs[1], ..., pcs[6] is the number of white

// pawns, ..., kings and pcs[9], ..., pcs[14] is the number of black

// pawns, ..., kings.

static uint64 calc_key_from_pcs(int *pcs, int mirror)

{

  int color;

  PieceType pt;

  int i;

  uint64 key = 0;

  color = !mirror ? 0 : 8;

  for (pt = PAWN; pt <= KING; ++pt)

    for (i = 0; i < pcs[color + pt]; i++)

      key ^= Zobrist::psq[WHITE][pt][i];

  color ^= 8;

  for (pt = PAWN; pt <= KING; ++pt)

    for (i = 0; i < pcs[color + pt]; i++)

      key ^= Zobrist::psq[BLACK][pt][i];

  return key;

}

bool is_little_endian() {

  union {

    int i;

    char c[sizeof(int)];

  } x;

  x.i = 1;

  return x.c[0] == 1;

}

static ubyte decompress_pairs(struct PairsData *d, uint64 idx)

{

  static const bool isLittleEndian = is_little_endian();

  return isLittleEndian ? decompress_pairs<true >(d, idx)

                        : decompress_pairs<false>(d, idx);

}

// probe_wdl_table and probe_dtz_table require similar adaptations.

static int probe_wdl_table(Position& pos, int *success)

{

  struct TBEntry *ptr;

  struct TBHashEntry *ptr2;

  uint64 idx;

  uint64 key;

  int i;

  ubyte res;

  int p[TBPIECES];

  // Obtain the position's material signature key.

  key = pos.material_key();

  // Test for KvK.

  if (key == (Zobrist::psq[WHITE][KING][0] ^ Zobrist::psq[BLACK][KING][0]))

    return 0;

  ptr2 = TB_hash[key >> (64 - TBHASHBITS)];

  for (i = 0; i < HSHMAX; i++)

    if (ptr2[i].key == key) break;

  if (i == HSHMAX) {

    *success = 0;

    return 0;

  }

  ptr = ptr2[i].ptr;

  if (!ptr->ready) {

    LOCK(TB_mutex);

    if (!ptr->ready) {

      char str[16];

      prt_str(pos, str, ptr->key != key);

      if (!init_table_wdl(ptr, str)) {

        ptr2[i].key = 0ULL;

        *success = 0;

        UNLOCK(TB_mutex);

        return 0;

      }

      // Memory barrier to ensure ptr->ready = 1 is not reordered.

#ifdef _MSC_VER

      _ReadWriteBarrier();

#else

      __asm__ __volatile__ ("" ::: "memory");

#endif

      ptr->ready = 1;

    }

    UNLOCK(TB_mutex);

  }

  int bside, mirror, cmirror;

  if (!ptr->symmetric) {

    if (key != ptr->key) {

      cmirror = 8;

      mirror = 0x38;

      bside = (pos.side_to_move() == WHITE);

    } else {

      cmirror = mirror = 0;

      bside = !(pos.side_to_move() == WHITE);

    }

  } else {

    cmirror = pos.side_to_move() == WHITE ? 0 : 8;

    mirror = pos.side_to_move() == WHITE ? 0 : 0x38;

    bside = 0;

  }

  // p[i] is to contain the square 0-63 (A1-H8) for a piece of type

  // pc[i] ^ cmirror, where 1 = white pawn, ..., 14 = black king.

  // Pieces of the same type are guaranteed to be consecutive.

  if (!ptr->has_pawns) {

    struct TBEntry_piece *entry = (struct TBEntry_piece *)ptr;

    ubyte *pc = entry->pieces[bside];

    for (i = 0; i < entry->num;) {

      Bitboard bb = pos.pieces((Color)((pc[i] ^ cmirror) >> 3),

                                      (PieceType)(pc[i] & 0x07));

      do {

        p[i++] = pop_lsb(&bb);

      } while (bb);

    }

    idx = encode_piece(entry, entry->norm[bside], p, entry->factor[bside]);

    res = decompress_pairs(entry->precomp[bside], idx);

  } else {

    struct TBEntry_pawn *entry = (struct TBEntry_pawn *)ptr;

    int k = entry->file[0].pieces[0][0] ^ cmirror;

    Bitboard bb = pos.pieces((Color)(k >> 3), (PieceType)(k & 0x07));

    i = 0;

    do {

      p[i++] = pop_lsb(&bb) ^ mirror;

    } while (bb);

    int f = pawn_file(entry, p);

    ubyte *pc = entry->file[f].pieces[bside];

    for (; i < entry->num;) {

      bb = pos.pieces((Color)((pc[i] ^ cmirror) >> 3),

                                    (PieceType)(pc[i] & 0x07));

      do {

        p[i++] = pop_lsb(&bb) ^ mirror;

      } while (bb);

    }

    idx = encode_pawn(entry, entry->file[f].norm[bside], p, entry->file[f].factor[bside]);

    res = decompress_pairs(entry->file[f].precomp[bside], idx);

  }

  return ((int)res) - 2;

}

static int probe_dtz_table(Position& pos, int wdl, int *success)

{

  struct TBEntry *ptr;

  uint64 idx;

  int i, res;

  int p[TBPIECES];

  // Obtain the position's material signature key.

  uint64 key = pos.material_key();

  if (DTZ_table[0].key1 != key && DTZ_table[0].key2 != key) {

    for (i = 1; i < DTZ_ENTRIES; i++)

      if (DTZ_table[i].key1 == key) break;

    if (i < DTZ_ENTRIES) {

      struct DTZTableEntry table_entry = DTZ_table[i];

      for (; i > 0; i--)

        DTZ_table[i] = DTZ_table[i - 1];

      DTZ_table[0] = table_entry;

    } else {

      struct TBHashEntry *ptr2 = TB_hash[key >> (64 - TBHASHBITS)];

      for (i = 0; i < HSHMAX; i++)

        if (ptr2[i].key == key) break;

      if (i == HSHMAX) {

        *success = 0;

        return 0;

      }

      ptr = ptr2[i].ptr;

      char str[16];

      int mirror = (ptr->key != key);

      prt_str(pos, str, mirror);

      if (DTZ_table[DTZ_ENTRIES - 1].entry)

        free_dtz_entry(DTZ_table[DTZ_ENTRIES-1].entry);

      for (i = DTZ_ENTRIES - 1; i > 0; i--)

        DTZ_table[i] = DTZ_table[i - 1];

      load_dtz_table(str, calc_key(pos, mirror), calc_key(pos, !mirror));

    }

  }

  ptr = DTZ_table[0].entry;

  if (!ptr) {

    *success = 0;

    return 0;

  }

  int bside, mirror, cmirror;

  if (!ptr->symmetric) {

    if (key != ptr->key) {

      cmirror = 8;

      mirror = 0x38;

      bside = (pos.side_to_move() == WHITE);

    } else {

      cmirror = mirror = 0;

      bside = !(pos.side_to_move() == WHITE);

    }

  } else {

    cmirror = pos.side_to_move() == WHITE ? 0 : 8;

    mirror = pos.side_to_move() == WHITE ? 0 : 0x38;

    bside = 0;

  }

  if (!ptr->has_pawns) {

    struct DTZEntry_piece *entry = (struct DTZEntry_piece *)ptr;

    if ((entry->flags & 1) != bside && !entry->symmetric) {

      *success = -1;

      return 0;

    }

    ubyte *pc = entry->pieces;

    for (i = 0; i < entry->num;) {

      Bitboard bb = pos.pieces((Color)((pc[i] ^ cmirror) >> 3),

                                    (PieceType)(pc[i] & 0x07));

      do {

        p[i++] = pop_lsb(&bb);

      } while (bb);

    }

    idx = encode_piece((struct TBEntry_piece *)entry, entry->norm, p, entry->factor);

    res = decompress_pairs(entry->precomp, idx);

    if (entry->flags & 2)

      res = entry->map[entry->map_idx[wdl_to_map[wdl + 2]] + res];

    if (!(entry->flags & pa_flags[wdl + 2]) || (wdl & 1))

      res *= 2;

  } else {

    struct DTZEntry_pawn *entry = (struct DTZEntry_pawn *)ptr;

    int k = entry->file[0].pieces[0] ^ cmirror;

    Bitboard bb = pos.pieces((Color)(k >> 3), (PieceType)(k & 0x07));

    i = 0;

    do {

      p[i++] = pop_lsb(&bb) ^ mirror;

    } while (bb);

    int f = pawn_file((struct TBEntry_pawn *)entry, p);

    if ((entry->flags[f] & 1) != bside) {

      *success = -1;

      return 0;

    }

    ubyte *pc = entry->file[f].pieces;

    for (; i < entry->num;) {

      bb = pos.pieces((Color)((pc[i] ^ cmirror) >> 3),

                            (PieceType)(pc[i] & 0x07));

      do {

        p[i++] = pop_lsb(&bb) ^ mirror;

      } while (bb);

    }

    idx = encode_pawn((struct TBEntry_pawn *)entry, entry->file[f].norm, p, entry->file[f].factor);

    res = decompress_pairs(entry->file[f].precomp, idx);

    if (entry->flags[f] & 2)

      res = entry->map[entry->map_idx[f][wdl_to_map[wdl + 2]] + res];

    if (!(entry->flags[f] & pa_flags[wdl + 2]) || (wdl & 1))

      res *= 2;

  }

  return res;

}

// Add underpromotion captures to list of captures.

static ExtMove *add_underprom_caps(Position& pos, ExtMove *stack, ExtMove *end)

{

  ExtMove *moves, *extra = end;

  for (moves = stack; moves < end; moves++) {

    Move move = moves->move;

    if (type_of(move) == PROMOTION && !pos.empty(to_sq(move))) {

      (*extra++).move = (Move)(move - (1 << 12));

      (*extra++).move = (Move)(move - (2 << 12));

      (*extra++).move = (Move)(move - (3 << 12));

    }

  }

  return extra;

}

static int probe_ab(Position& pos, int alpha, int beta, int *success)

{

  int v;

  ExtMove stack[64];

  ExtMove *moves, *end;

  StateInfo st;

  // Generate (at least) all legal non-ep captures including (under)promotions.

  // It is OK to generate more, as long as they are filtered out below.

  if (!pos.checkers()) {

    end = generate<CAPTURES>(pos, stack);

    // Since underpromotion captures are not included, we need to add them.

    end = add_underprom_caps(pos, stack, end);

  } else

    end = generate<EVASIONS>(pos, stack);

  CheckInfo ci(pos);

  for (moves = stack; moves < end; moves++) {

    Move capture = moves->move;

    if (!pos.capture(capture) || type_of(capture) == ENPASSANT

                        || !pos.legal(capture, ci.pinned))

      continue;

    pos.do_move(capture, st, pos.gives_check(capture, ci));

    v = -probe_ab(pos, -beta, -alpha, success);

    pos.undo_move(capture);

    if (*success == 0) return 0;

    if (v > alpha) {

      if (v >= beta) {

        *success = 2;

        return v;

      }

      alpha = v;

    }

  }

  v = probe_wdl_table(pos, success);

  if (*success == 0) return 0;

  if (alpha >= v) {

    *success = 1 + (alpha > 0);

    return alpha;

  } else {

    *success = 1;

    return v;

  }

}

// Probe the WDL table for a particular position.

// If *success != 0, the probe was successful.

// The return value is from the point of view of the side to move:

// -2 : loss

// -1 : loss, but draw under 50-move rule

//  0 : draw

//  1 : win, but draw under 50-move rule

//  2 : win

int Tablebases::probe_wdl(Position& pos, int *success)

{

  int v;

  *success = 1;

  v = probe_ab(pos, -2, 2, success);

  // If en passant is not possible, we are done.

  if (pos.ep_square() == SQ_NONE)

    return v;

  if (!(*success)) return 0;

  // Now handle en passant.

  int v1 = -3;

  // Generate (at least) all legal en passant captures.

  ExtMove stack[192];

  ExtMove *moves, *end;

  StateInfo st;

  if (!pos.checkers())

    end = generate<CAPTURES>(pos, stack);

  else

    end = generate<EVASIONS>(pos, stack);

  CheckInfo ci(pos);

  for (moves = stack; moves < end; moves++) {

    Move capture = moves->move;

    if (type_of(capture) != ENPASSANT

          || !pos.legal(capture, ci.pinned))

      continue;

    pos.do_move(capture, st, pos.gives_check(capture, ci));

    int v0 = -probe_ab(pos, -2, 2, success);

    pos.undo_move(capture);

    if (*success == 0) return 0;

    if (v0 > v1) v1 = v0;

  }

  if (v1 > -3) {

    if (v1 >= v) v = v1;

    else if (v == 0) {

      // Check whether there is at least one legal non-ep move.

      for (moves = stack; moves < end; moves++) {

        Move capture = moves->move;

        if (type_of(capture) == ENPASSANT) continue;

        if (pos.legal(capture, ci.pinned)) break;

      }

      if (moves == end && !pos.checkers()) {

        end = generate<QUIETS>(pos, end);

        for (; moves < end; moves++) {

          Move move = moves->move;

          if (pos.legal(move, ci.pinned))

            break;

        }

      }

      // If not, then we are forced to play the losing ep capture.

      if (moves == end)

        v = v1;

    }

  }

  return v;

}

// This routine treats a position with en passant captures as one without.

static int probe_dtz_no_ep(Position& pos, int *success)

{

  int wdl, dtz;

  wdl = probe_ab(pos, -2, 2, success);

  if (*success == 0) return 0;

  if (wdl == 0) return 0;

  if (*success == 2)

    return wdl == 2 ? 1 : 101;

  ExtMove stack[192];

  ExtMove *moves, *end = NULL;

  StateInfo st;

  CheckInfo ci(pos);

  if (wdl > 0) {

    // Generate at least all legal non-capturing pawn moves

    // including non-capturing promotions.

    if (!pos.checkers())

      end = generate<NON_EVASIONS>(pos, stack);

    else

      end = generate<EVASIONS>(pos, stack);

    for (moves = stack; moves < end; moves++) {

      Move move = moves->move;

      if (type_of(pos.moved_piece(move)) != PAWN || pos.capture(move)

                || !pos.legal(move, ci.pinned))

        continue;

      pos.do_move(move, st, pos.gives_check(move, ci));

      int v = -probe_ab(pos, -2, -wdl + 1, success);

      pos.undo_move(move);

      if (*success == 0) return 0;

      if (v == wdl)

        return v == 2 ? 1 : 101;

    }

  }

  dtz = 1 + probe_dtz_table(pos, wdl, success);

  if (*success >= 0) {

    if (wdl & 1) dtz += 100;

    return wdl >= 0 ? dtz : -dtz;

  }

  if (wdl > 0) {

    int best = 0xffff;

    for (moves = stack; moves < end; moves++) {

      Move move = moves->move;

      if (pos.capture(move) || type_of(pos.moved_piece(move)) == PAWN

                || !pos.legal(move, ci.pinned))

        continue;

      pos.do_move(move, st, pos.gives_check(move, ci));

      int v = -Tablebases::probe_dtz(pos, success);

      pos.undo_move(move);

      if (*success == 0) return 0;

      if (v > 0 && v + 1 < best)

        best = v + 1;

    }

    return best;

  } else {

    int best = -1;

    if (!pos.checkers())

      end = generate<NON_EVASIONS>(pos, stack);

    else

      end = generate<EVASIONS>(pos, stack);

    for (moves = stack; moves < end; moves++) {

      int v;

      Move move = moves->move;

      if (!pos.legal(move, ci.pinned))

        continue;

      pos.do_move(move, st, pos.gives_check(move, ci));

      if (st.rule50 == 0) {

        if (wdl == -2) v = -1;

        else {

          v = probe_ab(pos, 1, 2, success);

          v = (v == 2) ? 0 : -101;

        }

      } else {

        v = -Tablebases::probe_dtz(pos, success) - 1;

      }

      pos.undo_move(move);

      if (*success == 0) return 0;

      if (v < best)

        best = v;

    }

    return best;

  }

}

static int wdl_to_dtz[] = {

  -1, -101, 0, 101, 1

};

// Probe the DTZ table for a particular position.

// If *success != 0, the probe was successful.

// The return value is from the point of view of the side to move:

//         n < -100 : loss, but draw under 50-move rule

// -100 <= n < -1   : loss in n ply (assuming 50-move counter == 0)

//         0        : draw

//     1 < n <= 100 : win in n ply (assuming 50-move counter == 0)

//   100 < n        : win, but draw under 50-move rule

//

// The return value n can be off by 1: a return value -n can mean a loss

// in n+1 ply and a return value +n can mean a win in n+1 ply. This

// cannot happen for tables with positions exactly on the "edge" of

// the 50-move rule.

//

// This implies that if dtz > 0 is returned, the position is certainly

// a win if dtz + 50-move-counter <= 99. Care must be taken that the engine

// picks moves that preserve dtz + 50-move-counter <= 99.

//

// If n = 100 immediately after a capture or pawn move, then the position

// is also certainly a win, and during the whole phase until the next

// capture or pawn move, the inequality to be preserved is

// dtz + 50-movecounter <= 100.

//

// In short, if a move is available resulting in dtz + 50-move-counter <= 99,

// then do not accept moves leading to dtz + 50-move-counter == 100.

//

int Tablebases::probe_dtz(Position& pos, int *success)

{

  *success = 1;

  int v = probe_dtz_no_ep(pos, success);

  if (pos.ep_square() == SQ_NONE)

    return v;

  if (*success == 0) return 0;

  // Now handle en passant.

  int v1 = -3;

  ExtMove stack[192];

  ExtMove *moves, *end;

  StateInfo st;

  if (!pos.checkers())

    end = generate<CAPTURES>(pos, stack);

  else

    end = generate<EVASIONS>(pos, stack);

  CheckInfo ci(pos);

  for (moves = stack; moves < end; moves++) {

    Move capture = moves->move;

    if (type_of(capture) != ENPASSANT

                || !pos.legal(capture, ci.pinned))

      continue;

    pos.do_move(capture, st, pos.gives_check(capture, ci));

    int v0 = -probe_ab(pos, -2, 2, success);

    pos.undo_move(capture);

    if (*success == 0) return 0;

    if (v0 > v1) v1 = v0;

  }

  if (v1 > -3) {

    v1 = wdl_to_dtz[v1 + 2];

    if (v < -100) {

      if (v1 >= 0)

        v = v1;

    } else if (v < 0) {

      if (v1 >= 0 || v1 < -100)

        v = v1;

    } else if (v > 100) {

      if (v1 > 0)

        v = v1;

    } else if (v > 0) {

      if (v1 == 1)

        v = v1;

    } else if (v1 >= 0) {

      v = v1;

    } else {

      for (moves = stack; moves < end; moves++) {

        Move move = moves->move;

        if (type_of(move) == ENPASSANT) continue;

        if (pos.legal(move, ci.pinned)) break;

      }

      if (moves == end && !pos.checkers()) {

        end = generate<QUIETS>(pos, end);

        for (; moves < end; moves++) {

          Move move = moves->move;

          if (pos.legal(move, ci.pinned))

            break;

        }

      }

      if (moves == end)

        v = v1;

    }

  }

  return v;

}

// Check whether there has been at least one repetition of positions

// since the last capture or pawn move.

static int has_repeated(StateInfo *st)

{

  while (1) {

    int i = 4, e = std::min(st->rule50, st->pliesFromNull);

    if (e < i)

      return 0;

    StateInfo *stp = st->previous->previous;

    do {

      stp = stp->previous->previous;

      if (stp->key == st->key)

        return 1;

      i += 2;

    } while (i <= e);

    st = st->previous;

  }

}

static Value wdl_to_Value[5] = {

  -VALUE_MATE + MAX_PLY + 1,

  VALUE_DRAW - 2,

  VALUE_DRAW,

  VALUE_DRAW + 2,

  VALUE_MATE - MAX_PLY - 1

};

// Use the DTZ tables to filter out moves that don't preserve the win or draw.

// If the position is lost, but DTZ is fairly high, only keep moves that

// maximise DTZ.

//

// A return value false indicates that not all probes were successful and that

// no moves were filtered out.

bool Tablebases::root_probe(Position& pos, Search::RootMoveVector& rootMoves, Value& score)

{

  int success;

  int dtz = probe_dtz(pos, &success);

  if (!success) return false;

  StateInfo st;

  CheckInfo ci(pos);