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

Question

一个小的 (3x3, 4x4) tic-tac-toe 可以通过考虑所有情况轻松解决。但是，例如，您有一个 30x30 的井字棋。在这种情况下，您将使用什么算法来决定下一个最佳着法？

Minimax + alpha-beta pruning是我知道的一种方式。

有没有其他更高效/不是更高效但更酷的方法？

---

我知道这不是一个非常有趣的游戏。我说 30x30 只是想问我想要什么，即哪种算法在这类游戏中效果最好，在这些游戏中需要考虑完美解决方案的案例数量非常多，因此不可行。

Answer 1

我认为这可能不是一个很有成果的问题。原因是:

• 如果您需要赢得的连续分数很高，游戏将(在我看来)以任何合理的技能水平绘制，因为阻止可能的胜利比阻止可能的胜利容易得多自己实现一个。例如，如果您需要连续 20 次才能在 30x30 的棋盘上取胜，您需要防止获胜的唯一方法是在每行和每列大致靠近棋盘中间的地方做一个标记，并在每个行和列的中间附近做一个标记长对角线。

• 如果您需要赢得的连续标记数很少，我怀疑棋盘上的额外空间不会对策略产生太大影响，而且唯一明智的策略是第二个防守球员将涉及在你的对手附近打球。因此，某种 alpha-beta 方法就可以了。