The current implementation of the transposition table resulted in nodes that
were evaluated to a depth either lower or higher than the depth_limit.
This change eliminates cache hits which resulted in a node evaluated to a depth
less than depth_limit.
Technically this means that there are fewer cache hits than before, therefore it
plays slightly slower when there are still small numbers on the board. However,
since this allows the use of a deeper cache without negative effects to ai
strength, when coupled with Petr Moravek's adaptive search depth limit, it
results in a significant speedup when there are large numbers on the board
(ex. in cases just before a large number is reached).
I also increased CACHE_DEPTH_LIMIT to 15 which, since the current implementation
results in a maximum depth_limit of 14, means that the cache will be used in all
levels of the search. The program is obviously more memory hungry now. During
testing I saw spikes up to about 60MB of memory usage just before reaching a
32768 tile, which isn't really that bad. In my opinion memory is cheap, but time
is money haha.
I ran a test by fixing the search depth to 3 (I disabled the adaptive search
depth limit) and then running 100 games each of the following 3 variants:
(A) CACHE_DEPTH_LIMIT set to 0
(B) CACHE_DEPTH_LIMIT set to 3 using the old transposition table
(C) CACHE_DEPTH_LIMIT set to 3 using the new transposition table
I then checked the average score of the 100 games. My results were as follows:
(A) 132341
(B) 129610
(C) 134610
I ran the test several times and every time the results were B < A < C. It is
evident that the old implementation was negatively affecting the strength of
the AI, while the new one actually improves it a little bit.
Letting the program run until it reached the 32768 tile, I noticed
approximately a 50% improvement in average speed throughout the game.
The current implementation of the transposition table resulted in nodes that were evaluated to a depth either lower or higher than the depth_limit. This change eliminates cache hits which resulted in a node evaluated to a depth less than depth_limit.
Technically this means that there are fewer cache hits than before, therefore it plays slightly slower when there are still small numbers on the board. However, since this allows the use of a deeper cache without negative effects to ai strength, when coupled with Petr Moravek's adaptive search depth limit, it results in a significant speedup when there are large numbers on the board (ex. in cases just before a large number is reached).
I also increased CACHE_DEPTH_LIMIT to 15 which, since the current implementation results in a maximum depth_limit of 14, means that the cache will be used in all levels of the search. The program is obviously more memory hungry now. During testing I saw spikes up to about 60MB of memory usage just before reaching a 32768 tile, which isn't really that bad. In my opinion memory is cheap, but time is money haha.
I ran a test by fixing the search depth to 3 (I disabled the adaptive search depth limit) and then running 100 games each of the following 3 variants: (A) CACHE_DEPTH_LIMIT set to 0 (B) CACHE_DEPTH_LIMIT set to 3 using the old transposition table (C) CACHE_DEPTH_LIMIT set to 3 using the new transposition table
I then checked the average score of the 100 games. My results were as follows: (A) 132341 (B) 129610 (C) 134610
I ran the test several times and every time the results were B < A < C. It is evident that the old implementation was negatively affecting the strength of the AI, while the new one actually improves it a little bit.
Letting the program run until it reached the 32768 tile, I noticed approximately a 50% improvement in average speed throughout the game.