fork(2) download
copy 
  1. program optstop(input,output);
  2. {
  3.    An optimal stopping card game
  4.    Posted on December 7, 2013 by possiblywrong.wordpress.com
  5.  
  6.    Let's play the following simple game: I will shuffle a standard
  7.    52-card deck, and deal one card at a time face up onto the table
  8.    between us.  You can say "Stop" at any time, at which point I will pay
  9.    you an amount equal to the fraction of cards dealt so far that are red.
  10.    For example, if you stop after seeing a single card, you win 1 if it
  11.    is red, 0 if it is black, with expected return 1/2.  Of course,
  12.    you can wait until the entire deck is dealt, also with a guaranteed
  13.    return of 1/2.
  14.  
  15.    The problem is: can you do better than this?
  16.    What is the optimal strategy for playing this game,
  17.    and what is the corresponding expected return?
  18. }
  19.  
  20. const
  21.   RED=26;
  22.   BLACK=26;
  23.  
  24. type
  25.   tBlack = 0..BLACK;
  26.   tRed = 0..RED;
  27.   tMatrix = array[tRed, tBlack] of Double;
  28.   tDraw = array[tRed, tBlack] of Boolean;
  29.  
  30. var
  31.   r: tRed;
  32.   b: tBlack;
  33.   avg: Double; { average }
  34.   q: Double; { quotient = current return = r/(r+b) }
  35.   Matrix: tMatrix; { value of hand }
  36.   Draw: tDraw; { draw another? yes=true }
  37.  
  38. begin
  39.   { right column }
  40.   for b:=0 to BLACK do
  41.   begin
  42.     Matrix[RED,b]:=RED/(RED+b);
  43.     Draw[RED,b]:=false;
  44.   end;
  45.  
  46.   { bottom row }
  47.   for r:=0 to RED-1 do
  48.   begin
  49.     Matrix[r, BLACK]:=RED/(RED+BLACK);
  50.     Draw[r, BLACK]:=true;
  51.   end;
  52.  
  53.   { the center }
  54.   for r := RED-1 downto 0 do
  55.     for b:= BLACK-1 downto 1 do
  56.     begin
  57.       q := r/(r+b);
  58.       avg:=  (RED-r)/(RED+BLACK-r-b)*Matrix[r+1,b]
  59.           +(BLACK-b)/(RED+BLACK-r-b)*Matrix[r,b+1];
  60.       if q > avg then  { best strategy }
  61. {     if r > b then } { simple strategy }
  62.       begin
  63.         Matrix[r,b]:=q;
  64.         Draw[r,b]:=false;
  65.       end
  66.       else
  67.       begin
  68.         Matrix[r,b]:=avg;
  69.         Draw[r,b]:=true;
  70.       end;
  71.     end;
  72.  
  73.  
  74.   { top row }
  75.   for r:= RED downto 1 do
  76.   begin
  77.     Matrix[r,0]:=1;
  78.     Draw[r,0]:=false;
  79.   end;
  80.   { top left corner, avoiding division by zero }
  81.   Matrix[0,0]:=  RED/(RED+BLACK)*Matrix[1,0]
  82.               +BLACK/(RED+BLACK)*Matrix[0,1];
  83.   Draw[0,0]:=true;
  84.  
  85.  
  86.   { OUTPUT }
  87.   { top row }
  88.   for r:= 0 to RED do
  89.     write(r:7);
  90.   writeln;
  91.  
  92.   { data }
  93.   for b:= 0 to BLACK do
  94.   begin
  95.     write(b:2,'  ');
  96.     for r:= 0 to RED do
  97.       if Draw[r,b] then
  98.         write(Matrix[r,b]:4:3,'  ')
  99.       else
  100.         write(Matrix[r,b]:4:3,'* ');
  101.     writeln;
  102.   end;
  103.  
  104. end.
  105.  
  106.  
  107.  
Success #stdin #stdout 0s 236KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
      0      1      2      3      4      5      6      7      8      9     10     11     12     13     14     15     16     17     18     19     20     21     22     23     24     25     26
 0  0.792  1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 1.000* 
 1  0.584  0.616  0.667* 0.750* 0.800* 0.833* 0.857* 0.875* 0.889* 0.900* 0.909* 0.917* 0.923* 0.929* 0.933* 0.938* 0.941* 0.944* 0.947* 0.950* 0.952* 0.955* 0.957* 0.958* 0.960* 0.962* 0.963* 
 2  0.551  0.565  0.585  0.617  0.667* 0.714* 0.750* 0.778* 0.800* 0.818* 0.833* 0.846* 0.857* 0.867* 0.875* 0.882* 0.889* 0.895* 0.900* 0.905* 0.909* 0.913* 0.917* 0.920* 0.923* 0.926* 0.929* 
 3  0.536  0.544  0.554  0.569  0.591  0.625* 0.667* 0.700* 0.727* 0.750* 0.769* 0.786* 0.800* 0.813* 0.824* 0.833* 0.842* 0.850* 0.857* 0.864* 0.870* 0.875* 0.880* 0.885* 0.889* 0.893* 0.897* 
 4  0.528  0.532  0.538  0.547  0.558  0.575  0.600* 0.636* 0.667* 0.692* 0.714* 0.733* 0.750* 0.765* 0.778* 0.789* 0.800* 0.810* 0.818* 0.826* 0.833* 0.840* 0.846* 0.852* 0.857* 0.862* 0.867* 
 5  0.522  0.525  0.529  0.535  0.542  0.551  0.565  0.585  0.615* 0.643* 0.667* 0.688* 0.706* 0.722* 0.737* 0.750* 0.762* 0.773* 0.783* 0.792* 0.800* 0.808* 0.815* 0.821* 0.828* 0.833* 0.839* 
 6  0.518  0.521  0.523  0.527  0.531  0.538  0.546  0.558  0.575  0.600* 0.625* 0.647* 0.667* 0.684* 0.700* 0.714* 0.727* 0.739* 0.750* 0.760* 0.769* 0.778* 0.786* 0.793* 0.800* 0.806* 0.813* 
 7  0.515  0.517  0.519  0.522  0.525  0.529  0.534  0.542  0.552  0.566  0.588* 0.611* 0.632* 0.650* 0.667* 0.682* 0.696* 0.708* 0.720* 0.731* 0.741* 0.750* 0.759* 0.767* 0.774* 0.781* 0.788* 
 8  0.513  0.514  0.516  0.518  0.520  0.523  0.527  0.531  0.538  0.547  0.560  0.579* 0.600* 0.619* 0.636* 0.652* 0.667* 0.680* 0.692* 0.704* 0.714* 0.724* 0.733* 0.742* 0.750* 0.758* 0.765* 
 9  0.511  0.512  0.513  0.515  0.517  0.519  0.521  0.525  0.529  0.535  0.543  0.554  0.571* 0.591* 0.609* 0.625* 0.640* 0.654* 0.667* 0.679* 0.690* 0.700* 0.710* 0.719* 0.727* 0.735* 0.743* 
10  0.510  0.511  0.512  0.513  0.514  0.515  0.517  0.520  0.523  0.527  0.532  0.539  0.550  0.565* 0.583* 0.600* 0.615* 0.630* 0.643* 0.655* 0.667* 0.677* 0.688* 0.697* 0.706* 0.714* 0.722* 
11  0.509  0.509  0.510  0.511  0.512  0.513  0.514  0.516  0.518  0.521  0.525  0.529  0.536  0.546  0.560* 0.577* 0.593* 0.607* 0.621* 0.633* 0.645* 0.656* 0.667* 0.676* 0.686* 0.694* 0.703* 
12  0.508  0.508  0.509  0.509  0.510  0.511  0.512  0.513  0.515  0.517  0.519  0.523  0.527  0.533  0.542  0.556* 0.571* 0.586* 0.600* 0.613* 0.625* 0.636* 0.647* 0.657* 0.667* 0.676* 0.684* 
13  0.507  0.507  0.507  0.508  0.509  0.509  0.510  0.511  0.512  0.514  0.516  0.518  0.521  0.525  0.531  0.539  0.552* 0.567* 0.581* 0.594* 0.606* 0.618* 0.629* 0.639* 0.649* 0.658* 0.667* 
14  0.506  0.506  0.506  0.507  0.507  0.508  0.509  0.509  0.510  0.511  0.513  0.514  0.517  0.519  0.523  0.529  0.536  0.548* 0.563* 0.576* 0.588* 0.600* 0.611* 0.622* 0.632* 0.641* 0.650* 
15  0.505  0.505  0.506  0.506  0.506  0.507  0.507  0.508  0.509  0.509  0.510  0.512  0.513  0.515  0.518  0.521  0.527  0.534  0.545* 0.559* 0.571* 0.583* 0.595* 0.605* 0.615* 0.625* 0.634* 
16  0.504  0.505  0.505  0.505  0.505  0.506  0.506  0.507  0.507  0.508  0.509  0.510  0.511  0.512  0.514  0.516  0.520  0.525  0.532  0.543* 0.556* 0.568* 0.579* 0.590* 0.600* 0.610* 0.619* 
17  0.504  0.504  0.504  0.504  0.505  0.505  0.505  0.506  0.506  0.507  0.507  0.508  0.509  0.510  0.511  0.513  0.515  0.518  0.523  0.529  0.541* 0.553* 0.564* 0.575* 0.585* 0.595* 0.605* 
18  0.503  0.503  0.504  0.504  0.504  0.504  0.504  0.505  0.505  0.505  0.506  0.506  0.507  0.508  0.509  0.510  0.512  0.514  0.517  0.521  0.527  0.538* 0.550* 0.561* 0.571* 0.581* 0.591* 
19  0.503  0.503  0.503  0.503  0.503  0.504  0.504  0.504  0.504  0.505  0.505  0.505  0.506  0.506  0.507  0.508  0.509  0.510  0.512  0.515  0.519  0.525  0.537* 0.548* 0.558* 0.568* 0.578* 
20  0.502  0.502  0.503  0.503  0.503  0.503  0.503  0.503  0.503  0.504  0.504  0.504  0.505  0.505  0.506  0.506  0.507  0.508  0.509  0.511  0.514  0.517  0.524* 0.535* 0.545* 0.556* 0.565* 
21  0.502  0.502  0.502  0.502  0.502  0.502  0.502  0.503  0.503  0.503  0.503  0.503  0.504  0.504  0.504  0.505  0.505  0.506  0.507  0.508  0.510  0.512  0.516  0.523* 0.533* 0.543* 0.553* 
22  0.501  0.502  0.502  0.502  0.502  0.502  0.502  0.502  0.502  0.502  0.502  0.503  0.503  0.503  0.503  0.504  0.504  0.504  0.505  0.506  0.507  0.508  0.510  0.514  0.522* 0.532* 0.542* 
23  0.501  0.501  0.501  0.501  0.501  0.501  0.501  0.502  0.502  0.502  0.502  0.502  0.502  0.502  0.502  0.503  0.503  0.503  0.503  0.504  0.505  0.505  0.507  0.509  0.512  0.521* 0.531* 
24  0.501  0.501  0.501  0.501  0.501  0.501  0.501  0.501  0.501  0.501  0.501  0.501  0.501  0.501  0.502  0.502  0.502  0.502  0.502  0.502  0.503  0.503  0.504  0.505  0.507  0.510* 0.520* 
25  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.501  0.501  0.501  0.501  0.501  0.501  0.501  0.501  0.501  0.501  0.501  0.501  0.501  0.502  0.502  0.502  0.503  0.505  0.510* 
26  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500  0.500*
https://ideone.com/8ilm6V
language:
Pascal (fpc 3.0.4)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!