Sign in to follow this  

Size of TranspositionTable and the alternative of an binary search tree

This topic is 4686 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites

This topic is 4686 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this