/*  RoShamBo Tournament Test Suite         Darse Billings,  Oct 1999  */
/*                                                                    */
/*  This program may be used and modified freely, as long as the      */
/*  original author credit is maintained.  There are no guarantees    */
/*  of any kind.  Use at your own risk.                               */
/*                                                                    */
/*  The RoShamBo player algorithms contained in this test suite have  */
/*  been generously donated by their authors.  Entries for future     */
/*  RoShamBo competitions may be based on these ideas, but credit     */
/*  must be given to the original author.  Any entry deemed to be     */
/*  too similar to an uncredited existing program will be rejected    */
/*  without further consideration.                                    */
/*                                                                    */
/*  I am pleased to say that _all_ of the top contenders have been    */
/*  released (except for RoShamBot, which is proprietary, and not     */
/*  the author's to give).                                            */
/*                                                                    */
/*  Check the main web page for future versions of this program:      */
/*                                                                    */
/*        http://www.cs.ualberta.ca/~darse/rsbpc.html                 */

/*  Modified by Michael Gherrity                            Nov 1999  */
/*                                                                    */
/*  The tournament management sections were modified to support the   */
/*  Glicko rating system.  See:                                       */
/*                                                                    */
/*        http://www.gherrity.org/roshambo.html                       */


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

#include <assert.h>
#include <sys/time.h>
#include <unistd.h>
#include <float.h>

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

#define players   42         /* number of players in the tournament */
#define trials    1000       /* number of turns per match */

#define fw        4          /* field width for printed numbers */

/*  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 {
    int id;
    long order;              /* used for initial player order */
    double score;            /* score in the latest tournament */
    char name[nameleng+1];   /* descriptive name (max 18 chars) */
    int(*pname)();           /* function name for computer player */
    int result[players+1];   /* list of player's total points */
    int wins[players+1];     /* list of player's wins */
    int loses[players+1];    /* list of player's loses */
    int draws[players+1];    /* list of player's draws */
    int rating;              /* the glicko rating of this player */
    double RD;               /* the glicko rating deviation of this player */
    int lastGame;            /* last rated match */
} Player_Table;

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

/* from the Free Internet Chess Server */
#define initialRating 1720
#define initialRD 350.0

int        verboseLevel;
int        tourneys;      /* number of tournaments */
int        drawn;         /* +/- statistical draw range */
int        rounds;        /* number of rounds per tournament */

double     c, p, q;       /* some numbers used by the Glicko system */
int        gamesRated;


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); }
}


void Copy_Table (Player_Table *tableA, Player_Table *tableB)
{
  int     i;

  tableA->id = tableB->id;
  tableA->order = tableB->order;
  tableA->score = tableB->score;
  strcpy(tableA->name, tableB->name);
  tableA->pname = tableB->pname;
  for (i = 0; i <= players; i++)
  {
      tableA->result[i] = tableB->result[i];
      tableA->wins[i] = tableB->wins[i];
      tableA->loses[i] = tableB->loses[i];
      tableA->draws[i] = tableB->draws[i];
  }
  tableA->rating = tableB->rating;
  tableA->RD = tableB->RD;
  tableA->lastGame = tableB->lastGame;
}


void Swap_Tables (Player_Table crosstable[players+1], int indexA, int indexB)
{
  int              i, swap;
  Player_Table     temp;

  /* swap table entries */
  /**/
  Copy_Table(&temp, &crosstable[indexA]);
  Copy_Table(&crosstable[indexA], &crosstable[indexB]);
  Copy_Table(&crosstable[indexB], &temp);

  /* swap array entries for each player */
  /**/
  for (i = 1; i <= players; i++)
  {
      swap = crosstable[i].result[indexA];
      crosstable[i].result[indexA] = crosstable[i].result[indexB];
      crosstable[i].result[indexB] = swap;

      swap = crosstable[i].wins[indexA];
      crosstable[i].wins[indexA] = crosstable[i].wins[indexB];
      crosstable[i].wins[indexB] = swap;

      swap = crosstable[i].loses[indexA];
      crosstable[i].loses[indexA] = crosstable[i].loses[indexB];
      crosstable[i].loses[indexB] = swap;

      swap = crosstable[i].draws[indexA];
      crosstable[i].draws[indexA] = crosstable[i].draws[indexB];
      crosstable[i].draws[indexB] = swap;
  }

}


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

    /* a simple O(n^2) sort */
    /**/
    for (i = 1; i <= players; i++)
    {
	/* find the player with the highest rating */
	/**/
        max = i;
        for (j = i; j <= players; j++) {
            if ( (crosstable[j].rating > crosstable[max].rating) ) {
                max = j;
            }
        }

	/* swap table entries */
	/**/
	Swap_Tables(crosstable, i, max);

    }

}


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

    /* a simple O(n^2) sort */
    /**/
    for (i = 1; i <= players; i++)
    {
	/* find the player with the highest score */
	/**/
        max = i;
        for (j = i; j <= players; j++) {
            if ( (crosstable[j].score > crosstable[max].score) ) {
                max = j;
            }
        }

	/* swap table entries */
	/**/
	Swap_Tables(crosstable, i, max);

    }

}


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

    /* a simple O(n^2) sort */
    /**/
    for (i = 1; i <= players; i++)
    {
	/* find the player with the highest order */
	/**/
        max = i;
        for (j = i; j <= players; j++) {
            if ( (crosstable[j].order > crosstable[max].order) ) {
                max = j;
            }
        }

	/* swap table entries */
	/**/
	Swap_Tables(crosstable, i, max);
    }

}


void Init_Glicko ()
{
  /* The value of c is determined by how many games (n) must be played before
     the rating of a typical player (with RD = 50) becomes as uncertain as an
     unrated player (RD = 350).  The equation is
     c = (350^2 - 50^2) / n
     Let n = 100.
  */
  c = 1200.0;
  p = 3.0 * log(10.0) * log(10.0) / (M_PI * M_PI * 400.0 * 400.0);
  q = log(10.0) / 400.0;
}


void Init_Glicko_Ratings (Player_Table crosstable[players+1])
{
  int     i;

  for (i = 1; i <= players; i++)
  {
      crosstable[i].rating = initialRating;
      crosstable[i].RD = initialRD;
      crosstable[i].lastGame = gamesRated;
  }
}


double f (double rd)
{
  return(1.0 / sqrt(1.0 + p * rd * rd));
}


double reverseResult (double w)
{
  return(1.0 - w);
}


double round (double d)
{
  return(((int) (d + 0.5)) / 1.0);
}


/*
score is the number of trials player1 won over player2
*/
void New_Rating (Player_Table crosstable[players+1],
                 int indx1, int indx2, int score)
{
  Player_Table     *p1, *p2;
  double           E1, E2, K1, K2, temp1, temp2, f1, f2, r, w;

  p1 = &crosstable[indx1];
  p2 = &crosstable[indx2];

  if (score > drawn)
     w = 1.0;
  else if (score < -drawn)
     w = 0.0;
  else
     w = 0.5;

  /* Calculate new RD for both players.  They can't be greater than 350, or
     less than 30.
  */
  p1->RD = sqrt(p1->RD * p1->RD + c * (gamesRated - p1->lastGame));
  p2->RD = sqrt(p2->RD * p2->RD + c * (gamesRated - p2->lastGame));
  if (p1->RD > 350.0)
     p1->RD = 350.0;
  if (p2->RD > 350.0)
     p2->RD = 350.0;
  if (p1->RD < 30.0)
     p1->RD = 30.0;
  if (p2->RD < 30.0)
     p2->RD = 30.0;

  /* calculate the attenuating factor using the other player's RD
  */
  f1 = f(p2->RD);
  f2 = f(p1->RD);

  /* calculate E
  */
  E1 = 1.0 / (1.0 + pow(10.0, -(p1->rating - p2->rating) * f1 / 400.0));
  E2 = 1.0 / (1.0 + pow(10.0, -(p2->rating - p1->rating) * f2 / 400.0));

  /* calculate K
  */
  temp1 = 1.0 / p1->RD / p1->RD + q * q * f1 * f1 * E1 * (1.0 - E1);
  temp2 = 1.0 / p2->RD / p2->RD + q * q * f2 * f2 * E2 * (1.0 - E2);
  K1 = q * f1 / temp1;
  K2 = q * f2 / temp2;
  if (K1 < 16.0)
     K1 = 16.0;
  if (K2 < 16.0)
     K2 = 16.0;

  /* Calculate new ratings.  None can be below 100.  The difference between
     old and new has to be at least one, unless the game was drawn.
  */
  r = (int) round(p1->rating + K1 * (w - E1));
  if (((r - p1->rating) == 0) &&    
      (w != 0.5))
  {           
     if (w == 1.0)  
        r++; 
     else if (w == 0.0)
        r--; 
     else
     {
        fprintf(stderr, "w = %f!\n", w);
        exit(0);
     }
  }
  p1->rating = r;
  r = (int) round(p2->rating + K2 * (reverseResult(w) - E2));
  if (((r - p2->rating) == 0) &&    
      (w != 0.5))
  {           
     if (w == 1.0)  
        r++; 
     else if (w == 0.0)
        r--; 
     else
     {
        fprintf(stderr, "w = %f!\n", w);
        exit(0);
     }
  }
  p2->rating = r;
  if (p1->rating < 100)
     p1->rating = 100;
  if (p2->rating < 100)
     p2->rating = 100;

  /* calculate new RDs
  */
  p1->RD = 1.0 / sqrt(temp1);
  p2->RD = 1.0 / sqrt(temp2);

}


/*  Index of RoShamBo Player Algorithms:

 Rank  Dummy Bot         Open BoB  Leng      -max  level history use

  27 * Random (Optimal)   32  19     1       [-0]    L0  h0
   - * Good Ole Rock       -   -     1       [-1000] L0  h0
   - * R-P-S 20-20-60      -   -     1       [-1000] L0  h0
   - * Rotate R-P-S        -   -     1       [-1000] L0  h0
   - * Beat Last Move      -   -     1       [-1000] L1 oh1
   - * Always Switchin'    -   -     3       [-500]  L0 mh1
   - * Beat Frequent Pick  -   -    11       [-1000] L1 oh1
    
  21 * Pi                 31   9     5       [-1000] L0  h0
  49 * Switch A Lot       45  49     3       [-320]  L0 mh1
  40 * Flat               40  44    16       [-420]  L0 mh1
   - * Anti-Flat           -   -    16       [-1000] L1 oh1
  32 * Foxtrot            36  22     4       [-500]  L0 mh1
  16 * De Bruijn          28   3     5       [-500]  L0  h0
  46 * Text               41  52     5       [-ukn]  L0  h0
  29 * Anti-rotn          22  32    40       [-40]   L1 oh2 +fail-safe
  45 * Copy-drift         39  50     9       [-500]  L0 oh1
  48 * Add-react          43  51     9       [-800]  L0 bh1 +gear-shifting
  42 * Add-drift          38  47     9       [-500]  L0 bh1

 Rank Entrant           Open BoB  Leng Nat  Author

   1  Iocaine Powder      1   1   134  USA  Dan Egnor
   2  Phasenbott          2   2    99  USA  Jakob Mandelson
   3  MegaHAL             3   7   149  Aus  Jason Hutchens
   4  RussRocker4         4   8   120  USA  Russ Williams
   5  Biopic              6   6    80  Can  Jonathan Schaeffer
   7  Simple Modeller     7  13   135   UK  Don Beal
  14  Simple Predictor    9  21    63   UK  Don Beal
   8  Robertot            8  12    53  Ger  Andreas Junghanns
  10  Boom               10  18   208  Net  Jack van Rijswijk
  11  Shofar             17  11    98  USA  Rudi Cilibrasi
  13  ACT-R Lag2         15  14    20  USA  Dan Bothell, C Lebiere, R West
  15  Majikthise         25   5    62  Can  Markian Hlynka
  18  Vroomfondel        24  10    62  Can  Markian Hlynka
  17  Granite            11  23    97  Can  Aaron Davidson
  19  Marble             12  24    95  Can  Aaron Davidson
  22  ZQ Bot             16  26    99  Can  Neil Burch
  24  Sweet Rocky        18  30    36  Mex  Lourdes Pena
  25  Piedra             19  31    23  Mex  Lourdes Pena
  28  Mixed Strategy     23  29    53   UK  Thad Frogley
  38  Multi-strategy     42  38    86  Can  Mark James
  44  Inocencio          48  37    95   UK  Rafael Morales
  50  Peterbot           53  42    43  USA  Peter Baylie
  12  Bugbrain           14  15    51  Can  Sunir Shah
  52  Knucklehead        49  48    30  Can  Sunir Shah

  --  Psychic Friends Network      47  USA  Michael Schatz, F Hill, TJ Walls
      (Unofficial Super-Modified Class, i.e. it cheats)
*/

/*  Dummy Bots  (written by Darse Billings)  */

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

int rockbot ()  /* Good Ole Rock */
{
    /* "Good ole rock.  Nuthin' beats rock." */
    return(rock);
}

int r226bot ()  /* R-P-S 20-20-60 */
{
    /* play 20% rock, 20% paper, 60% scissors */
    return( biased_roshambo(0.2, 0.2));
}

int rotatebot ()  /* Rotate R-P-S */
{
    /* rotate choice each turn r -> p -> s */
    return( my_history[0] % 3);
}

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

int switchbot ()  /* Always Switchin' */
{
    /* 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) );
}

int freqbot ()  /* Beat Frequent Pick */
{
    /* beat the opponent's most frequent choice */

    int i, rcount, pcount, scount;

    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++; }
    }
    if ( (rcount > pcount) && (rcount > scount) ) { return(paper); }
    else if ( pcount > scount ) { return(scissors); }
    else { return(rock); }
}

int freqbot2 ()  /* Beat Frequent Pick (again) */
{
    /* maintain stats with static variables to avoid re-scanning
       the history array  (based on code by Don Beal) */

    static int rcount, pcount, scount;
    int opp_last;

    if( opp_history[0] == 0 ) {
        rcount = 0;  pcount = 0;  scount = 0;  }
    else {
      opp_last = opp_history[opp_history[0]];
      if ( opp_last == rock)          { rcount++; }
      else if ( opp_last == paper)    { pcount++; }
      else /* opp_last == scissors */ { scount++; }
    }
    if ( (rcount > pcount) && (rcount > scount) ) { return(paper); }
    else if ( pcount > scount ) { return(scissors); }
    else { return(rock); }
}

int pibot ()  /* Pi bot */
{
    /* base each decision on a digit of pi (skipping 0s) */

    static int index;
    static int pi_table [1200] =  /* skipping 0s leaves 1088 digits */
{3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3,3,8,3,2,7,9,5,0,2,8,8,4,1,9,7,
 1,6,9,3,9,9,3,7,5,1,0,5,8,2,0,9,7,4,9,4,4,5,9,2,3,0,7,8,1,6,4,0,6,2,8,6,2,0,8,9,
 9,8,6,2,8,0,3,4,8,2,5,3,4,2,1,1,7,0,6,7,9,8,2,1,4,8,0,8,6,5,1,3,2,8,2,3,0,6,6,4,
 7,0,9,3,8,4,4,6,0,9,5,5,0,5,8,2,2,3,1,7,2,5,3,5,9,4,0,8,1,2,8,4,8,1,1,1,7,4,5,0,
 2,8,4,1,0,2,7,0,1,9,3,8,5,2,1,1,0,5,5,5,9,6,4,4,6,2,2,9,4,8,9,5,4,9,3,0,3,8,1,9,
 6,4,4,2,8,8,1,0,9,7,5,6,6,5,9,3,3,4,4,6,1,2,8,4,7,5,6,4,8,2,3,3,7,8,6,7,8,3,1,6,
 5,2,7,1,2,0,1,9,0,9,1,4,5,6,4,8,5,6,6,9,2,3,4,6,0,3,4,8,6,1,0,4,5,4,3,2,6,6,4,8,
 2,1,3,3,9,3,6,0,7,2,6,0,2,4,9,1,4,1,2,7,3,7,2,4,5,8,7,0,0,6,6,0,6,3,1,5,5,8,8,1,
 7,4,8,8,1,5,2,0,9,2,0,9,6,2,8,2,9,2,5,4,0,9,1,7,1,5,3,6,4,3,6,7,8,9,2,5,9,0,3,6,
 0,0,1,1,3,3,0,5,3,0,5,4,8,8,2,0,4,6,6,5,2,1,3,8,4,1,4,6,9,5,1,9,4,1,5,1,1,6,0,9,
 4,3,3,0,5,7,2,7,0,3,6,5,7,5,9,5,9,1,9,5,3,0,9,2,1,8,6,1,1,7,3,8,1,9,3,2,6,1,1,7,
 9,3,1,0,5,1,1,8,5,4,8,0,7,4,4,6,2,3,7,9,9,6,2,7,4,9,5,6,7,3,5,1,8,8,5,7,5,2,7,2,
 4,8,9,1,2,2,7,9,3,8,1,8,3,0,1,1,9,4,9,1,2,9,8,3,3,6,7,3,3,6,2,4,4,0,6,5,6,6,4,3,
 0,8,6,0,2,1,3,9,4,9,4,6,3,9,5,2,2,4,7,3,7,1,9,0,7,0,2,1,7,9,8,6,0,9,4,3,7,0,2,7,
 7,0,5,3,9,2,1,7,1,7,6,2,9,3,1,7,6,7,5,2,3,8,4,6,7,4,8,1,8,4,6,7,6,6,9,4,0,5,1,3,
 2,0,0,0,5,6,8,1,2,7,1,4,5,2,6,3,5,6,0,8,2,7,7,8,5,7,7,1,3,4,2,7,5,7,7,8,9,6,0,9,
 1,7,3,6,3,7,1,7,8,7,2,1,4,6,8,4,4,0,9,0,1,2,2,4,9,5,3,4,3,0,1,4,6,5,4,9,5,8,5,3,
 7,1,0,5,0,7,9,2,2,7,9,6,8,9,2,5,8,9,2,3,5,4,2,0,1,9,9,5,6,1,1,2,1,2,9,0,2,1,9,6,
 0,8,6,4,0,3,4,4,1,8,1,5,9,8,1,3,6,2,9,7,7,4,7,7,1,3,0,9,9,6,0,5,1,8,7,0,7,2,1,1,
 3,4,9,9,9,9,9,9,8,3,7,2,9,7,8,0,4,9,9,5,1,0,5,9,7,3,1,7,3,2,8,1,6,0,9,6,3,1,8,5,
 9,5,0,2,4,4,5,9,4,5,5,3,4,6,9,0,8,3,0,2,6,4,2,5,2,2,3,0,8,2,5,3,3,4,4,6,8,5,0,3,
 5,2,6,1,9,3,1,1,8,8,1,7,1,0,1,0,0,0,3,1,3,7,8,3,8,7,5,2,8,8,6,5,8,7,5,3,3,2,0,8,
 3,8,1,4,2,0,6,1,7,1,7,7,6,6,9,1,4,7,3,0,3,5,9,8,2,5,3,4,9,0,4,2,8,7,5,5,4,6,8,7,
 3,1,1,5,9,5,6,2,8,6,3,8,8,2,3,5,3,7,8,7,5,9,3,7,5,1,9,5,7,7,8,1,8,5,7,7,8,0,5,3,
 2,1,7,1,2,2,6,8,0,6,6,1,3,0,0,1,9,2,7,8,7,6,6,1,1,1,9,5,9,0,9,2,1,6,4,2,0,1,9,8,
 9,3,8,0,9,5,2,5,7,2,0,1,0,6,5,4,8,5,8,6,3,2,7,8,8,6,5,9,3,6,1,5,3,3,8,1,8,2,7,9,
 6,8,2,3,0,3,0,1,9,5,2,0,3,5,3,0,1,8,5,2,9,6,8,9,9,5,7,7,3,6,2,2,5,9,9,4,1,3,8,9,
 1,2,4,9,7,2,1,7,7,5,2,8,3,4,7,9,1,3,1,5,1,5,5,7,4,8,5,7,2,4,2,4,5,4,1,5,0,6,9,5,
 9,5,0,8,2,9,5,3,3,1,1,6,8,6,1,7,2,7,8,5,5,8,8,9,0,7,5,0,9,8,3,8,1,7,5,4,6,3,7,4,
 6,4,9,3,9,3,1,9,2,5,5,0,6,0,4,0,0,9,2,7,7,0,1,6,7,1,1,3,9,0,0,9,8,4,8,8,2,4,0,1};

    if (my_history[0] == 0) { index = 0; }
    else { index++; }
    while (pi_table[index] == 0) { index++; }
    if (index >= 1200) { index -= 1200; };
    return(pi_table[index] % 3);
}

int switchalot ()  /* Switch A Lot */
{
    /* seldom repeat the previous pick */
    if ( my_history[my_history[0]] == rock ) {
        return( biased_roshambo(0.12, 0.44) ); }
    else if ( my_history[my_history[0]] == paper ) {
        return( biased_roshambo(0.44, 0.12) ); }
    else return( biased_roshambo(0.44, 0.44) );
}

int flatbot3 ()  /* Flat bot */
{
    /* flat distribution, 20% chance of most frequent actions */
    static int rc, pc, sc;
    int mylm, choice;

    if ( my_history[0] == 0 ) {
        rc = 0; pc = 0; sc = 0; }
    else {
        mylm = my_history[my_history[0]];
        if (mylm == rock)            { rc++; }
        else if (mylm == paper)      { pc++; }
        else /* mylm == scissors */  { sc++; }
    }
    if ((rc < pc) && (rc < sc)) {
        choice = biased_roshambo(0.8, 0.1); }
    if ((pc < rc) && (pc < sc)) {
        choice = biased_roshambo(0.1, 0.8); }
    if ((sc < rc) && (sc < pc)) {
        choice = biased_roshambo(0.1, 0.1); }
    if ((rc == pc) && (rc < sc)) {
        choice = biased_roshambo(0.45, 0.45); }
    if ((rc == sc) && (rc < pc)) {
        choice = biased_roshambo(0.45, 0.1); }
    if ((pc == sc) && (pc < rc)) {
        choice = biased_roshambo(0.1, 0.45); }
    if ((rc == pc) && (rc == sc)) {
        choice = random() % 3; }
    /* printf("[%d %d %d: %d]", rc, pc, sc, choice); */
    return(choice);
}

int antiflatbot ()  /* Anti-Flat bot */
{
    /* maximally exploit flat distribution */

    static int rc, pc, sc;
    int opplm, choice;

    if ( opp_history[0] == 0 ) {
        rc = 0; pc = 0; sc = 0; }
    else {
        opplm = opp_history[opp_history[0]];
        if (opplm == rock)           { rc++; }
        else if (opplm == paper)      { pc++; }
        else /* opplm == scissors */  { sc++; }
    }
    if ((rc < pc) && (rc < sc)) {
        choice = paper; }
    if ((pc < rc) && (pc < sc)) {
        choice = scissors; }
    if ((sc < rc) && (sc < pc)) {
        choice = rock; }
    if ((rc == pc) && (rc < sc)) {
        choice = paper; }
    if ((rc == sc) && (rc < pc)) {
        choice = rock; }
    if ((pc == sc) && (pc < rc)) {
        choice = scissors; }
    if ((rc == pc) && (rc == sc)) {
        choice = random() % 3; }
    /* printf("[%d %d %d: %d]", rc, pc, sc, choice); */
    return(choice);
}

int foxtrotbot ()  /* Foxtrot bot */
{
    /* set pattern: rand prev+2 rand prev+1 rand prev+0, repeat */

    int turn;

    turn = my_history[0] + 1;

    if ( turn % 2 ) {
        return( random() % 3 ); }
    else {
        return( (my_history[turn-1] + turn) % 3 ); }
}

int debruijn81 ()  /* De Bruijn string */
{
    /* several De Bruijn strings of length 81 concatentated */

    static int index;
    static int db_table [1000] = /* De Bruijn sequence: */
{1,0,2,0,0,2,0,2,0,1,1,0,0,2,2,1,0,0,1,1,2,2,0,0,1,2,1,0,2,2,2,2,0,1,2,0,2,2,0,2,
 1,1,2,1,1,0,1,1,1,2,0,0,0,0,2,1,0,1,0,1,2,2,1,2,0,1,0,0,0,1,0,2,1,2,1,2,2,2,1,1,
 1,0,0,1,1,1,1,0,1,0,2,2,2,0,0,2,2,0,2,0,1,0,1,1,0,2,1,1,2,2,2,2,1,1,1,2,0,1,2,2,
 1,2,0,0,0,1,0,0,0,0,2,0,2,2,1,0,0,1,2,1,2,2,0,1,1,2,1,1,0,0,2,1,0,1,2,0,2,1,2,1,
 0,2,1,1,2,0,0,1,0,1,2,2,0,1,0,0,2,0,1,2,0,1,1,2,1,1,1,1,0,2,0,2,1,0,2,2,0,2,2,2,
 2,0,0,0,1,2,1,2,2,2,1,1,0,1,1,0,0,0,0,2,1,2,0,2,0,0,2,2,1,0,0,1,1,1,2,2,1,2,1,0,
 1,0,2,1,0,1,0,2,0,2,0,0,1,2,2,2,0,2,1,0,0,1,1,1,2,2,1,1,0,2,2,0,0,0,2,2,2,2,1,2,
 2,0,1,2,0,0,2,0,1,1,2,1,2,1,1,1,1,0,0,2,1,2,0,1,0,0,0,0,1,0,1,1,0,1,2,1,0,2,1,1,
 2,0,2,2,2,2,1,1,1,1,0,0,2,0,2,2,2,1,2,1,0,2,1,0,0,0,0,2,1,1,2,2,1,0,1,0,0,1,1,1,
 2,1,1,0,1,2,2,2,2,0,0,1,2,0,2,0,1,2,1,2,0,1,0,1,1,2,0,0,0,1,0,2,2,0,2,1,2,2,0,1,
 1,0,2,0,0,0,0,0,0,1,0,0,0,2,1,1,0,0,1,1,1,1,0,2,0,2,1,2,0,2,2,1,2,2,2,1,1,1,2,1,
 2,1,0,0,2,0,1,1,0,1,0,2,1,0,2,2,2,2,0,2,0,0,2,2,0,0,1,2,2,1,0,1,1,2,0,1,2,1,1,2,
 2,0,1,0,1,2,2,2,0,2,0,0,2,0,2,1,2,2,2,2,0,0,0,0,2,2,1,0,0,0,1,2,0,1,2,1,2,0,0,1,
 0,2,0,1,0,0,2,1,0,1,2,2,1,1,2,0,2,2,2,1,2,1,0,2,2,0,1,1,0,2,1,1,0,0,1,1,2,1,1,1,
 1,0,1,0,1,1,1,1,1,1,2,1,0,0,0,0,1,1,0,2,1,2,1,2,2,2,0,0,1,2,0,1,0,1,2,1,1,2,2,0,
 2,0,2,1,1,0,0,1,0,2,0,0,2,0,1,1,2,0,2,2,1,1,1,1,0,1,0,0,2,2,2,2,1,2,0,0,0,2,1,0,
 2,2,0,1,2,2,1,0,2,1,0,1,0,1,1,1,1,2,1,1,0,1,2,1,2,2,2,2,1,2,0,0,0,1,1,2,0,2,0,2,
 1,0,0,0,0,2,0,0,1,0,0,2,2,2,0,0,2,1,1,2,2,0,1,2,0,1,1,0,0,1,2,2,1,1,1,0,2,0,1,0,
 2,2,0,2,2,1,0,2,1,2,2,2,1,0,1,0,2,2,1,2,0,2,1,0,2,0,0,0,0,1,2,1,0,0,2,0,2,2,0,1,
 0,1,1,2,1,1,0,0,1,0,0,0,2,1,1,2,0,0,2,2,2,2,0,0,1,1,1,0,2,1,2,1,2,2,1,1,1,1,2,2,
 0,2,0,1,2,0,1,1,0,1,1,0,0,1,1,0,1,2,0,1,2,1,2,2,1,0,0,2,0,2,1,0,1,0,2,2,0,1,1,2,
 1,0,2,0,0,1,0,1,1,1,2,2,2,2,1,2,0,2,2,1,1,2,0,0,2,1,2,1,1,1,1,0,2,1,1,0,0,0,0,2,
 2,2,0,0,0,1,2,2,0,2,0,2,2,0,2,1,1,2,0,2,0,0,1,1,1,0,0,1,2,1,1,0,1,1,0,2,2,0,0,2,
 2,1,1,1,1,2,1,2,1,0,2,0,2,2,2,2,1,2,0,0,0,1,0,0,2,1,0,0,0,0,2,0,1,1,2,2,2,0,1,2,
 2,1,0,1,0,1,2,0,1,0,2,1,0,2,0,2,1,1,1,0,0,2,2,2,0,1,1,2,2,1,2,0,0,0,1,0,1,2,1,0};

    if (my_history[0] == 0) { index = 0; }
    else { index = (index + 1) % 1001; }
    return(db_table[index]);
}

int textbot ()  /* Text bot */
{
    /* English text (rsbpc post) converted to r-p-s */
    /* contains:  281 0's, 267 1's, 452 2's (heavy bias) */

    static int index;
    static int db_table [1000] = 
{2,0,2,2,2,1,0,0,1,2,2,1,2,2,2,0,2,1,2,0,0,2,1,0,2,1,0,2,2,1,1,0,0,2,2,0,0,1,0,1,
 1,1,0,2,1,2,1,0,1,1,2,2,0,2,0,0,2,2,2,0,1,1,1,0,1,1,2,0,0,0,2,2,2,1,2,1,0,0,1,0,
 1,1,2,2,0,2,1,0,1,1,2,1,0,0,2,0,2,1,1,2,0,0,2,0,0,1,1,0,0,1,2,2,1,2,1,2,2,2,2,2,
 0,2,0,2,2,2,0,2,1,0,1,1,2,0,2,2,1,2,2,0,1,2,2,2,0,0,1,1,2,2,0,2,0,0,2,2,1,1,1,0,
 2,1,2,2,0,2,2,2,0,2,1,0,0,1,0,1,1,1,1,2,2,2,0,0,1,0,1,2,1,2,0,0,2,2,1,1,2,2,0,0,
 2,2,2,1,2,1,2,1,1,1,2,2,2,0,2,1,0,2,2,1,0,1,2,2,2,0,2,1,1,2,2,1,0,2,2,1,1,0,0,2,
 1,1,0,1,0,2,2,2,0,2,2,2,1,1,2,1,0,0,2,0,2,1,1,2,0,0,2,0,0,1,1,0,0,1,2,2,0,1,2,1,
 2,1,0,1,1,0,2,2,1,1,1,2,2,2,2,0,2,2,2,2,2,2,2,2,1,2,2,1,2,0,1,2,2,1,1,2,0,1,2,2,
 2,2,0,0,1,2,2,2,0,0,2,2,2,0,0,1,1,0,0,0,1,2,2,1,2,2,2,2,2,2,1,0,1,1,0,2,1,2,1,1,
 1,0,2,1,2,2,0,1,0,0,0,2,0,2,2,0,1,1,0,2,2,2,2,1,2,1,1,0,0,2,2,1,1,2,2,0,1,1,2,1,
 1,2,1,2,2,0,2,2,2,1,1,1,2,2,0,1,2,1,0,1,1,2,1,2,2,2,2,2,2,2,2,2,2,2,0,2,1,0,1,1,
 2,0,1,1,2,2,1,2,2,2,1,0,2,2,2,0,0,2,2,2,2,2,2,2,1,0,1,1,2,0,1,2,1,0,1,0,0,2,1,2,
 2,0,0,1,0,1,2,0,2,0,0,1,2,2,0,2,2,2,0,0,2,1,0,0,0,2,1,2,2,1,1,1,1,2,0,1,2,2,0,0,
 2,1,1,0,0,1,1,0,0,1,1,1,2,2,1,0,2,2,2,2,1,2,0,2,0,0,1,2,2,2,2,2,2,1,1,1,2,2,0,2,
 2,1,2,2,2,2,2,2,0,2,1,0,0,2,2,0,1,2,1,2,2,0,2,2,2,0,2,2,2,0,2,0,1,2,2,1,1,1,2,0,
 2,0,0,1,2,0,1,2,0,0,0,2,2,2,1,0,0,1,1,0,0,1,2,0,0,2,1,2,1,1,1,2,0,2,2,0,0,2,0,0,
 0,2,2,0,0,0,1,2,2,1,2,1,0,0,1,1,0,0,1,1,2,2,2,2,1,1,2,0,2,2,0,0,2,1,0,1,2,1,2,0,
 0,2,1,2,1,2,0,0,2,1,2,0,0,2,2,0,0,2,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,2,1,0,1,1,
 2,0,1,1,2,2,0,2,2,2,1,1,1,2,2,0,1,2,2,0,0,1,0,1,0,2,0,0,0,1,2,1,2,1,1,1,2,0,2,2,
 2,0,0,2,2,0,0,2,1,0,0,2,2,2,0,0,2,1,0,2,2,1,2,2,0,2,2,2,0,1,2,0,1,1,0,2,1,0,0,2,
 1,2,1,2,0,1,2,2,1,1,2,0,1,2,2,0,2,0,2,0,0,1,2,2,1,2,2,1,0,2,0,0,2,2,0,2,0,0,0,0,
 1,0,1,2,1,2,2,0,1,2,1,0,1,2,1,0,2,2,0,2,2,0,0,1,2,1,0,0,2,1,2,0,0,0,2,1,2,0,0,2,
 2,1,0,2,2,1,2,2,0,2,0,1,2,2,0,0,0,2,2,2,1,0,0,2,2,1,2,2,0,2,1,2,0,2,1,2,2,2,0,2,
 1,0,0,2,2,0,2,2,2,2,2,2,0,0,2,1,2,0,0,2,2,2,0,2,1,1,0,1,0,2,1,1,2,0,0,2,2,0,2,2,
 1,2,0,0,2,1,2,1,0,0,2,2,0,2,2,2,2,1,2,0,2,2,2,2,2,2,0,1,1,0,2,2,2,2,2,0,1,1,2,2};

    if (my_history[0] == 0) { index = 0; }
    else { index = (index + 1) % 1001; }
    return(db_table[index]);
}

int antirotnbot ()  /* Anti-rotn bot */
{
    /* observes rotations in opponent's sequence,
       exploits max or min, whichever difference is greater */

    /* crude implementation, could be simplified */

    static int no, up, dn, score;
    int mv, diff, diff2, small, med, large;

    mv = opp_history[0];
    if (mv == 0) {
        no = 0; up = 0; dn = 0; score = 0;
    }
    else {
        diff = (my_history[mv] - opp_history[mv] + 3) % 3;
        if ( diff == 1 ) { score++; }
        if ( diff == 2 ) { score--; }
        if (mv > 1) {
            diff = (opp_history[mv] - opp_history[mv-1] + 3) % 3;
            if (diff == 0) { no++; }
            if (diff == 1) { up++; }
            if (diff == 2) { dn++; }
        }
    }

    /* fail-safe at 4% of match length */
    if ( score < -trials/25 ) {
        return(random() % 3); }

    if ((no == up) && (no == dn)) {
        return(random() % 3); }

    /* sort */
    if ((no <= up) && (no <= dn)) {
        small = no;
        if (up <= dn) { med = up; large = dn; }
        else { med = dn; large = up; }
    }
    else if (up <= dn) {
        small = up;
        if (no <= dn) { med = no; large = dn; }
        else { med = dn; large = no; }
    }
    else {
        small = dn;
        if (no <= up) { med = no; large = up; }
        else { med = up; large = no; }
    }

    diff = med - small;    diff2 = large - med;

    if (diff < diff2) { /* clear maximum */
        if ((no > up) && (no > dn)) {
            return((opp_history[opp_history[0]] + 1) % 3); }
        if ((up > no) && (up > dn)) {
            return((opp_history[opp_history[0]] + 2) % 3); }
        if ((dn > no) && (dn > up)) {
            return(opp_history[opp_history[0]]); }
    }
    else if (diff > diff2) { /* clear minimum */
        if ((dn < up) && (dn < no)) {
            return((opp_history[opp_history[0]] + 1) % 3); }
        if ((up < dn) && (up < no)) {
            return(opp_history[opp_history[0]]); }
        if ((no < dn) && (no < up)) {
            return((opp_history[opp_history[0]] + 2) % 3); }
    }
    else if (diff == diff2) {
        if ((no > up) && (up > dn)) {
            return((opp_history[opp_history[0]] + 1) % 3); }
        if ((dn > up) && (up > no)) {
            if (flip_biased_coin(0.5)) {
                return(opp_history[opp_history[0]]); }
            else { return((opp_history[opp_history[0]] + 2) % 3); }
        }
        if ((dn > no) && (no > up)) {
            return(opp_history[opp_history[0]]); }
        if ((up > no) && (no > dn)) {
            if (flip_biased_coin(0.5)) {
                return((opp_history[opp_history[0]] + 1) % 3); }
            else { return((opp_history[opp_history[0]] + 2) % 3); }
        }
        if ((up > dn) && (dn > no)) {
            return((opp_history[opp_history[0]] + 2) % 3); }
        if ((no > dn) && (dn > up)) {
            if (flip_biased_coin(0.5)) {
                return(opp_history[opp_history[0]]); }
            else { return((opp_history[opp_history[0]] + 1) % 3); }
        }
    }
    printf("Error in antirotnbot decision tree!\n");
    return(0);
}

int driftbot ()  /* Copy-drift bot */
{
    /* bias decision by opponent's last move, but drift over time */
    /* max -EV = -0.50 ppt */

    static int gear;
    int mv, throw;

    mv = my_history[0];
    if (mv == 0) { 
        gear = 0;
        throw = random() % 3; }
    else {
        if (flip_biased_coin(0.5)) {    
            throw = opp_history[mv]; }
        else { throw = random() % 3; }
        if ( mv % 111 == 0 ) {
            gear += 2; }
    }
    return((throw + gear) % 3);
}

int addshiftbot3 ()  /* Add-react bot */
{
    /* base on sum of previous pair (my & opp), shift if losing */
    /* deterministic 80% of the time, thus max -EV = -0.800 ppt */

    static int gear, recent, score;
    int mv, diff;

    mv = my_history[0];
    if (mv == 0) {
        gear = 0; recent = 0; score = 0;
        return( random() % 3 );
    }
    else {
        diff = (my_history[mv] - opp_history[mv] + 3) % 3;
        if ( diff == 1 ) { score++; }
        if ( diff == 2 ) { score--; }
        recent++;
    }

    if (((recent <= 20) && (score <= -3)) ||
        ((recent >  20) && (score <= -recent/10))) {
        /* printf("switching gears at turn %d (%d / %d)\n", mv, score, recent); */
        gear += 2;
        recent = 0;
        score = 0;
    }
    if ( flip_biased_coin(0.2) ) {
        return( random() % 3 ); }
    else {
        return((my_history[mv] + opp_history[mv] + gear) % 3);
    }
}

int adddriftbot2 ()  /* Add-drift bot */
{
    /* base on sum of previous pair (my & opp), drift over time */
    /* deterministic 50% of the time, thus max -EV = -0.500 ppt */

    static int gear;
    int mv;

    mv = my_history[0];
    if (mv == 0) {
        gear = 0;
        return( random() % 3 );
    }
    else if ( mv % 200 == 0 ) { gear += 2; }

    if ( flip_biased_coin(0.5) ) {
        return( random() % 3 ); }
    else {
        return((my_history[mv] + opp_history[mv] + gear) % 3);
    }
}
/**********************************************************************/


/*  Entrant:  Iocaine Powder (1)   Dan Egnor (USA)

    Winner of the First International RoShamBo Programming Competition

 Iocaine Powder             (from: http://ofb.net/~egnor/iocaine.html)

 They were both poisoned.
 
 Iocaine Powder is a heuristically designed compilation of strategies and
 meta-strategies, entered in Darse Billings' excellent First International
 RoShamBo Programming Competition. You may use its source code freely; I
 ask only that you give me credit for any derived works. I attempt here to
 explain how it works.
 
 Meta-Strategy
 
 RoShamBo strategies attempt to predict what the opponent will do. Given a
 successful prediction, it is easy to defeat the opponent (if you know they
 will play rock, you play paper). However, straightforward prediction will
 often fail; the opponent may not be vulnerable to prediction, or worse, they
 might have anticipated your predictive logic and played accordingly. Iocaine
 Powder's meta-strategy expands any predictive algorithm P into six possible
 strategies:
 
 P.0: naive application
      Assume the opponent is vulnerable to prediction by P; predict their
      next move, and play to beat it. If P predicts your opponent will play
      rock, play paper to cover rock. This is the obvious application of P.
 
 P.1: defeat second-guessing
      Assume the opponent thinks you will use P.0. If P predicts rock, P.0
      would play paper to cover rock, but the opponent could anticipate this
      move and play scissors to cut paper. Instead, you play rock to dull
      scissors.
 
 P.2: defeat triple-guessing
      Assume the opponent thinks you will use P.1. Your opponent thinks you
      will play rock to dull the scissors they would have played to cut the
      paper you would have played to cover the rock P would have predicted,
      so they will play paper to cover your rock. But you one-up them,
      playing scissors to cut their paper.
 
      At this point, you should be getting weary of the endless chain. "We
      could second-guess each other forever," you say. But no; because of the
      nature of RoShamBo, P.3 recommends you play paper -- just like P.0! So
      we're only left with these three strategies, each of which will suggest
      a different alternative. (This may not seem useful to you, but have
      patience.)
 
 P'.0: second-guess the opponent
      This strategy assumes the opponent uses P themselves against you.
      Modify P (if necessary) to exchange the position of you and your
      opponent. If P' predicts that you will play rock, you would expect
      your opponent to play paper, but instead you play scissors.
 
 P'.1, P'.2: variations on a theme
      As with P.1 and P.2, these represent "rotations" of the basic idea,
      designed to counteract your opponent's second-guessing.
 
 So, for even a single predictive algorithm P, we now have six possible
 strategies. One of them may be correct -- but that's little more useful
 than saying "one of rock, scissors, or paper will be the correct next
 move". We need a meta-strategy to decide between these six strategies.
 
 Iocaine Powder's basic meta-strategy is simple: Use past performance to
 judge future results.
 
 The basic assumption made by this meta-strategy is that an opponent will not
 quickly vary their strategy. Either they will play some predictive algorithm
 P, or they will play to defeat it, or use some level of second-guessing; but
 whatever they do, they will do it consistently. To take advantage of this
 (assumed) predictability, at every round Iocaine Powder measures how well
 each of the strategies under consideration (six for every predictive
 algorithm!)  would have done, if it had played them. It assigns each one a
 score, using the standard scoring scheme used by the tournament: +1 point if
 the strategy would have won the hand, -1 if it would have lost, 0 if it
 would have drawn.
 
 Then, to actually choose a move, Iocaine Powder simply picks the strategy
 variant with the highest score to date.
 
 The end result is that, for any given predictive technique, we will beat any
 contestant that would be beaten by the technique, any contestant using the
 technique directly, and any contestant designed to defeat the technique
 directly.
 
 Strategies
 
 All the meta-strategy in the world isn't useful without some predictive
 algorithms. Iocaine Powder uses three predictors:
 
 Random guess
      This "predictor" simply chooses a move at random. I include this
      algorithm as a hedge; if someone is actually able to predict and defeat
      Iocaine Powder with any regularity, before long the random predictor
      will be ranked with the highest score (since nobody can defeat
      random!). At that point, the meta-strategy will ensure that the program
      "cuts its losses" and starts playing randomly to avoid a devastating
      loss. (Thanks to Jesse Rosenstock for discovering the necessity of such
      a hedge.)
 
 Frequency analysis
      The frequency analyzer looks at the opponent's history, finds the move
      they have made most frequently in the past, and predicts that they will
      choose it. While this scores a resounding defeat again "Good Ole Rock",
      it isn't very useful against more sophisticated opponents (which are
      usually quite symmetrical). I include it mostly to defeat other
      competitors which use it as a predictive algorithm.
 
 History matching
      This is easily the strongest predictor in Iocaine Powder's arsenal, and
      variants of this technique are widely used in other strong entries. The
      version in Iocaine Powder looks for a sequence in the past matching the
      last few moves. For example, if in the last three moves, we played
      paper against rock, scissors against scissors, and scissors against
      rock, the predictor will look for times in the past when the same three
      moves occurred. (In fact, it looks for the longest match to recent
      history; a repeat of the last 30 moves is considered better than just
      the last 3 moves.) Once such a repeat is located, the history matcher
      examines the move our opponent made afterwards, and assumes they will
      make it again. (Thanks to Rudi Cilibrasi for introducing me to this
      algorithm, long ago.)
 
      Once history is established, this predictor easily defeats many weak
      contestants. Perhaps more importantly, the application of meta-strategy
      allows Iocaine to outguess other strong opponents.
 
 Details
 
 If you look at Iocaine Powder's source code, you'll discover additional
 features which I haven't treated in this simplified explanation. For
 example, the strategy arsenal includes several variations of frequency
 analysis and history matching, each of which looks at a different amount of
 history; in some cases, prediction using the last 5 moves is superior to
 prediction using the last 500. We run each algorithm with history sizes of
 1000, 100, 10, 5, 2, and 1, and use the general meta-strategy to figure out
 which one does best.
 
 In fact, Iocaine even varies the horizon of its meta-strategy analyzer!
 Strategies are compared over the last 1000, 100, 10, 5, 2, and 1 moves, and
 a meta-meta-strategy decides which meta-strategy to use (based on which
 picker performed best over the total history of the game). This was designed
 to defeat contestants which switch strategy, and to outfox variants of the
 simpler, older version of Iocaine Powder.
 
 Summary
 
 One must remember, when participating in a contest of this type, that we are
 not attempting to model natural phenomena or predict user actions; instead,
 these programs are competing against hostile opponents who are trying very
 hard not to be predictable. Iocaine Powder doesn't use advanced statistical
 techniques or Markov models (though it could perhaps be improved if it did),
 but it is very devious.
 
 It is, however, by no means the last word. Iocaine may have defeated all
 comers in the first tournament, but I have no doubt that my opponents will
 rise to the challenge in upcoming events.
   ------------------------------------------------------------------------
   Dan Egnor
*/

#define will_beat(play) ("\001\002\000"[play])
#define will_lose_to(play) ("\002\000\001"[play])

/* ------------------------------------------------------------------------- */

static const int my_hist = 0,opp_hist = 1,both_hist = 2;

static int match_single(int i,int num,int *history) {
    int *highptr = history + num;
    int *lowptr = history + i;
    while (lowptr > history && *lowptr == *highptr) --lowptr, --highptr;
    return history + num - highptr;
}

static int match_both(int i,int num) {
    int j;
    for (j = 0; j < i && opp_history[num-j] == opp_history[i-j]
              && my_history[num-j]  == my_history[i-j]; ++j) ;
    return j;
}

static void do_history(int age,int best[3]) {
    const int num = my_history[0];
    int best_length[3],i,j,w;

    for (w = 0; w < 3; ++w) best[w] = best_length[w] = 0; 
    for (i = num - 1; i > num - age && i > best_length[my_hist]; --i) {
        j = match_single(i,num,my_history);
        if (j > best_length[my_hist]) {
            best_length[my_hist] = j;
            best[my_hist] = i;
            if (j > num / 2) break;
        }
    }

    for (i = num - 1; i > num - age && i > best_length[opp_hist]; --i) {
        j = match_single(i,num,opp_history);
        if (j > best_length[opp_hist]) {
            best_length[opp_hist] = j;
            best[opp_hist] = i;
            if (j > num / 2) break;
        }
    }

    for (i = num - 1; i > num - age && i > best_length[both_hist]; --i) {
        j = match_both(i,num);
        if (j > best_length[both_hist]) {
            best_length[both_hist] = j;
            best[both_hist] = i;
            if (j > num / 2) break;
        }
    }
}

/* ------------------------------------------------------------------------- */

struct stats {
    int sum[1 + trials][3];
    int age;
};

static void reset_stats(struct stats *st) {
    int i;
    st->age = 0;
    for (i = 0; i < 3; ++i) st->sum[st->age][i] = 0;
}

static void add_stats(struct stats *st,int i,int delta) {
    st->sum[st->age][i] += delta;
}

static void next_stats(struct stats *st) {
    if (st->age < trials) {
        int i;
        ++(st->age);
        for (i = 0; i < 3; ++i) 
            st->sum[st->age][i] = st->sum[st->age - 1][i];
    }
}

static int max_stats(const struct stats *st,int age,int *which,int *score) {
    int i;
    *which = -1;
    for (i = 0; i < 3; ++i) {
        int diff;
        if (age > st->age) 
            diff = st->sum[st->age][i];
        else
            diff = st->sum[st->age][i] - st->sum[st->age - age][i];
        if (diff > *score) {
            *score = diff;
            *which = i;
        }
    }

    return -1 != *which;
}

/* ------------------------------------------------------------------------- */

struct predict {
    struct stats st;
    int last;
};

static void reset_predict(struct predict *pred) {
    reset_stats(&pred->st);
    pred->last = -1;
}

/* last: opponent's last move (-1 if none)
 | guess: algorithm's prediction of opponent's next move */
static void do_predict(struct predict *pred,int last,int guess) {
    if (-1 != last) {
        const int diff = (3 + last - pred->last) % 3;
        add_stats(&pred->st,will_beat(diff),1);
        add_stats(&pred->st,will_lose_to(diff),-1);
        next_stats(&pred->st);
    }

    pred->last = guess;
}

static void scan_predict(struct predict *pred,int age,int *move,int *score) {
    int i;
    if (max_stats(&pred->st,age,&i,score)) *move = ((pred->last + i) % 3);
}

/* ------------------------------------------------------------------------- */

static const int ages[] = { 1000, 100, 10, 5, 2, 1 };
#define num_ages (sizeof(ages) / sizeof(ages[0]))

struct iocaine {
    struct predict pr_history[num_ages][3][2],pr_freq[num_ages][2];
    struct predict pr_fixed,pr_random,pr_meta[num_ages];
    struct stats stats[2];
};

static int iocaine(struct iocaine *i) {
    const int num = my_history[0];
    const int last = (num > 0) ? opp_history[num] : -1;
    const int guess = biased_roshambo(1.0/3.0,1.0/3.0);
    int w,a,p;

    if (0 == num) {
        for (a = 0; a < num_ages; ++a) {
            reset_predict(&i->pr_meta[a]);
            for (p = 0; p < 2; ++p) {
                for (w = 0; w < 3; ++w)
                    reset_predict(&i->pr_history[a][w][p]);
                reset_predict(&i->pr_freq[a][p]);
            }
        }
        for (p = 0; p < 2; ++p) reset_stats(&i->stats[p]);
        reset_predict(&i->pr_random);
        reset_predict(&i->pr_fixed);
    } else {
        add_stats(&i->stats[0],my_history[num],1);
        add_stats(&i->stats[1],opp_history[num],1);
    }

    for (a = 0; a < num_ages; ++a) {
        int best[3];
        do_history(ages[a],best);
        for (w = 0; w < 3; ++w) {
            const int b = best[w];
            if (0 == b) {
                do_predict(&i->pr_history[a][w][0],last,guess);
                do_predict(&i->pr_history[a][w][1],last,guess);
                continue;
            }
            do_predict(&i->pr_history[a][w][0],last,my_history[b+1]);
            do_predict(&i->pr_history[a][w][1],last,opp_history[b+1]);
        }

        for (p = 0; p < 2; ++p) {
            int best = -1,freq;
            if (max_stats(&i->stats[p],ages[a],&freq,&best))
                do_predict(&i->pr_freq[a][p],last,freq);
            else
                do_predict(&i->pr_freq[a][p],last,guess);
        }
    }

    do_predict(&i->pr_random,last,guess);
    do_predict(&i->pr_fixed,last,0);

    for (a = 0; a < num_ages; ++a) {
        int aa,score = -1,move = -1;
        for (aa = 0; aa < num_ages; ++aa) {
            for (p = 0; p < 2; ++p) {
                for (w = 0; w < 3; ++w)
                    scan_predict(&i->pr_history[aa][w][p],
                             ages[a],&move,&score);
                scan_predict(&i->pr_freq[aa][p],ages[a],&move,&score);
            }
        }

        scan_predict(&i->pr_random,ages[a],&move,&score);
        scan_predict(&i->pr_fixed,ages[a],&move,&score);
        do_predict(&i->pr_meta[a],last,move);
    }

    {
        int score = -1,move = -1;
        for (a = 0; a < num_ages; ++a)
            scan_predict(&i->pr_meta[a],trials,&move,&score);
        return move;
    }
}

/* ------------------------------------------------------------------------- */

int iocainebot(void)
{
    static struct iocaine p;
    return iocaine(&p);
}
/**********************************************************************/


/*  Entrant:  Phasenbott (2)   Jakob Mandelson (USA)
 
 Phasenbott uses a similar strategy to Dan Egnor's "Iocaine Powder", 
 indeed it is derived from an early version of Dan's work.
 
 The early Iocaine Powder ("Old IP") took a single strategy as input, and
 "conjugated" it into six strategies:
   1. Play the strategy.
   2. Assume opponent thinks you'll play the strategy, and beat that.
   3. Assume opponent thinks you'll do (2), and beat that.
   4. Assume opponent plays strategy, and beat that.
   5. Assume opponent thinks you'll do (4), and beat that.
   6. Assume opponent thinks you'll do (5), and beat that.
 
 Because of the circular nature of the Rock beats Scissors beats Paper 
 beats Rock, if you assume the opponent thinks you'll do (3) then you'll
 play (1), and if you assume the opponent thinks you'll do (6) then you'll
 play (4), so these six "strategies" subsume a whole slew of second-guessing.
 (All assuming the initial strategy, though.)  Then it counts which one would
 have done best historically if played, and chooses that strategy to play.
 Old IP used a history match as its base strategy.
 
 I generalised this concept into a function which took in an array of
 "bots" (each of which returns what it would play if it were you, and if
 it were your opponent), did the six-way conjugation on each, and chose the 
 best strategy of those to play.  Note that this function is itself a "bot", 
 and can be fed into itself.  If you consider the operator I to take 
 strategies and choose the best among their conjugates, then Old IP can be
 represented by I(History).  Phasenbott uses a alternate history mechanism
 which performed better, in addition to Dan's original history mechanism and
 Old IP and Random (as a fallback) for its set of base strategies.
 Phasenbott=I(History, AltHistory, Old IP, Random)
 
 "New" IP (Dan's winning program) effectly subsumes Phasenbott, so it's
 no surprise that Phasenbott lost to it.  It uses the new history mechanism
 in addition to the original one, like Phasenbott, and also incorporates
 frequency analysis.  In addition, at the very end after it's applied the 
 various strategies, it applies the I operator to the result!  This means
 it's effectively checking to see how well it would do by playing to beat/lose
 to itself, and playing that if it is better.  I've checked the effects of
 this "meta-ing", and after the first couple steps it's not worthwhile:
 If one of the base strategies doesn't match the opponent's play, then 
 Iocaine's strategy becomes so subtle as to be effectively random.  If one
 of the base strategies does associate with the opponent, then the meta-ing
 does no good.
 
 Iocaine Powder also uses a more accurate metric for comparing the strategies.
 Where Phasenbott plays the strategy that results in the most wins, Iocaine
 Powder takes draws (or losses, depending on your POV) into account, and plays
 the highest scorer.  Phasenbott's metric would be more appropriate in a 
 non-zero sum Rock-Paper-Scissors game where one simply tallied points for
 wins.  This game is more interesting from the theoretical standpoint, as
 there is now incentive for cooperation and no longer a single optimal 
 strategy.  Random scores an expected 1/3, but cooperating players could
 do better by alternating wins, for 1/2.  A player wanting to do better than 
 1/2 would try to exploit the other player, but not enough that the other
 player detects that it's worthwhile to switch into Random mode.  The weak
 player scoring say 2/5 could know that it's being exploited by the stronger,
 but still go along with it as if it refused (by going Random) its score would
 drop to 1/3.  This in my mind makes for a much more interesting 
 Rock-Paper-Scissors game to study than "Roshambo".  Maybe the next 
 Rock-Paper-Scissors programming contest will feature such a non-zero sum
 game.  [Hint, hint. :) ]
 */

/*  Phasenbott  --   Jakob Mandelson.
 *    Roshambo competition program
 *    Looks at a series of strategies, and compares how they did historically.
 *    Then plays one that would have played best.
 *    Strategies used: Historical prediction based on sequence of both parties,
 *      and of one party, and itself using only both-party history prediction.
 *    Based on early Iocaine Powder bot of Dan Egnor of playing strategy
 *      that would have done best historically.  Used with permission,
 *      and some ideas crossed back into Dan's Iocaine.
 *    May the best program (more likely Dan's than mine :) win!
 */

#define pwill_beat(x) ("\001\002\000"[x])

typedef struct {
   long (*fcn)(void *state);
   void *state;
} jlmbot;

typedef struct {
   int both, my, opp, num;
} jlmhistret;

static void jlm_history(jlmhistret *s) {
    int besta,bestb,bestc,i,j,num;
    /* a is both history, b is my history, c is opponent history. */

    if (s->num == my_history[0]) return;
    s->num = num = my_history[0];
    s->both = s->my = s->opp = besta = bestb = bestc = 0;
    for (i = num - 1; i > besta; --i) {
        for (j = 0; j < i 
                && opp_history[num - j] == opp_history[i - j]
                && my_history[num - j] == my_history[i - j]; ++j) { } 
        if (j > besta) { besta = j; s->both = i; }
        if (j > bestb) { bestb = j; s->my = i; }
        if (j > bestc) { bestc = j; s->opp = i; }
        if (opp_history[num-j] != opp_history[i - j]) {
            for ( ; j < i && my_history[num-j] == my_history[i-j]; ++j) { }
            if (j > bestb) { bestb = j; s->my = i; }
        }
        else /* j >= i || my_history[num-j] != my_history[i - j] */ {
            for ( ; j < i && opp_history[num-j] == opp_history[i-j]; ++j) { }
            if (j > bestc) { bestc = j; s->opp = i; }
        }
    }
}

static long jlmhist1(jlmhistret *s) {
        jlm_history(s);
        if (0 == s->opp) return biased_roshambo(1.0/3.0,1.0/3.0);
        return pwill_beat(opp_history[s->opp + 1]) | 
                (pwill_beat(my_history[s->my + 1]) << 16) ;
}

static long jlmhist0(jlmhistret *s) {
        jlm_history(s);
        if (0 == s->both) return biased_roshambo(1.0/3.0,1.0/3.0);
        return pwill_beat(opp_history[s->both + 1]) | 
                (pwill_beat(my_history[s->both + 1]) << 16) ;
}

static long jlmrand(void *throwaway) {  
    /* Fallback to keep from losing too badly.  */
        return biased_roshambo(1.0/3.0, 1.0/3.0) |
                (biased_roshambo(1.0/3.0, 1.0/3.0) << 16);
}

typedef struct {
  int n;
  int *my_last, *opp_last;
  int (*my_stats)[3], (*opp_stats)[3];
  int (*my_ostats)[3], (*opp_ostats)[3];
  int *opp_guess, *my_guess;
  jlmbot *to_beat;
} jocaine_state;

static long apply_jocaine(jocaine_state *);

int phasenbott()
{
   typedef long (*fcn)(void *state);
   typedef int arr4[4];
   static jlmhistret h;
   static arr4 my_last, opp_last, opp_guess, my_guess;
   static int my_stats[4][3], opp_stats[4][3], my_ostats[4][3], 
                opp_ostats[4][3];
   static int sy_last, spp_last, spp_guess, sy_guess;
   static int sy_stats[3], spp_stats[3], sy_ostats[3], spp_ostats[3];
   static jlmbot hb = { (fcn)jlmhist0,  &h};
   static jocaine_state t = { 1, &sy_last, &spp_last,
                              &sy_stats, &spp_stats, &sy_ostats, &spp_ostats,
                              &spp_guess, &sy_guess, &hb };
   static jlmbot ba[4] = {{(fcn)jlmhist1, &h}, {(fcn)jlmhist0, &h}, 
                          {(fcn)jlmrand, 0}, {(fcn)apply_jocaine, &t}};
   static jocaine_state s = { 4, my_last, opp_last,
                              my_stats, opp_stats, my_ostats, opp_ostats,
                              opp_guess, my_guess, ba};
   return apply_jocaine(&s) & 0xFFFF;
}

static long apply_jocaine(jocaine_state *s) {
        const int num = my_history[0];
        long b;
        int i,my_most,opp_most, h;
        int my_omost, opp_omost;
        int hy_omost, hpp_omost;
        int hy_most, hpp_most;

        if (0 == num) {
            for (h = 0; h < s->n; h++)
            {   for (i = 0; i < 3; ++i) 
                        s->my_stats[h][i] = s->opp_stats[h][i] = 
                        s->my_ostats[h][i] = s->opp_ostats[h][i] = 0;
                b = s->to_beat[h].fcn(s->to_beat[h].state);
                s->my_last[h] =  b & 0xFFFF;
                s->opp_last[h] =  b >> 16; 
            }
            return random()%3;
        }

     for (h = 0; h < s->n; h++)
     {
        b = s->to_beat[h].fcn(s->to_beat[h].state); 
        s->my_guess[h] = b & 0xFFFF;
        s->opp_guess[h] = b >> 16;

        s->my_stats[h][(3 + opp_history[num] - s->my_last[h]) % 3]++;
        s->opp_stats[h][(3 + opp_history[num] - s->opp_last[h]) % 3]++;
        s->my_ostats[h][(3 + my_history[num] - s->opp_last[h]) % 3]++;
        s->opp_ostats[h][(3 + my_history[num] - s->my_last[h]) % 3]++;

        s->my_last[h] = s->my_guess[h];
        s->opp_last[h] = s->opp_guess[h];
    }

        my_most = opp_most = my_omost = opp_omost = 0;
        hy_most = hpp_most = hy_omost = hpp_omost = 0;
        for (h = 0; h < s->n; ++h) 
            for (i = 0; i < 3; ++i) {
                if (s->my_stats[h][i] > s->my_stats[hy_most][my_most]) 
                        { my_most = i; hy_most = h; }
                if (s->opp_stats[h][i] > s->opp_stats[hpp_most][opp_most]) 
                        { opp_most = i; hpp_most = h; }
                if (s->my_ostats[h][i] > s->my_ostats[hy_omost][my_omost]) 
                        { my_omost = i; hy_omost = h; }
                if (s->opp_ostats[h][i] > s->opp_ostats[hpp_omost][opp_omost]) 
                        { opp_omost = i; hpp_omost = h; }
            }

        if (s->opp_stats[hpp_most][opp_most] >= s->my_stats[hy_most][my_most])
                b = pwill_beat((s->opp_guess[hpp_most] + opp_most) % 3);
        else
                b = pwill_beat((s->my_guess[hy_most] + my_most) % 3);

        if (s->opp_ostats[hpp_omost][opp_omost] 
                        >= s->my_ostats[hy_omost][my_omost])
                b |= pwill_beat((s->my_guess[hpp_omost] + opp_omost) % 3) << 16;
        else
                b |= pwill_beat((s->opp_guess[hy_omost] + my_omost) % 3) << 16;

        return b;
}
/**********************************************************************/


/*  Entrant:  MegaHAL (3)   Jason Hutchens (Aus)

 MegaHAL     (from: http://ciips.ee.uwa.edu.au/~hutch/puzzles/roshambo/)
 
 MegaHAL, named in honour of a conversation simulator of mine, was my entry
 into the First International RoShamBo Programming Competition, which was
 conducted by Darse Billings. MegaHAL came third in the competition, behind
 the excellent Iocaine Powder of Dan Egnor, and Phasenbott by Jakob
 Mandelson. This web page is a brief attempt to explain how the MegaHAL
 algorithm works.
 
 Source Code
 
 Please feel free to download the source code to the MegaHAL algorithm. To
 compile it with Darse's tournament program (available from the competition
 home page), I recommend that you modify the tournament program by adding an
 external declaration to the halbot() function, and then linking the code as
 follows:
 
 gcc -o roshambo roshambo.c megahal.c
 
 I have also written a simple program which allows a human being to play
 against a RoShamBo algorithm. You may compile that as follows:
 
 gcc -o shell shell.c megahallc -lcurses
 
    * megahal.c (18Kb)
    * shell.c (15Kb)
 
 Prediction
 
 My opinion, as I have stated on the comp.ai.games newsgroup often enough,
 is that Darse's competition provides an ideal test-bed for predictive
 algorithms, or predictors. I have worked with predictors for the last five
 years, applying them to various syntactic pattern recognition problems,
 speech recognition, text generation and data compression.
 
 A predictor is an algorithm which is able to predict the next symbol in a
 sequence of symbols as a probability distribution over the alphabet of
 symbols. The only information available to the predictor is the history of
 symbols seen so far. In order to turn a predictor into a RoShamBo algorithm,
 we need to decide what the history of symbols should be, and how to turn a
 prediction into a RoShamBo move.
 
 Determining the history
      Because we are trying to predict our opponent's next move, and because
      our opponent may be using our previous moves to decide what they're
      going to do, it seems reasonable to make the symbol sequence an
      interlacing of both our histories: x1,y1,x2,y2,..., xn-1,yn-1, where x
      represents our opponent's move, y represents our move, and our job is
      to predict the value of xn in order to determine what yn should be.
 Choosing our move
      Once we have a prediction for yn in the form of a probability
      distribution over all possible moves, we need to decide what our move
      is going to be. We do this by choosing the move which maximises the
      expected value of our score. For example, imagine that the prediction
      gives P(rock)=0.45, P(paper)=0.15, P(scissors)=0.40. The maximum
      likelihood move (paper) gives an expected score of 1*0.45-1*0.40=0.05,
      while the defensive move of rock gives an expected score of
      1*0.40-1*0.15=0.25, and is therefore chosen.
 
 With these two modifications, any predictor may play RoShamBo!
 
 The MegaHAL Predictor
 
 MegaHAL is a very simple "infinite-order" Markov model. It stores frequency
 information about the moves the opponent has made in the past for all
 possible contexts (from a context of no symbols at all right up to a context
 of the entire history). In practise, the context is limited to forty-two
 symbols so that the algorithm satisfies the time constraint of playing one
 game every millisecond on average.
 
 MegaHAL stores this information in a ternary trie. Each context is
 represented as a node in this trie. Every time MegaHAL is asked to make a
 move, many of these nodes may activate, and each of them is capable of
 providing us with a prediction about what's coming next. We need to select
 one of them. We do this by storing in each node the average score that that
 node would have if it had been used exclusively in the past. We select the
 node which has the highest average score. If more than one node qualifies,
 we choose the one which takes the longest context into account.
 
 In some situations, no nodes will be selected. In this situation, we make a
 move at random.
 
 MegaHAL also gathers statistics over a sliding window, which means that it
 "forgets" about events which occurred a long time ago. This process allows
 MegaHAL to adapt more rapidly to changes in its opponents strategy. In the
 competition version, a sliding window of four hundred symbols was used (a
 match consists of two thousand symbols).
 
 Conclusion
 
 I hope that brief explanation of the MegaHAL strategy has been enlightening.
 I apologise for any omissions or poor English, and blame that on the fact
 that it was written at 12:45pm on a Saturday night, following a night out
 with friends!
*/

/*============================================================================*/
/*
 *  Copyright (C) 1999 Jason Hutchens
 *
 *  This program is free software; you can redistribute it and/or modify it
 *  under the terms of the GNU General Public License as published by the Free
 *  Software Foundation; either version 2 of the license or (at your option)
 *  any later version.
 *
 *  This program is distributed in the hope that it will be useful, but
 *  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 *  or FITNESS FOR A PARTICULAR PURPOSE.  See the Gnu Public License for more
 *  details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program; if not, write to the Free Software Foundation, Inc.,
 *  675 Mass Ave, Cambridge, MA 02139, USA.
 */
/*============================================================================*/
/*
 *      NB:      File displays best with tabstops set to three spaces.
 *
 *      Name:      MegaHAL (in honour of http://ciips.ee.uwa.edu.au/~hutch/hal/)
 *
 *      Author:   Jason Hutchens (hutch@amristar.com.au)
 *
 *      Purpose:   Play the game of Rock-Paper-Scissors.  Statistics about the
 *               game so far are recorded in a ternary trie, represnting an
 *               infinite-order Markov model.  The context which has performed
 *               best in the past is used to make the prediction, and we
 *               gradually fall-back through contexts which performed less well
 *               when the contexts haven't yet been observed.  One of the
 *               contexts is always guaranteed to make a move at random, so
 *               we never encounter a situation where we can't make a move.
 *               Statistics are gathered over a sliding window, allowing
 *               adaption if the opponent's strategies change.
 *
 *      $Id: rsb-glko.c,v 1.2 1999/12/02 07:22:23 mike Exp $
 */
/*============================================================================*/

/*============================================================================*/

int halbot(void);
static int halbot_compare(const void *, const void *);

/*============================================================================*/
/*
 *      Function:   halbot
 *
 *      Arguments:   void
 *
 *      Returns:      An integer between 0 and 2, representing the move that the
 *                  predictor makes in the game of Rock-Paper-Scissors.
 *
 *      Overview:   The program collects statistics about the game using an
 *                  infinite context Markov model, which is stored in a ternary
 *                  trie.  The procedure is to update the statistics of the
 *                  model with the latest moves, and remove the statistics of
 *                  moves outside a sliding window of defined length.  We build
 *                  an array of contexts which make valid predictions, including
 *                  the special context which always predicts at random, and we
 *                  sort this according to how well the contexts have performed
 *                  in the recent past (again with the sliding window).  The
 *                  best context is then used to make the prediction, and our
 *                  move is selected in order to maximise the expected value of
 *                  the score.  The bot monitors how much time it's been
 *                  spending, and emits a message when this time exceeds an
 *                  average of one millisecond per move (i.e. one second per
 *                  one thousand moves).
 *
 *      Comment:      Even though it's really messy, everything is done in this
 *                  one function to allow it to be added to the competition
 *                  source code easily.
 */
int halbot(void)
{
   /*
    *      Set this to a non-zero value to emit an warning message if the
    *      algorithm averages more than one millisecond per move.
    */
   #define   ERROR      0
   /*
    *      These defines are the three heuristic parameters that can be modified
    *      to alter performance.  BELIEVE gives the number of times a context
    *      must be observed before being used for prediction, HISTORY gives the
    *      maximum context size to observe (we're limited by time, not memory),
    *      and WINDOW gives the size of the sliding window, 0 being infinite.
    *
    *      - BELIEVE>=1
    *      - HISTORY>=1
    *      - WINDOW>=HISTORY or 0 for infinite
    */
   #define   BELIEVE   1
   #define   HISTORY   21
   #define   WINDOW   200
   /*
    *      This define just makes the code neater (huh, as if).
    */
   #define   COUNT      trie[context[i].node].move
   #define   SCOUNT   trie[sorted[i].node].move
   /*
    *      These macros returns the maximum/minimum values of two expressions.
    */
   #define   MAX(a,b)   (((a)>(b))?(a):(b))
   #define   MIN(a,b)   (((a)<(b))?(a):(b))
   /*
    *      Each node of the trie contains frequency information about the moves
    *      made at the context represented by the node, and where the sequent
    *      nodes are in the array.
    */
   typedef struct S_NODE {
      short int total;
      short int move[3];
      int next[3];
   } NODE;
   /*
    *      The context array contains information about contexts of various
    *      lengths, and this is used to select a context to make the prediction.
    */
   typedef struct S_CONTEXT {
      int worst;
      int best;
      int seen;
      int size;
      int node;
   } CONTEXT;
   /*
    *      This is the only external information we have about our opponent;
    *      it's a history of the game so far.
    */
   extern int my_history[];
   extern int opp_history[];
   /*
    *      We declare all variables as statics because we want most of them to
    *      be persistent.
    */
   static int move=-1;
   static int last_move=-1;
   static int random_move=-1;
   static NODE *trie=NULL;
   static int trie_size=0;
   static int context_size=0;
   static CONTEXT *context=NULL;
   static CONTEXT *sorted=NULL;
   static int **memory=NULL;
   static int remember=0;
   static struct timeval start;
   static struct timeval end;
   static long think;
   static int node;
   static int expected[3];
   /*
    *      But you canny have static register variables!
    */
   register int i,j;
   /*
    *      Start the timer.
    */
   (void)gettimeofday(&start,NULL);
   /*
    *      If this is the beginning of the game, set some things up.
    */
   if(my_history[0]==0) {
      if(trie==NULL) {
         /*
          *      If this is the first game we've played, initialise the memory.
          *      On some Unices, realloc doesn't work with NULL arguments, so
          *      we're just making sure they're non-NULL.
          *
          *      NB: We must allocate two elements for the context!
          */
         context=(CONTEXT *)malloc(sizeof(CONTEXT)*(HISTORY+2));
         assert(context);
         sorted=(CONTEXT *)malloc(sizeof(CONTEXT)*(HISTORY+2));
         assert(sorted);
         if(WINDOW>0) {
            memory=(int **)malloc(sizeof(int *)*WINDOW);
            assert(memory);
            for(i=0; i<WINDOW; ++i) {
               memory[i]=(int *)malloc(sizeof(int)*(HISTORY+2));
               assert(memory[i]);
            }
         }
         trie=(NODE *)malloc(sizeof(NODE));
         assert(trie);
      }
      /*
       *      Clear the trie, by setting its size to unity, and clearing the
       *      statistics of the root node.
       */
      trie_size=1;
      trie[0]=(NODE){0,{0,0,0},{-1,-1,-1}};
      /*
       *      Clear the memory matrix.
       */
      for(i=0; i<WINDOW; ++i)
         for(j=0; j<HISTORY+2; ++j)
            memory[i][j]=-1;
      /*
       *      Clear the context array.
       */
      for(i=0; i<HISTORY+2; ++i) context[i]=(CONTEXT){0,0,0,0,0};
      context[0]=(CONTEXT){0,0,0,-1,-1};
      context[1]=(CONTEXT){0,0,0,0,0};
      /*
       *      Clear the variable we use to keep track of how long MegaHAL
       *      spends thinking.
       */
      think=0;
   }
   /*
    *      If we've already started playing, evaluate how well we went on our
    *      last turn, and update our list which decides which contexts give the
    *      best predictions.
    */
   if(my_history[0]>0) {
      /*
       *      We begin by forgetting which contexts performed well in the
       *      distant past.
        */
      if(WINDOW>0) for(i=1; i<context_size; ++i) {
         if(WINDOW-i>0) {
            if(memory[(remember+i-1)%WINDOW][i]>=0) {
               if(memory[(remember+i-1)%WINDOW][i]==
                  ((opp_history[my_history[0]-WINDOW+i-1]+1)%3))
                     context[i].best-=1;
               if(memory[(remember+i-1)%WINDOW][i]==
                  ((opp_history[my_history[0]-WINDOW+i-1]+2)%3))
                     context[i].worst-=1;
               context[i].seen-=1;
            }
         }
      }
      /*
       *      Clear our dimmest memory.
       */
      if(WINDOW>0) for(i=0; i<context_size; ++i)
         memory[remember][i]=-1;
      /*
       *      We then remember the contexts which performed the best most
       *      recently.
       */
      for(i=0; i<context_size; ++i) {
         if(context[i].node>=trie_size) continue;
         if(context[i].node==-1) continue;
         if(trie[context[i].node].total>=BELIEVE) {
            for(j=0; j<3; ++j)
               expected[j]=COUNT[(j+2)%3]-COUNT[(j+1)%3];
            last_move=0;
            for(j=1; j<3; ++j)
               if(expected[j]>expected[last_move])
                  last_move=j;
            if(last_move==(opp_history[my_history[0]]+1)%3)
               context[i].best+=1;
            if(last_move==(opp_history[my_history[0]]+2)%3)
               context[i].worst+=1;
            context[i].seen+=1;
            if(WINDOW>0) memory[remember][i]=last_move;
         }
      }
      if(WINDOW>0) remember=(remember+1)%WINDOW;
   }
   /*
    *      Clear the context to the node which always predicts at random, and
    *      the root node.
    */
   context_size=2;
   /*
    *      We begin by forgetting the statistics we've previously gathered
    *      about the symbol which is now leaving the sliding window.
    */
   if((WINDOW>0)&&(my_history[0]-WINDOW>0))
      for(i=my_history[0]-WINDOW;
         i<MIN(my_history[0]-WINDOW+HISTORY,my_history[0]); ++i) {
      /*
       *      Find the node which corresponds to the context.
       */
      node=0;
      for(j=MAX(my_history[0]-WINDOW,1); j<i; ++j) {
         node=trie[node].next[opp_history[j]];
         node=trie[node].next[my_history[j]];
      }
      if((node<0)||(node>=trie_size))fprintf(stderr, "OUCH\n");
      /*
       *      Update the statistics of this node with the opponents move.
       */
      trie[node].total-=1;
      trie[node].move[opp_history[i]]-=1;
   }
   /*
    *      Build up a context array pointing at all the nodes in the trie
    *      which predict what the opponent is going to do for the current
    *      history.  While doing this, update the statistics of the trie with
    *      the last move made by ourselves and our opponent.
    */
#if(WINDOW>0)
   for(i=my_history[0]; i>MAX(my_history[0]-MIN(WINDOW,HISTORY),0); --i) {
#else
   for(i=my_history[0]; i>MAX(my_history[0]-HISTORY,0); --i) {
#endif
      /*
       *      Find the node which corresponds to the context.
       */
      node=0;
      for(j=i; j<my_history[0]; ++j) {
         node=trie[node].next[opp_history[j]];
         node=trie[node].next[my_history[j]];
      }
      if((node<0)||(node>=trie_size))fprintf(stderr, "OUCH\n");
      /*
       *      Update the statistics of this node with the opponents move.
       */
      trie[node].total+=1;
      trie[node].move[opp_history[my_history[0]]]+=1;
      /*
       *      Move to this node, making sure that we've allocated it first.
       */
      if(trie[node].next[opp_history[my_history[0]]]==-1) {
         trie[node].next[opp_history[my_history[0]]]=trie_size;
         trie_size+=1;
         trie=(NODE *)realloc(trie,sizeof(NODE)*trie_size);
         assert(trie);
         trie[trie_size-1]=(NODE){0,{0,0,0},{-1,-1,-1}};
      }
      node=trie[node].next[opp_history[my_history[0]]];
      if((node<0)||(node>=trie_size))fprintf(stderr, "OUCH\n");
      /*
       *      Move to this node, making sure that we've allocated it first.
       */
      if(trie[node].next[my_history[my_history[0]]]==-1) {
         trie[node].next[my_history[my_history[0]]]=trie_size;
         trie_size+=1;
         trie=(NODE *)realloc(trie,sizeof(NODE)*trie_size);
         assert(trie);
         trie[trie_size-1]=(NODE){0,{0,0,0},{-1,-1,-1}};
      }
      node=trie[node].next[my_history[my_history[0]]];
      if((node<0)||(node>=trie_size))fprintf(stderr, "OUCH\n");
      /*
       *      Add this node to the context array.
       */
      context_size+=1;
      context[context_size-1].node=node;
      context[context_size-1].size=context_size-2;
   }
   /*
    *      Sort the context array, based upon what contexts have proved
    *      successful in the past.  We sort the context array by looking
    *      at the context lengths which most often give the best predictions.
    *      If two contexts give the same amount of best predictions, choose
    *      the longest one.  If two contexts have consistently failed in the
    *      past, choose the shortest one.
    */
   for(i=0; i<context_size; ++i)
      sorted[i]=context[i];
   qsort(sorted,context_size,sizeof(CONTEXT),halbot_compare);
   /*
    *      Starting at the most likely context, gradually fall-back until we
    *      find a context which has been observed at least BELIEVE times.  Use
    *      this context to predict a probability distribution over the opponents
    *      possible moves.  Select the move which maximises the expected score.
    */
   move=-1;
   for(i=0; i<context_size; ++i) {
      if(sorted[i].node>=trie_size) continue;
      if(sorted[i].node==-1) break;
      if(trie[sorted[i].node].total>=BELIEVE) {
         for(j=0; j<3; ++j)
            expected[j]=SCOUNT[(j+2)%3]-SCOUNT[(j+1)%3];
         move=0;
         for(j=1; j<3; ++j)
            if(expected[j]>expected[move])
               move=j;
         break;
      }
   }
   /*
    *      If no prediction was possible, make a random move.
    */
   random_move=random()%3;
   if(move==-1) move=random_move;
   /*
    *      Update the timer, and warn if we've exceeded one second per one
    *      thousand turns.
    */
   (void)gettimeofday(&end,NULL);
   if(think>=0)
      think+=1000000*(end.tv_sec-start.tv_sec)+(end.tv_usec-start.tv_usec);
   if((ERROR!=0)&&((think/(my_history[0]+1)>=1000)&&(my_history[0]>100))) {
      think=-1;
      fprintf(stdout, "\n\n*** MegaHAL-Infinite is too slow! ***\n\n");
   }
   /*
    *      Return our move.
    */
   return(move);

}   /* end "halbot" */

/*----------------------------------------------------------------------------*/
/*
 *      Function:   halbot_compare
 *
 *      Arguments:   const void *value1, const void *value2
 *                  Two pointers into the sort array.  Our job is to decide
 *                  whether value1 is less than, equal to or greater than
 *                  value2.
 *
 *      Returns:      An integer which is positive if value1<value2, negative if
 *                  value1>value2, and zero if they're equal.  Various heuristics
 *                  are used to test for this inequality.
 *
 *      Overview:   This comparison function is required by qsort().
 */
static int halbot_compare(const void *value1, const void *value2)
{
   /*
    *      This is a duplicate of the typedef in halbot(), put here to avoid
    *      having to make it external to the functions.
    */
   typedef struct S_CONTEXT {
      int worst;
      int best;
      int seen;
      int size;
      int node;
   } CONTEXT;
   /*
    *      Some local variables.
    */
   CONTEXT *context1;
   CONTEXT *context2;
   float prob1=0.0;
   float prob2=0.0;
   /*
    *      This looks complicated, but it's not.  Basically, given two nodes
    *      in the trie, these heuristics decide which node should be used to
    *      make a prediction first.  The rules are:
    *      - Choose the one which has performed the best in the past.
    *      - If they're both being tried for the first time, choose the shortest.
    *      - If they've both performed equally well, choose the longest.
    */
   context1=(CONTEXT *)value1;
   context2=(CONTEXT *)value2;
   if(context1->seen>0)
      prob1=(float)(context1->best-context1->worst)/(float)(context1->seen);
   if(context2->seen>0)
      prob2=(float)(context2->best-context2->worst)/(float)(context2->seen);
   if(prob1<prob2) return(1);
   if(prob1>prob2) return(-1);
   if((context1->seen==0)&&(context2->seen=0)) {
      if(context1->size<context2->size) return(-1);
      if(context1->size>context2->size) return(1);
      return(0);
   }
   if(context1->size<context2->size) return(1);
   if(context1->size>context2->size) return(-1);
   return(0);

}   /* end of "halbot_compare" */

/*============================================================================*/
/*
 *      $Log: rsb-glko.c,v $
 *      Revision 1.2  1999/12/02 07:22:23  mike
 *      update
 *
 *      Revision 1.3  1999/12/02 06:43:13  mike
 *      update
 *
 *      Revision 1.11  1999/12/01 17:43:43  mike
 *      better tournament format
 *
 *      Revision 1.10  1999/11/29 00:49:33  mike
 *      bug fixes
 *
 *      Revision 1.9  1999/11/28 00:43:37  mike
 *      added initial randomization of player order
 *
 *      Revision 1.8  1999/11/27 21:33:04  mike
 *      adding round stats
 *
 *      Revision 1.7  1999/11/26 07:52:04  mike
 *      adding rounds
 *
 *      Revision 1.6  1999/11/19 21:22:58  mike
 *      keep track of wins, losses, and ties
 *
 *      Revision 1.5  1999/11/19 19:35:40  mike
 *      added verboseLevel
 *
 *      Revision 1.4  1999/11/17 00:15:12  mike
 *      update
 *
 *      Revision 1.3  1999/11/15 21:27:03  mike
 *      update
 *
 *      Revision 1.2  1999/11/14 09:12:13  mike
 *      added
 *
 *      Revision 1.1  1999/11/11 08:43:40  mike
 *      new
 *
 *      Revision 1.1  1999/11/09 07:34:38  mike
 *      original
 *
 *      Revision 1.7  1999/09/16 03:16:55  hutch
 *      Did some speed improvements, improved the method of remembering past
 *      strategies, and imroved the heuristics for sorting.  Over 1000 tourneys
 *      of 1000 trials, it performed 17.6 times better than the second best bot,
 *      "Beat Last Move", and scored an average of 678 per match.  It also
 *      consistently beats version 1.1, scoring an average of 100 or so per
 *      match.
 *
 *      Revision 1.5  1999/09/13 16:51:57  hutch
 *      The sliding window is working perfectly.  Of course, this strategy
 *      doesn't improve the performance of MegaHAL-Infinite on the standard
 *      algorithms, but it will hopefully improve performance on smarter ones.
 *
 *      Revision 1.4  1999/09/13 14:48:57  hutch
 *      Cleaned up the source a bit, and prepared to implement the sliding
 *      window strategy.
 *
 *      Revision 1.3  1999/09/12 06:29:30  hutch
 *      Consideration of the statistics, and correcting it to give proper
 *      probability estimates, improved Megahal-Infinite beyond MegaHAL.
 *
 *      Revision 1.2  1999/09/12 06:23:02  hutch
 *      Infinite contexts are done, and we now choose the context that has
 *      performed the best in the past.  Doesn't perform as well as MegaHAL,
 *      but I believe it will perform better on craftier algorithms.  Plus
 *      it out-performs MegaHAL on R-P-S 20-20-60.
 *
 *      Revision 1.1  1999/09/12 03:53:08  hutch
 *      This is the first official version.  We are now going to concentrate
 *      on making an infinite-context model, and collecting statistics over
 *      a sliding window, in the hope that this will improve performance
 *      against more sophisticated algorithms.
 *
 *      Revision 0.4  1999/09/11 12:40:11  hutch
 *      Okay, experimentation with parameters has increased it's performance to
 *      about 15 times better than the second best bot, and it's near perfect on
 *      "Beat Last Move", "Beat Frequent Pick", "Rotate RPS" and "Good Ol Rock".
 *      It scores about half on "Always Switchin'", and about a third on "R-P-S
 *      20-20-60".  Interestingly, this is the only bot which it has difficulty
 *      with.  Over 1000 tourneys of 1000 trials, it performed 17.5 times better
 *      than the second best bot, "Beat Last Move", and scored an average of 677
 *      per match.
 *
 *      Revision 0.3  1999/09/11 12:33:54  hutch
 *      Everything is working; the program kicks ass against the standard bots
 *      (performing at least twelve times better than the second best).  I will
 *      fine-tune the algorithm a bit, although it is quite quick, and will play
 *      around with the heuristics before submitting.
 *
 *      Revision 0.2  1999/09/11 11:40:01  hutch
 *      The mechanism for selecting the best move has been finished, and the
 *      model is working for a NULL context.  Now we need to expand it to the
 *      infinite context.
 *
 *      Revision 0.1  1999/09/11 05:58:29  hutch
 *      Initial revision
 */
/*============================================================================*/
/**********************************************************************/


/*  Entrant:  RussRocker4 (4)   Russ Williams (USA)

   > I also welcome more feedback from the participants,
 
 Ok, here's some more feedback & personal info for you.  Feel free to include
 any of it at your site if it seems of interest.
 
 You summed up the basic idea of my AI pretty well in your Part 1 report.  I
 basically made a Markov model of the other player's actions, given the last
 3 moves of both players and basing the probabilities on the entire match
 history.  I then assumed they would simply pick the most likely move.  I
 also used the last 2 moves if the last 3 moves gave a tie for most likely
 guess, and if that still tied, use the last move, and so on.  Experimenting
 showed that using this tie breaking seemed to only be useful early on, so
 after a while ties for most likely opponent choice were broken by choosing
 randomly.
 
 I also intentionally chose to use the large arrays to avoid having to scan
 the entire history array each turn, since I wasn't sure how much of an issue
 execution speed would be.  The cost of that was that there was no simple or
 obvious way to give more emphasis to more recent games, which I would have
 liked to have done.
 
 I'd misunderstood and thought that reverting to random behavior even as a
 "bailout" measure was considered unsporting, else I might have added such a
 feature which would have (as you observed) saved me getting so trounced by
 the rank 1 & 2 programs.  Or did you have some other sort of bailout measure
 in mind?  I could imagine another potentially useful (or at least amusing)
 bailout measure would be "if I'm losing hideously, then start doing the
 opposite of whatever my algorithm says I should do."
 
 I fiddled off & on with my program for about 5 days.  It went through quite
 a few iterations, and I played many long tournaments with variations of
 itself and lots of intentionally weak players to tweak it.
 
 I also found that some versions seemed much stronger at short matches (e.g.
 100 games) and weaker at long matches (e.g. 10000 games), and vice-versa.
 The reasons were not always apparent.
 
 In real life I am a game programmer, which I got into after completing a MS
 in CS at UT Austin.  I worked on 1830 (from Avalon Hill) and Master of Orion
 2 (from Microprose), doing AI for both.  I plan to work on AI for Go one of
 these days.
*/

static int russrock_max(int *a, int n)
{
    int i;
    int best_index = 0;
    int max_so_far = a[0];
    for (i = 1; i < n; ++i) {
        if (max_so_far < a[i]) {
            max_so_far = a[i];
            best_index = i;
        }
    }
    return best_index;
}

int russrocker4()
{
/* by Russ Williams (e-mail: russrocker at hotmail dot com */
    const int n_moves_for_3 = 825;
    const int n_moves_for_2 = 11;
    const int n_moves_for_1 = 6;

    static int moves0[3];
    static int moves1[3][3][3];
    static int moves2[3][3][3][3][3];
    static int moves3[3][3][3][3][3][3][3];

    int max_index, max_value;

    int i, j, n;

    int n_moves = opp_history[0];
    int their_last = -1;

    int temp[3];
    int n_votes[3] = {1, 1, 1};

    if (n_moves == 0) {
        memset(moves0, 0, sizeof moves0);
        memset(moves1, 0, sizeof moves1);
        memset(moves2, 0, sizeof moves2);
        memset(moves3, 0, sizeof moves3);
    } else {
        their_last = opp_history[n_moves];
    }

    switch (n_moves) {
    default:
        ++moves3
            [my_history[n_moves - 3]][opp_history[n_moves - 3]]
            [my_history[n_moves - 2]][opp_history[n_moves - 2]]
            [my_history[n_moves - 1]][opp_history[n_moves - 1]]
            [their_last];
        /*  fall through */
    case 3:
        ++moves2
            [my_history[n_moves - 2]][opp_history[n_moves - 2]]
            [my_history[n_moves - 1]][opp_history[n_moves - 1]]
            [their_last];
        /*  fall through */
    case 2:
        ++moves1
            [my_history[n_moves - 1]][opp_history[n_moves - 1]]
            [their_last];
        /*  fall through */
    case 1:
        ++moves0
            [their_last];
        /*  fall through */
    case 0:
        break;
    }

    do {

        if (3 <= n_moves) {
            for (i = 0; i < 3; ++i) {
                temp[i] = moves3
                    [my_history[n_moves - 2]][opp_history[n_moves - 2]]
                    [my_history[n_moves - 1]][opp_history[n_moves - 1]]
                    [my_history[n_moves]][their_last]
                    [i];
            }
            max_index = russrock_max(temp, 3);
            max_value = temp[max_index];
            if (0 < max_value) {
                n = 0;
                for (i = 0; i < 3; ++i) {
                    if (temp[i] == max_value) {
                        n_votes[i] += 10000;
                        ++n;
                    }
                }
                if (n == 1 || n_moves_for_3 <= n_moves) break;
            }

            for (i = 0; i < 3; ++i) {
                temp[i] = 0;
                for (j = 0; j < 3; ++j) {
                    temp[i] += moves3
                        [j][opp_history[n_moves - 2]]
                        [my_history[n_moves - 1]][opp_history[n_moves - 1]]
                        [my_history[n_moves]][their_last]
                        [i]
                        + moves3
                        [my_history[n_moves - 2]][j]
                        [my_history[n_moves - 1]][opp_history[n_moves - 1]]
                        [my_history[n_moves]][their_last]
                        [i];
                }
            }
            max_index = russrock_max(temp, 3);
            max_value = temp[max_index];
            if (0 < max_value) {
                n = 0;
                for (i = 0; i < 3; ++i) {
                    if (temp[i] == max_value) {
                        n_votes[i] += 5000;
                        ++n;
                    }
                }
            }
        }

        if (2 <= n_moves) {
            for (i = 0; i < 3; ++i) {
                temp[i] = moves2
                    [my_history[n_moves - 1]][opp_history[n_moves - 1]]
                    [my_history[n_moves]][their_last]
                    [i];
            }
            max_index = russrock_max(temp, 3);
            max_value = temp[max_index];
            if (0 < max_value) {
                n = 0;
                for (i = 0; i < 3; ++i) {
                    if (temp[i] == max_value) {
                        n_votes[i] += 1000;
                        ++n;
                    }
                }
                if (n_moves_for_2 <= n_moves) break;
            }

            for (i = 0; i < 3; ++i) {
                temp[i] = 0;
                for (j = 0; j < 3; ++j) {
                    temp[i] += moves2
                        [j][opp_history[n_moves - 1]]
                        [my_history[n_moves]][their_last]
                        [i]
                        + moves2
                        [my_history[n_moves - 1]][j]
                        [my_history[n_moves]][their_last]
                        [i];
                }
            }
            max_index = russrock_max(temp, 3);
            max_value = temp[max_index];
            if (0 < max_value) {
                n = 0;
                for (i = 0; i < 3; ++i) {
                    if (temp[i] == max_value) {
                        n_votes[i] += 500;
                        ++n;
                    }
                }
            }
        }

        if (1 <= n_moves) {
            for (i = 0; i < 3; ++i) {
                temp[i] = moves1
                    [my_history[n_moves]][their_last]
                    [i];
            }
            max_index = russrock_max(temp, 3);
            max_value = temp[max_index];
            if (0 < max_value) {
                n = 0;
                for (i = 0; i < 3; ++i) {
                    if (temp[i] == max_value) {
                        n_votes[i] += 100;
                        ++n;
                    }
                }
                if (n_moves_for_1 <= n_moves) break;
            }

            for (i = 0; i < 3; ++i) {
                temp[i] = 0;
                for (j = 0; j < 3; ++j) {
                    temp[i] += moves1
                        [j][their_last]
                        [i]
                        + moves1
                        [my_history[n_moves]][j]
                        [i];
                }
            }
            max_index = russrock_max(temp, 3);
            max_value = temp[max_index];
            if (0 < max_value) {
                n = 0;
                for (i = 0; i < 3; ++i) {
                    if (temp[i] == max_value) {
                        n_votes[i] += 50;
                        ++n;
                    }
                }
            }
        }

        {
            for (i = 0; i < 3; ++i) {
                temp[i] = moves0
                    [i];
            }
            max_index = russrock_max(temp, 3);
            max_value = temp[max_index];
            if (0 < max_value) {
                n = 0;
                for (i = 0; i < 3; ++i) {
                    if (temp[i] == max_value) {
                        n_votes[i] += 10;
                        ++n;
                    }
                }
            }
        }
    } while (0);

    max_index = russrock_max(n_votes, 3);
    for (i = 0; i < 3; ++i) {
        if (n_votes[i] < n_votes[max_index]) {
            n_votes[i] = 0;
        }
    }

    return (1 + biased_roshambo(n_votes[0]/(double)(n_votes[0] + n_votes[1]
 + n_votes[2]), n_votes[1]/(double)(n_votes[0] + n_votes[1] + n_votes[2]))) % 3;
}
/*  russrocker4  */
/**********************************************************************/


/*  Entrant:  Biopic (5)   Jonathan Schaeffer (Can)  */

/* RoShamBo -- Biopic version that switches between using opponent's and */
/* our history to decide on a strategy.                                  */
/*                                                                       */
/* Jonathan Schaeffer                                                    */
/* September 27, 1999    (debugged version, after the official event)    */

/* Shortcuts, because I am lazy */
#define ME           my_history
#define YOU          opp_history
#define TRIAL        ME [ 0 ]
#define MY_PLAY      ME [ TRIAL ]
#define YOU_PLAY     YOU[ TRIAL ]
#define JRANDOM_MOVE return( random() % 3 );
#define INFINITY     (1<<30)

/* Application dependent parameters */
#define WSIZE        25      /* Size of a losing margin? */
#define CSIZE        10      /* Storage inefficient */
#define EV_SCALE     5       /* Used to determine a "small" value */
#define WEIGHTED             /* Bias towards more rather than less context */

extern void bzero();

static int mult[ CSIZE ];

/* Support routines */

#define EV_TTL  ttl = ev[ rock ] + ev[ paper ] + ev[ scissors ];

int BiopicMove( int * wt )
{
    int ev[ 3 ], ttl, i;

    ev[ paper    ] = wt[ rock     ] - wt[ scissors ];
    ev[ rock     ] = wt[ scissors ] - wt[ paper    ];
    ev[ scissors ] = wt[ paper    ] - wt[ rock     ];

    /* Decide */

    /* Make small values 0 */
    EV_TTL
    for( i = 0; i < 3; i++ )
        if( ev[ i ] * EV_SCALE < ttl )
            ev[ i ] = 0;

    /* Make large values big */
    EV_TTL
    for( i = 0; i < 3; i++ )
        if( ev[ i ] * 5 / 3 >= ttl )
            ev[ i ] = 99999;

    /* Decide */
    EV_TTL
    if( ttl <= 0 )
        return( biased_roshambo( (double) 1.0/3, (double) 1.0/3 ) );
    else    return( biased_roshambo( (double) ev[ rock  ] / ttl,
                     (double) ev[ paper ] / ttl ) );
}

void BiopicWeight( int wt[], short int * context[], int * history )
{
    int i, j, ptr[ CSIZE ];

    /* Get indices into context */
    for( j = i = 0; i < CSIZE && TRIAL - i > 0; i++ )
        ptr[ i ] = ( j += history[ TRIAL - i ] * mult[ i ] ) * 3;

    /* Process context */
    wt[ rock ] = wt[ paper ] = wt[ scissors ] = 0;
    for( i = 0; i < CSIZE; i++ )
    {
        if( TRIAL - i <= 0 )
            continue;
        for( j = 0; j < 3; j++ )
            wt[ j ] += context[ i ][ ptr[ i ] + j ]
#ifdef WEIGHTED
                * mult[ i ]
#endif
                ;
    }
}


/* This is it! */

int biopic ()
{
    static int score = -INFINITY;
    static int gorandom, move[ 4 ], sc[ 4 ], freq[ 2 ][ 3 ];
    /* Short int limits matches to 32K */
    static short int * myh[ CSIZE ], * oph[ CSIZE ];

    int i, j, ix, wt[3];

    /*
     *
     * Initialize
     *
     */

    /* (1) First time the bot is run */
    if( score == -INFINITY )
    {
        for( i = 1, ix = 3; i < CSIZE; i++, ix *= 3 )
            mult[ i ] = ix;
        mult[ 0 ] = 1;
        for( i = 0, ix = 3; i < CSIZE; i++, ix *= 3 )
        {
            myh[ i ] = malloc( ix * sizeof(short int) * 3 );
            oph[ i ] = malloc( ix * sizeof(short int) * 3 );
        }
    }

    /* (2) First hand of a match */
    if( TRIAL == 0 )
    {
        score = gorandom = 0;
        for( i = 0; i < 4; sc[ i++ ] = 0 );
        for( i = 0; i < 3; i++ )
            freq[ 0 ][ i ] = freq[ 1 ][ i ] = 0;
        for( i = 0, ix = 3; i < CSIZE; i++, ix *= 3 )
        {
            bzero( myh[ i ], ix * sizeof(short int) * 3 );
            bzero( oph[ i ], ix * sizeof(short int) * 3 );
        }
    }

    /* (3) Last hand of the match */

    /* Statistics -- deleted */


    /* First hand - make a random move */
    if( TRIAL <= 0 )
        JRANDOM_MOVE



    /*
     *
     * Process previous game
     *
     */

    /* (1) How is the match going? */
         if( ( MY_PLAY - YOU_PLAY ==  1 ) ||
         ( MY_PLAY - YOU_PLAY == -2 ) )
        score += 1;
    else if( ( YOU_PLAY - MY_PLAY ==  1 ) ||
         ( YOU_PLAY - MY_PLAY == -2 ) )
        score += -1;

    /* (2) Save context */
    freq[ 0 ][ ME [ TRIAL ] ]++;
    freq[ 1 ][ YOU[ TRIAL ] ]++;

    /* (3) How good are our predictions? */
    if( TRIAL > 1 )
    {
        for( i = 0; i < 4; i++ )
            if( ( ( move[ i ] + 2 ) % 3 ) == YOU_PLAY )
                sc[ i ]++;
    }

    /* (4) Update context strings */
    for( j = YOU[TRIAL], i = 1; i <= CSIZE && TRIAL-i > 0; i++ )
        oph[ i-1 ][ j += YOU[ TRIAL-i ] * 3 * mult[ i-1 ] ]++;
    for( j = YOU[TRIAL], i = 1; i <= CSIZE && TRIAL-i > 0; i++ )
        myh[ i-1 ][ j += ME [ TRIAL-i ] * 3 * mult[ i-1 ] ]++;

    /* Periodically scale back results so that the program can */
    /* switch strategies.                      */
    if( ( TRIAL % 32 ) == 0 )
    {
        for( i = 0; i < 3; i++ )
        {
            freq[ 0 ][ i ] >>= 1;
            freq[ 1 ][ i ] >>= 1;
        }
        for( i = 0; i < 4; sc[ i++ ] >>= 1 );
    }



    /*
     *
     * Use 4 special cases and 4  prediction models
     *
     *
     */

    /* (1) First move */
    /* Taken care of above */

    /* (2) If down too far, go random */
    if( score < -WSIZE )
        JRANDOM_MOVE

    /* (3) Make a random move to confuse the opponent */
    if( gorandom )
    {
        if( (--gorandom) >= 8 )
            JRANDOM_MOVE
    }

    /* (4) If things not going well with our predicitons, make */
    /* random moves for a while to confuse the opponent        */
    if( score <= -10 && gorandom == 0 )
    {
        gorandom = 16;
        JRANDOM_MOVE
    }

    /* (5) Use tables to predict next move using opponent info */
    /* Prediction 1                                            */
    BiopicWeight( wt, oph, YOU );
    move[ 0 ] = BiopicMove( wt );

    /* (6) Use tables to predict next move using our info   */
    /* Prediction 2                                         */
    BiopicWeight( wt, myh, ME );
    move[ 1 ] = BiopicMove( wt );

    /* (7) Check the frequency of the opponent's actions    */
    /* Prediction 3                                         */
    move[ 2 ] = BiopicMove( &freq[ 0 ][ 0 ] );

    /* (8) Check the frequency of the opponent's actions    */
    /* Prediction 4                                         */
    move[ 3 ] = BiopicMove( &freq[ 1 ][ 0 ] );

    /* Finally, we decide which strategy to use             */
    /* Use maximum sc for the move                          */
    for( j = 0, i = 1; i < 4; i++ )
        if( sc[ i ] > sc[ j ] )
            j = i;
    /* Ta da */
    return( move[ j ] );
}
/**********************************************************************/


/*  Entrant:  Simple Modeller (7)   Don Beal (UK)

 The simple predictor counts the number of times r/p/s occurred
 after each of the possible move events.  In addition to the 9
 possible r/p/s combinations for the two players, counts are kept
 ignoring the player move, ignoring the opponent move, or both,
 leading to 16 sets of counts.  The predictor then selects the
 count set that has the most extreme distribution, and plays
 against that.  The play against a given distribution is obtained
 by calculating the expected return of each play, and selecting the
 play with the best return.
 
 The idea to select the most extreme distribution (instead of the
 distribution in which we have the greatest confidence) was an
 experiment - I thought it might promote information gathering
 plays, and aggressively exploit easily-predictable opponents
 earlier than cautious approaches would.  It had the accidental
 advantage of being harder to predict!
 
 The simple modeller keeps the same information as the simple
 predictor, but for both players.  It can therefore counter an
 opponent using a similar counting technique.  To choose the count
 set to play against, the simple modeller keeps track of past
 performance (the score we would have if we had used that count set
 for all the moves so far).  The simple modeller then plays against
 the count set with the highest score.  If no count set shows a
 positive score, it plays at random.
 
 Both programs exponentially decay their memory of past plays to
 improve performance against opponents who change their strategy
 over time.
 
 [Both programs were written hastily and not very readably - sorry
 about that!]
  --
  Don Beal
*/

int mod1bot()  /* Don Beal (UK) simple model builder */
{   static double c[96], d[96], fade=0.98;
    static double c0,c1,c2,u0,u1,u2,b;  int bm;
#define SETC(x) c0=c[x];c1=c[x+1];c2=c[x+2];
#define SETD(x) c0=d[x];c1=d[x+1];c2=d[x+2];
#define SETU u0=c2-c1;u1=c0-c2;u2=c1-c0;
#define SETBM b=u0;bm=0;if(u1>b){b=u1;bm=1;};if(u2>b){b=u2;bm=2;}
#define BEATBM bm=(bm+1)%3;
#define SCORE(m,o) (m==o?0:(((o+1)%3)==m?1:-1))
    int i,j,k,l,m,m1,o,o1, s, id;
    double q, qi, qj, qk, ql, qd;
    int history_length= my_history[0];
    if(history_length>0)
    { o = opp_history[history_length];
      m = my_history[history_length];
    }
    if(history_length>1)
    { o1 = opp_history[history_length-1];
      m1 = my_history[history_length-1];
    }
    if(history_length==0)
    { for(i=0;i<96;i++) c[i]=d[i]=0;   }
    if(history_length>1)
    { i=o1*24+m1*6; j=o1*24+3*6; k=3*24+m1*6; l=3*24+3*6;
      if(history_length>2)
      { if(c[i+3]>0)
                /* c[i+4]+=score(bplay(&c[i]),o); */
          { SETC(i); SETU; SETBM; c[i+4]+=SCORE(bm,o); c[i+5]+=1; }
        if(c[j+3]>0)
          { SETC(j); SETU; SETBM; c[j+4]+=SCORE(bm,o); c[j+5]+=1; }
        if(c[k+3]>0)
          { SETC(k); SETU; SETBM; c[k+4]+=SCORE(bm,o); c[k+5]+=1; }
        if(c[l+3]>0)
          { SETC(l); SETU; SETBM; c[l+4]+=SCORE(bm,o); c[l+5]+=1; }
      }
      c[i+o]+=1;  c[j+o]+=1;  c[k+o]+=1; c[l+o]+=1;
      c[i+3]+=1;  c[j+3]+=1;  c[k+3]+=1; c[l+3]+=1;
      i=m1*24+o1*6; j=m1*24+3*6; k=3*24+o1*6; l=3*24+3*6;
      if(history_length>2)
      { if(d[i+3]>0)
                /* md=bplay(&d[i]); d[i+4]+=score((md+1)%3,o); */
          { SETD(i); SETU; SETBM; BEATBM; d[i+4]+=SCORE(bm,o); d[i+5]+=1; }
        if(d[j+3]>0)
          { SETD(j); SETU; SETBM; BEATBM; d[j+4]+=SCORE(bm,o); d[j+5]+=1; }
        if(d[k+3]>0)
          { SETD(k); SETU; SETBM; BEATBM; d[k+4]+=SCORE(bm,o); d[k+5]+=1; }
        if(d[l+3]>0)
          { SETD(l); SETU; SETBM; BEATBM; d[l+4]+=SCORE(bm,o); d[l+5]+=1; }
      }
      d[i+m]+=1;  d[j+m]+=1;  d[k+m]+=1; d[l+m]+=1;
      d[i+3]+=1;  d[j+3]+=1;  d[k+3]+=1; d[l+3]+=1;
    }
    if(history_length>50)
      for(i=0;i<96;i++) { c[i]=c[i]*fade;  d[i]=d[i]*fade; }
    if(history_length==0)   return( random() % 3 );
    else if(history_length==1)    return( (o+1) % 3 );
    else
    { id=m*24+o*6;  SETD(id); SETU; SETBM; BEATBM;
      qd= d[id+5]>0? d[id+4]/d[id+5]:0;
      i=o*24+m*6; j=o*24+3*6; k=3*24+m*6; l=3*24+3*6;
      qi= c[i+5]>0? c[i+4]/c[i+5]:0;
      qj= c[j+5]>0? c[j+4]/c[j+5]:0;
      qk= c[k+5]>0? c[k+4]/c[k+5]:0;
      ql= c[l+5]>0? c[l+4]/c[l+5]:0;
      q=qi; s=i;
      if(qj>q) { q=qj; s=j; }
      if(qk>q) { q=qk; s=k; }
      if(ql>q) { q=ql; s=l; }
      if(qd>q && qd>0) return(bm);
      SETC(s); SETU; SETBM;
      if(q>0) return(bm);
      return( random()%3 );
    }
#undef SETC
#undef SETD
#undef SETU
#undef SETBM
#undef BEATBM
#undef SCORE
}
/**********************************************************************/


/*  Entrant:  Simple Predictor (14)   Don Beal (UK)  */

int predbot()
{
    static double c[64];  int history_length= my_history[0];
    int i,j,k,l,m,m1,o,o1, s,mr,mp,ms,mb;
    double q, qi, qj, qk, ql;
    if(history_length==0)
    { for(i=0;i<64;i++) c[i]=0;
      return( random() % 3 );
    }
    else {
    o = opp_history[history_length];
    m = my_history[history_length];
    if(history_length>1)
    { o1 = opp_history[history_length-1];
      m1 = my_history[history_length-1];
      i=o1*16+m1*4+o; j=o1*16+3*4+o; k=3*16+m1*4+o; l=3*16+3*4+o;
      c[i]+=1;  c[j]+=1;  c[k]+=1; c[l]+=1;
      c[i+3-o]+=1;  c[j+3-o]+=1;  c[k+3-o]+=1; c[l+3-o]+=1;
    }
    for(i=0;i<64;i++) c[i]=c[i]*0.98;
    i=o*16+m*4; j=o*16+3*4; k=3*16+m*4; l=3*16+3*4;
    for(qi=c[i],m=1;m<3;m++) if(c[i+m]>qi) qi=c[i+m];
    if (c[i+3] == 0.0) qi = DBL_MAX; else qi=qi/c[i+3]; /* mjg */
    for(qj=c[j],m=1;m<3;m++) if(c[j+m]>qj) qj=c[j+m];
    if (c[j+3] == 0.0) qj = DBL_MAX; else qj=qj/c[j+3]; /* mjg */
    for(qk=c[k],m=1;m<3;m++) if(c[k+m]>qk) qk=c[k+m];
    if (c[k+3] == 0.0) qk = DBL_MAX; else qk=qk/c[k+3]; /* mjg */
    for(ql=c[l],m=1;m<3;m++) if(c[l+m]>ql) ql=c[l+m];
    if (c[l+3] == 0.0) ql = DBL_MAX; else ql=ql/c[l+3]; /* mjg */
    q=qi; s=i;
    if(qj>q) { q=qj; s=j; }
    if(qk>q) { q=qk; s=k; }
    if(ql>q) { s=l; }
    mr= c[s+2]-c[s+1];
    mp= c[s]-c[s+2];
    ms= c[s+1]-c[s];
    mb=mr;  m=rock;
    if(mp>mb) { mb=mp;  m=paper; }
    if(ms>mb) m=scissors;
    return(m);
    }
}
/**********************************************************************/


/*  Entrant:  Robertot (8)   Andreas Junghanns (Ger)  */

int robertot ()
{
#define NHIST           10
#define NPREDICTS       2
#define STEPS           200     /* grains for the freq count % */
#define MAXVOTE         256     /* maximal vote for 0/100% */
#define ZERO            11.1    /* zero point for the distribution */

#define FUNC(x) ((x)*(x)*(x)*(x)*(x))
#define MAXR(x,y) ((x)>(y)?(x):(y))
#define MINR(x,y) ((x)<(y)?(x):(y))

    /* gather stats for counts of related events, NHIST back */
    static int hitsd[NHIST][3][3][3];   /* NHIST counts, for each combination */
    static int countd[NHIST][3][3];     /* history was seen how many times */
    int p,h,pos,rsb,h_rsb,o_rsb;
    int vote[3];
    static int incvote[STEPS+1];
    float index;

    if (opp_history[0] == 0) {
        memset(hitsd,0,sizeof(int)*NHIST*3*3*3);
        memset(countd,0,sizeof(int)*NHIST*3*3);
        for (index=((float)MAXVOTE)/FUNC(ZERO), p=0, h=ZERO; h>0; h--)
                incvote[p++] = -((int)((((float)FUNC(h))*index)+0.5));
        for (index=((float)MAXVOTE)/FUNC(STEPS-ZERO), h=ZERO; h<=STEPS; h++)
                incvote[p++] = ((int)((((float)FUNC(h-ZERO))*index)+0.5));
    }
    if (opp_history[0] >= NPREDICTS) {
        /* Only with enough data try to predict! */
        pos = opp_history[0];
        rsb = opp_history[pos];
        for (h=0; h<NHIST && (pos-(h+1))>0; h++) {
            countd[h][opp_history[pos-(h+1)]][my_history[pos-(h+1)]]++;
            hitsd [h][rsb][opp_history[pos-(h+1)]][my_history[pos-(h+1)]]++;
        }
        for (rsb=0; rsb<3; rsb++) vote[rsb]=0;
        /* Now, each history entry will vote for which move to play */
        for (rsb=0; rsb<3; rsb++) {
            for (h=0; h<NHIST && (pos-h)>0; h++) {
                o_rsb = opp_history[pos-h];
                h_rsb =  my_history[pos-h];
                if (countd[h][o_rsb][h_rsb]) {
                  index=((float)STEPS)*
                          hitsd[h][rsb][o_rsb][h_rsb]/countd[h][o_rsb][h_rsb];
                  vote[rsb] += incvote[(int)index];
                }
            }
        }
        h = MINR(vote[rock],vote[paper]);
        h = MINR(h,vote[scissors]);
        vote[rock] -= h; vote[paper] -= h; vote[scissors] -= h;
        h = MAXR(vote[rock],vote[paper]);
        h = MAXR(h,vote[scissors]);
        h = (h*3)/4;
        if (h==0) h++;
        vote[rock] /= h; vote[paper] /= h; vote[scissors] /= h;
        if (verboseLevel == 1)
                printf("%i %i %i\n", vote[rock], vote[paper], vote[scissors]);
        if (vote[rock] > vote[scissors] && vote[rock] > vote[paper])
            return(paper);
        else if (vote[scissors] > vote[paper] && vote[scissors] > vote[rock])
            return(rock);
        else if (vote[paper] > vote[rock] && vote[paper] > vote[scissors])
            return(scissors);
        else if (vote[rock] == vote[paper] && vote[paper] == vote[scissors])
            return( random() % 3);
        else if (vote[rock] == vote[paper])
            return(paper);
        else if (vote[paper] == vote[scissors])
            return(scissors);
        else if (vote[scissors] == vote[rock])
            return(rock);
        else return( random() % 3); /* should never happen */
    } else {
        return( random() % 3);
    }
}
/**********************************************************************/


/*  Entrant:  Boom (10)   Jack van Rijswijk (Net)  */

float boom_getrelevance(int r, int p, int s) {
  float best;

  best = s-p;
  if (r-s > best) best = r-s;
  if (p-r > best) best = p-r;

  return (best/(r+p+s+5));
}

int boom_rotate (int rps, int increment) {
  rps = (rps+increment) % 3;
  if (rps < 0) rps += 3;
  return(rps);
}

int boom_rps_result (int action1, int action2) {
  if (action1 == action2) return(0);
  if (boom_rotate(action1,1) == action2) return(-1);
  return(1);
}

int boom () {
  int boom_history = 27;
  float lambda = 0.95;

  static int boom_stats[28][4][4][3];
  int boom_secondary_stats[28][4][4][3];
  static int boom_overall;
  static int boom_gear;
  static float boom_gear_success[3];
  static float boom_recent_success;

  float bail_min,bail_max,bail;
  float bail_l_min,bail_l_max,bail_l_diff;

  int turn, action;
  int i,j;
  int opp_earlier,my_earlier,opp_last,my_last;
  float best,pred_r,pred_p,pred_s;

  int filter_opp, filter_me, filter_lag;
  
  pred_r = 0; pred_p = 0; pred_s = 0;
  filter_opp = 0; filter_me = 0; filter_lag = -1;
  turn = opp_history[0];

  bail_l_min = sqrt((1-lambda)/3);
  bail_l_max = sqrt(2*(1-lambda));
  bail_l_diff = bail_l_min - bail_l_max;

  if (turn == 0) { /* initialize arrays */
    int k,l;
    for (i=0; i<boom_history; i++) for (j=0; j<4; j++) for (k=0; k<4; k++)
      for (l=0; l<3; l++) boom_stats[i][j][k][l] = 0;
    boom_overall = 0;
    boom_gear = 0;
    for (i=0; i<3; i++) boom_gear_success[i] = 0;
    boom_recent_success = 0;
  }
  else { /* update statistics */

    opp_last = opp_history[turn];
    my_last = my_history[turn];

    for (i=0; i<boom_history; i++) {
      if (turn-i-1 > 0) {
        opp_earlier = opp_history[turn-i-1];
        my_earlier = my_history[turn-i-1];

        boom_stats[i][opp_earlier][my_earlier][opp_last]++;
        boom_stats[i][3][my_earlier][opp_last]++;
        boom_stats[i][opp_earlier][3][opp_last]++;
        boom_stats[i][3][3][opp_last]++;
      }
    }

    for (i=0; i<3; i++) boom_gear_success[i] *= lambda;
    boom_recent_success *= lambda;

    j = boom_rps_result(my_last,opp_last); /* win/tie/loss previous turn */
    if (j == -1) {
      boom_overall--;
      boom_recent_success -= 1-lambda;
      boom_gear_success[boom_gear] -= 1-lambda;
      boom_gear_success[boom_rotate(boom_gear,-1)] += 1-lambda;
    }
    else if (j == 1) {
      boom_overall++;
      boom_recent_success += 1-lambda;
      boom_gear_success[boom_gear] += 1-lambda;
      boom_gear_success[boom_rotate(boom_gear,+1)] -= 1-lambda;
    }
    else { 
      boom_gear_success[boom_rotate(boom_gear,+1)] += 1-lambda;
      boom_gear_success[boom_rotate(boom_gear,-1)] -= 1-lambda;
    }
  }

  /* check current context */
  best = 0;

  for (i=0; i<boom_history; i++) if (i<=turn) {
    int r,p,s,t;
    float w;

    opp_earlier = opp_history[turn-i]; my_earlier = my_history[turn-i];

    r = boom_stats[i][opp_earlier][my_earlier][0];
    p = boom_stats[i][opp_earlier][my_earlier][1];
    s = boom_stats[i][opp_earlier][my_earlier][2];
    w = boom_getrelevance(r,p,s);
    if (w>best) {
      best = w; t = r+p+s;
      pred_r = (float) r/t; pred_p = (float) p/t; pred_s = (float) s/t;
      filter_opp = opp_earlier; filter_me = my_earlier; filter_lag = i;
    }

    r = boom_stats[i][3][my_earlier][0];
    p = boom_stats[i][3][my_earlier][1];
    s = boom_stats[i][3][my_earlier][2];
    w = boom_getrelevance(r,p,s);
    if (w>best) {
      best = w; t = r+p+s;
      pred_r = (float) r/t; pred_p = (float) p/t; pred_s = (float) s/t;
      filter_opp = 3; filter_me = my_earlier; filter_lag = i;
    }

    r = boom_stats[i][opp_earlier][3][0];
    p = boom_stats[i][opp_earlier][3][1];
    s = boom_stats[i][opp_earlier][3][2];
    w = boom_getrelevance(r,p,s);
    if (w>best) {
      best = w; t = r+p+s;
      pred_r = (float) r/t; pred_p = (float) p/t; pred_s = (float) s/t;
      filter_opp = opp_earlier; filter_me = 3; filter_lag = i;
    }

    r = boom_stats[i][3][3][0];
    p = boom_stats[i][3][3][1];
    s = boom_stats[i][3][3][2];
    w = boom_getrelevance(r,p,s);
    if (w>best) {
      best = w; t = r+p+s;
      pred_r = (float) r/t; pred_p = (float) p/t; pred_s = (float) s/t;
      filter_opp = 3; filter_me = 3; filter_lag = i;
    }
  }
  
  /* filter statistics, get second-order stats */
  /*    only if we're less than 95% sure so far */

  if ((best < 0.95) && (filter_lag >= 0)) { 
    int k,l,r,p,s,t;
    float w;

    /* reset 2nd order stats */
    for (i=0; i<boom_history; i++) for (j=0; j<4; j++) for (k=0; k<4; k++)
      for (l=0; l<3; l++) boom_secondary_stats[i][j][k][l] = 0;

    /* get 2nd order stats */
    for (i=filter_lag+2; i<=turn; i++) {
      opp_earlier = opp_history[i-filter_lag-1];
      my_earlier = my_history[i-filter_lag-1];
      if (((filter_opp == 3) || (filter_opp == opp_earlier)) &&
          ((filter_me == 3) || (filter_me == my_earlier))) {
        opp_last = opp_history[i];
        for (j=0; j<boom_history; j++) {
          if (i-j-1 > 0) {
            opp_earlier = opp_history[i-j-1];
            my_earlier = my_history[i-j-1];
            boom_secondary_stats[j][opp_earlier][my_earlier][opp_last]++;
            boom_secondary_stats[j][3][my_earlier][opp_last]++;
            boom_secondary_stats[j][opp_earlier][3][opp_last]++;
            boom_secondary_stats[j][3][3][opp_last]++;
          }
        }
      }
    }

    /* any better information in there? */
    for (i=0; i<boom_history; i++) if (i<turn) {
      opp_earlier = opp_history[turn-i]; my_earlier = my_history[turn-i];

      r = boom_secondary_stats[i][opp_earlier][my_earlier][0];
      p = boom_secondary_stats[i][opp_earlier][my_earlier][1];
      s = boom_secondary_stats[i][opp_earlier][my_earlier][2];
      w = boom_getrelevance(r,p,s);
      if (w>best) {
          best = w; t = r+p+s; 
          pred_r = (float) r/t; pred_p = (float) p/t; pred_s = (float) s/t;
      }

      r = boom_secondary_stats[i][3][my_earlier][0];
      p = boom_secondary_stats[i][3][my_earlier][1];
      s = boom_secondary_stats[i][3][my_earlier][2];
      w = boom_getrelevance(r,p,s);
      if (w>best) {
        best = w; t = r+p+s;
        pred_r = (float) r/t; pred_p = (float) p/t; pred_s = (float) s/t;
      }

      r = boom_secondary_stats[i][opp_earlier][3][0];
      p = boom_secondary_stats[i][opp_earlier][3][1];
      s = boom_secondary_stats[i][opp_earlier][3][2];
      w = boom_getrelevance(r,p,s);
      if (w>best) {
        best = w; t = r+p+s;
        pred_r = (float) r/t; pred_p = (float) p/t; pred_s = (float) s/t;
      }
    }
  }

  /* got the predicted probabilities of r-p-s -- determine suggested action */
  best = pred_s - pred_p; action = rock;
  if ((pred_r - pred_s) > best) {best = pred_r - pred_s; action = paper;}
  if ((pred_p - pred_r) > best) action = scissors;

  /* modify the action according to the gears */
  best = boom_gear_success[0]; boom_gear = 0;
  if (boom_gear_success[1] > best) {
    best = boom_gear_success[1]; boom_gear = 1;
  }
  if (boom_gear_success[2] > best) {
    best = boom_gear_success[2]; boom_gear = 2;
  }
  action = (action + boom_gear)%3;

  /* ignore the action altogether if we're losing */
  /* global bailout */
  bail_min = (float) sqrt(turn) / sqrt(3.0);
  bail_max = (float) sqrt(turn) * sqrt(2.0);
  if (bail_min < bail_max)
    bail = (float) (bail_min + boom_overall) / (bail_min - bail_max);
  else bail = 0;

  /* local bailout */
  if ((boom_recent_success + bail_l_min) / bail_l_diff > bail)
    bail = (boom_recent_success + bail_l_min) / bail_l_diff;

  if (bail < 0) bail = 0;
  if (bail > 1) bail = 1;

  /* final decision: going random this turn? */
  if (flip_biased_coin(bail))
    action = biased_roshambo((float) 1/3,(float) 1/3);

  return(action);
}
/**********************************************************************/


/*  Entrant:  Shofar (11)   Rudi Cilibrasi (USA)  */

struct strat {
    int(*pname)();
    void (*init)();
    double score;
    int ivar[16];
    double dvar[16];
    int move;
};

struct strat s[128];
int sc = 0;
int chose = -1;
struct strat *cur;

void narcissus_init() {
    static int whoiam = 0;
    cur->ivar[0] = whoiam;
    whoiam = (whoiam+1) % 3;
}

int narcissus_play() {
    int mymove = my_history[my_history[0]];
    return (cur->ivar[0] + mymove) % 3;
}

void mirror_init() {
    static int whoiam = 0;
    cur->ivar[0] = whoiam;
    whoiam = (whoiam+1) % 3;
}

int mirror_play() {
    int hermove = opp_history[opp_history[0]];
    return (cur->ivar[0] + hermove) % 3;
}

void single_init() {
    static int whoiam = 0;
    cur->ivar[0] = whoiam;
    whoiam = (whoiam+1) % 3;
}

int single_play() {
    return cur->ivar[0];
}

void pattern_init() {
    int i;
    cur->ivar[0] = 1 + random() / (maxrandom / 5);
    cur->ivar[1] = 0;
    for (i = 0; i < cur->ivar[0]; ++i)
      {
        cur->ivar[i+2] = 3*(random() / maxrandom) ;
      }
}

int pattern_play() {
    int which = cur->ivar[cur->ivar[1]+2];
    cur->ivar[1] = (cur->ivar[1]+1) % cur->ivar[0];
    return which;
}

void update_score() {
    int i;
    double worstscore = 1000;
    int worstguy;
    int hermove, winmove, losemove;
    if (opp_history[0] == 0) return;
    hermove = opp_history[opp_history[0]];
    winmove = (hermove + 1) % 3;
    losemove = (hermove + 2) % 3;
    for (i = 0; i < sc; ++i)
      {
        int multiplier;
        multiplier = (i == chose) ? 4 : 3;
        if (s[i].move == winmove) s[i].score += multiplier;
        if (s[i].move == losemove) s[i].score -= multiplier;
        s[i].score *= 0.99;
      }
    for (i = 9; i < sc; ++i)
      if (s[i].score < worstscore)
        {
          worstguy = i;
          worstscore = s[i].score;
        }
    cur = s + worstguy;
    cur->init();
}

void enregister( void (*initfunc)(), int (*playfunc)())
{
    s[sc].pname = playfunc;
    s[sc].init = initfunc;
    cur = s+sc;
    cur->init();
    ++sc;
}

void shofar_init(void)
{
    int i;
    enregister(single_init, single_play);
    enregister(single_init, single_play);
    enregister(single_init, single_play);
    enregister(mirror_init, mirror_play);
    enregister(mirror_init, mirror_play);
    enregister(mirror_init, mirror_play);
    enregister(narcissus_init, narcissus_play);
    enregister(narcissus_init, narcissus_play);
    enregister(narcissus_init, narcissus_play);
    for (i = 0; i < 80; ++i)
        enregister(pattern_init, pattern_play);
    for (i = 0; i < sc; ++i)
        s[i].init();
}

int shofar(void)
{
    static int has_init = 0;
    double base=1.05;
    double total=0, r;
    int i;
    if (has_init == 0) { shofar_init(); has_init = 1; }
    update_score();
    for (i = 0; i < sc; ++i)
      {
        cur = s + i;
        cur->move = cur->pname();
        total += pow(base, s[i].score);
      }
    r = (random() / maxrandom) * total;
    for (i = 0; i < sc; ++i)
      {
        r -= pow(base, s[i].score);
        if (r <= 0) break;
      }
    assert(i >= 0 && i < sc);
    chose = i;
/*      printf("Her move was %d, my move was %d\n", opp_history[opp_history[0]], s[chose].move); */
    return s[chose].move;
}

/* naivete - poor roshambo player, written by cstone@pobox.com */
#define THRESH_BIGOM 0.42
#define THRESH_OKBEDUMB 0.75

enum { ROCK=0, PAPER, SCISSORS };

int triprescalc(int *x) {
    return((1<<*x)|(1<<*(x+1))|(1<<*(x+2)));
}

int win(int x) {
    if(x == ROCK) return PAPER;
    if(x == PAPER) return SCISSORS;
    return ROCK;
}

int filcompltrip(int *x) {
    int c=0;

    c=(1<<*x)|(1<<*(x+1));
    if((c^(1<<ROCK)) == 7) return ROCK;
    if((c^(1<<PAPER)) == 7) return PAPER;
    return SCISSORS;
}

int copychecklast(int offset) {

    if(opp_history[my_history[0]]==win(my_history[0]+offset)) 
        return(1);
    else return(0);
}

int naivete(void)
{
    /* imperative flags */
    static unsigned int c_trseqrpt, c_trresrpt, f_notwoseq, f_nothreeseq,
                                                f_bigom, f_okbedumb;
    static int f_cpyoffset=0, om=0;
    static float oc[3], pcts[3], tots[3], avgs[3];
    int tempint0, tempint1;
    float tempfloat0;

    if(my_history[0]==0) 
        c_trseqrpt=c_trresrpt=f_notwoseq=f_nothreeseq=f_bigom=f_cpyoffset=
          om=oc[0]=oc[1]=oc[2]=pcts[0]=pcts[1]=pcts[2]=tots[0]=tots[1]=
          tots[2]=avgs[0]=avgs[1]=avgs[2]=0;

    if(my_history[0]<=3) 
        return(SCISSORS);

    tempint0=triprescalc(&opp_history[my_history[0]-2]);

    if(opp_history[my_history[0]]==ROCK) oc[ROCK]++;
    if(opp_history[my_history[0]]==PAPER) oc[PAPER]++;
    if(opp_history[my_history[0]]==SCISSORS) oc[SCISSORS]++;

    switch(tempint0) {

    case 1:
    case 2:
    case 4:
        c_trseqrpt++;
        break;
    case 7:
        c_trresrpt++;
        break;
    default:
        c_trseqrpt=c_trresrpt=0;
        break;
    }

    if(c_trseqrpt > 2) 
        return(win(opp_history[my_history[0]-2]));

    if(c_trresrpt > 2)
        return(win(filcompltrip(&opp_history[my_history[0]-1])));

    if(!(my_history[0] % 3)) {
        if(f_cpyoffset && !copychecklast(f_cpyoffset))
            f_cpyoffset=0;
        }

        if(f_bigom && !(my_history[0] && 7)) {
            if(f_bigom >= THRESH_OKBEDUMB)
                f_okbedumb=1;
            else
                f_okbedumb=0;
        }

        if(!(my_history[0] % 23)) {
            int i;

            f_cpyoffset=0;
            for(i=0;i>=-4;i--) {
              if((opp_history[my_history[0]]==win(my_history[my_history[0]+i])) &&
                 (opp_history[my_history[0]-1]==win(my_history[my_history[0]+i-1])) &&
                 (opp_history[my_history[0]-2]==win(my_history[my_history[0]+i-2])) &&
                 (opp_history[my_history[0]-3]==win(my_history[my_history[0]+i-3])))
                 f_cpyoffset=i;
            }
        }
        /* i don't like this */
        if(!(my_history[0] % 27)) {
            int i=my_history[0]-26;
            f_notwoseq=f_nothreeseq=1;
            for(;i<=my_history[0];i++) 
                if(opp_history[i-1] == opp_history[i]) {
                    if((i<my_history[0])&&(opp_history[i]==opp_history[i+1])){
                        f_nothreeseq=0;
                        f_notwoseq=0;
                        break;
                    } else
                      f_notwoseq=0;
                }
        }
        if(!(my_history[0]%10)) {
            tempfloat0=my_history[0];

            if(my_history[0] > 10) {
                avgs[0]=tots[0]/((my_history[0]-10)/10);
                avgs[1]=tots[1]/((my_history[0]-10)/10);
                avgs[2]=tots[2]/((my_history[0]-10)/10);
            }
            tots[0]+=(pcts[0]=oc[0]/tempfloat0);
            tots[1]+=(pcts[1]=oc[1]/tempfloat0);
            tots[2]+=(pcts[2]=oc[2]/tempfloat0);
        }

        if(f_cpyoffset) 
            return(win(win(my_history[my_history[0]])));

        if(oc[ROCK] >= oc[PAPER]) {
            if((oc[SCISSORS] > oc[PAPER]) && (oc[SCISSORS] > oc[ROCK])) om=SCISSORS;
            else om=ROCK;
        } else {
            if(oc[SCISSORS] > oc[PAPER]) om = SCISSORS;
            else om=PAPER;
        }
        tempfloat0=my_history[0];
        if((my_history[0] > 30) && (oc[om]/tempfloat0 > THRESH_BIGOM)) 
            f_bigom=1;
        else
            f_bigom=0;

        switch(my_history[0] % 6) {

        case 4:
            if(f_bigom) {
                tempint0=win(om);
                break;
            }
            if(!(my_history[0] % 16)) {
                tempint0=win(om);
                break;
            }  

        case 5:
            tempint1=om;
            if((pcts[0]-avgs[0]) < (pcts[1]-avgs[1])) 
                tempint1=0;
            else
                tempint1=1;
            if((pcts[2]-avgs[2]) < (pcts[tempint1]-avgs[tempint1]))
                tempint1=2;

            tempint0=win(tempint1);
            break;
                
        case 3:
            if(my_history[0] % 12)
                tempint0=win(win(om));
            tempint0=win(om);
            break;

        case 2:
            if(f_bigom)
                tempint0=win(om);
            else            
                tempint0=win(my_history[my_history[0]]);
            break;

        case 1:
            if(f_okbedumb)
                tempint0=win(om);
            else
                tempint0=win(opp_history[my_history[0]]);
            break;

        case 0:
            tempint0=win(om);
            break;
        }       
        if(f_notwoseq && (tempint0==win(opp_history[my_history[0]])))
            tempint0=win(tempint0);
        
        if(f_nothreeseq && 
             (opp_history[my_history[0]] == opp_history[my_history[0]-1]) &&
             (tempint0==win(opp_history[my_history[0]])))
            tempint0=win(tempint0);      
                
        return(tempint0);
}
/**********************************************************************/


/*  Entrant:  ACT-R Lag2 (13)   Dan Bothell, C Lebiere, R West (USA)

 RoShamBo player submission by Christian Lebiere, Robert West, 
 and Dan Bothell 
 
 This player is based on an ACT-R (http://act.psy.cmu.edu) model
 that plays RoShamBo.  The model can be played against on the web 
 at http://act.psy.cmu.edu/ACT/ftp/models/RPS/index.html.
 
 suggested name "ACT-R Lag2"
 function name actr_lag2_decay
*/
/*
  C function that implements the math underlying the
  ACT-R (http://act.psy.cmu.edu) model of RPS by 
  Christian Lebiere and Robert West (Published in the 
  Proceedings of the Twenty-first Conference of the 
  Cognitive Science Society.)
  This model stores in long-term memory sequences of 
  moves and attempts to anticipate the opponent's 
  moves by retrieving from memory the most active sequence. 
  More information, and a web playable version avalable at:
  http://act.psy.cmu.edu/ACT/ftp/models/RPS/index.html
*/
int actr_lag2_decay (void)
{
  double frequencies[3],score,p,best_score=maxrandom;
 
  int back1 = 0,back2 = 0,i,winner,index=my_history[0];
        
  for(i=0;i<3;i++)
     frequencies[i]=pow(index + 1,-.5);
 
  if (index >= 2)
  {
     back2=opp_history[index - 1];
     back1=opp_history[index];
  }
 
  for(i=0;i<index;i++)
  {
     if (i >= 2 && opp_history[i - 1] == back2 && opp_history[i] == back1)
       frequencies[opp_history[i + 1]] +=  pow(index - i, -0.5); 
  }
                
  for (i=0;i<3;i++)
  {
     /*
      Approximates a sample from a normal distribution with mean zero
      and s-value of .25 [s = sqrt(3 * sigma) / pi]
     */
      
     do
     {
       p=random();
     }while(p == 0.0);
 
     p /= maxrandom;
     p= .25 * log ((1 - p) / p);
 
     /* end of noise calculation */
     score = p + log(frequencies[i]);
        
     if (best_score == maxrandom || score > best_score)
     {
       winner=i;
       best_score = score;
     }
  }
   return ((winner + 1) % 3);
}       
/**********************************************************************/


/*  Entrant:  Majikthise (15)   Markian Hlynka (Can)  */

int markov5 ()
{
#define markovLength 243
  /* This bot is designed to win the current match. */

    int i,j;
    int markovindex;
    int nonzeros;
    int score;
    double newprob, cumprob;
    int retval;     /* the value to return */
    static int windowSize=5;
    /* int markovLength=9; */ /*3^size*/
    static int wins, losses;
    static double percentWins,percentLosses, margin;

    static double MarkovChain[markovLength][3];
    static int Markovuse[markovLength];
    static int MarkovTally[markovLength][3];

    if (my_history[0]==0)   /* if we're just starting, init the array. */
    {
        for(i=0;i<markovLength;i++)         /* for every row */
        {
            Markovuse[i]=0;
            for(j=0;j<3;j++)            /* reset every column */
            {
              MarkovChain[i][j]=0.33;
              MarkovTally[i][j]=0;
            }
        }
        /* now set our watch vars and stats accumulators */
    wins=losses=0;
    percentWins=percentLosses=margin=0;

    }
    else
    {
      /* check if we won or lost on the last turn */
        if ((opp_history[opp_history[0]]+1)%3 == my_history[my_history[0]])
            wins++;
        else if ((opp_history[opp_history[0]]+2)%3 == my_history[my_history[0]])
            losses++;

        /* accumulate our stats       */
        percentWins = (double)wins/(double)my_history[0];
        percentLosses = (double)losses/(double)my_history[0];
    }/* else */

    /*******This is where we update the markov chain**************/

    /* regardless, update the markov chain. */

    if(opp_history[0]>windowSize)       /* if we're past P1.. remember, P1=P0 */
    {
        markovindex=0;
        for(i=windowSize;i>=1;i--)
            markovindex+=((i==1)?
                (opp_history[opp_history[0]-i]):(opp_history[opp_history[0]-i]*3));

        /* now if we haven't used the row before, zero it and put a one in the */
        /* right place */
        if (!Markovuse[markovindex])
        {
            Markovuse[markovindex]=1;
            for(j=0;j<3;j++)
                MarkovChain[markovindex][j]=0;
            MarkovChain[markovindex][opp_history[opp_history[0]]]=1.0;
            MarkovTally[markovindex][opp_history[opp_history[0]]]++;
        }/* if */
        else /* ah. it's been used before, so now we distribut it across all used ones. */
        {/* duh. don't forget to check that this is a new one */
            MarkovTally[markovindex][opp_history[opp_history[0]]]++;

            nonzeros=0;

            /* count how many have been used (are non-zero). */
            for(j=0;j<3;j++)
                nonzeros+=MarkovTally[markovindex][j];
            /* add one */
            newprob=1.0/((double)nonzeros);
                
            /* distribute that value among them. */
            for(j=0;j<3;j++)
              if (MarkovTally[markovindex][j]>0)
                MarkovChain[markovindex][j]=newprob*(double)MarkovTally[markovindex][j];
        }/* else */

    }

    /**********************/

    margin=percentWins-percentLosses;
    score=wins-losses;

    /* if we're more that 60% behind or ahead, bail. also, if we haven't done */
    /* even one move, don't use the markov chain if we don't have a previous */
    /* move to look up. */
    if ((my_history[0]<=windowSize)/*||(score<-50)*/)
        retval=(biased_roshambo(0.33333,0.33333));

    else
    {
      /* if we didn't bail, we use the markov chain */
      /* for now use random */
      /* retval=(biased_roshambo(0.33333,0.33333)); */