Game Playing AI - Strategy to overcome the transposition table taking up too much memory?

by Inertial Ignorance   Last Updated January 02, 2019 04:05 AM

I've made an engine that plays Connect Four using the standard search algorithms (minimax, alpha-beta pruning, iterative deepening, etc). I've implemented a transposition table so that the engine can immediately evaluate a same position reached via a different move order, and also to allow for move-ordering.

The problem with the TT is that on each step of the iterative deepening process, the amount of bytes it takes up grows by at least double. The TT stores objects that represent important info for a given position. Each of these objects is 288 bytes. Below, depth limit is how far the engine searches on each step of iterative deepening:

depth limit = 1 - TT size = 288 bytes (since just one node/position looked at).

depth limit = 2 - TT size = 972 bytes.

depth limit = 3 - TT size = 3708 bytes.

depth limit = 4 - TT size = 11664 bytes

depth limit = 5 - TT size = 28476 bytes.

....

depth limit = 12 - TT size = 11,010,960 bytes.

depth limit = 13 - TT size = 22,645,728 bytes.

And now at this point the .exe file crashes.

I'm wondering what can be done about this problem. In Connect Four the branching factor is 7 (since there are usually 7 possible moves that can be made, at least in the beginning of the game). The reason the TT isn't growing by a factor of 7 on each step is due to pruning methods I've implemented.

This problem isn't a big deal if the engine only searches up to depth 8-9, but my goal is to get it to refute Connect Four by going all the way to the end (so depth limit = 42).



Related Questions


Rooted tree - Representation & Performance

Updated December 13, 2016 08:02 AM

Is there a tree data structure with multiple root nodes?

Updated September 26, 2017 12:05 PM

Optimal way of storing sorted tree in memory

Updated April 26, 2018 15:05 PM