Answers.Body: <p>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.</p>
  
  <p>I've never implemented any Alpha-Beta agents for Gomoku specifically, but I can provide some numbers for our Alpha-Beta implementation in the <a href="https://ludii.games/" rel="nofollow noreferrer">Ludii General Game System</a>. <strong>Note that this is a general game system that implements a wide variety of games in a single game description language</strong>. 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, <strong>you should consider these numbers to be lower bounds on what you can achieve in a Gomoku-only game-specific implementation</strong>.</p>
  
  <hr>
  
  <ul>
  <li>We can reach a search depth of 3 for the initial game state in half a second.</li>
  <li>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.</li>
  <li>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".</li>
  <li>I'm not keeping track of the number of visited nodes, so can't provide those.</li>
  </ul>
  
  <hr>
  
  <p>Note that it's <strong>very important</strong> 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 <a href="https://eprints.qut.edu.au/17025/" rel="nofollow noreferrer">Automatic generation and evaluation of recombination games</a> (but with a simpler scoring rule than the union of probabilities as described there).</p>
  
  <hr>
  
  <p>CPU:
  - Intel Core i5-6500 CPU @ 3.20GHz</p>
  
  <p>Game implementation details:</p>
  
  <ul>
  <li>General game system (so not optimised for this specific game).</li>
  <li>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).</li>
  <li>Implemented in Java</li>
  </ul>
  
  <p>Alpha-Beta implementation details:</p>
  
  <ul>
  <li>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).</li>
  <li>Ludii does not provide <em>undo</em> operations for moves, only <em>apply</em> operations. This means we have to create lots of copies of states, because we cannot undo moves after exiting out of a recursive call.</li>
  <li>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)</li>
  <li>No transposition tables <strong>yet</strong> (we do already compute the Zobrist hashes, just didn't get around to implementing the TT yet).</li>
  <li>No move ordering (other than in between the iterations of iterative deepening).</li>
  <li>No smaller search windows than just the regular alpha-beta windows.</li>
  <li>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.</li>
  <li>No smart tricks like the ones you mentioned about only looking at windows around placed stones; we need to support general games.</li>
  </ul>
  
  <hr>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-18T23:28:08.740Z
Answers.Text: Back from focusing on your great great post and especially Ludii document, the part you mentioned. This portion is totally targeting the problematic the current implementation i have is facing on (search depth / search time). I did not already investigate enough time to look the wide of Ludii and the these. Just commenting back fast here to tell you that your work is currently showing lot of interest and i'm taking time to focus on. I'll probably go back to you here in few times to keep you informed ! Thanks again
Answers.UserDisplayName: user7364588
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-18T18:01:36.897Z
Answers.LastActivityDate: 2019-12-18T20:10:28.450Z
Answers.LastEditDate: 2019-12-18T20:10:28.450Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>Currently, I am working on a Gomoku AI implementation with <strong>minimax + alpha-beta pruning</strong>.</p>
  <p>I'm targeting these two rules from '<em>acceptable implementation</em>' in terms of <strong>search time</strong> and <strong>search depth</strong> :</p>
  <ul>
  <li>Search time (over 0.5 seconds is <em>&quot;bad&quot;</em>, less 0.5 seconds is <em>ok</em>)</li>
  <li>Search depth (less than 10 search depth levels is <em>&quot;bad&quot;</em>, over 10 search depth levels is <em>ok</em>)</li>
  </ul>
  <p>The minimax algorithm generates, by recursive function calls, a tree of nodes, each node represented by a function call with a specific game state.</p>
  <p>Increasing the depth search increases the number of nodes in the tree, and therefore search time.</p>
  <p>There is a compromise between <strong>search time</strong> and <strong>search depth</strong>.</p>
  <p><strong>Alpha-beta pruning</strong> tends to help this compromise by pruning useless nodes search and reducing tree size. The pruning is directly related to the evaluation/heuristic function. Bad implementation of heuristic may lead to bad efficiency of alpha-beta pruning.</p>
  <hr />
  <p><strong>If you are working on or have done a Gomoku AI, <strong>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</strong>.</strong></p>
  <hr />
  <p>The implementation at this time does not fit the '<em>is not acceptable</em>' for me, having <strong>search time</strong> over 1sec for a <strong>search depth</strong> of 4 at first step ... on IntelCore i7 3.60GHz CPU ...</p>
  <p>Here are the properties of the actual implementation:</p>
  <ul>
  <li>Board of size 19x19</li>
  <li>Implements search window of size 5x5 around stones to reduce search nodes</li>
  <li>Implements heuristic computation at each node on the played stone instead of computation on all board size on leaf nodes number.</li>
  <li>Implements alpha-beta pruning</li>
  <li>No multi thread</li>
  </ul>
  <hr />
  <p>Here are the current stats it is reaching for <strong>search depth of 4</strong> at the first step:</p>
  <ul>
  <li>Timing minimax algorithm: 1.706175 seconds</li>
  <li>Number of nodes in that compose the tree: 2850</li>
  </ul>
  <pre><code>. . . . . . . . . . . . . . . . . . . 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
  </code></pre>
  <p>Bad stats might be lead to bad heuristics, causing inefficient pruning. Waiting for other stats/replies to validate this hypothesis may help.</p>
  <h2>Edit 1</h2>
  <p>Coming back from a new search campaign on this question.</p>
  <ul>
  <li><p>The implementation was facing a 19*19 loop index at each heuristic computation ... Removed this by heuristic computation at a specific index (not the entire board)</p>
  </li>
  <li><p>The implementation was facing a 19*19 loop index to check win state ... Removed this by checking only around played index any alignment at each step.</p>
  </li>
  <li><p>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 <span class="math-container">$O(n)$</span> insertion, <span class="math-container">$O(\log n)$</span> search and <span class="math-container">$O(1)$</span> deletion by index)</p>
  </li>
  <li><p>The implementation was lacking a Zobrist hash table, a very nice idea from the below answer. It is now implemented with unit tests to prove that implementation is working. An array sorted by hash is updated at each new node, with the hash-node association. The array is a dichotomic array (with <span class="math-container">$O(n)$</span> insertion, <span class="math-container">$O(\log n)$</span> search and <span class="math-container">$O(1)$</span> deletion by index)</p>
  </li>
  <li><p>The implementation is at each step trying each index in a random way (not computation order or evaluation score order).</p>
  </li>
  </ul>
  <p>The before edit example is not great because it is playing on a sideboard and the allowed indexes window is half max size.</p>
  <p>Here are the newly obtained performances :</p>
  <ul>
  <li><p>with Zobrist table <strong>off</strong> and seed at 42 for <strong>search depth of 4</strong> at the first step</p>
  <ul>
  <li>Timing minimax algorithm: 0.083288 seconds</li>
  <li>Number of nodes that compose the tree: 6078</li>
  </ul>
  </li>
  </ul>
  <pre><code>. . . . . . . . . . . . . . . . . . . 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
  </code></pre>
  <ul>
  <li><p>with Zobrist table <strong>on</strong> and seed at 42 for <strong>search depth of 4</strong> at the first step</p>
  <ul>
  <li>Timing minmax_algorithm: 0.434098 seconds</li>
  <li>Number of nodes that compose the tree: 9320</li>
  </ul>
  </li>
  </ul>
  <pre><code>. . . . . . . . . . . . . . . . . . . 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
  </code></pre>
  <p>Actually, it is ok for search depth 4, but not for more than 6. The node number is becoming exponential (over 20 000) ...</p>
  <p>Found <a href="https://github.com/terngkub/gomoku" rel="nofollow noreferrer">here</a> 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.</p>
  <p>The issue must be somewhere else, causing exponential growth of node - inefficient pruning.</p>
  
Tags: <game-ai><minimax><alpha-beta-pruning>
Title: Could you share with me the tree size, search time and search depth of your implementation of Gomoku with minimax and alpha-beta prunning?
UserDisplayName: user7364588
ThreadText: # Could you share with me the tree size, search time and search depth of your implementation of Gomoku with minimax and alpha-beta prunning?
  
  (Asked by: username_0 on 2019-12-18)
  
  Currently, I am working on a Gomoku AI implementation with minimax + alpha-beta pruning.
  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 minimax 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 the evaluation/heuristic function. Bad implementation of heuristic may lead to bad efficiency of alpha-beta pruning.
  
  If you are working 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 the first step:
  
  Timing minimax 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 might be lead to bad heuristics, causing inefficient pruning. Waiting for other stats/replies to validate this hypothesis may help.
  Edit 1
  Coming back from a new search campaign on this question.
  
  The implementation was facing a 19*19 loop index at each heuristic computation ... Removed this by heuristic computation at a specific index (not the entire board)
  
  The implementation was facing a 19*19 loop index to check win state ... Removed this by checking only around played index any alignment 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 a Zobrist hash table, a very nice idea from the below answer. It is now implemented with unit tests to prove that implementation is working. An array sorted by hash is updated at each new node, with the 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 index in a random way (not computation order or evaluation score order).
  
  
  The before edit example is not great because it is playing on a sideboard and the allowed indexes window is half max size.
  Here are the newly obtained performances :
  
  with Zobrist table off and seed at 42 for search depth of 4 at the first step
  
  Timing minimax algorithm: 0.083288 seconds
  Number of nodes 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 Zobrist table on and seed at 42 for search depth of 4 at the first step
  
  Timing minmax_algorithm: 0.434098 seconds
  Number of nodes 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. The 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 somewhere else, causing exponential growth of node - inefficient pruning.
  
  **Tags:** game-ai, minimax, alpha-beta-pruning
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-12-18. Score: 3 | Accepted answer
  
  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](https://ludii.games/). **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](https://eprints.qut.edu.au/17025/) (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.
  
  ---
  
  > **Comments:**
  > **username_0**: Back from focusing on your great great post and especially Ludii document, the part you mentioned. This portion is totally targeting the problematic the current implementation i have is facing on (search depth / search time). I did not already investigate enough time to look the wide of Ludii and the these. Just commenting back fast here to tell you that your work is currently showing lot of interest and i'm taking time to focus on. I'll probably go back to you here in few times to keep you informed ! Thanks again  
  
  ---
  
  