Node isomorphism refers to the situation in which two nodes correspond to identical hand configurations with equal number of tricks taken by N/S. Node isomorphism can be implemented by maintaining a list of configurations and their associated values, indicating which partnership, N/S or E/W, will prevail starting from that configuration. When encountering a configuration, C, the list is checked to determine whether C is listed. If it is, then the value of configuration C can be obtained from the stored value, thereby avoiding the necessity of expanding the entire tree of possibilities. If it is not, then the pair [C,unknown] is entered onto the list and, after C has been evaluated (say, to find that N/S will prevail) then this entry is updated (to become [C,N/S]).
For difficult problems, the number of encountered configurations can be so large that there will not be enough space to store all of them. In that situation, it is effective to store the configurations that will have the most impact in avoiding tree expansion. Also, for speed considerations, it is important that the list be searchable very rapidly. These various concerns can be addressed efficiently and effectively by using a variant of Robin Hood hashing. For very difficult problems, additional speed enhancements might be possible by use of a Bloom filter.
To obtain the greatest benefit, it is best that the hash table have the largest size possible. The size of the table is not the number of bytes stored in the table -- it is the maximum number of entries that can be stored in the table. It is true that increasing the number of bytes available for the table will increase the number of entries. But equally effective, and even more important for speed considerations, is the fact that decreasing the number of bytes required for one entry will increase the maximum number of entries that can be held by a table having capacity of a fixed number of bytes.
I encode a configuration in 8 bytes. When it is possible that an output tree will be produced, each configuration requires an additional 4 bytes. Also, producing an output tree necessitates the use of a rather large stack, typically allowed 1-2 Megs.
The stack contains the body of what will ultimately be the tree file. The tree file format is roughly as follows. There is a primary header, which describes the initial state of the program (number of cards per player, who are the "goodguys",etc.) a secondary header, which describes the contents of the 4 hands, and the body, which contains one word that gives the number of words in the rest of the body and then a series of cells that are stored in depth-first search order. A cell describes a trick. It contains: