Scid  4.6.5
fastgame.h
Go to the documentation of this file.
1 /*
2 * Copyright (C) 2013-2015 Fulvio Benini
3 
4 * This file is part of Scid (Shane's Chess Information Database).
5 *
6 * Scid 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.
9 *
10 * Scid is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with Scid. If not, see <http://www.gnu.org/licenses/>.
17 */
18 
19 #ifndef FASTGAME_H
20 #define FASTGAME_H
21 
22 #include "common.h"
23 #include "fullmove.h"
24 #include "position.h"
25 #include <cstdlib>
26 #include <cstring>
27 #include <sstream>
28 #include <string>
29 
30 class FastBoard {
31  byte board_[64];
32  uint8_t nPieces_[2][8];
33  struct P_LIST {
34  squareT sq;
35  pieceT piece;
36  } list[2][16];
37 
38 public:
39  FastBoard() {}
40  FastBoard(Position& pos) { Init(pos); }
41 
42  void Init() {
43  static Position StdStartPos(Position::getStdStart());
44  static FastBoard StdStart(StdStartPos);
45  *this = StdStart;
46  }
47 
48  void Init(Position& pos) {
49  std::memset(nPieces_, 0, sizeof(nPieces_));
50  std::memset(board_, 0, sizeof(board_));
51  for (byte c=0; c<2; c++) {
52  nPieces_[c][0] = pos.GetCount(c);
53  for (uint i=0, n = nPieces_[c][0]; i < n; ++i) {
54  squareT sq = pos.GetList(c)[i];
55  pieceT piece = piece_Type(pos.GetBoard()[sq]);
56  list[c][i].sq = sq;
57  list[c][i].piece = piece;
58  board_[sq] = i;
59  nPieces_[c][piece] += 1;
60  }
61  }
62  }
63 
64  bool isEqual(const pieceT* board, const byte* nPiecesW, const byte* nPiecesB) const {
65  const uint64_t* w = reinterpret_cast<const uint64_t*>(nPieces_[WHITE]);
66  const uint64_t* b = reinterpret_cast<const uint64_t*>(nPieces_[BLACK]);
67  const uint64_t* Sw = reinterpret_cast<const uint64_t*>(nPiecesW);
68  const uint64_t* Sb = reinterpret_cast<const uint64_t*>(nPiecesB);
69  if (*w != *Sw || *b != *Sb) return false;
70  for (int i=0, n = nPieces_[WHITE][0]; i < n; i++) {
71  const P_LIST* p = & list[WHITE][i];
72  if (board[p->sq] != piece_Make(WHITE, p->piece)) return false;
73  }
74  for (int i=0, n = nPieces_[BLACK][0]; i < n; i++) {
75  const P_LIST* p = & list[BLACK][i];
76  if (board[p->sq] != piece_Make(BLACK, p->piece)) return false;
77  }
78  return true;
79  }
80 
81  template <colorT color>
82  squareT getSquare(byte idx) const {
83  return list[color][idx].sq;
84  }
85 
86  template <colorT color>
87  pieceT getPiece(byte idx) const {
88  return list[color][idx].piece;
89  }
90 
91  template <colorT color>
92  uint8_t getCount(pieceT p = 0) const {
93  ASSERT(p < 8);
94  return nPieces_[color][p];
95  }
96 
97  template <colorT color>
98  void castle(squareT king_to, squareT rook_from, squareT rook_to) {
99  const byte king_idx = 0;
100  const byte rook_idx = board_[rook_from];
101  list[color][rook_idx].sq = rook_to;
102  list[color][king_idx].sq = king_to;
103  board_[rook_to] = rook_idx;
104  board_[rook_from] = 0;
105  board_[king_to] = king_idx;
106  // board_[king_from] = 0; //Is not necessary because King_idx == 0
107  }
108 
109  template <colorT color>
111  if (promo != 0) {
112  list[color][idx].piece = promo;
113  nPieces_[color][PAWN] -= 1;
114  nPieces_[color][promo] += 1;
115  }
116  board_[ list[color][idx].sq ] = 0;
117  list[color][idx].sq = to;
118  return remove< 1 - color >(to, idx);
119  }
120 
121  template <colorT color>
122  pieceT remove (squareT sq, byte newIdx = 0) {
123  const byte oldIdx = board_[sq];
124  board_[sq] = newIdx;
125  if (oldIdx == 0) return 0;
126 
127  pieceT res = list[color][oldIdx].piece;
128  nPieces_[color][res] -= 1;
129  nPieces_[color][0] -= 1;
130  if (oldIdx != nPieces_[color][0]) {
131  list[color][oldIdx] = list[color][ nPieces_[color][0] ];
132  ASSERT(list[color][oldIdx].sq != sq);
133  board_[ list[color][oldIdx].sq ] = oldIdx;
134  }
135  return res;
136  }
137 
138  void fillSANInfo(FullMove& lastmove) const {
139  pieceT piece = lastmove.getPiece();
140  colorT col = lastmove.getColor();
141  if (isCheck(col)) lastmove.setCheck();
142  if (piece == PAWN || nPieces_[col][piece] <= 1) return;
143  squareT to = lastmove.getTo();
144  for (size_t i=1, n = nPieces_[col][0]; i < n; i++) { //i=1 because King_idx == 0
145  if (list[col][i].piece == piece) {
146  squareT from = list[col][i].sq;
147  if (from != to && !FastBoard::invalidMove(piece, list[col][i].sq, to)) {
148  FullMove tmp;
149  tmp.reset(col, piece, from, to);
150  /*TODO:
151  - Check for obstacles (including lastmove.getFrom() square);
152  - Check for pinned piece (do not leave the king in check)
153  */
154  lastmove.setAmbiguous(tmp);
155  }
156  }
157  }
158  }
159 
160 private:
161  template <bool once>
162  inline pieceT getNeighbor(int col, int row, int col_off, int row_off) const {
163  ASSERT(col_off != 0 || row_off !=0);
164  do {
165  col += col_off;
166  row += row_off;
167  if (row < 0 || row > 7 || col < 0 || col > 7) break;
168  uint8_t sq = col + row*8;
169  uint8_t idx = board_[sq];
170  if (idx != 0) {
171  if (idx < nPieces_[WHITE][0] && list[WHITE][idx].sq == sq)
172  return piece_Make(WHITE, list[WHITE][idx].piece);
173 
174  return piece_Make(BLACK, list[BLACK][idx].piece);
175  }
176  } while (!once);
177 
178  return END_OF_BOARD;
179  }
180 
181  bool isCheck(colorT enemy) const {
182  const int kingSq = list[1- enemy][0].sq;
183  const int kingCol = kingSq % 8;
184  const int kingRow = kingSq / 8;
185 
186  const pieceT pQ = piece_Make(enemy, QUEEN);
187  const pieceT pB = piece_Make(enemy, BISHOP);
188  static const int bishop[] = { +1, +1, +1, -1, -1, -1, -1, +1 };
189  for (size_t i=0, n = sizeof(bishop)/sizeof(int); i < n; i+= 2) {
190  const pieceT p = getNeighbor<false>(kingCol, kingRow, bishop[i], bishop[i+1]);
191  if (p == pB || p == pQ) return true;
192  }
193 
194  const pieceT pR = piece_Make(enemy, ROOK);
195  static const int rook[] = { +1, 0, -1, 0, 0, +1, 0, -1 };
196  for (size_t i=0, n = sizeof(rook)/sizeof(int); i < n; i+= 2) {
197  const pieceT p = getNeighbor<false>(kingCol, kingRow, rook[i], rook[i+1]);
198  if (p == pR || p == pQ) return true;
199  }
200 
201  const pieceT pN = piece_Make(enemy, KNIGHT);
202  static const int knight[] = { +1, +2, +1, -2, -1, +2, -1, -2, +2, +1, +2, -1, -2, +1, -2, -1 };
203  for (size_t i=0, n = sizeof(knight)/sizeof(int); i < n; i+= 2) {
204  const pieceT p = getNeighbor<true>(kingCol, kingRow, knight[i], knight[i+1]);
205  if (p == pN) return true;
206  }
207 
208  const pieceT pP = piece_Make(enemy, PAWN);
209  const int p_row = (enemy == BLACK) ? 1 : -1;
210  if (pP == getNeighbor<true>(kingCol, kingRow, +1, p_row)) return true;
211  if (pP == getNeighbor<true>(kingCol, kingRow, -1, p_row)) return true;
212 
213  return false;
214  }
215 
216  static bool invalidMove(pieceT p, squareT from, squareT to) {
217  const int fromCol = from % 8;
218  const int fromRow = from / 8;
219  const int toCol = to % 8;
220  const int toRow = to / 8;
221  const int dCol = std::abs(fromCol - toCol);
222  const int dRow = std::abs(fromRow - toRow);
223 
224  if (dCol == dRow) { //Diagonal
225  if (dCol != 0 && (p == BISHOP || p == QUEEN)) return false;
226  } else if (dCol == 0 || dRow == 0) { //Linear
227  if (p == ROOK || p == QUEEN) return false;
228  } else if (p == KNIGHT) {
229  if ((dCol == 1 || dCol == 2) && (dRow == 1 || dRow == 2)) return false;
230  }
231  return true;
232  }
233 
234 };
235 
236 
237 
238 class FastGame {
239  FastBoard board_;
240  const byte* v_it_;
241  const byte* v_end_;
242  colorT cToMove_;
243 
244 public:
245  static FastGame Create(const byte* v_begin, const byte* v_end) {
246  const byte* v_it = v_begin;
247  while (v_it < v_end) {
248  byte b = *v_it++;
249  if (b == 0) {
250  if (v_it >= v_end) break; // Error
251  byte haveFEN = *v_it++ & 1;
252  if (haveFEN == 0) {
253  return FastGame(v_it, v_end);
254  } else {
255  const char* FENstring = (char*) v_it;
256  while (v_it < v_end) {
257  if (*v_it++ == 0) return FastGame(FENstring, v_it, v_end);
258  }
259  break; // FEN error
260  }
261  } else if (b == 255) { // Skip special 3-byte binary encoding of EventDate
262  v_it += 3;
263  } else { // Skip tags
264  enum { MAX_TAG_LEN = 240 };
265  if (b <= MAX_TAG_LEN) v_it += b;
266  if (v_it < v_end) v_it += *v_it +1;
267  }
268  }
269 
270  return FastGame(0,0); // Error default to StdStart and empty buffer
271  }
272 
273  FullMove getMove(int ply_to_skip) {
274  FullMove move;
275  Dummy dummy;
276 
277  for (int ply=0; ply <= ply_to_skip; ply++, cToMove_ = 1 - cToMove_) {
278  if (cToMove_ == WHITE) {
279  if (! DecodeNextMove <WHITE>(move, dummy)) break;
280  } else {
281  if (! DecodeNextMove <BLACK>(move, dummy)) break;
282  }
283 
284  if (ply == ply_to_skip) {
285  board_.fillSANInfo(move);
286  cToMove_ = 1 - cToMove_;
287  return move;
288  }
289  }
290  return FullMove();
291  }
292 
293  std::string getMoveSAN(int ply_to_skip, int count) {
294  std::stringstream res;
295  Dummy dummy;
296  for (int ply=0; ply < ply_to_skip + count; ply++, cToMove_ = 1 - cToMove_) {
297  FullMove move;
298  if (cToMove_ == WHITE) {
299  if (! DecodeNextMove <WHITE>(move, dummy)) break;
300  if (ply < ply_to_skip) continue;
301  if (ply > ply_to_skip) res << " ";
302  res << (1 + ply/2) << ".";
303  } else {
304  if (! DecodeNextMove <BLACK>(move, dummy)) break;
305  if (ply < ply_to_skip) continue;
306  if (ply == ply_to_skip) res << (1 + ply/2) << "...";
307  else res << " ";
308  }
309  board_.fillSANInfo(move);
310  res << move.getSAN();
311  }
312  return res.str();
313  }
314 
315  template <colorT toMove>
316  int search(const byte* board, const uint8_t (&nPieces) [2][8]) {
317  int ply = 1;
318  Dummy dummy;
319  MinPieces minP(nPieces);
320 
321  if (cToMove_ != toMove) {
322  if (! DecodeNextMove<1 - toMove>(dummy, minP)) return 0;
323  ply += 1;
324  }
325  for (;;) {
326  if (board_.isEqual(board, nPieces[WHITE], nPieces[BLACK])) return ply;
327  if (! DecodeNextMove<toMove>(dummy, minP)) return 0;
328  if (! DecodeNextMove<1 - toMove>(dummy, minP)) return 0;
329  ply += 2;
330  }
331  return 0;
332  }
333 
334 private:
335  FastGame(const byte* v_it, const byte* v_end)
336  : v_it_ (v_it), v_end_(v_end), cToMove_(WHITE) {
337  board_.Init();
338  }
339 
340  FastGame(const char* FEN, const byte* v_it, const byte* v_end)
341  : v_it_ (v_it), v_end_(v_end) {
342  Position StartPos;
343  if (FEN == 0 || StartPos.ReadFromFEN(FEN) != OK) StartPos.StdStart();
344  board_.Init(StartPos);
345  cToMove_ = StartPos.GetToMove();
346  }
347 
348  template <colorT toMove, typename P1, typename P2>
349  inline bool DecodeNextMove(P1& p1, const P2& p2) {
351  enum { ENCODE_FIRST = 11, ENCODE_LAST = 15 };
352 
353  while (v_it_ < v_end_) {
354  byte b = *v_it_++;
355  if (b < ENCODE_FIRST || b > ENCODE_LAST) return doPly<toMove>(b, p1, p2);
356  if (b == ENCODE_END_GAME || b == ENCODE_END_MARKER) return false;
357  if (b == ENCODE_NAG) {v_it_++; continue; }
358  if (b == ENCODE_START_MARKER) {
359  uint nestCount = 1;
360  do {
361  if (v_it_ >= v_end_) return false;
362  switch (*v_it_++) {
363  case ENCODE_NAG: v_it_++; break;
364  case ENCODE_START_MARKER: nestCount++; break;
365  case ENCODE_END_MARKER: nestCount--; break;
366  case ENCODE_END_GAME: return false;
367  }
368  } while (nestCount > 0);
369  }
370  }
371  return false;
372  }
373 
374  template <colorT toMove, typename P1, typename P2>
375  inline bool doPly(byte v, P1& lastMove, const P2& minPieces) {
376  byte idx_piece_moving = v >> 4;
377  byte move = v & 0x0F;
378  pieceT moving_piece = board_.getPiece<toMove>(idx_piece_moving);
379  squareT from = board_.getSquare<toMove>(idx_piece_moving);
380  squareT to;
381  pieceT promo = 0;
382  bool enPassant = false;
383  switch (moving_piece) {
384  case PAWN: to = decodePawn<toMove>(from, move, promo, enPassant); break;
385  case BISHOP: to = decodeBishop(from, move); break;
386  case KNIGHT: to = decodeKnight(from, move); break;
387  case ROOK: to = decodeRook(from, move); break;
388  case QUEEN:
389  if (move != square_Fyle(from)) to = decodeRook(from, move);
390  else if (v_it_ < v_end_) to = decodeQueen2byte(*v_it_++);
391  else return false;
392  break;
393  default: // Default to KING
394  if (move == 0) { // NULL MOVE
395  lastMove.reset(toMove, KING, 0, 0);
396  return true;
397  }
398  if (move > 8) { // CASTLE
399  const squareT black = (toMove == WHITE) ? 0 : 56;
400  squareT king_to, rook_from, rook_to;
401  if (move == 10) { // King Side
402  king_to = black + G1;
403  rook_from = black + H1;
404  rook_to = black + F1;
405  } else { // Queen Side
406  king_to = black + C1;
407  rook_from = black + A1;
408  rook_to = black + D1;
409  }
410  const byte king_idx = 0;
411  lastMove.resetCastle(toMove, board_.getSquare<toMove>(king_idx), rook_from);
412  board_.castle<toMove>(king_to, rook_from, rook_to);
413  // ClearCastlingRights;
414  return true;
415  }
416  to = decodeKing(from, move);
417  }
418 
419  lastMove.reset(toMove, moving_piece, from, to, promo);
420  const colorT enemy = 1 - toMove;
421  pieceT captured = board_.move<toMove> (idx_piece_moving, to, promo);
422  if (captured == 0) {
423  if (!enPassant) return true;
424  captured = PAWN;
425  squareT sq = (toMove == WHITE) ? to - 8 : to + 8;
426  board_.remove<enemy>(0x3F & sq);
427  }
428  lastMove.setCapture(captured, enPassant);
429 
430  return minPieces(enemy, captured, board_.getCount<enemy>(),
431  board_.getCount<enemy>(PAWN) + board_.getCount<enemy>(captured));
432  }
433 
434  /**
435  * decode*() - decode a move from Scid format
436  * @from: start square of the moving piece
437  * @val: index of the target square
438  *
439  * Excluding queens, the other chess pieces cannot reach more than 16 target
440  * squares from any given position. This allow to store the target square of
441  * a move into 4 bits, as an index of all the possible target squares.
442  * Return:
443  * - the target square
444  * Error handling:
445  * - Debug code will check if the decoded value is a valid [0-63] square.
446  * - Release code will force the returned valid to be a valid [0-63] square
447  * but, for performance reasons, do not report invalid encoded moves.
448  */
449  static inline squareT square_forceValid(int sq) {
450  ASSERT(sq >= 0 && sq <= 63);
451  return 0x3F & static_cast<squareT>(sq);
452  }
453  static inline squareT decodeKing(squareT from, byte val) {
454  ASSERT(val <= 8);
455  static const int sqdiff[] = {0, -9, -8, -7, -1, 1, 7, 8, 9};
456  int to = static_cast<int>(from) + sqdiff[val];
457  return square_forceValid(to);
458  }
459  static inline squareT decodeQueen2byte(byte val) {
460  int to = static_cast<int>(val) - 64;
461  return square_forceValid(to);
462  }
463  static inline squareT decodeBishop(squareT from, byte val) {
464  int fylediff = static_cast<int>(square_Fyle(val)) -
465  static_cast<int>(square_Fyle(from));
466  int to = (val >= 8) ? static_cast<int>(from) - 7 * fylediff
467  : static_cast<int>(from) + 9 * fylediff;
468  return square_forceValid(to);
469  }
470  static inline squareT decodeKnight(squareT from, byte val) {
471  ASSERT(val <= 16);
472  static const int sqdiff[] = {0, -17, -15, -10, -6, 6, 10, 15, 17, 0, 0, 0, 0, 0, 0, 0};
473  int to = static_cast<int>(from) + sqdiff[val];
474  return square_forceValid(to);
475  }
476  static inline squareT decodeRook(squareT from, byte val) {
477  ASSERT(val <= 16);
478  if (val >= 8)
479  return square_Make(square_Fyle(from), (val - 8));
480  else
481  return square_Make(val, square_Rank(from));
482  }
483  template <colorT color>
484  static inline squareT decodePawn(squareT from, byte val, pieceT& promo,
485  bool& enPassant) {
486  ASSERT(val <= 16);
487  static const int sqdiff [] = { 7,8,9, 7,8,9, 7,8,9, 7,8,9, 7,8,9, 16 };
488  static const pieceT promoPieceFromVal [] = {
490  };
491  promo = promoPieceFromVal[val];
492  enPassant = (val == 0 || val == 2);
493  int to = (color == WHITE) ? static_cast<int>(from) + sqdiff[val]
494  : static_cast<int>(from) - sqdiff[val];
495  return square_forceValid(to);
496  }
497 
498  struct Dummy {
499  void reset(colorT, pieceT, squareT, squareT, pieceT = 0) {}
500  void resetCastle(colorT, squareT, squareT) {}
501  void setCapture(pieceT, bool) {}
502  bool operator()(colorT, pieceT, uint8_t, uint8_t) const { return true; }
503  };
504 
505  class MinPieces{
506  const uint8_t (&m_)[2][8];
507  public:
508  MinPieces(const uint8_t (&m)[2][8]) : m_(m) {}
509  bool operator()(colorT col, pieceT p, uint8_t tot, uint8_t p_count) const {
510  return (tot >= m_[col][0] && p_count >= (m_[col][PAWN] + m_[col][p]));
511  }
512  };
513 
514 };
515 
516 
517 #endif
unsigned char byte
Definition: common.h:97
piecew sq
Definition: board.tcl:1293
const colorT WHITE
Definition: common.h:203
void castle(squareT king_to, squareT rook_from, squareT rook_to)
Definition: fastgame.h:98
pieceT piece_Type(pieceT p)
Definition: common.h:287
uint GetCount(colorT c)
Definition: position.h:163
squareT getTo() const
Definition: fullmove.h:55
sqsqname
Definition: board.tcl:292
FullMove getMove(int ply_to_skip)
Definition: fastgame.h:273
pieceT getPiece(byte idx) const
Definition: fastgame.h:87
FastBoard(Position &pos)
Definition: fastgame.h:40
const errorT OK
Definition: error.h:23
const squareT H1
Definition: common.h:343
promopiece
Definition: calvar.tcl:255
void Init()
Definition: fastgame.h:42
static const Position & getStdStart()
Definition: position.cpp:595
#define ASSERT(f)
Definition: common.h:67
uint8_t getCount(pieceT p=0) const
Definition: fastgame.h:92
const squareT C1
Definition: common.h:343
#define ENCODE_COMMENT
Definition: game.cpp:3306
const pieceT KING
Definition: common.h:221
void setAmbiguous(const FullMove &move2)
Definition: fullmove.h:116
const colorT BLACK
Definition: common.h:204
bool isEqual(const pieceT *board, const byte *nPiecesW, const byte *nPiecesB) const
Definition: fastgame.h:64
rankT square_Rank(squareT sq)
Definition: common.h:385
errorT ReadFromFEN(const char *s)
Definition: position.cpp:2812
FastBoard()
Definition: fastgame.h:39
const pieceT BISHOP
Definition: common.h:224
const squareT A1
Definition: common.h:343
const pieceT KNIGHT
Definition: common.h:225
squareT square_Make(fyleT f, rankT r)
Definition: common.h:372
colorpct?col?
Definition: ptracker.tcl:77
static FastGame Create(const byte *v_begin, const byte *v_end)
Definition: fastgame.h:245
#define ENCODE_NAG
Definition: game.cpp:3305
const squareT G1
Definition: common.h:343
const pieceT QUEEN
Definition: common.h:222
uint32_t uint
Definition: common.h:99
Definition: board.tcl:276
std::string getSAN(colorT *toMove=0) const
Definition: fullmove.h:66
const pieceT ROOK
Definition: common.h:223
Definition: move.tcl:20
void StdStart()
Definition: position.h:145
pieceT move(byte idx, squareT to, pieceT promo)
Definition: fastgame.h:110
squareT * GetList(colorT c)
Definition: position.h:162
std::string getMoveSAN(int ply_to_skip, int count)
Definition: fastgame.h:293
const pieceT PAWN
Definition: common.h:226
const squareT D1
Definition: common.h:343
const uint MAX_TAG_LEN
Definition: game.h:113
#define ENCODE_FIRST
Definition: game.cpp:3311
squareT getSquare(byte idx) const
Definition: fastgame.h:82
void Init(Position &pos)
Definition: fastgame.h:48
const pieceT * GetBoard() const
Definition: position.h:189
const pieceT END_OF_BOARD
Definition: common.h:235
byte colorT
Definition: common.h:112
colorT getColor() const
Definition: fullmove.h:58
int search(const byte *board, const uint8_t(&nPieces)[2][8])
Definition: fastgame.h:316
colorT GetToMove()
Definition: position.h:155
pieceT remove(squareT sq, byte newIdx=0)
Definition: fastgame.h:122
void setCheck()
Definition: fullmove.h:124
void reset(colorT c, pieceT p, squareT from, squareT to, pieceT promo=0)
Definition: fullmove.h:104
#define ENCODE_START_MARKER
Definition: game.cpp:3307
void fillSANInfo(FullMove &lastmove) const
Definition: fastgame.h:138
#define ENCODE_END_GAME
Definition: game.cpp:3309
const squareT F1
Definition: common.h:343
pieceT piece_Make(colorT c, pieceT p)
Definition: common.h:290
#define ENCODE_LAST
Definition: game.cpp:3312
pieceT getPiece() const
Definition: fullmove.h:57
byte squareT
Definition: common.h:113
byte pieceT
Definition: common.h:111
fyleT square_Fyle(squareT sq)
Definition: common.h:379
#define ENCODE_END_MARKER
Definition: game.cpp:3308