/*  Entrant:  PredictorArrayBot     George B. Moody (george@mit.edu)

 This mini-program maintains an array of predictors, tracks the recent
 performance of each predictor, and uses the best-performing predictor to intuit
 the opponent's next move.  The predictors are simply the last 15 moves made by
 each player (and the increments of each of these).  Hence on any given move,
 exactly one-third of the predictions will be winning moves, one-third will tie,
 and one-third will lose.  The trick is to figure out which predictors (if any)
 are reliable.  PredictorArrayBot uses the past performance of each predictor to
 assess its reliability.  For example, against a non-exploitive opponent that
 makes (say) 7 random moves and then repeats those moves, PredictorArrayBot
 quickly identifies the opponent's seventh previous move as a good predictor of
 its next move.  PredictorArrayBot's own moves are often effective predictors of
 an exploitive opponent's moves.

 I coded PredictorArrayBot in about half an hour, and spent a couple of hours
 tuning up its magic numbers (16, one of the factors of NP, which determines the
 depth of the search for a good predictor;  and 24, the weighting constant in the
 ARMA filter, which determines how much extra emphasis is given the most recent
 moves).  PredictorArrayBot's performance against the test suite is, sad to say,
 much too sensitive to the values of these numbers, so I was pleasantly surprised
 at its somewhat-better-than-middling performance in this year's competition.

 One of my research interests is identification and modelling of cardiac
 arrhythmias (abnormal heart rhythms).  The inspiration for PredictorArrayBot
 comes from an idea for detecting atrial fibrillation, an arrhythmia that is
 characterized by seemingly unpredictable time intervals between heart beats.
 Interestingly, in a healthy person, the previous interval is usually not the
 best predictor of the next one, because respiration causes the healthy heart to
 speed up and slow down with each breath;  thus if one breath lasts for (say) 6
 heart beats, the sixth previous beat interval is likely to be a good predictor
 of the next one.  In most abnormal rhythms, unusually short or (less often) long
 intervals repeat in predictable patterns.  So the idea (first proposed by Paul
 Schluter in his 1980 MIT Ph.D. thesis) is to measure the absolute differences
 between the most recent interval and each of the previous N intervals (the
 prediction errors), and to select as the best predictor the one for which the
 prediction error is smallest on average;  then if _none_ of the predictors has
 a small average error, the rhythm is probably atrial fibrillation.  This
 detection algorithm does reasonably well, although better methods are known. 

 */

#define NP      (6*16)	/* the number of predictors */

int predictorarraybot()
{
    static double err[NP], smallest_err;
    static int choice, i, imax, mv, pred[NP], score;

    if ((mv = my_history[0]) == 0)
        for (i = score = 0; i < NP; i++)	/* first move only */
            err[i] = pred[i] = 0;

    /* Avoid using predictors that haven't been initialized. */
    imax = (mv < NP/6) ? mv*6-1 : NP-1;

    /* Update the predictor array. */
    for (i = imax; i >= 0; i--)
	/* Shift the older moves and their increments through the array,
	   discarding the oldest ones. */
        if (i > 5) pred[i] = pred[i-6];
	/* Move in the opponent's latest move and its increments ... */
        else if (i > 2) pred[i] = (opp_history[mv]+i)%3;
	/* ... and PredictorArrayBot's own move and increments. */
        else pred[i] = (my_history[mv]+i)%3;

    /* Update the error array and find the best predictor. */
    for (i = smallest_err = 6; i <= imax; i++) {
        err[i] += (((opp_history[mv] - pred[i] + 3) % 3 + 1) % 3 - err[i])/24.;
	/* No, that wasn't line noise!  The expression
	           ((opp_history[mv] - pred[i] + 3) % 3 + 1) % 3
           (let's call it e0) evaluates to:
	     0 if pred[i] would have defeated the opponent's latest move,
	     1 if pred[i] would have tied, or
	     2 if pred[i] would have lost.
	   So everything after the '+=' is a fraction of the difference between
	   e0 and err[i].  What's happening above is thus:
	     err[i] = (1/24)*e0 + (1 - 1/24)*err[i]
	   In other words, err[i] is an autoregressive moving average (ARMA)
	   filter applied to the sequence of errors (e0) for pred[i].  The
	   magic number 24 is related to the characteristic time constant of the
	   filter. */

        if (err[i] < smallest_err) {
            smallest_err = err[i];
            choice = pred[i-6];		/* Save the best move found so far. */
        }
    }

    /* The next line keeps a running tally of how we're doing so far. */
    score += ((((my_history[mv] - opp_history[mv]) + 3) % 3) + 1) % 3 - 1;

    /* The first two moves, and any moves made if we seem to be losing, are
       random;  otherwise, we use the choice from the best predictor. */
    return ((mv > 1 && score >= -trials/25) ? choice : (random() % 3));
}

#undef NP