Have you played Hex? You could use hexagon paper, although it might be more interesting to play this with people as pieces; each team tries to make a link across the board by joining hands!  You might need to reduce the size of the board unless you have a lot of people...

The game of Hex is described in more detail in Martin Gardner's book 'Hexaflexagons and other Mathematical Diversions', including an analysis of the strategy and some nice puzzles to solve in a similar way to chess puzzles, where a situation is set up and the reader must work out where to go next to win the game. Can you think of any puzzles like this?