Sign in to follow this  

Effective Transposition Table in JAVA

This topic is 3453 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

Howdy Everyone! So its been several months since I've posted last and my game has went through several evolutions. I'm writing a checkers varient thats using Minimax and killer move. It's playing to four plys deep and takes its turns in about 2-4 seconds which is acceptable, but I want to tighten up gameplay and speed up my engine to eight plys. The branching factor of my game is approximatly 20moves per ply. Previously, I added a transposition table with some degree of success. It would give me out-of-memory errors during heavy game play. Two 64bit long values uniquely describes min's and max's piece positions. My previous implementation used two Java Hashmaps to store and index the cache values. On retrospect this might be wastefull. I've read about zobrist hashing and I think that might be something to work on. Is there anything else I should be looking for? Thanks

Share this post


Link to post
Share on other sites
Quote:
Original post by gfrommer


Previously, I added a transposition table with some degree of success. It would give me out-of-memory errors during heavy game play. Two 64bit long values uniquely describes min's and max's piece positions.

128 bits for a checkers position seem very wasteful; you can certainly put 5^32 states (a very gross overestimation) in 96 bits, for instance.

Share this post


Link to post
Share on other sites
Edit: oops, I forgot about kings when I made this post, they increase the state size so that 64 bits is not quite enough...

Java's built in data structures are probably inefficient for storing 64 bit values, since Java's generic containers are designed to hold objects and primitives will end up being boxed in object types (unless they've fixed this in the past few years, I haven't used Java lately). This boxing will probably at least double the memory overhead.

You say you used two hash tables? Why two? What did each of them contain? All you need is one table. Its key is the 64 bit hash and its value is the evaluation of that position.

Share this post


Link to post
Share on other sites

This topic is 3453 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