No more information is leaked than necessary.

That's very open to cheating. I can pretend to have another piece, and thus get a good read on what your piece is.

Yes, I was assuming there would be a anti-cheating mechanism in the end game as Hodgman described.

In addition, an assumption I made that I perhaps wasn't clear on is that the protocol would only be started once one peer commits to making a move. Thus the gamestate is altered by running it, so one cannot query your peer in a speculative manner for the value of an arbitrary piece.

There is weakness in that protocol compared with the ideal of having a trusted third party resolve the combat. While it (mostly) protects the identity of the winning piece, it leaks the precise identity of the losing piece. This means with each win the winner gains an additional data point, they know how many pieces of a given rank have been eliminated, allowing the winner to slowly build a better statistical model of the pieces that remain than they could with the trusted third party.

I would note that this is at least "fair" in that both players can potentially benefit from it, even though it unfortunately benefits a player who is doing better. However I feel this could be an acceptable trade-off to achieve peer to peer play in the absence of a trusted third party.

If we accept this limitation, I believe I have developed a modified protocol which protects the identity of the spy in the "Game of Generals" linked in the OP, however it allows for the identity of the Sergeant to be revealed in some circumstances.

First, flag combat is "easy" as it always ends the game. If either peer is using a flag, they must reveal that information and the game ending can be determined immediately. Please note that this might not be strictly necessary, it might naturally fall out of the rest of the protocol, but let us treat this as an early special case to simplify.

That case aside, the protocol begins at the first officer rank (i.e. Sergeant), rather than the "lowest" rank. Instead of asking if one can beat the rank, ask if one would lose to this rank. Identical ranks "lose" to one another in this protocol.

In general, if both peers say "I would lose", then it is a draw and both pieces are eliminated. If both players say "I would not lose", test the next highest rank. Otherwise, the combat is resolved and the piece belonging to the peer who said "I would lose" is eliminated.

When all the officer ranks are exhausted without conclusively determining the combat, then both pieces are removed as they must both be spies. This does not leak information, even with a trusted third part when any two pieces are removed together each player knows that their opponent had the same piece.

I believe this handles all the cases where an officer better than a Sergeant and a Spy are involved. However when there is a draw or a loss on the first round, we have ambiguity. We know that one of the peers has a piece that would lose to a Sergeant, but there are two pieces that qualify, a Sergeant and a Private. We also have to handle the case where a Spy, who can beat a Sergeant, loses to a Private.

If both players say "I would lose" on the first round, there are the following combinations:

• Private VS Private

• Sergeant VS Private

• Sergeant VS Sergeant

We can resolve this by getting each player to reveal the identity of their piece. Here is the case that leaks information compared with the previous protocol, where a Sergeant eliminates a Private, the losing player has learned the location of the Sergeant. The other two cases do not leak information for the same reason as the spy case above.

Where one player says "I would not lose" and the other says "I would lose" on the first round, we have the following cases:

• Private VS (Officer > Sergeant)

• Private VS Spy

• Sergeant VS Spy

• Sergeant VS (Officer > Sergeant)

Let the "losing" player reveal the identity of their piece. If it is a Sergeant it must lose either case. If it is a Private, the "winner" must specify whether they have a Spy (i.e. a boolean piece of information, they do not need to reveal the identity of their piece if it is not a spy). Resolve the combat as per the game rules. Note that this isn't leaking information compared with a trusted third party, in any case a Private wins without also being eliminated, we can infer the losing piece must have been a Spy.

This revised protocol still has the property that the exact nature of the losing piece is revealed in all cases. However, we no longer leak the identity of the Spy (until it is killed, and as noted these cases are obvious even with a trusted third party). In the context of the overall game rules, this is much better than revealing the identity of the spy in every combat. There is only a single sergeant, and it is (arguably) the second least interesting/valuable piece. There are two spies, and they are probably the most interesting piece - their potential presence puts one into a real dilemma about whether there is an easily defeated spy rampaging through one's officers or a high ranking piece which can only be defeated with similar strength.

Unless I've made a mistake in my reasoning somewhere?