From: bas@phys.uva.nl (Bas de Bakker)
Newsgroups: rec.puzzles
Subject: Re: Game Theory
Date: 14 Apr 92 08:21:47 GMT
Organization: Institute for Theoretical Physics, Amsterdam, the Netherlands
In-reply-to: jpk2581@tesla.njit.edu's message of 14 Apr 92 05:03:19 GMTLines: 85

>>>>> In article <1992Apr14.000319.1@tesla.njit.edu>,
j>I'm not sure if this is the appropriate group for this, but I've got
j>a game I would like analyzed:

j>A suit of cards (say ace through king of clubs) is shuffled and six
j>cards are dealt randomly to each of two players. The left over card
j>is placed face down in the middle of the table. Each player ante's
j>one chip. The players then alternate turns having the option on each
j>turn to either put another chip in the pot and ask the opponent if
j>he holds a particular card (if the opponent does he must place it
j>face up on the table in front of him) or announce what he believes
j>the value of the card in the center of the table to be and turn it
j>over (doing this doesn't require the player to put a chip in the
j>pot) If the one flipping the card is right he wins the pot, if not
j>the other player does.

j>The game is a lot more subtle than it first appears.  It should be
j>seen immediately that one cannot always simply ask you opponent if
j>he has the cards which you, yourself don't hold, because the instant
j>you name a card that he doesn't hold he will know that it's the one
j>on the table.  So you have to occasionally bluff and ask for a card
j>that you hold in your own hand. It should also be noted that if you
j>bluff and your opponent does not flip the card on the next turn then
j>he will KNOW you were bluffing (and thus know one of the cards in
j>your hand) when you don't know the value of the hidden card.

j>Well, anyway the game doesn't seem like it's overly difficult to
j>solve, but it has escaped me. I assume that the solution involves
j>playing randomly with different probabilities for; 1) asking a legit
j>ques., 2) Bluffing, 3) Calling what you beleive to be a bluff (ie
j>claiming that the center card is the one that your opponent just
j>asked you if you had) 4) asking a dummy question (ie asking for a
j>card which is already face up on the table) and 5) making an
j>educated guess as to the value of the hidden card.

j>Would any of you game theoritians care to give this one 
j>a try?

The comments I'm going to make below are for a slightly different
game. We leave out the chips, players just win or lose (say one
point).

This make the game into a well known game called Guess It. Here are a
few references:

Some comments on the game can be found in "Mathematical Magic Show" by
Martin Gardner (Alfred A. Knopf).

A full analysis is in "A Card Game With Bluffing." Rufus Isaacs, The
American Mathematical Monthly, Vol. 62, February 1955, pages 99-108.

Finally, a basic program that plays the game according to the best
strategy is in "More Basic Compter Games" by David H. Ahl (Creative
Computing Press).

These are the results of my own analysis I did some time ago:
First make a table of numbers P(n,m) which are recursively defined
such that

P(n,m) = (1+mP(m,n-1)(1-P(m-1,n)))/(1+(m+1)P(m,n-1))

Now, apart from obvious moves (like you didn't bluff last time, and he
didn't have the card you asked for so you know the card now) do the
following where n is the number of your opponent's cards and m is the
number of your cards:

If you just answered no to his query: assume that he didn't bluff and
guess the card with probability

((m+1)P(m,n-1)-mP(m-1,n))/(1+(m+1)P(m,n-1))

If its your turn to play, bluff with probability

1/(1+(n+1)P(n,m-1))

As is usual with Game Theory, this is the best strategy against
another best strategy, i.e. it will never lose (on average) against
any other strategy. Of course, if your opponent is obviously dumb
(like he never bluffs) adept your strategy to this.

I'm afraid my old notes are too chaotic to retrieve the actual
analysis from them, interested readers should get the article
mentioned above.

Bas de Bakker.
Xref: sparky rec.puzzles:3522 soc.culture.indian:13633