具有α-β剪枝问题的极小极大

Question

我在为游戏筷子做一个C程序。

这是一个非常简单的游戏，总共只有625个游戏状态（如果考虑到对称性和不可到达的状态，它甚至更低）。我读过minimax和alpha-beta算法，主要是针对tic-tac-toe的，但我遇到的问题是，在tic-tac-toe中，不可能循环回到以前的状态，而这在筷子中很容易发生。因此，当运行代码时，它将以堆栈溢出结束。

我通过添加以前访问过的州的标志来解决这个问题(我不知道这样做是否正确。)以便可以避免它们，但现在我的问题是输出并不像预期的那样对称。

例如，在游戏的开始状态下，每个玩家都有一个手指，所以它都是对称的。程序告诉我，最好的动作是用左手打我的右手，而不是相反。

我的源代码是-

#include <iostream>
#include <array>
#include <vector>
#include <limits>
std::array<int, 625> t; //Flags for visited states.
std::array<int, 625> f; //Flags for visited states.
int no = 0; //Unused. For debugging.
class gamestate
{
public:
    gamestate(int x, bool t) : turn(t) //Constructor.
    {
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++) {
                val[i][j] = x % 5;
                x /= 5;
            }
        init();
    }
    void print() //Unused. For debugging.
    {
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++)
                std::cout << val[i][j] << "\t";
            std::cout << "\n";
        }
        std::cout << "\n";
    }
    std::array<int, 6> canmove = {{ 1, 1, 1, 1, 1, 1 }}; //List of available moves.
    bool isover() //Is the game over.
    {
        return ended;
    }
    bool won() //Who won the game.
    {
        return winner;
    }
    bool isturn() //Whose turn it is.
    {
        return turn;
    }
    std::vector<int> choosemoves() //Choose the best possible moves in the current state.
    {
        std::vector<int> bestmoves;
        if(ended)
            return bestmoves;
        std::array<int, 6> scores;
        int bestscore;
        if(turn)
            bestscore = std::numeric_limits<int>::min();
        else
            bestscore = std::numeric_limits<int>::max();
        scores.fill(bestscore);
        for (int i = 0; i < 6; i++)
            if (canmove[i]) {
                t.fill(0);
                f.fill(0);
                gamestate *play = new gamestate(this->playmove(i),!turn);
                scores[i] = minimax(play, 0, std::numeric_limits<int>::min(), std::numeric_limits<int>::max());
                std::cout<<i<<": "<<scores[i]<<std::endl;
                delete play;
                if (turn) if (scores[i] > bestscore) bestscore = scores[i];
                if (!turn) if (scores[i] < bestscore) bestscore = scores[i];
            }
        for (int i = 0; i < 6; i++)
            if (scores[i] == bestscore)
                bestmoves.push_back(i);
        return bestmoves;
    }
private:
    std::array<std::array<int, 2>, 2 > val; //The values of the fingers.
    bool turn; //Whose turn it is.
    bool ended = false; //Has the game ended.
    bool winner; //Who won the game.
    void init() //Check if the game has ended and find the available moves.
    {
        if (!(val[turn][0]) && !(val[turn][1])) {
            ended = true;
            winner = !turn;
            canmove.fill(0);
            return;
        }
        if (!(val[!turn][0]) && !(val[!turn][1])) {
            ended = true;
            winner = turn;
            canmove.fill(0);
            return;
        }
        if (!val[turn][0]) {
            canmove[0] = 0;
            canmove[1] = 0;
            canmove[2] = 0;
            if (val[turn][1] % 2)
                canmove[5] = 0;
        }
        if (!val[turn][1]) {
            if (val[turn][0] % 2)
                canmove[2] = 0;
            canmove[3] = 0;
            canmove[4] = 0;
            canmove[5] = 0;
        }
        if (!val[!turn][0]) {
            canmove[0] = 0;
            canmove[3] = 0;
        }
        if (!val[!turn][1]) {
            canmove[1] = 0;
            canmove[4] = 0;
        }
    }
    int playmove(int mov) //Play a move to get the next game state.
    {
        auto newval = val;
        switch (mov) {
        case 0:
            newval[!turn][0] = (newval[turn][0] + newval[!turn][0]);
            newval[!turn][0] = (5 > newval[!turn][0]) ? newval[!turn][0] : 0;
            break;
        case 1:
            newval[!turn][1] = (newval[turn][0] + newval[!turn][1]);
            newval[!turn][1] = (5 > newval[!turn][1]) ? newval[!turn][1] : 0;
            break;
        case 2:
            if (newval[turn][1]) {
                newval[turn][1] = (newval[turn][0] + newval[turn][1]);
                newval[turn][1] = (5 > newval[turn][1]) ? newval[turn][1] : 0;
            } else {
                newval[turn][0] /= 2;
                newval[turn][1] = newval[turn][0];
            }
            break;
        case 3:
            newval[!turn][0] = (newval[turn][1] + newval[!turn][0]);
            newval[!turn][0] = (5 > newval[!turn][0]) ? newval[!turn][0] : 0;
            break;
        case 4:
            newval[!turn][1] = (newval[turn][1] + newval[!turn][1]);
            newval[!turn][1] = (5 > newval[!turn][1]) ? newval[!turn][1] : 0;
            break;
        case 5:
            if (newval[turn][0]) {
                newval[turn][0] = (newval[turn][1] + newval[turn][0]);
                newval[turn][0] = (5 > newval[turn][0]) ? newval[turn][0] : 0;
            } else {
                newval[turn][1] /= 2;
                newval[turn][0] = newval[turn][1];
            }
            break;
        default:
            std::cout << "\nInvalid move!\n";
        }
        int ret = 0;
        for (int i = 1; i > -1; i--)
            for (int j = 1; j > -1; j--) {
                ret+=newval[i][j];
                ret*=5;
            }
        ret/=5;
        return ret;
    }
    static int minimax(gamestate *game, int depth, int alpha, int beta) //Minimax searching function with alpha beta pruning.
    {
        if (game->isover()) {
            if (game->won())
                return 1000 - depth;
            else
                return depth - 1000;
        }
        if (game->isturn()) {
            for (int i = 0; i < 6; i++)
                if (game->canmove[i]&&t[game->playmove(i)]!=-1) {
                    int score;
                    if(!t[game->playmove(i)]){
                        t[game->playmove(i)] = -1;
                        gamestate *play = new gamestate(game->playmove(i),!game->isturn());
                        score = minimax(play, depth + 1, alpha, beta);
                        delete play;
                        t[game->playmove(i)] = score;
                    }
                    else
                        score = t[game->playmove(i)];
                    if (score > alpha) alpha = score;
                    if (alpha >= beta) break;
                }
            return alpha;
        } else {
            for (int i = 0; i < 6; i++)
                if (game->canmove[i]&&f[game->playmove(i)]!=-1) {
                    int score;
                    if(!f[game->playmove(i)]){
                        f[game->playmove(i)] = -1;
                        gamestate *play = new gamestate(game->playmove(i),!game->isturn());
                        score = minimax(play, depth + 1, alpha, beta);
                        delete play;
                        f[game->playmove(i)] = score;
                    }
                    else
                        score = f[game->playmove(i)];
                    if (score < beta) beta = score;
                    if (alpha >= beta) break;
                }
            return beta;
        }
    }
};
int main(void)
{
    gamestate test(243, true);
    auto movelist = test.choosemoves();
    for(auto i: movelist)
        std::cout<<i<<std::endl;
    return 0;
}

我正在以 5 为基数到十进制的系统传递移动，因为每手牌都可以有 0 到 4 的值。

在代码中，我输入了状态-

3    3

4    1

输出说我应该打我的右手（1）到对方的右边（3），但它没有说我应该打我的对手的左边（也是3）

我认为问题是因为我处理无限循环的方式。

做这件事的正确方法是什么？或者如果这是正确的方法，那么我该如何解决这个问题呢？

另外，请让我知道如何改进我的代码。

非常谢谢。

编辑：

我已经按如下方式更改了我的极小极大函数，以确保无限循环的得分高于损失，但我仍然没有得到对称性。我还做了一个函数来增加分数的深度

static float minimax(gamestate *game, int depth, float alpha, float beta) //Minimax searching function with alpha beta pruning.
    {
        if (game->isover()) {
            if (game->won())
                return 1000 - std::atan(depth) * 2000 / std::acos(-1);
            else
                return std::atan(depth) * 2000 / std::acos(-1) - 1000;
        }
        if (game->isturn()) {
            for (int i = 0; i < 6; i++)
                if (game->canmove[i]) {
                    float score;
                    if(!t[game->playmove(i)]) {
                        t[game->playmove(i)] = -1001;
                        gamestate *play = new gamestate(game->playmove(i), !game->isturn());
                        score = minimax(play, depth + 1, alpha, beta);
                        delete play;
                        t[game->playmove(i)] = score;
                    } else if(t[game->playmove(i)] == -1001)
                        score = 0;
                    else
                        score = adddepth(t[game->playmove(i)], depth);
                    if (score > alpha) alpha = score;
                    if (alpha >= beta) break;
                }
            return alpha;
        } else {
            for (int i = 0; i < 6; i++)
                if (game->canmove[i]) {
                    float score;
                    if(!f[game->playmove(i)]) {
                        f[game->playmove(i)] = -1001;
                        gamestate *play = new gamestate(game->playmove(i), !game->isturn());
                        score = minimax(play, depth + 1, alpha, beta);
                        delete play;
                        f[game->playmove(i)] = score;
                    } else if(f[game->playmove(i)] == -1001)
                        score = 0;
                    else
                        score = adddepth(f[game->playmove(i)], depth);
                    if (score < beta) beta = score;
                    if (alpha >= beta) break;
                }
            return beta;
        }
    }

这是添加深度的函数-

float adddepth(float score, int depth) //Add depth to pre-calculated score.
{
    int olddepth;
    float newscore;
    if(score > 0) {
        olddepth = std::tan((1000 - score) * std::acos(-1) / 2000);
        depth += olddepth;
        newscore = 1000 - std::atan(depth) * 2000 / std::acos(-1);
    } else {
        olddepth = std::tan((1000 + score) * std::acos(-1) / 2000);
        depth += olddepth;
        newscore = std::atan(depth) * 2000 / std::acos(-1) - 1000;
    }
    return newscore;
}

Answer 1

免责声明：我不懂C， 坦率地说，我没有费心阅读游戏规则 。我现在已经阅读了规则，仍然坚持我所说的......但我仍然不知道C.不过，我可以介绍一些关于算法的一般知识，这些知识应该会让你朝着正确的方向前进。

不对称本身并不是一件坏事。如果两个招式完全等价，它应该选择其中一个，而不是像布里丹的屁股一样无助地站着。事实上，你应该确信你写的任何代理都有某种方法可以在它不能区分的策略中任意选择。

您应该更仔细地考虑拒绝访问以前的状态所暗示的效用方案。追求无限循环是一个有效的策略，即使你当前的表示会使程序崩溃;也许错误是溢出，而不是导致溢出的策略。如果让你在输掉游戏和拒绝让游戏结束之间做出选择，你希望你的经纪人更喜欢哪个？

如果你希望你的代理不惜一切代价避免失败——也就是说，你希望它更喜欢不确定的游戏而不是失败——那么我建议将任何重复的状态视为终端状态，并在输赢之间赋予它一个值。毕竟，从某种意义上说，它是终端——这是游戏将永远永远进入的循环，它的明确结果是没有赢家。然而，记住，如果你使用的是简单的极小值（一个效用函数，而不是两个），那么这意味着你的对手也将永恒的游戏视为中等结果。

这听起来可能很荒谬，但也许玩到无限实际上是一种合理的政策。记住，minimax假设了最坏的情况——一个完全理性的敌人，他的利益与你的完全相反。但是，例如，如果你正在写一个代理人与一个人比赛，那么这个人要么在逻辑上出错，要么最终会决定他们宁愿以输球结束比赛——所以你的代理人会从耐心地保持纳什均衡循环中受益！

如果你希望你的经纪人希望游戏最终结束，那么我建议你实施一个活的惩罚——一个添加到你的效用中的修正，它随着时间的推移而减少（无论是渐进的还是无限制的）。仔细实施，这可以保证，最终，任何一个结局都比另一个结局更好。对于这个解决方案，你需要小心考虑这对你的对手意味着什么偏好。

另一个常见的解决方案是深度限制你的搜索并实现一个评估函数。这将游戏状态作为其输入，并只是吐出一个效用值，这是它对最终结果的最佳猜测。这可以证明是最优的吗？不，除非你的评估函数只是完成极小极大，但这意味着你的算法将在合理的时间内完成。通过将这个粗略的估计埋在树中足够深的地方，你最终会得到一个非常合理的模型。然而，这会产生一个不完整的策略，这意味着它对重新规划代理比标准规划代理更有用。最小极大重新规划是复杂游戏的通常方法（如果我没弄错的话，它是深蓝遵循的基本算法），但是因为这是一个非常简单的游戏，你可能不需要采取这种方法。

请注意，所有这些解决方案都被概念化为对效用函数的数字更改或估计。一般来说，这比任意丢弃可能的策略更可取。毕竟，这就是你的效用函数的用途——任何时候你根据效用的数值以外的任何东西做出策略决策，你都在破坏你的抽象，使你的代码不那么健壮。