tag:blogger.com,1999:blog-2564777502681463717.post7530267096920590688..comments2023-12-31T10:17:57.560-05:00Comments on Teaching, Playing, and Programming: Games for Programmers: Black ViennaChris Okasakihttp://www.blogger.com/profile/18247315355264748920noreply@blogger.comBlogger20125tag:blogger.com,1999:blog-2564777502681463717.post-139562928788050402010-01-03T19:27:55.618-05:002010-01-03T19:27:55.618-05:00Playing this game optimally is much harder than su...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). <br /><br />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.<br /><br />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.<br /><br />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.Paul Christianohttps://www.blogger.com/profile/09161849602388308455noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-71284126697809153492009-02-12T19:01:00.000-05:002009-02-12T19:01:00.000-05:00We found that an "interesting" variant was to allo...We found that an "interesting" variant was to allow one lie ...Unknownhttps://www.blogger.com/profile/13176903305520517144noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-55695372801461094202009-02-12T18:57:00.000-05:002009-02-12T18:57:00.000-05:00petunia: Yes, in fact I wrote about Jotto in a pre...petunia: Yes, in fact I wrote about Jotto in a <A HREF="http://okasaki.blogspot.com/2008/04/games-for-programmers-jotto.html" REL="nofollow">previous post</A>. It's a great game!Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-2706773765460689292009-02-12T18:53:00.000-05:002009-02-12T18:53:00.000-05:00Have you ever played Jotto? We played it a lot in...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".Unknownhttps://www.blogger.com/profile/13176903305520517144noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-23605451845486677102008-08-04T18:05:00.000-04:002008-08-04T18:05:00.000-04:00Yes, how stupid of me. I took another look at it ...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.Jim Freerhttps://www.blogger.com/profile/04675896663697865109noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-12824437937995517762008-08-04T17:55:00.000-04:002008-08-04T17:55:00.000-04:00(replaces earlier post where I got the names backw...<I>(replaces earlier post where I got the names backward)</I><BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>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.Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-59816796890413707282008-08-04T16:23:00.000-04:002008-08-04T16:23:00.000-04:00I commented earlier about building a program to he...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:<BR/><BR/>http://www.thegamesjournal.com/puzzles/BlackVienna1.shtml<BR/><BR/>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:<BR/><BR/>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.<BR/><BR/>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?<BR/><BR/>I have saved the puzzle output of my program with some addition notes at:<BR/><BR/>http://elegantfloraldesigns.us/blogstuff/BvPuzzle.jpgJim Freerhttps://www.blogger.com/profile/04675896663697865109noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-72162628731276258452008-07-31T09:32:00.000-04:002008-07-31T09:32:00.000-04:00I've played several 3-player games lately. It wor...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.)Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-60065505143645937352008-07-31T09:27:00.000-04:002008-07-31T09:27:00.000-04:00Weeble: That seems like a reasonable way to make t...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.<BR/><BR/>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 Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-43615407802348720212008-07-31T08:36:00.000-04:002008-07-31T08:36:00.000-04:00Sorry if this is getting a bit boring, but I suppo...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.<BR/><BR/>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:<BR/><BR/>ABC<BR/>DEF<BR/>GHI<BR/><BR/>JKL<BR/>MNO<BR/>PQR<BR/><BR/>STU<BR/>VWX<BR/>YZÖ<BR/><BR/>Then your diagonal slices would be ANÖ, BOY, CMZ, DQU, etc.<BR/><BR/>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:<BR/><BR/>AÖN<BR/>DUQ<BR/>GXK<BR/><BR/>JIW<BR/>MCZ<BR/>PFT<BR/><BR/>SRE<BR/>VLH<BR/>YOB<BR/><BR/>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.<BR/><BR/>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. ;)Weeblehttps://www.blogger.com/profile/14430249240219688811noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-73686030510972155122008-07-30T07:43:00.000-04:002008-07-30T07:43:00.000-04:00Weeble: I believe that the letters are evenly dist...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.<BR/><BR/>It would matter if letters were not evenly distributed, because then players holding cards that appear on fewer investigations would have an advantage.Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-47212703931594891922008-07-30T04:09:00.000-04:002008-07-30T04:09:00.000-04:00I'm curious about how the 36 investigation cards w...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?Weeblehttps://www.blogger.com/profile/14430249240219688811noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-54432487903242590472008-07-29T12:08:00.000-04:002008-07-29T12:08:00.000-04:00jim: I personally would have no problem playing ag...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.)<BR/><BR/>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.Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-63209816074933639122008-07-29T11:08:00.000-04:002008-07-29T11:08:00.000-04:00I have an ethics question about playing a game lik...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.<BR/><BR/>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.<BR/><BR/>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.<BR/><BR/>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. :)<BR/><BR/>Sample output:<BR/>http://elegantfloraldesigns.us/blogstuff/BvGameExample.jpgJim Freerhttps://www.blogger.com/profile/04675896663697865109noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-70939553776895784972008-07-17T23:25:00.000-04:002008-07-17T23:25:00.000-04:00"I should think that there is some formula one cou..."I should think that there is some formula one could derive that would give you the average time-to-win based on..."<BR/><BR/>Yes, I think that would be pretty straightforward if you could choose the investigations freely (as you do in, say, Mastermind).<BR/> <BR/>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.<BR/><BR/>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.<BR/><BR/>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.Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-88712237157653257742008-07-17T23:08:00.000-04:002008-07-17T23:08:00.000-04:00@chrisThat strikes me as a fairly straightforward ...@chris<BR/><BR/>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.<BR/><BR/>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. <BR/><BR/>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.<BR/><BR/>I'm intrigued, certainly. I'll have to think about it some more...Joe Fredettehttps://www.blogger.com/profile/07170469679136904832noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-66303293823935296622008-07-17T19:34:00.000-04:002008-07-17T19:34:00.000-04:00Joe: Yes, it should be pretty easy to hack up a Bl...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!<BR/><BR/>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."Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-5758802809482625802008-07-17T17:12:00.000-04:002008-07-17T17:12:00.000-04:00It strikes me that this is a game well suited for ...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. <BR/><BR/>I mean- assuming you _have_ to alibi every card you can, hmm...<BR/><BR/>I'll have to hack up a haskell implementation to mess around with.Joe Fredettehttps://www.blogger.com/profile/07170469679136904832noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-43485493631478698372008-07-17T13:51:00.000-04:002008-07-17T13:51:00.000-04:00pengrate: There are certainly similarities between...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.Chris Okasakihttps://www.blogger.com/profile/18247315355264748920noreply@blogger.comtag:blogger.com,1999:blog-2564777502681463717.post-59355908886964551952008-07-17T12:19:00.000-04:002008-07-17T12:19:00.000-04:00You know, this is just Clue without the board and ...You know, this is just Clue without the board and dice.Unknownhttps://www.blogger.com/profile/13204120952458936162noreply@blogger.com