Conference rusure::math

I haven't thought about this enough, but I have a gut feeling that the
optimal strategy leads to a draw, with each player making the same bid at each
turn. It also seems likely that the best play at each turn is to bid the value
of the Club currently faced. The game is entirely too symettrical: what is
optimum for one player is also optimum for the other, and once a good strategy
is found I see no reason why both players should not make the same plays. It's
likely that there is a strategy that will win over all other strategies, but
if both players know it the game will get very dull very quickly!

No rule is included to resolve the game in the case where both players play
alike; I assume that's a draw. 

Lynn Yarbrough 

    A stategy for this game may be probabilistic, e.g., at a given play
    a strategy may specify to take one action with probability p and
    to take the alternative with probability 1-p.  If an optimal strategy
    were of this form, then both players could follow it without
    necessarily making identical plays.
    
    Dan

    Re .1:
    
    Lynn I have played this game (with the full deck) for many years,
    and I can assure you that just playing straight face value is a
    big loser.
    
    --  Barry

    Yes.  For example:

    Card  Bid A  Bid B
     1      1      2	B wins 1
     2      2      3    B wins 2
     3      3      4    B wins 3
     4      4      5    B wins 4
     5      5      6    B wins 5
     6      6      1    A wins 6
                       ----------
			A wins 6, B wins 15

< Note 771.4 by CLT::GILBERT "Builder" >


    Yes.  For example:

    Card  Bid A  Bid B
     1      1      2	B wins 1
     2      2      3    B wins 2
     3      3      4    B wins 3
     4      4      5    B wins 4
     5      5      6    B wins 5
     6      6      1    A wins 6
                       ----------
			A wins 6, B wins 15

    Re .4:
    
    Card  Bid C  Bid B
     1      3      2	C wins 1
     2      4      3    C wins 2
     3      5      4    C wins 3
     4      6      5    C wins 4
     5      1      6    B wins 5
     6      2      1    C wins 6
                       ----------
			B wins 5, C wins 16

    John

Based on the first card shown, we have the folowing games matrices.

If the first card displayed is a 1, then all bids except 1 are recessive;
if the first card displayed is a 2 or 3, then bids of 5 or 6 are recessive.
if the first card displayed is a 4, then a bids of 6 is recessive.

I've not yet calculated the probabilities with which other bids should be made.


(1)       1          2          3          4          5          6
    1	 0.0        0.0449762  0.329673   0.611329   0.838422   1.0
    2	-0.0449762  0.0        0.0799245  0.406259   0.719465   1.0
    3	-0.329673  -0.0799245  0.0        0.100166   0.479419   0.980173
    4	-0.611329  -0.406259  -0.100166   0.0        0.157973   0.768317
    5	-0.838422  -0.719465  -0.479419  -0.157973   0.0        0.273276
    6	-1.0       -1.0       -0.980173  -0.768317  -0.273276   0.0


(2)       1          2          3          4          5          6
    1	 0.0       -0.255224   0.0230925  0.353442   0.708391   1.00000
    2	 0.255224   0.0       -0.185813   0.195183   0.593423   1.00000
    3	-0.0230925  0.185813   0.0       -0.114204   0.326654   0.940266
    4	-0.353442  -0.195183   0.114204   0.0       -0.0542997  0.690646
    5	-0.708391  -0.593423  -0.326654   0.0542997  0.0        0.0767811
    6	-1.00000   -1.00000   -0.940266  -0.690646  -0.0767811  0.0


(3)       1          2          3          4          5          6
    1	 0.0       -0.360723  -0.0659593  0.262770   0.657126   1.00000
    2	 0.360723   0.0       -0.301670   0.111189   0.539346   1.00000
    3	 0.0659593  0.301670   0.0       -0.207589   0.277646   0.934999
    4	-0.262770  -0.111189   0.207589   0.0       -0.107977   0.679171
    5	-0.657126  -0.539347  -0.277646   0.107977   0.0        0.0460065
    6	-1.00000   -1.00000   -0.934999  -0.679171  -0.0460065  0.0


(4)       1          2          3          4          5          6
    1	 0.0       -0.577227  -0.327183  -0.0101114  0.413511   1.00000 
    2	 0.577227   0.0       -0.557823  -0.180881   0.254398   1.00000 
    3	 0.327183   0.557823   0.0       -0.485288   0.0232754  0.883010 
    4	 0.0101113  0.180881   0.485288   0.0       -0.346608   0.604607 
    5	-0.413511  -0.254398  -0.0232754  0.346608   0.0       -0.0546824
    6	-1.00000   -1.00000   -0.883010  -0.604607   0.0546824  0.0


(5)       1          2          3          4          5          6
    1	 0.0       -0.839281  -0.595172  -0.285680   0.208484   0.800117 
    2	 0.839281   0.0       -0.819912  -0.462126   0.0317561  0.726742 
    3	 0.595172   0.819912   0.0       -0.731584  -0.233658   0.504729 
    4	 0.285680   0.462126   0.731584   0.0       -0.587593   0.137049 
    5	-0.208484  -0.0317561  0.233658   0.587593   0.0       -0.332484 
    6	-0.800117  -0.726742  -0.504729  -0.137049   0.332484   0.0


(6)       1          2          3          4          5          6
    1	 0.0       -0.937100  -0.786428  -0.557211  -0.162860   0.501976 
    2	 0.937100   0.0       -0.929834  -0.712169  -0.340816   0.407651 
    3	 0.786428   0.929834   0.0       -0.889544  -0.571833   0.183575 
    4	 0.557211   0.712169   0.889544   0.0       -0.819470  -0.277414 
    5	 0.162860   0.340816   0.571833   0.819470   0.0       -0.661133 
    6	-0.501976  -0.407651  -0.183575   0.277414   0.661133   0.0

	My experience playing GOPS has been with a full deck (suit)
	rather than just A-6.  I've also found the game to be much
	more interesting with 3 or more players.

	One variation on resolving tie bids (when playing with more
	than two players) is to award the card to the next highest
	bid.

    I suppose I should describe how 771.7 was generated (perhaps someone
    wants to double-check the figures).
    
    The program is recursive, and uses the following two functions:

    V := VALUE0 (C, A, B, S, D);

	VALUE0 calculates the value (expectation) of the position for player A
	C is the set of cards remaining in the deck to be bid upon
	A is the set of cards remaining in the A player's hand
	B is the set of cards remaining in the B player's hand
	|C| = |A| = |B|
	S is the current 'stake' -- usually this is 0, but it may not
	    be if the previous cards played by A and B were equal.
	D is the number of points on cards 'won' by A less those won by B
	
    V := VALUE1 (C, A, B, S, D);

	VALUE1 calculates the value (expectation) of the position for player A
	The parameters are as above, except that |C|+1 = |A| = |B|, and S is
	non-zero.

    The recursion is as follows:

	VALUE0 (C, A, B, S, D)
	    if |C| = 0 then V := signum(D)
	    else V := the average of
		VALUE1 (C - {i}, A, B, S+i, D),
		where i varies over all cards in the set C
		
	VALUE1 (C, A, B, S, D)
	    V := the value of the games matrix Z[i,j], where
		i ranges over the cards in A's hand and
		j ranges over the cards in B's hand, and
		Z[i,j] = VALUE0 (C, A-{i}, B-{j},
			    (if i=j then s else 0),	! still at stake if tied
			    (d + signum(i-j)*s));	! award s to higher card

    Unfortunately, I don't have a good program for solving games matrices.
    Can somebody else supply one?  For what it's worth, here's a short
    description of matrix games.

    The approach to solving a game matrix is as follows.  There is a matrix of
    values.  Player R chooses a row, and player C chooses a column.  This
    determines an element in the matrix, and that value is the amount R wins
    from C (if positive) or that C wins from R (if negative).  Thus, R wants to
    choose rows (with probabilities) that maximize his expectation, and C
    chooses columns to minimize R's expectation.  With each player playing
    an optimal strategy, there is a single 'value' for the game.

    The solution of the following matrix game:

	 3 -4
	-1  1

    would usually proceed as follows.  First, a value is added to each element
    so that all table entries are non-negative.  Here, we add 5 -- this simply
    increases the 'value' of the game by 5.

	8 1
	4 6

    Now supposing that C chooses columns 1 and 2 with probabilities c1 and c2
    respectively, C wants to ensure that if R chooses the first row, then

	8 * c1 + 1 * c2 <= v

    where v is the value of the game, and if R chooses the second row, then

	4 * c1 + 6 * c2 <= v

    We also have c1 + c2 = 1.  Usually, we solve the above equations
    for c1/v and c2/v (since v > 0).

	8 * (c1/v) + 1 * (c2/v) <= 1
	4 * (c1/v) + 6 * (c2/v) <= 1
	c1/v + c2/v = 1/v

    Here, we find that (c1/v,c2/v) = (5/44,4/44) gives equality in the first
    two equations (the best that C can hope for), and the third equation yields
    v = 44/9.  Thus, C should choose the first column with probability 5/9, and
    the second with probability 4/9.  If you're thinking 'Simplex algorithm',
    you're following along nicely.

    The analysis for R is similar:
	
	8 * (r1/v) + 4 * (r2/v) >= 1
	1 * (r1/v) + 6 * (r2/v) >= 1
	r1/v + r2/v = 1/v

    We find (r1/v,r2/v) = (2/44,7/44), and v = 44/9 (again, of course),
    so (r1,r2) = (2/9,7/9).

    The original game:

	 3 -4
	-1  1

    has a value of 44/9 - 5 = -1/9.  Thus, R should expect to lose 1/9
    on every play.  To make this a fair game, C should pay R 1/9 before
    every play.