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.