The original FF already used state hashing to help identify previously visited states, with a full comparison of states in case of a collision. Each fact of a planning problem is assigned a unique 32-bit random number, and the hash code of a problem state is the sum of all random numbers associated to the facts that characterize the given state. Profiling runs showed that in some domains up to 35% of the CPU time is spent in the comparison of states. These are in particular domains with large states and small graphplan structures such as PSR and Philosophers. We replaced the original hash key by a 64-bit Zobrist hash key implementation, a standard technique in game-tree search [20]. Each fact is assigned 64-bit random number, and the hash key of a state is obtained applying the XOR operator to the random numbers corresponding to all facts true in the state.
When checking if two states are identical, only their hash codes are compared. If the hash codes are different, than the states are guaranteed to be different too. If the two compared states have the same hash code, we assume that the states are identical. This choice gives up completeness of a search algorithm: two different states with the same hash code can exist. However, this is so unlikely to occur that fast state comparison based on 64-bit Zobrist hashing is a common standard in high-performance game-playing programs. The large size of the hash key and the better randomization makes the occurrence of hash collisions much less probable than random hardware errors.