1) The dim statement you provided earlier does not provide an array with multiple data entries per index, but an array with multiple indexes. It's neither a proper table nor an entry. We'll get back to the functional options for this in a moment.
2) The function of a transposition table and core parts
a) The hashed representation of your position
Your actual position representation is going to be much larger than the actual statespace of the game in order to be efficient to work with. positions in your search are going to be very similar such that if you use only a portion of your position representation you're going to get collisions. So you use a hashing function on the entirety of the game state. In chess engines, the established effective method for doing this is a zobrist hash key. For each possible state a 64-bit number is assigned (usually a random 64-bit number) - Then all of these 64-bit numbers are xored together, and the result is a position hash key that changing one thing on the board changes on average a random half of the bits. For your transposition table this resulting 64-bit key is what determines the index into your table, and what's not needed from that is used to determine when two positions that share the same index are not in fact the same position.
b) how the table is used
- at the end of your search for a node when you have a result, you convert the hash key into an index, look up that entry of the transposition table, and replace it (or one of it if using multiple buckets - but starting with single-bucket always-replace is probably simplest)
- at the top of the search for a node you then look up the index, check if the hash key matches what's found at that index and if so: check if the depth and entry type are sufficient to return a result now, if you can't take a return now from that then use the move stored first in the search for this node
c) back to defining the table - the right answer is to create a user-defined custom type composed of primitive types - but if that's something you want to avoid learning for now the alternative is multiple arrays - it's less efficient for many reasons but would look like this (note you may need to change some of these types for simplicity if for instance you're using floating point scores)
Code: Select all
Dim TTkey(tablesize-1) As ULongInt
Dim TTmove(tablesize-1) As UShort
Dim TTscore(tablesize-1) As Short
Dim TTdepth(tablesize-1) As Byte
Dim TTentrytype(tablesize-1) As UByte
creating a user defined type instead:
Code: Select all
Type TTEntry Field = 1
key As ULongInt
move As UShort
score As Short
depth As Byte
entrytype As UByte
End Type
Dim TT(tablesize-1) As TTEntry