#include <iostream>
#include <chrono>
using namespace std;
using namespace chrono;
const int BOARD_SIZE = 8;
struct Move {
int fromRow, fromCol, toRow, toCol;
};
class Chessboard {
public:
char board[BOARD_SIZE][BOARD_SIZE];
void initializeBoard() {
// Initialize the chessboard with pieces
// '0' represents an empty square
board[0][0] = board[0][7] = 'r';
board[0][1] = board[0][6] = 'n';
board[0][2] = board[0][5] = 'b';
board[0][3] = 'q';
board[0][4] = 'k';
for (int i = 0; i < BOARD_SIZE; ++i)
board[1][i] = 'p';
for (int i = 2; i < 6; ++i)
for (int j = 0; j < BOARD_SIZE; ++j)
board[i][j] = '0';
for (int i = 0; i < BOARD_SIZE; ++i)
board[6][i] = 'P';
board[7][0] = board[7][7] = 'R';
board[7][1] = board[7][6] = 'N';
board[7][2] = board[7][5] = 'B';
board[7][3] = 'Q';
board[7][4] = 'K';
}
void printBoard() {
for (int i = 0; i < BOARD_SIZE; ++i) {
for (int j = 0; j < BOARD_SIZE; ++j)
cout << board[i][j] << " ";
cout << endl;
}
cout << endl;
}
bool isValidMove(int fromRow, int fromCol, int toRow, int toCol) {
// Check if the move is within the bounds of the board
if (fromRow < 0 || fromRow >= BOARD_SIZE || fromCol < 0 || fromCol >= BOARD_SIZE ||
toRow < 0 || toRow >= BOARD_SIZE || toCol < 0 || toCol >= BOARD_SIZE)
return false;
// Check if there is a piece at the starting position
if (board[fromRow][fromCol] == '0')
return false;
// Check if the destination is a valid empty square or has an opponent's piece
if (board[toRow][toCol] == '0' || (islower(board[fromRow][fromCol]) && isupper(board[toRow][toCol])) ||
(isupper(board[fromRow][fromCol]) && islower(board[toRow][toCol])))
return true;
return false;
}
void makeMove(int fromRow, int fromCol, int toRow, int toCol) {
// Make the move on the chessboard
board[toRow][toCol] = board[fromRow][fromCol];
board[fromRow][fromCol] = '0';
}
void undoMove(int fromRow, int fromCol, int toRow, int toCol, char capturedPiece) {
// Undo the move on the chessboard
board[fromRow][fromCol] = board[toRow][toCol];
board[toRow][toCol] = capturedPiece;
}
void generateMoves(int depth) {
// Generate all possible moves at the current depth
if (depth == 0)
return;
for (int i = 0; i < BOARD_SIZE; ++i) {
for (int j = 0; j < BOARD_SIZE; ++j) {
if (islower(board[i][j])) {
for (int k = 0; k < BOARD_SIZE; ++k) {
for (int l = 0; l < BOARD_SIZE; ++l) {
if (isValidMove(i, j, k, l)) {
Move move = {i, j, k, l};
char capturedPiece = board[k][l];
makeMove(i, j, k, l);
generateMoves(depth - 1);
undoMove(i, j, k, l, capturedPiece);
}
}
}
}
}
}
}
};
int perft(Chessboard& chessboard, int depth) {
// Perform perft at the specified depth and return the total number of leaf nodes
if (depth == 0)
return 1;
int leafNodes = 0;
for (int i = 0; i < BOARD_SIZE; ++i) {
for (int j = 0; j < BOARD_SIZE; ++j) {
if (islower(chessboard.board[i][j])) {
for (int k = 0; k < BOARD_SIZE; ++k) {
for (int l = 0; l < BOARD_SIZE; ++l) {
if (chessboard.isValidMove(i, j, k, l)) {
Move move = {i, j, k, l};
char capturedPiece = chessboard.board[k][l];
chessboard.makeMove(i, j, k, l);
leafNodes += perft(chessboard, depth - 1);
chessboard.undoMove(i, j, k, l, capturedPiece);
}
}
}
}
}
}
return leafNodes;
}
int main() {
Chessboard chessboard;
chessboard.initializeBoard();
chessboard.printBoard();
auto start = high_resolution_clock::now();
int result = perft(chessboard, 5);
auto stop = high_resolution_clock::now();
auto duration = duration_cast<milliseconds>(stop - start);
cout << "Perft(5) Result: " << result << endl;
cout << "Time taken: " << duration.count() << " milliseconds" << endl;
return 0;
}