16
\$\begingroup\$

My chess game is over, everything has been finished, except for some special (like en passant)moves. The main part of the game is its engine which I have coded using the Minimax algorithm with alpha-beta pruning currently, It is searching at a depth of 4 moves ahead. this takes less than 4 seconds at most times to search for a move. This is the procedure are which I find a good move

  • Initialise two containers std::vector<std::string> legal_moves and pseudomoves

  • These two will hold all the possible moves in the current position from either player. The reason there are two containers is that one of them is generated by following all the individual rules for the pieces. For example, a bishop moves diagonally. These are the pseudomoves. This is because it does not look into the aspect of check in chess. That means if your king is under attack, you are ought to get rid of that attack either by blocking it or moving the king. Also in a situation where your king will come under attack AFTER you move a piece as it was blocking the attack. This is why I iterate through pseudomoves first.

  • Iterate through pseudomoves and perform each move in the container. After performing the move, if there is no check. Then the move is valid. Hence insert(themove,legal_moves.begin()).

  • After you have a valid set of moves. Start the search depth. Perform each move in the container and give it points based on your evaluation function, then pick the best accordingly. This is the minimax algorithm

Here are the values for each piece on the board, which is represented by an 8x8 integer array.

  • King = 10
  • Pawn = 1
  • Bishop = 3
  • Knight = 2
  • Queen = 6
  • Rook = 5

negative values of the same represent black pieces. Here is my chess class to that holds everything. My main goal is to speed up the time taken to get the best move.

chess2.h

#ifndef CHESS2_H_INCLUDED
#define CHESS2_H_INCLUDED

#include<vector>
#include<string>


typedef std::vector<std::string> buff;
typedef std::string str;

class Chess2
{
public:
    buff pseudomoves;
    buff legal_moves;
    short int board[8][8] = // This array represents the chess board
    {
      {-5,0,0,-6,-10,-2,-3,-5},
      {-1,-1,-1,0,0,-1,-1,-1},
      {0,0,-3,-1,0,0,0,0},
      {0,0,0,0,-1,0,0,0},
      {0,0,2,0,1,0,-2,0},
      {0,0,3,0,0,3,0,0},
      {1,1,1,1,0,1,1,1},
      {5,3,2,6,10,0,0,5},
    };
    int perform(str Move);
    str push(int row, int col, int desrow, int descol);
    buff getallmoves(bool turn);
    str computer_move(unsigned short int depth);
    bool checkmate(bool turn);

    bool check(bool turn);
    bool checkmatewhite = false;
    bool checkmateblack = false;
    private:
    void getdiagonalmoves(bool turn, int row, int col);
    void getstraigtmoves(bool turn, int row, int col);
    void getknightmoves(bool turn, int row, int col);
    void getpawnmoves(bool turn, int row, int col);
    void getkingmoves(bool turn, int row, int col);
    int evaluation();
    int miniMax(int depth, bool ismax, int alpha, int beta);
    str miniMaxroot(int depth, bool turn);
    void undomove(int original, str Move);
};


#endif // CHESS2_H_INCLUDED

Note that the board is not set to the starting position(for testing purposes)

chess2.cpp

#include "chess2.h"
#include<iostream>

int Chess2::perform(str Move) {
    int original;
    original = board[Move[2] - 48][Move[3] - 48];
    board[Move[2] - 48][Move[3] - 48] = board[Move[0] - 48][Move[1] - 48];
    board[Move[0] - 48][Move[1] - 48] = 0;
    return original;
}

str Chess2::push(int row, int col, int desrow, int descol) {
    using std::to_string;
    str mystr = to_string(row) + to_string(col) + to_string(desrow) + to_string(descol);
    return mystr;
}

str Chess2::computer_move(unsigned short int depth) {
    str bestmove;
    bestmove = miniMaxroot(depth, false);
    perform(bestmove);
    return bestmove;
}

buff Chess2::getallmoves(bool turn) {
    int original = 0;
    pseudomoves.clear();
    legal_moves.clear();
    if (turn == true) {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (!board[i][j]) continue;
                if (board[i][j] == 1) getpawnmoves(true, i, j);
                else if (board[i][j] == 2) getdiagonalmoves(true, i, j);
                else if (board[i][j] == 3) getknightmoves(true, i, j);
                else if (board[i][j] == 5) getstraigtmoves(true, i, j);
                else if (board[i][j] == 6) {
                    getdiagonalmoves(true, i, j);
                    getstraigtmoves(true, i, j);
                }
                else if (board[i][j] == 10) getkingmoves(true, i, j);
            }
        }
        for(std::string i:pseudomoves){
            original = perform(i);
            if (check(true) == false) {
                legal_moves.push_back(i);
            }
            undomove(original, i);
        }
    }
    else if (!turn) {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (!board[i][j]) continue;
                else if (board[i][j] == -1){
                    getpawnmoves(false, i, j);
                }
                else if (board[i][j] == -2) getdiagonalmoves(false, i, j);
                else if (board[i][j] == -3) getknightmoves(false, i, j);
                else if (board[i][j] == -5) getstraigtmoves(false, i, j);
                else if (board[i][j] == -6) {
                    getdiagonalmoves(false, i, j);
                    getstraigtmoves(false, i, j);
                }
                else if (board[i][j] == -10) getkingmoves(false, i, j);
            }
        }
        for(std::string i:pseudomoves){
            original = perform(i);
            if (check(false) == false) {
                legal_moves.push_back(i);
            }
            undomove(original, i);
        }
    }
    return legal_moves;
}

bool Chess2::check(bool turn) {

    if (turn == true) {
        bool found = false;
        int row, col;
        //Finding the king on the board

        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (board[i][j] == 10) {
                    row = i;
                    col = j;
                    found = true;
                    break;
                }
            }
        }
        if (found == false){
            return false;
        }

        //Finding the king on the board
        if (row != 0 && col != 0 && board[row - 1][col - 1] == -1) return true;
        else if (row != 0 && col != 7 && board[row - 1][col + 1] == -1) return true;
        int a, b;
        a = row;
        b = col;
        if (a != 0 && b != 0) {
            for (;;) {
                a -= 1;
                b -= 1;
                if (board[a][b] == -6 || board[a][b] == -2) return true;
                if (board[a][b] != 0 || a == 0 || b == 0) break;
            }
        }
        a = row;
        b = col;
        if (a != 0 && b != 7) {
            for (;;) {
                a -= 1;
                b += 1;
                if (board[a][b] == -6 || board[a][b] == -2) return true;
                if (board[a][b] != 0 || a == 0 || b == 7) break;
            }
        }
        a = row;
        b = col;
        if (a != 7 && b != 0) {
            for (;;) {
                a += 1;
                b -= 1;
                if (board[a][b] == -6 || board[a][b] == -2) return true;
                if (board[a][b] != 0 || a == 7 || b == 0) break;
            }
        }
        a = row;
        b = col;
        if (a != 7 && b != 7) {
            for (;;) {
                a += 1;
                b += 1;
                if (board[a][b] == -6 || board[a][b] == -2) return true;
                if (board[a][b] != 0 || a == 7 || b == 7) break;
            }
        }

        a = row;
        b = col;
        if (a != 7) {
            for (;;) {
                a += 1;
                if (board[a][b] == -6 || board[a][b] == -5) return true;
                if (board[a][b] != 0 || a == 7) break;
            }
        }
        a = row;
        b = col;
        if (a != 0) {
            for (;;) {
                a -= 1;
                if (board[a][b] == -6 || board[a][b] == -5) return true;
                if (board[a][b] != 0 || a == 0) break;
            }
        }

        a = row;
        b = col;
        if (b != 7) {
            for (;;) {
                b += 1;
                if (board[a][b] == -6 || board[a][b] == -5) return true;
                if (board[a][b] != 0 || b == 7) break;
            }
        }
        a = row;
        b = col;
        if (b != 0) {
            for (;;) {
                b -= 1;
                if (board[a][b] == -6 || board[a][b] == -5) return true;
                if (board[a][b] != 0 || b == 0) break;
            }
        }

        if (row > 0 && col < 6 && board[row - 1][col + 2] == -3)return true;
        if (row > 1 && col < 7 && board[row - 2][col + 1] == -3)return true;
        if (row < 7 && col < 6 && board[row + 1][col + 2] == -3)return true;
        if (row < 6 && col < 7 && board[row + 2][col + 1] == -3)return true;
        if (row < 6 && col > 0 && board[row + 2][col - 1] == -3)return true;
        if (row < 7 && col > 1 && board[row + 1][col - 2] == -3)return true;
        if (row > 1 && col > 0 && board[row - 2][col - 1] == -3)return true;
        if (row > 0 && col > 1 && board[row - 1][col - 2] == -3)return true;

        if (row != 7 && board[row + 1][col] == -10)return true;
        if (row != 0 && board[row - 1][col] == -10)return true;
        if (col != 7 && board[row][col + 1] == -10) return true;
        if (col != 0 && board[row][col - 1] == -10) return true;
        if (row != 7 && col != 7 && board[row + 1][col + 1] == -10)return true;
        if (row != 7 && col != 0 && board[row + 1][col - 1] == -10) return true;
        if (row != 0 && col != 7 && board[row - 1][col + 1] == -10) return true;
        if (row != 0 && col != 0 && board[row - 1][col - 1] == -10) return true;


    }

    else if (turn == false) {
        bool found = false;
        int row, col;
        //Finding the king on the board

        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (board[i][j] == -10) {
                    row = i;
                    col = j;
                    found = true;
                    break;
                }
            }
        }
        if (found == false){
            return false;
        }

        //Finding the king on the board

        if (row != 7 && col != 0 && board[row + 1][col - 1] == 1) return true;
        else if (row != 7 && col != 7 && board[row + 1][col + 1] == 1) return true;

        int a, b;
        a = row;
        b = col;
        if (a != 0 && b != 0) {
            for (;;) {
                a -= 1;
                b -= 1;
                if (board[a][b] == 6 || board[a][b] == 2) return true;
                if (board[a][b] != 0 || a == 0 || b == 0) break;
            }
        }
        a = row;
        b = col;
        if (a != 0 && b != 7) {
            for (;;) {
                a -= 1;
                b += 1;
                if (board[a][b] == 6 || board[a][b] == 2) return true;
                if (board[a][b] != 0 || a == 0 || b == 7) break;
            }
        }
        a = row;
        b = col;
        if (a != 7 && b != 0) {
            for (;;) {
                a += 1;
                b -= 1;
                if (board[a][b] == 6 || board[a][b] == 2) return true;
                if (board[a][b] != 0 || a == 7 || b == 0) break;
            }
        }
        a = row;
        b = col;
        if (a != 7 && b != 7) {
            for (;;) {
                a += 1;
                b += 1;
                if (board[a][b] == 6 || board[a][b] == 2) return true;
                if (board[a][b] != 0 || a == 7 || b == 7) break;
            }
        }

        a = row;
        b = col;
        if (a != 7) {
            for (;;) {
                a += 1;
                if (board[a][b] == 6 || board[a][b] == 5) return true;
                if (board[a][b] != 0 || a == 7) break;
            }
        }
        a = row;
        b = col;
        if (a != 0) {
            for (;;) {
                a -= 1;
                if (board[a][b] == 6 || board[a][b] == 5) return true;
                if (board[a][b] != 0 || a == 0) break;
            }
        }

        a = row;
        b = col;
        if (b != 7) {
            for (;;) {
                b += 1;
                if (board[a][b] == 6 || board[a][b] == 5) return true;
                if (board[a][b] != 0 || b == 7) break;
            }
        }
        a = row;
        b = col;
        if (b != 0) {
            for (;;) {
                b -= 1;
                if (board[a][b] == 6 || board[a][b] == 5) return true;
                if (board[a][b] != 0 || b == 0) break;
            }
        }

        if (row > 0 && col < 6 && board[row - 1][col + 2] == 3)return true;
        if (row > 1 && col < 7 && board[row - 2][col + 1] == 3)return true;
        if (row < 7 && col < 6 && board[row + 1][col + 2] == 3)return true;
        if (row < 6 && col < 7 && board[row + 2][col + 1] == 3)return true;
        if (row < 6 && col > 0 && board[row + 2][col - 1] == 3)return true;
        if (row < 7 && col > 1 && board[row + 1][col - 2] == 3)return true;
        if (row > 1 && col > 0 && board[row - 2][col - 1] == 3)return true;
        if (row > 0 && col > 1 && board[row - 1][col - 2] == 3)return true;

        if (row != 7 && board[row + 1][col] == 10)return true;
        if (row != 0 && board[row - 1][col] == 10)return true;
        if (col != 7 && board[row][col + 1] == 10) return true;
        if (col != 0 && board[row][col - 1] == 10) return true;
        if (row != 7 && col != 7 && board[row + 1][col + 1] == 10)return true;
        if (row != 7 && col != 0 && board[row + 1][col - 1] == 10) return true;
        if (row != 0 && col != 7 && board[row - 1][col + 1] == 10) return true;
        if (row != 0 && col != 0 && board[row - 1][col - 1] == 10) return true;

    }

    return false;
}

void Chess2::getdiagonalmoves(bool turn, int row, int col) {

    int a, b;
    if (turn) {
        a = row;
        b = col;
        if (a != 0 && b != 0) {
            for (;;) {
                a -= 1;
                b -= 1;
                if (board[a][b] > 0) break;
                if (board[a][b] < 0 || a == 0 || b == 0) {
                    pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
                    break;
                }
                if (!board[a][b])pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
            }
        }
        a = row;
        b = col;
        if (a != 0 && b != 7) {
            for (;;) {
                a -= 1;
                b += 1;
                if (board[a][b] > 0) break;
                if (board[a][b] < 0 || a == 0 || b == 7) {
                    pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
                    break;
                }
                if (!board[a][b])pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));

            }
        }
        a = row;
        b = col;
        if (a != 7 && b != 7) {
            for (;;) {
                a += 1;
                b += 1;
                if (board[a][b] > 0) break;
                if (board[a][b] < 0 || a == 7 || b == 7) {
                    pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
                    break;
                }
                if (!board[a][b])pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
            }
        }
        a = row;
        b = col;
        if (a != 7 && b != 0) {
            for (;;) {
                a += 1;
                b -= 1;
                if (board[a][b] > 0) break;
                if (board[a][b] < 0 || a == 7 || b == 0) {
                    pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
                    break;
                }
                if (!board[a][b])pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
            }
        }
    }
    else if (!turn) {

        a = row;
        b = col;
        if (a != 0 && b != 0) {
            for (;;) {
                a -= 1;
                b -= 1;
                if (board[a][b] < 0) break;
                if (board[a][b] > 0 || a == 0 || b == 0) {
                    pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
                    break;
                }
                if (!board[a][b])pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
            }
        }
        a = row;
        b = col;
        if (a != 0 && b != 7) {
            for (;;) {
                a -= 1;
                b += 1;
                if (board[a][b] < 0)
                    break;
                if (board[a][b] > 0 || a == 0 || b == 7) {
                    pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
                    break;
                }
                if (board[a][b] == 0)
                    pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));

            }
        }
        a = row;
        b = col;
        if (a != 7 && b != 7) {
            for (;;) {
                a += 1;
                b += 1;
                if (board[a][b] < 0) break;
                if (board[a][b] > 0 || a == 7 || b == 7) {
                    pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
                    break;
                }
                if (!board[a][b])pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
            }
        }
        a = row;
        b = col;
        if (a != 7 && b != 0) {
            for (;;) {
                a += 1;
                b -= 1;
                if (board[a][b] < 0) break;
                if (board[a][b] > 0 || a == 7 || b == 0) {
                    pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
                    break;
                }
                if (!board[a][b])pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
            }
        }

    }
}

void Chess2::getstraigtmoves(bool turn, int row, int col)
{
    int a, b;
    if (turn) {// white player
        a = row;
        b = col;
        if (a != 0) {
            for (;;) {
                a -= 1;
                if (board[a][b] > 0) break;
                if (board[a][b] < 0 || a == 0) {
                    pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
                    break;
                }
                if (!board[a][b]) pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
            }
        }
        a = row;
        b = col;
        if (a != 7) {
            for (;;) {
                a += 1;
                if (board[a][b] > 0) break;
                if (board[a][b] < 0 || a == 7) {
                    pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
                    break;
                }
                if (!board[a][b]) pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
            }
        }
        a = row;
        b = col;
        if (b != 0) {
            for (;;) {
                b -= 1;
                if (board[a][b] > 0) break;
                if (board[a][b] < 0 || b == 0) {
                    pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
                    break;
                }
                if (!board[a][b]) pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
            }
        }
        a = row;
        b = col;
        if (b != 7) {
            for (;;) {
                b += 1;
                if (board[a][b] > 0) break;
                if (board[a][b] < 0 || b == 7) {
                    pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
                    break;
                }
                if (!board[a][b]) pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
            }
        }
    }

    else if (!turn) // black player
    {
        a = row;
        b = col;
        if (a != 0) {
            for (;;) {
                a -= 1;
                if (board[a][b] < 0) break;
                if (board[a][b] > 0 || a == 0) {
                    pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
                    break;
                }
                if (!board[a][b]) pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
            }
        }
        a = row;
        b = col;
        if (a != 7) {
            for (;;) {
                a += 1;
                if (board[a][b] < 0) break;
                if (board[a][b] > 0 || a == 7) {
                    pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
                    break;
                }
                if (!board[a][b]) pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
            }
        }
        a = row;
        b = col;
        if (b != 0) {
            for (;;) {
                b -= 1;
                if (board[a][b] < 0) break;
                if (board[a][b] > 0 || b == 0) {
                    pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
                    break;
                }
                if (!board[a][b]) pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
            }
        }
        a = row;
        b = col;
        if (b != 7) {
            for (;;) {
                b += 1;
                if (board[a][b] < 0) break;
                if (board[a][b] > 0 || b == 7) {
                    pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
                    break;
                }
                if (!board[a][b]) pseudomoves.insert(pseudomoves.begin(),push(row, col, a, b));
            }
        }
    }
    //returnpseudomoves;
}

void Chess2::getknightmoves(bool turn, int row, int col) {

    if (turn) {

        if (row > 0 && col < 6 && board[row - 1][col + 2] <= 0) // one up two right
            pseudomoves.insert(pseudomoves.begin(),push(row, col, row - 1, col + 2));

        if (row > 1 && col < 7 && board[row - 2][col + 1] <= 0) // two up one right
            pseudomoves.insert(pseudomoves.begin(),push(row, col, row - 2, col + 1));

        if (row < 7 && col < 6 && board[row + 1][col + 2] <= 0) // one down two right
            pseudomoves.insert(pseudomoves.begin(),push(row, col, row + 1, col + 2));

        if (row < 6 && col < 7 && board[row + 2][col + 1] <= 0) // two down one right
            pseudomoves.insert(pseudomoves.begin(),push(row, col, row + 2, col + 1));

        if (row < 6 && col > 0 && board[row + 2][col - 1] <= 0) //two down one left
            pseudomoves.insert(pseudomoves.begin(),push(row, col, row + 2, col - 1));

        if (row < 7 && col > 1 && board[row + 1][col - 2] <= 0) // one down two left
            pseudomoves.insert(pseudomoves.begin(),push(row, col, row + 1, col - 2));

        if (row > 1 && col > 0 && board[row - 2][col - 1] <= 0) // two up one left
            pseudomoves.insert(pseudomoves.begin(),push(row, col, row - 2, col - 1));

        if (row > 0 && col > 1 && board[row - 1][col - 2] <= 0) // one up two left
            pseudomoves.insert(pseudomoves.begin(),push(row, col, row - 1, col - 2));
    }

    else if (!turn) {
        if (row > 0 && col < 6 && board[row - 1][col + 2] >= 0)pseudomoves.insert(pseudomoves.begin(),push(row, col, row - 1, col + 2));
        if (row > 1 && col < 7 && board[row - 2][col + 1] >= 0)pseudomoves.insert(pseudomoves.begin(),push(row, col, row - 2, col + 1));
        if (row < 7 && col < 6 && board[row + 1][col + 2] >= 0)pseudomoves.insert(pseudomoves.begin(),push(row, col, row + 1, col + 2));
        if (row < 6 && col < 7 && board[row + 2][col + 1] >= 0)pseudomoves.insert(pseudomoves.begin(),push(row, col, row + 2, col + 1));
        if (row < 6 && col > 0 && board[row + 2][col - 1] >= 0)pseudomoves.insert(pseudomoves.begin(),push(row, col, row + 2, col - 1));
        if (row < 7 && col > 1 && board[row + 1][col - 2] >= 0)pseudomoves.insert(pseudomoves.begin(),push(row, col, row + 1, col - 2));
        if (row > 1 && col > 0 && board[row - 2][col - 1] >= 0)pseudomoves.insert(pseudomoves.begin(),push(row, col, row - 2, col - 1));
        if (row > 0 && col > 1 && board[row - 1][col - 2] >= 0)pseudomoves.insert(pseudomoves.begin(),push(row, col, row - 1, col - 2));
    }

    //returnpseudomoves;
}

void Chess2::getpawnmoves(bool turn, int row, int col) {
    if (turn) {
        if (row == 0){
            return ;
        }
        if (row == 6 && board[row - 1][col] == 0 && board[row - 2][col] == 0)
            pseudomoves.insert(pseudomoves.begin(),push(row, col, row - 2, col));
        if (board[row - 1][col] == 0)
            pseudomoves.insert(pseudomoves.begin(),push(row, col, row - 1, col));
        if (col != 0 && board[row - 1][col - 1] < 0)
            pseudomoves.insert(pseudomoves.begin(),push(row, col, row - 1, col - 1));
        if (col != 7 && board[row - 1][col + 1] < 0)
            pseudomoves.insert(pseudomoves.begin(),push(row, col, row - 1, col + 1));
    }

    else if (!turn) {
        if (row == 7){
            return ;
        }
        if (row == 1 && board[row + 1][col] == 0 && board[row + 2][col] == 0){
            pseudomoves.insert(pseudomoves.begin(),push(row, col, row + 2, col));
        }
        if (board[row + 1][col] == 0)
            pseudomoves.insert(pseudomoves.begin(),push(row, col, row + 1, col));
        if (col != 0 && board[row + 1][col - 1] > 0)
            pseudomoves.insert(pseudomoves.begin(),push(row, col, row + 1, col - 1));
        if (col != 7 && board[row + 1][col + 1] > 0)
            pseudomoves.insert(pseudomoves.begin(),push(row, col, row + 1, col + 1));
    }

    //returnpseudomoves;
}

void Chess2::getkingmoves(bool turn, int row, int col) {

    if (!turn) {
        if (row != 7 && board[row + 1][col] >= 0) pseudomoves.insert(pseudomoves.begin(),push(row, col, row + 1, col));
        if (row != 0 && board[row - 1][col] >= 0) pseudomoves.insert(pseudomoves.begin(),push(row, col, row - 1, col));
        if (col != 7 && board[row][col + 1] >= 0) pseudomoves.insert(pseudomoves.begin(),push(row, col, row, col + 1));
        if (col != 0 && board[row][col - 1] >= 0) pseudomoves.insert(pseudomoves.begin(),push(row, col, row, col - 1));
        if (row != 7 && col != 7 && board[row + 1][col + 1] >= 0) pseudomoves.insert(pseudomoves.begin(),push(row, col, row + 1, col + 1));
        if (row != 7 && col != 0 && board[row + 1][col - 1] >= 0) pseudomoves.insert(pseudomoves.begin(),push(row, col, row + 1, col - 1));
        if (row != 0 && col != 7 && board[row - 1][col + 1] >= 0) pseudomoves.insert(pseudomoves.begin(),push(row, col, row - 1, col + 1));
        if (row != 0 && col != 0 && board[row - 1][col - 1] >= 0) pseudomoves.insert(pseudomoves.begin(),push(row, col, row - 1, col - 1));
    }
    else if (turn) {
        if (row != 7 && board[row + 1][col] <= 0) pseudomoves.insert(pseudomoves.begin(),push(row, col, row + 1, col));
        if (row != 0 && board[row - 1][col] <= 0) pseudomoves.insert(pseudomoves.begin(),push(row, col, row - 1, col));
        if (col != 7 && board[row][col + 1] <= 0) pseudomoves.insert(pseudomoves.begin(),push(row, col, row, col + 1));
        if (col != 0 && board[row][col - 1] <= 0) pseudomoves.insert(pseudomoves.begin(),push(row, col, row, col - 1));
        if (row != 7 && col != 7 && board[row + 1][col + 1] <= 0) pseudomoves.insert(pseudomoves.begin(),push(row, col, row + 1, col + 1));
        if (row != 7 && col != 0 && board[row + 1][col - 1] <= 0) pseudomoves.insert(pseudomoves.begin(),push(row, col, row + 1, col - 1));
        if (row != 0 && col != 7 && board[row - 1][col + 1] <= 0) pseudomoves.insert(pseudomoves.begin(),push(row, col, row - 1, col + 1));
        if (row != 0 && col != 0 && board[row - 1][col - 1] <= 0) pseudomoves.insert(pseudomoves.begin(),push(row, col, row - 1, col - 1));
    }
    //returnpseudomoves;
}


int Chess2::evaluation() {
    const short int pawn = 95,bishop = 330,knight = 320,rook = 500,queen = 900,king = 2000;
    const int pawnt[8][8] = {
     {0,  0,  0,  0,  0,  0,  0,  0},
    {50, 50, 50, 50, 50, 50, 50, 50},
    {10, 10, 20, 30, 30, 20, 10, 10},
     {5,  5, 10, 45, 45, 10,  5,  5},
     {0,  0,  0, 20, 20,  0,  0,  0},
    {5, -5,-10,  0,  0,-10, -5,  5},
    {5, 10, 10,-20,-20, 10, 10,  5},
    {0,  0,  0,  0,  0,  0,  0,  0}
    };

    const int bishopt[8][8] = {
        {-20,-10,-10,-10,-10,-10,-10,-20},
        {-10,  0,  0,  0,  0,  0,  0,-10},
        {-10,  0,  5, 10, 10,  5,  0,-10},
        {-10,  5,  5, 10, 10,  5,  5,-10},
        {-10,  0, 10, 10, 10, 10,  0,-10},
        {-10, 10, 10, 10, 10, 10, 10,-10},
        {-10,  5,  0,  0,  0,  0,  5,-10},
        {-20,-10,-10,-10,-10,-10,-10,-20},
    };

    const int knightt[8][8] = {
    {-50,-40,-30,-30,-30,-30,-40,-50},
    {-40,-20,  0,  0,  0,  0,-20,-40},
    {-30,  0, 10, 15, 15, 10,  0,-30},
    {-30,  5, 15, 20, 20, 15,  5,-30},
    {-30,  0, 15, 20, 20, 15,  0,-30},
    {-30,  5, 10, 15, 15, 10,  5,-30},
    {-40,-20,  0,  5,  5,  0,-20,-40},
    {-50,-40,-30,-30,-30,-30,-40,-50},
    };

    const int queent[8][8] = {
        {-20,-10,-10, -5, -5,-10,-10,-20},
        {-10,  0,  0,  0,  0,  0,  0,-10},
        {-10,  0,  5,  5,  5,  5,  0,-10},
         {-5,  0,  5,  5,  5,  5,  0, -5},
          {0,  0,  5,  5,  5,  5,  0, -5},
        {-10,  5,  5,  5,  5,  5,  0,-10},
        {-10,  0,  5,  0,  0,  0,  0,-10},
        {-20,-10,-10, -5, -5,-10,-10,-20}
    };
    const int kingt[8][8] = {
        {-30,-40,-40,-50,-50,-40,-40,-30},
        {-30,-40,-40,-50,-50,-40,-40,-30},
        {-30,-40,-40,-50,-50,-40,-40,-30},
        {-30,-40,-40,-50,-50,-40,-40,-30},
        {-20,-30,-30,-40,-40,-30,-30,-20},
        {-10,-20,-20,-20,-20,-20,-20,-10},
        {20, 20,  0,  0,  0,  0, 20, 20},
        {20, 30, 10,  0,  0, 10, 30, 20 },
    };
    const int rookt[8][8] = {
      {0,  0,  0,  0,  0,  0,  0,  0},
      {5, 10, 10, 10, 10, 10, 10,  5},
     {-5,  0,  0,  0,  0,  0,  0, -5},
     {-5,  0,  0,  0,  0,  0,  0, -5},
     {-5,  0,  0,  0,  0,  0,  0, -5},
     {-5,  0,  0,  0,  0,  0,  0, -5},
     {-5,  0,  0,  0,  0,  0,  0, -5},
      {0,  0,  0,  5,  5,  0,  0,  0}
    };
    int score = 0;

    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            if (!board[i][j]) continue;
            if (board[i][j] == 1) {
                score-=pawnt[i][j];
                score -= pawn;
                if (board[i-1][j] == 1) // double stacked pawn
                    score-=20;
            }
            else if (board[i][j] == 2){
                score-=bishopt[i][j];
                score -= bishop;
            }
            else if (board[i][j] == 3){
                score-=knightt[i][i];
                score -= knight;
            }
            else if (board[i][j] == 5){
                score-=rookt[i][j];
                score -= rook;
            }
            else if (board[i][j] == 6){
                score-=queent[i][j];
                score -= queen;
            }
            else if (board[i][j] == 10){
                score-=kingt[i][j];
                score -= king;
            }
             if (board[i][j] == -1) {
                score+=pawnt[7-i][7-j];
                score+= pawn;
            }
            else if (board[i][j] == -2){
                score+=bishopt[7-i][7-j];
                score+= bishop;
            }
            else if (board[i][j] == -3){
                score+=knightt[7-i][7-j];
                score+= knight;
            }
            else if (board[i][j] == -5){
                score+=rookt[7-i][7-j];
                score+= rook;
            }
            else if (board[i][j] == -6){
                score+=queent[7-i][7-j];
                score+= queen;
            }
            else if (board[i][j] == -10){
                score+=kingt[7-i][7-j];
                score+= king;
            }

        }
    }

    return score;
}

int Chess2::miniMax(int depth, bool ismax, int alpha, int beta) {
    if (depth == 0) {
        return evaluation();
    }
    int maxeval = -999999;
    int mineval = 999999;
    buff possiblemoves;
    int original;
    int eval;
    if (ismax == true) {
        possiblemoves = getallmoves(false);
        if (possiblemoves.size() == 0 && check(false) == false) {
            return 999999;
        }
        if (possiblemoves.size() == 0 && check(false) == true) {
            return -999999;
        }
        for (std::string i:possiblemoves) {
            original = perform(i);
            eval = miniMax(depth - 1, false, alpha, beta);
            undomove(original, i);
            if (eval > maxeval)
                maxeval = eval;
            if (alpha >= eval)
                alpha = eval;
            if (beta <= alpha)
                break;
        }
        return maxeval;
    }
    else {
        possiblemoves = getallmoves(true);
        if (possiblemoves.size() == 0 && check(true) == false){
            return -99999999;
        }
        if (possiblemoves.size() == 0 && check(true) == true){
            return 99999999;
        }
        else if (possiblemoves.size() == 0 && check(true) == false){
            return -99999999;
        }
        for (std::string i:possiblemoves) {
            original = perform(i);
            eval = miniMax(depth - 1, true, alpha, beta);
            undomove(original, i);
            if (eval < mineval)
                mineval = eval;
            if (beta <= eval)
                beta = eval;
            if (beta <= alpha)
                break;
        }
        return mineval;
    }
    return 1;
}

str Chess2::miniMaxroot(int depth, bool turn) {
    str bestmove;
    int maxeval = -9999999;
    buff allmoves = getallmoves(turn);
    int original;
    int eval;
    for (std::string i:allmoves) {
        original = perform(i);
        eval = miniMax(depth - 1, false, -99999999, 99999999);
        std::cout << "Move: " << i << ' ' << "Points: " << eval << '\n';
        undomove(original, i);
        if (eval > maxeval) {
            maxeval = eval;
            bestmove = i;
        }
    }
    return bestmove;
}
void Chess2::undomove(int original, str Move) {
    board[Move[0] - 48][Move[1] - 48] = board[Move[2] - 48][Move[3] - 48]; // -48 is to convert char to int
    board[Move[2] - 48][Move[3] - 48] = original; // -48 to convert char to int
}

Here is what a move would look like "1030". the first two characters are the co-ordinates of a piece. The last two characters are the co-ordinates to where that piece should move.

Is this the best container choice for my purpose? How can I optimize this program? mainly the generator functions and the minimax algorithm

\$\endgroup\$
28
\$\begingroup\$

About using typedefs

First, don't create aliases for standard types. Just write std::string instead of str. For someone reading your code, or perhaps you yourself reading your own code half a year later, whenever one reads str one wonders "is this a std::string or some other kind of string?"

Furthermore, it is not good practice to introduce very generic names such as buff in the global namespace. Move that typedef into class Chess2. Also consider giving it a name that makes it more clear that it is a type, not a variable, for example use buffer_type.

Also, when you do declare a typedef, make sure you use it consistently.

Use a consistent way to write names

I see pseudomoves, legal_moves and miniMax. Be consistent and use one way to write variable and function names that might contain multiple words. I suggest you write function and variable names with all lower case characters, and separate individual words with an underscore. So:

  • pseudomoves -> pseudo_moves
  • getallmoves() -> get_all_moves()
  • checkmatewhite -> checkmate_white
  • ...and so on.

Avoid magic numbers

I see lots of code like if (board[i][j] == -6) {...}. What does -6 mean? Why is it negative? This makes the code really hard to understand. Of course you need to store the type of chess piece somehow, and a computer likes simple integers best, but in a programming language we can give those integers human readable names. So in C++, the best thing to do is create an enum class, like so:

class Chess2
{
    enum class Piece: signed char {
       EMPTY = 0,
       BLACK_PAWN = 1,
       BLACK_BISHOP = 2,
       ...
       WHITE_PAWN = -1,
       WHITE_BISHOP = -2,
       ...
    };

    Piece board[8][8] = {
        {WHITE_ROOT, EMPTY, EMPTY, ...},
        ...
    };
};

And in your code you can now write:

if (board[i][j] == Piece::WHITE_QUEEN) {...}

Note that I made the underlying type a signed char, since it is big enough to handle all possible chess pieces. Also, if the actual value doesn't really matter, you can omit them from the enum declaration. You will need to type a bit more, but in the end your code will be much more legible.

Similar to pieces, you made turn a boolean. But what does it mean that a turn is true? Again just use an enum class to make it explicit:

enum class Color {
    WHITE;
    BLACK;
};

And then use Color turn instead of bool turn everywhere.

Don't encode moves as strings

Strings are not the best way to store moves. A std::string is a large object and it might perform memory allocations. With the short string optimization technique commonly used in the standard libraries nowadays, you will not have an issue with memory allocations, but a string of only a few characters will still take about 32 bytes on a 64-bit machine. Also, lets look at your code:

board[Move[2] - 48][Move[3] - 48] = board[Move[0] - 48][Move[1] - 48];

That just looks terrible. Again there is no way to tell what the array indices mean just by looking at this line. And why do you need to subtract 48? Ideally, you want to create a class Position to encode a position on the chess board, and a class Move to encode a move. Both should be declared inside class Chess2. For example:

class Chess2 {
    class Position {
        unsigned char row;
        unsigned char col;
    };

    class Move {
        Position from;
        Position to;
    };

    std::vector<Move> pseudo_moves;
    std::vector<Move> legal_moves;
    ...
};

There are other ways to encode a position, for example you could store it in a single 8-bit integer if you enumerate all the positions from 0 to 63. But now that you have created a class for this, it will be much easier to change. Now you can use it like:

Piece Chess2::perform(Move move) {
    Piece original = board[move.to.row][move.to.col];
    board[move.to.row][move.to.col] = board[move.from.row][move.from.col];
    board[move.from.row][move.from.col] = Piece::EMPTY;
    return original;
}

Still very verbose, but at least now I can actually understand much better what is going on. But that brings me to:

Create a class to represent a chess board

Instead of declaring a two-dimensional array for the board and manipulating it directly, consider creating a class Board that contains helper functions to make manipulating the board easier. For example:

class Board {
    std::array<std::array<Piece, 8>, 8> squares;

public:
    Board(const std::array<std::array<Piece, 8>, 8> &initial_state): squares(initial_state) {}
    Piece &operator[](Position pos) {
        return squares[pos.row][pos.col];
    }
};

With this, you can now access the chess board as an array but using a Position as the array index. And perform() now simplifies to:

Piece Chess2::perform(Move move) {
    Piece original = board[move.to];
    board[move.to] = board[move.from];
    board[move.from] = Piece::EMPTY;
    return original;
}

More code improvements

There are many more improvements you could make to make your code more readable. For example, you could create an iterator class for Board so that instead of:

for (int i = 0; i < 8; i++) {
     for (int j = 0; j < 8; j++) {
         if (board[i][j] == 1) getpawnmoves(true, i, j)
         ...

You could write:

for (auto &[piece, pos]: board) {
    if (piece == Piece::BLACK_PAWN) get_pawn_moves(Color::BLACK, pos);
    ...

But this will take a bit of time, especially if you are not used to writing such code. However, while it has an up-front cost, it will pay off in the long run.

Avoid inserting at the start of a std::vector

Inserting something at the start of a std::vector is an expensive operation, since it has to move all elements one place. Either ensure you always push_back() elements, and reverse the order in which you iterator over pseudo_move(), or use a std::deque to store pseudo_moves, as it has an efficient push_front() operation.

Avoid code duplication

There is a lot of repetition in your code. Try to avoid this as much as possible. For example, you duplicate a lot of code for black and white turns. Find some way to generalize away the difference between black and white to avoid if (turn) ... else ... blocks. For example, take getdiagonalmoves(), where the only difference between the black and white turns is whether you write board[a][b] > 0 or board[a][b] < 0. Create a function to check if a given piece has a given color:

bool has_color(Piece piece, Color color) {
    // Make use of the fact that black pieces have a positive enum value
    if (color == COLOR_BLACK)
        return static_cast<unsigned char>(piece) > 0;
    else
        return static_cast<unsigned char>(piece) < 0;
}

Then in getdiagonalmoves(), you can write:

void Chess2::get_diagonal_moves(Color turn, Position from) {
    Color opponent = turn == Color::BLACK ? Color::WHITE : Color::BLACK;
    Position to = from;

    while (to.row != 0 && to.col != 0) {
        to.row--;
        to.pos--;
        if (has_color(board[to], turn)) break;
        if (has_color(board[to], opponent) || to.row == 0 || to.col == 0) {
            ...

Alternatively, make it even clearer what you are actually trying to check, and create a function to check if a destination square is a valid position for a piece of a given color, so you can write something like:

        if (is_valid_destination(to, turn))
            pseudo_moves.push_front({from, to});

Not only does this remove code duplication, removing if-statements might also remove branches from the code, which reduces the chance of branch mispredictions.

Another possibility to remove code duplication is to separate the constant part from the variables that do change. For example, in getknightmoves(), separate the 8 possible directions of a knight from the check whether a night can move in a possible direction, like so:

void Chess2::getknightmoves(Color turn, Position from) {
    static const struct Direction {
        signed char row;
        signed char col;
    } knight_moves[8] = {
        {-1, +2},
        {-2, +1},
        ...
    };

    for (auto dir: knight_moves) {
        Position to = {from.col + dir.col, from.row + dir.row};
        if (to.col < 8 && to.row < 8 && is_valid_destination(to, turn))
            pseudo_moves.push_front({from, to});
    }
}

You can do something similar for getkingmoves(), and even for the four directions of getstraightmoves() and getdiagonalmoves(). Also note that in check() you have very similar code that could also be shortened in the same way.

Consider keep track of the positions of the kings

You call check() a lot of times, and the first thing it does is to scan all the tiles of a chess board to find the position of a king. Consider storing the positions of the kings in separate variables in class Board. Of course, you now have to be a bit careful about keeping those variables up to date.

Optimize storage of state

As mentioned in S. Delsad's answer, a better way to store the board might be to use bitboards. This is particularly efficient on today's computers, since 64 squares on a chess board is a perfect fit for the 64-bit registers most processors have.

Another potential optimization is how to store positions. Instead of a separate row and column, consider storing a single integer, and enumerate the squares going from left to right first and then continue on from top to bottom. This also makes it easier to calculate desination positions. For example, a knight might move 2 squares right and 1 square down, but with the above enumeration, it just means adding 10 to the index (2 for going two squares right, plus 8 to go one row down).

Lastly, instead of storing the state of all 64 squares of a board, consider storing the position of the 32 chess pieces instead. When checking if a king is checked, you then for example only have to visit all the pieces of the opposite color, and then for example for a bishop, check if they are on the same diagonal (absolute difference in row and column position is identical), and if so you just need to check if there is no piece inbetween. This can potentially speed up this test a lot, especially in the end game when many pieces have already been removed.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ A lot of things to improve!, I would like to note one thing, the duplication part that you talked about, during the development process I did think about it for a whole day but I couldn't find any way where it would be easy for me to perform the same thing without duplicating to an extent. \$\endgroup\$ – Aryan Parekh Sep 6 at 11:33
  • 1
    \$\begingroup\$ Small note: use using instead of typedefs if you decide to use typedef anyways. It reads so much better! \$\endgroup\$ – val says Reinstate Monica Sep 6 at 17:43
  • \$\begingroup\$ Isn't it just the arcane naming of turn that invites use of an enum? If it was called white_to_move seems like a bool would be perfectly fine... \$\endgroup\$ – Will Sep 9 at 13:29
  • \$\begingroup\$ @Will Yes, ensuring the name of the variable fits a boolean true/false value would be a solution as well. But maybe even better is Color player_to_move. \$\endgroup\$ – G. Sliepen Sep 9 at 13:51
9
\$\begingroup\$

In my opinion, the best way to improve this program is by using bitboards. Instead of using a table in two dimensions to represent the chess board, you use 12 numbers of 64 bits, each number representing a type of piece and each bit saying whether there's a piece or not on a square. You can then use bitwise operators to modify the chessboard. This method is much more complex, but generating legal moves becomes 8'000 times faster (I can say that because I already tried using a 2D table and bitboards in a chess project). With this improvement, you can easily reach a depth of 5 in your minimax.

If you're looking for something easier that could also have a great impact on the performance of the minimax, use lookup tables. It is a table that knows lots of different board positions that have already been faced by professionals. You can modify your evaluation function to use this table to give more importance to moves made by professionals. To use less memory space, you can hash the chessboards (see hash tables).

Finally, all the articles I read give 9 points to the queen instead of 6. You can also set the value of the king to infinite (or a very high value). Apart from that, I advise you to use OpenMP library to multi-thread the minimax. This library is very easy to use (one line of code on top of a loop) and works well. Also, be sure to use -O2 or -O3 option if you compile your code with gcc.

I hope this answers your questions.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Updtate, I did use bitboards. I did spend nights going through hundreds of articles again and again. Today after I finished the generation of queen moves. I compared old and new. the old code took 13.458 seconds for 10,000. The new code took.....0.048 seconds. Yeah bitboards are fast \$\endgroup\$ – Aryan Parekh Sep 14 at 17:02

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.