Hi everybody, I have two related questions: 1. In a AlphaBeta search with a TranspositionTable, how big do you make your Trans-Table? 2. I have read the idea, that instead of a HashTable, one could use a binary tree for storing know positions! Did anybody have any expirienve with that? Do you think this could be a good Idea? Thanks! Nathan

LonelyStar,

1. As much as you can .... No joke, a match on TT saves a lot of time, so experiment with (primary number) sizes considering the amount of memory available. If it's going to run on an old PC and it needs to page to disk, probably it's too big.

2. Binary or hash, the problem will be the same: size. You cannot expect to store ALL positions (unless the game space is really small). Hash tables require no search (it depends on your replacing schema) so they should be quicker.

Hope it helps

Your sizes need to be really really big. (as in, take all of avalible physical memory (ie. no swapping or anything), minus a few mb).

Hash tables are hard to get right.
Both seriously trach cache. bst's are worse then this (because they have more memory reads).

bst's are also simpler, and can work much faster if your adding and deleating nodes very often. (ie, if your table size changes rapidly.)

they also let you use space more effectivelly (because each spot has a node in it, and about two pointers, so you don't have the wasted space of a hash table), and with a few modifications a bst can help you a lot. (you can add/deleate similar nodes, which haven't been used for a long time (relitively), and you could store the last time each branch has been acessed (as an int probably).

This allows you to get rid of the node which hasn't been used for the longest, (keep going until you get pretty close to the leaves), then you find the one which took the least effort to create (store the number of nodes searched in the tree).

Its only slightly slower, and needs just a tiny bit more memory. But bst's give you extra advantages, like using non-prime sizes (which lets you get those last few K nodes in there).

From,
Nice coder