//
// ASP.java
//
import java.util.*;
/**
ASP is a program for testing the stability of adversarial
sequence prediction under simple table driven learning
algorithms. Copyright (C) 2007 Bill Hibbard.
*/
public class ASP extends Object {
static boolean debug = false;
// here instability means one competitor getting and keeping all the resources
// possibility of instability is sensitive to RANDOM_INTERVAL and WIN_VALUE
// RANDOM_INTERVAL too small enables loser to come back, stabilizing game
// but RANDOM_INTERVAL too large creates a deterministic outcome
// instability happens faster for smaller MAX_LENGTH
// instability requires non-random in case of 'no result'
// instability takes a long time for next_2 algorithm and large MAX_LENGTH
// unless a large WIN_VALUE is used too
// instability is impossible for too large GROWTH_PER_PRINT
// max history length in table - should be <= 8
static final int MAX_LENGTH = 5;
// value of win/loss in table size
static final int WIN_VALUE = 2;
// interval of games between printing table sizes
static final int PRINT_INTERVAL = 100;
// maximum count in table
static final int MAX_COUNT = 1000000000;
// expected interval of games between random plays
static final int RANDOM_INTERVAL = 100;
// initial proportion of table space used
static final float INIT_TABLE = 0.2f;
// initial advantage to Evader (1.0f for even)
static final float E_ADVANTAGE = 1.0f;
// growthrate of total table, per PRINT_INTERVAL
static final float GROWTH_PER_PRINT = 0.01f;
static final float random_test = 1.0f / RANDOM_INTERVAL;
/* table layout
length = 0 -> 0 to 0 length_to_size(0) = 1
length = 1 -> 1 to 4 length_to_size(1) = 5
length = 2 -> 5 to 20 length_to_size(2) = 21
length = 3 -> 21 to 84 length_to_size(3) = 85
length = n -> (4^n-1)/3 to ((4^(n+1)-1)/3)-1
length = MAX_LENGTH -> (4^MAX_LENGTH-1)/3 to ((4^(MAX_LENGTH+1)-1)/3)-1
NOTE lengths 0 and 1 are useless
*/
static final int TABLE_SIZE = length_to_size(MAX_LENGTH) - 1;
static final int[] size_to_length = new int[TABLE_SIZE+1];
static final Random random = new Random();
// bit masks for history lengths
static final int[] record_masks = new int[MAX_LENGTH+1];
static final int[] lookup_masks = new int[MAX_LENGTH+1];
Predictor p;
Evader e;
public static void main(String args[]) {
if (debug) System.out.println("MAX_LENGTH = " + MAX_LENGTH +
" TABLE_SIZE = " + TABLE_SIZE);
for (int j=0; j<=MAX_LENGTH; j++) {
for (int i=length_to_size(j-1); i= 0) {
// table position is available (negative indicates not available)
// simply keep count of various histories
table[tp]++;
if (table[tp] > MAX_COUNT) {
// if count exceeds max, halve all counts in group of 4
// (4 combinations of values in most recent turn)
int bp = table_position(len, position & lookup_masks[len]);
table[bp] = table[bp] / 2;
table[bp + 1] = table[bp + 1] / 2;
table[bp + 2] = table[bp + 2] / 2;
table[bp + 3] = table[bp + 3] / 2;
}
}
}
// do occasional random next symbol
if (random.nextFloat() < random_test) {
int rv = (random.nextFloat() > 0.5f) ? one : zero;
if (debug) System.out.println(id + "random = " + rv);
return rv;
}
// now compute next symbol
// hist is history shifted one move back in time
int hist = history << 2;
int hist_length = history_length + 1;
if (hist_length >= 16) hist_length--;
max_len = Math.min(MAX_LENGTH, hist_length);
// try longer histories first
for (int len=max_len; len>=2; len--) {
int position = hist & lookup_masks[len];
int tp = table_position(len, position);
if (debug) System.out.println(id + "LOOKUP: len = " + len + " position = "
+ position + " table[" + tp + "] = " + table[tp]);
if (table[tp] >= 0) {
// table position is available (negative indicates not available)
// zeros = count of histories in which other played 0 after current history
int zeros = table[tp] + table[tp + self_select];
// ones = count of histories in which other played 1 after current history
int ones =
table[tp + other_select] + table[tp + self_select + other_select];
if (debug) System.out.println(id + "zeros = " + table[tp] + " + " +
table[tp + self_select] + " ones = " +
table[tp + other_select] + " + " +
table[tp + self_select + other_select] +
" self_select = " + self_select +
" other_select = " + other_select);
if (zeros == 0 && ones == 0) continue; // no counts, try shorter history
// pick next move based on comparing history counts
// ties go to 'one' - slightly favors Evader?
return (zeros > ones) ? zero : one;
} // end if (table[tp] >= 0)
}
// no result
if (debug) System.out.println(id + "no result: 0");
// 'return 0' is a very slight advantage for the Predictor
// 'return zero' would be a very slight advantage for the Evader
return 0;
// using a random return here enables loser to get back in the game
// return (random.nextFloat() > 0.5f) ? one : zero;
} // end next_1 method
// second algorithm
// compute next symbol, and record recent history in table
final int next_2(int history, int history_length) {
// first increment table positions for history
int max_len = Math.min(MAX_LENGTH, history_length);
for (int len=2; len<=max_len; len++) {
int position = history & record_masks[len];
int tp = table_position(len, position);
if (debug) System.out.println(id + "RECORD: len = " + len + " position = " +
position + " table[" + tp + "] = " + table[tp]);
if (table[tp] >= 0) {
// table position is available (negative indicates not available)
// keep count of various histories
table[tp]++;
if (debug) {
int po = table_position(len, (position ^ other_select));
int pos = table_position(len, (position ^ 3));
System.out.println(id + "tp = " + tp + " po = " + po + " pos = " + pos);
}
// clear counts for opposite value from other
table[table_position(len, (position ^ other_select))] = 0;
// clear counts for opposite value from other (and opposite
// value from self - note 3 = self_select + other_select)
table[table_position(len, (position ^ 3))] = 0;
}
}
// do occasional random next symbol
if (random.nextFloat() < random_test) {
int rv = (random.nextFloat() > 0.5f) ? one : zero;
if (debug) System.out.println(id + "random = " + rv);
return rv;
}
// now compute next symbol
// hist is history shifted one move back in time
int hist = history << 2;
int hist_length = history_length + 1;
if (hist_length >= 16) hist_length--;
int margin = 0;
int choice = 0;
max_len = Math.min(MAX_LENGTH, hist_length);
// try longer histories first
for (int len=max_len; len>=2; len--) {
int position = hist & lookup_masks[len];
int tp = table_position(len, position);
if (debug) System.out.println(id + "LOOKUP: len = " + len + " position = " +
position + " table[" + tp + "] = " + table[tp]);
if (table[tp] >= 0) {
// table position is available (negative indicates not available)
// zeros = count of histories in which other played 0 after current history
int zeros = table[tp] + table[tp + self_select];
// ones = count of histories in which other played 1 after current history
int ones =
table[tp + other_select] + table[tp + self_select + other_select];
if (debug) System.out.println(id + "zeros = " + table[tp] + " + " +
table[tp + self_select] + " ones = " +
table[tp + other_select] + " + " +
table[tp + self_select + other_select] +
" self_select = " + self_select +
" other_select = " + other_select);
if (zeros == 0 && ones == 0) continue; // no counts, try shorter history
if (zeros > 0 && ones > 0) {
// cannot happen because of clearing counts for opposite value from other
System.out.println("IMPOSSIBLE");
System.exit(0);
}
// pick next move based on comparing history counts
if (zeros > ones) {
// choice weight is count plus length
int m = (zeros - ones) + len;
if (m > margin) {
margin = m;
choice = zero;
if (debug) System.out.println(id + "margin = " + margin + " choice = " + choice);
}
}
else { // ones > zeros (cannot be == unless both 0)
// choice weight is count plus length
int m = (ones - zeros) + len;
if (m > margin) {
margin = m;
choice = one;
if (debug) System.out.println(id + "margin = " + margin + " choice = " + choice);
}
}
} // end if (table[tp] >= 0)
} // end for (int len=max_len; len>=2; len--)
if (margin > 0) return choice;
// no result
if (debug) System.out.println(id + "no result: 0");
// 'return 0' is a very slight advantage for the Predictor
// 'return zero' would be a very slight advantage for the Evader
return 0;
// using a random return here enables loser to get back in the game
// return (random.nextFloat() > 0.5f) ? one : zero;
} // end next_2 method
// remove n spaces (4*n ints) from table
final void remove(int n) {
if (n > table_size / 4) n = table_size / 4;
int left = n;
while (left > 0) {
int l = size_to_length[table_size];
int lo = length_to_size(l - 1) - 1;
int hi = length_to_size(l) - 1;
int len = (hi - lo) / 4;
int used = (table_size - lo) / 4;
int m = Math.min(used, left);
int k = (int) (len * random.nextFloat());
while (m > 0) {
if (k >= len) k = k - len;
int j = lo + 4 * k;
if (table[j+1] >= 0) {
if (debug) System.out.println(id + "REMOVE: j = " + j + " table_size = " +
table_size + " l = " + l + " lo = " + lo +
" k = " + k);
table[j+1] = -1;
table[j+2] = -1;
table[j+3] = -1;
table[j+4] = -1;
m--;
left--;
table_size = table_size - 4;
}
k++;
} // end while ((m > 0)
} // end while (left > 0)
} // end remove method
// add n spaces (4*n ints) to table
final void add(int n) {
if (n > (TABLE_SIZE - table_size) / 4) n = (TABLE_SIZE - table_size) / 4;
int left = n;
while (left > 0) {
int l = size_to_length[table_size + 4];
int lo = length_to_size(l - 1) - 1;
int hi = length_to_size(l) - 1;
int len = (hi - lo) / 4;
int unused = (hi - table_size) / 4;
int m = Math.min(unused, left);
int k = (int) (len * random.nextFloat());
while (m > 0) {
if (k >= len) k = k - len;
int j = lo + 4 * k;
if (table[j+1] < 0) {
if (debug) System.out.println(id + "ADD: j = " + j + " table_size = " +
table_size + " l = " + l + " lo = " + lo +
" k = " + k);
table[j+1] = 0;
table[j+2] = 0;
table[j+3] = 0;
table[j+4] = 0;
m--;
left--;
table_size = table_size + 4;
}
k++;
} // end while ((m > 0)
} // end while (left > 0)
} // end add method
} // end class PE
public class Predictor extends PE {
Predictor(int r) {
id = "P ";
remove(r);
self_select = 2;
other_select = 1;
one = 1;
zero = 0;
}
}
public class Evader extends PE {
Evader(int r) {
id = "E ";
remove(r);
self_select = 1;
other_select = 2;
one = 0;
zero = 1;
}
}
}