GameCracker - 4. Results

I've described the state graph of a game, and how results of certain states can be proven. I've also talked a little bit about how I store only a small portion of the entire state graph, as small as necessary for my purposes. From now on, when I say 'graph', I will mean the data structure of my program, consisting of normal and transformation nodes, and (usually) having a whole lot of edges that do not connect to anything. I call these edges 'unexpanded moves', for some reason.

There's an important aspect of the graph that I need to mention. In order to facilitate proofs, I attach to each node a result field, which indicates the most information that we currently know about the result of the state. In the early days of development, this field had four possible values: Unknown, WhiteWins, BlackWins, and Draw. Then I realized that by adding two more, I can further reduce the size of my graph. These additional values are WhiteWontWin (meaning that the actual result will be either Draw or BlackWins) and BlackWontWin.

In order to see how these values help, imagine that we are in a state 'A' where White is to move, and there is still a possibility that at least one of White's moves will lead to her winning the match. Let's call one of these moves (and also the state that this move leads to) 'P' for 'possibly good'. Now, if we find out that a move leads to a state in which the result is WhiteWontWin (let's call this move and state 'BD' for 'BlackWins or Draw'), then it is greatly beneficial to postpone the examination of this move and first consider 'P', which still might lead to a WhiteWins state. Here's why. If the actual result of this state 'A' is WhiteWins, then we will need to find a move which leads to a WhiteWins state; the 'BD' move is obviously not the correct one, and we won't need the actual result of this move for our proof, so calculating it is a waste of time, building this part of the graph is unnecessary. On the other hand, if the actual result of the state 'A' is not WhiteWins, then to prove it, we will need to prove that none of the moves can bring victory to White, and this includes finding out more about 'P'. So we will need to work with 'P', and there is a possibility that we won't need to work with 'BD', and this latter fact we wouldn't know if there weren't a WhiteWontWin state, if BD were still Unknown.

Proving something about P will be necessary for proving anything about A. However, trying to proving something more about BD might be a waste of time.

Now, to the main point of this entry. The graph object provides a single important operation (other than being able to more around in it). Given a node and a move from this node that isn't connected to anything yet, this operation connects this 'unexpanded' node; I call this operation 'expand'. Two very important operations need to be performed during expansion. The first is the update of the results of any nodes for which this new connection allows us to prove something more than we could before. It is of utmost importance that the result value of every single node is always up-to-date and is the most concrete possible. The second task is to try and find an existing node which is equivalent to the new state, so that we won't have multiple instances of the same subgraph. I'll come back to this latter issue, because in this entry, we're talking about results.

So how to update the results during expansion? There are two cases when we obtain additional information. One is when we add a new node to the graph which contains an end state. (In end states, we know the result by definition: it is the result of the match.) The other is when a connection is made to an existing node in which we have a non-Unknown result. Both cases might provide some information on the result of the current node, the one which is being expanded, so we update its result. A result update consists of a recalculation of the result, and - if the new result is different from our previous knowledge - a recursive update of all the parents of this node (for this reason it is important to store references to the parent nodes). Recalculation is performed along the lines described in the second entry of this series, but of course extended for the two additional -WontWin possibilities. I think it is not too interesting an algorithm to describe here; I basically drew a big table with all the possibilities regarding the results we can find among the next-states, and see what we could say. I needed to be careful so that I don't accidentally label a state with a result which is too weak (like say that it is Unknown when WhiteWontWin can be proven, or say that it is WhiteWontWin when Draw can be proven etc.). Now this algorithm is in place, and I don't need to worry about it, I just need to choose the next state and move to expand, in a way which preferably results in the smallest number of expansions.

That's all for this entry. Next time I talk about the other aspect of expansion, the search for equivalent states. The reason this will be an issue is of course the humongous number of nodes in the graph.