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?
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.