CODEWITHSUNDEEP
c#dictionarykey
Chronicide
Chronicide

Reputation: 1152

How do I reference the properties of a reference type dictionary key?

I'm working on a chess engine, and I'm currently implementing the transposition table (a set of already evaluated board positions from past moves). The general idea is that when a move is made, I check the transposition table for a matching position. If it exists, I skip the costly evaluation process and just pull the previously calculated results from the transposition table. If it doesn't exist, I do the required calculations and then add it to the transposition table for future reference.

To me, this sounds like a job for a hashset or a dictionary. I decided upon the dictionary. I wanted the key to be the class representing my board, and the value to be an int count of how many times the position has been encountered. The reason for the count is to be able to detect a threefold repetition draw. If the same position has been encountered three or more times, the player has the option to call a draw. Using a dictionary instead of a hashset allows me to greatly simplify the detection of a threefold repetition draw by combining it with my transposition table.

In order to do this, I've made the class that represents a board's state override Equals() and GetHashCode(). It works just fine, and I now am able to keep track of all of the historical states that a game previously encountered.

My problem is that I need to be able to access the properties of the key object in the dictionary. I can see whether a match exists (by using the .ContainsKey(...) method and my Equals()/GetHashCode() logic), but now I need to pull the previously mentioned calculated values (stored as public properties of my board state object) from the key.

I was able to come up with:

BoardState board = TranspositionTable.Keys.FirstOrDefault(tt => tt.GetHashCode() == this.GetHashCode());

This works, but feels clunky to me. The whole point of the transposition table is to speed up a recursive search of millions of successive board states. Querying a dictionary for each match just sounds counter-intuitive. Is there a better way to do this?

EDIT:

As it's been pointed out, my hash couldn't be perfect due to the huge number of valid board states. My Equals() override checks a second alternatively generated hash to reduce the possibilities of collisions. My above 'solution' is flawed, as it relys on an imperfect hash. I should have used:

BoardState board = TranspositionTable.Keys.FirstOrDefault(tt => tt.Equals(this));

A stupid oversight on my part. Still, I'm not a fan a querying dictionaries.

Upvotes: 4

Views: 200

Answers (1)

Servy
Servy

Reputation: 203834

One option is to just hold a reference to the key in the value of the dictionary, as well as the actual value of the dictionary, like so:

Dictionary<BoardState, Tuple<BoardState, int>>

Then whenever you add an object add the same object to the value as to the key:

Dictionary<BoardState, Tuple<BoardState, int>> boards = 
    new Dictionary<BoardState,Tuple<BoardState,int>>();
BoardState board = new BoardState();
boards.Add(board, Tuple.Create(board, 1));

The other option (which is probably better design) is to break up your board state object into two different types. Have one which really does just represent the state of the board (this should be immutable), and another that holds the other information about that state including the times it has occurred and any other mutable attributes that may apply to your specific application. This would prevent you from needing to access the dictionary key.

Upvotes: 2

Related Questions