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.
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.