Dictionary has same key more than once

New to Julia
1

For my chess engine with alpha-beta-pruning algorithm with transposition tables, I wanted to create a Dictionary, that uses my own hash function. So i did the following:

mutable struct Zobrist
    val::UInt
end

Base.hash(a::Zobrist, h::UInt) = xor(a.val, h)
Base.:(==)(a::Zobrist, b::Zobrist) = a.val == b.val

gTranspositions = Dict{Zobrist, Transpositionentry}();

This is the Transpositionentry structure:

mutable struct Transpositionentry
    value::Int64
    recursion::Int64
    vtype::Valuetype
end

After running my algorithm the dictionary looks like this:

Dict{Zobrist, Transpositionentry} with 116849 entries:
  Zobrist(0x3fb8d5fc38d3094c) => Transpositionentry(40, 1, upperbound)
  Zobrist(0x7ec1223b4016e966) => Transpositionentry(-15, 1, upperbound)
  Zobrist(0x491a5a230f24671a) => Transpositionentry(-75, 1, lowerbound)
  Zobrist(0x491a5a230f24671a) => Transpositionentry(55, 1, upperbound)
  Zobrist(0x491a5a230f24671a) => Transpositionentry(25, 1, upperbound)
  Zobrist(0x63b155121ea7907e) => Transpositionentry(-65, 1, upperbound)
  ....

As you can see, for example the zobrist key with the value “491a5a230f24671a” is more than one time in the dictionary and i don’t know how that is possible.

Does someone have an idea what the problem is?

1 Like
2

I think you might need to define isequal rather than == (although I thought isequal had a fallback to ==). also, you probably want immutable structs here. they will be faster

2 Likes
3

This may be caused by mutation of keys. I made a simpler example based on yours:

julia> mutable struct MyRef{T}  val::T  end
julia> Base.hash(a::MyRef, h::UInt) = xor(a.val, h)
julia> Base.:(==)(a::MyRef, b::MyRef) = a.val == b.val

julia> d = Dict{MyRef{Int}, Symbol}()
Dict{MyRef{Int64}, Symbol}()

julia> x = MyRef(0); y = MyRef(0); d[x] = :x; d[y] = :y; d # y replaces x
Dict{MyRef{Int64}, Symbol} with 1 entry:
  MyRef{Int64}(0) => :y

julia> y.val = 1; d[x] = :x; d # mutate y, now add x
Dict{MyRef{Int64}, Symbol} with 2 entries:
  MyRef{Int64}(1) => :y
  MyRef{Int64}(0) => :x

julia> y.val = 0; d # mutate y back, now same key as x
Dict{MyRef{Int64}, Symbol} with 2 entries:
  MyRef{Int64}(0) => :y
  MyRef{Int64}(0) => :x

julia> d[x], d[y] # uh oh
(:y, :y)
2 Likes
4

Good call. That’s the actual problem.

1 Like
5

We can’t say that’s the problem for sure, we don’t know what algorithm resulted in OP’s dictionary.

1 Like
6

Given how Zobrist hashes work and that Zobrist is a mutable struct, it’s highly likely that mutation is the problem. The solution would be to either make Zobrist an immutable struct and adapt the code as needed or simply key the transposition table on the Zobrist value rather than the object.

1 Like
7

Now that I look up Zobrist hashing, it doesn’t seem like a mutable object is necessary? I still don’t understand the algorithm at all, really.

For thoroughness, when a key is inserted, its index is computed by the hash function, and the index does not change. So if the key’s value changes in a way that also changes its hash value, you have a couple problems: 1) it cannot be used to find its own existing index, 2) another key with the previous value (and thus hash value) can be inserted.

I was really careful not to say mutable or immutable struct because 1) a mutable struct can have const fields or fixed properties like size(::Matrix), and the hash value is constant if it only depends on those, and 2) an immutable struct’s value and hash value can depend on a field holding a mutable instance e.g. many wrappers of mutable arrays are actually immutable structs.

1 Like