我正在编写一个游戏，它是Gomoku的变体。基本上是一个巨大的棋盘上的井字游戏。
想知道是否有人知道该游戏的良好 AI 策略。我当前的实现非常愚蠢并且需要很长时间（O（n ^ 3），大约1-2秒才能采取行动）：
-(void) moveAI {
//check if the enemy is trying to make a line horizontally, vertically, or diagonally
//O(n^3 * 3)
[self checkEnemies];
//check if we can make a line horizontally, vertically, or diagonally
//O(n^3 * 3)
[self checkIfWeCanMakeALine];
//otherwise just put the piece randomly
[self put randomly];
}
对于五子棋，已经找到了获胜的策略。请参阅这篇论文：L. Victor Allis、HJ van den Herik、MPH Huntjens，1993。Go-Moku 和威胁空间搜索。当我编写自己的程序时，它帮助了我很多。这样，您将能够编写非常擅长攻击对手并找到获胜组合的程序。
The traditional and rather effective strategy for writing AI for such games is the typical tree search strategy. That is, each board state forms a node in a graph, and a directed edge is placed between each node and states that can be resulted by a single move. In this way a tree is built with the root board being an empty node. Then, traverse the tree in some clever way to find what looks like a 'good' state. A 'good' state is usually measured by an evaluation function that uses some clever heuristics. Obviously you don't want to visit all the nodes in the tree -- that would be a lot of work! You just want something clever.
You can add in a pre-computed early game and end-game to speed up those scenarios and then rely on a well-optimized tree-traversal heuristic for the mid game.
The actual name of such tree traversal algorithms is the "Minimax" algorithm. Look for it on Wikipedia and you'll see a lot of rather decent material. There's some ways of boosting the efficiency of the algorithm, the most notable of which alpha-beta pruning, so be sure you take a look at that. You may want to take a look at connect-four heuristics and decide how you can apply them to your game. For example, a likely good heuristic for evaluation of board states would be to count the number of continuable 2-runs, 3-runs, and 4-runs and weight them into the score. (e.g. each 2-run would be worth 1 point, each 3 run would be worth 10 points, and each 4-run would be worth 1000 points)
Another optimization strategy is to develop a heuristic that prioritizes where the minimax algorithm should search more -- usually by estimating some sort of certainty of the board evaluation function.
With this strategy you should be able to get not-so-stupid AI in the same amount of time. However, really, really good AI takes a lot of effort to build, even in these sorts of "simple" games, and it still may take upwards of 10 seconds or more to get smart moves out of the way. On the other hand, there's some clever programming tricks such as pre-computing traversals through the tree while the human opponent is busy thinking. Hey, humans get to think while the computer does. Fair is fair!
一段时间以来，我一直在尝试为同一个程序创建算法。
你当然是正确的，你的程序应该做的第一件事就是检查是否有办法形成 5 并获胜。如果没有，接下来应该检查你的对手是否可以做到，如果可以，然后防守。
你自己玩过多少五子棋？怎么掌握好你的基础知识？
好的，下一步是思考：我们如何才能到达我们可以获胜的位置？显然，要赢，我们必须连续四场比赛。但是我们只是像这样连续形成四个：
__________
____XOOOO_
__________
然后对手可以关闭它。
但是如果我们形成“开四”，像这样：
__________
____OOOO__
__________
然后对手不能关闭双方，你可以赢。因此，形成开放式四人组是获胜的一种方式。现在来了一个问题：我们如何形成一个开放的四？当然，如果我们形成“开三”，像这样：
__________
____OOO___
__________
然后对手可以阻止我们：
___________
____XOOO___
___________
我们又回到了起点。
要赢，我们可以同时形成两个空位三分：
____________
____OOO_____
_____O______
____O_______
现在如果对手阻挡其中一个，我们可以使用另一个形成一个开放的四：
____________
_______O____
___XOOO_____
_____O______
____O_______
____________
并赢得：
________O___
_______O____
___XOOO_____
_____O______
____O_______
___X________
用 gomoku 术语来说，这称为 3x3，如果你同时投进两个空位三分球。
请注意，两者都必须打开：您能理解为什么吗？
还有其他获胜方式：
4x3：你看到获胜的举动了吗？为什么获胜？
____________
__XOOO______
__XXXO______
____OX______
____________
4x4：看到制胜法宝了吗？
____________
__XOOO______
__XXXO______
__OXOX______
___O________
__X_________
这些只是游戏的基础。了解策略可以帮助您思考如何构建 AI，因此您可以对原则进行硬编码。
当然，这只是开始。如果您能尝试实现这一点，然后向我提供反馈，我将不胜感激。
我一直在尝试用 Java 编写程序。你想看看我做的代码，这样你就可以玩测试了吗？它还不是很好，但你可以从那里得到新的想法。虽然注释和变量名是用爱沙尼亚语写的.. 可能很难理解。:(
五子棋是解决了，但是在开局和资源有限的情况下玩它并没有解决。
我是Hewer gomoku程序和Gomocup组织者的作者，我可以告诉你，编写好的 Gomoku AI 需要很长时间。连珠要复杂得多。您可以使用Gomocup界面简化您的工作并编写“仅”AI。
我曾经创建了一个五子棋玩家，它使用 alpha-beta 修剪非常成功，并且根据每个玩家拥有的半开和全开 2s、3s 和 4s 给每个位置打分。
计算这不是 n^3。您只需检查最新的移动是否关闭了您的任何对手线，如果它延伸了您的一些线，然后相应地修改分数。
如果你需要它玩得更好，我会研究一些国际象棋计算机的技术。例如，在搜索时先尝试“杀手招式”（记住哪些招式得分高或在其他位置上直接获胜）将显着提高树搜索的效率。在 alpha-beta 修剪中首先尝试假设的最佳移动是很重要的。
当你拥有你的球员时，你应该尝试找出不同元素（2s、3s、4s、开场和半开场等）的得分最好，通过相互对战不同的版本。
我也创建了我的五子棋播放器。它并不完美，但它玩得相当不错，而且它肯定是比我更好的球员。无论如何，我发现：
所以，我的五子棋玩家评估所有棋盘位置，没有深度搜索。它将水平、垂直和对角的板线分成字符串。然后在表格中搜索这些字符串中的模式。对于黑人玩家，一些模式是：
X 标记黑棋子，O 标记白棋子，“-”标记空位。玩家将找到的所有模式相加，并找到最高分的移动。