通过考虑所有情况，可以轻松解决小型（3x3、4x4）井字游戏。但例如，您有一个 30x30 的井字游戏。在这种情况下，你会使用什么算法来决定下一个最佳动作？
Minimax + alpha-beta 修剪是我知道的一种方法。
有没有其他更高效/不是更高效但更酷的方法？
我知道这不会是一个非常有趣的游戏。我说 30x30 只是为了问我想问什么，即哪种算法在这类游戏中效果最好，其中要考虑的完美解决方案的案例数量非常多，因此不可行。
问问题
7723 次
7 回答
7
我不认为这可能是一个非常有成果的问题。原因是：
如果您需要赢得的连续分数很高，那么（在我看来）游戏将在任何合理的技能水平下进行，因为阻止可能的胜利比自己取得胜利要容易得多。例如，如果您需要连续 20 人才能在 30x30 的棋盘上获胜，那么防止获胜所需的只是在棋盘中间附近的每行和每列上做一个标记，并在每行和每列的中间附近做一个标记。长对角线。
如果你需要赢得的连续标记数很少，我怀疑棋盘上的额外空间不会对策略产生太大影响，而第二个防守的唯一明智的策略将涉及在你的对手附近打球。因此，某种 alpha-beta 方法就可以了。
于 2009-10-09T18:05:25.180 回答
4
对于围棋游戏，这对计算机来说很困难，原因与 30x30 tic-tac-toe 困扰您的原因相同（请注意，我并不是说 30x30 tic-tac-toe 和围棋一样难，更直接的技术不适用），蒙特卡洛树搜索最近给出了很好的结果。
于 2009-10-09T17:56:43.373 回答
3
看看五子棋或五连冠。网络上有许多通用策略。维基百科的文章也有一篇关于使用 gomoku 进行基于威胁的搜索的好论文，您可能会看到。
于 2009-12-30T03:51:22.887 回答
0
使用贪心算法搜索最后一步的相邻空间并尝试在与相邻对手棋子对齐的任何空白空间中放下一个块不是很好吗？只要玩家不能赢，你就赢了。
于 2009-10-09T22:02:27.047 回答
0
Alpha Beta 绝对是您可以使用的最好的东西。Alpha beta 的重要性在于其评估功能。这不仅返回 1/0/-1（赢/无/输）（从一名玩家的角度来看），而且还返回位置质量。
查看这篇文章（他使用井字游戏，但主要使用国际象棋作为示例游戏） http://www.fierz.ch/strategy1.htm
于 2009-10-11T11:54:35.043 回答
-1
将第一个令牌放在第 3 行第 3 列。如果对手将他的令牌放在第 3 行，则将下一个令牌放在第 2 行第 3 列，否则放在第 3 行第 2 列。您应该能够弄清楚下一个（获胜） 移动。
如果对手开始，请选择一个空的 4x4 块并从中间开始，如上文所述。如果对手在你之前完成他的三倍，你就输了。
我敢说，这是 4x4 及以上板的最佳策略。
于 2009-10-09T18:04:35.747 回答