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.

GameCracker - 3. Graphs

The data structure that I use is (a subset of) the state graph of the game. The state graph is a useful model of the game in its entirety.

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.

 

It is a very-very small part of the state graph of tic-tac-toe. In the actual graph, the root node has nine children, each of these nine children have eight children of their own, which means that if I wanted to draw the entire graph but only up to two moves, that would mean 1+9+9*8=82 nodes, so now you can probably forgive me for only drawing 9 of them, it was not only laziness.

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.

GameCracker - 2. From simple to not so much

The little pseudo-code I gave in the previous entry is a pretty straightforward algorithm to determine the result of a game state. Nevertheless, that is not quite how I do it. It actually had never occured to me to implement the program this way, and now that I have thought about the reasons, I can give you two.

First of all, it is not sufficient for me that my program tells me the result of a state: I need it to be able to prove what it claims. By this I mean that taking on the role of the player to move in that state, the program must be able to achieve the claimed result against any opponent, against any sequence of moves; and on the other hand, it must be able to prove that a better result can always be prevented by the opponent. This is a pretty abstract formulation, so let me be more concrete. Suppose that we are in a state where it is White's turn to move. If the program says that White will win, proving this means providing a move, and (recursively) proving that the state after the move is also a win for White. To prove a draw result, it has to be able to indicate a move, proving that the state after the move is a draw, and also proving that none of White's moves will bring her victory. Finally, Black's win can be proven by showing that the state after every single one of White's moves is a loss for her.

Maybe I'm talking a bit too much about the concept of proving a result, but I'll just describe it from another aspect. Suppose that the program has solved the initial state of a game. If it turns out to be a win for White, the fact that my program can prove this claim means that by playing White, it can always win, against anyone, no matter what. In case of a draw, my program playing White can always achieve at least draw (so it will never lose), but this alone isn't enough, it needs to be shown that White has no winning move. Proving this means that the program has to also be able to achieve at least a draw when playing Black. Finally, if chess is actually winnable by Black, then of course my program must be able to win with the black pieces. And one last thing: when the program is actually playing one of these games, I want it to be able to give the correct moves in a very short time, basically using some look-up method, and not by performing a search like chess engines do. This would not be possible using the simple algorithm.

The second reason against it is that there are a lot of possibilities in a game. And I mean lot. I did say that I disregard any actual time and storage requirements, but still, there is one significant way of reducing the size of the work needed to prove results that I won't ignore. And it is to avoid calculating the result of a state multiple times.

Let us consider chess. Suppose that, after ten years of work, the program has finally obtained the result of the state after moves 1. e2-e4, e7-e6; 2. d2-d3, d7-d5. Suppose also that later the program finds itself at a point where it needs the result of the state after moves 1. e2-e4, d7-d5; 2. d2-d3, e7-e6. This is the exact same state as the previous one, but the naive little algorithm doesn't know that, and spends another ten years wth this state. I definitely want to avoid this. Now let me go one step further. There are also states that are, although different, similar enough so that the proof the program finds for the result of one is applicable to the other. I call this relationship either symmetry or equivalence. Reversi is an excellent example. In the starting position, White has four possible moves, but the resulting positions are symmetrical, basically the same. You just have to apply a transformation to the board (a rotation or a reflection) to get one from the other, and the proof for one is applicable to the other by applying the same transformation to the moves themselves.

So these were my two needs: the ability to prove claims about results of game states, and the ability to avoid computation of equivalent states. Next time, I'll describe how I've built GameCracker with these requirements in mind.

GameCracker - 1. Introduction

Let us consider two-player games. Not games of chance, like card games, where the players do not have all the information. I am interested in games like reversi or chess, where the players perform moves (usually taking turns), and the rules of the game stipulates what moves are legal in a certain state, and exactly what new state the move will lead to. For these games, it is in theory possible to determine which player can win provided that they both play perfectly. Let me demonstrate this fairly obvious fact with some pseudocode.

WhoWillWin(state):
  if state.isGameOver: return state.result
  canBeDraw = false
  playerToMove = state.playerToMove
  for each move in state.moves:
    whoWinsAfterMove = WhoWillWin(state.move(move))
    if whoWinsAfterMove == playerToMove: return playerToMove
    if (whoWinsAfterMove == DRAW): canBeDraw = true
  if canBeDraw: return DRAW
  return playerToMove.opponent

This will determine the result of the game starting from an arbitrary state. Let me just write out how this works in prose. Let us call the player to move White, and her opponent Black. The WhoWillWin function checks if White has any moves which lead to her win; if there are, then she can win now by choosing that move. If she does not have a winning move, then she still might achieve a draw (for games in which there is such a thing at all). So if she has a move which leads to a draw, she should obviously choose it, since we have already established that she cannot win. If none of her moves lead to a win or a draw, that means that Black will win no matter what White moves, so the current state is a win for Black as well. It is as simple as that, whether the game in question is tic-tac-toe, reversi, or chess. (Incidentally, these are the games that I will keep mentioning as examples.)

There are a couple of things we need to stipulate for this algorithm to work. First of all, the game must end after a limited number of moves, otherwise our recursive function might get trapped in an infinite sequence of moves, never finding a game-over. Fortunately, tic-tac-toe cannot last longer than 9 moves, reversi takes at most 60, and chess also cannot go on indefinitely thanks to the 50-move draw rule (though I will not bother to calculate the maximum possible length of a chess match, I'm not that interested).

Another requirement is that there is always a finite number of possible moves. If this is not the case, then of course the for-loop might never terminate. There was a game popular in my school days, a variation of tic-tac-toe, where you had to get 5 in a row, and the board had no bounds. You could place your X or O however far away you wanted. (The matches could also go on forever, at least in theory. In practice, they never did.) This is the only real counter-example I can think of, but I can imagine games where the players take turns placing points on a line or in a geometric area, and of course the continuous domain would imply an infinite number of possible moves, even if the length of the match were limited.

Basically that's all we need. There are some other, fairly obvious requirements, like that the current state and the move must determine the state after the move is made (so nothing random), or that the result of a game is either a draw or one of the players winning. But now we can probably see that there is a good chunk of games that can be 'solved' using this method, by feeding the initial position to the function. A different question is whether it is practical to do so. The answer is obviously 'yes' for tic-tac-toe, and obviously 'no' for chess. But let us ignore this for now.

I have a program that can, given 'sufficient' time and storage capacity, solve such games. I call it GameCracker, and I plan to describe some aspects of it in this blog. Mostly for my own benefit, kind of as a documentation, but still, putting it out there. And I think this is good enough for an introduction.