1

我有表格和一些函数，如 Generate_moves() 等，但要使 minmax 算法起作用，我需要为表格设置分数，以使计算机选择最佳表格。

        public int Score()
        {
            if (Turn == "X")
            {
                if (gameWon("X")) return 100;
                if (gameWon("O")) return -100;
                if (gameDrawn()) return 0;

                return n - canWin("X");
            }

            if (Turn == "O")
            {
                if (gameWon("O")) return 100;
                if (gameWon("X")) return -100;
                if (gameDrawn()) return 0;

                return n - canWin("O");
            }

            return -1;
        }

MycanWin(string)返回一个数字，告诉我在一条直线或一列中有多少个 X 或 Os，但我怀疑这是为表格设置分数的一个很好的原因。

如果我有桌子：

X - X
0 X 0
- - 0

分数应该与

X - -
0 - X
0 0 X

并且应该大于

X - X
0 - -
- 0 -

而且我不知道如何让 Score 函数告诉我不同​​的分数。我怎样才能实现方法 Score 来告诉我这个？

编辑：

如果计算机首先是 X 而我是 O

X - -      X - -      X - -     X - -
- - -   -> 0 - -   -> 0 X -  -> 0 X -
- - -      - - -      - - -     - - 0

现在我怎样才能让计算机选择下一个最佳选项

X - X
0 X -
- - 0
4

5 回答 5

1

I think you are overcomplicating things. There are less than 400,000 possible Tic-tac-toe games - in fact, Tic-tac-toe is simple enough that you can write down the best moves for every possible game on a single sheet of paper

(complete tic-tic-toe map) - XKCD

Even an algorithm as simple as minmax is overkill - just check all possible moves by brute-force. It should only take a few milliseconds on a modern PC.

于 2012-02-08T18:01:46.547 回答
1

Tic-Tac-Toe 是一种相对简单的计算机游戏 - 因为分支因子和可能性的数量相对较小，因此：最好创建最容易 [计算] 可能的启发式函数，并让 minmax 达到最深一层，博弈树的叶子，都是一定的输赢。

如果您仍在寻找启发式方法，则可以使用number of rows/cols/diagonals with exactly 2 "X"s and left square is empty

尽管如此，我仍然认为 [对于这个特定问题] 一个 minmax 算法，它返回 -1 表示失败，1 表示获胜，0 表示所有其他可能性会表现得更好 - 因为它会更快地到达游戏的叶子，因此会更了解任何启发式。

于 2012-02-08T14:09:07.533 回答
0

一种可能性...分数 = 赢得 x 的剩余方式数（行、列或对角线仍然可以填充到获胜状态） - 对于每个不是叶子的状态（最终状态）赢得 0 的剩余方式数) 对于叶子状态，您只有 Score = 1、0 或 -1

于 2012-02-08T14:14:02.000 回答
0

我知道你在说什么。你需要的是一个好的启发式函数。你可以从这里找到启发式函数（我没有尝试任何一个）：

使用 MiniMax 算法解决井字游戏

Visualgos：井字游戏

于 2013-01-28T08:02:44.663 回答
0

回答你的第二个问题：

现在我怎样才能让计算机选择下一个最佳选择是......

这是极小极大算法的任务。它从游戏树中窥探了最好的举动。对于井字游戏，您不需要非常复杂的评估函数，如果玩家赢了，则返回正值或负值就足够了，否则返回0。如果你愿意，你可以通过评估一个玩家是否可以在下一步中获胜来扩展它。在具有更大分支因子的游戏中需要更复杂的评估函数，并且游戏树可以变得更深（不仅仅是 9 步）。
我的经历*就是说，由于更智能的评估函数，在博弈树搜索中深入一层会比不达到这一层（同时）产生更好的结果。由于简单的评估或由于复杂的评估而不那么深入的搜索，区分更深的搜索并不容易。minimax 算法还有很多其他重要的改进很有希望，不要陷入复杂的评估，首先考虑：

之后您仍然可以改进评估功能。评估的其他一些想法：也许最好在函数中做一些工作makeMove，这里你只需要检查一个（而不是全部）行、一列和一两条对角线。然后，在当前板旁边，保留从该检查中获得的信息。此信息包括，如果这是一个获胜的举动（设置分数），或者是否强迫其他玩家的下一步行动（记住下一个玩家必须做出的移动，getMoves只会返回这个移动）。最后但并非最不重要的一点是，如果一列/行和一条对角线包含强制移动，则玩家在两步中获胜（保持得分）。

祝你的评估功能好运！

* 前段时间我在做一个Connect-Four-Game-Engine的评估函数。评估连接四板的最佳方法是分析奇数和偶数威胁，如James D. Allen的四连接中的文章专家游戏的“威胁分析”一章中所述。该算法分析了主要和次要威胁。去掉次要威胁分析部分后，alpha-beta 搜索表现更好！

于 2012-02-08T21:18:43.667 回答