基于五子棋阵列的人工智能算法？
很久以前（想想 20 多年前），我在一本杂志上遇到了五子棋游戏源代码，我在电脑上输入了它，并从中获得了很多乐趣。
这场比赛很难赢，但计算机AI的核心算法非常简单，并没有占很多代码。我想知道是否有人知道这个算法并且有一些关于它的来源或理论的链接。
我记得的是它基本上分配了一个覆盖整个板的数组。然后，每当我或它放置一个棋子时，它都会向棋盘上该棋子可能影响的所有位置添加一些权重。
例如（请注意，权重肯定是错误的，因为我不记得了）：
1 1 1
2 2 2
3 3 3
444
1234X4321
3 3 3
2 2 2
1 1 1
然后它只是扫描数组以查找具有最低或最高值的开放位置。
我模糊的事情：
- 也许它有两个数组，一个给我，一个给它自己，并且有一个最小/最大权重？
- 该算法可能还有更多内容，但其核心基本上是一个数组和加权数字。
这是否引起了任何人的注意？有人有什么可以帮忙的吗？
Way way back (think 20+ years) I encountered a Gomoku game source code in a magazine that I typed in for my computer and had a lot of fun with.
The game was difficult to win against, but the core algorithm for the computer AI was really simply and didn't account for a lot of code. I wonder if anyone knows this algorithm and has some links to some source or theory about it.
The things I remember was that it basically allocated an array that covered the entire board. Then, whenever I, or it, placed a piece, it would add a number of weights to all locations on the board that the piece would possibly impact.
For instance (note that the weights are definitely wrong as I don't remember those):
1 1 1
2 2 2
3 3 3
444
1234X4321
3 3 3
2 2 2
1 1 1
Then it simply scanned the array for an open location with the lowest or highest value.
Things I'm fuzzy on:
- Perhaps it had two arrays, one for me and one for itself and there was a min/max weighting?
- There might've been more to the algorithm, but at its core it was basically an array and weighted numbers
Does this ring a bell with anyone at all? Anyone got anything that would help?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
阅读您的描述并思考一下，我认为它可能适用于单个数组，正如您所描述的那样。
为了实现五连胜的目标，你必须 (a) 阻止对手成功，以及 (b) 自己成功。
为了让自己取得成功，你必须将棋子放置在棋盘上已有的其他棋子附近，因此为你的棋子旁边可以连续参与的区域添加正分是有意义的。您给出的线性示例或二次示例可能会效果很好。
为了防止对手成功，您必须将棋子放在他/她棋子旁边。如果你用一颗石头击中两只鸟，那就特别好，所以对手的石头应该像你的一样增加周围区域的价值——他已经排列的石头越多，得分就越高，更有可能算法会尝试切断对手。
这里最重要的是不同领域的权重，以及对手的棋子的权重是否与你的不同。不幸的是我对此无能为力，但是一旦游戏本身编写完毕，这些值应该相当简单，可以通过反复试验来找出。
然而，这是一种非常基本的方法，树搜索算法的性能会优于它。搜索 Google，有一篇相关的关于威胁搜索的论文，显然对五子棋很有效。不过，这篇论文是付费墙后面的：/
Reading your description, and thinking a little about it, I think it probably works with a single array, exactly the way you described.
To accomplish the goal of getting five-in-a-row you have to (a) prevent the opponent from succeeding and (b) succeed yourself.
To succeed yourself, you have to place stones near other stones you already have on the board, so it makes sense to add a positive score for fields next to your stones that could participate in a row. Either the linear example you gave, or something quadratic would probably work well.
To prevent your opponent from succeeding, you have to place stones next to his / her stones. It's especially good if you strike two birds with a single stone, so opponent's stones should increase the value of the surrounding fields the same way yours do -- the more stones he already has lined up, the higher the score, and the more likely the algorithm will try to cut the opponent off.
The most important thing here is the weighting of the different fields, and whether the opponent's stones are weighted differently than yours. Unfortunately I can't help with that, but the values should be reasonably simple to figure out through trial and error once the game itself is written.
However this is a very basic approach, and would be outperformed by a tree search algorithm. Searching Google, there's a related paper on Threat search, which apparently works well for Gomoku. The paper is behind a pay-wall though :/
我还没有读过这篇文章，但从描述中我猜测是 Minimax 算法的某种形式
I haven't read the article, but from the description my guess would be some form of the Minimax algorithm
我看到了你提到的这个算法 - 它非常简单和快速（没有回溯:-)）并且运行得很好:-)我一定在某个地方有源代码，但那是很多年前了......你的石头有重量取决于附近有多少其他棋子，以及对手棋子的重量。这些较低，因此算法首选攻击策略。
但这当然是非常简单的算法。制胜策略已经找到。
请参阅本文：L.维克多·艾利斯、HJ·范·登·赫里克、MPH Huntjens。 Go-Moku 和威胁空间搜索。当我编写自己的程序时，它对我帮助很大。通过这种方式，您将能够编写非常擅长攻击对手并找到获胜组合的程序。
I saw this algorithm you mentioned - it was pretty simple and fast (no backtracking :-)) and it played very well :-) I must have the source somewhere but it is a lot years ago... There were weights for your stones depending on how much of other stones were near, and weights of oponent stones. These were lower so the algorithm preferred the attacking strategy.
But this is of course very trivial algorithm. Winning strategy has been already found.
See this paper: L. Victor Allis, H. J. van den Herik, M. P. H. Huntjens. Go-Moku and Threat-Space Search. It helped me a lot when I was writting my own program. This way you'll be able to write program which is very good in attacking the opponent and finding winning combinations.
这是一个古老的游戏 - 我在 Planet Source 上找到了代码代码。我在大学期间玩过这个游戏，并在 286 天之内得到了它的 BASIC 版本。
It's an ancient game - I found the code on Planet Source Code. I played this game during college and in 286 days had a BASIC version of it.
这是您正在寻找的程序
ftp://ftp.mrynet.com/USENIX/80.1/boulder/dpw /gomoku.c
快40岁了
Here is the program you are looking for
ftp://ftp.mrynet.com/USENIX/80.1/boulder/dpw/gomoku.c
It is almost 40 years old
正在开发 iPhone 的开源版本。
有兴趣加入就联系我吧！
https://github.com/kigster/kigomoku
Working on an open source version for iPhone.
Hit me up if interested in joining!
https://github.com/kigster/kigomoku