您会使用什么算法来解决非常大的井字游戏？
通过考虑所有情况，可以轻松解决一个小（3x3、4x4）井字游戏。但例如，您有一个 30x30 的井字游戏。在这种情况下，您会使用什么算法来决定下一个最佳行动？
Minimax + alpha-beta 修剪 是我所知道的一种方法。
是否有其他更高效/不是更高效但更酷的方法？
我知道这不会是一个非常有趣的游戏。我说 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 pruning is one way that I know.
Is there some other way that is more efficient/not more efficient but cooler?
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
我认为这可能不是一个富有成果的问题。原因是：
如果你需要赢得的连续分数很高，那么游戏（在我看来）将在任何合理的技能水平上进行平局，因为阻止可能的胜利比阻止可能的胜利容易得多自己实现一个。例如，如果您需要在 30x30 的棋盘上连续 20 局获胜，那么您需要防止胜利的只是在棋盘中间附近的每行和每列上做一个标记，并在每个棋盘的中间附近做一个标记。长对角线。
如果你需要赢得的连续分数很少，我怀疑棋盘上的额外空间不会对策略产生太大影响，并且是第二个玩家唯一明智的策略防守将涉及在你的对手附近进行比赛。因此，某种 alpha-beta 方法就可以了。
I don't think this is probably a very fruitful problem. Reason being:
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.
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.
对于围棋游戏，对于计算机来说很难，其原因与困扰您的原因相同30x30 tic-tac-toe（请注意，我并不是说 30x30 tic-tac-toe 与 Go 一样困难并且更直接的技术不适用），蒙特卡罗树搜索最近给出了很好的结果。
For the game of Go, which is difficult for computers for the same reasons that are troubling you for 30x30 tic-tac-toe (note that I am not saying that 30x30 tic-tac-toe is as difficult as Go and that more direct techniques do not apply), the Monte Carlo tree search has given good results recently.
看看五子棋或五连棋。网络上有许多通用策略。维基百科文章还有一篇关于使用五子棋进行基于威胁的搜索的好论文，您可以看看。
Take a look at Gomoku or Five in a row. There are a number of general strategies on the web. The wikipedia article also has a good paper on threat based search with gomoku that you might look at.
您可以使用基于规则的系统
规则比任何树搜索算法更快，并且可以与他们混合。
您可以自己创建规则或使用（例如）遗传算法
You can use Rule-based system
Rules are faster then any tree search algorithms and can be mixed with them.
You can create rules by yourself or use (for example) a Genetic algorithm
使用贪心算法来搜索最后一步的相邻空间并尝试在与相邻对手棋子内联的任何空白空间中放置一个块不是可以吗？只要玩家赢不了，你就赢了。
Wouldn't it be alright to use a greedy algorithm that searches the neighboring space of the last move and tries to put down a block in any empty space inline with an adjacent opponent piece? As long as the player can't win, you sort of do win.
将第一个令牌放在第 3 行第 3 列。如果对手将其令牌放在第 3 行，则将下一个令牌放在第 2 行第 3 列，否则放在第 3 行第 2 列。您应该能够算出下一个（获胜） ） 移动。
如果对手开始，请选择一个空的 4x4 块并从中间开始，如上所述。如果对手在你之前完成了三连，你就输了。
我敢说，这是 4x4 及以上棋盘的最佳策略。
Place the first token on row 3 column 3. If the opponent places his token on row 3, place the next token on row 2, column 3, otherwise on row 3, column 2. Your should be able to figure out the next (winning) move.
If the opponent starts, choose an empty 4x4 block and start in the middle like outlined above. If the opponent completes his triple before you, you lose.
I would dare to say, that this is an optimal strategy for 4x4 boards and above.
Alpha Beta 绝对是您可以使用的最好的东西。 Alpha beta 的重要性在于其评估函数。它不仅返回 1/0/-1（赢/无/输）（从一名玩家的角度来看），而且还返回位置质量。
查看这篇文章（他使用井字游戏，但主要是国际象棋作为示例游戏）
http://www.fierz.ch/strategy1.htm
Alpha Beta is absolutely the best thing you can use. Importance in Alpha beta is in its evaluation function. Which not return only 1/0/-1 (win/nothing/lost) (from one player point of view) but also qualty of position.
Check this article (he uses tic-tac-toe but mostly chess as example game)
http://www.fierz.ch/strategy1.htm