//
// 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.<P>
*/
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<length_to_size(j); i++) {
        size_to_length[i] = j;
      }
    }

    for (int j=0; j<=MAX_LENGTH; j++) {
      record_masks[j] = (int) Math.pow(4, j) - 1;
      lookup_masks[j] = record_masks[j] & 0xfffffffc; // lose lowest 2 bits
    }

    ASP asp = new ASP();
    asp.run_game();
  }

  static int length_to_size(int n) {
    return (int) ((Math.pow(4, (n + 1)) - 1) / 3);
  }

  // 0 <= position < 4^length
  static int table_position(int length, int position) {
    return length_to_size(length - 1) + position;
  }

  int history = 0;
  int history_length = 0;

  ASP() {
    int it = ((TABLE_SIZE - 4) / 4);
    int r = (int) (INIT_TABLE * it);
    // int r = (TABLE_SIZE - 4) / 8;
    int er = (int) (E_ADVANTAGE * r);
    int pr = r + r - er;
System.out.println("r = " + r + " pr = " + pr + " er = " + er +
                   " it - pr = " + (it - pr) +
                   " it - er = " + (it - er));
    p = new Predictor(it - pr);
    e = new Evader(it - er);
  }

  void run_game() {
    int px = 0;
    int ex = 0;
    while (true) {
System.out.println(" p.table_size = " + p.table_size +
                   " e.table_size = " + e.table_size);
      delay(100); // let a ctrl C in once, hey
      for (int pi=0; pi<PRINT_INTERVAL; pi++) {

        // uncomment the next two statements for algorithm 1
        // px = p.next_1(history, history_length);
        // ex = e.next_1(history, history_length);

        // uncomment the next two statements for algorithm 2
        px = p.next_2(history, history_length);
        ex = e.next_2(history, history_length);

        history = (history << 2) | (px + px) | ex;
        if (history_length < 16) history_length++;
        if (px == ex) {
          // p wins
          int n = WIN_VALUE;
          if (n > (TABLE_SIZE - p.table_size) / 4) {
            n = (TABLE_SIZE - p.table_size) / 4;
          }
          if (n > e.table_size / 4) n = e.table_size / 4;
          p.add(n);
          e.remove(n);
        }
        else {
          // e wins
          int n = WIN_VALUE;
          if (n > (TABLE_SIZE - e.table_size) / 4) {
            n = (TABLE_SIZE - e.table_size) / 4;
          }
          if (n > p.table_size / 4) n = p.table_size / 4;
          e.add(n);
          p.remove(n);
        }
if (debug) System.out.println("px, ex = " + px + " " + ex +
                              " history = " + Integer.toHexString(history) +
                              " history_length = " + history_length +
                              " p.table_size = " + p.table_size +
                              " e.table_size = " + e.table_size);
        // if (p.table_size == 0 || e.table_size == 0) debug = true;
      } // end for (int pi=0; pi<PRINT_INTERVAL; pi++)
      // growth of total table
      int addp = (int) (GROWTH_PER_PRINT * p.table_size / 4);
      p.add(addp);
      int adde = (int) (GROWTH_PER_PRINT * e.table_size / 4);
      e.add(adde);
    } // end while (true)
  } // end run_game method

  void delay(int n) {
    try {
      Thread.sleep(n);
    }
    catch (java.lang.InterruptedException ex) {
    }
  }

  // super class for Predictor and Evader does the real work
  public class PE extends Object {
    int[] table = new int[TABLE_SIZE+1];
    int table_size = TABLE_SIZE;

    // variables that differ between Predictor and Evader
    int self_select;
    int other_select;
    int one;
    int zero;
    String id;

    PE() {
      for (int i=0; i<TABLE_SIZE; i++) table[i] = 0;
    }


    // first algorithm
    // compute next symbol, and record recent history in table
    final int next_1(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)
          // 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;
    }
  }

}