1) Introduce a neutral third party, not under control of the two players. Typically, this is why online games use game servers hosted by the game operator. For a strategy game, it's quite likely you can have thousands of games running at the same time on a single server.
2) Relax the design, such that one of the players' computers (or both) knows all the game pieces, but don't display it to the user. A player using a memory scanner can find out all the pieces, but a casual player will still have a good game.
This defeats the point of my question. I don't think it's entirely impossible. Yao's millionaire problem comes pretty close.
This isn't really for a game, it's more of a thought experiment.
EDIT: I believe the problem is Secure Multi-party Computation, I just don't know how to implement it exactly yet.