#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

#define rock      0
#define paper     1
#define scissors  2

#define players   50         /* number of players in the tournament */
#define tourneys  1          /* number of round-robin tournaments */
#define trials    1000       /* number of turns per match */

#define fw        5          /* field width for printed numbers */
#define verbose1  0          /* print result of each trial */
#define verbose2  0          /* print match histories */
#define verbose3  1          /* print result of each match */

/*  Full History Structure (global variables, accessible to the
                            current player during each match)

      - element 0 is the number of trials played so far
      - element i is the action taken on turn i (1 <= i <= trials ) */

int my_history[trials+1], opp_history[trials+1];

/*  Tournament Crosstable Structure  */

#define nameleng  18
typedef struct {
    char name[nameleng+1];   /* descriptive name (max 18 chars) */
    int(*pname)();           /* function name for computer player */
    int result[players+1];   /* list of player's match results */
} Player_Table;


#define maxrandom 2147483648.0   /* 2^31, ratio range is 0 <= r < 1 */

int flip_biased_coin (double prob)
{
    /* flip an unfair coin (bit) with given probability of getting a 1 */

    if ( (random() / maxrandom) >= prob )
         return(0);
    else return(1);
}

int biased_roshambo (double prob_rock, double prob_paper)
{
    /* roshambo with given probabilities of rock, paper, or scissors */
    double throw;

    throw = random() / maxrandom;

    if ( throw < prob_rock )                   { return(rock); }
    else if ( throw < prob_rock + prob_paper ) { return(paper); }
    else /* throw >= prob_rock + prob_paper */ { return(scissors); }
}

int beat (int what_to_beat) {
    return ((what_to_beat + 1)%3);
}

/*  RoShamBo Player Algorithms  */

int randbot () {
    /* generate action uniformly at random (optimal strategy) */
    return( random() % 3); }

int rockbot () {
    /* "Good ole rock.  Nuthin' beats rock." */
    return(rock); }
int scissorbot () {
    return(scissors); }
int paperbot () {
    return(paper); }

int r226bot () {
    return( biased_roshambo(0.2, 0.2)); }
int r262bot () {
    return( biased_roshambo(0.2, 0.6)); }
int r622bot () {
    return( biased_roshambo(0.6, 0.2)); }

int rotatebot ()
{   /* rotate choice each turn */
    return( my_history[0] % 3); }
int rotatebackbot () {
    /* rotate choice each turn */
    return( 2 - my_history[0] % 3); }
int flip1bot () {
    return( my_history[0] % 2); }
int flip2bot () {
    return( my_history[0] % 2 * 2); }
int flip3bot () {
    return( my_history[0] % 2 + 1); }
int quad1bot () {
    return( ((my_history[0]) % 2) * (my_history[0] % 4 / 2 + 1)); }
int quad2bot () {
    return( (((my_history[0]) % 2) * (my_history[0] % 4 / 2 + 1) + 1) % 3); }
int quad3bot () {
    return( (((my_history[0]) % 2) * (my_history[0] % 4 / 2 + 1) + 2) % 3); }

int copybot ()
{
    /* do whatever would have beat the opponent last turn */
    return( (opp_history[opp_history[0]] + 1) % 3);
}

int copy2bot ()
{
    /* do whatever would have beat the opponent two turns ago */
    if (opp_history[0]==1) 
       return( random() % 3);
    else
       return( (opp_history[opp_history[0]-1] + 1) % 3);
}

int last3bot () {
    /* beat whatever was the most frequent in the last 3 moves */
    if (opp_history[0]==1)
       return( random() % 3 );
    else if (opp_history[0]==2) {
       if (opp_history[1] == opp_history[2])
	  return (beat(opp_history[1]));
       else 
	  return (beat(opp_history[1+random()%2]));
    } else {
       if (opp_history[opp_history[0]] 
        == opp_history[opp_history[0]-1])  
	  return (beat(opp_history[opp_history[0]]));
       else if (opp_history[opp_history[0]] 
        == opp_history[opp_history[0]-2])  
	  return (beat(opp_history[opp_history[0]]));
       else if (opp_history[opp_history[0]-1] 
        == opp_history[opp_history[0]-2])  
	  return (beat(opp_history[opp_history[0]-1]));
       else
	  return ( random() % 3 );
    }
}
int last3but2bot () {
    /* beat whatever was the most frequent in the last 3 moves */
    if (opp_history[0]==1)
       return( random() % 3 );
    else if (opp_history[0]==2) {
       if (opp_history[1] == opp_history[2])
	  return (beat(opp_history[1]));
       else 
	  return (beat(opp_history[1+random()%2]));
    } else {
       if (opp_history[opp_history[0]] 
        == opp_history[opp_history[0]-1])  
	  return (beat(opp_history[opp_history[0]]));
       else if (opp_history[opp_history[0]] 
        == opp_history[opp_history[0]-2])  
	  return (beat(opp_history[opp_history[0]]));
       else if (opp_history[opp_history[0]-1] 
        == opp_history[opp_history[0]-2])  
	  return (beat(opp_history[opp_history[0]-1]));
       else
	  return (beat(opp_history[opp_history[0]-(random() % 2)]));
    }
}

int copyeitherbot () {
    /* do whatever would have beat the opponent one or two turns ago */
    if ((random() % 2) || (opp_history[0]==1))
       return( (opp_history[opp_history[0]] + 1) % 3);
    else
       return( (opp_history[opp_history[0]-1] + 1) % 3);
}


int copy3eitherbot () {
    /* do whatever would have beat the opponent one to three turns ago */
    int i; i = (random() % 3);
    if ((i==0) || (opp_history[0]<3))
       return( (opp_history[opp_history[0]] + 1) % 3);
    else if (i==1)
       return( (opp_history[opp_history[0]-1] + 1) % 3);
    else
       return( (opp_history[opp_history[0]-2] + 1) % 3);
}

int copy4eitherbot () {
    /* do whatever would have beat the opponent one to four turns ago */
    int i; i = (random() % 4);
    if ((i==0) || (opp_history[0]<4))
       return( (opp_history[opp_history[0]] + 1) % 3);
    else if (i==1)
       return( (opp_history[opp_history[0]-1] + 1) % 3);
    else if (i==2)
       return( (opp_history[opp_history[0]-2] + 1) % 3);
    else
       return( (opp_history[opp_history[0]-3] + 1) % 3);
}

int apebot ()
{
    /* do whatever the opponent did last turn */
    return( (opp_history[opp_history[0]] + 0) % 3);
}

int losebot ()
{
    /* do whatever would have lost to the opponent last turn */
    return( (opp_history[opp_history[0]] + 2) % 3);
}

int switchbot ()
{
    /* never repeat the previous pick */
    if ( my_history[my_history[0]] == rock ) {
        return( biased_roshambo(0.0, 0.5) ); }
    else if ( my_history[my_history[0]] == paper ) {
        return( biased_roshambo(0.5, 0.0) ); }
    else return( biased_roshambo(0.5, 0.5) );
}

void makestats(int *rcount, int *pcount, int *scount) {
    int i;
    rcount = 0;  pcount = 0;  scount = 0;
    for (i = 1; i <= opp_history[0]; i++) {
        if (opp_history[i] == rock)            { rcount++; }
        else if (opp_history[i] == paper)      { pcount++; }
        else /* opp_history[i] == scissors */  { scount++; }
    }
}

int copyfreqbot () {
    int rcount, pcount, scount; 
    if (random() % 2)
       return( (opp_history[opp_history[0]] + 1) % 3);
    else {
      makestats(&rcount,&pcount,&scount);
      if ( (rcount > pcount) && (rcount > scount) ) { return(paper); }
      else if ( pcount > scount ) { return(scissors); }
      else { return(rock); }
    }
}

int cheesebot ()
{
    /* do whatever would have beat the opponent last turn */
    if ( opp_history[opp_history[0]] == ((my_history[my_history[0]] +1) %3)) {
           return((((my_history[my_history[0]] + 1) % 3)+1) % 3);
    } else {
           return switchbot();
    }
}


int lfreqbot () {
    /* play whatever will lose the opponent's most lfrequent choice */
    int rcount, pcount, scount; makestats(&rcount,&pcount,&scount);
    if ( (rcount > pcount) && (rcount > scount) ) { return(scissors); }
    else if ( pcount > scount ) { return(rock); }
    else { return(paper); }
}
int ilfreqbot () {
    /* play whatever will lose the opponent's most inlfrequent choice */
    int rcount, pcount, scount; makestats(&rcount,&pcount,&scount);
    if ( (rcount < pcount) && (rcount < scount) ) { return(scissors); }
    else if ( pcount < scount ) { return(rock); }
    else { return(paper); }
}
int mlfreqbot () {
    /* play whatever will lose the opponent's middle choice */
    int rcount, pcount, scount; makestats(&rcount,&pcount,&scount);
    if ( (rcount > pcount) && (rcount < scount) ) { return(scissors); }
    else if ( (rcount < pcount) && (rcount > scount) ) { return(scissors); }
    else if ( (rcount < pcount) && (scount > pcount) ) { return(rock); }
    else if ( (rcount > pcount) && (scount < pcount) ) { return(rock); }
    else { return(paper); }
}

int tfreqbot () {
    /* play whatever will tie the opponent's most tfrequent choice */
    int rcount, pcount, scount; makestats(&rcount,&pcount,&scount);
    if ( (rcount > pcount) && (rcount > scount) ) { return(rock); }
    else if ( pcount > scount ) { return(paper); }
    else { return(scissors); }
}
int itfreqbot () {
    /* play whatever will tie the opponent's most intfrequent choice */
    int rcount, pcount, scount; makestats(&rcount,&pcount,&scount);
    if ( (rcount < pcount) && (rcount < scount) ) { return(rock); }
    else if ( pcount < scount ) { return(paper); }
    else { return(scissors); }
}
int mtfreqbot () {
    /* play whatever will tie the opponent's middle choice */
    int rcount, pcount, scount; makestats(&rcount,&pcount,&scount);
    if ( (rcount > pcount) && (rcount < scount) ) { return(rock); }
    else if ( (rcount < pcount) && (rcount > scount) ) { return(rock); }
    else if ( (rcount < pcount) && (scount > pcount) ) { return(paper); }
    else if ( (rcount > pcount) && (scount < pcount) ) { return(paper); }
    else { return(scissors); }
}

int freqbot () {
    /* play whatever will beat the opponent's most frequent choice */
    int rcount, pcount, scount; makestats(&rcount,&pcount,&scount);
    if ( (rcount > pcount) && (rcount > scount) ) { return(paper); }
    else if ( pcount > scount ) { return(scissors); }
    else { return(rock); }
}
int ifreqbot () {
    /* play whatever will beat the opponent's most infrequent choice */
    int rcount, pcount, scount; makestats(&rcount,&pcount,&scount);
    if ( (rcount < pcount) && (rcount < scount) ) { return(paper); }
    else if ( pcount < scount ) { return(scissors); }
    else { return(rock); }
}
int mfreqbot () {
    /* play whatever will beat the opponent's middle choice */
    int rcount, pcount, scount; makestats(&rcount,&pcount,&scount);
    if ( (rcount > pcount) && (rcount < scount) ) { return(paper); }
    else if ( (rcount < pcount) && (rcount > scount) ) { return(paper); }
    else if ( (rcount < pcount) && (scount > pcount) ) { return(scissors); }
    else if ( (rcount > pcount) && (scount < pcount) ) { return(scissors); }
    else { return(rock); }
}

    /*  End of RoShamBo Player Algorithms  */

void Init_Player_Table (Player_Table crosstable[players+1])
{
    int i, j;

    strcpy(crosstable[0].name, "Player Name");

    strcpy(crosstable[1].name, "Random (Optimal)");
    crosstable[1].pname = randbot;

    strcpy(crosstable[2].name, "Good Ole Rock");
    crosstable[2].pname = rockbot;

    strcpy(crosstable[3].name, "R-P-S 20-20-60");
    crosstable[3].pname = r226bot;

    strcpy(crosstable[4].name, "Rotate R-P-S");
    crosstable[4].pname = rotatebot;

    strcpy(crosstable[5].name, "Beat The Last Move");
    crosstable[5].pname = copybot;

    strcpy(crosstable[6].name, "Always Switchin'");
    crosstable[6].pname = switchbot;

    strcpy(crosstable[7].name, "Beat Frequent Pick");
    crosstable[7].pname = freqbot;

    strcpy(crosstable[8].name, "Ape The Last Move");
    crosstable[8].pname = apebot;

    strcpy(crosstable[9].name, "Lose The Last Move");
    crosstable[9].pname = losebot;

    strcpy(crosstable[10].name, "Beat Two Moves Ago");
    crosstable[10].pname = copy2bot;


    strcpy(crosstable[11].name, "Rotate R-S-P");
    crosstable[11].pname = rotatebackbot;
    strcpy(crosstable[12].name, "Beat 1/2 Prev Move");
    crosstable[12].pname = copyeitherbot;
    strcpy(crosstable[13].name, "Beat Infreq Pick");
    crosstable[13].pname = ifreqbot;
    strcpy(crosstable[14].name, "Beat Middle Pick");
    crosstable[14].pname = mfreqbot;
    strcpy(crosstable[15].name, "R-P-S 20-60-20");
    crosstable[15].pname = r262bot;
    strcpy(crosstable[16].name, "R-P-S 60-20-20");
    crosstable[16].pname = r622bot;
    strcpy(crosstable[17].name, "Ed Scissorhands");
    crosstable[17].pname = scissorbot;
    strcpy(crosstable[18].name, "Paperboy");
    crosstable[18].pname = paperbot;
    strcpy(crosstable[19].name, "Lose Freq Pick");
    crosstable[19].pname = lfreqbot;

    strcpy(crosstable[20].name, "Lose Mid Pick");
    crosstable[20].pname = mlfreqbot;
    strcpy(crosstable[21].name, "Lose Infreq Pick");
    crosstable[21].pname = ilfreqbot;
    strcpy(crosstable[22].name, "Tie Freq Pick");
    crosstable[22].pname = tfreqbot;
    strcpy(crosstable[23].name, "Tie Middle Pick");
    crosstable[23].pname = mtfreqbot;
    strcpy(crosstable[24].name, "Tie Infreq Pick");
    crosstable[24].pname = itfreqbot;
    strcpy(crosstable[25].name, "Beat 1/3 Prev Move");
    crosstable[25].pname = copy3eitherbot;
    strcpy(crosstable[26].name, "Beat 1/4 Prev Move");
    crosstable[26].pname = copy4eitherbot;
    strcpy(crosstable[27].name, "Beat Last or Freq");
    crosstable[27].pname = copyfreqbot;
    strcpy(crosstable[28].name, "RP cycle");
    crosstable[28].pname = flip1bot;
    strcpy(crosstable[29].name, "RS cycle");
    crosstable[29].pname = flip2bot;

    strcpy(crosstable[30].name, "PS cycle");
    crosstable[30].pname = flip3bot;
    strcpy(crosstable[31].name, "RPRS cycle");
    crosstable[31].pname = quad1bot;
    strcpy(crosstable[32].name, "PSPR cycle");
    crosstable[32].pname = quad2bot;
    strcpy(crosstable[33].name, "SRSP cycle");
    crosstable[33].pname = quad3bot;
    strcpy(crosstable[34].name, "Best in last 3");
    crosstable[34].pname = last3bot;
    strcpy(crosstable[35].name, "Best in last 3/2");
    crosstable[35].pname = last3but2bot;
    strcpy(crosstable[36].name, "Cheese Bot");
    crosstable[36].pname = cheesebot;
    strcpy(crosstable[37].name, "Random");
    crosstable[37].pname = randbot;
    strcpy(crosstable[38].name, "Random");
    crosstable[38].pname = randbot;
    strcpy(crosstable[39].name, "Random");
    crosstable[39].pname = randbot;

    strcpy(crosstable[40].name, "Random");
    crosstable[40].pname = randbot;
    strcpy(crosstable[41].name, "Random");
    crosstable[41].pname = randbot;
    strcpy(crosstable[42].name, "Random");
    crosstable[42].pname = randbot;
    strcpy(crosstable[43].name, "Random");
    crosstable[43].pname = randbot;
    strcpy(crosstable[44].name, "Random");
    crosstable[44].pname = randbot;
    strcpy(crosstable[45].name, "Random");
    crosstable[45].pname = randbot;
    strcpy(crosstable[46].name, "Random");
    crosstable[46].pname = randbot;
    strcpy(crosstable[47].name, "Random");
    crosstable[47].pname = randbot;
    strcpy(crosstable[48].name, "Random");
    crosstable[48].pname = randbot;
    strcpy(crosstable[49].name, "Random");
    crosstable[49].pname = randbot;

    strcpy(crosstable[50].name, "Random");
    crosstable[50].pname = randbot;

    for (i = 0; i <= players; i++) {
        for (j = 0; j <= players; j++) {
            crosstable[i].result[j] = 0;
        }
    }
}

void Print_T_Results (Player_Table crosstable[players+1])
{
   int i, j;
     int wins;
  
    printf("\n Tournament results: \n\n");
      printf("  ");
     printf("%-*s ", nameleng, crosstable[0].name);
       for (j = 1; j <= players; j++) {
         printf(" %*d", fw, j);
        }
      printf(" total, wins\n\n");
        for (i = 1; i <= players; i++) {
          wins=0;
           printf(" %2d ", i);
            printf("%-*s ", nameleng, crosstable[i].name);
             for (j = 1; j <= players; j++) {
                      printf(" %*d", fw, crosstable[i].result[j]);
                         wins += (crosstable[i].result[j] > 0 ? 1 : 0 );
                       }
                   printf(" %*d ", fw+1, crosstable[i].result[0]);
                    printf(" %*d \n", fw+1, wins);
                   }
            printf("\n");
}


int Play_Match ( int(*player1)(), int(*player2)() )
{
    /* play a match between two RoShamBo players */

    int i, j, p1, p2, p1total, p2total, ties;
    int p1hist[trials+1], p2hist[trials+1];

    p1total = 0; p2total = 0; ties = 0;

    for (i = 0; i <= trials; i++) {
        p1hist[i] = 0; p2hist[i] = 0;
        my_history[i] = 0; opp_history[i] = 0;
    }

    for (i = 1; i <= trials; i++) {

        /* provide copies of history arrays for each player */
        memcpy(my_history, p1hist, sizeof(int)*(trials+1));
        memcpy(opp_history, p2hist, sizeof(int)*(trials+1));

        p1 = player1 ();              /* get player1 action */
        if ( (p1 < 0) || (p1 > 2) ) {
            printf("Error: return value out of range.\n");
            p1 = (p1 % 3 + 3) % 3;    /* note: -5 % 3 = -2, not 1 */
        }

        memcpy(opp_history, p1hist, sizeof(int)*(trials+1));
        memcpy(my_history, p2hist, sizeof(int)*(trials+1));

        p2 = player2 ();             /* get player2 action */
        if ( (p2 < 0) || (p2 > 2) ) {
            printf("Error: return value out of range.\n");
            p2 = (p2 % 3 + 3) % 3;
        }

        p1hist[0]++; p1hist[p1hist[0]] = p1;
        p2hist[0]++; p2hist[p2hist[0]] = p2;

        if (verbose1) { printf(" p1 = %d, p2 = %d", p1, p2); }
        if (p1 == p2) {
            ties++;
            if (verbose1) { printf(" tie!\n"); } }
        else if ( (p1-p2 == 1) || (p1-p2 == -2) ) {
            p1total++;
            if (verbose1) { printf(" p1 wins!\n"); } }
        else if ( (p2-p1 == 1) || (p2-p1 == -2) ) {
            p2total++;
            if (verbose1) { printf(" p2 wins!\n"); } }
        else printf("Error: should not be reached.\n");
    }
    if (verbose2) {
        printf(" Full history of p1 (%d trials):\n", p1hist[0]);
        for (j = 1; j <= trials; j++) {
            printf(" %d", p1hist[j]); }
        printf("\n");
        printf(" Full history of p2 (%d trials):\n", p1hist[0]);
        for (j = 1; j <= trials; j++) {
            printf(" %d", p2hist[j]); }
        printf("\n");
    }
    if (verbose3) {
        printf(" Match: %*d (%*d+ %*d- %*d=)\n", fw, p1total-p2total,
                            fw-1, p1total, fw-1, p2total, fw-1, ties);
    }

    return (p1total - p2total);
}

void Print_Sorted_Results (Player_Table crosstable[players+1])
{
    int i, j, max, swap;
    char nameswap[nameleng+1];

    Player_Table sorted[players+1];

    for (i = 0; i <= players; i++) {
        strcpy(sorted[i].name, crosstable[i].name);
        for (j = 0; j <= players; j++) {
            sorted[i].result[j] = crosstable[i].result[j];
        }
    }

    for (i = 1; i <= players; i++) {
        max = i;
        for (j = i; j <= players; j++) {
            if ( (sorted[j].result[0] > sorted[max].result[0]) ) {
                max = j;
            }
        }
        strcpy(nameswap, sorted[i].name);
        strcpy(sorted[i].name, sorted[max].name);
        strcpy(sorted[max].name, nameswap);
        for (j = 0; j <= players; j++) {
            swap = sorted[i].result[j];
            sorted[i].result[j] = sorted[max].result[j];
            sorted[max].result[j] = swap;
        }
        for (j = 1; j <= players; j++) {
            swap = sorted[j].result[i];
            sorted[j].result[i] = sorted[j].result[max];
            sorted[j].result[max] = swap;
        }
    }
    Print_T_Results (sorted);
}

void Play_Tournament (Player_Table crosstable[players+1])
{
    int i, j, score;

    for (i = 1; i <= players; i++) {
        for (j = i+1; j <= players; j++) {
            if (verbose3) { printf(" %-*s vs %-*s ", nameleng,
                crosstable[i].name, nameleng, crosstable[j].name); }
            score = Play_Match (crosstable[i].pname, crosstable[j].pname);
            crosstable[i].result[j] += score;
            crosstable[j].result[i] -= score;
        }
    }

    for (i = 1; i <= players; i++) {
        crosstable[i].result[0] = 0;
        for (j = 1; j <= players; j++) {
            crosstable[i].result[0] += crosstable[i].result[j];
        }
    }
    if (verbose2) { Print_T_Results (crosstable); }
}

int main() {

    int i;
    Player_Table crosstable[players+1];

    /* fixed or variable seed to the random() function */
    /* srandom(0); */
    srandom(time(0));

    Init_Player_Table (crosstable);

    printf(" Playing %d tournaments with %d trials per match...\n\n",
             tourneys, trials);

    for (i = 1; i <= tourneys; i++) {
        Play_Tournament (crosstable);
    }
    Print_Sorted_Results (crosstable);
    return(0);
}