I'm currently programming an AI for the game called Lines of Action. As I was looking into how to optimize my program, I learned about alpha-beta pruning, which I have implemented, and I now am looking to implement a transposition table. I have implemented the Zobrist hashing part, but I am not sure how I should store the hash key and the corresponding value object that is meant to store the depth, best move, flag, and score. I think I should be using a hash table or an array, but I am not sure how this should be done. Also, apparently since the game states will eventually lead to an overload of memory, I understand that there has to be some sort of replacement scheme. I would appreciate if someone could either provide a naive implementation or point me in the direction of some resource that explains some of the schemes.

Additionally, I was wondering if always starting with the bestMove stored in the transposition table would work as move ordering, or should I be using some other method to choose the first moves?

I assume you mean https://en.wikipedia.org/wiki/Transposition_table this, right?

It seems to simply cache results of a function call, ie you have f(x) = y, where computing “f” is costly, so you cache x → y pairs that you calculated already, and before evaluating f(x) you check the cache for a matching x. If you have it, you just return the y part of the pair and you saved computing f(x). If you don't have it, run the f(x) computation, and store the x → y pair afterwards to avoid more f(x) computations.

For the cache, you need to find out whether a given x exists already in the cache. Hashing is a good technique to reduce the number of comparisons that you have to make. (Most other positions should result in a different hash value, so there are only a handful of x-es that you need to check completely to find your x→y pair.) Read about hash table implementations how these things work internally. That should give you a good idea of how to implement it.

Assuming you have more x→y pairs than you have room in the computer, indeed you'll run out of memory at some point. The trick here is to drop the less useful entries at some point. A common algorithm here is LRU (least recently used), that is, drop entries that you haven't needed for some time. When the value is needed again you need to re-compute it.

There are however many strategies for dropping ‘old' entries, I don't know if LRU is any good for game positions, it all depends on the typical access patterns.