/*
 * Question:
 * 
 * Suppose you have 2m pieces on your one point to bear off and your
 * opponent has 2n pieces on their one point.  When should you double
 * and/or accept?
 * 
 * The solution to this problem will apply (more or less) to many situations
 * where you have m rolls remaining & your opponent has n rolls remaining.
 * 
 * Solution:
 * 
 * Let f[m][n] be your expected winnings assuming that the doubling cube is
 * free,
 * it is your turn, the game is currently worth one point,
 * you have 2m pieces on your one point,
 * and your opponent has 2n pieces on their one point.
 * 
 * Let c[m][n] be your expected winnings assuming that the doubling cube is
 * under your control,
 * it is your turn, the game is currently worth one point,
 * you have 2m pieces on your one point,
 * and your opponent has 2n pieces on their one point.
 * 
 * Let v[m][n] be your expected winnings assuming that the doubling cube is
 * under your opponents control (i.e. you are vulnerable),
 * it is your turn, the game is currently worth one point,
 * you have 2m pieces on your one point,
 * and your opponent has 2n pieces on their one point.
 * 
 * Note that "the game is currently worth one point" implies that
 * f,c,v[m][n] <= 1 for all m,n.
 * We have the following formulas for f,c,v:
 * 
 * f[m][n] = c[m][n] = v[m][n] = 1 for m=0, n=0,1,2,...
 * f[m][n] = c[m][n] = v[m][n] = 1 for m=1, n=1,2,3,...
 * f[m][n] = c[m][n] = v[m][n] = -1 for m=1,2,3,..., n=0
 * 
 * For m>=2, n>=1, we have the following:
 * v[m][n] = -(1/6 * c[n][m-2] + 5/6 * c[n][m-1])
 * f[m][n] = MAX( -(1/6 * f[n][m-2] + 5/6 * f[n][m-1]) , MIN(1,2*v[m][n]) )
 * c[m][n] = MAX( -(1/6 * v[n][m-2] + 5/6 * v[n][m-1]) , MIN(1,2*v[m][n]) )
 * 
 * If the cube is free, you should double when 2*v[m][n] >= f[m][n].
 * If you have control, you should double when 2*v[m][n] >= c[m][n].
 * In either case, the opponent (with n men) should accept if 2*v[m][n] <= 1.
 */ 

#include <stdio.h>

#define NULL_VAL -99
#define MAX_VAL 100

int m,n;

float f[MAX_VAL+1][MAX_VAL+1];
float c[MAX_VAL+1][MAX_VAL+1];
float v[MAX_VAL+1][MAX_VAL+1];

float compute_f();
float compute_c();
float compute_v();

float MAX(float,float);
float MIN(float,float);

main()
{
  initialize_data();

/*
  for(m=1; m <= 10; m++)
  for(n=1; n <= 10; n++)
  {
    printf("f(%d,%d)=%f ",m,n,compute_f(m,n));
    printf("c(%d,%d)=%f ",m,n,compute_c(m,n));
    printf("v(%d,%d)=%f ",m,n,compute_v(m,n));
    printf("\n");
  }
*/

  printf("\\n         111111111122222222223333333333444444444455555555556\n");
  printf("m\\123456789012345678901234567890123456789012345678901234567890\n");
  for(m=1; m <= 60; m++)
  {
    printf("%2d",m);
    for(n=1; n <= 60; n++)
    {
      if( 2*compute_v(m,n) >= compute_c(m,n) )
      {
        if( 2*compute_v(m,n) <= 1 )
	  /* D means double and opponent should accept. */
	  printf("D");
	else
	  /* d means double and opponent shouldn't accept. */
	  printf("d");
      }
      else if( 2*compute_v(m,n) >= compute_f(m,n) )
      {
        if( 2*compute_v(m,n) <= 1 )
	  /* F means double if cube is free and opponent should accept. */
	  printf("F");
	else
	  /* f means double if cube is free and opponent shouldn't accept. */
	  printf("f");
      }
      else
	/* . means you shouldn't double. */
	printf(".");
    }
    printf("\n");
  }
}

initialize_data()
{
  for(m=0; m <= MAX_VAL; m++)
  for(n=0; n <= MAX_VAL; n++)
    f[m][n] = c[m][n] = v[m][n] = NULL_VAL;

  for(n=0; n <= MAX_VAL; n++)
    f[0][n] = c[0][n] = v[0][n] = 1;

  for(n=1; n <= MAX_VAL; n++)
    f[1][n] = c[1][n] = v[1][n] = 1;

  for(m=1; m <= MAX_VAL; m++)
    f[m][0] = c[m][0] = v[m][0] = -1;
}    

float compute_v(int m, int n)
{
  if(v[m][n] == NULL_VAL)
    v[m][n] = -1 * ( (1.0/6) * compute_c(n,m-2) + (5.0/6) * compute_c(n,m-1) );

  return(v[m][n]);
}

float compute_f(int m, int n)
{
  if(f[m][n] == NULL_VAL)
    f[m][n] = MAX( -1 * ((1.0/6)*compute_f(n,m-2) + (5.0/6)*compute_f(n,m-1)), 
                   MIN(1,2*compute_v(m,n)) );

  return(f[m][n]);
}

float compute_c(int m, int n)
{
  if(c[m][n] == NULL_VAL)
    c[m][n] = MAX( -1 * ((1.0/6)*compute_v(n,m-2) + (5.0/6)*compute_v(n,m-1)), 
		   MIN(1,2*compute_v(m,n)) );

  return(c[m][n]);
}

float MAX(float m, float n)
{
  if(m<n)
    return(n);
  else
    return(m);
}

float MIN(float m, float n)
{
  if(m<n)
    return(m);
  else
    return(n);
}