🔒 Locked

Effective Transposition Table in JAVA

Started by gfrommer Jun 25, 2008 at 11:00 PM 1 replies 2.3k views

Original Post

Jun 25, 2008 at 11:00 PM

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

LorenzoGatti

1,011

LorenzoGatti

Jun 29, 2008 at 9:58 AM

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.

Vorpy

Jun 29, 2008 at 1:20 PM

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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.