C++连接4 Minimax + Alpha Beta修剪AI做出错误决策

Question

这篇文章是对我上一篇文章的跟进。为了提高极小极大连接-4AI算法的效率，我决定使用α-beta剪枝。这无疑有助于程序的长时间运行(我以前认为这是一个无限递归)，但是AI并没有按照我希望的方式工作。

AI只是选择下一个可用的空位来标记，即使这会导致损失.

我试着增加和降低深度级别，并确保检查获胜者的功能实际上是有效的。此外，我将先前用于板的2d矢量转换为一维矢量，并相应地更新了其他功能。

任何帮助，为什么AI的行为方式，这将是非常感谢。

代码：

#include <iostream>
#include <vector>

using namespace std;

bool isFull(std::vector<char>& grid) { //just checks if no empty spaces
    for(int i = 0; i < 16; i++) {
        if(grid[i] == '-') { 
            return false;
        }
    } 

    return true;
}

pair<bool, char> isWinner(std::vector<char>& grid, char aiMark, char hMark) {
    pair<bool, char> temp; // the pair of: whether the game is over, and who won(if any.)
    //'X' if AI wins, 'O' if human wins, '-' if tie/game not over.

    //horizontal check
    for (int i = 0; i < 16; i += 4) {
        if (grid[i] == aiMark && grid[i + 1] == aiMark && 
            grid[i + 2] == aiMark && grid[i + 3] == aiMark) {
            temp.first = true;
            temp.second = aiMark;
            return temp;
        }
        else if (grid[i] == hMark && grid[i + 1] == hMark && 
                 grid[i + 2] == hMark && grid[i + 3] == hMark) {
            temp.first = true;
            temp.second = hMark;
            return temp;
        }
    }

    //vertical check
    for (int i = 0; i < 4; i++) {
        if (grid[i] == aiMark && grid[i + 4] == aiMark && 
            grid[i + 8] == aiMark && grid[i + 12] == aiMark) {
            temp.first = true;
            temp.second = aiMark;
            return temp;
        } 
        else if (grid[i] == hMark && grid[i + 4] == hMark && 
                 grid[i + 8] == hMark && grid[i + 12] == hMark) {
            temp.first = true;
            temp.second = hMark;
            return temp;
        }
    }

    //diagonal checks
    if (grid[0] == aiMark && grid[5] == aiMark && 
        grid[10] == aiMark && grid[15] == aiMark) {
        temp.first = true;
        temp.second = aiMark;
        return temp;
    } 
    else if (grid[0] == hMark && grid[5] == hMark && 
             grid[10] == hMark && grid[15] == hMark) {
        temp.first = true;
        temp.second = hMark;
        return temp;
    }

    if (grid[3] == aiMark && grid[6] == aiMark && 
        grid[9] == aiMark && grid[12] == aiMark) {
        temp.first = true;
        temp.second = aiMark;
        return temp;
    } 
    else if (grid[3] == hMark && grid[6] == hMark && 
             grid[9] == hMark && grid[12] == hMark) {
        temp.first = true;
        temp.second = hMark;
        return temp;
    }

    if (isFull(grid) == true) {
        temp.first = true;
        temp.second = '-';
        return temp;
    }

    temp.first = false;
    temp.second = '-';
    return temp;
}

int minimax(std::vector<char>& grid, int depth, bool maxim, 
            char aiMark, char hMark, int al, int be) {
    pair<bool, char> result = isWinner(grid, aiMark, hMark);
    
    // result.first will be true if game is over, and result.second is:
    // 'X' if ai wins, 'O' if human wins, '-' if game is not over or if it ends with tie
   
    if (result.first != false || depth == 0) {
        if (result.second == aiMark) {
            return depth; // AI wins (maximizing)
        } 
        else if (result.second == hMark) {
            return -depth; // Human wins (minimizing)
        } 
        else {
            return 0; // Tie or depth = 0
        }
    } 
    else {
        if (maxim == true) {
            int best = INT_MIN;

            for (int i = 0; i < 16; i++) {
                if (grid[i] == '-') { // is space empty?
                    grid[i] = aiMark; // editing board
                    int score = minimax(grid, depth - 1, !maxim, aiMark, hMark, al, be); // call minimax with "new" board
                    best = max(best, score); // update max
                    grid[i] = '-'; // backtrack
                    al = best; // update alpha
                        
                    if (al >= be) {
                        break; // pruning     
                    }
                }
            }
            
            return best; //return max score
        } 
        else {
            int worst = INT_MAX;

            for (int i = 0; i < 16; i++) {
                if (grid[i] == '-') {
                    grid[i] = hMark;
                    int score = minimax(grid, depth - 1, !maxim, aiMark, hMark, al, be);
                    worst = min(worst, score);
                    grid[i] = '-';
                    be = worst;

                    if (be <= al) {  //same as the maximizing player but is minimizing instead
                        break;
                    }
                }
            }

            return worst; //return min score
        }
    }
}

void bestMove(std::vector<char>& grid, char aiMark, char hMark) {
    int best = INT_MIN; //best score for ai
    int finalSpot = -1; //place where ai will put mark
    
    pair<bool, char> result = isWinner(grid, aiMark, hMark); // explained in minimax function comments
    
    if (result.first != false) {
        return; // if game is supposed to be over
    } 

    for (int i = 0; i < 16; i++) {
        if (grid[i] == '-') {
            grid[i] = aiMark;
            int score = minimax(grid, 8, true, aiMark, hMark, INT_MIN, INT_MAX);
             
            if (score > best) {
                best = score;
                finalSpot = i; // update best score and best spot
            }
                
            grid[i] = '-'; // backtrack
        }
    }
    
    grid[finalSpot] = aiMark; // AI finally updates grid
    return;
}

Answer 1

该算法可以选择失败的移动，因为在bestMove()中，您放置一个aiMark，然后调用minmax()，并将maxim设置为true，这将在一行中放置第二个aiMark。人类在IA之后不玩游戏。

关于alpha beta，您还可以使用：alpha = max(alpha, best)更新alpha，以及使用beta的等效方式。这样做并不是错误的，而是没有优化的，因为alpha的值可能会下降，而它只应该提高。

我认为解决你的游戏最好的方法是增加一个转位表。这是有点沉重的实施，但IA将避免学习两次相同的立场。您可以首先将您的代码转换为Negamax版本，这既简单又方便。