When I was in university at the end of 80s / beginning of 90s, I played a pen and paper game named morpion solitaire (see rules). After a few search I found out that this game has been studied by mathematicians (a Ph.D. thesis, another good paper), and is still being played by a lot of people who are devoting their time to develop algorithm to resolve it.
There is a nice Java applet available here which keep high scores, the official record is 170.
Do you know this game?