Board cannot be the key to a HashMap

[Nicholas-Baron]

I want to use a board state (represented by the Board struct in this library) as a key to a HashMap. This is for a chess engine I am writing for fun.

std::collections::Hashmap requires that its key be Eq and Hash. Both should be doable, yet are not in this library. Checking the struct definition and cross-referencing with cargo doc --open in my project reveals that the following:

• the only type which needs Eq and Hash as well is Bitboard
• Color, and Square are already Hash and Eq
• CastleRights has Hash, but no Eq (only PartialEq)

As Bitboard is just a wrapper around a u64, it seems as simple as adding Hash, Eq into the #[derive]. Once that is done, it is probably a similar matter for Board and CastleRights.

To-do List / Summary (in no particular order)

• Hash for Bitboard
• Eq for Bitboard
• Hash for Board
• Eq for CastleRights
• Eq for Board

[jordanbray]

I'm not opposed to implementing this, but the library does have a CacheTable type and zobrist hash functions. I believe we could implement hash directly and just return the current hash of the board. It's a field that's incrementally updated in the board for performance purposes. That said, I don't see a reason to 'not' implement hash or eq on the types where it can be.

…

On Mon, Mar 1, 2021, 9:42 PM Nicholas Baron ***@***.***> wrote: I want to use a board state (represented by the Board struct in this library) as a key to a HashMap. This is for a chess engine I am writing for fun. std::collections::Hashmap requires that its key be Eq and Hash. Both should be doable, yet are not in this library. Checking the struct definition <https://github.com/jordanbray/chess/blob/a09032e36a1d10fdeab163afd943df66c00b897b/src/board.rs#L24> and cross-referencing with cargo doc --open in my project reveals that the following: - the only type which needs Eq and Hash as well is Bitboard - Color, and Square are already Hash and Eq - CastleRights has Hash, but no Eq (only PartialEq) As Bitboard is just a wrapper around a u64, it seems as simple as adding Hash, Eq into the #[derive]. Once that is done, it is probably a similar matter for Board and CastleRights. To-do List / Summary (in no particular order) - Hash for Bitboard - Eq for Bitboard - Hash for Board - Eq for CastleRights - Eq for Board — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#44>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AADJ5PILNOIRXWVB5MGUMY3TBRGADANCNFSM4YN2EGYA> .

[Nicholas-Baron]

@jordanbray If I understand this correctly, Bitboard and CastleRights would just #[derive(Hash, Eq)], while Board would #[derive(Eq)] and have an impl Hash that just returns self.hash?

CacheTable has pretty strict requirements (I consider Copy "strict" as it means only "lightweight" types should be used) and I would be more comfortable using the Rust standard HashMap.

[jordanbray]

That all looks reasonable to me. I don't see why MoveGen, Square, Rank, File and anything else should be excluded from the new derives. Yes, CacheTable actually has even stricter requirements than that: 1. The size of the hash table must be a power of 2. 2. When inserting, items are overwritten. There's no mechanism for dealing with collisions. It's true purpose is for iterative deepening which requires you to cache existing values, and pawn evaluation caching. If you're doing either of those things, CacheTable is probably better for you than HashMap. It just has so much lower overhead thanks to the stricter requirements. It may not match you're use case though.

…

On Mon, Mar 1, 2021, 11:10 PM Nicholas Baron ***@***.***> wrote: @jordanbray <https://github.com/jordanbray> If I understand this correctly, Bitboard and CastleRights would just #[derive(Hash, Eq)], while Board would #[derive(Eq)] *and* have an impl Hash that just returns self.hash? CacheTable has pretty strict requirements (I consider Copy "strict" as it means only "lightweight" types should be used) and I would be more comfortable using the Rust standard HashMap. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#44 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AADJ5PP3OUSXALEUPW2NB2LTBRQLZANCNFSM4YN2EGYA> .

[Nicholas-Baron]

@jordanbray PR #45 ready for review.