1 /***************************************************************************
2 * (C) 2005 William Hoggarth <whoggarth@users.sourceforge.net> *
3 * (C) 2005-2009 Michal Rudolf <mrudolf@kdewebdev.org> *
4 * *
5 * This program is free software; you can redistribute it and/or modify *
6 * it under the terms of the GNU General Public License as published by *
7 * the Free Software Foundation; either version 2 of the License, or *
8 * (at your option) any later version. *
9 ***************************************************************************/
10
11 #ifndef MOVE_H_INCLUDED
12 #define MOVE_H_INCLUDED
13
14 #include "piece.h"
15 #include "square.h"
16
17 #include <QString>
18 #include <QVector>
19
20 class BitBoard;
21
22 /** @ingroup Core
23 Moves are dependent on current position, (remembers piece, check, capture etc)
24 and don't make much sense when considered without a Board.
25 However, you can create a move with only a source and destination square,
26 Such moves are considered "illegal", but can be convenient when dealing with move entry.
27 */
28
29
isFile(const char c)30 inline bool isFile(const char c)
31 {
32 return c >= 'a' && c <= 'h';
33 }
34
isRank(const char c)35 inline bool isRank(const char c)
36 {
37 return c >= '1' && c <= '8';
38 }
39
40 class Move
41 {
42 public:
43 using List = QVector<Move>;
44
45 /** Default constructor, creates an empty (illegal) move */
46 Move();
47
Move(const Move & move)48 Move(const Move& move)
49 {
50 m = move.m;
51 u = move.u;
52 }
53
54 /** Move entry constructor, untested (illegal) move with only from, and to squares set */
55 Move(const chessx::Square from, const chessx::Square to);
56
57 /** Construct a untested (illegal) Move from a SAN like string */
58 inline Move fromUCI(const QByteArray& bs);
59
60 /** Set type of piece (Queen, Rook, Bishop, Knight, Pawn) pawn promoted to */
61 void setPromoted(PieceType p);
62
63 // Query
64 /** return Square piece sits on after move */
65 chessx::Square to() const;
66 /** return Square piece sat on before move */
67 chessx::Square from() const;
68 /** return Square where rook is placed after castling */
69 chessx::Square castlingRookTo() const;
70 /** return Square when en-passant is captured. Undefined if there is no en-passant. */
71 chessx::Square enPassantSquare() const;
72 /** return Square where rook was placed before castling */
73 chessx::Square castlingRookFrom() const;
74 /** Convert to algebraic notation (e2e4, g8f6 etc.) */
75 QString fromSquareString() const;
76 QString toSquareString() const;
77 QString toAlgebraic() const;
78 QString dumpAlgebraic() const;
79 QString toAlgebraicDebug() const;
80
81 /** Get the piece type moving -- note, returns Pawn, QUEEN, etc.. not colorized */
82 Piece pieceMoved() const;
83 /** Piece captured from the opponent by this move */
84 Piece capturedPiece() const;
85 /** If move is promotion, get promotion piece. Result is undefined if there is no promotion */
86 Piece promotedPiece() const;
87
88 /** Check whether a given move is a null move ( an illegal move by the king to its own square ) often used as a placeholder in ebooks */
89 bool isNullMove() const;
90 Move& setNullMove();
91
92 /** Check whether move is special (promotion, castling, en passant */
93 bool isSpecial() const;
94 /** Check whether move is a promotion */
95 bool isPromotion() const;
96 /** Check whether move is a castling */
97 bool isCastling() const;
98 /** Determine if this castling is short (to the kingside) */
99 bool isCastlingShort() const;
100 /** Check whether the move is a pawn double advance */
101 bool isDoubleAdvance() const;
102 /** Check whether move is an en passant */
103 bool isEnPassant() const;
104 /** Check if move is completely legal in the context it was created */
105 bool isLegal() const;
106
107 Color color() const;
108
109 /** Return true if this move was made by given color */
110 bool operator==(const Color& color) const;
111 /** Return true if this move was NOT made by given color */
112 bool operator!=(const Color& color) const;
113 /** Return true if this move was made by given piece */
114 bool operator==(const Piece& p) const;
115 /** Return true if this move was NOT made by given piece */
116 bool operator!=(const Piece& p) const;
117
118 Move& operator=(const Move& move)
119 {
120 if (this != &move)
121 {
122 m = move.m;
123 u = move.u;
124 }
125 return *this;
126 }
127
128 /** Moves are considered the same, only if they match exactly */
129 friend bool operator==(const Move& m1, const Move& m2);
130 friend bool operator!=(const Move& m1, const Move& m2);
131 /** Required for keeping moves in some map-like structures */
132 friend bool operator<(const Move& m1, const Move& m2);
133
rawMove()134 unsigned int rawMove() const { return m; }
rawUndo()135 unsigned short rawUndo() const { return u; }
136
137 friend class BitBoard;
138 private:
139 static const quint64 CASTLE = 9;
140 static const quint64 TWOFORWARD = 22;
141 static const quint64 PROMOTE = 38;
142 static const quint64 ENPASSANT = 14;
143
144 static const quint64 CASTLINGBIT = 1uL << 15;
145 static const quint64 TWOFORWARDBIT = 1uL << 16;
146 static const quint64 PROMOTEBIT = 1uL << 17;
147 static const quint64 ENPASSANTBIT = 1uL << 21;
148 static const quint64 LEGALITYBIT = 1uL << 31;
149 static const quint64 SPECIALBITS = CASTLINGBIT | TWOFORWARDBIT | PROMOTEBIT | ENPASSANTBIT;
150 static const quint64 PTCLEAR = ~(7uL << 12);
151 static const quint64 CAPCLEAR = ~(7uL << 18);
152 static const quint64 PROCLEAR = ~((7uL << 22) | PROMOTEBIT);
153 static const quint64 BLACKTM = 1uL << 26;
154
155 /** Set Pawn move of one forward */
156 void genOneForward(unsigned int from, unsigned int to);
157 /** Set two-squares forward move of Pawn */
158 void genTwoForward(unsigned int from, unsigned int to);
159 /** Set pawn promotion move to given Piecetype */
160 void genPromote(unsigned int from, unsigned int to, unsigned int type);
161 /** Set pawn capture and promotion, promote to piece type, capturing type */
162 void genCapturePromote(unsigned int from, unsigned int to, unsigned int type, unsigned int captured);
163 /** Set pawn en passant capture of opponent pawn */
164 void genEnPassant(unsigned int from, unsigned int to);
165 /** Set simple pawn move with capture of piece type */
166 void genPawnMove(unsigned int from, unsigned int to, unsigned int captured);
167 /** Set knight move, capturing piece type */
168 void genKnightMove(unsigned int from, unsigned int to, unsigned int captured);
169 /** Set bishop move, capturing piece type */
170 void genBishopMove(unsigned int from, unsigned int to, unsigned int captured);
171 /** Set rook move, capturing piece type */
172 void genRookMove(unsigned int from, unsigned int to, unsigned int captured);
173 /** Set queen move, capturing piece type */
174 void genQueenMove(unsigned int from, unsigned int to, unsigned int captured);
175 /** Set king move, capturing piece type */
176 void genKingMove(unsigned int from, unsigned int to, unsigned int captured);
177 /** Set castling short move for White with king and rook */
178 void genWhiteOO();
179 /** Set castling long move for White with king and rook */
180 void genWhiteOOO();
181 /** Set castling short move for Black with king and rook */
182 void genBlackOO();
183 /** Set castling long move for Black with king and rook */
184 void genBlackOOO();
185 /** Mark this move as validated and fully legal in position */
186 void setLegalMove();
187 /** Set source square for this move */
188 void setFrom(chessx::Square from);
189 /** Set destination square for this move */
190 void setTo(chessx::Square to);
191 /** Mark this move as being made by the Black side */
192 void setBlack();
193 /** Return piece type of promoted piece (or 0 if none) */
194 unsigned int promoted() const;
195 /** Set type of piece (Queen, Rook, Bishop, Knight, Pawn) making move */
196 void setPieceType(unsigned char p);
197 /** Set type of piece (Queen, Rook, Bishop, Knight, Pawn) captured */
198 void setCaptureType(unsigned char p);
199 /** Mark this move as an initial pawn move of 2 squares */
200 void setTwoForward();
201 /** Mark this move capturing a pawn en passant */
202 void setEnPassant();
203 /** Mark this move as giving check */
204 void setCheck();
205 /** Mark this move as giving checkmate */
206 void setMate();
207 /** Add castling bit in addition to other flags */
208 void SetCastlingBit();
209
210
211 /** Return pawn2forward, castle or piece type for doMove() and undoMove() */
212 unsigned int action() const;
213 /** Return captured piece or En passant for doMove() and undoMove() */
214 unsigned int removal() const;
215 /** Return piece type of captured piece (or 0 if none) */
216 unsigned int capturedType() const;
217
218 // The move definition 'm' bitfield layout:
219 // 00000000 00000000 00000000 00111111 = from square = bits 1-6
220 // 00000000 00000000 00001111 11000000 = to square = bits 7-12
221 // 00000000 00000000 01110000 00000000 = piece type = bits 13-15
222 // 00000000 00000000 10000000 00000000 = castle = bit 16
223 // 00000000 00000001 00000000 00000000 = pawn 2 forward = bit 17
224 // 00000000 00000010 00000000 00000000 = promotion = bit 18
225 // 00000000 00011100 00000000 00000000 = capture piece = bits 19-21
226 // 00000000 00100000 00000000 00000000 = en passant = bit 22
227 // 00000001 11000000 00000000 00000000 = promotion piece = bits 23-25
228 // 00000010 00000000 00000000 00000000 = Extra data set = bits 26 // NOT YET IMPLEMENTED
229 // 00000100 00000000 00000000 00000000 = White=0,Black=1 = bit 27
230 // 00001000 00000000 00000000 00000000 = SAN needs file = bit 28 // NOT YET IMPLEMENTED
231 // 00010000 00000000 00000000 00000000 = SAN needs rank = bit 29 // NOT YET IMPLEMENTED
232 // 00100000 00000000 00000000 00000000 = gives mate? = bit 30 // NOT YET IMPLEMENTED
233 // 01000000 00000000 00000000 00000000 = gives check? = bit 31 // NOT YET IMPLEMENTED
234 // 10000000 00000000 00000000 00000000 = legality status = bit 32
235 unsigned int m;
236 // The undo definition 'u' bitfield layout:
237 // 00000000 11111111 = half move clock = bits 1-8
238 // 00001111 00000000 = castling rights = bits 8-12
239 // 11110000 00000000 = previous ep file = bits 13-16
240 unsigned short u;
241 };
242
243 // return true if a null move
244 // null move is coded as a2a2 which is better than a king move
isNullMove()245 inline bool Move::isNullMove() const
246 {
247 // Must be consistent with Guess::movelist::isNullMove
248 return (to() == chessx::a2 && from() == chessx::a2);
249 }
250
setNullMove()251 inline Move& Move::setNullMove()
252 {
253 m = chessx::a2 | (chessx::a2 << 6);
254 u = 0;
255 return *this;
256 }
257
from()258 inline chessx::Square Move::from() const
259 {
260 return chessx::Square(m & 63);
261 }
262
to()263 inline chessx::Square Move::to() const
264 {
265 return chessx::Square((m >> 6) & 63);
266 }
267
Move()268 inline Move::Move()
269 : m(0), u(0)
270 {}
271
Move(const chessx::Square from,const chessx::Square to)272 inline Move::Move(const chessx::Square from, const chessx::Square to)
273 : m(from | (to << 6)), u(0)
274 {}
275
fromUCI(const QByteArray & bs)276 inline Move Move::fromUCI(const QByteArray& bs)
277 {
278 const char *san = bs.constData();
279 const char* s = san;
280 char c = *(s++);
281
282 if(isFile(c))
283 {
284 // Check From
285 int fromFile = c - 'a';
286 c = *(s++);
287 if(isRank(c))
288 {
289 chessx::Square fromSquare = chessx::Square((c - '1') * 8 + fromFile);
290 fromFile = -1;
291 c = *(s++);
292 // Destination square
293 if(isFile(c))
294 {
295 int f = c - 'a';
296 c = *(s++);
297 if(isRank(c))
298 {
299 chessx::Square toSquare = chessx::Square((c - '1') * 8 + f);
300 Move m(fromSquare, toSquare);
301 c = *(s++);
302 if(c == '=' || c == '(' || QString("QRBN").indexOf(toupper(c))>=0)
303 {
304 if(c == '=' || c == '(')
305 {
306 c = *(s++);
307 }
308 PieceType promotePiece;
309 switch(toupper(c))
310 {
311 case 'Q':
312 promotePiece = Queen;
313 break;
314 case 'R':
315 promotePiece = Rook;
316 break;
317 case 'B':
318 promotePiece = Bishop;
319 break;
320 case 'N':
321 promotePiece = Knight;
322 break;
323 default:
324 promotePiece = None;
325 break;
326 }
327 m.setPromoted(promotePiece);
328 }
329 return m;
330 }
331 }
332 }
333 }
334
335 return Move();
336 }
337
castlingRookFrom()338 inline chessx::Square Move::castlingRookFrom() const
339 {
340 return chessx::Square((to() % 8 == 2) ? to() - 2 : to() + 1);
341 }
342
castlingRookTo()343 inline chessx::Square Move::castlingRookTo() const
344 {
345 return chessx::Square((from() + to()) / 2);
346 }
347
fromSquareString()348 inline QString Move::fromSquareString() const
349 {
350 QString alg;
351 alg += QChar('a' + from() % 8);
352 alg += QChar('1' + from() / 8);
353 return alg;
354 }
355
toSquareString()356 inline QString Move::toSquareString() const
357 {
358 QString alg;
359 alg += QChar('a' + to() % 8);
360 alg += QChar('1' + to() / 8);
361 return alg;
362 }
363
dumpAlgebraic()364 inline QString Move::dumpAlgebraic() const
365 {
366 QString alg;
367 alg += QChar('a' + from() % 8);
368 alg += QChar('1' + from() / 8);
369 alg += QChar('a' + to() % 8);
370 alg += QChar('1' + to() / 8);
371 if (isPromotion())
372 {
373 alg += QChar('=');
374 alg += "XKQRBNPKQRBNP"[promotedPiece()];
375 }
376 return alg;
377 }
378
toAlgebraic()379 inline QString Move::toAlgebraic() const
380 {
381 if (isNullMove())
382 {
383 return QString("--");
384 }
385 if(!isLegal())
386 {
387 return QString("?");
388 }
389 return dumpAlgebraic();
390 }
391
toAlgebraicDebug()392 inline QString Move::toAlgebraicDebug() const
393 {
394 QString alg;
395 if(!isLegal())
396 {
397 alg = "?";
398 }
399 alg += dumpAlgebraic();
400 return alg;
401 }
402
enPassantSquare()403 inline chessx::Square Move::enPassantSquare() const
404 {
405 return chessx::Square(from() > 31 ? to() - 8 : to() + 8);
406 }
407
pieceMoved()408 inline Piece Move::pieceMoved() const
409 {
410 return Piece((7 & (m >> 12)) + (m & BLACKTM ? 6 : 0));
411 }
412
capturedPiece()413 inline Piece Move::capturedPiece() const
414 {
415 unsigned char p = (m >> 18) & 7;
416 if(p == 0)
417 {
418 return Piece(0);
419 }
420 return Piece(p + (m & BLACKTM ? 0 : 6));
421 }
422
promotedPiece()423 inline Piece Move::promotedPiece() const
424 {
425 return Piece((7 & (m >> 22)) + (m & BLACKTM ? 6 : 0));
426 }
427
isSpecial()428 inline bool Move::isSpecial() const
429 {
430 return m & SPECIALBITS;
431 }
432
isPromotion()433 inline bool Move::isPromotion() const
434 {
435 return m & PROMOTEBIT;
436 }
437
isCastling()438 inline bool Move::isCastling() const
439 {
440 return m & CASTLINGBIT;
441 }
442
443 #define CW_00 (4 | (6 << 6) | (King << 12) | CASTLINGBIT)
444 #define CB_00 (60 | (62 << 6) | (King << 12) | CASTLINGBIT)
445
isCastlingShort()446 inline bool Move::isCastlingShort() const
447 {
448 return (((m & CW_00) == CW_00) || ((m & CB_00) == CB_00));
449 }
450
isDoubleAdvance()451 inline bool Move::isDoubleAdvance() const
452 {
453 return m & TWOFORWARDBIT;
454 }
455
isEnPassant()456 inline bool Move::isEnPassant() const
457 {
458 return m & ENPASSANTBIT;
459 }
460
isLegal()461 inline bool Move::isLegal() const
462 {
463 return m & LEGALITYBIT;
464 }
465
color()466 inline Color Move::color() const
467 {
468 return ((m & BLACKTM) ? Black : White);
469 }
470
genOneForward(unsigned int from,unsigned int to)471 inline void Move::genOneForward(unsigned int from, unsigned int to)
472 {
473 m = from | (to << 6) | (Pawn << 12);
474 }
475
genTwoForward(unsigned int from,unsigned int to)476 inline void Move::genTwoForward(unsigned int from, unsigned int to)
477 {
478 m = from | (to << 6) | (Pawn << 12) | (1 << 16);
479 }
480
genPromote(unsigned int from,unsigned int to,unsigned int type)481 inline void Move::genPromote(unsigned int from, unsigned int to, unsigned int type)
482 {
483 m = from | (to << 6) | (Pawn << 12) | (type << 22) | (1 << 17);
484 }
485
genCapturePromote(unsigned int from,unsigned int to,unsigned int type,unsigned int captured)486 inline void Move::genCapturePromote(unsigned int from, unsigned int to, unsigned int type, unsigned int captured)
487 {
488 m = from | (to << 6) | (Pawn << 12) | (captured << 18) | (type << 22) | (1 << 17);
489 }
490
genEnPassant(unsigned int from,unsigned int to)491 inline void Move::genEnPassant(unsigned int from, unsigned int to)
492 {
493 m = from | (to << 6) | (Pawn << 12) | (Pawn << 18) | (1 << 21);
494 }
495
genPawnMove(unsigned int from,unsigned int to,unsigned int captured)496 inline void Move::genPawnMove(unsigned int from, unsigned int to, unsigned int captured)
497 {
498 m = from | (to << 6) | (Pawn << 12) | (captured << 18);
499 }
500
genKnightMove(unsigned int from,unsigned int to,unsigned int captured)501 inline void Move::genKnightMove(unsigned int from, unsigned int to, unsigned int captured)
502 {
503 m = from | (to << 6) | (Knight << 12) | (captured << 18);
504 }
505
genBishopMove(unsigned int from,unsigned int to,unsigned int captured)506 inline void Move::genBishopMove(unsigned int from, unsigned int to, unsigned int captured)
507 {
508 m = from | (to << 6) | (Bishop << 12) | (captured << 18);
509 }
510
genRookMove(unsigned int from,unsigned int to,unsigned int captured)511 inline void Move::genRookMove(unsigned int from, unsigned int to, unsigned int captured)
512 {
513 m = from | (to << 6) | (Rook << 12) | (captured << 18);
514 }
515
genQueenMove(unsigned int from,unsigned int to,unsigned int captured)516 inline void Move::genQueenMove(unsigned int from, unsigned int to, unsigned int captured)
517 {
518 m = from | (to << 6) | (Queen << 12) | (captured << 18);
519 }
520
genKingMove(unsigned int from,unsigned int to,unsigned int captured)521 inline void Move::genKingMove(unsigned int from, unsigned int to, unsigned int captured)
522 {
523 m = from | (to << 6) | (King << 12) | (captured << 18);
524 }
525
genWhiteOO()526 inline void Move::genWhiteOO()
527 {
528 m = 4 | (6 << 6) | (King << 12) | CASTLINGBIT;
529 }
530
genWhiteOOO()531 inline void Move::genWhiteOOO()
532 {
533 m = 4 | (2 << 6) | (King << 12) | CASTLINGBIT;
534 }
535
genBlackOO()536 inline void Move::genBlackOO()
537 {
538 m = 60 | (62 << 6) | (King << 12) | CASTLINGBIT;
539 }
540
genBlackOOO()541 inline void Move::genBlackOOO()
542 {
543 m = 60 | (58 << 6) | (King << 12) | CASTLINGBIT;
544 }
545
SetCastlingBit()546 inline void Move::SetCastlingBit()
547 {
548 m |= CASTLINGBIT;
549 }
550
setLegalMove()551 inline void Move::setLegalMove()
552 {
553 m |= LEGALITYBIT;
554 }
555
setFrom(chessx::Square from)556 inline void Move::setFrom(chessx::Square from)
557 {
558 m = (m & (~63)) | from;
559 m &= ~LEGALITYBIT;
560 }
561
setTo(chessx::Square to)562 inline void Move::setTo(chessx::Square to)
563 {
564 m = (m & (~(63 << 6))) | (to << 6);
565 m &= ~LEGALITYBIT;
566 }
567
action()568 inline unsigned int Move::action() const
569 {
570 return (m >> 12) & 63;
571 }
572
removal()573 inline unsigned int Move::removal() const
574 {
575 return (m >> 18) & 15;
576 }
577
setBlack()578 inline void Move::setBlack()
579 {
580 m |= BLACKTM;
581 }
582
promoted()583 inline unsigned int Move::promoted() const
584 {
585 return 7 & (m >> 22);
586 }
587
capturedType()588 inline unsigned int Move::capturedType() const
589 {
590 return (m >> 18) & 7;
591 }
592
setPieceType(unsigned char p)593 inline void Move::setPieceType(unsigned char p)
594 {
595 m &= PTCLEAR ;
596 m |= (7 & p) << 12;
597 }
598
setCaptureType(unsigned char p)599 inline void Move::setCaptureType(unsigned char p)
600 {
601 m &= CAPCLEAR ;
602 m |= (7 & p) << 18;
603 }
604
setTwoForward()605 inline void Move::setTwoForward()
606 {
607 m |= TWOFORWARDBIT;
608 }
609
setEnPassant()610 inline void Move::setEnPassant()
611 {
612 m |= ENPASSANTBIT;
613 setCaptureType(Pawn);
614 }
615
setPromoted(PieceType p)616 inline void Move::setPromoted(PieceType p)
617 {
618 m &= PROCLEAR ;
619 m |= PROMOTEBIT | ((7 & p) << 22);
620 }
621
setCheck()622 inline void Move::setCheck()
623 {
624 m |= (1 << 30);
625 }
626
setMate()627 inline void Move::setMate()
628 {
629 m |= (1 << 29);
630 }
631
632 inline bool operator==(const Move& m1, const Move& m2)
633 {
634 return m1.m == m2.m;
635 }
636
637 inline bool operator!=(const Move& m1, const Move& m2)
638 {
639 return !(m1==m2);
640 }
641
642 inline bool operator<(const Move& m1, const Move& m2)
643 {
644 return m1.m < m2.m;
645 }
646
647 inline bool Move::operator==(const Color& color) const
648 {
649 return color == ((m & BLACKTM) ? Black : White);
650 }
651
652 inline bool Move::operator!=(const Color& color) const
653 {
654 return !(*this == color);
655 }
656
657 inline bool Move::operator==(const Piece& p) const
658 {
659 return (unsigned int) p == (((m & BLACKTM) && ((m >> 12) & 7)) ? ((m >> 12) & 7) + 6 : ((m >> 12) & 7));
660 }
661
662 inline bool Move::operator!=(const Piece& p) const
663 {
664 return !(*this == p);
665 }
666
667 #endif // MOVE_H_INCLUDED
668