0

我创建了一个棋盘游戏，我希望计算机计算出最优化的移动。这是我到目前为止所做的：

public BoardS calcNextMove(BoardS bs)
{
    ArrayList<BoardS>options = calcPossibleOptions(bs);
    int max = -1;
    int temp;
    int bestMove = 0;

    for(int k=0;k<options.size();k++)
    {
        temp = calculateNextMove2(options.get(k));
        if(max<temp)
        {
            max = temp;
            bestMove = k;
        }
    }
    return options.get(bestMove);
}

public int calculateNextMove2(BoardS bs)
{
    int res = soWhoWon(bs);

    if(res == 2) //pc won(which is good so we return 1)
        return 1;
    if(res == 1)
        return 0;

    ArrayList<BoardS>options = calcPossibleOptions(bs);

    int sum = 0;
    for(int k=0;k<options.size();k++)
    {
        sum += calculateNextMove2(options.get(k));
    }
    return sum;
}

我不断得到

线程“AWT-EventQueue-0”中的异常 java.lang.StackOverflowError

calcPossibleOptions 效果很好，它是一个返回所有可能选项数组的函数。

BoardS 是一个代表游戏板的类。

我想我必须让它更有效率，怎么样？

4

2 回答 2

0

您将需要找到 MinMax 的替代方案，即使最有可能进行 alpha-beta 修剪，因为棋盘太大，导致太多可能的移动和反移动。这会导致堆栈溢出。

我很惊讶地看到为井字游戏制作完整的决策树并没有让我自己溢出，但恐怕我对人工智能规划或解决这些问题的其他算法了解不够，无法帮助你除此之外。

于 2013-04-06T15:03:45.540 回答
0

“calculateNextMove2()”的递归将运行得太深，这就是你得到 StackOverFlow 的原因。如果您希望游戏进行到最后（除非相对接近实际胜利），这可能确实需要很长时间。就像国际象棋一样（我有更多的经验），一个引擎可能会走 20 步，然后你可能会使用它迄今为止发现的东西。如果你从一局国际象棋游戏开始就运行它......它可以运行 100 年以当前的技术（仍然不能真正说出获胜的第一步是什么）。也许只是尝试 10 或 20 步深度？（它仍然会击败大多数人——并且仍然可能被归类为“最佳移动”）。与国际象棋一样，您将很难评估一个位置的好坏（通常计算为物质优势和位置优势的组合）。这是棘手的部分。注意：奇努克项目已经完成了您想要实现的目标 - 它已经“击败”了西洋跳棋游戏（国际象棋还没有这样的东西编辑：Magnus Carslen 出于所有意图和目的已经“击败”了游戏：D）。

请参阅：Alpha-beta pruning （它可能会有所帮助）

这里还有一篇我在这个主题上看到的（旧的）论文：

Graham Owen 1997 Search Algorithms and Game Playing （可能有用）

另请注意，返回导致“获胜”的第一步是“幼稚的”——因为这可能是一个完全不可能的移动路线，如果对手不参加非常特别的胜利，他们将获得优势——例如国际象棋中的傻瓜伴侣或学者伴侣......（快速但非常受惩罚）

于 2013-04-06T15:07:31.467 回答