What would be a good AI strategy to play Gomoku?

user_361247 0
Viewed 46790

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];
}
gomoku minimax artificial-intelligence
6 Answers

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.

user_143415120
Related