Line data Source code
1 : /*
2 : * Copyright (C) 2011-2017 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 : /** @file
20 : * Implements functions for the validation of chess moves.
21 : */
22 :
23 : #include <utility>
24 :
25 : // These functions use the following move classification:
26 : // - a VALID move is a move that respects the basic rules for moving the pieces,
27 : // for example a bishop should move diagonally. Validating this type of moves
28 : // do not require any info about the current position.
29 : // - an ATTACK move is a valid move that can capture an enemy piece at the
30 : // destination square. It takes into account the special rule for pawns that
31 : // can capture only diagonally and the board position for obstacles, for
32 : // example a valid diagonal bishop move is an attack move only if the
33 : // in-between squares are empty. To validate this type of moves it is
34 : // necessary to know the location of empty squares in the current position.
35 : // - a PSEUDO-LEGAL move is an attack move, or a non-capture pawn move, or a
36 : // castle move.
37 : // - a LEGAL move is a pseudo-legal move where the destination square is not
38 : // occupied by a friendly piece and that do not leave the king in check.
39 : // To validate this type of moves it is necessary to know the type and
40 : // position of every piece.
41 :
42 : namespace movegen {
43 :
44 : const int NSQUARES = 8;
45 :
46 1024722 : inline bool valid_king(squareT sqFrom, squareT sqTo) {
47 1024722 : unsigned distRank = 1 + (sqTo / NSQUARES) - (sqFrom / NSQUARES);
48 1024722 : unsigned distFyle = 1 + (sqTo % NSQUARES) - (sqFrom % NSQUARES);
49 1024722 : return distRank <= 2 && distFyle <= 2;
50 : }
51 :
52 621708 : inline bool valid_knight(squareT sqFrom, squareT sqTo) {
53 621708 : int distRank = (sqTo / NSQUARES) - (sqFrom / NSQUARES);
54 621708 : int distFyle = (sqTo % NSQUARES) - (sqFrom % NSQUARES);
55 621708 : int distProduct = distRank * distFyle;
56 621708 : return (distProduct == 2 || distProduct == -2);
57 : }
58 :
59 3328129 : inline int valid_slider(squareT sqFrom, squareT sqTo, pieceT pieceType) {
60 3328129 : ASSERT(pieceType == QUEEN || pieceType == ROOK || pieceType == BISHOP);
61 :
62 3328129 : int distRank = (sqTo / NSQUARES) - (sqFrom / NSQUARES);
63 3328129 : int distFyle = (sqTo % NSQUARES) - (sqFrom % NSQUARES);
64 :
65 : // Make sure the direction is valid:
66 : int sqStep;
67 3328129 : bool isDiagonal = false;
68 3328129 : if (distRank == 0) {
69 391311 : sqStep = 1; // horizontal
70 2936818 : } else if (distFyle == 0) {
71 438464 : sqStep = NSQUARES; // vertical
72 2498354 : } else if (distFyle == distRank) {
73 265016 : sqStep = NSQUARES + 1;
74 265016 : isDiagonal = true;
75 2233338 : } else if (distFyle == -distRank) {
76 267002 : sqStep = NSQUARES - 1;
77 267002 : isDiagonal = true;
78 : } else {
79 1966336 : return 0;
80 : }
81 1361793 : if (pieceType == ROOK && isDiagonal)
82 62204 : return 0;
83 1299589 : if (pieceType == BISHOP && !isDiagonal)
84 110068 : return 0;
85 :
86 1189521 : return sqStep;
87 : }
88 :
89 187086 : inline bool attack_pawn(squareT sqFrom, squareT sqTo, colorT pieceCol) {
90 187086 : int distRank = (sqTo / NSQUARES) - (sqFrom / NSQUARES);
91 187086 : int distFyle = (sqTo % NSQUARES) - (sqFrom % NSQUARES);
92 187086 : if (pieceCol == WHITE && distRank != 1)
93 82960 : return false;
94 104126 : if (pieceCol == BLACK && distRank != -1)
95 85102 : return false;
96 :
97 19024 : return (distFyle == 1 || distFyle == -1);
98 : }
99 :
100 : template <typename TBoard>
101 3328129 : bool attack_slider(squareT sqFrom, squareT sqTo, pieceT pieceType,
102 : const TBoard* board, const TBoard EMPTY_SQUARE) {
103 3328129 : int sqStep = valid_slider(sqFrom, sqTo, pieceType);
104 3328129 : if (sqStep == 0)
105 2138608 : return false;
106 :
107 : // Make sure all the in-between squares are empty:
108 1189521 : if (sqFrom > sqTo)
109 589567 : sqStep = -sqStep;
110 :
111 2605267 : for (int sq = sqFrom + sqStep; sq != sqTo; sq += sqStep) {
112 1676955 : if (board[sq] != EMPTY_SQUARE)
113 261209 : return false;
114 : }
115 :
116 928312 : return true;
117 : }
118 :
119 : /**
120 : * Validate an ATTACK move, that is if a piece placed at @e sqFrom can capture
121 : * an enemy piece at @e sqTo.
122 : * @param sqFrom: square of the piece.
123 : * @param sqTo: square of the piece to be captured.
124 : * @param pieceCol: color of the moving piece.
125 : * @param pieceType: type of the moving piece.
126 : * @param board: pointer to the board position; it's is irrelevant if the
127 : * position is the one before or after the move was made.
128 : * @param EMPTY_SQUARE: value of an empty square in the board position.
129 : * @returns true if the move is a valid ATTACK move.
130 : */
131 : template <typename TBoard>
132 1052712 : bool attack(squareT sqFrom, squareT sqTo, pieceT pieceCol, pieceT pieceType,
133 : const TBoard* board, const TBoard EMPTY_SQUARE) {
134 1052712 : switch (pieceType) {
135 2 : case KING:
136 2 : return valid_king(sqFrom, sqTo);
137 204585 : case KNIGHT:
138 204585 : return valid_knight(sqFrom, sqTo);
139 187086 : case PAWN:
140 187086 : return attack_pawn(sqFrom, sqTo, pieceCol);
141 661039 : default:
142 661039 : break;
143 : }
144 661039 : return attack_slider(sqFrom, sqTo, pieceType, board, EMPTY_SQUARE);
145 : }
146 :
147 : template <typename TBoard>
148 1596632 : bool pseudo(squareT sqFrom, squareT sqTo, colorT /*pieceCol*/, pieceT pieceType,
149 : const TBoard* board, const TBoard EMPTY_SQUARE) {
150 : // TODO: pawn and king moves
151 1596632 : ASSERT(pieceType != PAWN && pieceType != KING);
152 :
153 1596632 : switch (pieceType) {
154 417123 : case KNIGHT:
155 417123 : return valid_knight(sqFrom, sqTo);
156 1179509 : default:
157 1179509 : break;
158 : }
159 1179509 : return attack_slider(sqFrom, sqTo, pieceType, board, EMPTY_SQUARE);
160 : }
161 :
162 : /**
163 : * Given a pseudo-legal move, this functions return the type and the location of
164 : * the piece that can possibly pin the moving piece, making the move not legal.
165 : * @param sqFrom: start square of the pseudo-legal move.
166 : * @param sqTo: destination square of the pseudo-legal move.
167 : * @param sqRay: the projected ray starts from @e sqRay and goes through
168 : * @e sqFrom; it is usually the square where the king is.
169 : * @param board: pointer to the board position where the pseudo-legal
170 : * move has to be made.
171 : * @param EMPTY_SQUARE: value of an empty square in the board position.
172 : * @returns a std::pair with the type (INVALID_PIECE, BISHOP, ROOK) and the
173 : * square of the candidate pinning piece. If the type is INVALID_PIECE there is
174 : * no pin and the move is legal, otherwise it's necessary to test the board
175 : * position and if the returned square is occupied by an enemy QUEEN, or an
176 : * enemy piece matching the returned type, the move is not legal.
177 : */
178 : template <typename TBoard>
179 876725 : inline std::pair<pieceT, squareT> opens_ray(squareT sqFrom, squareT sqTo,
180 : squareT sqRay, const TBoard* board,
181 : const TBoard EMPTY_SQUARE) {
182 876725 : ASSERT(sqRay != sqFrom);
183 :
184 876725 : int fyleFrom = sqFrom % NSQUARES;
185 876725 : int distFyle = (sqRay % NSQUARES) - fyleFrom;
186 876725 : int distRank = (sqRay / NSQUARES) - (sqFrom / NSQUARES);
187 :
188 : // Make sure the direction is valid:
189 : int fyleEdge;
190 : int sqStep;
191 : pieceT pt;
192 876725 : if (distFyle == 0) {
193 87515 : sqStep = NSQUARES; // vertical
194 87515 : fyleEdge = -1;
195 87515 : pt = ROOK;
196 : } else {
197 789210 : if (fyleFrom == 0 || fyleFrom == (NSQUARES - 1))
198 180789 : return std::pair<pieceT, squareT>(INVALID_PIECE, 0);
199 :
200 608421 : if (distRank == 0) {
201 129680 : sqStep = 1; // horizontal
202 129680 : fyleEdge = 0;
203 129680 : pt = ROOK;
204 478741 : } else if (distFyle == distRank) {
205 51624 : sqStep = NSQUARES + 1;
206 51624 : fyleEdge = 0;
207 51624 : pt = BISHOP;
208 427117 : } else if (distFyle == -distRank) {
209 52264 : sqStep = NSQUARES - 1;
210 52264 : fyleEdge = NSQUARES - 1;
211 52264 : pt = BISHOP;
212 : } else {
213 374853 : return std::pair<pieceT, squareT>(INVALID_PIECE, 0);
214 : }
215 : }
216 321083 : if (sqFrom > sqRay) {
217 147970 : sqStep = -sqStep;
218 147970 : fyleEdge = NSQUARES - 1 - fyleEdge;
219 : }
220 :
221 573277 : for (int sq = sqFrom + sqStep; sq != sqRay; sq += sqStep) {
222 339390 : if (sq == sqTo || board[sq] != EMPTY_SQUARE)
223 87196 : return std::pair<pieceT, squareT>(INVALID_PIECE, 0);
224 : }
225 :
226 470258 : for (int sq = sqFrom - sqStep; sq < NSQUARES * NSQUARES; sq -= sqStep) {
227 439424 : if (sq < 0 || sq == sqTo)
228 : break;
229 :
230 385335 : if (board[sq] != EMPTY_SQUARE)
231 88385 : return std::make_pair(pt, static_cast<squareT>(sq));
232 :
233 296950 : if ((sq % NSQUARES) == fyleEdge)
234 60579 : break;
235 : }
236 145502 : return std::pair<pieceT, squareT>(INVALID_PIECE, 0);
237 : }
238 :
239 :
240 : } // end of namespace movegen
|