6

我正在尝试使用迭代 Alpha-Beta 修剪来玩井字游戏，我的移动有一秒钟的限制，但由于某种原因它不能很好地工作。

我修改了常规的 alpha-beta 代码，因此它不是返回 alpha 或 beta，而是返回一个状态（这是下一步的棋盘）

每次我创建孩子时，我都会更新他们的深度。

但是由于某种原因，我一直在输，我看到我的 alpha beta 没有看到最好的举动。

这是我的代码：

外循环：

while (watch.get_ElapsedMilliseconds() < 900 && d <= board.length * board[0].length - 1)
        {
            s = maxiMin(beginSt, d, watch);
            if (s.getNextMove().getIsWin() == true)
            {
                break;
            }
            d++;
        }
        return new location(s.getNextMove().getRow(), s.getNextMove().getCol());

阿尔法贝塔：

public State maxiMin(State s, int depth, Stopwatch timer)
    {
        if (s.getDepth() == 7)
        {
            Console.WriteLine();
        }
        if (timer.get_ElapsedMilliseconds() > 850 || s.getDepth() == depth || goalTest(s.getBoard()) != 0)
        {
            s.evaluationFunc(line_length, PlayerShape);
            s.setAlpha(s.getEvaluation());
            s.setBeta(s.getEvaluation());
            return s;
        }
        LinkedList<State> children = createChildren(s, true);
        // No winner, the board is full
        if (children.get_Count() == 0)
        {
            s.evaluationFunc(line_length, PlayerShape);
            s.setAlpha(s.getEvaluation());
            s.setBeta(s.getEvaluation());
            return s;
        }
        while (children.get_Count() > 0)
        {
            State firstChild = children.get_First().get_Value();
            children.RemoveFirst();
            State tmp = miniMax(firstChild, depth, timer);
            int value = tmp.getBeta();
            if (value > s.getAlpha())
            {
                s.setAlpha(value);
                s.setNextMove(tmp);
            }
            if (s.getAlpha() >= s.getBeta())
            {
                return s;
            }
        }
        return s;
    }

    public State miniMax(State s, int depth, Stopwatch timer)
    {
        if (s.getDepth() == 7)
        {
            Console.WriteLine();
        }
        if (timer.get_ElapsedMilliseconds() > 850 || s.getDepth() == depth || goalTest(s.getBoard()) != 0)
        {
            s.evaluationFunc(line_length, PlayerShape);
            s.setAlpha(s.getEvaluation());
            s.setBeta(s.getEvaluation());
            return s;
        }
        LinkedList<State> children = createChildren(s, false);
        // No winner, the board is full
        if (children.get_Count() == 0)
        {
            s.evaluationFunc(line_length, PlayerShape);
            s.setAlpha(s.getEvaluation());
            s.setBeta(s.getEvaluation());
            return s;
        }
        while (children.get_Count() > 0)
        {
            State firstChild = children.get_First().get_Value();
            children.RemoveFirst();
            State tmp = maxiMin(firstChild, depth, timer);
            int value = tmp.getAlpha();
            if (value < s.getBeta())
            {
                s.setBeta(value);
                s.setNextMove(tmp);
            }
            if (s.getAlpha() >= s.getBeta())
            {
                return s;
            }
        }
        return s;
    }

如果有人能告诉我是否有问题，我会非常感激。我怀疑这可能与我返回“s”而不是返回评估的常规 alpha beta 有关，但我没有设法找到错误。

提前致谢，

莉娜

4

1 回答 1

5

首先井字游戏是一个非常简单的游戏，我相信它可以用更简单的代码来解决，主要是因为我们知道总有一个平局选项，并且状态总数少于 3^9（包括对称和许多不可能的状态）。

至于您的代码，我相信您的问题之一是您似乎没有增加递归调用的深度。

您的代码中也存在许多不良风格的问题，您将 miniMax 和 MaxiMin 分成两个函数，尽管它们基本相同。您可以通过从中删除元素来迭代集合，而不是使用 for-each 或迭代器（甚至是 int 迭代器）。

于 2010-02-16T19:16:26.173 回答