Imagine that we use dots to represent states of the game; we call these the nodes of the graph. They don't have to be dots, they could be small drawings of the current board for easy visualization. Then from each of these nodes, we have arrows (or edges in graph terms) going out and pointing to different nodes. These represent the possible moves in the state corresponding to the node. It can be useful to put some textual representation of the move onto the arrow as a label just so we can easily find our way. Then we can imagine that actual matches are just a path in this graph, starting from the root node, which denotes the initial position, and moving along the edges which correspond to the moves that the players actually make. We can also think of this the other way around: if we start from the initial position and move along the edges until we reach a node which has no outgoing arrows, no legal moves, then the path we take defines a valid match that could possibly happen between two players.
Just so I can talk about stuff, let me define a couple of notions. I call a state S2 a child of another state S1, if there is an edge leading from node S1 to S2, or (in different words) if there is a move in S1 which results in S2. Appropriately, I call S1 the parent of S2, because you can get to S2 from S1 with a move. Finally, I will use the term leaf to refer to nodes which have no children, these are the end positions of the game.
Now I think is time for an illustration.
My main point with this is that state graphs are huge. Even in a game as simple and limited as tic-tac-toe, the number of nodes is enormous. The graph, up to 5 moves (which is the length of the shortest possible match) contains 18730 nodes. If we consider chess, or some other, more interesting game, the size of the state graph is astronomical.
My program works by building up a part of this graph. It will never need the entirety of it due to how results are proven, which I described in my previous entry. As an example, suppose that chess can be won by White after the first move e2-e4. In this case, all the other 19 moves that White could start with are totally uninteresting and there is no need to consider them. This makes huge parts of the state graph irrelevant that we do not need to build up, because they are not needed for the proof of White's win in the initial position.
Another thing that I mentioned previously is that I definitely want to avoid doing the same work multiple times. In terms of the graph, this means checking if a new state that we come across is equivalent to one which we have already encountered and added to the graph. If it is, we can just draw the arrow to this existing state and not have to create two instances of everything beneath it. Example incoming!
Nothing complicated is happening. This does mean that nodes can have multiple parents, but administering this is a small price to pay.
I have described a different kind of equivalence, where two states are not the same, but are symmetrical, and thus we still don't need to examine both of them. These I handle differently, since just plainly connecting them would violate what the arrows mean. In order to note that this move leads to a state that is related an existing one through some transformation, I use a different kind of node, which I call transformation node (and, in contrast, I call normal nodes ... normal nodes). The semantics of edges leaving a transformation nodes are different, they do not model moves, they model the transformation. So each transformation node has a single arrow leaving it, and this arrow points to the other, symmetrical state. I also store the exact transformation in the node. Example to the rescue!
What I have drawn here is the same subgraph of the tic-tac-toe graph as in the first illustration, but using transformation nodes. Due to the fact that I have included only ten states in the first place, we cannot see any great benefits at first glance (we still have ten nodes), but note that originally there were seven nodes which required further work, now there are only three. Once we have added a transformation node, we basically don't have to worry about it as an individual state, only the normal node that it references. Of course when we move around in the graph, we need to take special care around transformation nodes, they will not need any extra effort to prove beyond what is needed for the corresponding normal node.
So this is the basic structure. Tune in for the next time when I describe how the result of the individual nodes are created in a way that also provides all the aspects of provability that I talked about in the previous entry.
Nincsenek megjegyzések:
Megjegyzés küldése