The Intelligent Piece of Paper
First, you have the students play a game of tic-tac-toe with a partner. Then, you have them play two or three more games, keeping track of who did what move in what order (so for example, ‘Player 1 put an X in the left top corner first. Player two put an O in the center square next)
Then, they try to ‘program’ a piece of paper to first play a game of tic tac toe without cheating, and then (hopefully) to win. It’s about figuring out the logic behind programming (and also how computers won’t do anything you won’t EXPLICITLY let them do)
Then maybe we could put one team’s solution into a simple program to show how a computer would play it.