Gomoku array-based AI-algorithm?

Question

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?

Answer 1

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 :/

Answer 2

I haven't read the article, but from the description my guess would be some form of the Minimax algorithm

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

Working on an open source version for iPhone.

Hit me up if interested in joining!

https://github.com/kigster/kigomoku