您将使用什么算法来解决一个非常大的井字游戏？ [英] What algorithm would you use to solve a very large tic-tac-toe game?

问题描述

考虑所有情况，可以轻松解决一个小的（3x3、4x4）井字游戏。但是，例如，您有一个30x30的井字游戏。在这种情况下，您将使用哪种算法来决定下一个最佳动作？

A small (3x3, 4x4) tic-tac-toe can be easily solved by considering all the cases. But for example, you have a 30x30 tic-tac-toe. What algorithm would you use to decide the next best move in that case?

Minimax + alpha-beta修剪是我所知道的一种方法。

Minimax + alpha-beta pruning is one way that I know.

还有其他更有效/更不高效但更凉爽的方法吗？

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

I know it would not be a very interesting game to play. I said 30x30 just to ask what I wanted to i.e. which algorithms work best at these sort of games where the number of cases to consider for a perfect solution is very very high and thus not feasible.

推荐答案

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

I don't think this is probably a very fruitful problem. Reason being:

• 如果连续要赢的分数很高，那么游戏将会（似乎我）以任何合理的技能水平被吸引，因为阻止可能的胜利要比自己取得胜利容易得多。例如，如果您需要在30x30的木板上排成一排才能赢得胜利，那么要防止胜利，您所要做的就是在木板中间附近的每一行和每一列上都留下一个标记，而在木板中间附近则留下一个标记。长对角线。

• If the number of marks in a row you need to win is high, the game will (it seems to me) be drawn at any reasonable level of skill, because it's much easier to prevent a possible victory than to achieve one yourself. For example, if you need 20-in-a-row to win on a 30x30 board, all you need to prevent victory is a mark on each row and column roughly near the middle of the board, and a mark near the middle of each long diagonal.

如果您需要赢得的连续记分数量很少，我怀疑板上多余的空间不会策略上的差异很大，第二名球员防守的唯一明智策略是在对手附近打球。因此，可以使用某种alpha-beta方法。

If the number of marks in a row you need to win is low, I suspect that the extra space on the board isn't going to make much of a difference in strategy, and the only sensible strategy for the second player to defend will involve playing near your opponent. As a result, some kind of alpha-beta method is fine.

这篇关于您将使用什么算法来解决一个非常大的井字游戏？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！