|
I'm revising for an examination and I'm trying to figure out why symmetry is significant? The question I'm stuck on is the following... There is symmetry in the game Nine Men's Morris, what difficulty is there in exploiting the Symmetry whilst using Zobrist Hashing? How would you overcome this issue? What advantage can be gained from doing so? |
|
I don't know anything about Nine Men's Morris. But in general, when you are using Zobrist Hashing, you are converting a game state into a hash. You use this hash to keep track of the value (say, probability of winning, or a heuristic score) of the state. If you have two symmetric game states, they logically have the same value so that you can re-use it rather than recompute it every time you have to deal with that state. If you were to hash symettric states to the same hash, then you can re-use the same value, and you avoid doing repeated computation and can save memory (whose waste factor is proportional to the number of symmetries not exploited). The problem is that you need to write a state cannonicalization function that turns any member of a set of symmetric states into the same canonical member. Often such functions will take time proportional to the size of the game state (if you imagine generalizing your game so that it supports a larger board or more pieces, cannonilization in the bigger game gets harder). This destroys one advantage of Zobrist hashing, in that it is very fast, taking only a couple of instructions from a move and a previous hash. Zobrist hashing will always take only a couple of instructions, regardless of how complex your game/game states are. |
