#include <stdio.h>
#include <math.h>

#define STATES 3

#define ACTIONS 2

double actions[ACTIONS][STATES][STATES] = {
  {
    { 0.0, 0.9, 0.1 },
    { 1.0, 0.0, 0.0 },
    { 1.0, 0.0, 0.0 }
  },
  {
    { 0.0, 0.1, 0.9 },
    { 0.0, 0.8, 0.2 },
    { 0.0, 0.2, 0.8 }
  }
};

double reward[ACTIONS][STATES] = {
  { 0.0, 10.0, 1.0 },
  { 0.0, 10.0, 1.0 }
};

#define ITERATIONS 20
#define DISCOUNT 0.5

double values[ITERATIONS][STATES];

void showvalues(int ite) {
  int i;
  printf("%i:",ite);
  for(i=0;i<STATES;i++) {
    printf(" %.4f",values[ite][i]);
  }
  printf("\n");
}

void latexshowvalues(int ite) {
  int i;
  printf("%i",ite);
  for(i=0;i<STATES;i++) {
    printf(" & %.2f",values[ite][i]);
  }
  printf(" \\\\ \n");
  fflush(stdout);
}

int main() {
  int i,j,k,iteration;
  for(i=0;i<STATES;i++) {
    values[0][i] = 0.0;
  }
  for(iteration=1;iteration<=ITERATIONS;iteration++) {
    for(i=0;i<STATES;i++) {
      double maxval = 0.0;
      int action;
      for(j=0;j<ACTIONS;j++) {
	double val = reward[j][i];
	for(k=0;k<STATES;k++) {
	  double p = actions[j][i][k];
	  val += DISCOUNT*p*values[iteration-1][k];
	}
	if(val > maxval) {
	  action = j;
	  maxval = val;
	}
      }
      //      printf("state %i action %i.\n",i,action);
      values[iteration][i] = maxval;
    }
    showvalues(iteration);
  }

  /* See which action produce the policy. */
  for(i=0;i<STATES;i++) {
    int action;
    double bestval = -1E20;
    int bestaction = -1;
    for(j=0;j<ACTIONS;j++) {
      double val = reward[j][i];
      for(k=0;k<STATES;k++) {
	double p = actions[j][i][k];
	val += DISCOUNT*p*values[ITERATIONS][k];
      }
      if(fabs(val-values[ITERATIONS][i]) < fabs(bestval-values[ITERATIONS][i])) {
	bestval = val;
	bestaction = j;
      }
    }
    printf("state %i has action %i.\n",i,bestaction);
  }
  exit(0);
}