Another game that comes to mind is Nim. It has a lot of interesting variations, and I particularly enjoy the subtraction game.
In the subtraction game, you start at
N and two players take turns subtracting
3 from the total. The goal is to force the other player to remove the last number.
For example, you could play against the whole class. Let the students pick a starting number (let's say
11). You take away
2, so the total is
9. The students take away
3, so the total is
6. You take away
1, so the total is
5. Students take away
1, so the total is
4. You take away
3 so the total is
1. The students lose! Play a few rounds, letting the students choose the starting number each time.
There is a trick that makes this game very easy, but it's hard to spot if you've never seen it before. Students will realize that they can't win if it's their turn and they have
5, because no matter what they pick you'll be able to leave them with
1 in your next turn. Can they extrapolate and realize that they can't win if they have
9, because you can always leave them with
5? What number allows you to force them to
9? (Hint: the trick involves modulo.)
I like this game so much because you can use it to talk about basic AI topics. For example, you could start by creating a program that plays against a human player by just choosing randomly.
Or you could take the modulo trick and create a program that plays a perfect game each time. Or you could add variation by adding some randomness to the computer's choices instead of always choosing the correct answer.
A more advanced example is a program that solves this using weighted averages that it adjusts after every game (so it "learns" from experience and thinks about the game in the same way humans do: it can "know" that
5 is bad without "understanding" the underlying trick).
You could then make this AI program face off against the perfect computer player. The weighted average computer will "learn" pretty fast. Compare this to what happens if you make this AI program face off against the randomized computer player. The weighted average program will have a much harder time against the randomized player!
Anyway, Nim is a simple game that you can easily play against students, gives them a fun "ah-ha!" moment, and leads pretty naturally to more advanced topics.