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 functionpseudomoves.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.
check_w
. Also, the title should state what your code does, not the concerns you have with it. \$\endgroup\$