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.