Adding a Transposition Table to Monte Carlo Tree Search

Question

I think I'm having a bit of trouble wrapping my head around how a transposition table functions:

As I understand it you can store a value (simulation result?) for a given game state in this (hash) table and use it instead of a simulation when that game state is encountered again. However, since the simulation is (or at least in my case is) completely random play, I would think that you need to build up a sample size before the result value of the simulation starts meaning anything.

It seems to me that with the way I understand it now, these two principles can't both be achieved simultaneously, so what am I missing?

As a side note I have come across some information that suggests changing the valuation algorithm to account for the transposition table and have done so (hopefully correctly).

Answer 1

I have had a chat with ChatGPT which helped me wrap my head around it:

An important factor here is that my simulation (also called a rollout) consists of random play. Because of this I need ot visit this state and pplay randomly for many times in order to be able to somewhat accurately estimate the value of the position.

The aim of adding a transposition table is to save computation of states that have already been evaluated before. But you can store multiple evaluations before skipping the simulation and reusing the value once your confidence in it is high enough. It depends on the game and the size of the search space and most importantly the way you achieve the game value (random play simulation vs for example a neural network as alpha zero does it) how large that number needs to be.

Another important aspect I learned is that you need to persist the table and use it for later games. If you don't it will not be effective, because you only save the states in the past which you likely will not encounter (there are some exceptions like both players putting a piece back sequentially). So essentially it becomes a dataset.