Simmetrie about monkey HOT 4 CLOSED

Fare una tabella a indirizzamento diretto rispetto a una tabella hash

from monkey.

In Chapter 3, we noted that repeated states in the search tree can cause an exponential increase in search cost. In many games, repeated states occur frequently because of transpo- sitions—different permutations of the move sequence that end up in the same position. For example, if White has one move, a1, that can be answered by Black with b1 and an unre- lated move a2 on the other side of the board that can be answered by b2, then the sequences [a1, b1, a2, b2] and [a2, b2, a1, b1] both end up in the same position. It is worthwhile to store the evaluation of the resulting position in a hash table the first time it is encountered so that we don’t have to recompute it on subsequent occurrences. The hash table of previously seen positions is traditionally called a transposition table; it is essentially identical to the explored list in GRAPH-SEARCH (Section 3.3). Using a transposition table can have a dramatic effect, sometimes as much as doubling the reachable search depth in chess. On the other hand, if we are evaluating a million nodes per second, at some point it is not practical to keep all of them in the transposition table. Various strategies have been used to choose which nodes to keep and which to discard.

from monkey.

Equivalence table hashing: https://en.wikipedia.org/wiki/Zobrist_hashing

from monkey.

• numero di classi di equivalenza non gestibile
• Zobrist hashing VS BHC hashing: molto simili, ma Zobrist ha più letteratura a disposizione
• hashmap già presente in Java

from monkey.