Simple, but lots of strategy involved. Stratego. They have a 2-player version and a 4-player version as far as I know, but the 2 player one is the one I've played the most.

Few people can beat me (Or could, since I haven't played in AGES!!!)