#include <iostream.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>


const int N = 150;
bool PRINT_ON = 0;
int CURRENT_TO_BEAT;
double BLUFF[N][N][N];
double CALL[N][N];
int NET_STANDING[1000];
int ROUNDS_PLAYED = 0;
int MAX_SCORE;

// return player 1's utility
double compute_local_equilibrium(double* p, double* v_1, double* v_2, int n){
  double bluffer_strategy[N][N];
  double caller_strategy[N];
  for (int i=0;i<N;i++) 
    for (int j=0;j<N;j++)
      bluffer_strategy[i][j]=0;
  for (int i=0;i<N;i++)
    caller_strategy[i]=0;

  caller_strategy[0]=1;
  bluffer_strategy[0][0]=1;
  int i = 1;
  int j=n-1;
  bool stop = 0;
  double remaining_prob=1-p[0];
  double remaining_j_prob = p[j];
  while (!stop){
    double needed_prob = v_2[i]*p[i]/(1-v_2[i]);
    if (needed_prob + p[i] > remaining_prob){
      stop=1;
    }
    else {
      remaining_prob -= needed_prob;
      remaining_prob -= p[i];
      while (remaining_j_prob < needed_prob){

	bluffer_strategy[j][i] = remaining_j_prob/p[j];
	needed_prob -=remaining_j_prob;
	j--;
	remaining_j_prob = p[j];
      }
      remaining_j_prob -= needed_prob;
      bluffer_strategy[j][i] = needed_prob/p[j];
      bluffer_strategy[i][i] = 1;
      i++;
    }
  }  //stopped
  bluffer_strategy[j][i] = remaining_j_prob/p[j];
  j--;
  while (j>= i){
    bluffer_strategy[j][i] = 1;
    j--;
  }


  // ok, figured out bluffer strategy. know that i is uncontested
  if (PRINT_ON)
    cout << MAX_SCORE-i << " is uncontested\n";
  for (int j = 1; j<=i; j++)
    if (v_1[j]==0)
      caller_strategy[j]=0;  // this makes sense, but is it right?
    else
      caller_strategy[j] = 1-(v_1[i]/v_1[j]);
  for (int j = i+1; j<n; j++)
    caller_strategy[j]=0;


  //let's compute the value to player 1
  double result=0;
  for (int j=0; j<=i; j++){
    result += p[j]*caller_strategy[j];
    result += p[j]*(1-caller_strategy[j])*v_1[j];
  }
  for (int j=i+1; j<n; j++){
    result += p[j]*v_1[i];  // always can get uncontested value
  }


  if (PRINT_ON){
  for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
      if (bluffer_strategy[i][j]>0)
	cout << "Given that the roller rolls " << MAX_SCORE-i << ", the probability of claiming " << MAX_SCORE-j << " is " << bluffer_strategy[i][j] << "\n";
  for (int i=0;i<n;i++)
    if (caller_strategy[i]>0)
      cout << "The probability that the caller will call when the roller claims " << MAX_SCORE-i << " is " << caller_strategy[i] << "\n";

  cout << "The utility for the player is " << result << ".\n";
  }

  for (int i=0;i<n;i++)
    for (int j=0;j<n;j++)
      BLUFF[CURRENT_TO_BEAT][i][j]=bluffer_strategy[i][j];
  for (int i=0;i<n;i++)
    CALL[CURRENT_TO_BEAT][i]= caller_strategy[i];


  return result;

}

double compute_overall_equilibrium(double* p, int n){ // zero sum only
  double intermediate[N];  // number to beat
  intermediate[0]=0; // cannot beat 0
  CURRENT_TO_BEAT=1;
  double v_1[N];
  double v_2[N];
  for (int i=0;i<N;i++){
    v_1[i]=0;
    v_2[i]=1;
  }
  //PRINT_ON=1;
  for (int i=1;i<n;i++){
    //cout << "\nStep " << i << " of the DP\n";
    if (PRINT_ON)
      cout << "\nComputing the optimal strategy when the last claim was " << MAX_SCORE - i << "\n";
    v_1[i-1] = 1- intermediate[i-1];
    if (PRINT_ON)
      for (int k=0; k<n; k++)
	cout << "The utility of reaching state " << MAX_SCORE-k << " is now "<< v_1[k] << "\n";

    v_2[i-1] = intermediate[i-1];
    intermediate[i] = compute_local_equilibrium(p,v_1,v_2,n);
    CURRENT_TO_BEAT++;
  }

  //  cout << "\nStep " << n << " of the DP\n";
  if (PRINT_ON)
    cout << "\nComputing the optimal strategy when the last claim was " << MAX_SCORE - n << "\n";

  v_1[n-1] = 1- intermediate[n-1];
  if (PRINT_ON)
    for (int k=0; k<n; k++)
      cout << "The utility of reaching state " << MAX_SCORE-k << " is now "<< v_1[k] << "\n";
  //    cout << "v_1 of " << k+1 << " is now "<< v_1[k] << "\n";
  v_2[n-1] = intermediate[n-1];

 
  //PRINT_ON=1;
  return compute_local_equilibrium(p,v_1,v_2,n);

  
}







double random_double(){
  return ((double)rand())*1.0/((double)RAND_MAX);
}

int random_int(int n){
  return (int) (random_double() * ((double) n));
}


int roll(int n, double* p){
  double rn=random_double();
  int i=0;
  while (1){
    if (p[i] >= rn)
      return i;
    else{
      rn -= p[i];
      i++;
    }
  }
}


int bluff_play(int to_beat, int rolled){
  double rn = random_double();
  int i=0;
  while (1){
    if (BLUFF[to_beat][rolled][i] >= rn)
      return i;
    else{
      rn -= BLUFF[to_beat][rolled][i];
      i++;
    }
  }
}

bool call_play(int to_beat, int said){
  double rn = random_double();
  if (CALL[to_beat][said] >= rn)
    return 1;
  else
    return 0;
}


int play_step(int n, double* p, int to_beat, int player){
  if (player==0) { //computer
    int rolled = roll(n,p);
    if (rolled == 0){
      cout << "The computer rolled "<<MAX_SCORE<<".  The computer wins this round.\n";
      return 0;
    }
    int chosen = bluff_play(to_beat, rolled);
    if (chosen >= to_beat){ // sometimes the computer has no hope of winning and reports something illegal.  hack to fix this:
      //cout << "(hopeless computer)\n";
      chosen = to_beat-1;
    }
    cout << "The computer claims " << MAX_SCORE-chosen; 
    bool called;
    if (chosen==0){
      cout << ". You must call because this is the highest possible claim.\n";
      called=1;
    }
    else{
      cout << ". Type 1 to call, 0 to accept: ";
      cin >> called;
    }
    cout << "(The computer rolled " << MAX_SCORE-rolled <<".)\n";
    if (called) {
      if (chosen!=rolled){
	cout << "You win this round.\n";
	return 1;
      }
      else{
	cout << "The computer wins this round.\n";
	return 0;
      }
    }
    else
      return play_step(n, p, chosen, 1);
  }
  else {
    int rolled = roll(n,p);
    if (rolled == 0){
      cout << "You rolled " << MAX_SCORE << ".  You win this round!\n";
      return 1;
    }
    cout << "You rolled " << MAX_SCORE-rolled << ".  What would you like to claim? ";
    int chosen;
    cin >> chosen;
    chosen= MAX_SCORE-chosen;
    while (chosen >= to_beat || chosen <0){
      cout << "That is not a legal move.  Please try again: ";
      cin >> chosen;
      chosen=MAX_SCORE-chosen;
    }
   
    bool called = call_play(to_beat, chosen);
    if (called) {
      cout << "The computer calls.\n";
      if (chosen==rolled){
        cout << "You win this round.\n";
        return 1;
      }
      else{
        cout << "The computer wins this round.\n";
        return 0;
      }
    }
    else{
      cout << "The computer did not call.\n";
      return play_step(n, p, chosen, 0);
    }
  }
}
  
double compute_prob(int num_dice, int dice_sides, int target_total){
  int num_ways_current[N];
  int num_ways_next[N];
  for (int i=0; i<N; i++){
    num_ways_current[i]=0;
    num_ways_next[i]=0;
  }
  num_ways_current[0]=1;

  for (int j=0;j<num_dice;j++){
    for (int i=0; i<= target_total; i++){
      for (int k=i-dice_sides; k<i; k++)
        if (k >= 0)
          num_ways_next[i]+=num_ways_current[k];
    }

    for (int i=0; i<N; i++){
      num_ways_current[i]=num_ways_next[i];
      num_ways_next[i]=0;
    }
  }
  return (double) num_ways_current[target_total] / pow(dice_sides,num_dice);
}


int main(){

  cout << "\nThis variant of the game of Liar's Dice proceeds as follows.  Player 1 rolls some number of dice under a cup, and peeks under the cup.  Then, player 1 makes a claim about the total value that she rolled.  Player 2 must then accept this claim, or call bluff.  If player 2 calls, then player 1 wins if she told the truth, and player 2 wins if she lied.  If player 2 accepts, then player 2 must roll next, and make a claim.  However, player 2 *must* make a higher claim than the claim from player 1 that he accepted.  Then, player 1 must accept or call bluff; if she accepts, she has to roll again and claim a higher value than the claim that she accepted, etc.\n\n";




  cout << "This program computes a game-theoretically optimal (minimax) strategy for this game, for an arbitrary number of dice (with an arbitrary number of sides per die), or even for an arbitrary distribution over 'scores' that a player can roll.  (Thus, the program can in principle also model such things as 'four-of-a-kind beats full house,' but for now the user has to specify the distribution herself in such cases.)\n\n";

  cout << "Because the game is luck-based, it is still possible to beat this optimal player if you play well and get lucky...\n\n";

  cout << "Please send any questions, observations, or bugs to Vincent Conitzer (conitzer@cs.cmu.edu).\n\n";

  cout << "Would you like to play with dice (0) or specify your own probability distribution over scores (1)? ";
  bool ans;
  cin >> ans;
  int n;
  double p[N];
  if (!ans){
    int dice_sides;
    cout << "How many sides does a die have? (E.g. a 2-sided die is a coin.) ";
    cin >> dice_sides;
    int num_dice;
    cout << "How many dice are there? ";
    cin >> num_dice;

    MAX_SCORE = num_dice * dice_sides;
    n=MAX_SCORE;
    for (int i=0; i<n; i++){
      p[i] = compute_prob(num_dice,dice_sides,MAX_SCORE-i);
      //      cout << p[i] << " is prob of " << MAX_SCORE-i << "\n";
    }
  }

  else {
    cout << "Give the highest possible score: ";
    cin >> n;
    MAX_SCORE=n;
    for (int j=0;j<n;j++){
      cout << "Give P(" << MAX_SCORE-j << "): ";
      cin >> p[j];
    }
  }
  //  double v_1[N];
  //  double v_2[N];
  //  for (int j=0;j<n;j++){
  //    cout << "give v_1(" << j+1 << "): ";
  //    cin >> v_1[j];
  //    cout << "give v_2(" << j+1 << "): ";
  //    cin >> v_2[j];
  //  }

  cout << "Would you like to see the optimal strategy (1) or turn this off (0)? ";
  cin >> PRINT_ON;
  compute_overall_equilibrium(p,n);

  cout << "\nOptimal strategy computed, ready to play...\n\n";
  int computer_wins=0;
  int human_wins=0;
  while(1){
    NET_STANDING[ROUNDS_PLAYED++]=human_wins-computer_wins;
    cout << "History of total winnings: ";
    for (int i=0; i<ROUNDS_PLAYED; i++)
      cout << NET_STANDING[i] << " ";
    cout << "\n";
    int winner = play_step(n,p,n,0);
    human_wins+=winner;
    computer_wins+=(1-winner);
    cout << "\nYou have won " << human_wins << " times, the computer has won " << computer_wins << " times.\n";
    winner = play_step(n,p,n,1);
    human_wins+=winner;
    computer_wins+=(1-winner);
    cout << "\nYou have won " << human_wins << " times, the computer has won " << computer_wins << " times.\n";
  }
  

}