Implementing Transposition table for a board game..what is the best approach?

[patishi]

Hi all. I want to implement a Transposition table for my Gomoku engine which i started to write in C. I am relatively new to the language (coming from java) so I need some advices.

The most logical approach (I think) is to use a struct called "Entry" that will contain all the relevant information for a position.. like depth,hash key, score etc.
Those structs will be stored in a table (Array) of more than a million entries.. (maybe a lot more, but this will suffice for now).

Is it best to make the table contain the pointers to the structs or the actual structs? the reason for this question is ,I don't know if it is better to make all the entries NULL pointers at initialization (?) That means that when i want to store an entry in the table i will have to allocate memory dynamically every time i do that? can it be a little slow?
I can instead use some sort of a flag indicating whether an entry is active or not, and change that. in the latter case i guess i don't need to use pointers but i can initiate the whole 1,000000+ entires right from the start?

I am clueless..what is better approach and please feel free to recommend other ideas.
Thx!

EDIT: oh..and i will be using the Zobrist hashing scheme for the hash keys.. 64 bit hash keys

[Adak]

I would consult with the chess programmers and get their opinion on this, as well. Many of their programs are open source, and use TT's and Zobrist hashing.

TalkChess.com :: Index

Check out the programming and technical discussions. DO NOT post a single word regarding CLONES -- no joke.

[Barney McGrew]

Is it best to make the table contain the pointers to the structs or the actual structs?

You need to know *when* you know the number of entries that your program will actually use, then allocate that number of structs. If you know it before interpretation, make it an array of that many structs. Otherwise make it an array of pointers to that many structs, and allocate storage for all those structs in a single call to malloc. If some are inactive at a given time and others are active, you can use the members within the struct to indicate that.

Of course, if you need to handle collisions and you're doing that with a linked list, you'll need an array of pointers either way.

EDIT: I'm assuming that each struct object is quite a bit larger than a pointer to struct object. If they're around the same size, you may as well just allocate an array of struct objects; even the ones your program won't use.

[patishi]

Thanks. yes, The size of the table will be fixed right from the beginning. so in that case it is ok to do : Entry entries[N] ? where N = 1048583..or some other prime number.
I will be using "Always replace" scheme, that means always replace entries, so no special collision handling is needed.

[oogabooga]

I would consult with the chess programmers [at] TalkChess.com :: Index. ... DO NOT post a single word regarding CLONES -- no joke.

For those who want to know about "clones":
​Attack of the clones | ChessVibes

[Barney McGrew]

@patishi: That seems like the simplest way to go about it for now. If you notice it eats up a lot of memory later on (when you have your program working the way you want it to), you could try optimising it for space.

[Neo1]

Thanks. yes, The size of the table will be fixed right from the beginning. so in that case it is ok to do : Entry entries[N] ? where N = 1048583..or some other prime number.
I will be using "Always replace" scheme, that means always replace entries, so no special collision handling is needed.

You could risk running out of space on the stack if you allocate an array of that size. I suggest allocating it on the heap instead using malloc().

[patishi]

@neo1 , this is actually what worries me. so how should i allocate this on the heap? at first i wanted it to be a static variable of the main file (declared above main() ). should i than do it with pointers? should i make them all null at first and allocate them one by one when inserting to the table or allocate them all at the same time?
As i understand correctly, the heap is less vulnerable to memory loss?

[Barney McGrew]

Stacks and heaps are implementation details. The three storage durations you need to concern yourself with are automatic, static, and allocated. Either of the last two would be a good choice for your table.

[patishi]

sorry for the ignorance, but automatic means when i declaring and initiating something above the main? because i am doing it a lot. for the board array for example and other "public" arrays and shared variables i use. would it be better to initiate them inside the main function and than pass them as pointers to functions? (although it can be complicated sometimes because some functions use those public variables a lot..like the checkWin() functions and the evaluation function that use the board array.
can you please exaplain to me what is the difference between those storage durations?

[Barney McGrew]

Automatic storage has a limited lifetime that's associated with the block it's declared in -- they're commonly implemented with a stack. Static storage, on the other hand, has a lifetime that extends from the beginning of the program's interpretation to the end of the program's interpretation, so the objects you define *outside* of functions all have static storage duration. Allocated storage is different from the other two, where you can only get a pointer into that kind of storage out of the 'alloc' functions (malloc, realloc, calloc).

[patishi]

ah ok..i think i got it. so automatic is when i declare something temporeraly inside a function, and static is when i initiate it outside of a function like i do. and allocated is when i use alloc and need to free it afterwards. so it is ok to declare the transposition table out side of main as a static variable than?

[Barney McGrew]

so automatic is when i declare something temporeraly inside a function, and static is when i initiate it outside of a function like i do. and allocated is when i use alloc and need to free it afterwards.

That's pretty much the idea.

so it is ok to declare the transposition table out side of main as a static variable than?

Sure is. I'd say it's the better choice in this case. The other good choice of allocated storage duration would be ideal if you don't know how the size of the array in advance, so you might consider using it if you ever have to optimise your program for space.

[patishi]

thanks a lot for the explanation

[Barney McGrew]

You're welcome.