Hi. I have learned the chess AI from https://www.chessprogramming.org/ and I’m interested in transposition table, which use to speed up the computing AI game. After i read the Wiki, my implementation that i can code is using unordered_map. And i found that the performance of table will affect the program significantly, and unordered_map isn’t the best option for the performance .
Do you have any suggestions for the tips to optimize the unordered_map or some generic hash map implementation that i can refer to ?
Unordered map pointers, not the objects itself (create the objects static or at 1st turn). Use .reserve(n) to avoid hash growths, clearing a big hashtable can take several ms. Good luck trying it, I’ve had many problems with them
Use a simple type for the key (a pointer is fine). If you have to use a custom hash, the performances will be bad. Like Marchete said, reserve the full size at the start of the program to avoid any resize.
If you want something faster than an unordered_map, your only option is a simple array. But you’ll have to use a key or a 32b size.
I found some implementations like this:
You create a hash of the game with the size you want. You don’t care. It can be 100ko (well, just beware of the maximum RAM of course). You create a 32b key with your hash (you reduce if to 32b, you’ll lose information of course).
Then the 32b key can be used to store it into an array like transposition_table[key] = myState;. Now there’s 2 options:
Your transposition table does not contains they given key. You just store your state in tour transposition table.
Your transposition table contains the given key. You check if the hash is the same. It’s the same ? good, nothing to do. Not the same ? Then you’ll have to choose if you replace the state in the table.
Thanks for your advice. The cost of rehashing when the table grows up make the performance goes down, and i have read a blog on Codeforces talks about the tips, but there are some facts that the N in reserve should be the power of 2, the others say that should be the prime closet power of 2. So which one do you think that is suitable for AI problems ?
Thanks for your advice. I think that you are talking the open-addressing version of the hash map right ?
Of course the custom hash is the must, i will choose the Zobrist for hashing the state of game, and that is the only hashing for game that i can know so far.
Yes the size of the node (Game) doesn’t matter for me, i can trust the allocation of memory will be 1GB :)) , so i prefer optimize the time to the memory.