模块化Connect4游戏使用极小极大算法和alpha-beta剪枝出现段错误

我正在开发一个模块化的Connect 4游戏,支持从3×3到10×10的不同网格大小,以及可变数量的获胜“棋子”。下面的程序通过传递三个参数来运行:网格大小(网格为正方形)、连续需要的棋子数量以及谁先开始(尚未实现)。例如,运行命令将是connectM 6 5 1。

在下面的代码中,你可以看到我的尝试。当第二个参数使用4时,程序运行良好,但如果使用更大的值,我会在第338行左右遇到段错误,我无法找出问题所在。有人能提供一些我明显做错的地方的见解吗?

#include <stdio.h>#include <iostream>#include <vector>#include <limits.h>#include <array>#include <sstream>#define min(a,b) (((a) < (b)) ? (a) : (b))#define max(a,b) (((a) > (b)) ? (a) : (b))using namespace std;// function declarationsvoid printBoard(vector<vector<int> >&);int userMove();void makeMove(vector<vector<int> >&, int, unsigned int);void errorMessage(int);int aiMove();vector<vector<int> > copyBoard(vector<vector<int> >);bool winningMove(vector<vector<int> >&, unsigned int);int scoreSet(vector<unsigned int>, unsigned int);int tabScore(vector<vector<int> >, unsigned int);array<int, 2> miniMax(vector<vector<int> >&, unsigned int, int, int, unsigned int);int heurFunction(unsigned int, unsigned int, unsigned int);// Avoid magic numbersunsigned int NUM_COL = 7; // how wide is the boardunsigned int NUM_ROW = 7; // how tallunsigned int PLAYER = 1; // player numberunsigned int COMPUTER = 2; // AI numberunsigned int MAX_DEPTH = 5; // the default "difficulty" of the computer controlled AIunsigned int WINNING_PUCKS = 4; //Default winning pucksunsigned int FIRST_PLAYER = 0;bool gameOver = false; // flag for if game is overunsigned int turns = 0; // count for # turnsunsigned int currentPlayer = PLAYER; // current playervector<vector<int>> board(NUM_ROW, vector<int>(NUM_COL)); // the game board/** * game playing function * loops between players while they take turns */void playGame() {    printBoard(board); // print initial board    while (!gameOver) { // while no game over state        if (currentPlayer == COMPUTER) { // AI move            makeMove(board, aiMove(), COMPUTER);        }        else if (currentPlayer == PLAYER) { // player move            makeMove(board, userMove(), PLAYER);        }        else if (turns == NUM_ROW * NUM_COL) { // if max number of turns reached            gameOver = true;        }        gameOver = winningMove(board, currentPlayer); // check if player won        currentPlayer = (currentPlayer == 1) ? 2 : 1; // switch player        turns++; // iterate number of turns        cout << endl;        printBoard(board); // print board after successful move    }    if (turns == NUM_ROW * NUM_COL) { // if draw condition        cout << "Draw!" << endl;    }    else { // otherwise, someone won        cout << ((currentPlayer == PLAYER) ? "AI Wins!" : "Player Wins!") << endl;    }}/** * function that makes the move for the player * @param b - the board to make move on * @param c - column to drop piece into * @param p - the current player */void makeMove(vector<vector<int> >& b, int c, unsigned int p) {    // start from bottom of board going up    for (unsigned int r = 0; r < NUM_ROW; r++) {        if (b[r][c] == 0) { // first available spot            b[r][c] = p; // set piece            break;        }    }}/** * prompts the user for their move * and ensures valid user input * @return the user chosen column */int userMove() {    int move = -1; // temporary    while (true) { // repeat until proper input given        cout << "Enter a column: ";        cin >> move; // init move as input        if (!cin) { // if non-integer            cin.clear();            cin.ignore(INT_MAX, '\n');            errorMessage(1); // let user know        }        else if (!((unsigned int)move < NUM_COL && move >= 0)) { // if out of bounds            errorMessage(2); // let user know        }        else if (board[NUM_ROW - 1][move] != 0) { // if full column            errorMessage(3); // let user know        }        else { // if it gets here, input valid            break;        }        cout << endl << endl;    }    return move;}/** * AI "think" algorithm * uses minimax to find ideal move * @return - the column number for best move */int aiMove() {    cout << "AI is thinking about a move..." << endl;    return miniMax(board, MAX_DEPTH, 0 - INT_MAX, INT_MAX, COMPUTER)[1];}/** * Minimax implementation using alpha-beta pruning * @param b - the board to perform MM on * @param d - the current depth * @param alf - alpha * @param bet - beta * @param p - current player */array<int, 2> miniMax(vector<vector<int> > &b, unsigned int d, int alf, int bet, unsigned int p) {    /**     * if we've reached minimal depth allowed by the program     * we need to stop, so force it to return current values     * since a move will never (theoretically) get this deep,     * the column doesn't matter (-1) but we're more interested     * in the score     *     * as well, we need to take into consideration how many moves     * ie when the board is full     */    if (d == 0 || d >= (NUM_COL * NUM_ROW) - turns) {        // get current score to return        return array<int, 2>{tabScore(b, COMPUTER), -1};    }    if (p == COMPUTER) { // if AI player        array<int, 2> moveSoFar = {INT_MIN, -1}; // since maximizing, we want lowest possible value        if (winningMove(b, PLAYER)) { // if player about to win            return moveSoFar; // force it to say it's worst possible score, so it knows to avoid move        } // otherwise, business as usual        for (unsigned int c = 0; c < NUM_COL; c++) { // for each possible move            if (b[NUM_ROW - 1][c] == 0) { // but only if that column is non-full                vector<vector<int> > newBoard = copyBoard(b); // make a copy of the board                makeMove(newBoard, c, p); // try the move                int score = miniMax(newBoard, d - 1, alf, bet, PLAYER)[0]; // find move based on that new board state                if (score > moveSoFar[0]) { // if better score, replace it, and consider that best move (for now)                    moveSoFar = {score, (int)c};                }                alf = max(alf, moveSoFar[0]);                if (alf >= bet) { break; } // for pruning            }        }        return moveSoFar; // return best possible move    }    else {        array<int, 2> moveSoFar = {INT_MAX, -1}; // since PLAYER is minimized, we want moves that diminish this score        if (winningMove(b, COMPUTER)) {            return moveSoFar; // if about to win, report that move as best        }        for (unsigned int c = 0; c < NUM_COL; c++) {            if (b[NUM_ROW - 1][c] == 0) {                vector<vector<int> > newBoard = copyBoard(b);                makeMove(newBoard, c, p);                int score = miniMax(newBoard, d - 1, alf, bet, COMPUTER)[0];                if (score < moveSoFar[0]) {                    moveSoFar = {score, (int)c};                }                bet = min(bet, moveSoFar[0]);                if (alf >= bet) { break; }            }        }        return moveSoFar;    }}

回答:

我发现你没有更改之前版本游戏中的一个硬编码值。在第336行,你有

        for (unsigned int r = 3; r < NUM_ROW; r++) {

这仅在WINNING_PUCKS设置为4时正确。一般情况应该是:

        for (unsigned int r = (WINNING_PUCKS - 1); r < NUM_ROW; r++) {

请注意,虽然这部分现在应该能正确工作了,但我运行它时,在游戏结束时仍然会崩溃,并显示错误消息:

double free or corruption (out)Aborted (core dumped)

我还没有确定这是什么原因导致的。

Related Posts

L1-L2正则化的不同系数

我想对网络的权重同时应用L1和L2正则化。然而,我找不…

使用scikit-learn的无监督方法将列表分类成不同组别,有没有办法?

我有一系列实例,每个实例都有一份列表,代表它所遵循的不…

f1_score metric in lightgbm

我想使用自定义指标f1_score来训练一个lgb模型…

通过相关系数矩阵进行特征选择

我在测试不同的算法时,如逻辑回归、高斯朴素贝叶斯、随机…

可以将机器学习库用于流式输入和输出吗?

已关闭。此问题需要更加聚焦。目前不接受回答。 想要改进…

在TensorFlow中,queue.dequeue_up_to()方法的用途是什么?

我对这个方法感到非常困惑,特别是当我发现这个令人费解的…

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注