Transposition tables?

Question

I'm using Minimax to make the computer play connect 6. I am also using Alpha-Beta pruning to speed up the algorithm.

I wanna add in a transposition table to make the algorithm even faster. I have absolutely no experience with them.

Could someone explain the basics of transposition tables, and how they would apply to a game like Connect 6? A link to a useful resource would be fine.

I"m familiar with hash tables.

What I found:

1) https://www.chessprogramming.org/Transposition_Table

The link gives a good explanation of transposition tables but completely focuses on chess so its hard to figure out how transposition tables work independently from chess.

Answer 1

First up the minimax algorithm if applied naively has to calculate the best play (in a minimax sense) for each board position that you could possibly run into in the future. Alpha beta-pruning helps cut back on unnecessary computations because if you know you are never going to play a certain move then you don't need to compute the value of playing that move.

With some games the best play on a given board can be determined entirely by the state of the board at that moment in time. Chess is like this, so is go and so are a few other games. The key realization is that how you got to a particular game state doesn't really matter (from a minimax point of view) once you have arrived at that state.

Specifically a transposition in the chess sense of the word is what happens when you take 2 different paths of moves to get from a starting position to an ending position.

Transposition tables just let you optimize calculating the best move when you encounter situations where different plays results in the board being the in same end state. Essentially once you get to one specific board position you just store the result of your minimax calculation at that position in the transposition table. This means that later on if some other different list of moves arrives at the same board then all of a sudden you don't need to completely recalculate the minimax at that board because you've already done that and you can just look it up from the transposition table.

So if there are multiple ways the players can play that arrives at the same board position you don't need to duplicate looking down that branch of the game tree more than once if you are able to save the results of that calculation somehow. To do this efficiently you need to be able to efficiently represent a board position then have some data structure that allows you to look up that board position quickly in the transposition table. Finding the right representation will depend heavily on what game you are analyzing.

If connect6 is this game perhaps an example would be good:

Say the board starts like this (position A):

X 0 
0 X

There's more than one set of moves that get you to (position B):

X 0 0 0
0 X X X
0 X

Say there's n ways of going from position A to position B, if you went about this naively you might have to test to find the best move at position B up to n times (depending on which branches of the tree alpha-beta prunes off). But really it would be great if we didn't have to do the exact same computation multiple times for the B board position, once would hopefully be enough!

What you have to do to leverage this idea is find a way of representing a connect 6 board position. One way we could represent the board is just to have a N by N array where N is the board dimension and just store an enum value for each cell that corresponds to if it's empty, has an X in it or has a 0 in it. However this naive approach doesn't have great properties for looking up positions because we'd always be passing around these nasty N by N arrays. Not to mention that having to always store a lot of these N by N arrays would take a lot of memory.

So if we can define a hash function that takes the N by N board and maps it to an almost unique integer without a ton of processing overhead then we can streamline this process. Hashing a board and seeing if it's in the table should hopefully be quicker this way.

So this is why people try to make a hashing function for the specific game they are analyzing. For connect 6 I have no idea what the best hashing function is, that's something you would have to work out.

Getting the best performance out of something like this takes a whole bunch of tinkering but hopefully this post has given you some ideas. Please comment if you would like me to expand on anything.

Answer 2

This MediocreChess article explains transposition tables in details. The Zobrist algorithm is very simple to create transposition tables.

The zobrist system in two words :

1. Generate a random number (let's say 32 bits) for each couple of [possible piece, possible cell] (for tic-tac-toe it's 2*9) and store them in an array.
2. Start at hash=0, and XOR the hash with the stored number for each couple of [played piece, position of played piece]
3. You obtain your Zobrist key !

It's a very good system which allows removal of a piece ! you only have to XOR the same number again. It's really usefull for negamax/alpha-beta algorithms because we have to change/restore state a lot of times. It is easy to maintain a Zobrist key up-to-date.

The system of transposition table is :

• For a certain game position, you generate a hash, which is the signature of the game position, with the Zobrist algorithm, and you obtain an integer (32 bits or 64 bits for example).
• This "zobrist key" could be used directly to store best move and score for the given position, in a transposition table.

• But you'll probably don't want to store 2^32 or 2^64 entries, so you take a "hash" of the Zobrist key to limit entries of the transposition table, let's say 16 bits for 2^16 game positions (in reality it's probably >=2^20). To obtain this hash, a simple method is to "modulo" the zobrist key, or do a "binary and" :

  transposition table index = zobrist_key & 0xFFFF

You obtain an integer between 0 and 2^16-1, this is your index in the transposition table! Of course, we can encounter collisions, so we could store the full zobrist key in the transposition table.

Let's summarize :

1. For a given position, compute the zobrist key, and then a hash of the zobrist key, which will be your index in your transposition table. Let's store important data in this table entry : score, best_move, zobrist_key, flag, depth.
2. When you need to lookup in the transposition table, compute the zobrist key for the given game position, then the hash of it, and get the corresponding entry. Then check if entry's zobrist key is equal to yours, to avoid collision problems of "false positive".

So for a Connect 6, you have 2 stone colors, and let's say 59x59 positions, so you have to create an array of 59x59x2 = 6962 random numbers. To encode a game position in a Zobrist key, take each stone, and for its colour and its position, take the number you generated and XOR them together. Reduce your Zobrist Key to an index (hash, binary "and", ...), and store your data at this index in your transposition table.