Chess engine for chess without checks in C++

Question

Project Description:

Chess without checks: A chess variant where you can take the enemy king.

This engine implementation is for chess without checks. Since checks don't exist, expect the code to not account for pinned pieces. Kings can move to dangerous squares (and be captured next turn). Castling is not implemented yet.

The project is comprised of 3 .cpp and 3 .h files, and main.cpp

Most of the action happens in board.cpp, which is the one I needed review for the most.

---

File explanation:

graphics.cpp uses SDL2 library to draw the window, board and pieces, and handle events.

fen.cpp declares the Type and Color enums for the pieces, and loads FEN codes into the board. The board is an array of 64 ints. Color and Type int values are combined to create an int that represents a piece.

board.cpp handles everything that happens on the board. When the user plays a move, it calculates a response with PlayComputerMove() which in turn uses Minimax(int(&board)[64], int depth, bool isMaximizing) to find the best move. I have big performance issues here.

Evaluate(int(&board)[64]) evaluates the position. Note that it only counts material. The computer doesn't understand strategy, so when no obvious moves exist (taking a piece, protecting a piece) it just moves pieces back and forth, which is to be expected.

---

Concerns:

1. Performance: Even at a depth of 3, the algorithm seems to be taking multiple seconds to finish. You may notice std::chrono::duration<double,std::milli> total; which counts the milliseconds that GetLegalMoves(int position) took to execute (in sum for all the times it was called) each move. In my system, it seems to take ~1000ms, and PlayComputerMove() takes about 5-6 thousand ms.

2. Design: Currently, the algorithm searches the board for the black/white pieces in a for loop. I could use a std::map to keep track of the pieces at all times, but I believe it wouldn't positively impact performance by a lot.

GetLegalMoves(int position) returns a std::list<int>*. This works, but it seems ugly to me. I do delete it after I don't need the list anymore. Returning a reference to a list seems to throw exceptions. I am only doing this to avoid copying the list.

Comments on bad practices and bad style in my code are also greatly appreciated.

Note: Implementing strategy (accounting for doubled pawns, center control, pawns close to promotion) is not my priority for now.

---

Code:

graphics.h

#ifndef GRAPHICS_H
#define GRAPHICS_H
#include <memory>
#include <chrono>
#include <thread>
#include "board.h"
#include "SDL.h"
#define SCREEN_X 0
#define SCREEN_Y 0
#define SCREEN_WIDTH 640
#define SCREEN_HEIGHT 640
#define SQUARE_SIZE 64
class Graphics {
 std::unique_ptr<SDL_Window, decltype(&SDL_DestroyWindow)> window;
 std::unique_ptr<SDL_Renderer, decltype(&SDL_DestroyRenderer)> renderer;
 std::chrono::system_clock::time_point a = std::chrono::system_clock::now();
 std::chrono::system_clock::time_point b = std::chrono::system_clock::now();
 SDL_Texture* boardTexture;
 SDL_Texture* piecesTexture;
 Board* board;
 SDL_Event ev;
 int mouse_x, mouse_y;
 bool Init();
 void InitBoard();
 void InitSpritesheet();
 void FillPiece(int piece, int xx, int yy);
public:
 Graphics();
 ~Graphics();
 void PreRender();
 void Render();
 void UpdatePieces();
 void LimitFPS();
 bool InputCheck();
 void SetBoard(Board* board);
};
#endif

graphics.cpp

#include <iostream>
#include "graphics.h"
Graphics::Graphics() : window(nullptr, SDL_DestroyWindow), renderer(nullptr, SDL_DestroyRenderer) {
 Init();
 InitBoard();
 InitSpritesheet();
}
Graphics::~Graphics() {
 SDL_DestroyTexture(boardTexture);
 SDL_Quit();
}
void Graphics::PreRender() {
 SDL_RenderClear(renderer.get());
 SDL_RenderCopy(renderer.get(), boardTexture, 0, 0);
}
bool Graphics::Init(){
 if (SDL_Init(SDL_INIT_VIDEO) < 0) {
 std::cerr << "SDL failed to initialize. Error:" << SDL_GetError() << std::endl;
 return false;
 }
 else {
 window.reset(SDL_CreateWindow("Chess AI", SDL_WINDOWPOS_CENTERED, SDL_WINDOWPOS_CENTERED, SCREEN_WIDTH, SCREEN_HEIGHT, SDL_WINDOW_SHOWN));
 renderer.reset(SDL_CreateRenderer(window.get(), -1, SDL_RENDERER_ACCELERATED));
 return true;
 }
}
void Graphics::InitBoard() {
 SDL_Rect r;
 r.x = SCREEN_X;
 r.y = SCREEN_Y;
 r.w = SQUARE_SIZE;
 r.h = SQUARE_SIZE;
 SDL_Surface* surf = SDL_GetWindowSurface(window.get());
 for (int i = 0; i < 8; i++) {
 for (int j = 0; j < 8; j += 2) {
 SDL_FillRect(surf, &r, 0xAFC3C7FF);
 r.x += SQUARE_SIZE * 2;
 }
 r.y += SQUARE_SIZE;
 r.x = (r.x == SQUARE_SIZE * 9 ? 0 : SQUARE_SIZE);
 }
 r.y = SCREEN_Y;
 r.x = SQUARE_SIZE;
 for (int i = 0; i < 8; i++) {
 for (int j = 0; j < 8; j += 2) {
 SDL_FillRect(surf, &r, 0x618187FF);
 r.x += SQUARE_SIZE * 2;
 }
 r.y += SQUARE_SIZE;
 r.x = (r.x == SQUARE_SIZE * 9 ? 0 : SQUARE_SIZE);
 }
 boardTexture = SDL_CreateTextureFromSurface(renderer.get(), surf);
 SDL_FreeSurface(surf);
}
void Graphics::InitSpritesheet() {
 SDL_Surface* surf = SDL_LoadBMP("pieces.bmp");
 if (surf == NULL) {
 std::cerr << "Unable to load spritesheet. Error:" << SDL_GetError() << std::endl;
 }
 piecesTexture = SDL_CreateTextureFromSurface(renderer.get(), surf);
 SDL_FreeSurface(surf);
}
void Graphics::LimitFPS()
{
 a = std::chrono::system_clock::now();
 std::chrono::duration<double, std::milli> work_time = a - b;
 if (work_time.count() < 16.75) {
 std::chrono::duration<double, std::milli> delta_ms(16.75 - work_time.count());
 auto delta_ms_duration = std::chrono::duration_cast<std::chrono::milliseconds>(delta_ms);
 std::this_thread::sleep_for(std::chrono::milliseconds(delta_ms_duration.count()));
 }
 b = std::chrono::system_clock::now();
 std::chrono::duration<double, std::milli> sleep_time = b - a;
}
bool Graphics::InputCheck() {
 while (SDL_PollEvent(&ev) != 0) {
 SDL_GetMouseState(&mouse_x, &mouse_y);
 switch(ev.type){
 case SDL_QUIT:
 return true;
 break;
 case SDL_MOUSEBUTTONDOWN:
 int index = ((mouse_x - SCREEN_X) / SQUARE_SIZE) % 8 + ((mouse_y - SCREEN_Y) / SQUARE_SIZE) * 8;
 board->Click(index);
 break;
 }
 }
 return false;
}
void Graphics::SetBoard(Board* board) {
 Graphics::board = board;
}
void Graphics::Render() {
 SDL_RenderPresent(renderer.get());
}
void Graphics::FillPiece(int piece, int xx, int yy) {
 Type t = GetType(piece);
 int y = (GetColor(piece) == Color::White ? 0 : SQUARE_SIZE);
 int x = 0;
 switch (t) {
 case Type::King:
 x = 0;
 break;
 case Type::Queen:
 x = SQUARE_SIZE;
 break;
 case Type::Bishop:
 x = 2 * SQUARE_SIZE;
 break;
 case Type::Knight:
 x = 3 * SQUARE_SIZE;
 break;
 case Type::Rook:
 x = 4 * SQUARE_SIZE;
 break;
 case Type::Pawn:
 x = 5 * SQUARE_SIZE;
 break;
 }
 SDL_Rect srcRect;
 SDL_Rect dstRect;
 srcRect.x = x;
 srcRect.y = y;
 srcRect.w = SQUARE_SIZE;
 srcRect.h = SQUARE_SIZE;
 dstRect.x = xx;
 dstRect.y = yy;
 dstRect.w = SQUARE_SIZE;
 dstRect.h = SQUARE_SIZE;
 SDL_RenderCopy(renderer.get(), piecesTexture, &srcRect, &dstRect);
}
void Graphics::UpdatePieces() {
 for (int i = 0; i < 64; i++) {
 int piece = board->GetPiece(i);
 if (piece != 0) {
 FillPiece(piece, (i % 8) * SQUARE_SIZE, (i >> 3) * SQUARE_SIZE);
 }
 }
 int heldPiece = board->GetHeldPiece();
 if (heldPiece != 0) {
 FillPiece(heldPiece, mouse_x - SQUARE_SIZE / 2, mouse_y - SQUARE_SIZE / 2);
 }
}

fen.h

#ifndef FEN_H
#define FEN_H
#include <string>
#include <vector>
#include <array>
#include <ostream>
#include <istream>
#include <sstream>
enum class Type {
 Pawn = 1,
 Knight = 2,
 Bishop = 4,
 Rook = 8,
 Queen = 16,
 King = 32
};
enum class Color {
 Black = 64,
 White = 128
};
inline Type GetType(int piece) {
 return static_cast<Type>(piece & 0x3F);
}
inline Color GetColor(int piece) {
 return static_cast<Color>((piece >> 6) << 6);
}
struct FEN {
 std::string piecePlacement;
 Color activeColor;
 bool whiteCanCastleKingside;
 bool whiteCanCastleQueenside;
 bool blackCanCastleKingside;
 bool blackCanCastleQueenside;
 int enPassantSquare;
 bool justMovedTwoSquares;
 int halfmoveClock;
 int fullmoveNumber;
 int blackKingPos;
 int whiteKingPos;
 FEN(int (&board)[64], std::string& str);
};
inline std::ostream& operator<<(std::ostream& out, const FEN& fen) {
 out << "FEN: {\n"
 << fen.piecePlacement << ", \n"
 << ((fen.activeColor == Color::White) ? "White to play" : "Black to play") << ", \n"
 << "Move: " << fen.fullmoveNumber << "\n"
 << "}"
 << std::endl;
 return out;
}
#endif

fen.cpp

#include "fen.h"
// Syntactic sugar
int operator|(const Type& T, const Color& C) {
 return static_cast<int>(T) | static_cast<int>(C);
}
bool operator&(int I, Type T) {
 return I & static_cast<int>(T);
}
bool operator&(int I, Color C) {
 return I & static_cast<int>(C);
}
template <typename Out>
void split(const std::string& s, char delim, Out result) {
 std::istringstream iss(s);
 std::string item;
 while (std::getline(iss, item, delim)) {
 *result++ = item;
 }
};
std::vector<std::string> split(const std::string& s, char delim) {
 std::vector<std::string> elems;
 split(s, delim, std::back_inserter(elems));
 return elems;
};
FEN::FEN(int(&board)[64], std::string& str) {
 std::vector<std::string> fenParts = split(str, ' ');
 piecePlacement = fenParts[0];
 int i = 0;
 for (char c : piecePlacement) {
 if (c != '/') {
 if (c >= '1' && c <= '8') {
 i += c - '0';
 }
 else {
 if (isupper(c)) {
 board[i] += (int)Color::White;
 }
 else {
 board[i] += (int)Color::Black;
 }
 switch (tolower(c)) {
 case 'p':
 board[i] += (int)Type::Pawn;
 break;
 case 'n':
 board[i] += (int)Type::Knight;
 break;
 case 'b':
 board[i] += (int)Type::Bishop;
 break;
 case 'r':
 board[i] += (int)Type::Rook;
 break;
 case 'q':
 board[i] += (int)Type::Queen;
 break;
 case 'k':
 board[i] += (int)Type::King;
 if (board[i] & Color::White) {
 whiteKingPos = i;
 }
 else {
 blackKingPos = i;
 }
 break;
 }
 i++;
 }
 }
 }
 activeColor = (fenParts[1])[0] == 'w' ? Color::White : Color::Black;
 for (char c : fenParts[2]) {
 switch (c) {
 case 'K':
 whiteCanCastleKingside = true;
 break;
 case 'Q':
 whiteCanCastleQueenside = true;
 break;
 case 'k':
 blackCanCastleKingside = true;
 break;
 case 'q':
 blackCanCastleQueenside = true;
 break;
 }
 }
 if ((fenParts[3])[0] != '-') {
 int letter = (fenParts[3])[0] - 'a';
 int number = (fenParts[3])[0] - '0' * 8;
 enPassantSquare = letter + number;
 }
 halfmoveClock = std::stoi(fenParts[4]);
 fullmoveNumber = std::stoi(fenParts[5]);
}

board.h

#ifndef BOARD_H
#define BOARD_H
#include <memory>
#include <map>
#include <chrono>
#include <list>
#include "fen.h"
class Board {
 int board[64];
 std::unique_ptr<FEN> fen;
 std::list<int>* heldLegalMoves;
 int legalMoveCounter = 0;
 std::chrono::duration<double,std::milli> total;
 int heldPiece, heldSquare = -1;
 bool toMove = true;
 bool justMovedTwoSquares = false;
 void PlayComputerMove();
 int Evaluate(int(&board)[64]);
 int Minimax(int(&board)[64], int depth, bool isMaximizing);
public:
 Board(std::string& fenCode);
 std::list<int>* GetLegalMoves(int position);
 
 void Click(int index);
 void UndoClick();
 const int GetPiece(int index) const;
 int GetHeldPiece();
};
#endif

board.cpp

#include "board.h"
#include <algorithm>
#include <iostream>
Board::Board(std::string& fenCode) {
 fen = std::make_unique<FEN>(board, fenCode);
}
std::list<int>* Board::GetLegalMoves(int position) {
 auto t1 = std::chrono::high_resolution_clock::now();
 std::list<int>* ret = new std::list<int>;
 int piece = board[position];
 Type t = GetType(piece);
 Color c = GetColor(piece);
 Color e = ((c == Color::White) ? Color::Black : Color::White);
 switch (t) {
 case Type::Pawn:
 {
 if (c == Color::White) {
 if (position >= 8) {
 if (position >= 48 && position <= 55 && board[position - 16] == 0 && board[position - 8] == 0) {
 ret->push_back(position - 16);
 fen->enPassantSquare = position - 8;
 justMovedTwoSquares = true;
 }
 if (board[position - 8] == 0) {
 ret->push_back(position - 8);
 }
 if ((position % 8 != 0 && GetColor(board[position - 9]) == e) || fen->enPassantSquare == position - 9) {
 ret->push_back(position - 9);
 }
 if ((position + 1) % 8 != 0 && GetColor(board[position - 7]) == e || fen->enPassantSquare == position - 7) {
 ret->push_back(position - 7);
 }
 }
 }
 else {
 if (position <= 55) {
 if (position >= 8 && position <= 15 && board[position + 16] == 0 && board[position + 8] == 0) {
 ret->push_back(position + 16);
 fen->enPassantSquare = position + 8;
 justMovedTwoSquares = true;
 }
 if (board[position + 8] == 0) {
 ret->push_back(position + 8);
 }
 if ((position % 8 != 0 && GetColor(board[position + 7]) == e) || fen->enPassantSquare == position + 7) {
 ret->push_back(position + 7);
 }
 if (((position + 1) % 8 != 0 && GetColor(board[position + 9]) == e) || fen->enPassantSquare == position + 9) {
 ret->push_back(position + 9);
 }
 }
 }
 break;
 }
 case Type::Knight:
 {
 if (position >= 16 && position % 8 != 0) {
 if (GetColor(board[position - 17]) != c) {
 ret->push_back(position - 17);
 }
 }
 if (position >= 16 && (position + 1) % 8 != 0) {
 if (GetColor(board[position - 15]) != c) {
 ret->push_back(position - 15);
 }
 }
 if (position >= 8 && position % 8 != 0 && (position - 1) % 8 != 0) {
 if (GetColor(board[position - 10]) != c) {
 ret->push_back(position - 10);
 }
 }
 if (position >= 8 && (position + 1) % 8 != 0 && (position + 2) % 8 != 0) {
 if (GetColor(board[position - 6]) != c) {
 ret->push_back(position - 6);
 }
 }
 if (position <= 47 && (position + 1) % 8 != 0) {
 if (GetColor(board[position + 17]) != c) {
 ret->push_back(position + 17);
 }
 }
 if (position <= 47 && position % 8 != 0) {
 if (GetColor(board[position + 15]) != c) {
 ret->push_back(position + 15);
 }
 }
 if (position <= 55 && (position + 1) % 8 != 0 && (position + 2) % 8 != 0) {
 if (GetColor(board[position + 10]) != c) {
 ret->push_back(position + 10);
 }
 }
 if (position <= 55 && position % 8 != 0 && (position - 1) % 8 != 0) {
 if (GetColor(board[position + 6]) != c) {
 ret->push_back(position + 6);
 }
 }
 break;
 }
 case Type::Bishop:
 {
 int pTemp = position;
 while (pTemp >= 9 && (pTemp % 8 != 0)) {
 pTemp -= 9;
 if (board[pTemp] != 0) {
 if (GetColor(board[pTemp]) == e)
 ret->push_back(pTemp);
 break;
 }
 ret->push_back(pTemp);
 }
 pTemp = position;
 while (pTemp >= 8 && ((pTemp + 1) % 8 != 0)) {
 pTemp -= 7;
 if (board[pTemp] != 0) {
 if (GetColor(board[pTemp]) == e)
 ret->push_back(pTemp);
 break;
 }
 ret->push_back(pTemp);
 }
 pTemp = position;
 while (pTemp <= 55 && (pTemp % 8 != 0)) {
 pTemp += 7;
 if (board[pTemp] != 0) {
 if (GetColor(board[pTemp]) == e)
 ret->push_back(pTemp);
 break;
 }
 ret->push_back(pTemp);
 }
 pTemp = position;
 while (pTemp <= 55 && ((pTemp + 1) % 8 != 0)) {
 pTemp += 9;
 if (board[pTemp] != 0) {
 if (GetColor(board[pTemp]) == e)
 ret->push_back(pTemp);
 break;
 }
 ret->push_back(pTemp);
 }
 break;
 }
 case Type::Rook:
 {
 int pTemp = position;
 while (((pTemp--)) % 8 != 0) {
 if (board[pTemp] != 0) {
 if (GetColor(board[pTemp]) == e)
 ret->push_back(pTemp);
 break;
 }
 ret->push_back(pTemp);
 }
 pTemp = position;
 while ((++pTemp) % 8 != 0) {
 if (board[pTemp] != 0) {
 if (GetColor(board[pTemp]) == e)
 ret->push_back(pTemp);
 break;
 }
 ret->push_back(pTemp);
 }
 pTemp = position;
 while (pTemp >= 8) {
 pTemp -= 8;
 if (board[pTemp] != 0) {
 if (GetColor(board[pTemp]) == e)
 ret->push_back(pTemp);
 break;
 }
 ret->push_back(pTemp);
 }
 pTemp = position;
 while (pTemp <= 55 != 0) {
 pTemp += 8;
 if (board[pTemp] != 0) {
 if (GetColor(board[pTemp]) == e)
 ret->push_back(pTemp);
 break;
 }
 ret->push_back(pTemp);
 }
 break;
 }
 case Type::Queen:
 {
 int pTemp = position;
 while (pTemp >= 9 && (pTemp % 8 != 0)) {
 pTemp -= 9;
 if (board[pTemp] != 0) {
 if (GetColor(board[pTemp]) == e)
 ret->push_back(pTemp);
 break;
 }
 ret->push_back(pTemp);
 }
 pTemp = position;
 while (pTemp >= 8 && ((pTemp + 1) % 8 != 0)) {
 pTemp -= 7;
 if (board[pTemp] != 0) {
 if (GetColor(board[pTemp]) == e)
 ret->push_back(pTemp);
 break;
 }
 ret->push_back(pTemp);
 }
 pTemp = position;
 while (pTemp <= 55 && (pTemp % 8 != 0)) {
 pTemp += 7;
 if (board[pTemp] != 0) {
 if (GetColor(board[pTemp]) == e)
 ret->push_back(pTemp);
 break;
 }
 ret->push_back(pTemp);
 }
 pTemp = position;
 while (pTemp <= 55 && ((pTemp + 1) % 8 != 0)) {
 pTemp += 9;
 if (board[pTemp] != 0) {
 if (GetColor(board[pTemp]) == e)
 ret->push_back(pTemp);
 break;
 }
 ret->push_back(pTemp);
 }
 pTemp = position;
 while (((pTemp--)) % 8 != 0) {
 if (board[pTemp] != 0) {
 if (GetColor(board[pTemp]) == e)
 ret->push_back(pTemp);
 break;
 }
 ret->push_back(pTemp);
 }
 pTemp = position;
 while ((++pTemp) % 8 != 0) {
 if (board[pTemp] != 0) {
 if (GetColor(board[pTemp]) == e)
 ret->push_back(pTemp);
 break;
 }
 ret->push_back(pTemp);
 }
 pTemp = position;
 while (pTemp >= 8) {
 pTemp -= 8;
 if (board[pTemp] != 0) {
 if (GetColor(board[pTemp]) == e)
 ret->push_back(pTemp);
 break;
 }
 ret->push_back(pTemp);
 }
 pTemp = position;
 while (pTemp <= 55 != 0) {
 pTemp += 8;
 if (board[pTemp] != 0) {
 if (GetColor(board[pTemp]) == e)
 ret->push_back(pTemp);
 break;
 }
 ret->push_back(pTemp);
 }
 break;
 }
 case Type::King:
 {
 if (c == Color::White) {
 if (position == 60) {
 if (fen->whiteCanCastleKingside && board[62] == 0) {
 ret->push_back(62);
 }
 if (fen->whiteCanCastleQueenside && board[58] == 0) {
 ret->push_back(58);
 }
 }
 }
 else {
 if (position == 4) {
 if (fen->blackCanCastleKingside && board[6] == 0) {
 ret->push_back(6);
 }
 if (fen->blackCanCastleQueenside && board[2] == 0) {
 ret->push_back(2);
 }
 }
 }
 if (position % 8 != 0) {
 if (position >= 9) {
 if (GetColor(board[position - 9]) != c)
 ret->push_back(position - 9);
 }
 if (GetColor(board[position - 1]) != c)
 ret->push_back(position - 1);
 if (position <= 55) {
 if (GetColor(board[position + 7]) != c)
 ret->push_back(position + 7);
 }
 }
 if ((position + 1) % 8 != 0) {
 if (position >= 7) {
 if (GetColor(board[position - 7]) != c)
 ret->push_back(position - 7);
 }
 if (GetColor(board[position + 1]) != c)
 ret->push_back(position + 1);
 if (position < 55) {
 if (GetColor(board[position + 9]) != c)
 ret->push_back(position + 9);
 }
 }
 if (position >= 8) {
 if (GetColor(board[position - 8]) != c)
 ret->push_back(position - 8);
 }
 if (position <= 55) {
 if (GetColor(board[position + 8]) != c)
 ret->push_back(position + 8);
 }
 break;
 }
 }
 auto t2 = std::chrono::high_resolution_clock::now();
 total += t2 - t1;
 legalMoveCounter += ret->size();
 return ret;
}
int Board::Evaluate(int(&board)[64]) {
 int eval = 0;
 int whiteBishopCount = 0;
 int blackBishopCount = 0;
 for (int i = 0; i < 64; i++) {
 int piece = board[i];
 if (piece != 0) {
 int sign = GetColor(piece) == Color::White ? -1 : 1;
 Color c = GetColor(piece);
 Type t = GetType(piece);
 switch (t) {
 case Type::Pawn: {
 eval += 10 * sign;
 break;
 }
 case Type::Knight: {
 eval += 30 * sign;
 break;
 }
 case Type::Bishop: {
 if (c == Color::White) {
 whiteBishopCount++;
 if (whiteBishopCount > 1) {
 eval += 5;
 }
 }
 else {
 blackBishopCount++;
 if (blackBishopCount > 1) {
 eval -= 5;
 }
 }
 eval += 30 * sign;
 break;
 }
 case Type::Rook: {
 eval += 40 * sign;
 break;
 }
 case Type::Queen: {
 eval += 90 * sign;
 break;
 }
 case Type::King: {
 eval += INT16_MAX * sign;
 break;
 }
 }
 }
 }
 return eval;
}
void Board::Click(int index) {
 if (heldSquare == index) {
 UndoClick();
 return;
 }
 if (heldPiece == 0) {
 if (toMove) {
 delete heldLegalMoves;
 heldPiece = board[index];
 heldLegalMoves = GetLegalMoves(index);
 board[index] = 0;
 heldSquare = index;
 }
 }
 else {
 if (std::find(heldLegalMoves->begin(), heldLegalMoves->end(), index) != heldLegalMoves->end()) {
 if (index == fen->enPassantSquare && GetType(heldPiece) == Type::Pawn) {
 if (fen->enPassantSquare < 32) {
 board[index + 8] = 0;
 }
 else {
 board[index - 8] = 0;
 }
 }
 board[index] = heldPiece;
 heldPiece = 0;
 heldSquare = -1;
 toMove = false;
 PlayComputerMove();
 if (!justMovedTwoSquares) {
 fen->enPassantSquare = 0;
 }
 else {
 justMovedTwoSquares = false;
 }
 }
 else {
 UndoClick();
 }
 }
}
void Board::UndoClick() {
 if (heldPiece != 0) {
 board[heldSquare] = heldPiece;
 heldPiece = 0;
 heldSquare = -1;
 }
}
void Board::PlayComputerMove() {
 std::vector<int> blackPieces;
 for (int i = 0; i < 64; i++) {
 if (board[i] != 0 && GetColor(board[i]) == Color::Black) {
 blackPieces.push_back(i);
 }
 }
 int bestScore = INT_MIN;
 int bestMove = -1;
 int bestMoveOld = -1;
 for (int i : blackPieces) {
 auto legalMoves = GetLegalMoves(i);
 if (legalMoves->size() != 0) {
 for (int move : *legalMoves) {
 int oldP = board[move];
 board[move] = board[i];
 board[i] = 0;
 int score = Minimax(board, 2, false);
 board[i] = board[move];
 board[move] = oldP;
 if (score > bestScore) {
 bestScore = score;
 bestMove = move;
 bestMoveOld = i;
 }
 }
 }
 delete legalMoves;
 }
 board[bestMove] = board[bestMoveOld];
 board[bestMoveOld] = 0;
 toMove = true;
 std::cout << "Total time spent on legalmoves:" << total.count() << std::endl;
 std::cout << "Total legalmoves:" << legalMoveCounter << std::endl;
 legalMoveCounter = 0;
 total -= total;
}
int Board::Minimax(int(&board)[64], int depth, bool isMaximizing) {
 int result = Evaluate(board);
 // An evaluation bigger than 400 means that a king is taken, since
 // the evaluation of all the other pieces is less than 400 in total
 if (depth == 0 || result > 400 || result < -400) {
 return result;
 }
 if (isMaximizing) {
 int bestScore = INT_MIN;
 std::vector<int> blackPieces;
 for (int i = 0; i < 64; i++) {
 if (board[i] != 0 && GetColor(board[i]) == Color::Black) {
 blackPieces.push_back(i);
 }
 }
 for (int i : blackPieces) {
 auto legalMoves = GetLegalMoves(i);
 if (legalMoves->size() != 0) {
 for (int move : *legalMoves) {
 int oldP = board[move];
 board[move] = board[i];
 board[i] = 0;
 int score = Minimax(board, depth - 1, false);
 board[i] = board[move];
 board[move] = oldP;
 bestScore = std::max(score, bestScore);
 }
 }
 delete legalMoves;
 }
 return bestScore;
 }
 else {
 int bestScore = INT_MAX;
 std::vector<int> whitePieces;
 for (int i = 0; i < 64; i++) {
 if (board[i] != 0 && GetColor(board[i]) == Color::White) {
 whitePieces.push_back(i);
 }
 }
 for (int i : whitePieces) {
 auto legalMoves = GetLegalMoves(i);
 if (legalMoves->size() != 0) {
 for (int move : *legalMoves) {
 int oldP = board[move];
 board[move] = board[i];
 board[i] = 0;
 int score = Minimax(board, depth - 1, true);
 board[i] = board[move];
 board[move] = oldP;
 bestScore = std::min(score, bestScore);
 }
 }
 delete legalMoves;
 }
 return bestScore;
 }
}
int Board::GetHeldPiece() {
 return heldPiece;
}
const int Board::GetPiece(int index) const{
 return board[index];
}

main.cpp

#define SDL_MAIN_HANDLED 
#include <iostream>
#include "graphics.h"
#define VERSION "1.0.0"
int main() {
 std::string fenCode = "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1";
 Graphics g;
 Board b(fenCode);
 g.SetBoard(&b);
 bool quit = false;
 while (!quit) {
 g.LimitFPS();
 quit = g.InputCheck();
 g.PreRender();
 g.UpdatePieces();
 g.Render();
 }
 return 0;
}

• Daniel Lidström: Some general thoughts: don't use new in hot code (search), don't use vector or list (prefer c-arrays, you may pre-allocate 6 arrays for the 3 moves you search (6 ply). In general avoid any kind of allocation in hot code. Next, use alpha-beta instead of minimax. Will save you quite a bit.
• Yakk: @Offtkp If you are doing it a handful of times in response to a user action, vector is cheap. If you are doing it once per pixel per frame, or once per lookahead move, or the like, vector is expensive. In almost every case, std::list is a premature pessimization; do not use it unless you are spicing an order of magnitude more often than you are iterating, or your node data is a large number of kilobytes in size, and then still probably don't use it.
• Daniel Lidström: @Offkp you can absolutely use STL containers outside of your hot code. In your hot code you need to drop down a level. The fastest engines use all kinds of tricks to optimze the hot code. To have an idea of what such highly optimized code looks like, see for example github.com/abulmo/Dumb/blob/master/src/board.d (D language) or github.com/abulmo/hqperft/blob/master/hqperft.c (C language). Those examples might be overkill for you though.
• Karl Knechtel: If there is no check and nothing special about capturing a king, what exactly is the object of the game?
• Cody Gray: When writing in C++, there's no reason to use anything but standard library containers, even in "hot" code. Replace "c-arrays" in @Daniel Lidström's original comment with std::array (which is nothing more than a standard-library wrapper around a C-style array). The reason you want to avoid std::vector is the dynamic memory allocation. That problem doesn't plague std::array, since it is statically allocated (with the obvious caveat that the size cannot grow dynamically and must be specified at compile time.)

Answer 1

Here are some things that may help you improve your code.

Don't const qualify POD return values

The code includes this member function within Board:

const int GetPiece(int index) const;

The second const is useful and appropriate but the first one is not. It says that the return value may not be altered by the caller which is obviously not correct for plain old data (POD) such as int and is probably ignored by the compiler anyway.

Use C++ limits

The code includes INT_MIN which is defined in the old C <limits.h> file (which is not #included). You could add that file, but better would be to use std::numeric_limits<int>::min() from <limits>.

Beware of partially constructed objects

The Board constructor is currently this:

Board::Board(std::string& fenCode) {
 fen = std::make_unique<FEN>(board, fenCode);
}

However, the problem is that board, which is passed to the fen constructor, is uninitialized. A more subtle problem is this line:

int heldPiece, heldSquare = -1;

Due to C++ (and C) syntax, heldPiece does not get initialized. This is one of the major reasons that the guidelines say to always initalize every object (see ES.20).

Don't pass objects needlessly

The Evaluate() and Minimax() functions are both member functions of Board and so they already have access to data member board without explicitly passing it as an argument.

Prefer std::array to plain arrays

In pretty much every way, std::array is better than old-style plain C arrays. So I'd suggest Board::board should be std::array<int, 64>. See SL.con.1 for details.

Rethink the the use of pointers

The fen object is currently owned by the Board object as a std::unique_ptr, but this isn't really necessary. Instead, I'd suggest that if you follow the suggestions above, you can make fen just a plain FEN fen; and the Board constructor could look like this:

Board::Board(std::string& fenCode) 
 : board{}
 , fen(board, fenCode)
{}

Remove spurious semicolons

The semicolon at the end of both versions of split in fen.cpp can and should be omitted.

Eliminate "magic numbers"

This code is littered with "magic numbers," that is, unnamed constants such as 55, 62, 64, etc. Generally it's better to avoid that and give such constants meaningful names. That way, if anything ever needs to be changed, you won't have to go hunting through the code for all instances of "62" and then trying to determine if this particular 62 means that White can castle on the King's side or some other constant that happens to have the same value.

Evaluate whether an enum class is better expressed as a class

There are many places in the code where some operation is applied to a piece, but what exactly happens depends on whether it's a knight, bishop, queen, etc. For that reason, I'd suggest that a better approach may be to create a base Piece class and derive Knight, Bishop, etc. This would allow you to keep things better organized and reduce a great deal of repetition from the code. The board could contain pointers to Piece and then invoking actions on each would automatically route to the correct routine, whether for evaluating value or determining legal moves.

Use appropriate data structures

The heldLegalMoves is declared to be a std::list<int>* but I see no reason it couldn't instead be a much more efficient std::vector<int> without the pointer.

Understand the API

There is a fundamental problem in the way you're trying to draw the board. The problem is that you've already created a renderer, and then the code attempts to call SDL_GetWindowSurface(). Worse, the return value (which is nullptr on my machine) is never checked and it is later freed. You can either have a renderer or use SDL_GetWindowSurface() but not both. See https://wiki.libsdl.org/SDL_GetWindowSurface

If you do that, Graphics::InitBoard() gets simpler, and you can completely remove boardTexture and all references to it too:

void Graphics::InitBoard() {
 SDL_Rect r{SCREEN_X, SCREEN_Y, SQUARE_SIZE, SQUARE_SIZE};
 constexpr std::array<std::array<std::uint8_t, 4>, 2> color{{
 {0x61, 0x81, 0x87, 0xFF}, // dark color
 {0xAF, 0xC3, 0xC7, 0xFF} // light color
 }};
 bool light{true};
 for (int i = 0; i < 8; i++) {
 for (int j = 0; j < 8; ++j) {
 SDL_SetRenderDrawColor(renderer.get(), 
 color[light][0], color[light][1], color[light][2], color[light][3]
 );
 SDL_RenderFillRect(renderer.get(), &r); 
 r.x += SQUARE_SIZE;
 light = !light;
 }
 light = !light;
 r.y += SQUARE_SIZE;
 r.x = SCREEN_X;
 }
 SDL_SetRenderDrawColor(renderer.get(), 0, 0, 0, 255);
}

Think of the user

I was surprised to find out that I could manually move either the white or the black pieces. Maybe that's intentional? Being able to reverse or alter a move that my opponent just made might come in handy, but it's unexpected. Also, I understand this is a work in progress, but I was disappointed that castling (which you did mention) and pawn promotion (which you didn't) aren't yet implemented. Still, it was kind of fun!

Answer 2

The answers so far are good critiques of the code at a technical level, but optimizing performance of a chess engine is a separate topic. Without aggressive optimizations at the algorithmic level you will quickly run into a combinatorial explosion and very slow performance, and a number of chess-specific techniques have been studied to help with this problem. I haven't done this myself but I have read about it.

One example out of the many techniques available is "alpha-beta pruning" which is a way to stop considering entire trees of moves once it is found that another move is definitely better. This leads to a significant time savings. Read more: https://www.chessprogramming.org/Alpha-Beta#How_it_works

Here are even more links to dig deeper:

• https://www.chessprogramming.org/Getting_Started - a good overview of the concepts involved, even though you've already started down this path
• https://stackoverflow.com/questions/494721/what-are-some-good-resources-for-writing-a-chess-engine - explanations and links to a lot of other resources
• http://www.frayn.net/beowulf/theory.html - Computer Chess Programming Theory site including explanations and examples of some commonly used algorithms.

Answer 3

Note: this is just a review of graphics.h and graphics.cpp.

Apply RAII consistently

I see you used std::unique_ptr for window and renderer, but you did not use smart pointers for boardTexture and piecesTexture. Use smart pointers for those objects as well. You already have a memory leak here because you never call SDL_DestroyTexture(piecesTexture).

Be careful about the order of object creation and destruction

There is already a code smell when looking at the constructor and destructor of class Graphics: the constructor doesn't call any SDL functions directly, but instead calls Init*() functions. But the destructor calls SDL_DestroyTexture() and SDL_Quit() directly. Try to keep things symmetric: if you have an Init() function, there should be a corresponding Exit().

But a more subtle issue is the order in which member variables are constructed and destructed. At first glance, the code looks fine, but consider that the constructors of window and renderer have run before the body of Graphics::Graphics() itself. Destructors run in the reverse order of the constructors. So once the Graphics object is destructed, first the body of Graphics::~Graphics() is run, which calls SDL_Quit(), and only then will SDL_DestroyWindow() and SDL_DestroyRenderer() be called. This order is incorrect, and may cause a crash when the program exits.

There are various ways to solve this issue. If you want to go the RAII way, then create a class that calls SDL_Init() in its constructor and SDL_Quit() in its destructor, and put a member variable of that type at the start of the definition of class Graphics.

Check if variables need to be initialized

Raw pointers and built-in types like int are not initialized (unless they are declared static). Especially for pointers, you have to be careful that you don't accidentily dereference an unitialized pointer. Also keep in mind that while you think you might properly initialize them at some point, there might be an error condition occuring before that point which will cause destructors to be called that then might see the unitialized value. For pointer types, avoid raw pointers or ensure they are initialized to nulltpr.

For board, consider initializing it in the constructor. You can declare a Boardinmain()before you declare aGraphics` object.

Avoid adding unnecessary member variables

There is no need for having ev, mouse_x and mouse_y be a member variables of class Graphics. Just declare them as a local variable in Graphics::InputCheck(), they are not used elsewhere.

Use VSync to limit the FPS

Just pass the flag SDL_HINT_RENDER_VSYNC to SDL_CreateRenderer(), and SDL will take care of limiting the framerate. It will also prevent tearing.

Answer 4

Use the single responsibility principle.

Your board class stores a board state, evaluates it, runs the AI, provides a scoring function, stores game state, does profiling, supports undo, handles mouse clicks, produces a list of legal moves, and stores pieces being held by the user.

I might have missed something.

Make a class that stores a board state. Give it a simple API. Provide methods to modify the board state, possibly as simple as [[nodiscard]] Board Board::RemovePiece(Location) const and [[nodiscard]] Board Board::AddPiece(Location, Piece, Color) const (note they are const; I made my board Immutable, so editing it returns a brand new board; this isn't as insane as it might sound, as boards are small.)

Then have a function that takes a board and returns valid moves. It should not be part of the board class, especially in an initial pass.

Similarly, split off a scoring function from the board class, and an class that represents a function taking a scoring function, a valid move generator, and a board, and decides which move to pick.

Your legal moves should be either a vector of moves (not a pointer to it) which involves 1 memeory allocation, or even an array with a size (which involves 0 memory allocations). Memory allocations cost on the order of 100s of instructions, no point in doing them needlessly; and you'll want to get legal moves really often.

UI interaction should not be part of the above at all. The user-agent should store the state specific to a user. It might be a good idea to not care if the user-agent is a human or an AI as far as the Game class is concerned.

The display of the board is, naturally not a concern of the Board class itself. If you go with the immutable board design above, then the display engine has a copy of its own Board, and you change what you display by saying "SetBoard" into it.

An immutable board class can have some costs, but it does mean you can do things like send a copy of it off to the AI to solve in a thread without worrying about state shared with the UI.

For future use, Board should have ==/!= and a hash function. That will permit the AI to be working on future multiple future board states on the human turn, and when passed the result of the human turn can prune its tree to look into the one corresponding to the human's move. (It also helps for stalemate detection and move databases, but move databases should probably be fancier than just equality and hash really)

You are using ints a lot as different types of thing. Toss them into a struct;

struct Piece {
 Piece()=default;
 Piece( Type, Color );
 [[nodiscard]] Type Type()const;
 [[nodiscard]] Color Color()const;
 explicit operator bool()const{return bits!=-1;}
 [[nodiscard]] unsigned int GetInternalBits()const{return bits;}
 [[nodiscard]] static Piece MakeFromBits(unsigned int b){
 Piece retval;
 retval.SetInternalBits(b);
 return retval;
 }
private:
 void SetInternalBits(unsigned int b){bits=b;}
 unsigned int bits=-1;
};

This makes the Type/Color API more friendly; the bits interface exists, with intentionally awkward names, as you should use it only when you have to. It is also an immutable type; if you want to change the piece, use operator= and assign over it.

Use [[nodiscard]] whenever a function's job is to produce its return value; discarding that return value is a sign of a bug. (You can still force it with a void cast)

Always initialize your class member variables when declared;

int halfmoveClock = 0;

Use std::array instead of raw C arrays.

Write your AI code reentrantly and functionally. You have your universe of knowledge (the state), write a function that improves that universe of knowledge by 1 step (in some sense). Ideally the universe of knowledge can be split up (into multiple branches, say), and you can run the advance code in parallel on multiple branches.

Anticipating the need to multithread, make this code pure and functional -- it takes in some state, and produces some additional objects providing more knowledge.

This lets you (a) unit test the step logic seperately from the main AI, (b) thread off the AI work, (c) do AI work while the user is choosing their move, all of which can give you 100x or more CPU time to do AI work. Of course, writing a better AI will do more than 100x CPU time improvement, but breaking y our monolithic function down will help you do that as well.

• Edward: Good comments, especially about multithreading. I had considered that as well, but your answer states the issues and solution more clearly and succinctly than I would have done. Good job!
• Peter Cordes: I think Piece MakeFromBits(unsigned int b) should be static. It doesn't use any class members, and returns a new Piece.