C++ generator function for a Chess game

Question

Here is my code for a move generator function for a chess engine. It's currently working perfectly and returning fully legal moves. How can i improve it.

I am looking to improve this generator function and make it more efficient Any help is appreciated!

#include <iostream>
#include <vector>

using std::cout;
using std::cin;
using std::endl;
using std::vector;
int board[8][8] = {
  {-5,-3,-2,-6,-10,-2,-3,-5},
  {-1,-1,-1,-1,-1,-1,-1,-1},
  {0,0,0,0,0,0,0,0},
  {0,0,0,0,0,0,0,0},
  {0,0,0,0,0,0,0,0},
  {0,0,0,0,0,0,0,0},
  {1,1,1,1,1,1,1,1},
  {5,3,2,6,10,2,3,5},
};
bool check_w(){
    int row;
    int col;
    bool found = false;
    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;
            }
        }
    }
    if (found == false){
        cout << "There is no white king on the board " << endl;
        return false;
    }
    if (row != 0 && col != 0 && board[row-1][col-1] == -1) return true;
    if (row != 0 && col != 7 && board[row-1][col+1] == -1) return true;
    int a;
    int b;
    a = row;
    if (row != 7){
        for (;;){
            a+=1;
            if(board[a][col] == -5 || board[a][col] == -6) return true;
            if (a == 7 || board[a][col] != 0) break;
        }
    }
    a = row;
    if (row != 0){
        for (;;){
            a-=1;
            if(board[a][col] == -5 || board[a][col] == -6) return true;
            if (a == 0 || board[a][col] != 0) break;
        }
    }
    b = col;
    if (col != 0){
        for (;;){
            b-=1;
            if (board[row][b] == -6 or board[row][b] == -5) return true;
            if(b == 0 || board[row][b] != 0) break;
        }
    }
    b = col;
    if (col != 7){
        for (;;){
            b+=1;
            if (board[row][b] == -6 or board[row][b] == -5) return true;
            if(b == 7 || board[row][b] != 0) break;
        }
    }
    a = row;
    b = col;
    if (a != 0 && b != 0){
        for (;;){
            a-=1;
            b-=1;
            if (board[a][b] == -6 or board[a][b] == -2) return true;
            if(b == 0  || a == 0 || board[a][b] != 0) break;
        }
    }
    a = row;
    b = col;
    if (a != 0 && b != 7){
        for (;;){
            a-=1;
            b+=1;
            if (board[a][b] == -6 or board[a][b] == -2) return true;
            if(b == 7  || a == 0 || board[a][b] != 0) break;
        }
    }
    a = row;
    b = col;
    if (a != 7 && b != 0){
        for (;;){
            a+=1;
            b-=1;
            if (board[a][b] == -6 or board[a][b] == -2) return true;
            if(b == 0  || a == 7 || board[a][b] != 0) break;
        }
    }
    a = row;
    b = col;
    if (a != 7 && b != 7){
        for (;;){
            a+=1;
            b+=1;
            if (board[a][b] == -6 or board[a][b] == -2) return true;
            if(b == 7  || a == 7 || board[a][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 > 1 && col > 0 && board[row-2][col-1] == -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 != 0 && 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 != 7 && col != 0 && board[row+1][col-1] == 10) return true;
    if (row != 7 && col != 0 && board[row+1][col+1] == 10) return true;
    return false;
}

vector<int> push(int row,int col,int desrow,int descol){
    vector<int> move;
    move.push_back(row);
    move.push_back(col);
    move.push_back(desrow);
    move.push_back(descol);
    return move;
}

void undomove(int original,vector<int> Move){
    board[Move[0]][Move[1]] = board[Move[2]][Move[3]];
    board[Move[2]][Move[3]] = original;
}

int perform(vector<int> Move){
    int original;
    original = board[Move[2]][Move[3]];
    board[Move[2]][Move[3]] = board[Move[0]][Move[1]];
    board[Move[0]][Move[1]] = 0;
    return original;
}

vector<vector<int>> generate_moves_w(){
    vector<vector<int>> pseudomoves,legal_moves;
    vector<int> move;
    int original,a,b;
    for(int row = 0; row < 8; row++){
        for(int col = 0;col < 8;col++){
            if (!board[row][col]) continue;
            if (board[row][col] == 1 && row != 0){
                if (row == 6 && board[row-1][col] == 0 && board[row-2][col] == 0)
                    pseudomoves.push_back(push(row,col,row-2,col));
                if (board[row-1][col] == 0)
                    pseudomoves.push_back(push(row,col,row-1,col));
                if (col != 0 && board[row-1][col-1] < 0)
                    pseudomoves.push_back(push(row,col,row-1,col-1));
                if (col != 7 && board[row-1][col+1] < 0)
                    pseudomoves.push_back(push(row,col,row-1,col+1));
            }
            else if (board[row][col] == 5){
                a = row;
                b = col;
                if (a != 0){
                    for (;;){
                        a-=1;
                        if (board[a][b] > 0) break;
                        if (board[a][b] < 0 || a == 0){
                            pseudomoves.push_back(push(row,col,a,b));
                            break;
                        }
                        if(!board[a][b]) pseudomoves.push_back(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.push_back(push(row,col,a,b));
                            break;
                        }
                        if(!board[a][b]) pseudomoves.push_back(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.push_back(push(row,col,a,b));
                            break;
                        }
                        if(!board[a][b]) pseudomoves.push_back(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.push_back(push(row,col,a,b));
                            break;
                        }
                        if(!board[a][b]) pseudomoves.push_back(push(row,col,a,b));
                    }
                }

            }
            else if (board[row][col] == 3){
                if (row > 0 && col < 6 && board[row-1][col+2] <= 0)pseudomoves.push_back(push(row,col,row-1,col+2));
                if (row > 1 && col < 7 && board[row-2][col+1] <= 0)pseudomoves.push_back(push(row,col,row-2,col+1));
                if (row < 7 && col < 6 && board[row+1][col+2] <= 0)pseudomoves.push_back(push(row,col,row+1,col+2));
                if (row < 6 && col < 7 && board[row+2][col+1] <= 0)pseudomoves.push_back(push(row,col,row+2,col+1));
                if (row < 6 && col > 0 && board[row+2][col-1] <= 0)pseudomoves.push_back(push(row,col,row+2,col-1));
                if (row < 7 && col > 1 && board[row+1][col-2] <= 0)pseudomoves.push_back(push(row,col,row+1,col-2));
                if (row > 1 && col > 0 && board[row-2][col-1] <= 0)pseudomoves.push_back(push(row,col,row-2,col-1));
                if (row > 0 && col > 1 && board[row-1][col-2] <= 0)pseudomoves.push_back(push(row,col,row-1,col-2));
            }
            else if (board[row][col] == 2){
                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.push_back(push(row,col,a,b));
                            break;
                        }
                        if(!board[a][b])pseudomoves.push_back(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.push_back(push(row,col,a,b));
                            break;
                        }
                        if(!board[a][b])pseudomoves.push_back(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.push_back(push(row,col,a,b));
                            break;
                        }
                        if(!board[a][b])pseudomoves.push_back(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.push_back(push(row,col,a,b));
                            break;
                        }
                        if(!board[a][b])pseudomoves.push_back(push(row,col,a,b));
                }
                }
        }
            else if (board[row][col] == 6){
                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.push_back(push(row,col,a,b));
                            break;
                        }
                        if(!board[a][b])pseudomoves.push_back(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.push_back(push(row,col,a,b));
                            break;
                        }
                        if(!board[a][b])pseudomoves.push_back(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.push_back(push(row,col,a,b));
                            break;
                        }
                        if(!board[a][b])pseudomoves.push_back(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.push_back(push(row,col,a,b));
                            break;
                        }
                        if(!board[a][b])pseudomoves.push_back(push(row,col,a,b));
                }
                }
                a = row;
                b = col;
                if (a != 0){
                    for (;;){
                        a-=1;
                        if (board[a][b] > 0) break;
                        if (board[a][b] < 0 || a == 0){
                            pseudomoves.push_back(push(row,col,a,b));
                            break;
                        }
                        if(!board[a][b]) pseudomoves.push_back(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.push_back(push(row,col,a,b));
                            break;
                        }
                        if(!board[a][b]) pseudomoves.push_back(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.push_back(push(row,col,a,b));
                            break;
                        }
                        if(!board[a][b]) pseudomoves.push_back(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.push_back(push(row,col,a,b));
                            break;
                        }
                        if(!board[a][b]) pseudomoves.push_back(push(row,col,a,b));
                    }
                }

            }
            else if (board[row][col] == 10){
                if (row != 7 && board[row+1][col] <= 0)pseudomoves.push_back(push(row,col,row+1,col));
                if (row != 0 && board[row-1][col] <= 0)pseudomoves.push_back(push(row,col,row-1,col));
                if (col != 7 && board[row][col+1] <= 0)pseudomoves.push_back(push(row,col,row,col+1));
                if (col != 0 && board[row][col-1] <= 0)pseudomoves.push_back(push(row,col,row,col-1));
                if(row != 0 && col!= 0 && board[row-1][col-1] <= 0)pseudomoves.push_back(push(row,col,row-1,col-1));
                if(row != 0 && col!= 7 && board[row-1][col+1] <= 0)pseudomoves.push_back(push(row,col,row-1,col+1));
                if(row != 7 && col!= 0 && board[row+1][col-1] <= 0)pseudomoves.push_back(push(row,col,row+1,col-1));
                if(row != 7 && col!= 7 && board[row+1][col+1] <= 0)pseudomoves.push_back(push(row,col,row+1,col+1));
            }
        }//col loop
    }//row loop
    for (long unsigned int i = 0; i < pseudomoves.size(); i++){
        original = perform(pseudomoves[i]);
        if (check_w() == false) legal_moves.push_back(pseudomoves[i]);
        undomove(original,pseudomoves[i]);
    }
    return legal_moves;
}

int main(){
vector<vector<int>> legal_moves = generate_moves_w();
for (unsigned long int i = 0;i < legal_moves.size();i++) cout << legal_moves[i][0] << " " <<  legal_moves[i][1] << " " <<  legal_moves[i][2] << " " <<  legal_moves[i][3] << endl;
return 0;
}

The board is represented by an 8x8 integer array and the pieces are represented with numbers. Black pieces are negative of the same values white pieces use.

• pawn - 1
• bishop - 2
• rook - 5
• knight - 3
• queen - 6
• king - 10

A 0 in a place means that the position is empty. No piece is on it.

I have not added pawn promotion,en passant, and castle.

This is how the generator function works:

There are two main loops, outer loop for iterating through each row, inner loop for iterating through each column in each row. When I start iterating, if I find a 0, I skip the iteration. Hence, if(!board[row][col]) continue;

If i do find piece, a set of if statements check which piece it is, and accordingly add a vector of a possible move in the format [initial row, initial column, desired row,desired column]

After I generate all the moves, that means after it exits the loops, i need to iterate through all of them once again to validate them. Because if a piece was protecting a king from a check, it cannot be moved. I use the functions i have defined, which are perform() and undomove() to perform each move in the vector, add it to a new vector called legal_moves only IF the function check() returns false. this process returns a set of fully legal moves. However i wish to optimize it as i can perform this well over 50,000 times in a chess engine

MY LOGIC BEHIND GENERATING MOVES FOR EACH PIECE

• Pawn: A pawn has only a few conditions, so i didn't use any loops. Just hard code. I dont generate any moves for the pawn if the row in the loop is 7. Because it cannot move front. If it can however. I check whether board[row+1][col] is 0. If yes then i add it to pseudomoves by performing this function pseudomoves.push_back(push(row,col,row-1,col));. This statement is applicable to all. The first two arguments are co-ordinates of the initial position. Second two are co-ordinates of the desired position. For pawn i also check whether an enemy piece is available diagonally.

• Bishop: The moves of the bishop is done simply by using ** 4 loops ** Each loop for a direction it can move. Let's say i want to generate its moves top left. That means rows decreasing and col decreasing. I enter an infinite loop in which at each iteration. The increment/decrement happens(according to the direction). If at the new position i find a 0. I add it to pseudomoves and continue. If i find my own piece or if an edge has been reached, I break out of the loop. Lastly if I find an opponent's piece, add it to pseudomoves and then break , as it counts as a possible position. This same logic applies for all directions.

• Rook:

Same logic as bishop

• Queen:

moves of rook + moves of bishop

• King: total 8 directions in which the king can move. If the position is empty or has an opponents piece, add it to pseudomoves and check the next direction.

• Knight: Easiest out of all. At max 8 possible moves of the knight. Just increments and decrements in row and column. If the position is empty or has an opponents piece, add it to pseudomoves and check the next direction.

Answer 1

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

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid.

Provide complete code to reviewers

This is not so much a change to the code as a change in how you present it to other people. Without the full context of the code and an example of how to use it, it takes more effort for other people to understand your code. This affects not only code reviews, but also maintenance of the code in the future, by you or by others. One good way to address that is by the use of comments. Another good technique is to include test code showing how your code is intended to be used.

Reconsider container choices

A std::vector<std::vector<int>> is not likely to be an optimal choice for your data structure. Because a chess move, in this code is actually two pairs of coordinates (source and destination), I'd suggest that either a std::array or a custom type. A class representing a board location would be very handy for a number of things, as I'll demonstrate later. Finally rather than int board[8][8] a choice that would be just as efficient but would allow better use of standard algorithms would be std::array<int, 64> or better yet, make it a class.

Use more whitespace for legibility

The code contains this terribly long line:

if(row != 7 && col!= 7 && board[row+1][col+1] <= 0)pseudomoves.push_back(push(row,col,row+1,col+1));

It could be made more legible by not cramming it all onto a single line:

if (row != 7 && col!= 7 && board[row+1][col+1] <= 0) {
    pseudomoves.push_back(push(row,col,row+1,col+1));
}

Use an enum for clarity

Right now there are lots of magic numbers in the code to signify the various chess pieces. For example, the white King is represented as 10 and the black King as -10. The check_w routine includes this line:

if(board[i][j] == 10){

That's in the middle of a couple of nested loops looking for the white king.

Why not make an enum class instead?

enum class Piece{k=-10, q=-6, r, n=-3, b, p, x, P, B, N, R=5, Q, K=10};

if(board[i][j] == Piece::K){

Now it's a bit clearer what we're looking for without having to rely on the comment.

Rethink the code structure

Right now, it appears that you will have to duplicate the code for generate_moves_w to create the corresponding generate_moves_b, and a similar story with check_w. That really doesn't make much sense because the rules of chess are the same for both players. Also, all of the details of how each piece could move are in one long nested loop within generate_moves_w. An alternative approach would be to have one routine per type of piece, greatly simplifying the code and making it much easier to understand and test.

Don't use std::endl when '\n' will do

Using std::endl emits a \n and flushes the stream. Unless you really need the stream flushed, you can improve the performance of the code by simply emitting '\n' instead of using the potentially more computationally costly std::endl.

Eliminate global variables where practical

The code declares and uses a global variable board. Global variables obfuscate the actual dependencies within code and make maintainance and understanding of the code that much more difficult. It also makes the code harder to reuse. For all of these reasons, it's generally far preferable to eliminate global variables and to instead create an object to encapsulate both the data and the relevant functions that operate on it. In this code, one obvious class would be a ChessBoard.

Rethink the algorithm

Right now, the code searches the entire board for pieces, recalculates all possible moves, tests each possible move for a check and then finally returns a list of valid moves. If your interest is performance, the first thing to think about is how to avoid so much recalculation. For instance, in the opening stages of the game, the possible moves for either King are unaltered by most moves. If you calculate it at the beginning of the game, you don't really need to recalculate for any move -- just certain ones. Also, there are two important and related concepts. The first concept is the possible moves each piece has available, but the other is which pieces threaten or protect others. The calculations for threaten/protect are identical -- the only difference is whether the pieces are opposite colors or not. You could use this to simplify, for example, your check_w code.

An example

Here's a partial refactoring of the code to show how it might look using classes.

class Chess {
    class BoardLocation {
        int rank, file;
    public:
        BoardLocation(int rank, int file) :
            rank{rank}, file{file}
        { 
            if (rank < 0 || file < 0 || rank > 7 || file > 7) {
                throw std::invalid_argument("rank and file must be in the range [0,7]");
            }
        }
        int Rank() const { return rank; }
        int File() const { return file; }
        friend std::ostream& operator<<(std::ostream& out, const BoardLocation& bl) {
            return out << char('a'+bl.File()) << char('8'-bl.Rank());
        }
    };
public:
    enum class Piece{k, q, r, n, b, p, x, P, B, N, R, Q, K};
    struct ChessMove {
        BoardLocation from;
        BoardLocation to;
        friend std::ostream& operator<<(std::ostream& out, const ChessMove& m);
    };

    Chess();
    Piece operator()(int a, int b) const {
        return board[a][b];
    }
    Piece operator()(const BoardLocation& bl) const {
        return board[bl.Rank()][bl.File()];
    }
    Piece &operator()(const BoardLocation& bl) {
        return board[bl.Rank()][bl.File()];
    }
    bool isBlack(int a, int b) const {
        auto v{board[a][b]};
        return v==Piece::k || v==Piece::q || v==Piece::r || v==Piece::n || v==Piece::b || v==Piece::p;
    }
    bool isWhite(int a, int b) const {
        auto v{board[a][b]};
        return v==Piece::K || v==Piece::Q || v==Piece::R || v==Piece::N || v==Piece::B || v==Piece::P;
    }
    Piece perform(ChessMove &m);
    void undomove(Piece original, const ChessMove& m);
    bool check_w() const;
    std::vector<ChessMove> generate_moves_w();
    static const std::unordered_map<Chess::Piece, char> piecename; 
private:
    Piece board[8][8];
};