What would be a good AI strategy to play Gomoku?

Question

I'm writing a game that's a variant of Gomoku. Basically a tic tac toe on a huge board.

Wondering if anyone knows a good AI strategy for the game. My current implementation is very stupid and takes a long time (O(n^3), approx 1-2 second to make a move):

-(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];
}

Solution 1

For gomoku, winning strategy has been already found. See this paper: L. Victor Allis, H. J. van den Herik, M. P. H. Huntjens, 1993. 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.

Solution 2

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!

Solution 3

I have been trying to create a algorithm for the same program for a while now.

You are of course correct that first thing Your program should do, is to check if there is a way to form a 5 and win. And if there is not, the next should be to check if Your opponent can do that, and if yes, then defense.

How much have You played gomoku Yourself? How good grasp You have of the basics?

Ok, next step is to think: how we can get to the positions where we can win? Obviously, to win we must have four in a row. But it we just form four in a row like this:

__________
____XOOOO_
__________

Then opponent can close it.

But if we form "open four", like this:

__________
____OOOO__
__________

Then opponent cannot close both sides and You can win. So forming an open four is one way to win. Now comes the question: how can we form an open four? Surely, if we form "open three", like this:

__________
____OOO___
__________

Then opponent can block us:

___________
____XOOO___
___________

and we are back to the start.

To win, we can form two open threes at the same time:

____________
____OOO_____
_____O______
____O_______

Now if opponent blocks one of them, we can use the other to form an open four:

____________
_______O____
___XOOO_____
_____O______
____O_______
____________

and win:

________O___
_______O____
___XOOO_____
_____O______
____O_______
___X________

In gomoku terms, this is called 3x3, if You make two open threes at the same time.

Notice that both threes must be open: can You understand why?

There are other ways to win, too:

4x3: Do You see the winning move and why it is winning?

____________
__XOOO______
__XXXO______
____OX______
____________

4x4: See the winning move?

____________
__XOOO______
__XXXO______
__OXOX______
___O________
__X_________

These are just the basics of the game. Knowing the tactics helps You to think how to build the AI, so You can hard-code the principles.

Naturally, this is just the beginning. I would appreciate if You could try to implement this and then give feedback to me.

I have been trying to write the program in Java. Would You like to see the code I have done so You can playtest? It is not very good yet, but You could get new ideas from there. Although the comments and variable names are written in Estonian.. it might be very difficult to understand. :(

Solution 4

Gomoku is solved, but it is not solved when it is played with opening position and limited resources.

I am author of Hewer gomoku program and Gomocup organizer and I can tell you that it takes you very long time to write good Gomoku AI. Renju is much more complicated. You can simplify your job using Gomocup interface and write 'only' AI.

Solution 5

I created a gomoku player once and it was quite succesful using alpha-beta pruning and giving each position a score dependent on how many half-open and fully open 2s, 3s and 4s each player had.

Calculating this is not n^3. You just check if the latest move closes any of your opponents lines and if it extends some of your lines, then modify the score accordingly.

If you need it to play even better, I would look into some techniques from chess computers. For example, trying "killer moves" (remembering which moves gave a high score or won outright in other positions) first when you search will significantly improve the efficiency of your tree search. It is important to try the assumed best moves first in alpha-beta pruning.

When you have your player, you should try to find out which scoring of the different elements (2s, 3s, 4s, open and half-open, etc) is best, by playing different versions against each other.

View more solutions

Comments

[Rauni Lillemets]

Good comment. One thing, though: calculating the end-games is not realistic in Gomoku. It works in chess or checkers where end-games are significantly easier to calculate due to fact that there are only few game pieces left. In gomoku, on the other hand, the number of pieces grows (every move is new piece), so it does not work.

[Rauni Lillemets]

One thing to note: gomoku is solved, but the more advanced version of it, renju, is not. Renju basically adds openings and forbidden rules to the game to balance it more. But to write a good renju program, You have to first write a good gomoku program :)

[Enrico Susatyo]

Wow thanks very much Tomas! I'm actually writing quite a significant variant to Gomoku, basically the game does not end when one got five in a row. The game ends when someone scores 5 points. So in this case there might be a few things that is different (e.g. if you see someone with 4 open, don't bother and just try to score with our own pieces).

[Rauni Lillemets]

@the_great_monkey Maybe You could write more about the game You are writing AI for? As You said, the game does not end when one gets 5 in a row - that makes my previous answer on Gomoku tactics useless. :)

[Enrico Susatyo]

@Rauni No, in fact your answer actually helped quite a lot. One of the key point that I get from all the answers is that I only need to look at the last move from my opponent. My previous algorithm checks the whole board (that's why it took O(n^3)), but checking only if the last move made an open-3 or open-4 made the algorithm much more efficient.

[Peter Porfy]

@Rauni only the standard version of gomoku is solved. swap2 is not. and swap2 is the standard for professional gomoku.

[user1604015]

qub1n: can you expand on what "opening" and "limited resources" mean in this context. Put more generally: what are the interesting unsolved problems in the analysis of gomoku and related games?

[Tomas Kubes]

Limited resources means limit to memory and limit to time. I like the rules in Piskvork (sourceforge.net/projects/piskvork) tournament manager. The players are playing two games with limited memory, time limit to move and game. If it is draw, then the winner is AI which spent less time on 'thinking'.

[Eerik Sven Puudist]

Yes, I think it would be beneficial if you could share your code.