/* ---------------------------------------------------------------------- */
/*                                                                        */
/*  Iterated Rating Program  (version 2.0)    Darse Billings, March 2001  */
/*                                                 updated November 2002  */
/*                                                                        */
/*  This program computes player ratings to match a given set of game     */
/*  outcomes, using an iterated application of a simple rating formula:   */
/*                                                                        */
/*            Performance Rating  =  400 * (W-L)/G + Avg                  */
/*   where:                                                               */
/*            W is the number of wins                                     */
/*            L is the number of losses                                   */
/*            G is the total number of games (including draws)            */
/*            Avg is the average rating of the opponents                  */
/*                (each with a maximum difference of 400)                 */
/*                                                                        */
/*   This is a variation of the provisional rating formula used by the    */
/*   Chess Federation of Canada, for players with fewer than 20 games.    */
/*                                                                        */
/*   For purposes of ranking, the Adjusted Rating accounts for the        */
/*   statistical significance of each player's record, using a basic      */
/*   +/- uncertainty factor of:                                           */
/*                                                                        */
/*            U  =  400 / sqrt(G)                                         */
/*                                                                        */
/*   This value is subtracted from the Performance Rating to obtain       */
/*   a lower bound, and is then re-normalized by adding the average       */
/*   noise factor (N) over all players:                                   */
/*                                                                        */
/*            Adjusted Rating  =  Perf - U + N                            */
/*                                                                        */
/*   This program was originally written for the games on Richard's       */
/*   PBeM server (http://www.gamerz.net/pbmserv/), but it can be used     */
/*   for almost any two-player game.  The code may be used and modified   */
/*   freely, as long as the original author credit is maintained.         */
/*                                                                        */
/*   There are no guarantees of any kind, and the results are intended    */
/*   for entertainment purposes only -- *please*, no wagering.  :-)       */
/*                                                                        */
/*     compile with the C math library, eg:  "gcc -O3 dirp2.c -lm"        */
/*                                                                        */
/* ---------------------------------------------------------------------- */

#include <stdio.h>
#include <stdlib.h>

                     /* parameters */

#define maxplayers   2000       /* maximum number of players to be rated */
#define maxgames     1000       /* maximum number of games per player */
#define mingames        1       /* minimum number of games for full rating */
#define norm       1600.0       /* normal (mean) rating of all players */
#define range       400.0       /* rating class (double) */
#define epsilon     0.010       /* convergence limit */

#define iterations   1000       /* maximum number of re-rating cycles */

#define TAB             9       /* ASCII tab character */
#define EOLN           10       /* ASCII end of line (CRLF) character */
#define buffersize    256       /* limit on input line length */
#define ssleng         10       /* short string length */
#define nameleng       40       /* full name length */

FILE * Data_File;

                     /* crosstable structure */
typedef struct {
  int  id;                      /* player number */
  char nick[ssleng];            /* nickname (max 10 chars) */
  char name[nameleng];          /* descriptive name (max 40 chars) */
  int  win[maxgames+1];         /* list of player's wins */
  int  loss[maxgames+1];        /* list of player's losses */
  int  draw[maxgames+1];        /* list of player's draws */
  double rating;                /* player's performance rating P */
  double uncertainty;           /* generic deviation U = range / sqrt(games) */
  double adjusted;              /* adjusted rating A = P - U + average Noise */
} Player_Table;

typedef double Ratings [maxplayers+1][iterations+1];

Player_Table xtable[maxplayers+1];  /* crosstable of all players */
Ratings ratings;                    /* iterative rating lists */

                     /* global variables */

int numplayers;                 /* number of players in the database */
int bwins, wwins, draws;        /* total Black or White wins in database */
int iteration;                  /* current generation */
double change;                  /* average change per iteration */
double max_change;              /* maximum change per iteration */
double noise;                   /* average uncertainty factor */

void Init_Crosstable ()
{
   int i, j;

   numplayers = 0;
   bwins = 0; wwins = 0; draws = 0;
   for (i = 0; i <= maxplayers; i++) {
      xtable[i].id = i;
      for (j = 0; j < ssleng; j++) {
         xtable[i].nick[j] = ' ';
      }
      for (j = 0; j < nameleng; j++) {
         xtable[i].name[j] = ' ';
      }
      for (j = 0; j <= maxgames; j++) {
         xtable[i].win[j] = 0;
         xtable[i].loss[j] = 0;
         xtable[i].draw[j] = 0;
      }
      xtable[i].rating = norm;
   }
}

void Init_Ratings ()
{
   int i, j;

   iteration = 0;
   for (i = 0; i <= maxplayers; i++) {
      ratings[i][0] = norm;
      for (j = 1; j <= iterations; j++) {
         ratings[i][j] = 0.0;
      }
   }
}

void Print_Ratings ()
{
   int i, j, l;

   l = 1;
   if (iterations > 5) { l = iterations - 5; }
   for (j = l; j <= iterations; j++) {
      printf(" %4d", j);
   }
   printf("\n");
   for (i = 1; i <= numplayers; i++) {
      for (j = l; j <= iterations; j++) {
         printf(" %4.0f", ratings[i][j]);
      }
      printf("\n");
   }
}

void Print_Line (char buffer[buffersize])
{
   int i, j;

   i = buffersize - 1;
   while (buffer[i] == ' ') { i--; }
   for (j = 0; j <= i; j++) {
      printf("%c", buffer[j]);
   }
   printf("\n");
}

void Print_SS (char sstring[ssleng])
{
   int i;

   for (i = 0; i < ssleng; i++) {
      printf("%c", sstring[i]);
   }
}

void Print_Name (char name[nameleng])
{
   int i, end;

   end = nameleng - 1;
   while ((end >= 0) && (name[end] == ' ')) { end--; }
   for (i = 0; i <= end; i++) {
      printf("%c", name[i]);
   }
}

void Print_Player_List ()
{
   int i, j, w, d, l;
   double wp, wwp;

   j = 0;
   printf("  ID Nickname   Games  W  L  D    WP     WWP  Rating\n");
   for (i = 1; i <= numplayers; i++) {
      printf(" %3d ", xtable[i].id);
      Print_SS (xtable[i].nick);
      w = xtable[i].win[0];
      l = xtable[i].loss[0];
      d = xtable[i].draw[0];
      printf(" %4d ", w+d+l);
      printf(" %2d %2d %2d", w, l, d);
      wp = (0.5 * (2*w + d)) / (w+d+l);
      printf("  %4.3f", wp);
      wwp = wp;
      if ((w+d+l) < mingames) {
         wwp = (((1.0*(mingames-(w+d+l)))/mingames) * (0.5)) +
               (((1.0*(w+d+l))/mingames) * ((0.5*(2*w + d))/(w+d+l)));
      }
      printf("  %4.3f", wwp);
      printf("  %4.0f", xtable[i].rating);
      printf("\n");
   }
}

void Print_Player (int pid)
{
   int w, l, d, g;
   double wwp;

   Print_SS (xtable[pid].nick);
   w = xtable[pid].win[0];
   l = xtable[pid].loss[0];
   d = xtable[pid].draw[0];
   g = w + l + d;

   printf(" %4d %3d %3d %2d", g, w, l, d);
   wwp = (0.5*d + w) / g;
   if (g < mingames) {
      wwp = wwp*((1.0*g)/mingames) + 0.5*((1.0*(mingames-g))/mingames);
   }
   printf("  %4.3f", wwp);
   printf("  %4.0f  ", xtable[pid].rating);
   Print_Name (xtable[pid].name);
   printf("\n");
}

void Print_Rating_List ()
{
   /* sorted, with nicknames and full names */

   int i, j, pid;
   double rlist[maxplayers];

   printf("\n Rank Nickname   Games  W   L  D    WWP  Rating     Name (Country)\n\n");

   for (i = 1; i <= numplayers; i++) {
      rlist[i] = xtable[i].rating;
   }
   
   for (i = 1; i <= numplayers; i++) {
      pid = 1;
      for (j = 1; j <= numplayers; j++) {
         if (rlist[j] > rlist[pid]) { pid = j; }
      }
      printf(" %3d  ", i);
      Print_Player (pid);
      rlist[pid] = 0.0;
   }
}

void Print_Player_Adjusted (int pid)
{
   int w, l, d, g;
   double wwp;

   Print_SS (xtable[pid].nick);
   w = xtable[pid].win[0];
   l = xtable[pid].loss[0];
   d = xtable[pid].draw[0];
   g = w + l + d;

   printf(" %4d %3d %3d %2d", g, w, l, d);
   wwp = (0.5*d + w) / g;
   if (g < mingames) {
      wwp = wwp*((1.0*g)/mingames) + 0.5*((1.0*(mingames-g))/mingames);
   }
   printf("  %4.3f", wwp);
   printf("  %4.0f", xtable[pid].rating);
   printf(" %3.0f", xtable[pid].uncertainty);
   printf("  %4.0f  ", xtable[pid].adjusted);
   Print_Name (xtable[pid].name);
   printf("\n");
}

void Print_Adjusted_Rating_List ()
{
   /* sorted by adjusted rating, Adj = Perf - Uncertainty + average Noise */
   /* (use mingames = 1) */

   int i, j, pid;
   double rlist[maxplayers];

   printf("\n Rank Nickname   Games  W   L  D   WWP   Perf +/-  ARtg  Name (Country)\n\n");

   for (i = 1; i <= numplayers; i++) {
      rlist[i] = xtable[i].adjusted;
   }
   
   for (i = 1; i <= numplayers; i++) {
      pid = 1;
      for (j = 1; j <= numplayers; j++) {
         if (rlist[j] > rlist[pid]) { pid = j; }
      }
      printf(" %3d  ", i);
      Print_Player_Adjusted (pid);
      rlist[pid] = 0.0;
   }
}

int SStrcmp (char sstr1[ssleng], char sstr2[ssleng])
{
   int i, same;

   same = 1;
   for (i = 0; i < ssleng; i++) {
      if (sstr1[i] != sstr2[i]) {
         same = 0;
      }
   }
   return (same);
}

int Find_Player (char nick[ssleng])
{
   int i, same, pid;

   pid = 0;
   i = 1;
   while (i <= numplayers) {
      same = SStrcmp (nick, xtable[i].nick);
      if (same) {
         pid = i;
         i = numplayers + 1;    /* early cut-off */
      }
      i++;
   }
   return (pid);
}

int Find_Add_Player (char nick[ssleng])
{
   int i, j, same, pid;

   pid = 0;
   i = 1;
   while (i <= numplayers) {
      same = SStrcmp (nick, xtable[i].nick);
      if (same) {
         pid = i;
         i = numplayers + 1;    /* early cut-off */
      }
      i++;
   }
   if (pid == 0) {              /* add new player */
      numplayers++;
      pid = numplayers;
      for (j = 0; j < ssleng; j++) {
         xtable[pid].nick[j] = nick[j];
      }
   }
   return (pid);
}

void Record_Game (char bnick[ssleng], char wnick[ssleng], char vnick[ssleng])
{
   int i, j, bid, wid, same;

   i = j = same = 0;

   bid = Find_Add_Player (bnick);
   wid = Find_Add_Player (wnick);

   same = SStrcmp (bnick, vnick);
   if (same) {
      bwins++;
      xtable[bid].win[0]++;
      i = xtable[bid].win[0];
      xtable[bid].win[i] = wid;

      xtable[wid].loss[0]++;
      i = xtable[wid].loss[0];
      xtable[wid].loss[i] = bid;
   }
   else {
      same = SStrcmp (wnick, vnick); 
      if (same) {
         wwins++;
         xtable[wid].win[0]++;
         i = xtable[wid].win[0];
         xtable[wid].win[i] = bid;

         xtable[bid].loss[0]++;
         i = xtable[bid].loss[0];
         xtable[bid].loss[i] = wid;
      }
      else {
         same = SStrcmp (vnick, "draw            "); 
         if (same) {
            draws++;
            xtable[bid].draw[0]++;
            i = xtable[bid].draw[0];
            xtable[bid].draw[i] = wid;

            xtable[wid].draw[0]++;
            i = xtable[wid].draw[0];
            xtable[wid].draw[i] = bid;
         }
         else {
            printf("Error: could not determine game result.\n");
         }
      }
   }
}

void Read_Game (char *buffer, int posn)
{
   /* uses fixed sized strings (padded with spaces) throughout */

   int i, j, tokens, same;
   char gameid[ssleng], bnick[ssleng], wnick[ssleng];
   char result[ssleng], vnick[ssleng];

   i = 0;
   /* clear string after NULL and convert end of line to a space */
   while ((i < buffersize) && (buffer[i] != 0)) { i++; }
   for (j = i; j < buffersize; j++) {
      buffer[j] = ' ';
   }
   for (j = 0; j < buffersize; j++) {
      if (buffer[j] == EOLN) {
         buffer[j] = ' ';
      }
   }
   /* count tokens, there should be six, as in:
      game 6314 sbateman         ddyer            0-1 ddyer
   */
   tokens = 0;
   if (buffer[0] != ' ') { tokens++; }
   for (i = 1; i < buffersize; i++) {
      if ((buffer[i-1] == ' ') && (buffer[i] != ' ')) { tokens++; }
   }
   if (tokens != 6) {
      printf("Error: game entry does not have six fields:\n");
      Print_Line (buffer);
      return;
   }
   for (i = 0; i < ssleng; i++) {
      gameid[i] = ' ';
      bnick[i] = ' ';
      wnick[i] = ' ';
      result[i] = ' ';
      vnick[i] = ' ';
   }

   i = posn;
   while (buffer[i] == ' ') { i++; }
   j = 0;
   while ((buffer[i] != ' ') && (j < ssleng)) {
      gameid[j] = buffer[i]; j++; i++;
   }
   while (buffer[i] == ' ') { i++; }
   j = 0;
   while ((buffer[i] != ' ') && (j < ssleng)) {
      bnick[j] = buffer[i]; j++; i++;
   }
   while (buffer[i] == ' ') { i++; }
   j = 0;
   while ((buffer[i] != ' ') && (j < ssleng)) {
      wnick[j] = buffer[i]; j++; i++;
   }
   while (buffer[i] == ' ') { i++; }
   j = 0;
   while ((buffer[i] != ' ') && (j < ssleng)) {
      result[j] = buffer[i]; j++; i++;
   }
   while (buffer[i] == ' ') { i++; }
   j = 0;
   while ((buffer[i] != ' ') && (j < ssleng)) {
      vnick[j] = buffer[i]; j++; i++;
   }
   /* more consistency checking */
   if ((result[0] == '1') && (result[1] == '-') && (result[2] == '0')) {
      same = SStrcmp (bnick, vnick);
      if (same != 1) {
         printf("Warning: 1-0 result inconsistent with named winner:\n");
         Print_Line (buffer);
      }
   }
   else if ((result[0] == '0') && (result[1] == '-') && (result[2] == '1')) {
      same = SStrcmp (wnick, vnick);
      if (same != 1) {
         printf("Warning: 0-1 result inconsistent with named winner:\n");
         Print_Line (buffer);
      }
   }
   else if ((result[0] == '=') && (result[1] == '-') && (result[2] == '=')) {
      same = SStrcmp (vnick, "draw            ");
      if (same != 1) {
         printf("Warning: =-= result inconsistent with named draw:\n");
         Print_Line (buffer);
      }
   }
   else {
      printf("Warning: non-standard result string (use 1-0 0-1 or =-=).\n");
      Print_Line (buffer);
   }
   Record_Game (bnick, wnick, vnick);
   return;
}

void Read_Name (char *buffer, int posn)
{
   int i, j, tokens, pid;
   char pnick[ssleng];

   i = 0;
   /* clear string after NULL and convert end of line to a space */
   while ((i < buffersize) && (buffer[i] != 0)) { i++; }
   for (j = i; j < buffersize; j++) {
      buffer[j] = ' ';
   }
   for (j = 0; j < buffersize; j++) {
      if (buffer[j] == EOLN) {
         buffer[j] = ' ';
      }
   }
   /* count tokens, there should be at least three, as in:
      name mona             Mona (computer program) (Canada)
   */
   tokens = 0;
   if (buffer[0] != ' ') { tokens++; }
   for (i = 1; i < buffersize; i++) {
      if ((buffer[i-1] == ' ') && (buffer[i] != ' ')) { tokens++; }
   }
   if (tokens < 3) {
      printf("Error: name entry does not have at least three fields:\n");
      Print_Line (buffer);
      return;
   }
   for (i = 0; i < ssleng; i++) {
      pnick[i] = ' ';
   }

   i = posn;
   while (buffer[i] == ' ') { i++; }
   j = 0;
   while ((buffer[i] != ' ') && (j < ssleng)) {
      pnick[j] = buffer[i]; j++; i++;
   }
   while (buffer[i] == ' ') { i++; }

   pid = Find_Player (pnick);
   if (pid == 0) {              /* player must already have a game entry */
      if (0) {                  /* 0 = silent, 1 = verbose */
         printf("Error: name entry does not correspond to a known player:\n");
         Print_Line (buffer);
      }
      return;
   }
   for (j = 0; j < nameleng; j++) {
      xtable[pid].name[j] = buffer[i];
      i++;
   }
   return;
}

int Read_Line (char *buffer)
{
   if ( fgets( buffer, buffersize, Data_File ) == NULL ) {
      return(-1);  /* reached end of file */
   }

   if ( strlen(buffer) > buffersize-1 ) {
      printf("Warning: input exceeds maximum line length (%d).\n", buffersize);
   }
   return(0);
}
 
void Read_Data ()
{
   int i, lines, games, names, comms, done;
   char buffer[buffersize];

   done = 0; lines = 0; games = 0; names = 0; comms = 0;
   while (done == 0) {
      done = Read_Line (buffer);
      if (done == 0) {
         lines++;
         /* convert tab characters into spaces */
         for (i = 0; i < buffersize; i++) {
            if (buffer[i] == TAB) { buffer[i] = ' '; }
         }
         i = 0;
         while (buffer[i] == ' ') { i++; }
         if ((buffer[i] == 'g') && (buffer[i+1] == 'a') &&
             (buffer[i+2] == 'm') && (buffer[i+3] == 'e')) {
            games++;
            Read_Game (buffer, i+4);
         }
         else if ((buffer[i] == 'n') && (buffer[i+1] == 'a') &&
             (buffer[i+2] == 'm') && (buffer[i+3] == 'e')) {
            names++;
            Read_Name (buffer, i+4);
         }
         else if ((buffer[i] == 'c') && (buffer[i+1] == 'o') &&
             (buffer[i+2] == 'm') && (buffer[i+3] == 'm')) {
            comms++;
         }
         else { printf("Warning: unknown line type, ignored.\n"); }
      }
   }
   printf(" finished reading %d lines, with %d games,", lines, games);
   /* printf(" %d names, and %d comments.\n", names, comms); */
   printf(" and %d names.\n", names);
}

void Compute_Rating (int pid)
{
   int i, prev, opp, w, l, d, g;
   double sum, avg, rtg, ortg, diff, new, chg;

   sum = 0.0;
   prev = iteration - 1;
   rtg = ratings[pid][prev];
   w = xtable[pid].win[0];
   for (i = 1; i <= w; i++) {
      opp = xtable[pid].win[i];
      ortg = ratings[opp][prev];
      if ((ortg - rtg) > range) { ortg = rtg + range; }
      else if ((rtg - ortg) > range) { ortg = rtg - range; }
      sum += ortg;
   }
   l = xtable[pid].loss[0];
   for (i = 1; i <= l; i++) {
      opp = xtable[pid].loss[i];
      ortg = ratings[opp][prev];
      if ((ortg - rtg) > range) { ortg = rtg + range; }
      else if ((rtg - ortg) > range) { ortg = rtg - range; }
      sum += ortg;
   }
   d = xtable[pid].draw[0];
   for (i = 1; i <= d; i++) {
      opp = xtable[pid].draw[i];
      ortg = ratings[opp][prev];
      if ((ortg - rtg) > range) { ortg = rtg + range; }
      else if ((rtg - ortg) > range) { ortg = rtg - range; }
      sum += ortg;
   }
   g = w + l + d;
   avg = sum / g;
   diff = range * (w - l) / g;
   new = avg + diff;
   if (g < mingames) {   /* normalize if fewer than mingames played */
      new = ((new * g)/mingames) + (norm * (mingames - g))/mingames;
   }
   ratings[pid][iteration] = new;
   chg = rtg - new;
   if (chg < 0) { chg = new - rtg; }
   change += chg;
   if (chg > max_change) { max_change = chg; }
   return;
}

void Compute_Ratings ()
{
   int i, games;

   max_change = epsilon + 1;
   while ((iteration < iterations) && (max_change >= epsilon)) {
      iteration++;
      change = 0.0;
      max_change = 0.0;
      for (i = 1; i <= numplayers; i++) {
         Compute_Rating (i);
      }
      if (0) {
         printf (" after iteration %2d, maximum change = %5.3f, average change = %5.3f\n",
                   iteration, max_change, change / numplayers);
      }
   }
   noise = 0.0;
   for (i = 1; i <= numplayers; i++) {
      xtable[i].rating = ratings[i][iteration];
      games = xtable[i].win[0] + xtable[i].loss[0] + xtable[i].draw[0];
      xtable[i].uncertainty = range / sqrt(games);
      noise += xtable[i].uncertainty;
   }
   noise = noise / numplayers;
   if (1) {
      printf (" after iteration %2d, maximum change = %5.3f, average change = %5.3f\n",
                iteration, max_change, change / numplayers);
      printf (" average noise = %5.1f\n", noise);
   }
   for (i = 1; i <= numplayers; i++) {
      xtable[i].adjusted = xtable[i].rating - xtable[i].uncertainty + noise;
   }
}

int main()
{
   if ((Data_File = fopen ("game-results", "r" )) == NULL ) {
      printf( "Cannot open input file: game-results\n" );
      exit ( -1 );
   }
   printf("\n Darse's iterated rating program (version 2.0).\n");
   printf(" mingames = %d,  norm = %5.1f,  range = %5.1f,  epsilon = %5.3f\n",
            mingames, norm, range, epsilon);
   Init_Crosstable ();
   Init_Ratings ();
   Read_Data ();
   printf(" players = %d,", numplayers);
   printf("  P1wins P2wins Draws: %d %d %d,", bwins, wwins, draws);
   printf("  P1 Win Freq = %4.3f\n", (0.5*draws + bwins) / (bwins+wwins+draws));
   Compute_Ratings ();
   /* Print_Player_List (); */
   /* Print_Rating_List (); */
   Print_Adjusted_Rating_List ();

   return (0);
}