/* Shut-the-box: Atta Chui, Sept 95 */

#include <stdio.h>

#define MAXINT 9
#define MININT 1
#define MAXMOVES 5
#define MAXSTATES 512
#define MAXDICE 12
#define MINDICE 2

#define numToState(c) (1<<(c-MININT))

float pDice[MAXDICE + 1]; /* p[i] = dice value i is thrown */

typedef struct {
  int numLeft; /* numLeft = 0 when all numbers are discarded */
  int moveCount[MAXDICE + 1];
  int bestMove[MAXDICE + 1];
  float estProb;
} NODE;

NODE winningTable[MAXSTATES]; 

/* ShowState: display iState as a row of numbers; store the
   result in pbuffer; return number of characters printed */ 
int ShowState(int iState, char *pbuffer) {
  int i, count = 0;
  for (i=MAXINT; i>=MININT; i--)
    if (iState & numToState(i)) count += sprintf(pbuffer + count, "%i ", i);
  return count;
}

int MoveList(int iState, int nDice, int *availList) {
  int count = 0, num1, num2, comState;
  if (iState<=0) {
    printf ("Internal error: MoveList\n");
    return -1;
  }
  /* remove one number? */
  if (iState & numToState(nDice)) {
    availList[count] = iState - numToState(nDice);
    count++;
  }
  /* remove 2 numbers? */
  if (nDice >= 3) {
    for (num1 = MININT; num1 <= (nDice-1)/2; num1++) {
      num2 = nDice - num1;
      comState = numToState(num1) + numToState(num2);
      if ((iState & comState) == comState) {
        availList[count] = iState - comState;
        count++;
      }
    }
  }
  return count;
}

void SetuppDice(void) {
  pDice[0] = 0.0;
  pDice[1] = 0.0;
  pDice[2] = 1.0 / 36.0;
  pDice[3] = 2.0 / 36.0;
  pDice[4] = 3.0 / 36.0;
  pDice[5] = 4.0 / 36.0;
  pDice[6] = 5.0 / 36.0;
  pDice[7] = 6.0 / 36.0;
  pDice[8] = 5.0 / 36.0;
  pDice[9] = 4.0 / 36.0;
  pDice[10] = 3.0 / 36.0;
  pDice[11] = 2.0 / 36.0;
  pDice[12] = 1.0 / 36.0;
}

/* BuildTable */
/* mode = 0: best tactics */
/*      = 1: random choice */
/*      = 2: worst choice */
void BuildTable(int mode) {
  int iState, num, left;

  /* set numLeft */
  for (iState=0; iState<MAXSTATES; iState++) {
    left = 0;
    for (num=MININT; num<=MAXINT; num++) {
      if (iState & numToState(num)) left++;
    }
    winningTable[iState].numLeft = left;
    winningTable[iState].estProb = -1.0; /* uninitialized this node */
  }

  /* numLeft = 0 */
  winningTable[0].estProb = 1.00;

  /* loop through all states in increasing numLeft */
  for (left=1; left<=MAXINT-MININT+1; left++) {
    for (iState=1; iState<MAXSTATES; iState++) {
      if (winningTable[iState].numLeft == left) {
        /* fill in this node */
        int list[MAXMOVES], dice, count;
        int availMove, goodMove;
        float score, p, estProbSum = 0.0;
        for (dice = MINDICE; dice <= MAXDICE; dice++) {
          /* moveCount */
          count = MoveList(iState, dice, list);
          winningTable[iState].moveCount[dice] = count;
          /* bestMove */
          if (count == 0) {
            winningTable[iState].bestMove[dice] = -1;
          } else {
            /* pick the best move */
            switch (mode) {
            case 0: /* optimized */
              goodMove = -1;
              score = -99.9;
              for (availMove = 0; availMove < count; availMove++) {
                p = winningTable[list[availMove]].estProb;
                if (p < 0) {
                  printf("un-initialized node %i: algorithm aborted.", list[availMove]);
                  return;
                }
                if (p > score) {
                  goodMove = list[availMove];
                  score = p;
                }
              } /* end for availMove */
              winningTable[iState].bestMove[dice] = goodMove;
              break;
            case 1: /* averaged */
              score = 0.0;
              for (availMove = 0; availMove < count; availMove++) {
                p = winningTable[list[availMove]].estProb;
                if (p < 0) {
                  printf("un-initialized node %i: algorithm aborted.", list[availMove]);
                  return;
                }
                score += p;
              } /* end for availMove */
              winningTable[iState].bestMove[dice] = list[0];
              score = score / count;
              break;
            case 2: /* worst case */
              goodMove = -1;
              score = +99.9;
              for (availMove = 0; availMove < count; availMove++) {
                p = winningTable[list[availMove]].estProb;
                if (p < 0) {
                  printf("un-initialized node %i: algorithm aborted.", list[availMove]);
                  return;
                }
                if (p < score) {
                  goodMove = list[availMove];
                  score = p;
                }
              } /* end for availMove */
              winningTable[iState].bestMove[dice] = goodMove;
              break;
            default:
              printf("invalid mode %i: algorithm aborted.", mode);
              return;
            }
          }
          /* estProb */
          if (winningTable[iState].bestMove[dice] >= 0)
            estProbSum += pDice[dice] * score;
        } /* end for dice */
        winningTable[iState].estProb = estProbSum;
      } /* end if numLeft = left */
    } /* end for iState */
  } /* end for left (number of passes) */
}

/* ReadTable */
/* shortForm = 0: show all */
/*           = 1: show choices and probability */
/*           = 2: show choices only */
void ReadTable(int iState, int shortForm) {
  char buffer1[100], buffer2[100];
  int i, nextState;
  ShowState(iState, buffer1);
  for (i = MINDICE; i <= MAXDICE; i++) {
    if ((shortForm >= 1) && (winningTable[iState].moveCount[i] <= 1))
      goto nextDice;
    if (winningTable[iState].bestMove[i] == 0)
      printf("%s <-- %i = WIN\n", buffer1, i);
    else if (winningTable[iState].bestMove[i] == -1)
      printf("%s <-- %i = LOSE\n", buffer1, i);
    else {
      nextState = winningTable[iState].bestMove[i];
      ShowState(nextState, buffer2);
      printf("%s <-- %i = %s (%f)\n", buffer1, i, buffer2,
        winningTable[nextState].estProb);
    }
nextDice:
  }
  if (shortForm != 2) printf("%s *** p = %g\n", buffer1,
    winningTable[iState].estProb);
}

void PrintTable(FILE *stream, int iState, int shortForm) {
  char buffer1[100], buffer2[100];
  int i, nextState;
  ShowState(iState, buffer1);
  for (i = MINDICE; i <= MAXDICE; i++) {
    if ((shortForm >= 1) && (winningTable[iState].moveCount[i] <= 1))
      goto nextDice;
    if (winningTable[iState].bestMove[i] == 0)
      fprintf(stream, "%s <-- %i = WIN\n", buffer1, i);
    else if (winningTable[iState].bestMove[i] == -1)
      fprintf(stream, "%s <-- %i = LOSE\n", buffer1, i);
    else {
      nextState = winningTable[iState].bestMove[i];
      ShowState(nextState, buffer2);
      fprintf(stream, "%s <-- %i = %s (%f)\n", buffer1, i, buffer2,
        winningTable[nextState].estProb);
    }
nextDice:
  }
  if (shortForm != 2) fprintf(stream, "%s *** p = %g\n", buffer1,
    winningTable[iState].estProb);
}

void TestMoveList(void) {
  char buffer[100];
  int list[10], count, ndice, state, i;
  state = 487;
  ndice = 2;
  printf("state = %i\n", state);
  printf("ndice = %i\n", ndice);
  ShowState(state, buffer);
  printf("%s\n", buffer);
  count = MoveList(state, ndice, list);
  if (count>=1) {
    printf("available move(s) ...\n");
    for (i=0; i<count; i++) {
      ShowState(list[i], buffer);
      printf("%s\n", buffer);
    }
  } else {
    printf("no move.\n");
  }
}

void TestPrintTable(void) {
  int left, iState;
  FILE *stream;
  stream = fopen("f:\\a_box\\box2.txt", "w");
  for (left=MAXINT-MININT+1; left>=1; left--) 
    for (iState = MAXSTATES-1; iState >= 1; iState--)
      if (winningTable[iState].numLeft == left)
        PrintTable(stream, iState, 2);
  fclose(stream);
}

void TestReadTable(void) {
  int iState;
repeatInput:
  printf("\nState (1-511) = ? ");
  scanf("%i", &iState);
  if ((iState >= 1) && (iState <= MAXSTATES-1)) {
    ReadTable(iState, 0);
    goto repeatInput;
  } else {
    printf("Exit.");
  }
}

int main() {
  int iState;
  printf("Shut-the-box.\n");
  SetuppDice();
  BuildTable(0);
  TestPrintTable();
  printf("*** end ***");
  return 0;
}

/* some results: */
/* Optimized  - p = 0.0535 */
/* Averaged   - p = 0.0257 */
/* Worst case - p = 0.0146 */