File: bitbase.cpp

package info (click to toggle)
stockfish 12-2
  • links: PTS
  • area: main
  • in suites: bullseye, sid
  • size: 21,436 kB
  • sloc: cpp: 9,020; makefile: 740; ansic: 199; sh: 193
file content (170 lines) | stat: -rw-r--r-- 5,814 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
/*
  Stockfish, a UCI chess playing engine derived from Glaurung 2.1
  Copyright (C) 2004-2020 The Stockfish developers (see AUTHORS file)

  Stockfish 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.

  Stockfish 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 <cassert>
#include <vector>
#include <bitset>

#include "bitboard.h"
#include "types.h"

namespace {

  // There are 24 possible pawn squares: files A to D and ranks from 2 to 7.
  // Positions with the pawn on files E to H will be mirrored before probing.
  constexpr unsigned MAX_INDEX = 2*24*64*64; // stm * psq * wksq * bksq = 196608

  std::bitset<MAX_INDEX> KPKBitbase;

  // A KPK bitbase index is an integer in [0, IndexMax] range
  //
  // Information is mapped in a way that minimizes the number of iterations:
  //
  // bit  0- 5: white king square (from SQ_A1 to SQ_H8)
  // bit  6-11: black king square (from SQ_A1 to SQ_H8)
  // bit    12: side to move (WHITE or BLACK)
  // bit 13-14: white pawn file (from FILE_A to FILE_D)
  // bit 15-17: white pawn RANK_7 - rank (from RANK_7 - RANK_7 to RANK_7 - RANK_2)
  unsigned index(Color stm, Square bksq, Square wksq, Square psq) {
    return int(wksq) | (bksq << 6) | (stm << 12) | (file_of(psq) << 13) | ((RANK_7 - rank_of(psq)) << 15);
  }

  enum Result {
    INVALID = 0,
    UNKNOWN = 1,
    DRAW    = 2,
    WIN     = 4
  };

  Result& operator|=(Result& r, Result v) { return r = Result(r | v); }

  struct KPKPosition {
    KPKPosition() = default;
    explicit KPKPosition(unsigned idx);
    operator Result() const { return result; }
    Result classify(const std::vector<KPKPosition>& db);

    Color stm;
    Square ksq[COLOR_NB], psq;
    Result result;
  };

} // namespace


bool Bitbases::probe(Square wksq, Square wpsq, Square bksq, Color stm) {

  assert(file_of(wpsq) <= FILE_D);

  return KPKBitbase[index(stm, bksq, wksq, wpsq)];
}


void Bitbases::init() {

  std::vector<KPKPosition> db(MAX_INDEX);
  unsigned idx, repeat = 1;

  // Initialize db with known win / draw positions
  for (idx = 0; idx < MAX_INDEX; ++idx)
      db[idx] = KPKPosition(idx);

  // Iterate through the positions until none of the unknown positions can be
  // changed to either wins or draws (15 cycles needed).
  while (repeat)
      for (repeat = idx = 0; idx < MAX_INDEX; ++idx)
          repeat |= (db[idx] == UNKNOWN && db[idx].classify(db) != UNKNOWN);

  // Fill the bitbase with the decisive results
  for (idx = 0; idx < MAX_INDEX; ++idx)
      if (db[idx] == WIN)
          KPKBitbase.set(idx);
}


namespace {

  KPKPosition::KPKPosition(unsigned idx) {

    ksq[WHITE] = Square((idx >>  0) & 0x3F);
    ksq[BLACK] = Square((idx >>  6) & 0x3F);
    stm        = Color ((idx >> 12) & 0x01);
    psq        = make_square(File((idx >> 13) & 0x3), Rank(RANK_7 - ((idx >> 15) & 0x7)));

    // Invalid if two pieces are on the same square or if a king can be captured
    if (   distance(ksq[WHITE], ksq[BLACK]) <= 1
        || ksq[WHITE] == psq
        || ksq[BLACK] == psq
        || (stm == WHITE && (pawn_attacks_bb(WHITE, psq) & ksq[BLACK])))
        result = INVALID;

    // Win if the pawn can be promoted without getting captured
    else if (   stm == WHITE
             && rank_of(psq) == RANK_7
             && ksq[WHITE] != psq + NORTH
             && (    distance(ksq[BLACK], psq + NORTH) > 1
                 || (distance(ksq[WHITE], psq + NORTH) == 1)))
        result = WIN;

    // Draw if it is stalemate or the black king can capture the pawn
    else if (   stm == BLACK
             && (  !(attacks_bb<KING>(ksq[BLACK]) & ~(attacks_bb<KING>(ksq[WHITE]) | pawn_attacks_bb(WHITE, psq)))
                 || (attacks_bb<KING>(ksq[BLACK]) & ~attacks_bb<KING>(ksq[WHITE]) & psq)))
        result = DRAW;

    // Position will be classified later
    else
        result = UNKNOWN;
  }

  Result KPKPosition::classify(const std::vector<KPKPosition>& db) {

    // White to move: If one move leads to a position classified as WIN, the result
    // of the current position is WIN. If all moves lead to positions classified
    // as DRAW, the current position is classified as DRAW, otherwise the current
    // position is classified as UNKNOWN.
    //
    // Black to move: If one move leads to a position classified as DRAW, the result
    // of the current position is DRAW. If all moves lead to positions classified
    // as WIN, the position is classified as WIN, otherwise the current position is
    // classified as UNKNOWN.
    const Result Good = (stm == WHITE ? WIN   : DRAW);
    const Result Bad  = (stm == WHITE ? DRAW  : WIN);

    Result r = INVALID;
    Bitboard b = attacks_bb<KING>(ksq[stm]);

    while (b)
        r |= stm == WHITE ? db[index(BLACK, ksq[BLACK] , pop_lsb(&b), psq)]
                          : db[index(WHITE, pop_lsb(&b),  ksq[WHITE], psq)];

    if (stm == WHITE)
    {
        if (rank_of(psq) < RANK_7)      // Single push
            r |= db[index(BLACK, ksq[BLACK], ksq[WHITE], psq + NORTH)];

        if (   rank_of(psq) == RANK_2   // Double push
            && psq + NORTH != ksq[WHITE]
            && psq + NORTH != ksq[BLACK])
            r |= db[index(BLACK, ksq[BLACK], ksq[WHITE], psq + NORTH + NORTH)];
    }

    return result = r & Good  ? Good  : r & UNKNOWN ? UNKNOWN : Bad;
  }

} // namespace