mudslinger

...

if this is fine then Yao's approach seems doable since you probably don't have that many pieces.

...

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. 

...

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

...

 

I thought of these, it is a yes on all three points. It is the nature of the game that the strength of a piece is partially revealed after a challenge (e.g. opponent's piece won, it's stronger than mine). 

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.

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.

I have more or less finished the game, it can be played here: http://pinoyai.com/pdai.php . Java is needed.
I also put the rules here: http://pinoyai.com/pdrules.php

Everything on the website is still beta, the game doesn't even have drag-and-drop. I was too lazy to write it

I think I understand the tree part now. The expanding part is not directly dependent on the number of simulations, for example, I can do 1000 simulations, then generate a branch. I can generate another 1000 simulations, then generate another branch. I think I can't apply this to my game since the game has a max 13 moves at the start and this drops quickly. I'd run out of moves for the tree. Your pseudocode is what I had in mind.

I'm not familiar with tichu.

here's my UCB1 code, it's a bit rough, I apologize.
http://pastebin.com/rddWUSzF