My favourite is to play Go:
Draw a grid. Player 1 is /, player 2 is \. A cross is an empty square (and you note the prisoner on the side). A cross with two /'s is player 1 again, etc.
Havannah [1] is somewhat go-like and is perfect as a pencil and paper game, as stones are never removed. I've been playing on photocopied hex grids for years.
