什么样的算法你会用来解决一个非常大的井字游戏吗？

Question

一个小(3x3，4×4)井字游戏，可以很容易解决，通过考虑所有的案件。但例如，你有30×30井字游戏.什么样的算法你会用来决定未来的最佳移动在这种情况下?

Minimax + alpha beta修剪 是的一种方式，我知道。

是否有其他一些方式，更有效/无效率更高，但却器?

---

我知道这不会是一个非常有趣的游戏。我所说的30×30只是问什么我想即这算法的工作最好在这种游戏在哪些情况下需要考虑的一个完美的解决方案是非常非常高，因此不可行的。

Answer 1

我不认为这可能是一个非常富有成果的问题。原因是：

• 如果数量的标记在行你需要赢得很高，游戏会(它似乎对我来说)可在任何合理的技术水平，因为它更加容易，以防止可能的胜利于实现一个自己。例如，如果您需要20个行赢得对30×30板，你所需要防止的胜利是一个标记每个行和列的大约中间附近，标记附近的中间每长的对角线。

• 如果数量的标记在行你需要赢得低，我怀疑这一额外空间委员会是不会有太大的差异战略，唯一的明智战略的第二播放器来保卫将涉及附近玩耍你的对手。结果，某些种类的alpha beta方法是好的。

Answer 2

有关围棋游戏，这是难以计算机了解是相同的原因麻烦您30X30井字棋（注意，我不是说30×30井字棋是围棋的困难，而且更直接的方法不适用），将的蒙特卡洛树搜索最近得到良好结果。

Answer 3

取在一排看看五目或五。有许多在网络上一般策略。维基百科的文章还对与五子棋基于威胁的搜索，你可能会看到一个很好的文件。

Answer 4

可以使用基于规则的系统

规则是更快然后任何树搜索算法，并且可以相互混合。 可以通过自己创建的规则或使用（例如）一个遗传算法

Answer 5

岂不是好吗使用贪婪算法，搜索的最后移动的相邻的空间，并试图放下一个块中的任何空的空间内联与相邻的对手件？只要玩家赢不了，你有点不赢。

Answer 6

α+β绝对是你可以使用的最好的事情。重要性，α，β是其评价职能。这不仅返回1/0 / -1（赢/没有/丢失）（从一个播放机的角度来看），而且还的位置评定中。

检查本文（他使用井字棋但大多是国际象棋作为示例游戏） http://www.fierz.ch/strategy1.htm

Answer 7

放在第3行3列的第一个标记。如果对手放在3排他的道理，把第2行，第3列的下一个标记，否则在3行，列2.你应该能够找出下（获奖）移动。

如果对手开始时，选择一个空4×4块，并开始在中间像上面概述。如果对手在你面前完成他的三倍，你输了。

我敢说，这是对于4×4板的最优策略和上方。