btreemap vs hashmap for transposition table

Question

I have created a minimax algorithm that uses alpha beta pruning and a transposition table to speed up the search. I am currently using a hashmap that uses the board state as the key and saves the score as the value. (the game is tic tac toe on a 5x5 board)

The issue with this is hashing is slow and using the entire board state as the key eats up a lot of memory. Board state is represented by a 2d array of enums with 3 possible types: Blank, X, and O. I would like to use my own hash (probably zobrist) as the key and not save the board state at all, but a hashmap would take my key and hash it again. I have considered using the btree map which treats a key as unique, but the access time is log(n) instead of O(1). I also don't care at all about the order of the keys so a btree doesn't really seem to fit here.

so my question is, which data structure would be ideal here? should I use a hashmap even though it hashes my keys a second time?

If you implement your own hashing algorithm that hashes into an integer value (say `u64`), then the cost of rehashing it is basically nothing. However, you run into the issue that, unless you can guarantee your hash to yield a unique value for every board state, you can't not save the board state otherwise you might get incorrect results with hash collisions. — Aplet123, Feb 22 '21 at 21:08
There is no "right" data structure. Write benchmarks for your use case with both `HashMap` and `BTreeMap` and compare. For small collections (<1000 items), `BTreeMap` is often faster, but the exact limits are dependent on lots of factors (e.g. how many items fit in a cache line etc), so benchmarks are the only way to know. — Peter Hall, Feb 22 '21 at 21:36
@HHK the board state is stored as a 2d array of enums with 3 possible types: blank, X, and O. — The Mungler, Feb 22 '21 at 22:14
If you go with Zobrist hashing, you could store the hash alongside the board state to avoid the need to recompute it each time. Especially since Zobrist hashes can be computed incrementally at very low cost. — Jmb, Feb 23 '21 at 08:20
Using bit encoding for this purpose is going to be very efficient wrt memory usage. Setting aside 2 bits for each cell (3 states 0,X, blank), you can guarantee each generated code is going to be unique and faster to calculate as a key. — Vishal, Feb 23 '21 at 08:20

score 2 · Accepted Answer · answered Feb 23 '21 at 08:25

I've been doing something similar, and here's what I ended up with, adapted to your case:

Compact board representation: Assuming a 5x5 board, each cell having one of 3 possible values: This means you could use 2 bits per cell, amounting to a total of 25*2=50 bits. These would fit into a u64. This makes hashing/storing entries in the hashmap pretty cheap.

In my case, I also used u64 (see https://github.com/phimuemue/brainball_solver/blob/master/src/main.rs#L20-L22), and thought about using this value directly as the hash (specifing an own hasher that just tunnels the value through), but if I recall correctly, using a "real" hash function ended up being faster. (Possibly better collision behavior?)
I ended up inlining the backtracking stuff manually (see https://github.com/phimuemue/brainball_solver/blob/master/src/main.rs#L247-L253 and https://github.com/phimuemue/brainball_solver/blob/master/src/main.rs#L267-L272), which sped up the thing considerably.
I implemented the moves using generated lookup tables (https://github.com/phimuemue/brainball_solver/blob/master/src/main.rs#L17, https://github.com/phimuemue/brainball_solver/blob/master/build.rs#L37-L79) to speed up the moves.

All of this is to be taken with a grain of salt. In my case, it helped to speed up the search, but you'll have to test your case separately.

btreemap vs hashmap for transposition table

1 Answers1