Never heard of the perfect general, I will have to check it out. The moment you said War games I thought of the movie from 1983 lol good movie.
Other turn based strategy games?

Japanese Chess is extremely complex, with four additional pieces, I believe.
Also, every time you take your opponent's piece, you can use your turn to place it back on the board... on your side.
Once pieces get on or past the sixth rank, they can be promoted, which is generally a good idea, as it gives them better moves.
Games have been known to take more than a week to finish, (over-the-table games.)
It is pretty fun, though, especially if neither of you really know what you are doing.

yeah like I said earlier i like Shogi a lot, never heard of Gothic Chess though so I will check that one out.
Shogi is a good game, so is Xiangqi though I found it kind of hard to get into for some reason.I also tried Zatikon, the game you mentioned, and there are so many pieces which makes it insanely complex. It is going to take me awhile to get good at that game.
OK, not quite perfectly free, and there is just a touch of randomness thrown in for good measure... but you might try "Laser Squad Nemesis"... they have a free version so you can get the hang of the basics... very cool game.

Anything named Laser Squad Nemesis has to be cool lol can't really go wrong with a name like that, ill check it out. If its good im willing to buy it just dont want to spend obscene amounts of money on games! lol
You should definately try Stratego, even if you haven't played it in awhile, you should go back to it!
Civ 4.
I play Sid Meier's Civilization 4 as well-I love that game! I've played Stratego, but have never become very good at it as I have not played regularly.
Anyone tried Battle for Wesnoth? It's a FREE game, very addicting, and actually requires strategy (available at www.wesnoth.org).
It's just about tied with Civilization 4 (which is not free unless you get it as a gift like I did) for being my favorite non-chess game. It contains the option of going 1-on-1, 2-on-2, 2-on-1, 3-on-3, 2-on-2-on-2, 3-on-3-on-3, or free-for-all with up to 9 players!
When I get wesnoth on my Internet computer, perhaps I could play you all on the wesnoth multiplayer server!
I think I have heard of Battle for Wesnoth, I havta give it a try though. Civ 4 Is fun. You should try Risk.

Age of Wonders, AOW2, and Fantasy Wars are fun turn based strategy games for pc.
You might also enjoy Capitalism 2, a unique RTS game.
The Football Manager series is also worth taking a look at.
My favorite strategy game is Go. It gives you a level of strategic freedom far higher than any other game I know of. Go to KGS Go server and have a look.

Civ I was my first love (way before chess), I put countless hours into the game & then got into Civ II (mostly multiplayer since the AI sucked). I haven't played either of them for years though.
Fun fact : many of the members of my team (almost all of the first 20 people) came from the chess subforum of a forum dedicated to the Civilization series.

Also I play Xploreres (Settlers of Catan) @ asobrain.com
Almost always the Cities & Knights version rather than regular Settlers.
The co-founded of chess.com is also a big fan, I have played him there a few times.
I used to play Age of Empires and Majesty, not super turn based, but still decent strategy games. But I guess there are an endless amount of non turn based strategy games.

I am going to have to check Xploreres out. Currently I have been playing a lot of Stratego and Shogi. I did like the starcraft suggestion though lol made me laugh :P

Ah Stratego, I hated that game, mostly cause my older brother used to beat me mercilessly at it again & again (I don't think I every won). He'd always manage to take a few high ranking pieces & then "clog off the exits" & my defeat was inevitable.
Xploreres (Catan) is fun. Enough luck to give it appeal to girlfriends & non-competitive friends but enough skill where the best player will win at least 50% of the time (in a 3-player game).

Never won!? lol That game is fun though I used to play it a lot with my friends, I def like chess a lot more, but I guess nothing really beats it.
war games
the perfect general comes to mind
simple to learn, tough to get great at