使用alpha-beta修剪的C ++检查程序

问题描述 投票:1回答:1

我正在尝试使用alpha-beta pruning为Checkers游戏(AI vs AI)编写算法。您可以在下面或在此PasteBin中查看代码和评论。

游戏本身运行良好,但AI(alpha-beta修剪算法)似乎有一个错误,因为机器人基本上互相喂食棋子(根本没有计算显示)。该代码包含2个不同版本的alpha-beta算法函数(更详细,更不详细)。

我已经尝试在tmp中跟踪alphabeta()的值,它似乎有正常值(在深度= 5的情况下,范围从-3到3)。

我也尝试过将this代码应用到我的代码中,但得到了相同的结果。

我最好的猜测是问题出现在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;
}
c++ algorithm minimax alpha-beta-pruning
1个回答
0
投票

通常在文献中描述的α-β截止方式是不必要的错综复杂的。你不需要两个限制,从同一个玩家的角度评估移动也不是一个好主意。这里有一个更清晰的描述:

for all moves:
    evaluate the move  
    give it a temporary score from the point of view of the player at move  
    for all counter moves:
        evaluate the move
        give is a temporary score from the point of view of the player at move
        for all counter-counter moves:
            evaluate the move
            give it a score from the point of view of the player at move
            undo the counter-counter move
            update best counter-counter move if better
            if the counter-counter move is so good, that current
            counter move cant be best, (other is better) then break
        subtract best counter-counter-move score from temporary counter score
        undo the counter move
        update best counter move if better
        if the counter move is so good, that current move
        cant be best, (other is better) then break
    subtract best counter-move score from temporary score
    undo the move
    update best move if better

逻辑是这样的: 让我们说你已经评估了几个动作,到目前为止最好的是3 当前行动的临时得分为5。 您目前评估的反向移动值4。 这意味着目前的行动最多可能是值得的。(5-4) 由于当前的移动不是最好的,因此无需找到更好的反向移动

© www.soinside.com 2019 - 2024. All rights reserved.