Minmax algorithm, search time and search depth compromise and acceptability

Question

Currently working on Gomoku AI implementation with minmax + alpha beta implementation.

I'm targeting these two rules from 'acceptable implementation' in terms of search time and search depth :

• Search time (over 0.5 seconds is "bad", less 0.5 seconds is ok)
• Search depth (less than 10 search depth levels is "bad", over 10 search depth levels is ok)

---

The minmax algorithm generates, by recursive function calls, a tree of nodes, each node represented by a function call with a specific game state.

Increasing the depth search increases the number of nodes in the tree, and therefore search time.

There is a compromise between search time and search depth.

Alpha beta pruning tends to help this compromise by pruning useless nodes search and reducing tree size. The pruning is directly related to evaluation/heuristic function. Bad implementation of heuristic may lead to bad efficiency of alpha beta pruning.

---

QUESTION

If you are workin on or have done a Gomoku AI, sharing your stats of tree size, search depth and time search from your implementation at some game steps, and explain how you reach it may help to investigate.

---

The implementation at this time does not fit the 'is not acceptable' for me, having search time over 1sec for a search depth of 4 at first step ... on IntelCore i7 3.60GHz CPU ...

Here are the properties of the actual implementation :

• Board of size 19x19
• Implements search window of size 5x5 around stones to reduce search nodes
• Implements heuristic computation at each node on the played stone instead of computation on all board size on leaf nodes number.
• Implements alpha beta pruning
• No multi thread

---

Here are the current stats it is reaching for search depth of 4 at first step:

• == Timing minmax_algorithm: 1.706175 seconds ==
• == Number of nodes in that compose the tree: 2850 ==

. . . . . . . . . . . . . . . . . . . 00
. . . . . . . . . . . . . . . . . . . 01
. . . . . . . . . . . . . . . . . . . 02
. . . . . . . . . . . . . . . . . . . 03
. . . . . . . . . . . . . . . . . . . 04
. . . . . . . . . . . . . . . . . . . 05
. . . . . . . . . . . . . . . . . . . 06
. . . . . . . . . . . . . . . . . . . 07
. . . . . . . . . . . . . . . . . . . 08
. . . . . . . . . . . . . . . . . . . 09
. . . . . . . . . . . . . . . . . . . 10
. . . . . . . . . . . . . . . . . . . 11
. . . . . . . . . . . . . . . . . . . 12
. . . . . . . . . . . . . . . . . . . 13
. . . . . . . . . . . . . . . . . . . 14
o x . . . . . . . . . . . . . . . . . 15
. . . . . . . . . . . . . . . . . . . 16
. . . . . . . . . . . . . . . . . . . 17
. . . . . . . . . . . . . . . . . . . 18
A B C D E F G H I J K L M N O P Q R S 
Player: o - AI: x

Bad stats may be lead to bad heuristic, causing inefficient pruning. Waiting from other stats/replys to validate this hypothesis may help ! Thank you !

Edit 1

Coming back from new search campain on this question.

• The implementation was facing a 19*19 loop index at each heuristic computation ...
  Removed this by heuristic computation at speicific index (not entire board)

• The implementation was facing a 19*19 loop index to check win state ...
  Removed this by checking only around played index any alignement at each step.

• The implementation was facing a 19*19 loop index to check where it can play (even with the windows) ...
  Removed by propagating indexes array of valid indexes through the recursion updated at each step.
  The array is a dichotomic array (with O(n) insertion, O(log n) search and O(1) deletion by index)

• The implementation was lacking of zobrist hash table, very nice idea from below answer.
  It is now implemented with unit tests to prove that implementation is working.
  An array sorted by hash is updates at each new node, with hash-node association.
  The array is a dichotomic array (with O(n) insertion, O(log n) search and O(1) deletion by index)

• The implementation is at each step trying each indexes in a random way (not computation order or evaluation score order).

The before edit example is not great because it is playing on side board and allowed indexes window is half max size.

Here are the new obtains performances :

• with wobrist table off and seed at 42 for search depth of 4 at first step

  • == Timing minmax_algorithm: 0.083288 seconds ==
  • == Number of nodes in that compose the tree: 6078 ==

. . . . . . . . . . . . . . . . . . . 00
. . . . . . . . . . . . . . . . . . . 01
. . . . . . . . . . . . . . . . . . . 02
. . . . . . . . . . . . . . . . . . . 03
. . . . . . . . . . . . . . . . . . . 04
. . . . . . . . . . . . . . . . . . . 05
. . . . . . . . . . . . . . . . . . . 06
. . . . . . . . . . . . . . . . . . . 07
. . . . . . . . . . . . . . . . . . . 08
. . . . . . . . . . . . . . . . . . . 09
. . . . . . . . . . . . . . . . . . . 10
. . . . . . . . . x . . . . . . . . . 11
. . . . . . . . o . . . . . . . . . . 12
. . . . . . . . . . . . . . . . . . . 13
. . . . . . . . . . . . . . . . . . . 14
. . . . . . . . . . . . . . . . . . . 15
. . . . . . . . . . . . . . . . . . . 16
. . . . . . . . . . . . . . . . . . . 17
. . . . . . . . . . . . . . . . . . . 18
A B C D E F G H I J K L M N O P Q R S
Player: o - AI: x

• with wobrist table on and seed at 42 for search depth of 4 at first step

  • == Timing minmax_algorithm: 0.434098 seconds ==
  • == Number of nodes in that compose the tree: 9320 ==

. . . . . . . . . . . . . . . . . . . 00
. . . . . . . . . . . . . . . . . . . 01
. . . . . . . . . . . . . . . . . . . 02
. . . . . . . . . . . . . . . . . . . 03
. . . . . . . . . . . . . . . . . . . 04
. . . . . . . . . . . . . . . . . . . 05
. . . . . . . . . . . . . . . . . . . 06
. . . . . . . . . . . . . . . . . . . 07
. . . . . . . . . . . . . . . . . . . 08
. . . . . . . . . . . . . . . . . . . 09
. . . . . . x . . . . . . . . . . . . 10
. . . . . . . . . . . . . . . . . . . 11
. . . . . . . . o . . . . . . . . . . 12
. . . . . . . . . . . . . . . . . . . 13
. . . . . . . . . . . . . . . . . . . 14
. . . . . . . . . . . . . . . . . . . 15
. . . . . . . . . . . . . . . . . . . 16
. . . . . . . . . . . . . . . . . . . 17
. . . . . . . . . . . . . . . . . . . 18
A B C D E F G H I J K L M N O P Q R S
Player: o - AI: x

Actually it is ok for search depth 4, but not for more than 6. Node number is becoming exponential (over 20 000) ...

Found here great implementation in the same language/techno than can go to 10 depth in less than 1sec, without zobrist or smart trick, and followed the logic.

The issue must be somwhere else, causing exponential growth of node - inefficient pruning.

Answer 1

Intuitively I kind of doubt expecting a search depth of 10 in half a second is reasonable, especially for the initial game state where there's a rather large branching factor and no immediately-winning moves that help to prune some branches quickly.

I've never implemented any Alpha-Beta agents for Gomoku specifically, but I can provide some numbers for our Alpha-Beta implementation in the Ludii General Game System. Note that this is a general game system that implements a wide variety of games in a single game description language. Due to its generality, it's unlikely that any single game runs as efficiently as it would in a highly-optimised game-specific implementation. Therefore, you should consider these numbers to be lower bounds on what you can achieve in a Gomoku-only game-specific implementation.

---

• We can reach a search depth of 3 for the initial game state in half a second.
• Increasing this to 10 seconds is still not enough for a depth of 4. I don't know how much I'd have to increase it to reach a depth of 4.
• At a max search time of 1 second, it actually seems to play quite well against a few different MCTS-based baselines. So I'm not sure if you really need a depth of 10 before you consider it "acceptable".
• I'm not keeping track of the number of visited nodes, so can't provide those.

---

Note that it's very important to take into account the computational cost of your heuristic evaluation function. We're using a somewhat expensive heuristic which computes all potential lines of a length of 5 (because this is appears in the end rules in Gomoku) through all pieces that have been placed so far, as described on pages 82-84 of Automatic generation and evaluation of recombination games (but with a simpler scoring rule than the union of probabilities as described there).

---

CPU: - Intel Core i5-6500 CPU @ 3.20GHz

Game implementation details:

• General game system (so not optimised for this specific game).
• I updated the board size to 19x19 to match your test, but as far as I'm aware 15x15 is more common (and the default in Ludii).
• Implemented in Java

Alpha-Beta implementation details:

• Iterative deepening (so when I write that we reach depth 3, I mean that we completed searches of depth 1, followed by 2, followed by 3, and were probably in progress with a depth-4 search when we ran out of time).
• Ludii does not provide undo operations for moves, only apply operations. This means we have to create lots of copies of states, because we cannot undo moves after exiting out of a recursive call.
• No negamax (because we also want to support games in which players may have multiple moves in a row before control switches over to another player)
• No transposition tables yet (we do already compute the Zobrist hashes, just didn't get around to implementing the TT yet).
• No move ordering (other than in between the iterations of iterative deepening).
• No smaller search windows than just the regular alpha-beta windows.
• Also built-in support to handle games with more than 2 players (with Paranoid search), which probably adds a little bit of overhead to the algorithm.
• No smart tricks like the ones you mentioned about only looking at windows around placed stones; we need to support general games.

---