Problem session 3, 25 Sept 2002

Wrote a demonstration program, somewhat like performance art. Did this twice, so I wrote two different programs. The first was more fun, but on the other hand the second left us with more time to do various improvements which might be of interest. Things to look for are noted below.

Program one: Tic-Tac-Toe

Rules of the game:

Tic Tac Toe is played by two players on a three-by-three lattice. Each square can hold an "X" or an "O" or be empty. The board starts off all empty, and once tokens are placed they are not moved or removed. One player is "X" and the other is "O". "X" goes first and then the players take turns. A turn consists of placing a token of one's own kind on a previously blank square. As soon as someone has three tokens in a straight line (horizontal, vertical, or diagonal), that player wins. If the board fills up with no winner, it is a draw (tie).

Strategy of the program:

This program employs what I thought was a really cute idea for how to write a tic-tac-toe-playing program. It was suggested to me by Gary Baumgartner.

The program has no built-in strategy whatsoever. All it knows is the rules of the game. It "looks ahead" by playing the game to the end, recursively. It plays all possibilities. We assume that both players play optimally and then we decide which move we should make to achieve the optimal outcome. If a move will yield a win for us, that gets the value 1; if a tie, 0; if a loss, -1. So we choose one of the moves with the maximal value.

By using these particular three values, we make the recursion easier. How good a given position is for one player, is the arithmetic negation of how good it is for the other player.

Shortcuts:

Due to lack of time, we didn't do any input error checking. Also, there's no way for the user to tell what number they should type to move where they want. (The layout is actually as follows:

 0 | 1 | 2
---+---+---
 3 | 4 | 5
---+---+---
 6 | 7 | 8

)

The recursive howgood() function wasn't quite good enough to plug into computermove() as needed, but I didn't have time to fix it, so I ended up copying most of it into computermove() and hacking as applicable. This could be improved.

We hard-coded which of 'x' or 'o' is the user (as opposed to the computer), and who goes first. But both of these hard-codings consist solely of variable initializations which are fully used later; that is, to make these into options only involves writing code to solicit this information from the user, not any program enhancements.

Finally, the code:

ttt.c

I also wrote a quick Makefile to make the re-compiling cycle quicker, but I don't recommend looking at it; it's too trivial. The Makefile supplied with assignment one is less trivial but still really short. The Makefile supplied with assignment one is a good introductory example of a Makefile. There is a chapter on make in the King book. "make" might be covered in a future tutorial. It is certainly covered in CSC 209.

Program two: Nim

Rules of the game:

"Nim" is a two-player game played with sticks. The sticks are divided into piles. The players alternate turns. On each player's turn they may remove any number of sticks from one of the piles, up to the number of sticks remaining in that pile; but they can only take from a single pile on a given turn. The player must remove at least one stick.

The player who takes the last stick wins.

Try playing it

Consider an initial game position with piles as follows:

 1. XXX      (3 sticks)
 2. XXXXXX   (6 sticks)
 3. XXXXXX   (6 sticks)

First, try playing this where the computer goes first.

Afterwards, use your browser history or 'back' button to come back here, and try making your own move first, from that same position.

You can also try a full game with a random initial position.

Strategy of the program:

Nim-playing is a not-completely-trivial algorithm; I've described the theory behind it in a separate file called strategy.html.

Shortcuts:

Finally, the code:

nim.c

Other notables:

Unlike ttt.c, this program handles input properly. It loops (at least in some cases) if the user types an invalid input. This is harder than it might seem because scanf() is no longer good enough to use to parse the questionable input. We read an entire line at a time with fgets(), then parse that already-read line with sscanf(). sscanf() is like scanf() but doesn't do input; instead, it applies its scanning to a string which is already read-in.

Its randomization algorithm is terrible. Don't use that in other code unless you really don't care about the quality of random numbers. We'll talk about randomization in the topic of "simulation", third topic out of four in CSC 270.

[list of problem session notes] [main course page]