/* 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