Stratego is another simple, deterministic game, but picking a successful strategy is far from simple.

I played it a lot as a kid, and came up with a strategy that beat everyone I played against 100%. I never let on what it was, to their frustration :-)

Risk was good, but I disliked the randomness of it. There wasn't a whole lot of strategy to it, being way too much dependent on the roll of the dice.