What would be a good AI strategy to play Gomoku?

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开发者_如何学C-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];
}

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.

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!

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.

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. :(

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.

I too have created my Gomoku player. It is not perfect, but it plays quite decent game and it is certainly better player than me. Anyway, I found that:

• If a player will be using a depth search, the search for the right move should be limited to certain board positions. A naive way would be to search only the neighbouring positions to the stones. Another way is to include only the moves which produces a "threat", for example open 2s, open 3s and others. Then include only the defensive moves which blocks the attacking moves. This heuristic significantly reduces the number of nodes to search. If I understand correctly, a similar approach to reduce the search space was used to solve Gomoku.
• Yet Gomoku branching factor is high and if the player does not find the winning sequence, it has to take the "best" of the possible moves. Heuristic to define what is the "best" is very important for the AI player to work.

So, my Gomoku player evaluates all board positions with no depth search. It divides horizontal, vertical and diagonal board lines into strings. Then searches the table for the patterns in those strings. For the black player some of the patterns are:

1. xxxxx : score 10000000000
2. -xxxx- : 9999999
3. -xxx- : 50
4. -xx- : 500
5. ooooo : -100000000
6. -oooo- : -99999999
7. -ooo-- : -999999
8. -oo- : -2000

X's mark the black players stones, O's mark the white player stones and "-" mark the empty positions. The player sums all the patterns found and makes the highest score move found.