Wednesday, July 16, 2008

Games for Programmers: Black Vienna

The next in an irregular series of board game recommendations for programmers. Of course, you don't have to be a programmer to enjoy these games, but if you are a programmer, then I think there's a pretty good chance that you'll like them.

O frabjous day!

My favorite deduction game, Black Vienna, has long been out of print, but now you can give it a try online, thanks to the efforts of Greg Aleknevicus. Go check out Black Vienna Online. It's free and easy to use. The user interface isn't going to win any awards, but it gets the job done. I'm thrilled that this game can now reach a wider audience.

Most deduction games are for two players, but Black Vienna handles three to six players. Your goal is to figure out the members of the infamous “Black Vienna” gang. There are 27 suspect cards, labeled A-Z and Ö. At the beginning of the game, three of these cards are chosen randomly and set aside. Those are the members of the gang.

The remaining 24 suspect cards are dealt out evenly to the players. (With 5 players, one of the players gets only 4 cards.) These are the cards of suspects for whom you can provide alibis.

On your turn you conduct an investigation. There is a pool of available investigation cards, each showing three suspects. You choose one of the available investigation cards and place it in front of another player. That player marks the card with plastic chips, according to how many of the suspects are in her hand. For example, if I have the cards BGMTXY and somebody plays the BQT card on me, I would mark it with two chips (for the B and the T). Other players would then know that I had two of the three suspects, but not necessarily which ones.

The turn then passes to the player who was just investigated.

One nice thing about Black Vienna as a game is that every player is involved on every turn. Even if you are not actively part of the investigation, you still need to update your information with the results of the investigation, and follow any chains of deductions to their conclusions.

Example Deductions

Some deductions are obvious. For example, if I played two chips on the BQT card, and you have the Q card in your hand, then you know that I have the B and the T. Other deductions are less obvious. Here's an actual example from a recent game. Call the other players Caitlin, Monica, Drew, and Dom.

Monica played one chip on GPX, but I had the X, so I knew that she had either G or P (but not both). Similarly, she also played one chip on DHR, but I knew Dom had the R, so Monica had either D or H. Finally, she played two chips on LNV.

Drew played one chip on DVY and zero chips on FÖY, so he had either D or V. Between Drew and Monica, they had at least 4 of the 5 cards DHLNV and at least 5 of the 7 cards DGHLNPV (possibly more if Drew had any of GHLNP).

Meanwhile, I knew all but two of Caitlin's cards. The only possibilities for those last two cards were DGHLNPV. Monica and Drew together had at least 5 of those 7 cards, so Monica, Drew, and Caitlin together must have all 7.

This tells me that none of these 7 cards are in the gang, and none of these 7 cards are in Dom's hand. It also tells me that Drew does not have any of GHLNP.

Finally, I can be more specific about Caitlin's cards. One of her two cards is G or P, and the other is one of DHLNV.

Online Play

The online implementation is asynchronous. You do not need to be logged in at the same time as other players. Instead, the system emails you whenever a turn is taken with the results of the investigation. When it is your turn, you can log on and take your turn at your leisure. This means that a 45-minute face-to-face game can take days or even weeks when played online, but it also means that you can play the game with odd minutes here and there, instead of having to carve out a solid chunk of time. An additional benefit is that it is easy to play with friends in different time zones. For example, I frequently play with friends on the other side of the country.

However, the greatest benefit of the online implementation is that it does away with the greatest weakness of face-to-face play—player errors. Not errors in deductions, which would be your own fault and would only affect you, but errors in answering investigations. If a player carelessly puts out, say, one chip when he should have put out two chips, it ruins the game for everyone. Even if the player notices the error a few turns later and tries to correct it, it's far too late. By then, the other players have already updated their notes with deductions made from the faulty answer, and typically have no way of backing out of those deductions.

If you want to give Black Vienna a try, see the detailed rules of the game and the instructions for the online interface.

Addendum: I've played in several three-player games recently. It's ok with that number, but I think it's significantly better with four or five players. (I haven't tried six yet.) With three players, the deductions are less interesting, and there is a greater chance for one player to get lucky.

20 comments:

pengrate said...

You know, this is just Clue without the board and dice.

Chris Okasaki said...

pengrate: There are certainly similarities between Black Vienna and Clue, but Black Vienna is roughly an order of magnitude harder (27 choose 3 = 2925 possible solutions vs 9*6*6 = 324 possible solutions). If you want to think of it as "Clue for Grown-Ups", go ahead.

Joe Fredette said...

It strikes me that this is a game well suited for computers. Really- if you have a perfect memory, then the game boils down to taking the different plays on any given set of cards and doing so set-theoretic munges on them.

I mean- assuming you _have_ to alibi every card you can, hmm...

I'll have to hack up a haskell implementation to mess around with.

Chris Okasaki said...

Joe: Yes, it should be pretty easy to hack up a Black Vienna solver, although it probably won't work the same way that human solvers do. Just like it's easy to hack up a sudoku solver. I know some people for whom this ruins the game -- the fact that a good computer solution exists makes the game uninteresting to them. But, hey, I like to do sudoku by hand too!

One part of Black Vienna that might be harder to capture by computer is the inferences that human players draw from what investigations another player chooses to play. "Hmm, if he had card X, then I don't think he would have played that investigation, so I'm going to guess that he doesn't have X."

Joe Fredette said...

@chris

That strikes me as a fairly straightforward logic programming problem, actually. I was considering doing it via set operations in a functional way, but thats really irrelevant.

What I meant to say, really, is that there is a fast solution, unlike sudoku which is NP-hard, IIRC (It's the set covering problem). This game strikes me as being a fair bit easier, in that, If there are P players and K cards, then I start by knowing at least floor(K/P) cards, I learn t*P basic inference rules (where t is the number of cards in the trick, three in the classic game), then I should be able to infer knowledge about all the cards in the players hands in fairly short order, just stringing together whatever inferences at each stage till I cover the set. Unlike in sudoku, I don't have to determine the inferences on my own- that is, I get for free the set of inferences on each round, O(1) time. as opposed to sudoku, where the really hard problem is generating a new inference rule/constraint.

I should think that there is some formula one could derive that would give you the average time-to-win based on the number of cards removed from the deck in the begining, the number of remaining cards, the number of players, and the number of cards per trick.

I'm intrigued, certainly. I'll have to think about it some more...

Chris Okasaki said...

"I should think that there is some formula one could derive that would give you the average time-to-win based on..."

Yes, I think that would be pretty straightforward if you could choose the investigations freely (as you do in, say, Mastermind).

One complication here is that the investigations are quite constrained. On your turn, you typically have three or four investigation cards to choose between (sometimes a few more), and you are limited to asking about whatever combinations are printed on those cards.

For example, on your turn you might have the BCY, BQT and JMO cards available. If you have the BJM cards in your hand and you already know where the T and Y are, then these queries are somewhat suboptimal.

Another complication arises from the competitive nature of the game. You don't always want to choose the investigation that would give you the most information, because it might also give a lot of information to your opponents. So you sometimes choose a lesser query even though it gives you less total information because it gives you a greater advantage. Or sometimes you choose a query to remove it so that it cannot be played on you.

Jim Freer said...

I have an ethics question about playing a game like this on-line. I rarely play games. Programming for me is like playing a game and I just don't want to waste the little left of my mental energy on games. On the other hand, my son and his girlfriend are serious gamers. They even travel around the country to play games. Recently, out of the blue they invited me to play Black Vienna on-line. I never heard of it but they told me it was like Clue. I was told they usually use a spreadsheet to take notes.

Almost immediately I could see a good portion of the work in playing the game can be solved by a simple program. Probably even simpler for me because an awful lot of the programming applications I had in the 60's and 70's were solved in a similar way. These solutions are etched in my brain. So much that I was able to write the code and use it to win the one only game I've ever played.

I can even predetermine what the answers will yield when I ask my next question. There are still some other things that I haven't done which could aid in the decision making of the game.

Did I cheat? I don't have Excel anymore but I'm sure I could easily build the program with Excel. (I wrote it with ActionScript and build a Flash executable.) Or is this game missing an element or two to make it a real game? Of course, I have only played one game. Maybe there's more strategy in it than I'm seeing, but I warn you if you play against me, I'll just keep adding more logic to my program. :)

Sample output:
http://elegantfloraldesigns.us/blogstuff/BvGameExample.jpg

Chris Okasaki said...

jim: I personally would have no problem playing against a human using a computer assistant, or even against a computer using a human typist. (It might be awfully boring for the typist though.)

I suppose others might, however, so the polite thing to do would probably be to make sure your opponents are aware that you will be using a computer program.

Weeble said...

I'm curious about how the 36 investigation cards were chosen. Is there some neat, symmetric pattern to which letters appear on cards with each other? Is it important? Would the game work with different selections of cards?

Chris Okasaki said...

Weeble: I believe that the letters are evenly distributed on the cards (4 times each) and that no pair of letters appears twice. Beyond that, I don't see any obvious pattern.

It would matter if letters were not evenly distributed, because then players holding cards that appear on fewer investigations would have an advantage.

Weeble said...

Sorry if this is getting a bit boring, but I suppose I'm just eager to dismantle the game to understand the thinking behind it. I have come up with a way to assign letters to the 36 cards that I think is as symmetric as possible. I don't yet know if this is the method used to create the cards.

Assign one letter to each cell in a 3x3x3 cube. Now make an investigation card for each of the nine rows running left to right, each of the nine columns running top to bottom, and each of the nine rows running back to front. Finally, for the last nine cards, you need to take diagonal slices, wrapping around at the edges. E.g., if these are the layers of your cube:

ABC
DEF
GHI

JKL
MNO
PQR

STU
VWX
YZÖ

Then your diagonal slices would be ANÖ, BOY, CMZ, DQU, etc.

You can see that this gives you the properties that every letter is represented equally, and no two cards share more than one letter. What bothered me, though, is that while it's obvious that after randomising the letters, the row and column cards are indistinguishable, the diagonal slice ones feel like a special case. However, it's possible to construct another cube that (I believe) produces the same cards:

AÖN
DUQ
GXK

JIW
MCZ
PFT

SRE
VLH
YOB

This time we've swapped the diagonal slices with the left-to-right slices. I'm afraid I'm not really sure what the right terms are to describe this, but I think this demonstrates that the pattern is nicely symmetric.

I guess I should now try to figure out if there's some cube of letters that produces the cards in the game using this method. Then again, perhaps I should devote my effort to actually playing the game. ;)

Chris Okasaki said...

Weeble: That seems like a reasonable way to make the investigation cards, but I don't think the actual investigation cards could have been made that way.

Three of the cards are ACL, AGM, and BLM. I don't think in your cube you can get such a cycle of length 3 (A-L, A-M, -LM).

Chris Okasaki said...

I've played several 3-player games lately. It works ok with that number, but I think it's much better with 4 or 5. So, if you're thinking of giving it a try, I recommend 4 or 5 players for your first game. (The game also supports 6, but I've never had an opportunity to play it with that many, so I don't know whether to recommend it or not.)

Jim Freer said...

I commented earlier about building a program to help solve a game. I have only played 1 game and I may not have solved as much a I was hoping. However I'm not sure. You had mentioned how the game seems to play better when more than 3 play. That got me to wondering if I could use my program to stand in as a player or players when you can't find any challengers. So while trying to figure out how the 36 Investigation cards get distributed (I still don't know) I came across a Black Vienna puzzle at:

http://www.thegamesjournal.com/puzzles/BlackVienna1.shtml

I thought I would use my program to solve the problem but my program failed to yield the same results. So I've tried to understand his (Stefan Engblom) logic and I just don't get it. On his solution page he states:

Since neither you nor Magnus have any of these 5 suspects, and Marko has at most 2, Black Vienna must be comprised of some subset of A, K, P, Q, W.

I can't figure out how he can state that Marko has at most 2. My analysis is not even near to making an assertion like that. I'm willing to admit my program is inadequate, but I'm wondering if I'm really that far off. I was just wondering if you or one of your readers have looked at that puzzle?

I have saved the puzzle output of my program with some addition notes at:

http://elegantfloraldesigns.us/blogstuff/BvPuzzle.jpg

Chris Okasaki said...

(replaces earlier post where I got the names backward)

Jim: As you said, you know that you do not have any of AKPQW, and neither does Magnus. Therefore, those five cards must be split somehow between Marko and the answer.

Now, Marko showed 1 to KPW and also showed 1 to APQ. If he has P then he has none of AKQW. If he does not have P, then he has one of KW and one of AQ. So he has either one or two of those five cards total.

In fact, he must have two of those five cards, because if he had only one, then the answer would have four cards! Therefore, we can conclude that Marko does not have P.

Jim Freer said...

Yes, how stupid of me. I took another look at it a moment ago and saw it staring at me in the face. You beat me to my demise. Well I'll put the subject down for a while and look at it the next time my son wants to play a game. Thanks for looking at it.

petunia said...

Have you ever played Jotto? We played it a lot in chemistry labs many years ago - it's also a game of inference. Of course, we played it on blackboards - I have no idea whether it's been "onlined".

Chris Okasaki said...

petunia: Yes, in fact I wrote about Jotto in a previous post. It's a great game!

petunia said...

We found that an "interesting" variant was to allow one lie ...

Paul said...

Playing this game optimally is much harder than sudoku, in a complexity theoretic sense. There is no reason to suspect the natural generalization lies in NP, and it even seems unlikely that there are Nash equilibria with concise descriptions (if there are, I would not be surprised to learn that it is PSPACE hard to discover one).

The issue is that in choosing which deductions to make you not only are choosing what information to learn for yourself, but what information to leak to your opponents. You both give your opponents access to the information you obtain and you let your opponents know that this investigation was valuable to you (this second fact is why a pure strategy is unlikely to be optimal). I'm not sure if many people play the game at a level where is relevant though, and if they do it would certainly require working together with a computer assistant.

Discovering whether the identities of the Black Vienna are uniquely determined by the information available is also not obviously in NP. I expect it is hard for NP, and it seems plausible that it is hard for coNP as well. This doesn't really speak to the difficulty of solving the game when N = 27, but it does suggest that it might be a little harder than sudoku.

I don't enjoy games like this in general, but I like them much more than sudoku or other disguised satisfiability problems, which a lot of people like, so I can definitely see how it could be a lot of fun for some.