So, let's think about games like checkers, chess, tic-tac-toe, connect four. First, no information is hidden from either player, and nothing is random. Two players play, one at a time. Each player carefully considers a move and then makes one. How do we consider moves? I don't think any person does it exactly the same way, but usually one imagines taking a move and asks "Is it good if I move here?", doing that over and over until a really good one is found, or all possible moves are considered. After that, we play the move.
All of these games start with the board in some state. In chess and checkers, the peices are carefully placed in a certain order, starting the game in a certain position. In tic-tac-toe and connect four, the board is blank.
We can think of a "move" as the action of going from one position of the board (field of play) to another position. The rules of the game restrict these positions to only the possible positions to play. We'll call "possible positions to play" a player's options.
So, after many moves and considerations of moves, what happens? How does a game end? Well, in tic-tac-toe either a player has "three in a row" or be board is full and neither player can move. Hmm. In chess one player wins when the other's king can't move or stay put, so that player has no legal moves, checkmate. Also, play ends when the same three moves are repeated, or when neither player can possibly checkmate. In connect four we find the same situation as tic-tac-toe. Either a player gets "four in a row" or the board fills up entirely. In checkers we have a player winning when the other player either cannot move or has no pieces on the board (and thus cannot move).
There seems to be a common thread: A game ends when a player cannot move. The player that cannot move loses. It is trivial to add the following rule in connect four and tic-tac-toe: when a player moves to a position where they have 3 or 4 pieces or spaces in a row, the other player cannot move the next turn.
So what we have, then, is a list of what we want our mathematical model of a game to have:
- 2 players taking alternate turns
- Players play a strategy by asking "is this a good move?"
- Nothing hidden or random
- Games starting in a specific position
- A player wins when the other cannot move.
This doesn't say anything about ties - in fact it says that in the case of a tie, the last person to move wins, but perhaps we can extend a theory of games to include ties - we should have a clear idea of what it means to win and lose before we think about neither winning or losing.
So, what mathematical structures will have what we want? We want a way to move from a position to a possible position, chosen from many options. We want to be able to denote a game, and we want this notation to apply to all games that we find. It would be useful if we could find universal strategies for games, so that we know how to win if we're playing them.
With each post, I will have a game for you to explore and play. Life is great, but there are sometimes lulls - thinking about and playing these games is easy and free, usually they can be played on a napkin at a table at a restaurant or just on some paper at home. Experiment with the games, restricting rules or adding others and see how play changes.
This time's game: Sprouts
Sprouts is a pen-and-paper game, played with dots and lines on a piece of paper. This game starts with a number of dots drawn on the paper. Players then connect the dots with a line, straight or not straight, that cannot intersect with other lines. Then a dot is drawn somewhere on the new line. A dot cannot have more than three lines coming out of it.
To shake things up a bit, I've played Sprouts with more than two players, and by increasing the number of lines that can come out of a dot.
Example:
Start:
End:
Check back often!
