Здравствуйте, пишу код для игры в крестики нолики на достаточно большом игровом поле человека против компьютера. Компьютер должен быть "умным", использовать альфа-бета отсечения и делать проверку на почти выигрышную позицию соперника (человека). На поле 3x3 и 4x4 работает отлично, а вот если увеличивать поле, работает долго. Помогите, пожалуйста, решить данную проблему. Может нужно добавить какое-то дополнительное условие или таймер поставить (например, если работает больше какого-то времени, то переходить сразу к альфа-бета отсечению).
Код:
class ComputerPlayer
{
private:
char symbol;
int maxDepth;
public:
ComputerPlayer(char symbol, int maxDepth) : symbol(symbol), maxDepth(maxDepth) {}
void makeMove(GameBoard& board)
{
char opponentSymbol = (symbol == 'X') ? 'O' : 'X';
// проверяем наличие выигрышной позиции у игрока
for (int i = 0; i < board.getSize(); i++)
{
for (int j = 0; j < board.getSize(); j++)
{
if (board(i, j) == '-')// проверяем только пустые клетки
{
// проверяем горизонтальный ряд
bool found = true;
for (int k = j; k < j + board.getWin() && k < board.getSize(); k++)
{
if (board(i, k) != symbol)
{
found = false;
break;
}
}
if (found && j > 0 && board(i, j - 1) == '-') // блокируем выигрышную позицию
{
board(i, j - 1) = symbol;
return;
}
// проверяем вертикальный ряд
found = true;
for (int k = i; k < i + board.getWin() && k < board.getSize(); k++)
{
if (board(k, j) != opponentSymbol)
{
found = false;
break;
}
}
if (found && i > 0 && board(i - 1, j) == '-') // блокируем выигрышную позицию
{
board(i - 1, j) = symbol;
return;
}
// проверяем диагональный ряд (слева направо)
found = true;
for (int k = 0; k < board.getWin() && i + k < board.getSize() && j + k < board.getSize(); k++)
{
if (board(i + k, j + k) != opponentSymbol)
{
found = false;
break;
}
}
if (found && i > 0 && j > 0 && board(i - 1, j - 1) == '-') // блокируем выигрышную позицию
{
board(i - 1, j - 1) = symbol;
return;
}
// проверяем диагональный ряд (справа налево)
found = true;
for (int k = 0; k < board.getWin() && i + k < board.getSize() && j - k >= 0; k++)
{
if (board(i + k, j - k) != opponentSymbol)
{
found = false;
break;
}
}
if (found && i > 0 && j < board.getSize() - 1 && board(i - 1, j + 1) == '-') // блокируем выигрышную позицию
{
board(i - 1, j + 1) = symbol;
return;
}
}
}
}
// Если выигрышной позиции у игрока нет, используем альфа-бета отсечение
int alpha = INT_MIN;
int beta = INT_MAX;
int maxScore = INT_MIN;
int bestMoveRow = -1;
int bestMoveCol = -1;
for (int i = 0; i < board.getSize(); i++) {
for (int j = 0; j < board.getSize(); j++) {
if (board(i, j) == '-') {
board(i, j) = symbol;
int score = minimax(board, alpha, beta, false);
board(i, j) = '-';
if (score > maxScore) {
maxScore = score;
bestMoveRow = i;
bestMoveCol = j;
}
}
}
}
board(bestMoveRow, bestMoveCol) = symbol;
}
int minimax(GameBoard& board, int alpha, int beta, bool maximizingPlayer)
{
char opponentSymbol = (symbol == 'X') ? 'O' : 'X';
if (board.checkWinner()==symbol) {
return 10;
}
else if (board.checkWinner() == opponentSymbol) {
return -10;
}
else if (board.isFull()) {
return 0;
}
if (maximizingPlayer) {
int maxScore = INT_MIN;
for (int i = 0; i < board.getSize(); i++) {
for (int j = 0; j < board.getSize(); j++) {
if (board(i, j) == '-') {
board(i, j) = symbol;
int score = minimax(board, alpha, beta, false);
board(i, j) = '-';
maxScore = max(maxScore, score);
alpha = max(alpha, score);
if (beta <= alpha) {
break;
}
}
}
}
return maxScore;
}
else {
int minScore = INT_MAX;
for (int i = 0; i < board.getSize(); i++) {
for (int j = 0; j < board.getSize(); j++) {
if (board(i, j) == '-') {
board(i, j) = opponentSymbol;
int score = minimax(board, alpha, beta, true);
board(i, j) = '-';
minScore = min(minScore, score);
beta = min(beta, score);
if (beta <= alpha) {
break;
}
}
}
}
return minScore;
}
}
};