Replace Hashing method - Githubissues

notnil / chess

chess package for go

MIT License

518 stars 130 forks source link

Replace Hashing method #28

Open Kerrigan29a opened 5 years ago

Kerrigan29a commented 5 years ago

The hashing method it's very expensive (because of the MD5 dependency) to use it in any cache or transposition table. I suggest to implement Zobrist hashing wich is the de-facto standard.

Possible reference implementations:

dylhunn/dragontoothmg (Go): https://github.com/dylhunn/dragontoothmg/blob/b0146de1e275d419ae46e1f36d3cec255d5a2a7b/util.go#L11
niklasf/python-chess (Python): https://github.com/niklasf/python-chess/blob/f4e7c53a3695af6d5e14da04e69fcb862f378cac/chess/polyglot.py#L230, https://github.com/dylhunn/dragontoothmg/blob/b0146de1e275d419ae46e1f36d3cec255d5a2a7b/constants.go#L21
lemire/zobristhashing (C): https://github.com/lemire/zobristhashing/blob/f51882643d27845e5017bcbdcac79f2522c33532/src/zobrist.c

notnil commented 5 years ago

Love it. Ill take a look at it this weekend. @Kerrigan29a if you want to take a stab to compare benchmarks Ill review before then. Also the CPU profiler might be useful.

Kerrigan29a commented 4 years ago

I have implemented it. You can find in #49

notnil commented 4 years ago

@Kerrigan29a thanks for the pull. I will review it. Definitely a better approach than the current implementation, but I don't like the dependencies outside the standard lib. I have tried to keep those down historically (not as relevant today with module additions). They seem to be used to test for collisions which I totally get but adds a lot of distraction to the repo for just the hash. Let me think on it.

Kerrigan29a commented 4 years ago

You are welcome. I used golang.org/x/text/language and golang.org/x/text/message in the tool to view big numbers with thousands separator. Remove it if you want and just use fmt.Printf or remove the entire collision checking tools.