Minimize

Minimize is a game that seems to yield some fierce tactics despite being extremely simple. You could even play with Xs and Os.

You almost always want to play your opponent's color, trying to build small "territories" that you can create tiny groups in. Beginners should definitely start out on the base 5 grid and slowly work their way up to larger boards.

The rules are explained here: http://www.scribd.com/doc/260002289/Minimize

It should be mentioned that it seems to work on square grids as well, and some people even prefer it that way.