Recommend
3 
 Thumb up
 Hide
30 Posts
1 , 2  Next »   | 

BoardGameGeek» Forums » Board Game Design » Design Theory

Subject: Two people cannot play a hidden info game long distance. rss

Your Tags: Add tags
Popular Tags: [View All]
guy
Wallis and Futuna
Grand Bois Du Nord
msg tools
Avatar
mbmbmbmbmb
My wife and I were trying to figure out a way to play a card game by mail. We were designing the initial shuffle and deal using sealed envelopes within sealed envelopes and signed seals, etc. (all of which could be simulated with public key encryption techniques in software over the internet).

We realized, while designing the card-dealing protocol, that 2-player, hidden information games are impossible to play with just 2 people if they are not in each others' presence. In order to play such a game long distance, a trusted 3rd party must always be relied on. Of course, in software you can postulate a tamper-proof client to fulfill the roll of the trusted 3rd party. But this is not acceptable since a tamper-proof client cannot be assumed to exist.

Now this result seems obvious, but only in retrospect--I actually went into the card-dealing protocol design with the idea we could do it. The surprise was on me! If you are better at math than me, then you can laugh at me now. Oh, that's why there's chess by mail, but not Roulette by mail! Duh.

So 2 parties cannot play a 2-player, hidden information game long distance. On the internet, only 3 parties can play a 2-player hidden information game.


 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Josh Bodah
United States
Melrose
MA
flag msg tools
badge
Avatar
mbmbmbmbmb
This would be a bit of a stretch but suppose each player keeps their hand and mails the deck, discard, and played cards back and forth. Then it's no different than playing in person with the exception that you can't keep someone from cheating.

The hardest part of playing a game remotely is if you use two sets of components that you need to keep synchronized (e.g. If I drew a 2 of hearts, the only way to prevent you from also drawing that is to remove the 2 of hearts and send you the rest of the cards or have you remove them which would mean you'd know I drew it)
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Josh Bodah
United States
Melrose
MA
flag msg tools
badge
Avatar
mbmbmbmbmb
Actually, I'd imagine many deck builders would fit this fine; your hand draw each turn can be secret as long as all of your purchases are public and all decisions are bounced back to the other player when needed. I could see someone playing Dominion by mail pretty effectively
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
TTDG
United States
Fairfax
Virginia
flag msg tools
designer
Avatar
mbmbmbmbmb
Maybe it depends on what you mean, but I can imagine a whole group of hidden information games of the following form: Player 1 choses 1-4. Player 2 chooses A-D. The combined result is A1-D4 (you sunk my battle ship), yet neither player knows ALL of the information. At the end of the game, they reveal their half. If necessary, steps can be taken to insure that the initial selection remains the final selection, such as encryption, to avoid cheating.

In the case of a whole deck of cards unknown to both players, randomly determine the cards, and then encrypt the stack in layers such that to determine the 1st card you decrypt the 1st card (and the rest of the stack, which is under yet another layer of encryption). You can't get to the 2nd card without going through the 1st card. And, IIRC, there are certain types of decryption that leave a trace so that you can tell if the message was intercepted. OTOH, that seems like a lot of bother to ensure the honesty of "I did not peek".
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Lluluien
United States
Missouri
flag msg tools
Avatar
mbmbmb
This is actually not true at all, it's just that designing a protocol like this adds another layer of difficulty.

There are an entire class of encryption algorithms called "Zero knowledge protocols" that solve exactly the issues you are trying to handle.

In fact, for a semester project for my graduate cryptography class, I wrote an online variant version of Stratego where two players could play and when their pieces fought, the only information that was revealed was who lost the fight. The neither party knew the identity of the other piece in the fight.

Now one aspect of these protocols is that both clients needed to keep a log of the plays, and then when they reveal their respective crypto keys at the end, they replay the logs with the knowledge of both keys to make sure neither party cheated. So you didn't have to have an assurance that the opposing client wasn't tampered with, you only had to trust that YOUR client wasn't tampered with, which is a much easier problem. (Before the internet explodes into an argument about those statements on either side of that assertion, let me point out that the problem of making sure the your client hasn't been tampered with is much more famous and has much wider implications. You don't have to take my word about this either, you can just google for 10 billion articles about the Thompson hack.)

This is a bigger deal and a more powerful statement than most people make it out to be. OP asserted in his original post that you can make a trusted software executor that handles the "trusted third party" portion of this problem. With this type of protocol, you don't even need that.
5 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeremy Lennert
United States
California
flag msg tools
designer
Avatar
mbmbmbmbmb
You believe you've uncovered a new insight, but you aren't saying how you arrived at it or why you believe it's true?

The general case of hidden information is always hard without a referee. Board games that use hidden information often start with a specific trick(s) for doing hidden information and then build the rest of the game around that. It wouldn't be surprising if the best set of tricks is different for long-distance play, which would imply that a game designed for face-to-face play will often not work very well for long-distance play. But that does not, by itself, imply that you couldn't design a 2-player hidden information game specifically for long-distance play.

I'd guess that you were trying to play a game with some kind of precommitment (e.g. I play a card face-down on turn 2; you don't get to see it until turn 4, but you know that I can't have changed it in the meantime) and realized that if I keep the card until turn 4 then I can secretly change it but if you keep the card starting on turn 2 then you can peek.

But if that's the case, you may be interested to know that precommitments are a solved problem in cryptography. (Send a hash of your information in advance; when you send the final version, the recipient can check that the hash from earlier matches your final answer.) So you could definitely play, say, rock-paper-scissors--even if there's no way to declare your moves "simultaneously".


Now, as Josh Bodah points out, drawing from a shared deck is tricky. That's not a problem with hidden information in general, but rather with one specific mechanism that, again, is optimized specifically for face-to-face play. That might not translate well to remote play, but that wouldn't imply that hidden information games are intractable in general.

The best way to solve that is probably to invent a minor variant of the game you want to play where the players draw from separate decks instead of a shared deck. But there might also be some clever way of handling it; it's an interesting problem. I'll give it some thought.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Lluluien
United States
Missouri
flag msg tools
Avatar
mbmbmb
I feel compelled after Antistone's post to say something additional about zero knowledge protocols, because talk of precommitments is actually taking the conversation backwards. (Edit: with apologies to Antistone, I didn't mean that quite the way it came out; more along the lines of "crap, I didn't really say what I needed to before and now I need to clarify because it's not the same thing")

Let me make an even more powerful claim than "The OP is incorrect".


I claim this:

Since playing long-distance in this day and age implies playing using software, you can design mechanics using hidden information for these games that are impossible to design in cardboard without a third-party arbitrator.

So not only is the original statement incorrect, it's actually backwards from the truth.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Lluluien
United States
Missouri
flag msg tools
Avatar
mbmbmb
ThroughTheDeckGlass wrote:
Maybe it depends on what you mean, but I can imagine a whole group of hidden information games of the following form: Player 1 choses 1-4. Player 2 chooses A-D. The combined result is A1-D4 (you sunk my battle ship), yet neither player knows ALL of the information. At the end of the game, they reveal their half. If necessary, steps can be taken to insure that the initial selection remains the final selection, such as encryption, to avoid cheating.

In the case of a whole deck of cards unknown to both players, randomly determine the cards, and then encrypt the stack in layers such that to determine the 1st card you decrypt the 1st card (and the rest of the stack, which is under yet another layer of encryption). You can't get to the 2nd card without going through the 1st card. And, IIRC, there are certain types of decryption that leave a trace so that you can tell if the message was intercepted. OTOH, that seems like a lot of bother to ensure the honesty of "I did not peek".


By way of demonstrative example of what I'm saying, my group also wrote a protocol for playing this game of battleship for the same assignment as the variant Stratego game, except that the defending player didn't even know where the attacking player shot. He only knew if he had been hit (and where the hit landed). He didn't know where misses landed.

We didn't implement this game; only the protocol design made it into the report. The last protocol that made it was one that allowed a group of players to showdown in Poker and the winner was revealed without the hands being revealed - even the winning hand.

Now someone's going to ask for the protocols and the irony will be that these ideas are old enough that this was so long ago that I don't even have a computer that will accept either the hard drive or disk media that I might still have that maybe has those stored on it.

Llu (who thinks maybe crazy run-on sentences like that last one could be his cool calling card, like a corollary to this weird thing Pete does, since Pete already does that and everyone already know's it's Pete's thing)
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
suPUR DUEper
United States
Villa Hills
Kentucky
flag msg tools
Avatar
mbmbmbmbmb
Maybe I am missing something here but wargamers do this all the time utilizing Vassal and/or ACTS. We have common draw decks, hidden cards, hidden units, the works.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Lluluien
United States
Missouri
flag msg tools
Avatar
mbmbmb
TedW wrote:
Maybe I am missing something here but wargamers do this all the time utilizing Vassal and/or ACTS. We have common draw decks, hidden cards, hidden units, the works.


In this case, you're trusting Vassal or ACTS to act as your arbitrator. That's what the OP was talking about when he mentioned that the third party's role can be played by trusted software. It's still a third party in this case, though, in the sense you're having to utilize some form of information mediation.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Was George Orwell an Optimist?
United States
Corvallis
Oregon
flag msg tools
Thelonious Monk - Monk's Dream
badge
Avatar
mbmbmbmbmb
professorguy wrote:
So 2 parties cannot play a 2-player, hidden information game long distance. On the internet, only 3 parties can play a 2-player hidden information game.

As a veteran of many hidden movement games played on the internet, this comes as quite a surprise to me!

Specifically, the BaM Ladder was a very successful project where players around the world participated in games of Bonaparte at Marengo over a period of several years. Most of us used Cyberboard, which provides an excellent vehicle for play of games with hidden info via email.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Was George Orwell an Optimist?
United States
Corvallis
Oregon
flag msg tools
Thelonious Monk - Monk's Dream
badge
Avatar
mbmbmbmbmb
lluluien wrote:
TedW wrote:
Maybe I am missing something here but wargamers do this all the time utilizing Vassal and/or ACTS. We have common draw decks, hidden cards, hidden units, the works.


In this case, you're trusting Vassal or ACTS to act as your arbitrator. That's what the OP was talking about when he mentioned that the third party's role can be played by trusted software. It's still a third party in this case, though, in the sense you're having to utilize some form of information mediation.

But the fact that such software is readily available makes the thread rather pointless, n'est pas?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
suPUR DUEper
United States
Villa Hills
Kentucky
flag msg tools
Avatar
mbmbmbmbmb
lluluien wrote:
TedW wrote:
Maybe I am missing something here but wargamers do this all the time utilizing Vassal and/or ACTS. We have common draw decks, hidden cards, hidden units, the works.


In this case, you're trusting Vassal or ACTS to act as your arbitrator. That's what the OP was talking about when he mentioned that the third party's role can be played by trusted software. It's still a third party in this case, though, in the sense you're having to utilize some form of information mediation.


Thanks for the response!

If "tamper proof" is the standard, isn't a human mediator also subject to tampering?
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Lluluien
United States
Missouri
flag msg tools
Avatar
mbmbmb
TedW wrote:
lluluien wrote:
TedW wrote:
Maybe I am missing something here but wargamers do this all the time utilizing Vassal and/or ACTS. We have common draw decks, hidden cards, hidden units, the works.


In this case, you're trusting Vassal or ACTS to act as your arbitrator. That's what the OP was talking about when he mentioned that the third party's role can be played by trusted software. It's still a third party in this case, though, in the sense you're having to utilize some form of information mediation.


Thanks for the response!

If "tamper proof" is the standard, isn't a human mediator also subject to tampering?


Yes, but typically this person would either be your friend or a community judge of some kind in a tournament. In either case, you're probably okay.

The software is typically trustworthy too in the sense that it's typically requires more knowledge and more trouble to break it undetectably than it's worth.

However, consider how this question changes if you're wanting to do something like play Magic: the Gathering Pro Tour tournaments on such software where the prize pool is so large.

(Edit: You probably just considered how the question changes for the electronic version, but remember to consider how the question for the HUMAN version too - do you trust your judges when that much money is at stake? The answer to that question is why the word "collusion" exists.)
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Lluluien
United States
Missouri
flag msg tools
Avatar
mbmbmb
Sphere wrote:
lluluien wrote:
TedW wrote:
Maybe I am missing something here but wargamers do this all the time utilizing Vassal and/or ACTS. We have common draw decks, hidden cards, hidden units, the works.


In this case, you're trusting Vassal or ACTS to act as your arbitrator. That's what the OP was talking about when he mentioned that the third party's role can be played by trusted software. It's still a third party in this case, though, in the sense you're having to utilize some form of information mediation.

But the fact that such software is readily available makes the thread rather pointless, n'est pas?


Not necessarily. The practical need depends on the context of the question (see my post RE: Magic tournaments above).

However, the OP specifically separated out this point in his post in the first place as saying that he was discounting third party software because it isn't reliably trustworthy in the theoretical sense, regardless of whether or not it is in the practical sense.

That's neither here nor there though, because zero knowledge protocols are trustworthy in both the theoretical sense and the practical sense. Actually, for the discussion of just the trustworthiness part of the electronic translation of cardboard-game-moves and not the boundaries of how hidden information can be exchanged, the precommitment ("non-repudiation" is the technical term) protocols mentioned earlier solves most of this issue.

Perhaps more importantly, the clients can be relied on to double-check each other if they are designed using such protocols. (Edit: to clarify - relied on in the sense that you don't have to spend time writing code to have this extra piece of validation software written into some server that the game developer has to host, see next paragraph)

You might not think this is important, but it's the different between having a trustworthy peer-to-peer game versus having to run a mediation server like the overwhelming majority of video games do to prevent hacking. Brink is an example of an excellent video game that died very quickly because it was hosted peer-to-peer and was ruined by hacking and communication lossiness.

Board games are much more simple than most video games in the sense that their actions are much more discretized. It might be possible to make electronic versions of popular board games that are both trustworthy and able to be hosted peer-to-peer at the same time, whereas that's a pretty impractical problem from a protocol design standpoint for a modern action/fighting/MMORPG/etc video game.


Edit: It's amazing when this stuff is familiar to you how easy it is to leave out an important point. Regarding the peer-to-peer vs arbitration server models, you want the former because it's a hell of a lot cheaper, in case that's not clear.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeremy Lennert
United States
California
flag msg tools
designer
Avatar
mbmbmbmbmb
lluluien wrote:
I feel compelled after Antistone's post to say something additional about zero knowledge protocols, because talk of precommitments is actually taking the conversation backwards.

Well, I could hardly respond to your post given that I was already composing mine when yours appeared.

I have only an abstract knowledge of zero-knowledge protocols. Do you have a suite of zero-knowledge "primitives" that can be easily combined to create applications (analogous to cryptographic primitives), or do you require an expert-designed bespoke solution for each game?

It may be worth noting that reliance on a complex protocol may get you out of trusting your opponent but usually means you now need to trust the protocol designer and software engineer, because most users aren't capable of verifying them personally. There's some value in transparency.



Coincidentally, I am even now in the process of developing a computer version of a board game with hidden information, and it relies on peer-to-peer connections. A zero-knowledge protocol to prevent hackers from peeking would certainly be interesting academically!

However, even if I had one, I probably wouldn't use it in practice. My current plan is to maintain the full game state on every client so that the game can continue if someone gets disconnected (with an AI taking over for the missing player), and of course a zero-knowledge approach would make that impossible. I think being able to finish the game after a network outage or ragequit is probably more valuable than making cheating more difficult in my particular case. (Obviously, if I was running tournaments with huge prizes, things might be different.)

I suppose if I were seriously hardcore I could probably invent some sort of system where each player shares an encrypted version of their secret information that can only be decrypted with the cooperation of all (or a majority) of the other players, so that everyone would need to agree you had disconnected before anyone could look at your information...hm...
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeremy Lennert
United States
California
flag msg tools
designer
Avatar
mbmbmbmbmb
lluluien wrote:
Edit: It's amazing when this stuff is familiar to you how easy it is to leave out an important point. Regarding the peer-to-peer vs arbitration server models, you want the former because it's a hell of a lot cheaper, in case that's not clear.

That probably depends a great deal on the bandwidth and CPU load of your particular game. Board games tend to be pretty light in those areas, which makes hosting a server for them cheaper than for many digital games.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Lluluien
United States
Missouri
flag msg tools
Avatar
mbmbmb
Antistone wrote:
lluluien wrote:
Edit: It's amazing when this stuff is familiar to you how easy it is to leave out an important point. Regarding the peer-to-peer vs arbitration server models, you want the former because it's a hell of a lot cheaper, in case that's not clear.

That probably depends a great deal on the bandwidth and CPU load of your particular game. Board games tend to be pretty light in those areas, which makes hosting a server for them cheaper than for many digital games.


This is a good point; the fact that they're "easier" to design the right protocol for stands a very good chance of making this "easier" enough to both write and run that arbitration host that it could render that entire point of mine moot. Guess it would depend on easy it was for someone to design the right protocols.


Edit: On the other hand, having the peer-to-peer version might let you do something with a near-field communication network that you wouldn't otherwise be able to do (because of not having access to the internet for some reason), which then at least suggests an example of why this question might have practical merit in addition to theoretical merit. We only need a single plausible practical example to demonstrate by counterexample to Sphere that it's perhaps the case that the thread is not pointless.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Lluluien
United States
Missouri
flag msg tools
Avatar
mbmbmb
Antistone wrote:
I have only an abstract knowledge of zero-knowledge protocols. Do you have a suite of zero-knowledge "primitives" that can be easily combined to create applications (analogous to cryptographic primitives), or do you require an expert-designed bespoke solution for each game?

It may be worth noting that reliance on a complex protocol may get you out of trusting your opponent but usually means you now need to trust the protocol designer and software engineer, because most users aren't capable of verifying them personally. There's some value in transparency.


You are correct, and that trusting the designer/developer problem touches on the Thompson hack thing I mentioned. Fortunately, we found during initial brainstorming phases of the project that I mentioned that just about every game action we considered had a relatively easy translation to some well-established existing protocol, which is why our report included protocols for three games even though we only had to implement one to satisfy the requirements of the project. I don't know that I would call them primitives in the same sense you might use that word for something like hashing just because I don't know that any of the zero-knowledge ideas as so widely deployed to deserve that name. However, I think you could probably write a fairly "simple" (in the sense that you and I would easily understand them) justifications for domain translations for problems in the board games action space to actual encryption techniques for problems that have been written about in peer-reviewed science journals, and I think that addresses most of this concern.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Lluluien
United States
Missouri
flag msg tools
Avatar
mbmbmb
Antistone wrote:
I suppose if I were seriously hardcore I could probably invent some sort of system where each player shares an encrypted version of their secret information that can only be decrypted with the cooperation of all (or a majority) of the other players, so that everyone would need to agree you had disconnected before anyone could look at your information...hm...


Yep, this is exactly the kind of thing zero knowledge protocols were designed for! Your concept is more-or-less how several of them work. One of the most interesting ones that shares similarities with this idea is a protocol for the bank creating electronic "cash", where the reason it's called "cash" is because it can be spent anonymously.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Dallas Tucker
Indonesia
Jakarta
flag msg tools
designer
(This space intentionally left blank.)
badge
What is the good life?
Avatar
mbmbmbmbmb
A potential way to do things if both players are drawing from the same deck (poker, RftG, etc.) would be to order the cards, then do the kind of shuffle where you deal one card to each of X piles. Then you could stack the piles in a particular order and repeat as many times as you feel is necessary for both players to not have counted where the cards are. The rest after that should be fairly simple, but you could also number the cards in hand if necessary. It would be tedious in a game that needed more than one shuffle during the game though.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeremy Lennert
United States
California
flag msg tools
designer
Avatar
mbmbmbmbmb
lluluien wrote:
Would it necessarily make that impossible? If one client got chosen to manage the AI, that client managed the AIs communication with the rest of the players, and the client of the disconnected player maintained its game-specific crypto key until it reconnected to the game, I don't see why this would prevent you from being able to then drop the AI and continue on as normal.

Reconnecting isn't the issue; it's everything that happens while a client is offline.

Whichever client is running the AI in the player's absence requires access to that player's secret info. (In this specific game, the secret info is frequently required to make good tactical decisions, and sometimes is required even to guarantee your decisions are legal.)

Also--you will not be surprised to learn--the rules of the game are such that, at some point, every player's hidden information affects how various actions resolve. Those actions cannot be resolved unless some client (that is still actively participating in the game) actually has the information necessary to resolve them, in some form.

I guess I shouldn't absolutely swear it's impossible. If homomorphic encryption can exist, then maybe there's some really clever way of handling this that I'm just not smart enough to imagine. But the problem seems pretty difficult; you're basically demanding that the computer running an algorithm can produce the correct outputs without ever having enough information to construct the required inputs.

(If you're interested in discussing this specific example in depth, send me a geekmail and I'll be happy to get into details.)
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Lluluien
United States
Missouri
flag msg tools
Avatar
mbmbmb
Antistone wrote:
lluluien wrote:
Would it necessarily make that impossible? If one client got chosen to manage the AI, that client managed the AIs communication with the rest of the players, and the client of the disconnected player maintained its game-specific crypto key until it reconnected to the game, I don't see why this would prevent you from being able to then drop the AI and continue on as normal.

Reconnecting isn't the issue; it's everything that happens while a client is offline.

Whichever client is running the AI in the player's absence requires access to that player's secret info. (In this specific game, the secret info is frequently required to make good tactical decisions, and sometimes is required even to guarantee your decisions are legal.)

Also--you will not be surprised to learn--the rules of the game are such that, at some point, every player's hidden information affects how various actions resolve. Those actions cannot be resolved unless some client (that is still actively participating in the game) actually has the information necessary to resolve them, in some form.

I guess I shouldn't absolutely swear it's impossible. If homomorphic encryption can exist, then maybe there's some really clever way of handling this that I'm just not smart enough to imagine. But the problem seems pretty difficult; you're basically demanding that the computer running an algorithm can produce the correct outputs without ever having enough information to construct the required inputs.

(If you're interested in discussing this specific example in depth, send me a geekmail and I'll be happy to get into details.)


Yeah you're 100% right about this, and in the process of me editing my reply to concede that I hadn't addressed this point, I actually had my first potentially novel idea in the whole conversation that wasn't just a resynthesis of something that someone else did (including the games in the project I mention earlier - those might've been novel applications, but they weren't novel algorithms). I wasn't sure I wanted to share that idea just yet so I deleted the rest of it because the argument was incomplete without it, precisely as you're pointing out here! You were too fast for me

+2 thumbs if I could.

I wonder if there's a correlation to how much someone edits their posts to how much code they write. I get myself in trouble with this all the time because I write here the same way I write code - incrementally. The new kids call this Agile now, but that's just because they're hipsters.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jeremy Lennert
United States
California
flag msg tools
designer
Avatar
mbmbmbmbmb
Whoshim wrote:
do the kind of shuffle where you deal one card to each of X piles. Then you could stack the piles in a particular order and repeat as many times as you feel is necessary for both players to not have counted where the cards are.

This explanation is hard for me to follow. I think what you mean is:

1. Each player gets an actual, physical deck of cards (identical for each player)
2. Players each put their deck in some agreed-upon order, so they all have the same initial state
3. Players each "shuffle" their deck according to some deterministic algorithm, so they are guaranteed to get the same results
4. Players then draw from that physical deck of cards whenever necessary during the game (and set aside the appropriate number of cards, without looking at them, when another player draws)

This solves the synchronization issue, but not the trust issue: every player has the power to look at all of the cards whenever they want, so none of the information is actually secret. Every player has the power to cheat undetectably at any time.

Any algorithm that solves the trust issue must involve every participant generating some private numbers that indirectly affect the shuffle but which are not explicitly shared with the other players. (Like how a private cryptographic key influences your public key, but you never share the private key itself.) If all the information that determines the deck ordering is shared, then any player can determine the location of all cards at any time.
4 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Lluluien
United States
Missouri
flag msg tools
Avatar
mbmbmb
Antistone wrote:
Whoshim wrote:
do the kind of shuffle where you deal one card to each of X piles. Then you could stack the piles in a particular order and repeat as many times as you feel is necessary for both players to not have counted where the cards are.

This explanation is hard for me to follow. I think what you mean is:

1. Each player gets an actual, physical deck of cards (identical for each player)
2. Players each put their deck in some agreed-upon order, so they all have the same initial state
3. Players each "shuffle" their deck according to some deterministic algorithm, so they are guaranteed to get the same results
4. Players then draw from that physical deck of cards whenever necessary during the game (and set aside the appropriate number of cards, without looking at them, when another player draws)

This solves the synchronization issue, but not the trust issue: every player has the power to look at all of the cards whenever they want, so none of the information is actually secret. Every player has the power to cheat undetectably at any time.

Any algorithm that solves the trust issue must involve every participant generating some private numbers that indirectly affect the shuffle but which are not explicitly shared with the other players. (Like how a private cryptographic key influences your public key, but you never share the private key itself.) If all the information that determines the deck ordering is shared, then any player can determine the location of all cards at any time.


+2 thumbs for this one too!
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
1 , 2  Next »   | 
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.