алгоритм — проверка C ++ с использованием альфа-бета-обрезки

Я пытаюсь написать алгоритм, используя альфа-бета-обрезка для игры в шашки (AI против AI). Вы можете увидеть код & Комментарии
ниже или в этом Pastebin.

Сама игра работает нормально, но AI (алгоритм отсечения альфа-бета), похоже, содержит ошибку, потому что боты в основном подают шашки друг другу (никаких расчетов вообще не было). Код содержит 2 разные версии функций алгоритма альфа-бета (более подробный и менее подробный).

Я пробовал отслеживать значение tmp в alphabeta() и кажется, что он имеет нормальные значения (от -3 до 3 в случае глубины = 5).

Я также пытался реализовать этот Код в мой, но получил те же результаты.

Мое лучшее предположение, что проблема в bool whiteTurn, который объявляет, чей это ход сейчас, но я не могу найти никаких проблем с ним — повороты переключаются правильно.

Второе лучшее предположение — Move bestMove, Я не уверен, правильно ли вырывать его из рекурсивной функции.

В чем ошибка?

#include "stdafx.h"#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Move
{
public:
pair<int, int> start;
pair<int, int> end;
bool lethal;
Move(int x, int y, int x1, int y1, bool kill)
{
start.first = x; start.second = y;
end.first = x1; end.second = y1;
lethal = kill;
}
};char **initBoard(int size)
{
char **board = new char*[size];
for (int count = 0; count < size; count++)
board[count] = new char[size];
return board;
}

void newGame(char **board, int size)
{
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
{
board[i][j] = '-';
if ((i == 0 || i == 2) && j % 2 == 1) board[i][j] = 'O';
if (i == 1 && j % 2 == 0) board[i][j] = 'O';
if ((i == size - 3 || i == size - 1) && j % 2 == 0) board[i][j] = 'X';
if (i == size - 2 && j % 2 == 1) board[i][j] = 'X';
}
}

void printBoard(char **board, int size)
{
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
cout << board[i][j] << " ";
}
cout << endl;
}
cout << endl;
}

void do_move(char **board, Move play)
{
char temp = board[play.start.first][play.start.second];
board[play.start.first][play.start.second] = board[play.end.first][play.end.second];
board[play.end.first][play.end.second] = temp;
if (play.lethal)
board[(play.end.first + play.start.first) / 2][(play.end.second + play.start.second) / 2] = '-';
}

void undo_move(char **board, Move play)
{
board[play.start.first][play.start.second] = board[play.end.first][play.end.second];
board[play.end.first][play.end.second] = '-';
if (play.lethal)
{
if (board[play.start.first][play.start.second] == 'X')
board[(play.end.first + play.start.first) / 2][(play.end.second + play.start.second) / 2] = 'O';
if (board[play.start.first][play.start.second] == 'O')
board[(play.end.first + play.start.first) / 2][(play.end.second + play.start.second) / 2] = 'X';
}
}

vector<Move> findMoves(char **board, int size, bool whiteTurn)
{
vector<Move> moves;
//first jump (if possible)
for (int x = 0; x < size; x++)
{
for (int y = 0; y < size; y++)
{
if (whiteTurn && board[x][y] == 'X')
{
if (x > 1 && y > 1 && board[x - 1][y - 1] == 'O' && board[x - 2][y - 2] == '-')
moves.push_back(Move(x, y, x - 2, y - 2, true));
if (x > 1 && y < size - 2 && board[x - 1][y + 1] == 'O' && board[x - 2][y + 2] == '-')
moves.push_back(Move(x, y, x - 2, y + 2, true));
if (x < size - 2 && y > 1 && board[x + 1][y - 1] == 'O' && board[x + 2][y - 2] == '-')
moves.push_back(Move(x, y, x + 2, y - 2, true));
if (x < size - 2 && y < size - 2 && board[x + 1][y + 1] == 'O' && board[x + 2][y + 2] == '-')
moves.push_back(Move(x, y, x + 2, y + 2, true));
}
if (!whiteTurn && board[x][y] == 'O')
{
if (x > 1 && y > 1 && board[x - 1][y - 1] == 'X' && board[x - 2][y - 2] == '-')
moves.push_back(Move(x, y, x - 2, y - 2, true));
if (x > 1 && y < size - 2 && board[x - 1][y + 1] == 'X' && board[x - 2][y + 2] == '-')
moves.push_back(Move(x, y, x - 2, y + 2, true));
if (x < size - 2 && y > 1 && board[x + 1][y - 1] == 'X' && board[x + 2][y - 2] == '-')
moves.push_back(Move(x, y, x + 2, y - 2, true));
if (x < size - 2 && y < size - 2 && board[x + 1][y + 1] == 'X' && board[x + 2][y + 2] == '-')
moves.push_back(Move(x, y, x + 2, y + 2, true));
}
}
}
//then move
for (int x = 0; x < size; x++)
{
for (int y = 0; y < size; y++)
{
if (whiteTurn && board[x][y] == 'X')
{
if (x > 0 && y > 0 && board[x - 1][y - 1] == '-')
moves.push_back(Move(x, y, x - 1, y - 1, false));
if (x > 0 && y < size - 1 && board[x - 1][y + 1] == '-')
moves.push_back(Move(x, y, x - 1, y + 1, false));

}
if (!whiteTurn && board[x][y] == 'O')
{
if (x < size - 1 && y > 0 && board[x + 1][y - 1] == '-')
moves.push_back(Move(x, y, x + 1, y - 1, false));
if (x < size - 1 && y < size - 1 && board[x + 1][y + 1] == '-')
moves.push_back(Move(x, y, x + 1, y + 1, false));
}
}
}
return moves;
}

//plain score calculation function
int getScore(char **board, int size, bool whiteTurn)
{
int whiteNum = 0, blackNum = 0;

for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
if (board[i][j] == 'X') whiteNum++;
if (board[i][j] == 'O') blackNum++;
}
}

if (whiteTurn)
return whiteNum - blackNum;
else
return blackNum - whiteNum;
}

//old function, doesnt work as intended too
/*Move getBestMove(char **board, int size, bool whiteTurn)
{
int score, tmp;
Move bestMove(0, 0, 0, 0, false);
vector<Move> movelist = findMoves(board, size, whiteTurn);
score = getScore(board, size, whiteTurn);

for (unsigned int i = 0; i < movelist.size(); i++)
{
do_move(board, movelist.at(i));
tmp = getScore(board, size, whiteTurn);
undo_move(board, movelist.at(i));

if (tmp >= score)
{
score = tmp;
bestMove = movelist.at(i);
}
}
return bestMove;
}*/

//made this global - no idea how to avoid it being global with recursion in alphabeta
Move bestMove(0, 0, 0, 0, false);

//alphabeta function with more detailed calculations
/*int AlphaBeta(char **board, int size, bool whiteTurn, int depth, int alpha, int beta)
{
if (depth == 0) return getScore(board, size, whiteTurn);
int score = -100;
vector<Move> movelist = findMoves(board, size, whiteTurn);

for (unsigned int i = 0; i < movelist.size(); i++)
{
do_move(board, movelist.at(i));
int tmp = -AlphaBeta(board, size, !whiteTurn, depth - 1, alpha, beta);
undo_move(board, movelist.at(i));
if (tmp > score)
{
if (whiteTurn)
{
if (score > alpha)
{
alpha = score;
}
if (-alpha <= beta)
{
return alpha;
}
}
else
{
if (score > beta)
{
beta = score;
}
if (-beta <= alpha)
{
return beta;
}
}
}
}
return score;
}*/

//generic alphabeta function
int alphabeta(char **board, int size, bool whiteTurn, int depth, int alpha, int beta)
{
if (depth == 0) return getScore(board, size, whiteTurn);
vector<Move> movelist = findMoves(board, size, whiteTurn);

for (const Move &move : movelist)
{
do_move(board, move);
int tmp = -alphabeta(board, size, !whiteTurn, depth - 1, -beta, -alpha);
undo_move(board, move);
if (tmp > alpha)
{
if (depth == 5)
bestMove = move;
alpha = tmp;
}
}
return alpha;
}

//main game loop
void game(char **board, int size, bool &whiteTurn)
{
newGame(board, size);
printBoard(board, size);
system("PAUSE");

int a = -std::numeric_limits<int>::max();
int b = std::numeric_limits<int>::max();

do
{
alphabeta(board, size, whiteTurn, 5, a, b);
do_move(board, bestMove);
whiteTurn = !whiteTurn;
system("cls");
printBoard(board, size);
system("PAUSE");
} while (!findMoves(board, size, whiteTurn).empty());
}

int main()
{
int n = 8;
bool whTurn = true;
char **board=initBoard(n);
game(board, n, whTurn);
return 0;
}