This just the game of Dots and Boxes. There is a huge literature on this game. In particular, Berklekamp's book referenced in the above link shows how difficult this game is.
Richard Stanley
- 50.8k
- 14
- 155
- 279