0

I'm writing a checkers engine that takes a position, given by 6 32-bit integers + a boolean, and maps it to a struct that contains legal moves, and visit counts and prior probabilities for these moves.

I originally was using Zorbrist hashing to map the position to a 64-bit integer, and using that as the 'key' for std::unordered_map. This fails because any hash collision will result in the search tree accessing illegal moves and polluting the statistics with garbage information. For this reason I would like to use the entire position, as mentioned above, as the key to the map.

The move information is contained in the following struct

struct move{
    std::pair<uint32_t, uint32_t> a;
    int n = 0;
    double q = 0;
};

The problem is that I can not find a suitable type that will work with unordered map. For instance, trying to use a pair of boost 128-bit integers like so

std::unordered_map<std::pair<boost::uint128_type, boost::uint128_type>, move_data_struct> M;

results in errors that I am not equipped to understand, What type do I put in the first template argument of unordered_map that will accommodate 192 bits of information?

basket
  • 181
  • 6
  • 1
    Please show a [MCVE] – Jabberwocky Dec 12 '19 at 16:19
  • 4
    How are you saving the values originally? If you have them in a custom `struct` in some way, you can simply use that. You only need to specialize `std::hash` for your type, see e.g. [here](https://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key) – walnut Dec 12 '19 at 16:19
  • In a `unordered` map the key type is not the hash type. Here it would be the complete set of values. Hashing is done entirely internally. – François Andrieux Dec 12 '19 at 16:21
  • I was asking how you save the key values (i.e. the 6 integers + boolean), not the mapped values. The `struct` you are showing now seems to be the mapped type. – walnut Dec 12 '19 at 16:24
  • What do you mean I can simply use the struct. In a simulation I will encounter multiple positions. At the end I have a score, and a vector of the states, moves chosen along the way. Then I have to backpropogate and update the structs for all of these states. That's why I need the map. To map the state to the move stats. – basket Dec 12 '19 at 16:25
  • There is no bool, my mistake. Internally, a board state is represented as an array of 7 uint32_t's, only the first 6 are needed to identify the state uniquely. – basket Dec 12 '19 at 16:27
  • @basket Suppose the 6 32-bit integers representing the key values form a `struct my_key { uint32_t pos[6]; };`. Then you can use `std::unordered_map`. You just need to define an `operator==` overload and a `std::hash` specialization for `my_key`, see linked question. – walnut Dec 12 '19 at 16:27
  • @walnut I'm looking at the link. So are you saying I could make a struct containing the 6 ints, with a comparator given by comparing each int. The only thing I don't quite get is the custom hash function. I think I could do something like zorbrist hashing (which may collide) but std map would check for that and work around it? Would this not consume a lot more memory? – basket Dec 12 '19 at 16:32
  • 1
    @basket Hash functions colliding is not a problem. It is expected. One cannot map from a large space (e.g. 256bits) to a smaller one (fitting into memory) without possible collisions. A hash table implementation such as `unordered_map` must handle collisions internally in some manner (different approaches are possible). You only need to provide a hashing function that is outputting reasonably uniformly distributed values for the inputs you are giving it. What hashing algorithm you choose does not matter otherwise. – walnut Dec 12 '19 at 16:38
  • As suggested in the linked question, hashing individual numbers with `hash()(pos[0])` etc. and then combining them with some shifts and XORs is probably already sufficient. A somewhat better hash-combining approach is also shown, namely multiply and add with prime numbers. – walnut Dec 12 '19 at 16:39
  • I don't know what the bits represent, but there cannot be 2²⁵⁶ distinct states as there are only 10⁸⁰ particles in the whole universe. And collision doesn't mean a disaster, it just means that the hashing function is not good enough to distribute values to different buckets – phuclv Dec 13 '19 at 01:56
  • @phuclv You are missing an exponentiation :) Of course there can be more than 2^256 states! For instance, a Go game has around 2^170 legal positions. Even your phone has more than 2^(2^30) possible states. – Acorn Dec 13 '19 at 06:36

0 Answers0