Conference rusure::math

> What is the luckiest initial roll?

    Snake eyes. (American idiom for (1,1)).

You could roll until your next roll has an expectation value less than zero.
For an initial roll of 7, if you've amassed a score of s, then rolling is
worth:

	30                                  6
	--  *  average non-7 value    +    --  *  (-s)
	36                                 36

Roll if this is greater than zero (i.e. until your score is 35 or more.)

[Average non-7 value = weighted average of {2,3,...,6,8,...11,12} = 7]

 **  **  **  **  **  **  **  **  **  **  **  **  **  **  **  ** 

I think you'd have to be more daring than this to win the game, though.

John

> I think you'd have to be more daring than this to win the game, though.

That's a very interesting point!  The goal of the game (as stated in .0)
is not to maximize your expected sum, but to maximize the expectation that
your score will exceed your opponent's score.

    This sounds like a fine opportunity to write strategy programs that 
    compete against one another.  Perhaps a contest would be in order.
    
    One could easily program the strategy in .2.  Perhaps, however,
    Gilbert could concoct a strategy program that would beat that one.
    Then Yarbrough might be able to beat Gilbert, but lose to the .2 strategy!  
    That is, there may be no "best" strategy -- there's no law that says
    the strategies have to have a "best" member.

      John (always fond of anything that smacks of gambling)

    My recall is a little fuzzy on this one, but your problem sounds
    like craps with the players betting 'no come' on the come-out roll.
    This means that the initial bet is that the roller will *not* roll
    7 or ll (the two highest odds) on comeout.  After bearing out high
    odds on this roll, the no come bettor stands a very high chance
    of winning, since it is almost a sure thing (the house has only
    about 3%) that the roller will crap out before rolling his number.
    BTW as I understand it the reason that most houses bar a payoff
    on the 2 (the major difference between casino and street rules)
    is that the bar 2 is what gives the house its advantage.  Doggone
    it, I'll try to find my craps book and post some exact numbers if
    no one else beats me to it.

    Re .1:
    
>  > What is the luckiest initial roll?

>  Snake eyes. (American idiom for (1,1)).
          
    Actually, I think Box Cars (6,6) is the luckiest (Best) first roll.
    
    
    Reply .2 certainly seems to be the best stategy for the simple case
    of maximizing your totals, however, for the more complex cases of
    N-player competion, with only one winner after M rounds, several
    questions have to be answered before we can proceed.
    
    1)	Are the players aware of the other players current results?
     (Trivial otherwise).
    
    2)  How are rounds, turns, and current knowledge arranged?  The
    usual manner is the rotation method used in most card games.  That
    is, Players (A, B, ... N) are ordered (1, 2, ... N).  Player A would
    play out 1 turn (rolling the dice until he chooses to stop, or repeats
    his first total).  His result is calculated, and all players are
    made aware of it.  This is repeated for (B, C, ... N) in order.
    This constitutes 1 full round.  This is repeated, in the same order,
    for a total of M rounds.
    
    3)  If a player matches an intial roll in one of his later turns,
    does that cause his entire total to be brought to 0, or just the
    total for that turn?
    
    -- Barry
    

    re .5: no, this game has nothing to do with craps, because in craps
    what you win has nothing to do with the VALUE of your point, only
    its likelihood: i.e. 6 and 8 are identical in craps, but in this
    game???
    
    re 2 vs 12: 12 starts your total out with 10 more, but take a look
    at what happens when you roll the complement of your point, which
    you can do several times. (If you roll your point you score the same 
    - 0 - in either case.)

Based on the initial roll, my (current) strategy is to 'stand pat'
with any sum greater than or equal to:

	 2  195
	 3  123
	 4  103
	 5   97
	 6   81
	 7   48
	 8   84
	 9  100
	10  108
	11  113
	12  192

I believe the above strategy is good, but not optimal.

    Re .7:
    
>    re 2 vs 12: 12 starts your total out with 10 more, but take a look
>    at what happens when you roll the complement of your point, which
>    you can do several times. (If you roll your point you score the same 
>    - 0 - in either case.)
          
    I see 3 possible outcomes:
    
    1)	You roll the complement of your point
    	2 or more times before you quit.
    
    2)	You roll the complement of your point
    	once before you quit.
    
    3)	You do not roll the complement of
    	your point before you quit.
    
    Now (2) is even either way, so discount it, (1) obviously favors
    a low point (2 in this case), and (3) obviously favors a high point.
    Now I believe that the chances of (3) occuring with a point of 2
    or 12 are so much higher than (1) that you are better off having
    a high point than a low point.
    
    This would make (6,6) the best first roll.
    
    I guess I'll just test it tonight to see for sure, or someone could
    do the math for it.

    
    Well, here's my straw dog:
    
    initial
    roll   	n	expectation
    =======	====	===========
    2		35.50	92.69
    3		17.50	46.98
    4		11.49	32.19
    5		 8.49	25.13
    6		 6.69	21.17
    7		 5.48	18.77
    8		 6.69	22.49
    9		 8.49	27.74
    10		11.49	36.07
    11		17.50	52.12
    12		35.50	99.06
    
    where "n" is the number of rolls to attempt after the initial roll. "n"
    is calculated as 1/ln(1/(1-p)) with "p" being the probability of
    rolling the initial roll.  I calculate the overall expectation of this
    to be 31.59.  For practical purposes, using n values of 35, 17, 11, 8,
    7, 5, 7, 8, 11, 17, 35 yields an expectation of 31.56.
    
    Note the E(12)=99.06 > E(2)=92.69.
    
    This is (rightly or wrongly) independent of the number of players.
    

re 570.10
    That sounds like it's phrased wrong.  If the initial roll is 3,
    and the current total is 21, I wouldn't expect the decision of
    whether to roll again should be affected by the number of rolls
    taken to reach 21 (e.g., by 3+9+9 or 3+6+6+6).  However, it can
    be simply rephrased as 'cutoff' points; so the cutoff point for
    an initial roll of 2 is 2+35.50*7 = 250.5, and a player would
    stop rolling after reaching 251.


    I think the following adequately describes any strategy aspiring
    to being optimal.  Let p(i,t) be the probability that the player
    decides to roll again, where 'i' is the value of the initial roll,
    and 't' is the current total.  I'll be writing some code to test
    such strategies against each other (using a Markov-chain approach).
    If you care to code a contender, let me know.

    I believe that the "roll n times" method can be translated into a "roll
    until the total is t or more" method directly.  The translation of the
    table in 570.10 would be: 
    
    x		n	t
    ===		===	===
    2,12	35	249
    3,11	17	123
    4,10	11	81
    5,9		8	60
    6,8		7	48
    7		5	39
    
    This does NOT imply that 249 or more points will be achieved only after
    35 tosses.  But approximately the same result will occur regardless of
    which counting method is used. 
    
    Supposition:  The best method will have a probability of 1/e (about
    0.3679) of winning any turn, regardless of the initial value. 
    

I found that the following strategy (in 570.12):

	249  123  81  60  48  39  48  60  81  123  249

is beaten by:

	249  123  81  61  48  39  48  60  81  123  249

and this is beaten by:

	249  123  81  61  49  39  48  60  81  123  249

and this is beaten by....


Continuing in this way, I eventually reached a strategy that could not
be beaten by any strategy that was the same except for an increase by
one of the 'cutoff' points.  This, as it turned out, was beaten by the
strategy in 570.12.

The strategy I'd originally proposed was found using this iterative
approach.  It was handily beaten by Dwayne's strategy (in 570.12).

    I have been using the following strategy:
    
    2	:	250
    3	:	123
    4	:	 80
    5	:	 58
    6	:	 45
    7	:	 35
    8	:	 43
    9	:	 54
    10	:	 74
    11	:	115
    12	:	240
    
    I believe this strategy to be optimal.
    
    -- Barry

But the following beats it:

    2	:	250
    3	:	123
    4	:	 80
    5	:	 58
    6	:	 46 <--
    7	:	 35
    8	:	 43
    9	:	 54
    10	:	 74
    11	:	115
    12	:	240

    I haven't found anything that can beat Barry's strategy in 570.14.
    It may, indeed, be optimal.  Are there any other challengers?
    

    Barry, I think I've beaten your strategy, but only by a tiny amount.
    Try:
    
    2	:	250
    3	:	123
    4	:	 80
    5	:	 58
    6	:	 44 <--
    7	:	 35
    8	:	 42 <--
    9	:	 54
    10	:	 74
    11	:	115
    12	:	240
    
    My calculations say it wins, and a Monte Carlo sample run of 1,000,008
    turns agrees.  It's expectation is 29.76522367/turn.  I believe
    yours has expectation 29.76475483/turn.  A difference of only one
    point every 2133 turns.
    

Re .15:

>But the following beats it:
>
>    2	:	250
>    3	:	123
>    4	:	 80
>    5	:	 58
>    6	:	 46 <--
>    7	:	 35
>    8	:	 43
>    9	:	 54
>    10	:	 74
>    11	:	115
>    12	:	240

    (My 45 was replaced by Peters 46).

     I confess that I don't understand Markov chains too well, but what little
    I can remember leads me to believe that they don't apply in this case.

     The original problem called for ~10 turns, with the winner being the
    person whose TOTAL score was the greatest.  If the winner were the person
    who had the highest score for each seperate round, I might be inclined to
    agree with you.  Furthermore, all of the solutions that we have been
    presenting have been based on the assumption that we will have no knowledge
    of our opponets running score.  As I pointed out earlier, this is not
    normally the case for this kind of game, and this would drastically change
    the optimum strategy, especially in the later rounds.  Also we seem to be
    basing our strategies on the assumption that there are only two players,
    but in fact, the number of players is variable.  This also would greatly
    affect the optimum strategy.

     Now given all this, and that none of our strategies truly address these
    criterion, let me restate my case more unambiguously:

    	I contend that ny strategy will return the highest average value.

    -- Barry

    Re .17
    
    Dwayne, your response leads me to belive that we aren't using the
    same terminoligy.  This is because my calculations showed that there
    were in fact 'pairs' of optimal numbers to stand on.  For example,
    I said that with a point of two, you should stand with 250 or greater.
    In fact 250 is dead even.  Whether you stand or roll returns the
    same average total, I could also have said to stand on 251 with
    the same result.  In fact, all of the numbers that I gave could
    have had a 1 added to them, and still returned that same average
    totals.  All that is except 6 (45), and 8 (43), they were the
    unambiguous best values.  These are also the same values that you
    chose to lower by 1.
      I therefore suspect that you, or your program have taken my values
    as the highest total to continue rolling on, rather than the lowest
    values NOT to roll on.  This interpretation has the effect of adding
    1 to all of my values.  Because of the aforementioned 'pairs', they 
    would all still be correct, except for 6, and 8 which would now
    be 1 too high.  Lowering them would make in optimal again, and this
    gives the very sequence of values that you found to be optimal.(!)
    
    The second thing that I might note is that all the simulations that
    I have run similar to what yours sounded like have had an accuracy
    of only 2 digits in 10000 samples.  Therefore, I would expect that
    your simulation would only be accurate to 3, or 4 places, and the
    differences that you report are only in the fifth place.
    
    	-- Barry
    

What's the payoff??

I've been assuming that each player has no knowledge of the other
player's score (until it comes time to see who won).

I've also assumed that when it comes time to see who won, the two
scores are compared.  If they are equal, there is no payoff.  If
they are unequal, the person with the lower score pays $1 to the
player with the higher score.

Another possibility is that the player with the lower score pays
the *difference* between the two scores to the other player.  But
I doubt that this is the case, since my comment in 570.3 implied
a constant payoff, and the poser has not corrected this comment:

> That's a very interesting point!  The goal of the game (as stated in .0)
> is not to maximize your expected sum, but to maximize the expectation that
> your score will exceed your opponent's score.


We can compare strategies.

Given a strategy, it's possible to determine the probability that the player's
score will be 0, the probability that it'll be 2, that it will be 3, and so on. 

Given these results (as arrays from 0 to 300 or so), its possible to compute
the value of one strategy against annother, as:

	300 300
	Sum Sum  result1[i] * result2[j] * payoff(i,j)
	i=0 j=0

This gives the expected payoff per play.

Since I've been assuming a constant payoff of 1 (or zero if the scores
are equal), this is:

	300                 i-1              300
	Sum  result1[i] * ( Sum result2[j] - Sum result2[j] )
	i=0                 j=0             j=i+1

but because the sum of probabilities is one, this is equal to:

	300                 i-1                   i
	Sum  result1[i] * ( Sum result2[j] - 1 + Sum result2[j] )
	i=0                 j=0                  j=0
or
	300                     i-1
	Sum  result1[i] * ( 2 * Sum result2[j] + result2[i] - 1 )
	i=0                     j=0
or
	300                     i-1
	Sum  result1[i] * ( 2 * Sum result2[j] + result2[i] ) - 1
	i=0                     j=0

The following Pascal program takes this approach.  It reads two strategies
from the terminal, redisplays them and computes the expected value of the
first strategy when played against the second.  With it, you'll discover
that the strategy of .15 beats .14 and .17, and that .14 beats .17.

program dice (input, output);
const
    mm = 300;
    roll_min = 2;
    roll_max = 12;
type
    roll = roll_min..roll_max;
    xreal = quadruple;
    strategy = array [roll] of integer;
    results  = array [0..mm] of xreal;

var
    prob: array [roll] of xreal;

procedure init;
    var
	i: integer;
	w: xreal;
    begin
    for i := roll_min to roll_max do prob[i] := (6-abs(i-7));
    w := 36;
    for i := roll_min to roll_max do prob[i] := prob[i] / w;
    end;

procedure read_strategy (var s1: strategy);
    var
	i: integer;
    begin
    for i := roll_min to roll_max do read (s1[i]);
    readln;
    end;

procedure compute_results (s: strategy; var r: results);
    var
	i,j,k:	integer;
	t: results;
	w: xreal;
    begin
    for i := 0 to mm do r[i] := 0;
    for j := roll_min to roll_max do
	begin
	for i := 0 to mm do t[i] := 0;
	t[j] := prob[j];
	for i := j to s[j]-1 do
	    begin
	    w := t[i];
	    t[i] := 0;
	    for k := roll_min to roll_max do t[i+k] := t[i+k] + w*prob[k];
	    t[i+j] := t[i+j] - w*prob[j];
	    t[ 0 ] := t[ 0 ] + w*prob[j];
	    end;
	for i := 0 to s[j]-1+12 do r[i] := r[i] + t[i];
	end;
    end;

function compare_results (var r1,r2: results): xreal;
    var
	i:	integer;
	t2:	results;
	w:	xreal;
    begin
    t2[0] := 0;  for i := 0 to mm-1 do t2[i+1] := t2[i] + r2[i];
    w := 0;  for i := 0 to mm do w := w + r1[i]*(t2[i] + 0.5*r2[i]);
    compare_results := w;
    end;

function compute_compare (s1, s2: strategy): xreal;
    var
	b,i,j: integer;
	w1,w2: xreal;
	r1,r2: results;
    begin
    compute_results (s1, r1);
    compute_results (s2, r2);
    w1 := compare_results (r1, r2);
    for i := roll_min to roll_max do write(s1[i]:1,' ');writeln;
    for i := roll_min to roll_max do write(s2[i]:1,' ');writeln;
    writeln (w1);
    compute_compare := w1;
    end;

procedure better_strategy (var s1: strategy);
    var
	b,i,j,pj:	integer;
	w1,w2:	xreal;
	s2: strategy;
    label
	10;
    begin
    pj := 0;
    for j := 0 to 2000 do
	begin
	b := (j mod (roll_max-roll_min+1)) + roll_min;
	for i := roll_min to roll_max do s2[i] := s1[i];
	s1[b] := s1[b] + 1;
	w1 := compute_compare (s1, s2);
	if w1 < 0.5 then s1[b] := s1[b] - 1 else pj := j;
	if j-pj > (roll_max-roll_min+1) then goto 10;
	end;
    10:
    end;


procedure main;
var
    s1,s2: strategy;
    w1: xreal;
begin
while true do
    begin
    read_strategy (s1);
    read_strategy (s2);
    w1 := compute_compare (s1, s2);
{ }
{    if w1 > 0.5 then better_strategy (s1) else better_strategy (s2);
{    w1 := compute_compare (s1, s2);
{ }
    end;
end;

begin
init;
main;
end.

Let                                                     
	i = initial roll
	e = expected value of a roll that isn't (i)
	s = score to stop at for highest expectation value

Then
	(1 - p) * e  +  p * (-s)  =  0		[570.2]
	(1 - p) * e  +  p * i  =  7		[average roll is 7]

So
	ps  =  7  -  p * i
or
	s  =  252  /  (36 * p)  -  i

Tabulating:
		i	36*p	s
                                                
		2	1	250
		3	2	123
		4	3	80
		.
    		.
    		12	1	240		[570.14]
			
John

>    This sounds like a fine opportunity to write strategy programs that 
>    compete against one another.  Perhaps a contest would be in order.
    
John Hallyburton:

Would you be willing to run such a contest?  The timid (?!) strategy (250,
123, ..., 240) should surely be entered, but I think some contestants will
try for higher numbers.

John Munzer

re .21

from .20:
> Another possibility is that the player with the lower score pays
> the *difference* between the two scores to the other player.

Thus, over many plays, you'd get:

	Sum (your_total - opponents_total)
or
	Sum (your_total) - Sum(opponents_total)

NOW the expected total (as a single number) is important in judging
the value of a strategy.  And John solved that problem a week ago.

    
    Yup, Barry deduced my booboo.  I was rolling again up to AND INCLUDING
    the value.  And I confirm Barry's values.
    
    The next question (and leaning more toward what Peter's been pointing
    out):
    
         You have been challenged to play ONE game of ONE
         turn only.  A tie is as bad as a loss, and a loss
         by one point is as bad as a loss by 100 points. 
         The only information you have about your opposition
         is that there is only one opponent.
         
         What strategy maximizes your probability of winning?
         

Applying Peter's dice program (.20) to strategies

	EXP  = (250, 123, 80, 58, 45, 35, 43, 54, 74, 115, 240)	     [.14]
	STOP = (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
	XXV  = (25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25)

it seems that STOP beats EXP, EXP beats XXV, and XXV beats STOP.  I think
"beats" means something like "is favored with a yes/no payoff for one turn
for two players."

This was conjectured in .4, and makes .24 hard to answer.
    
John

Re .22:

    I'm willing to run such a contest on VMS.

    Each entry should be object module (or source program or shareable
    image, whichever is smaller) that defines the global entry point (or
    universal symbol) PLAY.  The evaluation program will call this function
    with two by-reference longword integer parameters: 

	roll_again = PLAY (initial_roll, current_total)
    
    The 'initial_roll' is the 'point' you're trying to avoid; 'current_total'
    is the current sum of the rolls.  The function returns 'roll_again', which
    is the probability with which you wish to roll again, expressed as an
    F-floating number.  Strategies that are not probabilistic would return 1.0
    to roll again, or 0.0 to 'stand pat'.  Note that although PLAY returns
    an F-floating number, strategies will be evaluated using H-floating
    precision.

    Each submitted object module (or shareable image) must have a different
    name, even if the new one is only a 'minor tweak'.  Be creative.

    The result of a comparison between two strategies will be a floating
    point number that indicates the expectation of a win (ties are split).
    For example, in a contest between SEATTLE and SLOUGH, SEATTLE might
    be rated 0.716 and SLOUGH would be rated 0.284.  Thus, SEATTLE is
    the better strategy, and would expect a win 71.6% of the time.

    For example, the strategy in 570.21 could be implemented in Pascal by
    the following program:

module dice_570_21;
 
var
    prob: array [2..12] of real;
	{ 1/36,2/36,3/36,4/36,5/36,6/36,5/36,4/36,3/36,2/36,1/36 }

[ initialize ]
procedure init_prob;
    var
	i : integer;
    begin
    for i := 2 to 12 do prob[i] := (6-abs(i-7)) / 36.0 ;
    end;
 
[ global ]
function play ( initial_roll, current_total : integer ) : real;
    begin
    if current_total > 7.0 / prob[initial_roll] - initial_roll 
    then
	play := 0.0
    else
	play := 1.0;
    end;

end.

    Good to see this one dusted off again.
    
    I take it that this contest is testing the two-player one-round
    game? (Seems that way from the description)
    
    Should we post the routines here or mail them to you?
    
    
    --  Barry

    Peter:
                                                  
    Will you run a round robin competition?  I hope so.
    
    Will you enter dice_570_21, please?
    
    Please accept STOP, below, to keep us honest.
    
    John
		==		==		==
module dice_stop;

function play ( initial_roll, current_total : integer ) : real;
    begin
    play := 0.0
    end;
end.

    Some thoughts:
    
    
    Module names:
    
    	One way to pretty much guarantee uniqueness of names without
    	requiring creativity is to name them all "node_user_play".
    
    Random number generator:
    
    	I'm a bit worried about the random number generator.  Particularly
    	in cases where you suggest that one strategy is a smidgeon better
    	than another, in the 9th decimal place.  I'd be more comfortable
    	if such standoffs were tested with a different random number
    	generator.  I assume you're using MTH$RANDOM.  How about trying
    	something else too and see if results change ?
    
    Interesting simpler game:
    
    	Consider a simpler game called "quick_dice" in which before
    	you see the initial roll, you have to announce how many
    	rolls you want.  What's the best number to choose ?  Again,
    	this probably has a different answer depending on whether only
    	one round or ten are being played, and whether exceeding opponents
    	score is sufficient or whether exceeding by as much as possible
    	is important.
                            
    /Eric

re .29
	Sorry, creative names are a requirement!

	What random number generator?  The evaluation uses Markov chain
	techniques.

	Re "quick_dice": I maintain that the optimal strategy need only
	rely on the initial roll and the current total -- it doesn't depend
	on the 'history' (number of rolls taken) to reach that total.
	Hence the interface as described.

>   	                                            [...] whether only
>   	one round or ten are being played, and whether exceeding opponents
>   	score is sufficient or whether exceeding by as much as possible
>   	is important.

	The first -- exceeding opponents score is sufficient.  The second
	-- exceeding by as much as possible -- was solved by Hallyburton
	some time ago.

module evaluate (input, output);
{ }
{	This module contains the routine EVALUATE, which evaluates the relative
{	value of two strategies for the dice game described in note 570 of the
{	MATH notes conference.
{ }
const
    max_total = 1023;			{ ignore rolls beyond this point }
    roll_min = 2;
    roll_max = 12;

type
    roll = roll_min..roll_max;		{ 2..12 }
{   xreal = quadruple;}
    xreal = double;			{ temporarily use double }
    { }
    {	The following describes a probabilistic strategy
    { }
    prob_dist	= array      [0..max_total] of xreal;

var
    prob: array [roll] of xreal;	{ 1/36, 1/18, 1/12, 1/9, 5/36, 1/6,... }

[ initialize ]
procedure init;
    var
	i: integer;
	w: xreal;
    begin
    for i := roll_min to roll_max do prob[i] := (6-abs(i-7));
    w := 36;
    for i := roll_min to roll_max do prob[i] := prob[i] / w;
    end;

procedure compute_dist (
	var pd: prob_dist;
	function play ( initial_roll, current_total : integer ) : real
	);
    var
	i,j,k:	integer;
	w:	xreal;
	pd1:	prob_dist;
    begin
    for i := 0 to max_total do pd[i] := 0;
    for j := roll_min to roll_max do
	begin
	{ }
	{   Initialize the starting configuration.
	{ }
	for i := 0 to max_total do pd1[i] := 0;
	pd1[j] := prob[j];
	{ }
	{   Sequence through the possible states, seeing what the strategy does.
	{ }
	for i := j to max_total - roll_max do
	    begin
	    if pd1[i] > 0 then		{ any chance of reaching this point? }
	        begin
	        w := play (j, i);	{ probability that he rolls }
		if (w > 0) and (w <= 1) then
		    begin
		    w := pd1[i] * w;
		    for k := roll_min to roll_max do
			if k = j
			    then pd1[ 0 ] := pd1[ 0 ] + w * prob[k]
			    else pd1[i+k] := pd1[i+k] + w * prob[k];
		    pd1[i] := pd1[i] - w;
		    end;
	        end;
	    end;
	{ }
	{   Accumulate the probabilities.
	{ }
	for i := 0 to max_total do pd[i] := pd[i] + pd1[i];
	end;
    
    end;

procedure partial_sums (var pd: prob_dist);
    var
	i:	integer;
	w:	xreal;
    begin
    w := 0;
    for i := 0 to max_total do
	begin
	w := w + pd[i];
	pd[i] := w;
	end;
    end;

[ global ]
function evaluate (
	function play1 ( initial_roll, current_total : integer ) : real;
	function play2 ( initial_roll, current_total : integer ) : real
	): xreal;
    var
	pd1,pd2:	prob_dist;
	ps1,ps2:	prob_dist;
	i:	integer;
	ptie,win1,win2:	xreal;
    begin
    { }
    {	Determine the probabilities with which the strategies will finish
    {	with various totals.
    { }
    compute_dist (pd1, play1);
    compute_dist (pd2, play2);
    { }
    {	Now compare the partial sums of the two strategies.
    { }
    ps1 := pd1;
    ps2 := pd2;
    partial_sums (ps1);
    partial_sums (ps2);
    { }
    {	Now determine the probability of a win (splitting ties).
    {	To avoid any bias, we compute this two ways.
    { }
    ptie := 0;
    for i := 0 to max_total do
	ptie := ptie + pd1[i] * pd2[i];
    win1 := ptie/2;
    win2 := ptie/2;
    for i := 1 to max_total do
	begin
	win1 := win1 + pd1[i] * ps2[i-1];
	win2 := win2 + pd2[i] * ps1[i-1];
	end;
    { }
    {	Verify our computations.
    { }
    if abs (win1+win2 - 1.0) > 1.0e-6 then
	begin
	writeln ('*** Roundoff error ***');
	writeln ('win1 = ', win1);
	writeln ('win2 = ', win2);
	end;
    { }
    {	'Average' the two calculated probabilities.
    { }
    evaluate := ((win1) + (1.0-win2)) / 2;
    end;

end.    

    I have a strategy called SA11 that beats DICE_570_21 50.788% of the time,
    beats STOP 60.872% of the time.  Are there any other entries?

{   After mail between Peter and myself we have the following template main
    program that you can hack, compile, link and run together with the
    EVALUATE module a few replies back.  THIS IS REALLY VERY EASY!!!
    
    [1] SAVE this note in (say) TEST.PAS
    [2] SAVE the EVALUATE module earlier in EVAL.PAS
    [3] Edit out header junk in both modules.
    [4] Be sure XREAL is either DOUBLE or QUADRUPLE in both modules.
    [5] Edit TEST.PAS (this note), adding your own function(s) to those herein.
        It is not necessary to remove the ones already there -- you
        will probably want to use them for comparison anyway.
    [6] Edit the last 7 lines of TEST.PAS, replacing STOP or DICE_570_21
        with the name of your function.
    [7] $ PASCAL TEST
    [8] $ PASCAL EVAL
    [9] $ LINK TEST,EVAL
    [A] $ RUN TEST
    
    The output should be self-explanatory.

      John & Peter    
    }
    
program test (input, output);
type
{    xreal = quadruple;}
    xreal = double;
var
    x:	xreal;
    prob: array [2..12] of real;
	{ 1/36,2/36,3/36,4/36,5/36,6/36,5/36,4/36,3/36,2/36,1/36 }

[ initialize ]
procedure init_prob;
    var
	i : integer;
    begin
    for i := 2 to 12 do prob[i] := (6-abs(i-7)) / 36.0 ;
    end;
 
function evaluate (
	function play1 ( initial_roll, current_total : integer ) : real;
	function play2 ( initial_roll, current_total : integer ) : real
	): xreal;
    external;

function stop ( initial_roll, current_total : integer ) : real;
    begin
    stop := 0;	{ Never roll again }
    end;

function dice_570_21 ( initial_roll, current_total : integer ) : real;
    var
	play:	real;
    begin
    if current_total > 7.0 / prob[initial_roll] - initial_roll 
    then
	play := 0.0
    else
	play := 1.0;
    dice_570_21 := play;
    end;

begin
x := evaluate (stop, dice_570_21);
writeln ('Result of STOP vs DICE_570_21 is:', x);
if x > 0.5 then writeln ('	STOP is the better strategy');
if x < 0.5 then writeln ('	DICE_570_21 is the better strategy');
if x = 0.5 then writeln ('	STOP and DICE_570_21 are tied');
end.

.32>    I have a strategy called SA11 that beats DICE_570_21 50.788% of the time,
.32>    beats STOP 60.872% of the time.  Are there any other entries?
    
    I have a strategy (creatively :-) named JCH_2 that beats
    
    	STOP		59.85% of the time,
    	DICE_570_21	53.02% of the time.
    
    Waiting to hear the results of the battle between JCH_2 and SA11...

      John

    CLT::SYS$PUBLIC:SA11.PAS is world-readable.

    The 'amazing' entry below beats STOP, DICE_570_21, and SA11.  Care
    to test JCH_2 against it John?
    

Function real FORTY_ONE ( long pnt, stand )
    If 41% > stand then
        Forty_one = 1
    Else
        Forty_one = 0
    End if
End function

Result of JCH_2 vs PLAY_SA11 is: 4.3905514106251828314767178903449E-0001
      PLAY_SA11 is the better strategy
Result of JCH_2 vs FORTY_ONE is: 4.6355208031659242256334846749652E-0001
      FORTY_ONE is the better strategy

    Well at long last I have completed my master strategy (evil laughter).
    I have been juggling something like 2 to 3 dozen strategies (most
    of them controls for comparision) refining different approachs trying
    to find one that was superior.
    
    I have discovered many interesting things while doing this.  One
    of the most important is that I fully agree with Peter's original
    claim that dominance in this game is NOT transitive, and that there
    is therefore no guarantee of a "perfect" strategy.  In fact I know
    that there can be no unbeatable strategy because I have a simple
    method that can take any strategy and devise a counter strategy
    that is assured of beating the original strategy, but not necessarily
    any other strategy.  I call this "targeting" a strategy, and while
    I have not proven it, I believe that it could be without too much
    trouble.

    The strategy that I have finally settled on is called
    META_PROBABILITY_2.  Of the 30 or so strategies that I have many
    cases of the lack of dominance show up.  There are strategies that
    beat others that beat still others that beat the originals.  M-P-2
    is distinct in that it is the only 'sane' strategy that beats ALL
    of the other strategies.  Except for the strategy that targets M-P-2
    of course, but it loses to most of the other 'sane' strategies.
    
    By a 'sane' strategy, I mean a non-suicidal strategy.  That is, any
    strategy that will not lose to STOP.  Just to be sure though, I
    included many suicidal strategies in my test bed also.

    Because of the aforementioned targeting phenomona I am going to
    wait until after the contest to post the routine.

    
    --  Barry

Take heed of that evil laughter!  META_PROBABILITY_2 is damned good!

>    I have discovered many interesting things while doing this.  One
>    of the most important is that I fully agree with Peter's original
>    claim that dominance in this game is NOT transitive, and that there
>    is therefore no guarantee of a "perfect" strategy.

We're all agreed that dominance is not transitive, but I disagree with the
conclusion that there is no "perfect" strategy.  I believe that there is a
perfect, probabilistic strategy that cannot be beaten. 

Consider the game 'Scissors-paper-stone' (scissors cut paper, paper wraps
stone, stone breaks scissors).  There is no optimal 'pure' strategy (i.e.,
always choose scissors), but the strategy that chooses each option with 1/3
probability cannot be beaten.  The same approach applies to the dice game
-- a player can randomly choose his strategy.

I'm taking the liberty of posting Barry's entry, because I think it comes
close to the "perfect" strategy.  It's certainly the one to beat.

					- Gilbert

From:	CHOVAX::YOUNG        "SWS, Cherry Hill NJ, and Wilmington DE." 20-SEP-1987 23:23
To:	CLT::GILBERT
Subj:	

Peter;

	Well, here it is!  Meta_probability_2, The result of many terracycles
    of CPU time.  I have no idea why this thing works so well on the 
    routines I tested it against (it was developed empiricaly), but it does.
    I doubt that it is optimal, but I do believe that it is close to optimal.
    Let me know when you plan to run the contest, and how my routine(s) do.

Barry



Function real META_PROBABILITY_2 (long pnt, stand)
    Option type = explicit, inactive = ( setup, integer overflow )
    Declare real return_value
    Return_value = 0
    Select pnt
      Case 2% to 6%
        Return_value = 1    If stand < ((6% - pnt) * 10%) + 45%  !   53%
      Case 7%
        Return_value = 1    If stand < 28%
      Case 8% to 12%
        Return_value = 1    If stand < ((pnt - 8%) * 10%) + 38%
    End select
    Meta_probability_2 = Return_value
End function

.38>    I have discovered many interesting things while doing this.  One
.38>    of the most important is that I fully agree with Peter's original
.38>    claim that dominance in this game is NOT transitive, and that there
.38>    is therefore no guarantee of a "perfect" strategy.

    I could have sworn this was conjectured in .4, but not by Peter :-)

    Barry, are you conjecturing that any strategy that beats M-P-2 loses
    to STOP?  Perhaps this is as good a definition of "optimal" as we
    are likely to find, though there is no guarantee it is the case.
    
      John

    1.  What does "stand" mean in meta_probability_2?
    
    2.  Suppose S is a strategy
    		S = {s2, s3, s4, ..., s12}
    	meaning that you stop if your initial roll is j and your current
    	total is greater or equal to sj.  Does strategy
    		S1 = {s2+1, s3+1, s4+1, ..., s12+1}
    	beat S?
    
    John

    RE .40:
    
    Sorry, John.  I can't remember who said what first anymore.
    
    Re .41:
    
    Yes John, you have surmised my 'targeting' trick, though I am now not
    certain that it will always work, it has always worked for me so
    far.
    
    Re .39:
    
    I can't go into it now Peter (I must sleep sometime), but I do not
    agree that all possible meaningful 'combination' strategies are
    representable in the enviornment you give our routines to work in.
    I refer to the Game Theory meaning of strategy, which is what I think 
    you are referring to also.

    
    --  Barry
    
    (ps.  We should do this more often, if only I didn't have to work too.)

    Re .41:
    
    "Stand"  means "how often do you want to stand on this total?"
    
    Bit of a misnomer, I'll admit, but developing 30+ routines on a
    1200 baud line in my spare time tends to strip away a lot of niceties
    like intelligent variable names.
    
    
    --  Barry

    Peter:
    
    Is it possible for you to post a round-robin table for the strategies
    submitted so far?  I'm wondering whether we could find a "best one"
    like Tit for Tat in 518.11.
    
    John

The strategies submitted so far are transitive (!), and so they can be listed
in order:

	META_PROBABILITY_2
	FORTY_ONE
	SA11
	HALF_MEDIAN
	JCH_2
	JCH_1
	STOP
	570_21

    Peter:
    
    What does "transitive" mean in .45?  That there's a best and a worst,
    and well-defined in-betweens?
    
    .25 asserts that
    
    			STOP > 570_21
    			570_21 > XXV
    			XXV > STOP
    
    where XXV is like FORTY_ONE (only it stops at 25, not 41.)  Is this
    assertion true?
    
    John

    It just so happened that AMOUNG THE SUBMITTED STRATEGIES, if S1 > S2
    and S2 > S3 then S1 > S3.

re .46:

    I thought the assertion was true, but just tried it, and it wasn't so.
    However, with a slight modification (going to XXVI) it's true:

module xxvi (input, output);
[ global ] function play ( initial_roll, current_total : integer ) : real;
    begin
    if 26 > current_total
    then play := 1
    else play := 0;
    end;
end.

Here's my entry.   From empirical evidence I'd have to say I fall in the camp
that says there isn't one optimal function that will beat all other functions.

							Simon
---------------------------------------------------------------------------

function WARRIOR (INITIAL_ROLL, CURRENT_TOTAL : integer) : real;
    var
	P : real;
    begin
    P := abs(INITIAL_ROLL-7)+1;
    if CURRENT_TOTAL > P*14 + (INITIAL_ROLL/2)
    then
	WARRIOR := 0
    else
	WARRIOR := 1;
    end;