opensource.dyc.edu

Games are interesting. We like games that simulate reality and put us into situations which we would otherwise avoid. We like games that are abstract and put us into worlds nothing like our own and with their own rules. We like games of chance, estimating the odds and taking risks. We like games of logic, thinking ahead, calculating scenarios, strategizing and winning. Or losing with dignity :) We like challenges in which loss is a real possibility because it makes winning meaningful. We examine our strategies, recognize our errors, and strive for improvement next time. But, the geek in us likes games for another reason. They give us the opportunity to play a meta game, ie. a game of games, better known as "Game Theory."

If we restrict ourselves to games of simple logic, devoid of chance or complex rules that attempt to simulate, then it should be possible to develop an algorithm which exhaustively searches all possibile outcomes of a particular situation in a game to see what the optimal next move should be. For example, suppose the computer plays white in a game of chess. Then it should be possible for it to enumerate all its possible opening moves, for each of these move to enumerate all possible responses, for each response to enumerate all possible counter responses, etc., until either white wins, or black wins, or the game ends in stalemate. Having all this information in memory, the computer can then choose what opening move to make based on where it will lead: choose a move if it leads to a win, avoid it if it leads to a loss or stalemate. Or, given that it might not be able to achive a win, the algorithm can at least try to head to a stalemate.

Easy no? A bit of coding, some testing, late nights, coffee, and its done. We start the program up and wait ... wait .. wait ... until we are out of memory. We swap to drive, run, wait even longer, and run out of memory again. We then sit down, calculate how many possible games of chess there are and we find that the number is about 10^120. We pause and realize that this is bigger than the estimated number of particles in the universe, which is about 10^90. Even if we could write an entire chess game on one subatomic particle (I'm not even sure we can put a bit on one), we would run out of matter in the universe before solving the problem this way. Reflecting further, we realize that our minds open up onto spaces bigger than space itself. We become mystical and go meditate on the meaning of consciousness on top of a mountain somewhere in the Himalayas.

Or maybe not. The persistant geek in us would go back to our meta game of games and reconsider our focus. Either we find other more heuristic methods to broach these large spaces, or we stick to the exhaustive search algorithm and pick games with smaller spaces. In this work, we have chosen the latter and looked at four simple games with large but tractable spaces: coin strip, welters game, mancala and sudoku. The former I first learned about from John Conway. Mancala and Sudoku I remember from my youth. Of these, Sudoku is better described as a puzzle than a game, but from our perspective it is simply a one player game rather than a two player. The others are true games in the sense that there are two players who take turns until either one or the other wins, or, in the case of mancala, there is a tie.

For each of these games we present perl scripts which first generate the entire game space, labeling each state as either a sure winner, a sure looser or a tie. Then a second set of scripts read this data and plays the game accordingly. Needless to say, one cannot win against this algorithm, so the games are not much fun to play! Resistance is futile! So the pleasure you'll have to derive is a meta pleasure! The solutions we present may serve as a good reference against other game playing algorithms. The next challenge is to produce good heuristic algorithms that minimize speed while simultaneously giving the exhaustive algorithm a run for its money.