The idea comes from a handy utility class that I've written called Match. It contains a sequence of valid moves, the positions along this path, and the corresponding nodes in the graph. It had two basic operations:
- move: in the current position (the last one in the sequence), make a given move, expanding it in the graph if it didn't exist, and append this move and the new position to the match sequence.
- back: undo the last move, update the match to reflect the previous position.
Besides the nice abstraction that Match provides, it also takes care of the fact that sometimes there are transformation nodes in the graph, and hides it from the 'user', so the state graph can be explored as if there were no transformation nodes. All in all, introducing this class made everything much cleaner and nicer.
And now my idea is: if I have Match, do I even need the nodes? It seems to me very likely that I don't! The main use case (described above) is handled by the Match operations very comfortably. The big question is if there are any other ways it might be useful to interact with the game graph. If all of these interactions can be solved using Match instead of nodes, then I'm a happy camper.
The only major thing I can think of right now is the 'local search'. The match is at a certain point, and I'm waiting for the chess program to suggest to me which is the winning move, so that I go that way instead of exploring bad moves. While I'm waiting for an answer, I do a search on the graph to see if I can find a good move myself. It can happen, for example, that I'm at a position P, and there is a move M that leads to a position Q which I've already solved. The graph already contains a node with position Q and the result 'White wins', but this position had been reached a different way, and the edge between P and Q is not in the graph yet, so the result of P is still unknown. If I were to ask the graph to add move M, then it would find this Q node, and suddenly P would be solved.
It is very possible that the chess program considers a different move stronger, and would guide me in that direction. It can very well be that this move M is something that a player would never make; but following the 'best' route would involve adding more (possibly much-much more) nodes and positions to the graph unnecessarily. (It is unnecessary with regards to proving the result of P.)
It's like that joke about boiling water. You ask a physicist and a mathematician to boil some water in the tea pot, which you place on the table. The engineer picks up the pot, fills it with water, places it on the stove, and turns the flame on. The mathematician does the same. Next, you put a pot filled with water on the table. The engineer picks it up, places it on the stove, and turns the flame on. The mathematician pours out the water and replaces it onto the table, saying that now we have the original problem that has already been solved. In GameCracker, we want to be the mathematician, to solve positions with minimal work rather than finding 'optimal' solutions, to try to keep the state graph as small as possible.
I might have been sidetracked a bit. Anyway, this local search requires the graph to be able to answer the question: here's this position, what do you know about its result? Fortunately the concept of nodes is not necessary for this operation either. And I cannot think of anything else that would require code outside the graph implementation to be able to refer to individual nodes.
To sum up, I don't see any reason why this change would be a bad idea, but I see quite a number of advantages. I'm quite excited about this! Suddenly all the problems I talked about previously, as well as some other issues with nodes, are mitigated, and with a simpler API. All that was required was to question whether the concept of nodes, such an important part of graphs, was actually necessary to expose.
