Dots & Boxes
A classic pencil-and-paper game

Dots and Boxes is a pencil-and-paper game for two players. Starting with an empty grid of dots, two players take turns adding a single horizontal or vertical line between two unjoined adjacent dots. The player who completes the fourth side of a 1×1 box earns one point and takes another turn. (A point is typically recorded by placing a mark that identifies the player in the box, such as an initial). The game ends when no more lines can be placed. The winner is the player with the most points. The board may be of any size. When short on time, a 2×2 board (a square of 9 dots) is good for beginners. A 5×5 is good for experts. (wikipedia)

Ideal when traveling, waiting in a queue or simply when you need to pass some time, the dots and boxes game is easy to put together and play with just paper and pen. And, if you're looking to keep playing without a partner, you can even go online and practice with a computer.