LCOV - code coverage report
Current view: top level - src - movegen.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 104 104 100.0 %
Date: 2018-02-05 16:49:44 Functions: 11 11 100.0 %

          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

Generated by: LCOV version 1.13