src/chess/rules.h

/*
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
 *
 * Copyright 2016 Mike Becker. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   1. Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *
 *   2. Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 *
 */

#ifndef RULES_H
#define	RULES_H

#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>

#define VALID_MOVE_SYNTAX      0
#define VALID_MOVE_SEMANTICS   0 /* use same code for a success */
#define INVALID_MOVE_SYNTAX    1
#define PIECE_NOT_FOUND        2
#define AMBIGUOUS_MOVE         3
#define NEED_PROMOTION         4
#define PIECE_PINNED           5
#define KING_IN_CHECK          6
#define KING_MOVES_INTO_CHECK  7
#define MISSING_CHECK          8
#define MISSING_CHECKMATE      9
#define INVALID_CHECK         10
#define INVALID_CHECKMATE     11
#define RULES_VIOLATED        32

#define ENPASSANT_THREAT 0x40u

#define WHITE 0x10u
#define BLACK 0x20u
#define opponent_color(color) ((color)==WHITE?BLACK:WHITE)

#define PIECE_MASK 0x0Fu
#define COLOR_MASK 0x30u

#define PAWN   0x01u
#define ROOK   0x02u
#define KNIGHT 0x03u
#define BISHOP 0x04u
#define QUEEN  0x05u
#define KING   0x06u

#define WPAWN   (WHITE|PAWN)
#define WROOK   (WHITE|ROOK)
#define WKNIGHT (WHITE|KNIGHT)
#define WBISHOP (WHITE|BISHOP)
#define WQUEEN  (WHITE|QUEEN)
#define WKING   (WHITE|KING)
#define BPAWN   (BLACK|PAWN)
#define BROOK   (BLACK|ROOK)
#define BKNIGHT (BLACK|KNIGHT)
#define BBISHOP (BLACK|BISHOP)
#define BQUEEN  (BLACK|QUEEN)
#define BKING   (BLACK|KING)

typedef uint8_t Board[8][8];
typedef uint8_t BoardIndex;
typedef BoardIndex Row;
typedef BoardIndex File;
typedef uint8_t Piece;
typedef uint8_t Color;

struct movetimeval {
    uint64_t tv_sec;
    int32_t tv_usec; /* important that this is signed b/c potential carry */
};

typedef struct {
    Piece piece;
    File fromfile;
    Row fromrow;
    File tofile;
    Row torow;
    Piece promotion;
    uint8_t check; /* must always be set if checkmate is set */
    uint8_t checkmate;
    uint8_t capture;
    uint8_t padding[7]; /* necessary for stable ABI across networks */
    struct movetimeval timestamp;
    struct movetimeval movetime;
    char string[8];
} Move;

typedef struct {
    uint8_t servercolor;
    /** 1: play with timecontrol, 0: play without time control */
    uint8_t timecontrol;
    /** If timecontrol is 1, initial clock time in seconds */
    uint16_t time;
    /** If timecontrol is 1, time added per move in seconds */
    uint16_t addtime;
    /** If timecontrol is 1, delay before the clock starts ticking down */
    uint16_t delay;
} GameInfo;

/** The buffer length for player names in GameState structures. */
#define PLAYER_NAME_BUFLEN 32

typedef struct {
    /** optional name of the white player - only used for PGN exports */
    char wname[PLAYER_NAME_BUFLEN];
    /** optional name of the black player - only used for PGN exports */
    char bname[PLAYER_NAME_BUFLEN];
    GameInfo info;
    Board board;
    Move* moves;
    /** starting position in FEN notation */
    char *fen_start;
    /** array of subsequent positions in FEN notation.
     * The capacity and element count are identical to the moves array.
     */
    char **fen;
    /** capacity of the move array */
    unsigned int movecapacity;
    /** number of (half-)moves (counting BOTH colors) */
    unsigned int movecount;
    /** a premove that shall be evaluated next time it's our turn */
    char premove[8];
    bool checkmate;
    bool stalemate;
    bool threefold;
    /** drawn due to insufficient material on both sides */
    bool nomaterial;
    /** flag is only set when players agreed on remis */
    bool remis;
    bool wresign;
    bool bresign;
    /** this flag is only supposed to be set when the opponent disconnects */
    bool ragequit;
    bool review;
} GameState;

#define piece_type(piece) ((piece)&PIECE_MASK)
#define piece_color(piece) ((piece)&COLOR_MASK)
#define mkpiece(type,color) ((type)|(color))

#define POS_UNSPECIFIED UINT8_MAX
#define mdst(m) (m)->torow, (m)->tofile
#define msrc(m) (m)->fromrow, (m)->fromfile

/** Checks if the index is specified and valid. */
#define isidx(idx) ((BoardIndex)(idx) < 8)
/** Checks if the index is unspecified or valid. */
#define isidxr(idx) ((idx) == POS_UNSPECIFIED || (BoardIndex)(idx) < 8)

#define isfile(file) (file >= 'a' && file <= 'h')
#define isrow(row) (row >= '1' && row <= '8')

#define rowidx(row) (row-'1')
#define fileidx(file) (file-'a')

#define rowchr(row) (row+'1')
#define filechr(file) (file+'a')

/* secure versions - use, if index is not checked with isidx() */
#define fileidx_s(c) (isfile(c)?fileidx(c):POS_UNSPECIFIED)
#define rowidx_s(c) (isrow(c)?rowidx(c):POS_UNSPECIFIED)


static inline void enpassant_threat_add(GameState *gamestate,
        Row row, File file) {
    gamestate->board[row][file] |= ENPASSANT_THREAT;
}

static inline void enpassant_threat_remove(GameState *gamestate,
        Row row, File file) {
    gamestate->board[row][file] &= ~ENPASSANT_THREAT;
}

static inline bool enpassant_threat_exists(const GameState *gamestate,
        Row row, File file) {
    return gamestate->board[row][file] & ENPASSANT_THREAT;
}

static inline bool is_game_drawn(const GameState *gamestate) {
    return gamestate->threefold || gamestate->stalemate
        || gamestate->nomaterial || gamestate->remis;
}

static inline bool is_game_running(const GameState *gamestate) {
    return !(gamestate->checkmate || gamestate->wresign || gamestate->bresign
        || is_game_drawn(gamestate) || gamestate->review);
}

static inline bool is_check_position(const GameState *gamestate) {
    return gamestate->moves[gamestate->movecount - 1].check;
}

static inline Color field_color(Row r, File f) {
    return (r + f) % 2 == 0 ? BLACK : WHITE;
}

/**
 * Initializes a game state and prepares the chess board.
 * @param gamestate the game state to initialize
 */
void gamestate_init(GameState *gamestate);

/**
 * Cleans up a game state and frees the memory for the movement list.
 * @param gamestate the game state to clean up
 */
void gamestate_cleanup(GameState *gamestate);

/**
 * Maps a character to a piece.
 * 
 * Does not work for pawns, since they don't have a character.
 *
 * @param c one of R,N,B,Q,K
 * @param color the piece color
 * @return the specified piece or zero when the character is invalid
 */
Piece getpiece(char c, Color color);

/**
 * Maps a piece to a character.
 * 
 * Does not work for pawns, since they don't have a character.
 * 
 * @param piece may have color or additional flags
 * @return character value for the specified piece
 */
char getpiecechr(Piece piece);

/**
 * Maps a piece to a unicode character sequence.
 * 
 * The returned unicode is for black pieces.
 * You may colorize the output by setting the terminal foreground color.
 * 
 * @param piece the piece to display
 * @return unicode character sequence for the specified piece
 */
char* getpieceunicode(Piece piece);

/**
 * Returns the color of the player who is next to move.
 *
 * @param gamestate the current game state
 * @return the color of the player who is next to move
 */
Color current_color(const GameState *gamestate);

/**
 * Returns the piece at the specified position.
 *
 * @param gamestate the current game state
 * @param row the row
 * @param file the file
 * @return the piece at the specified position
 */
Piece piece_at(const GameState *gamestate, Row row, File file);

/**
 * Places a piece at the specified position in the current game state.
 *
 * @param gamestate the current game state
 * @param row the row
 * @param file the file
 * @param piece the piece to place at the specified position
 */
void piece_set(GameState *gamestate, Row row, File file, Piece piece);

/**
 * Removes the piece at the specified position in the current game state.
 *
 * @param gamestate the current game state
 * @param row the row
 * @param file the file
 */
static inline void piece_remove(GameState *gamestate, Row row, File file) {
    piece_set(gamestate, row, file, 0);
}

typedef size_t(*moves_generator_func)(const GameState *gamestate,
        Color c, Row r, File f, Move *moves);

/**
 * Calculates all allowed moves for a specific piece.
 *
 * Use the macros for the specific pieces instead.
 *
 * @param gamestate the current gamestate
 * @param r the row of the piece
 * @param f the file of the piece
 * @param moves target array for the list of moves
 * @return the number of moves stored in the @p moves array
 */
size_t piece_moves_allowed(const GameState *gamestate,
        Row r, File f, Move *moves);

/**
 * Internal function used to filter out illegal moves.
 *
 * Use the macros for the specific pieces instead.
 *
 * @param gamestate the current gamestate
 * @param c color of the piece
 * @param r the row of the piece
 * @param f the file of the piece
 * @param moves target array for the list of moves
 * @param func a function that unconditionally generates the moves
 * @return the number of moves stored in the @p moves array
 */
size_t filter_moves_allowed(const GameState *gamestate,
    Color c, Row r, File f, Move *moves, moves_generator_func func);

/**
 * Determines a list of theoretically possible moves to the specified field.
 *
 * This will also list moves for pieces that are actually pinned.
 * Use get_real_candidates() to get only moves for pieces that are not pinned.
 *
 * The out-parameters may both be NULL, but if any of them is set, the other
 * must be set, too.
 *
 * @param gamestate the current game state
 * @param row row of the field to check
 * @param file file of the field to check
 * @param color the color of the piece that should move to the field
 * @param moves the array where to store the moves
 * (must be large enough, 16 is always enough)
 * @param movecount a pointer where the number of moves is stored
 * @return true, if any piece of the specified color can move to the specified
 * field regardless of being pinned
 */
bool get_candidates(const GameState *gamestate, Row row, File file,
        Color color, Move* moves, size_t* movecount);

/**
 * Determines a list of possible moves to the specified field.
 *
 * This cannot be used to check if a piece covers / threatens a field because
 * this is also possible when the piece is pinned. Use get_candidates() for a
 * list of possible moves regardless of pins.
 *
 * The out-parameters may both be NULL, but if any of them is set, the other
 * must be set, too.
 *
 * @param gamestate the current game state
 * @param row row of the field to check
 * @param file file of the field to check
 * @param color the color of the piece that should move to the field
 * @param moves the array where to store the moves
 * (must be large enough, 16 is always enough)
 * @param movecount a pointer where the number of moves is stored
 * @return true, if any piece of the specified color can move to the specified
 * field and is not pinned
 */
bool get_real_candidates(const GameState *gamestate, Row row, File file,
        Color color, Move* moves, size_t* movecount);

/**
 * Checks, if a specified field is threatened by a piece of a certain color.
 *
 * A field is threatened, if there is a piece of the specified color that could
 * capture an opponent piece on this field, regardless of being pinned.
 * 
 * The out-parameters may both be NULL, but if any of them is set, the other
 * must be set, too.
 * 
 * @param gamestate the current game state
 * @param row row of the field to check
 * @param file file of the field to check
 * @param color the color of the piece that should threaten the field
 * @param threats the array where to store the threats
 * (must be large enough, 16 is always enough)
 * @param threatcount a pointer where the count of threats is stored
 * @return true, if any piece of the specified color threatens the specified
 * field
 */
bool get_threats(const GameState *gamestate, Row row, File file,
        Color color, Move* threats, size_t* threatcount);

/**
 * Checks, if a specified field is threatened by a piece of a certain color AND
 * if this piece is not pinned and therefore able to perform the move.
 * 
 * The out-parameters may both be NULL, but if any of them is set, the other
 * must be set, too.
 * 
 * @param gamestate the current game state
 * @param row row of the field to check
 * @param file file of the field to check
 * @param color the color of the piece that should threaten the field
 * @param threats the array where to store the threats
 * (must be large enough, 16 is always enough)
 * @param threatcount a pointer where the count of threats is stored
 * @return true, if any piece of the specified color threatens the specified
 * field and is not pinned
 */
bool get_real_threats(const GameState *gamestate, Row row, File file,
        Color color, Move* threats, size_t* threatcount);

/**
 * Checks, if a specified field is threatened by a piece of a certain color.
 *
 * A field is threatened, if there is a piece of the specified color that could
 * capture an opponent piece on this field, regardless of being pinned.
 * 
 * @param gamestate the current game state
 * @param row row of the field to check
 * @param file file of the field to check
 * @param color the color of the piece that should cover the field
 * @return true, if any piece of the specified color threatens the specified
 * field
 */
#define is_covered(gamestate, row, file, color) \
    get_threats(gamestate, row, file, color, NULL, NULL)

/**
 * Checks, if a specified field is attacked by a piece of a certain color.
 * 
 * I.e. the field is threatened by a piece AND this piece is not pinned and
 * therefore able to perform the move.
 * 
 * @param gamestate the current game state
 * @param row row of the field to check
 * @param file file of the field to check
 * @param color the color of the piece that should cover the field
 * @return true, if any piece of the specified color threatens the specified
 * field and could capture an opponent piece
 */
#define is_attacked(gamestate, row, file, color) \
    get_real_threats(gamestate, row, file, color, NULL, NULL)

/**
 * Checks, if a specified field is protected by a piece of a certain color.
 * 
 * A field is protected, if any piece except the king can either capture on
 * that field or move to that field (and is not pinned).
 * 
 * @param gamestate the current game state
 * @param row row of the field to check
 * @param file file of the field to check
 * @param color the color of the piece that should cover the field
 * @return true, if any piece (excluding the king) of the specified color
 * can move to the specified field (including capturing moves)
 */
bool is_protected(const GameState *gamestate, Row row, File file, Color color);

/**
 * Checks, if the specified move cannot be performed, because the piece is
 * either pinned or cannot remove the check.
 * 
 * Note: in chess a piece is pinned, when it can't be moved because the move
 * would result in a check position. But this function <u>also</u> returns true,
 * if the king is already in check position and the specified move does not
 * protect the king.
 * 
 * @param gamestate the current game state
 * @param move the move to check
 * @return true, if the move cannot be performed because the king would be in
 * check after the move
 */
bool is_pinned(const GameState *gamestate, const Move *move);

/**
 * Evaluates a move syntactically and stores the move data in the specified
 * object.
 *
 * When short algebraic notation is used, the source position is determined by
 * evaluating the allowed moves according to the current game state.
 *
 * This function expects correct notation of check and checkmate indicators.
 * For a more lazy evaluation, use eval_move_lazy().
 *
 * For a purely syntactic check, regardless of whether a piece exists that is
 * allowed to move that way, use check_move().
 * 
 * @param gamestate the current game state
 * @param mstr the input string to parse
 * @param color the color of the player to evaluate the move for
 * @param move a pointer to object where the move data shall be stored
 * @return status code (see macros in this file for the list of codes)
 */
int eval_move(const GameState *gamestate,
    const char *mstr, Color color, Move *move);

/**
 * Evaluates a move syntactically and stores the move data in the specified
 * object.
 *
 * When short algebraic notation is used, the source position is determined by
 * evaluating the allowed moves according to the current game state.
 *
 * This function automatically corrects missing or incorrect check/checkmate
 * indicators. Use eval_move() if you want to keep the original notation.
 *
 * For a purely syntactic check, regardless of whether a piece exists that is
 * allowed to move that way, use check_move().
 *
 * @param gamestate the current game state
 * @param mstr the input string to parse
 * @param color the color of the player to evaluate the move for
 * @param move a pointer to object where the move data shall be stored
 * @return status code (see macros in this file for the list of codes)
 */
int eval_move_lazy(const GameState *gamestate,
    const char *mstr, Color color, Move *move);

/**
 * Syntactically checks a move without verifying that a piece exists that is
 * allowed to move that way.
 *
 * @param mstr the input string to parse
 * @param color the color of the player to evaluate the move for
 * @return status code (see macros in this file for the list of codes)
 */
int check_move(const char *mstr, Color color);

/**
 * Validates move by applying chess rules.
 * @param gamestate the current game state
 * @param move the move to validate
 * @return status code (see macros in this file for the list of codes)
 */
int validate_move(const GameState *gamestate, const Move *move);

/**
 * Applies a move and deletes captured pieces.
 * 
 * @param gamestate the current game state
 * @param move the move to apply
 */
void apply_move(GameState *gamestate, Move *move);

/**
 * Copies the state of the game at the specified move number.
 *
 * This function is helpful to generate a game state for reviewing past moves.
 *
 * @param gamestate the current game state
 * @param move_number the half-move that would now be played
 * @param replay the struct to populate with the state at the specified move
 */
void gamestate_at_move(const GameState *gamestate,
        unsigned move_number, GameState *replay);

/**
 * Returns the remaining time on the clock for the specified
 * half-move number.
 *
 * @param gamestate the current game state
 * @param move_number the half-move that is now going to be played
 * @return the remaining time - if time control is disabled, this function
 * always returns zero
 */
uint16_t remaining_movetime2(const GameState *gamestate, unsigned move_number);

/**
 * Returns the remaining time on the clock for the specified player.
 *
 * @param gamestate the current game state
 * @param color either BLACK or WHITE
 * @return the remaining time - if time control is disabled, this function
 * always returns zero
 */
uint16_t remaining_movetime(const GameState *gamestate, Color color);

/**
 * Converts clock time to string.
 *
 * @param time the time to format
 * @param str the target buffer (should be at least 10 chars large)
 * @param always_hours if hours should always be printed
 */
int print_clk(uint16_t time, char *str, bool always_hours);

/**
 * Checks if the current position already appeared two times before.
 *
 * This does not set the threefold flag in the game state as this flag is
 * intended to be set only when the game ends after actually claiming a draw.
 *
 * By standard chess rules this is not automatically a draw.
 * But implementation may choose to automatically draw the game anyway.
 *
 * @param gamestate the current game state
 * @return true if the game is in a threefold repetition position
 */
bool check_threefold_repetition(const GameState *gamestate);

/**
 * Checks if neither side has enough material left to win the game.
 *
 * Returns true if for both players one of the following three cases are true:
 * - they have only the king left
 * - they have a king + knight and the opponent has king + queens
 * - they have a king + bishop and the opponent doesn't have
 *   opposite color bishops or knights or pawns
 *
 * @param gamestate the current game state
 * @return true if neither side can win due to insufficient material
 */
bool check_no_material(const GameState *gamestate);

#endif	/* RULES_H */