How would I make a p2p program that doesn't require a third party and doesn't reveal the game pieces?

Someone needs to make a decision which piece is stronger.
That someone needs to know the strength of both pieces.
You only have the two players to choose from to decide "someone."
Ergo, at least one of the players needs to know the strength of both pieces.

both players exchange encrypted piece positions with each other at game start. at game end, the decryption keys are exchanged to determine if they had been telling the truth.

But it is possible to compare two values from different parties without revealing those two values.

http://www.proproco.co.uk/million.html

I believe I currently have a solution in my head.

EDIT: I plan to use the millionaire solution (link above) to compare pieces. To guard against players cheating the system by always sending a high piece, both players exchange encrypted piece positions with each other at game start. at game end, the decryption keys are exchanged to determine if they had been telling the truth.

It's rough, but it looks doable.

Yes, but the point hplus0603 was making is that there is always some unevitable amount of information leakage about the other player's piece simply by virtue of knowing the result of the comparison and the value of your own piece. In some cases, or if you don't have many pieces, this may often be enough to deduce the other player's piece. For example, using cards, if my card is a king and you still win, then I know you have an ace, no matter how much cryptography and obfuscation you throw at the problem. A fix would be to increase the number of different pieces, or perform the comparison less often. Another method is to change the number of pieces dynamically, but this doesn't make for a very enjoyable game since the comparison is no longer consistent with what people would expect. If this caveat is unacceptable to you, your problem has no solution.

Otherwise, if this is fine (and hopefully it is) then Yao's approach seems doable since you probably don't have that many pieces. Now as for cheating, your solution works if the initial state + the movement information received by each player is enough to derive the game's state at any turn. You could also send the encrypted game state every turn with no information leakage for faster failure response (1 turn) but perhaps it is not worth it. Make sure to implement a commitment scheme as well so that a player can't "change his mind" on his game state once the keys are revealed (by revealing a fake key which decrypts to what he wants - not likely to succeed in practice but it can be done depending on your encryption scheme and the complexity of the game state).

Yes, but the point hplus0603 was making is that there is always some unevitable amount of information leakage about the other player's piece simply by virtue of knowing the result of the comparison and the value of your own piece.

I believe that is by design in such games. This partial information is what the player uses to formulate their plan.

Just a thought, if you could impose a strict weak ordering on the ranks, I believe you can have a simple protocol to resolve the combat. Conceptually, each peer starts at the lowest value piece and asks if the other peer can beat it using their actual piece. If not, the peer asks if the next highest rank can beat it. And so on, stopping as soon as one player reveals they can beat that particular value. No more information is leaked than necessary.

For example, player A has a middling piece (e.g. "Lt. Colonel") but player B has a highly ranked piece (e.g. "Major General"). The protocol would be like so:

A -> B: Can you beat a flag: yes
B -> A: Can you beat a flag: yes
 
 
A -> B: Can you beat a spy: yes
B -> A: Can you beat a spy: yes
 
 
A -> B: Can you beat a private: yes
B -> A: Can you beat a private: yes
 
 
A -> B: Can you beat a sergeant: yes
B -> A: Can you beat a sergeant: yes
 
// ...
 
 
A -> B: Can you beat a major: yes
B -> A: Can you beat a major: yes
 
 
A -> B: Can you beat a Lt. Colonel: no
B -> A: Can you beat a Lt. Colonel: yes
 
 
 
 
 

Thus both players conclude that player B wins, without B revealing the exact value of the winning piece.

Unfortunately, the game you linked to does not appear to have this property, in particular due to the "Spy". Forcing the game logic to fit a strict weak ordering would probably also reduce some of the "strategy", by eliminating such interesting ranks; potentially making the game considerably less fun.

Maybe there is a clever way to handle such a case, but I cannot see it. The protocol would have be modified such that if a spy would lose, the spying peer can "reveal" the spy to allow the protocol to continue. Such an implementation would reduce the information being leaked to "just" spies (though they are quite a notable piece).

For example, player A has a their officer level piece (e.g. "Sergeant") and player B has a spy. The protocol would be like so:

A -> B: Can you beat a flag: yes
B -> A: Can you beat a flag: yes
 
A -> B: Can you beat a spy: yes
B -> A: Can you beat a spy: no, but I am a spy
 
A -> B: Can you beat a private: yes
B -> A: Can you beat a private: no, but I am a spy
 
A -> B: Can you beat a sergeant: no
B -> A: Can you beat a sergeant: yes

So the sergeant would be removed.

Maybe some of the uncertainty could be reclaimed by adding more special pieces to the mix, though the protocol itself might break down entirely too. Just thinking out loud, I may have made a mistake in my reasoning.

No more information is leaked than necessary.