18
\$\begingroup\$

Basic Description

What is the program for?

This is just a hobby project for me to improve at coding, not a serious one.

What does the program do?

It can take a chess position (not including variations like chess960 etc.), and generate all legal moves from it. Draw and checkmates are not added yet.

File and function description

main.cpp/hpp - Currently only used for testing

Note The functions here are just for debugging, thus don't matter much. Any feedback on how to write better code here is still appreciated though.

  • perft()/perftDivide() Perft test to check the move generation function.
  • printStateTest() Only used for debugging; prints the gameState.

gameState.cpp/hpp - Basic board handling

  • gameState - Game state class.
  • addPiece()/deletePiece()/movePieceFromPos() Pretty self-explanatory.
  • initWithFEN() Initialize game state with FEN notation.
  • isSameColor()/isSameType() Compare the color/type of two pieces.
  • oppositeColor() Make the piece an opponent's piece.

piece.hpp - Defines the enum value of the pieces

move.cpp/hpp - Move handling

  • pieceMove Move class.
  • initMove() Initialize pieceMove.
  • applyMove() Makes a move and updates the game state accordingly.
  • cordAlgebraicToNum() Converts an algebraic coordinate to the internal numeric format.
  • cordNumToAlgebraic() Opposite of the function above.
  • moveToUCI() Converts a piece move to UCI format.

moveGen.cpp/hpp - Move generation

  • isInCheck() Check if the selected side is in check. Doesn't use the function below, to increase performance .
  • generatePseudoMoves() Generate pseudo-legal moves.
  • generateLegalMoves() Filter legal moves from the function above.
  • generateSlidingMoves() Generate directional moves with specified depth.
  • easyMask() Generate move mask (see below).
  • moveCanBeMade() Testing if a move can be made without crossing the edge of the board.

What do I plan to add in the future?

  • Positional evaluation
  • AI engine

What do I wish to improve?

As I plan to implement more features to the code, I'm looking for ways to improve the structure and performance of it. (e.g. Better algorithms, code style...)

Any sort of help is appreciated, and thanks in advance!

The Code

main.cpp

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include "gameState.hpp"
#include "pieces.hpp"
#include "move.hpp"
#include "moveGen.hpp"
#include "main.hpp"

std::map<std::string, int> perftDivide (gameState currentState, int depth) {
    std::map<std::string, int> output;
    int sideToMove = currentState.whiteToMove ? COLOR_WHITE : COLOR_BLACK;
    std::vector<pieceMove> moveList = generateLegalMoves(currentState, sideToMove);
    
    for (int i = 0; i < moveList.size(); ++i) {
        output[moveToUCI(moveList[i])] = perft(applyMove(currentState, moveList[i]), depth - 1);
    }
    
    return output;
}

int perft (gameState currentState, int depth) {
    int sideToMove = currentState.whiteToMove ? COLOR_WHITE : COLOR_BLACK;
    std::vector<pieceMove> moveList = generateLegalMoves(currentState, sideToMove);
    int positionNum = 0;
    
    if (depth == 0) {
        return 1;
    }
    
    if (depth == 1) {
        return moveList.size();
    }
    
    for (int i = 0; i < moveList.size(); ++i) {
        positionNum += perft(applyMove(currentState, moveList[i]), depth - 1);
    }
    
    return positionNum;
}

void printStateTest(gameState test) { //Temp function for printing class gameState
    std::map<int, char> pieces = {
        {9, 'P'}, {10, 'N'}, {11,'B'}, {12, 'R'}, {13, 'Q'}, {14, 'K'},
        {17, 'p'}, {18, 'n'}, {19,'b'}, {20, 'r'}, {21, 'q'}, {22, 'k'}
    };
    int temp;
    
    std::cout << "Board:\n";
    for (int i = 7; i >= 0; --i) {
        for (int j = 0; j < 8; ++j) {
            temp = test.board[i * 8 + j];
            if (temp != 0) {
                std::cout << pieces[temp];
            } else {
                std::cout << ".";
            }
        }
        std::cout << std::endl;
    }
    
    std::cout << "White To Move: " <<  (test.whiteToMove == 1) << "\n";
    std::cout << "Castling Right: {";
    for (int i = 0; i < 4; ++ i) {
        std::cout << test.castlingRights[i] << " ";
    }
    std::cout << "}" << std::endl;
    std::cout << "En Passant: " << test.enPassant << "\n";
    std::cout << "Move Clock: " << test.moveClock << "\n";
    std::cout << "Moves: " << test.wholeTurn << "\n";
}

int main() {
    //Example usage
    gameState test = initWithFEN("rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 8");
    printStateTest(test);
    std::cout << "Position " << perft(test, 4) << "\n";
    
    return 0;
}

main.hpp

#ifndef main_h
#define main_h
#include "gameState.hpp"

int perft (gameState currentState, int depth);
std::map<std::string, int> perftDivide (gameState currentState, int depth);
void printStateTest(gameState test);
#endif /* main_h */

gameState.cpp

#include <string>
#include "gameState.hpp"
#include "pieces.hpp"
#include "move.hpp"

std::map<char, int>charToPiece = {
    {'P', TYPE_PAWN},
    {'N', TYPE_KNIGHT},
    {'B', TYPE_BISHOP},
    {'R', TYPE_ROOK},
    {'Q', TYPE_QUEEN},
    {'K', TYPE_KING},
};

bool isSameColor (int original, int reference) {
    return (original & 24) == (reference & 24);
}

bool isSameType (int original, int reference) {
    return (original & 7) == (reference & 7);
}

int oppsiteColor (int original) {
    int output;
    
    switch (original & 24) {
        case 8:
            output = (original & 7) | 16;
            break;
            
        case 16:
            output = (original & 7) | 8;
            break;
            
        default:
            output = original;
    }
    
    return output;
}

gameState addPiece (gameState currentState, int pieceType, int position) {
    gameState newState = currentState;
    newState.board[position] = pieceType;
    
    return newState;
}

gameState deletePiece (gameState currentState, int position) {
    gameState newState = currentState;
    newState.board[position] = 0;
    
    return newState;
}

gameState movePieceFromPos (gameState currentState, int startPos, int endPos) {
    gameState newState = currentState;
    newState = addPiece(newState, newState.board[startPos], endPos);
    newState = deletePiece(newState, startPos);
    
    return newState;
}

gameState initWithFEN (std::string FEN) {
    gameState newState;
    std::vector<std::string> parts(6);
    
    //Seperate different parts
    int temp = 0;
    for (int i = 0; i < FEN.size(); ++i) {
        if (FEN[i] == ' ') {
            ++temp;
        } else {
            parts[temp] += FEN[i];
            
        }
    }
    
    //Setting up the board
    int rank = 7, file = 0, piece;
    std::string boardFEN = parts[0];
    char current;
    for (int i = 0; i < boardFEN.size(); ++i) {
        current = boardFEN[i];
        if (current == '/') {
            file = 0;
            --rank;
        } else {
            if (isdigit(current)) {
                file += current - '0';
            } else {
                piece = charToPiece[toupper(current)];
                piece += isupper(current) ? COLOR_WHITE : COLOR_BLACK;
                newState.board[rank * 8 + file] = piece;
                ++file;
            }
        }
    }
    
    //Side to move
    newState.whiteToMove = (parts[1] == "w");
    
    //Castling rights
    for (int i = 0; i < parts[2].size(); ++i) {
        if (parts[2][i] == 'K') {
            newState.castlingRights[0] = true;
        }
        if (parts[2][i] == 'Q') {
            newState.castlingRights[1] = true;
        }
        if (parts[2][i] == 'k') {
            newState.castlingRights[2] = true;
        }
        if (parts[2][i] == 'q') {
            newState.castlingRights[3] = true;
        }
    }
    
    //En passant
    if (parts[3] == "-") {
        newState.enPassant = -1;
    } else {
        newState.enPassant = cordAlgebraicToNum(parts[3]);
    }
        
    //Half move clock
    newState.moveClock = std::stoi(parts[4]);
    
    //Whole moves
    newState.wholeTurn = std::stoi(parts[5]);
    
    return newState;
}
#include "gameState.hpp"

gameState.hpp

#ifndef gameState_hpp
#define gameState_hpp

#include <stdio.h>
#include <vector>
#include <string>

class gameState {
public:
    std::vector<int> board = std::vector<int>(64);
    std::vector<bool> castlingRights = std::vector<bool>(4);
    bool whiteToMove;
    int enPassant, wholeTurn, moveClock;
    
};

bool isSameColor (int original, int reference);
bool isSameType (int original, int reference);
int oppsiteColor (int original);
gameState addPiece (gameState currentState, int pieceType, int position);
gameState deletePiece (gameState currentState, int position);
gameState movePieceFromPos (gameState currentState, int startPos, int endPos);
gameState initWithFEN (std::string FEN);

#endif /* gameState_hpp */

piece.hpp

#ifndef pieces_hpp
#define pieces_hpp

#include <stdio.h>
#include <string>
#include <map>
enum pieceType {
    //EMPTY = 0,
    TYPE_PAWN = 1,
    TYPE_KNIGHT = 2,
    TYPE_BISHOP = 3,
    TYPE_ROOK = 4,
    TYPE_QUEEN = 5,
    TYPE_KING = 6
};

enum pieceColor {
    COLOR_WHITE = 8,
    COLOR_BLACK = 16,
    COLOR_ANY = 24
};

#endif /* pieces_hpp */

move.cpp

#include "move.hpp"
#include "gameState.hpp"
#include "pieces.hpp"

pieceMove initMove (int start, int end, int flag) {
    pieceMove output;
    output.startSqr = start;
    output.endSqr = end;
    output.flag = flag;
    
    return output;
}

gameState applyMove (gameState currentState, pieceMove move) { //Make move
    gameState newState;
    
    newState =  movePieceFromPos(currentState, move.startSqr, move.endSqr);
    
    newState.whiteToMove ^= 1;
    if (newState.whiteToMove) {
        ++newState.wholeTurn;
    }
    
    if (isSameType(newState.board[move.startSqr], TYPE_PAWN) || newState.board[move.endSqr] != 0) {
        newState.moveClock = 0;
    } else {
        ++newState.moveClock;
    }
    
    int castlingSide, isKingSide;
    for (int i = 0; i < 8; i += 7) {
        for (int j = 0; j < 8; j += 7) {
            if (move.startSqr == (i * 8 + j) || move.endSqr == (i * 8 + j)) {
                castlingSide = i == 0 ? 0 : 2;
                isKingSide = j == 0;
                
                newState.castlingRights[castlingSide | isKingSide] = false;
            }
        }
        
        if (move.startSqr == (i * 8 + 4) || move.endSqr == (i * 8 + 4)) {
            castlingSide = i == 0 ? 0 : 2;
            
            newState.castlingRights[castlingSide] = false;
            newState.castlingRights[castlingSide + 1] = false;
        }
    }
    
    switch (move.flag) {
        case FLAG_DOUBLE_JUMP: {
            newState.enPassant = move.endSqr;
            break;
        }
        
        case FLAG_EN_PASSANT: {
            newState.board[newState.enPassant] = 0;
            newState.enPassant = -1;
            break;
        }
            
        case FLAG_CASTLE: {
            int rookStartPosition = (move.startSqr - move.endSqr == 2) ? move.startSqr - 4 : move.startSqr + 3;
            int rookEndPosition = (move.startSqr - move.endSqr == 2) ? move.startSqr - 1 : move.startSqr + 1;
            newState = movePieceFromPos(newState, rookStartPosition, rookEndPosition);
            break;
        }
            
        case FLAG_PROMOTE_KNIGHT: {
            newState.board[move.endSqr] = (newState.board[move.endSqr] & 24) | TYPE_KNIGHT;
            break;
        }
            
        case FLAG_PROMOTE_BISHOP: {
            newState.board[move.endSqr] = (newState.board[move.endSqr] & 24) | TYPE_BISHOP;
            break;
        }
            
        case FLAG_PROMOTE_ROOK: {
            newState.board[move.endSqr] = (newState.board[move.endSqr] & 24) | TYPE_ROOK;
            break;
        }
            
        case FLAG_PROMOTE_QUEEN: {
            newState.board[move.endSqr] = (newState.board[move.endSqr] & 24) | TYPE_QUEEN;
            break;
        }
            
    }
    
    if (move.flag != FLAG_DOUBLE_JUMP) {
        newState.enPassant = -1;
    }
    
    return newState;
}


int cordAlgebraicToNum (std::string cordinate) {
    return (cordinate[0] - 'a') + (cordinate[1] - '1') * 8;
}

std::string cordNumToAlgebraic (int cordinate) {
    char rank = '1' + cordinate / 8;
    char file = (cordinate % 8) + ((int) 'a');
    
    return std::string() + file + rank;
}

std::string moveToUCI (pieceMove move) {
    std::string output;
    
    output = cordNumToAlgebraic(move.startSqr) + cordNumToAlgebraic(move.endSqr);
    
    switch (move.flag) {
        case FLAG_PROMOTE_KNIGHT: {
            output += "n";
            break;
        }
            
        case FLAG_PROMOTE_BISHOP: {
            output += "b";
            break;
        }
            
        case FLAG_PROMOTE_ROOK: {
            output += "r";
            break;
        }
            
        case FLAG_PROMOTE_QUEEN: {
            output += "q";
            break;
        }
    }
    
    return output;
}

move.hpp

#ifndef move_hpp
#define move_hpp

#include <stdio.h>
#include "gameState.hpp"

class pieceMove {
public:
    int startSqr;
    int endSqr;
    int flag;
};

enum moveFlag {
    FLAG_NONE = 0,
    FLAG_DOUBLE_JUMP = 1,
    FLAG_EN_PASSANT = 2,
    FLAG_CASTLE = 3,
    FLAG_PROMOTE_KNIGHT = 4,
    FLAG_PROMOTE_BISHOP = 5,
    FLAG_PROMOTE_ROOK = 6,
    FLAG_PROMOTE_QUEEN = 7
};

pieceMove initMove (int start, int end, int flag);
gameState applyMove (gameState currentState, pieceMove move);
int cordAlgebraicToNum (std::string cordinate);
std::string cordNumToAlgebraic (int cordinate);
std::string moveToUCI (pieceMove move);

#endif /* move_hpp */

moveGen.cpp

#include "moveGen.hpp"
#include "move.hpp"
#include "gameState.hpp"
#include "pieces.hpp"
#include <vector>
#include <iostream>
#include <math.h>

bool isInCheck (gameState currentState, int side) {
    int kingPosition = 0;

    for (int i = 0; i < 64; ++i) {
        if (currentState.board[i] == (side | TYPE_KING)) {
            kingPosition = i;
            break;
        }
    }
    
    //Pawn attacks
    int opponentDirection;
    opponentDirection = side == COLOR_WHITE ? 8 : -8;
    for (int i = -1; i < 2; i += 2) {
        if (moveCanBeMade(kingPosition, opponentDirection + i) && currentState.board[kingPosition + i + opponentDirection] == oppsiteColor(side | TYPE_PAWN)) {
            return true;
        }
    }
    
    //Knight attacks
    std::vector<int> directions = {-17, -15, -10, -6, 6, 10, 15, 17};
    int destination;
    for (int i = 0; i < directions.size(); ++i) {
        if (moveCanBeMade(kingPosition, directions[i])) {
            destination = kingPosition + directions[i];
            if (currentState.board[destination] == oppsiteColor(side | TYPE_KNIGHT)) {
                return true;
            }
        }
    }
    
    //King opposition
    directions = {-9, -8, -7, -1, 1, 7, 8, 9};
    for (int i = 0; i < directions.size(); ++i) {
        if (moveCanBeMade(kingPosition, directions[i])) {
            destination = kingPosition + directions[i];
            if (currentState.board[destination] == oppsiteColor(side | TYPE_KING)) {
                return true;
            }
        }
    }
    
    //Rook and (non-diaganol) Queen attacks
    directions = {-8, -1, 1, 8};
    for (int i = 0; i < directions.size(); ++i) {
        destination = kingPosition;
        for (int j = 0; j < 7; ++j) {
            //Can't move past the edge
            if (!moveCanBeMade(destination, directions[i])) {
                break;
            }
            
            destination += directions[i];
            //Found an attack piece
            if ((currentState.board[destination] == oppsiteColor(side | TYPE_ROOK)) || (currentState.board[destination] == oppsiteColor(side | TYPE_QUEEN))) {
                return true;
            }
            //Obstructed by piece
            if (currentState.board[destination]) {
                break;
            }
        }
    }
    
    //Bishop and (diaganol) Queen attacks
    directions = {-9, -7, 7, 9};
    for (int i = 0; i < directions.size(); ++i) {
        destination = kingPosition;
        for (int j = 0; j < 7; ++j) {
            //Can't move past the edge
            if (!moveCanBeMade(destination, directions[i])) {
                break;
            }
            
            destination += directions[i];
            //Found an attack piece
            if ((currentState.board[destination] == oppsiteColor(side | TYPE_BISHOP)) || (currentState.board[destination] == oppsiteColor(side | TYPE_QUEEN))) {
                return true;
            }
            //Obstructed by piece
            if (currentState.board[destination]) {
                break;
            }
        }
    }

    return false;
}

std::vector<pieceMove> generatePseudoMoves (gameState currentState, int sideToMove) {
    int piece, type;
    pieceMove move;
    std::vector<pieceMove> pseudoMoves;
    
    for (int i = 0; i < 64; ++i) {
        piece = currentState.board[i];
        if (isSameColor(piece, sideToMove)) {
            type = piece & 7;
            move.startSqr = i;
            switch (type) {
                case TYPE_PAWN: {
                    bool isWhite = isSameColor(piece, COLOR_WHITE);
                    int startingRank = isWhite ? 1 : 6;
                    int promotionRank = isWhite ? 7 : 0;
                    int forwardDirection = isWhite ? 8 : -8;
                    
                    //Forward move
                    if (currentState.board[i + forwardDirection] == 0 && moveCanBeMade(i, forwardDirection)) {
                        if ((i + forwardDirection) / 8 != promotionRank) {
                            pseudoMoves.push_back(initMove(i, i + forwardDirection, FLAG_NONE));
                        } else {
                            //Promotion
                            pseudoMoves.push_back(initMove(i, i + forwardDirection, FLAG_PROMOTE_KNIGHT));
                            pseudoMoves.push_back(initMove(i, i + forwardDirection, FLAG_PROMOTE_BISHOP));
                            pseudoMoves.push_back(initMove(i, i + forwardDirection, FLAG_PROMOTE_ROOK));
                            pseudoMoves.push_back(initMove(i, i + forwardDirection, FLAG_PROMOTE_QUEEN));
                        }
                        //Double jump
                        if (currentState.board[i + forwardDirection * 2] == 0 && (i / 8) == startingRank) {
                            pseudoMoves.push_back(initMove(i, i + forwardDirection * 2, FLAG_DOUBLE_JUMP));
                        }
                    }
                    
                    //Diagonal capture
                    int neighbor;
                    for (int j = -1; j < 2; j += 2) {
                        neighbor = i + j;
                        //Normal capture
                        if (moveCanBeMade(i, j + forwardDirection) && isSameColor(currentState.board[i], oppsiteColor(currentState.board[neighbor + forwardDirection]))) {
                            if ((i + forwardDirection) / 8 != promotionRank) {
                                pseudoMoves.push_back(initMove(i, neighbor + forwardDirection, FLAG_NONE));
                            } else {
                                //Promotion
                                pseudoMoves.push_back(initMove(i, neighbor + forwardDirection, FLAG_PROMOTE_KNIGHT));
                                pseudoMoves.push_back(initMove(i, neighbor + forwardDirection, FLAG_PROMOTE_BISHOP));
                                pseudoMoves.push_back(initMove(i, neighbor + forwardDirection, FLAG_PROMOTE_ROOK));
                                pseudoMoves.push_back(initMove(i, neighbor + forwardDirection, FLAG_PROMOTE_QUEEN));
                            }
                        }
                        
                        //En passant
                        if (moveCanBeMade(i, j + forwardDirection) && isSameColor(currentState.board[i], oppsiteColor(currentState.board[neighbor])) && currentState.enPassant == neighbor) {
                            pseudoMoves.push_back(initMove(i, neighbor + forwardDirection, FLAG_EN_PASSANT));
                        }
                    }
                    break;
                }
                    
                case TYPE_KNIGHT: {
                    std::vector<pieceMove> moveList = generateSlidingMoves(currentState, i, {-17, -15, -10, -6, 6, 10, 15, 17}, 1);
                    pseudoMoves.insert(std::end(pseudoMoves), std::begin(moveList), std::end(moveList));
                    break;
                }
                
                case TYPE_BISHOP: {
                    std::vector<pieceMove> moveList = generateSlidingMoves(currentState, i, {-9, -7, 7, 9}, 7);
                    pseudoMoves.insert(std::end(pseudoMoves), std::begin(moveList), std::end(moveList));
                    break;
                }
                    
                case TYPE_ROOK: {
                    std::vector<pieceMove> moveList = generateSlidingMoves(currentState, i, {-8, -1, 1, 8}, 7);
                    pseudoMoves.insert(std::end(pseudoMoves), std::begin(moveList), std::end(moveList));
                    break;
                }
                    
                case TYPE_QUEEN: {
                    std::vector<pieceMove> moveList = generateSlidingMoves(currentState, i, {-9, -8, -7, -1, 1, 7, 8, 9}, 7);
                    pseudoMoves.insert(std::end(pseudoMoves), std::begin(moveList), std::end(moveList));
                    break;
                }
                    
                case TYPE_KING: {
                    std::vector<pieceMove> moveList = generateSlidingMoves(currentState, i, {-9, -8, -7, -1, 1, 7, 8, 9}, 1);                   
                    pseudoMoves.insert(std::end(pseudoMoves), std::begin(moveList), std::end(moveList));
                    
                    int castlingRightsStart = sideToMove == COLOR_WHITE ? 0 : 2;
                    //Kingside castle
                    if (currentState.castlingRights[castlingRightsStart]) {
                        if (!(currentState.board[i + 1] | currentState.board[i + 2]) &&
                            !(isInCheck(currentState, sideToMove) || isInCheck(movePieceFromPos(currentState, i, i + 1), sideToMove))) {
                            pseudoMoves.push_back(initMove(i, i + 2, FLAG_CASTLE));
                        }
                    }
                    
                    //Queenside castle
                    if (currentState.castlingRights[castlingRightsStart + 1]) {
                        if (!(currentState.board[i - 1] | currentState.board[i - 2] | currentState.board[i - 3]) &&
                            !(isInCheck(currentState, sideToMove) || isInCheck(movePieceFromPos(currentState, i, i - 1), sideToMove))) {
                            pseudoMoves.push_back(initMove(i, i - 2, FLAG_CASTLE));
                        }
                    }
                    break;
                }
            }
        }
    }
    return pseudoMoves;
}

std::vector<pieceMove> generateLegalMoves (gameState currentState, int sideToMove) {
    std::vector<pieceMove> moveList, legalMoves, pseudoMoves = generatePseudoMoves(currentState, sideToMove);
    
    for (int i = 0; i < pseudoMoves.size(); ++i) {
        if (!isInCheck(applyMove(currentState, pseudoMoves[i]), sideToMove)) {
            legalMoves.push_back(pseudoMoves[i]);
        }
    }
    
    return legalMoves;
}

std::vector<pieceMove> generateSlidingMoves (gameState currentState, int square, std::vector<int> directions, int maxDepth) { //Move generation for Knights, Rooks, Queens and Kings
    std::vector<pieceMove> possibleMoves;
    pieceMove move;
    int destination;

    for (int i = 0; i < directions.size(); ++i) {
        destination = square;
        for (int j = 0; j < maxDepth; ++j) {
            //Can't move pass the edge
            if (!moveCanBeMade(destination, directions[i])) {
                break;
            }
            
            destination += directions[i];
            //Can't capture own piece
            if (isSameColor(currentState.board[square], currentState.board[destination])) {
                break;
            }
            
            move.endSqr = destination;
            possibleMoves.push_back(initMove(square, destination, FLAG_NONE));
            //Can't move past captured pieces
            if (isSameColor(currentState.board[square], oppsiteColor(currentState.board[destination]))) {
                break;
            }
        }
    }
    
    return possibleMoves;
}

long long int easyMask (int direction) { //Prevent moving past the edge
    long long int mask = 0;
    int vertical, horizontal;
    
    vertical = (int) lround((float) direction / 8);
    horizontal = direction - vertical * 8;
    
    if (horizontal != 0) {
        if (horizontal > 0) {
            for (int i = 0; i < horizontal; ++i) {
                mask = mask | ( 0x101010101010101 << (7 - i));
            }
        } else {
            for (int i = 0; i < (~horizontal + 1); ++i) {
                mask = mask | ( 0x101010101010101 << i);
            }
        }
    }
    
    if (vertical != 0) {
        if (vertical > 0) {
            for (int i = 0; i < vertical; ++i) {
                mask = mask | ( 0xff00000000000000 >> (i * 8));
            }
        } else {
            for (int i = 0; i < (~vertical + 1); ++i) {
                mask = mask | ( 0xff << (i * 8));
            }
        }
    }
    
    return mask;
}

bool moveCanBeMade (int square, int direction) {
    return !((easyMask(direction) >> square) & 1);
}

moveGen.hpp

#ifndef moveGen_hpp
#define moveGen_hpp

#include <stdio.h>
#include <vector>
#include "move.hpp"
#include "gameState.hpp"

bool isInCheck (gameState currentState, int side);
std::vector<pieceMove> generateSlidingMoves (gameState currentState, int square, std::vector<int> directions, int maxDepth);
std::vector<pieceMove> generatePseudoMoves (gameState currentState, int sideToMove);
std::vector<pieceMove> generateLegalMoves (gameState currentState, int sideToMove);
long long int easyMask (int direction);
bool moveCanBeMade (int square, int direction);
#endif /* moveGen_hpp */
\$\endgroup\$
4
  • 10
    \$\begingroup\$ Particularly for a new contributor this is an excellent first question - great formatting and layout. \$\endgroup\$
    – Reinderien
    Jun 2 at 14:32
  • 2
    \$\begingroup\$ Thank you! I made sure to write the question as clear as possible, to not waste people's time on making otherwise-simple-things out . \$\endgroup\$ Jun 2 at 15:07
  • \$\begingroup\$ Is it a copy'n'paste error that you #include "gameState.hpp" at the end of gameState.cpp? \$\endgroup\$
    – uli
    Jun 2 at 18:28
  • \$\begingroup\$ Huh. It seems like my compiler automatically added them. \$\endgroup\$ Jun 3 at 0:21
13
\$\begingroup\$
std::map<std::string, int> perftDivide (gameState currentState, int depth) {
    std::map<std::string, int> output;

First thing I notice: name your types. You have a map as the result, and a local variable with the same kind of map ... are these the same kind of thing, or do they just coincidentally use the same data structure? And what is it?

   int sideToMove = currentState.whiteToMove ? COLOR_WHITE : COLOR_BLACK;

Make that const. It doesn't change after you figure it out once.

    std::vector<pieceMove> moveList = generateLegalMoves(currentState, sideToMove);

Use auto. And why is sideToMove an integer rather than an enumeration type?

    for (int i = 0; i < moveList.size(); ++i) {
        output[moveToUCI(moveList[i])] = perft(applyMove(currentState, moveList[i]), depth - 1);
    }

You're going through the entire container in order, so use the range-based for loop:

for (auto& mv : moveList)
    output[moveToUCI(mv)] = perft(applyMove(currentState,mv), depth-1);

and that also takes care of the nit that you repeated moveList[i]. This is not a big deal for a vector, but more generally looking things up can be expensive. Don't do the same work multiple times in the same line!

As for whether mvshould be const as well, I can't tell just from looking here. Think about it. Add const throughout the code.


You are passing gamestate by value. This deep copies the two vectors it contains, you know. That function doesn't appear to modify the gamestate in-place. So why are you passing it around by value everywhere?


std::map<char, int>charToPiece = {
    {'P', TYPE_PAWN},
    {'N', TYPE_KNIGHT},
    {'B', TYPE_BISHOP},
    {'R', TYPE_ROOK},
    {'Q', TYPE_QUEEN},
    {'K', TYPE_KING},
};

This is a global variable, not static and not inside a namespace. You should be careful what global names you make, as this will become a problem when you combine libraries and other code.

I expect this is a fixed lookup table? Why isn't it const or better yet constexpr if your version of the compiler handles that. But still, for this use, that is a very expensive way to do it. This is better implemented as a function containing a switch statement. And, why is the map using int instead of the enumeration type?


class gameState {
public:
    std::vector<int> board = std::vector<int>(64);
    std::vector<bool> castlingRights = std::vector<bool>(4);
    bool whiteToMove;
    int enPassant, wholeTurn, moveClock;  
};

Those vectors are initialized to specific sizes... are they actually fixed size? Consider using an array instead of a vector if they will never change size! Note also that std::vector<bool> is weird. This may or may not bother you in this application.


pieceMove initMove (int start, int end, int flag) {
    pieceMove output;
    output.startSqr = start;
    output.endSqr = end;
    output.flag = flag;
    
    return output;
}

I think you meant to write a constructor. Even your comment calls this "initialize pieceMove". I see you wrote pieceMove as a class with all public data members and no functions, so it's just a plain struct. But maybe it should have member functions... you're just not using them right.


gameState initWithFEN (std::string FEN) {

Again, it appears that this should actually be a constructor for gameState.
You are passing in FEN by value. Do you actually need to make a local copy of the string? Normally you should pass these as const&, but it's even better to use std::string_view.

    //Castling rights
    for (int i = 0; i < parts[2].size(); ++i) {
        if (parts[2][i] == 'K') {
            newState.castlingRights[0] = true;
        }
        if (parts[2][i] == 'Q') {
            newState.castlingRights[1] = true;
        }
        if (parts[2][i] == 'k') {
            newState.castlingRights[2] = true;
        }
        if (parts[2][i] == 'q') {
            newState.castlingRights[3] = true;
        }
    }

Don't repeat blocks of code that only have one little thing like a single variable that's different between the copies. Copy/paste is not your friend.

You're also repeating the indexinging of parts[2].

All your commented sections in this long function should really be separate functions. Functions should be cohesive and do one thing.

To eliminate the duplicated statement, do the mapping of the letter to the index as a distinct step:

for (const auto L : parts[2]) {
   newState[castlingRights[castle_index(part)]=true;
}

long long int is compiler-specific as to how many bits it has. I think you are counting on it being a specific size. Also, you probably meant to be unsigned as you need the top bit for your bit flags as well. So use std::uint64_t.

Summary of issues to work on

  • Break up meandering functions into their individual helper functions.
  • Declare names for various types you use like the map.
  • Don't pass by value for non-simple types, most of the time.
  • Use the enumeration types you created. They are types, not just handy way to declare some constant ints.
  • Use classes properly: data members private, functions that work on them are member functions.
  • Use the special member functions for their proper role; i.e. constructors.
  • use const
  • use range-based for loop when you can.
  • Don't repeat code multiple times with only a single symbol changed between them.
\$\endgroup\$
8
  • \$\begingroup\$ Thanks! Although the functions in main.cpp is just for debugging purposes (thus its code doesn't matter much), I will keep these rules in mind when writing future functions. EDIT: The comment above is written before the answer edit. \$\endgroup\$ Jun 2 at 14:10
  • \$\begingroup\$ Also, since I plan to add an evaluation and search functions, I think I'd probably want to have duplicates of the same gameState. Other programs I see that doesn't work the same way mostly use makeMove() & unmakeMove(). Wouldn't that make it more expensive? \$\endgroup\$ Jun 2 at 14:17
  • 1
    \$\begingroup\$ @uri, He can use std::array or a plain built-in array. The need for std::array has been largely mitigated in later versions of the language, so I usually don't use that unless I actually need it (e.g. for a return value). \$\endgroup\$
    – JDługosz
    Jun 2 at 19:19
  • 2
    \$\begingroup\$ "better implemented as a function containing a switch statement." I would disagree with this. I prefer to only use switch when the code changes. If it's the same code, use a map of some sort. \$\endgroup\$ Jun 3 at 23:15
  • 1
    \$\begingroup\$ @ihavenoidea "meandering" Evocative of (this) but actually comes from a slow flowing meandering river. It means that the function does something, then does something else that's a different cohesive set of statements that's not cohesive with the previous group, the flows along into another different thing, etc. Think about floating down a lazy river with each bend showing you a different scene. \$\endgroup\$
    – JDługosz
    Jun 4 at 15:02
9
\$\begingroup\$

Note: I'm just adding a few things to previous reviews.

Include Guards

#ifndef main_h
#define main_h
...
#endif /* main_h */

The only important thing for them is to be unique. For that reason, I'd add a sequence of random characters to its end, just to make sure it doesn't collide with other include guards. Also, since they are macros, all rules for macros apply. In particular, use ALL_UPPERCASE_NAMES and only use them for macros.

Another thing I noticed there is that comment "main_h". What's the information a casual reader is supposed to gain from it? Was main_h defined or undefined in the preceding section? Two suggestions: Firstly, the last #endif in a header file terminates the include guards, this barely worth worth documenting. If you want to be really safe, comment it with include guard.

Piece Definitions

enum pieceType {
    //EMPTY = 0,
    TYPE_PAWN = 1,
    TYPE_KNIGHT = 2,
    TYPE_BISHOP = 3,
    TYPE_ROOK = 4,
    TYPE_QUEEN = 5,
    TYPE_KING = 6
};

Some notes on this:

  • TYPE_PAWN looks like a macro, see my previous comment.
  • Why is there no TYPE_EMPTY?
  • I think newer C++ supports enum class types where the constants don't leak into the surrounding namespace. Using that, you could then use pieceType::queen to replace TYPE_QUEEN.
  • With modern C++, you can also define the integer base type for an enumeration. Since you want performance and that is often tied to memory use, consider using uint8_t, which should be large enough.

There is also an according enumeration named pieceColor. The two form a compound type that bit-packs different kinds of information into what is represented as int throughout your program. Firstly, this is undocumented, making it difficult to understand. However, much worse, is that you use int all the time! A chessboard field is not a number, and it makes your code harder to read. Even if you created a simple typedef, it would help people to understand the code. If you created a proper type (perhaps overloading operators & and | for the enumeration) you could enjoy the type safety and expressiveness.

Flow Control

You have code like this:

for (...) {
    if (...) {
        ...
        // many lines of code
        ...
    }
}

In order to understand it, you have to skip over the many lines of code. A simple continue would make it easier to understand. Similarly, in oppsiteColor, where you write to a temporary, then break from the switch, only to return the temporary. Just return here, simple as that.

Magic Numbers

In the context of chess, I can well live with 64 (cells) and 8 (width/height). Here though, you also have 7, 4, 6, 16, 24 and a bunch of others. Avoid that, it makes code hard to read.

Bit Operations On Booleans

newState.whiteToMove ^= 1;

Don't. It works, but it's confusing. See "Principle of Least Surprise" as a general rule.

Vector vs. Arrays

For constant-size vectors like the cells of your board, use a std::array:

  • Vectors are typically implemented with three pointers, one to the beginning and end of the allocated storage, a third representing the number of actually created elements (see reserve() and resize()). On a 64-bit machine, that's 24 octets on top of the actually required memory for the cells. Your cells should fit into 64 octets overall, maybe even less. Keeping things small, also makes them fast by making better use of CPU caches.
  • Accessing elements of a vector requires first reading the start pointer, adding the index and then reading the element there. For a plain array, the indirection via the pointer is skipped, which improves performance.
  • Using the std::array wrapper, you still get things like iterators, size() methods etc.

Unnecessarily Large Scope

int piece;
for (int i = 0; i < boardFEN.size(); ++i) {
    ...
    piece = charToPiece[toupper(current)];
    piece += isupper(current) ? COLOR_WHITE : COLOR_BLACK;
    newState.board[rank * 8 + file] = piece;
    ...
}

Look at the use of piece in this code. It is never used between two loop iterations, which is again difficult to understand. Just use auto piece = ... exactly where it is used.

Another general rule violated here is to avoid uninitialized variables. This also applies to e.g. your gameState type. It should have constructors exactly to prevent uninitialized variables.

General Note

I'm not sure about the rest of your development. In particular, I'm wondering if you have unit tests and benchmarks to track your progress. Also, in particular for optimizing things, using a profiler is a valuable tool. These are wide fields, just keep in mind that you need to look at these things at some point.

\$\endgroup\$
6
  • \$\begingroup\$ Thank you! I'll try to improve the code by utilizing these tips. Extra questions: 1. What do I need to change when using array instead of vector? A lot of things broke when I tried to replace it. 2. I'm thinking about replacing the magic numbers with generateMove(horizontal, vertical). Wouldn't that take more computing resources? \$\endgroup\$ Jun 3 at 0:54
  • 3
    \$\begingroup\$ @羅凋守WitherClubtw To create an array, you need to specify its size. In gameState.hpp, the line std::vector<int> board would become std::array<int, 64> board. See here: en.cppreference.com/w/cpp/container/array \$\endgroup\$
    – Mark H
    Jun 3 at 4:33
  • 2
    \$\begingroup\$ I don't understand what you mean with your second question. The way to avoid magic numbers is simply to define named constants. Those don't cost additional computing resources, since they are replaced at compile time. \$\endgroup\$
    – uli
    Jun 3 at 7:53
  • 1
    \$\begingroup\$ @羅凋守WitherClubtw: Another speed advantage to std::array<char, 64> board is that the size is a compile-time constant, so for example copying one can be done with a fixed sequence of two 32-byte AVX load and store instructions like vmovdqu ymm0, [rdi], instead of needing to loop at all. (Or 4x 16-byte vectors are available on multiple ISAs without enabling any special ISA extensions). And removing a level of indirection: the data is right there, instead of pointed-to by the members of a std::vector. Note the use of char instead of int, usually 1/4 the size. \$\endgroup\$ Jun 4 at 2:30
  • \$\begingroup\$ @uil Thanks for the clarification. I was thinking of some algorithm that evaluates at compile time, but didn't know how to do it (I didn't know constexpr was a thing). As for the array part, I couldn't get it to work with built-inarray(direct substituting doesn't work). But I guess std::array works fine, too. \$\endgroup\$ Jun 4 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.