Name Date Period

← CS Unplugged

CS Unplugged activity

The Paper Othello Player

About 30 minutesPairPencil, and coins or counters if you have them

In The Paper That Never Loses, the Paper always won or drew at tic-tac-toe, because a program can check every possible tic-tac-toe game there is. Othello has far too many possible games to check them all, so this time the Paper can only follow rules of thumb, called heuristics. Play against it and find out: can you make it lose?

The rules of Othello

Play on a 6 by 6 board. Start with four discs in the middle, as shown on the boards below.

1. Black always moves first.
2. On your turn, place one disc so it traps a straight line (row, column, or diagonal) of the other color between your new disc and one of your own.
3. Flip every trapped disc to your color, right away.
4. No legal move (nothing to trap)? Say “pass.” Your turn is skipped and the other player goes again.
5. The game ends when neither player has a legal move. Count the discs. Whoever has more discs wins.

See it happen. Before Black’s first move, the board looks like this. Black plays at c2, trapping the White disc at c3 between the new disc and the Black disc already at c4, so c3 flips to Black.

Before

		W	B
		B	W

→

After: Black plays c2

		B
		B	B
		B	W

The Paper’s program

The Paper only follows these rules, checked in order, top to bottom. It never thinks, it never guesses; only legal moves ever count.

1. If a legal move takes a corner (a1, f1, a6, or f6), play it.
2. Cross off any legal move that touches an empty corner, even diagonally, unless that would cross off every legal move. (Those squares hand the corner to the other player next turn.)
3. If a legal move is left on an edge square (touching the border, not a corner), play it.
4. Otherwise, play the legal move that flips the most discs.

Still tied after a rule? Play the move closest to the top of the board; if still tied, play the one farthest to the left. Working through this program from the very first move gives c2, the same move shown above.

How to play.

1. Decide who runs the Paper and who plays the Human.
2. Whoever runs the Paper follows its program exactly. No thinking allowed. The Paper is Black and always goes first.
3. The Human is White. Play your best move each turn.
4. When the game ends, count the discs and write the score below.
5. Swap jobs and play again on the next board.

Game	Paper’s discs	Human’s discs	Who won
1
2

Game 1

	a	b	c	d	e	f
1
2
3			W	B
4			B	W
5
6

Game 2 (swap roles)

	a	b	c	d	e	f
1
2
3			W	B
4			B	W
5
6

Your turn. Change one rule in the Paper’s program. For example, swap rules 3 and 4, or add a brand new rule near the top. Play at least one more game with your changed program. (Erase one of the boards above and reuse it, or ask for another sheet.)

Which rule did you change, and how?
Did the Paper do better or worse?