GameCracker - 5. Categories

I have described why it is bad if we don't realize that a new state is the same or (symmetrically) equivalent to one that is already in the graph. I need all the help I can get when it comes to reducing the number of nodes. However, even if I do the best job possible, then - for complex games like chess - I still need an enormous number of different states to prove any interesting results. So searching the graph to see if a new state is a duplicate can be a serious issue. In particular, traversing the graph is out of the question.

My solution is the concept of categories. A category is basically a hash: a number that I assign to the states and I require that for symmetrical states, the category be the same. Then when a new state is about to be added as a result of an expansion, I query the category of this new state, and with this in my hand, I only need to check the nodes for which the category is the same (since, by definition, states with a different category cannot be related).

To implement this, I have included links in nodes which point to the next node of the same category. So for each category, I have a linked list, which I call a category chain, containing the relevant nodes. When searching for a related state, I just walk through the chain for the appropriate category, and if I don't find a match, then I can safely say that this state is new. The structure storing the category chains is a mapping from the category to the first node of the chain; this I call category heads.

Since adding new states to the graph is the elementary operation of the program, I need the search to be quick, I need the category chains to be short. This means that the categories need to be good hashes, with few duplicates, many different values for different states. On the other hand, if there are too many categories, then storing and accessing the heads quickly can also be an issue. Finally, if symmetrical equivalences are possible, then the creation of the category number itself can be difficult as well; extracting the most information possible into the value while making sure that all the transformed versions of this state produce the same category.

I will probably come back to some of these issues later, but for now, I have introduced the concept of categories, quite an important component of the program, and there are a couple more significant things I want to cover before delving into details.