MaridAudran: To that end I'd say the royal game, Chess, comes pretty close. After a millennium it still has yet to be solved and is still the standard-bearer of the intellectual boxing match. But I assume the OP means computer/video games.
HomerSimpson: You and I share an affinity for chess, Marid. And, in a broader context I would agree that chess comes as close to pefection (imo) as any game not so much for its complexity, but for the fact that it is an exercise in pure objectivity. No dice rolls, no hidden cards/pieces, same starting resources, etc.
But, yes, the question was directed more narrowly towards the computer/video game segment. And, frankly, I have yet to find a chess video game that I've stuck with for long. Chessmaster 9000 was the one I played the most. But even this game was average at best, imo.
JudasIscariot: Another damn near perfect game is The Warriors. Yes, it's one of those rare games based on a movie that is actually fun as hell to play. There's no guns, no awesome buttons, no press X to not die, there's just you and your gang. If you're looking for game that has fun hand-to-hand combat, then look no further than The Warriors. It's got the classic Rockstar attention to detail, some of the original actors from the movie reprise their roles, it's challenging as hell, and it controls beautifully.
Fun fact: the game mostly takes place before the events in the movie.
HomerSimpson: I had no idea that there was a video game based on The Warriors. I love that movie! I demand that this game be put on the GOG wishlist post haste! :-)