import java.util.*;

public class Position {

  static Random rand = new Random();
  static boolean stopflag = false;      // aborts evaluation

  byte[] pits;        // the game board:
                      // player B's pits 7-12, mancala 13
                      //     12 11 10  9  8  7
                      //  13                    6
                      //      0  1  2  3  4  5
                      // player A's pits 0-5, mancala 6

  int depth;          // number of moves from start
  byte lastmove;      // last pit played to create this position
  boolean a2move;     // true if it is player A's turn
  int avalue;         // value of position to player A
  Position next;      // next move (depth++)
  Position sib;       // sibling move same depth - sort by value

       //
       //   depth     (verticals are "next" links)
       //
       //     0       P0 - null                 initial setup
       //             |
       //     1       P1 - null                 first move
       //             |
       //     2       P2 - null                 second move
       //             |
       //            ...
       //             |
       //     X       PX - null                 current position
       //             |
       //     X+1     PA - PB - ... - PY - 0    possible sib moves
       //             |    |          |            (up to 6)
       //     X+2     P-P  P-P-P-P    P-P-P     next possible
       //             | |  | | | |    | | |
       //             ...

  public Position() {
  // used to construct the initial position only
    pits = new byte[14];
    for (int i=0; i<13; i++) { pits[i] = 4; }
    pits[6] = pits[13] = 0;
    depth = 0;
    lastmove = -1;
    a2move = true;
    avalue = 0;
    next = sib = null;
  }

  Position(Position sire, byte move) {
    pits = new byte[14];
    for (int i=0; i<14; i++) {
      pits[i] = sire.pits[i];
      }
    a2move = sire.a2move;
    sow( lastmove=move );
    avalue = (pits[6] - pits[13])* 2 + (a2move?1:-1);
    depth = sire.depth + 1;
    sib = sire.next;
    next = null;
  }

  void makenext() {
  // generate all possible next positions
    byte i, lasti;
    if (a2move) { i = 0; lasti = 5; }
    else { i = 7; lasti = 12; }
    for ( ; i <= lasti; i++ ) {
      if (pits[i] == 0) continue;
      next = new Position(this,i);
    }
  }

  void sow(int x) {
    int seeds = pits[x];
    pits[x] = 0;
    while (seeds-- != 0) {
      x++;
      if (a2move) {
        if ( x > 12 ) x = 0;
      }
      else {
        if ( x > 13 ) x = 0;
        else if ( x == 6 ) x = 7;
      }
      pits[x]++;
    }
    // free moves & captures
    bonus: while (true) {
      if ( x==6 || x == 13 ) break bonus;  // free turn!
      a2move = !a2move;
      // if (!CaptureParam) break bonus;
      if (pits[x] != 1) break bonus;
      if (!a2move) {       // (this was A's move)
        if (x>5) break bonus;
        pits[6] += pits[12-x] + 1;
      }
      else {               // (it was B's turn)
        if (x<7) break bonus;
        pits[13] += pits[12-x] + 1;
      }
      pits[x] = 0;
      pits[12-x] = 0;
      break bonus;
    }
    // game over?
    if (pits[0]+pits[1]+pits[2]+pits[3]+pits[4]+pits[5]==0) {
      for (int i=7; i<13; i++) {
        pits[13] += pits[i];
        pits[i] = 0;
      }
    }
    else if (pits[7]+pits[8]+pits[9]+pits[10]+pits[11]+pits[12]==0) {
      for (int i=0; i<6; i++) {
        pits[6] += pits[i];
        pits[i] = 0;
      }
    }
  }

  void evaluate(boolean a2go, int deeper) {
  // extend and rearrange tree to determine next best move
  // looks ahead (deeper/(1to3)) layers - leaves best move in next
    boolean swap;
    int diff;
    if (sib != null) {    // move out along branch
      sib.evaluate(a2go, deeper);
      // reorder branch as we back back in
      if (sib.sib!=null) {
        swap = false;
        diff = sib.avalue - sib.sib.avalue;
        if (diff == 0) { if (rand.nextInt()%2 == 0) swap = true; }
        else if ((diff>0) ^ a2go) swap = true;
        if (swap) {
          Position tmp = sib.sib;
          sib.sib = sib.sib.sib;
          tmp.sib = sib;
          sib = tmp;
        }
      }
    }
    if (deeper>0) {
      if (stopflag) return;
      Thread.yield();
      if (next==null) makenext(); // extend tree
      if (next!=null) {
        next.evaluate(a2move, deeper-((a2move==a2go)?1:3));
        if (next.sib!=null) {
          // there are at least two choices
          swap = false;
          diff = next.avalue - next.sib.avalue;
          if (diff == 0) { if (rand.nextInt()%2 == 0) swap = true; }
          else if ((diff>0) ^ a2move) swap = true;
          if (swap) {
            // swap the first two choices
            Position tmp = next.sib;
            next.sib = next.sib.sib;
            tmp.sib = next;
            next = tmp;
          }
        }
        avalue = next.avalue;   // value of this is next best value
      }
    }
  }

  public Position move() {
  // prune & expand the tree
  // return the position resulting from the next (best) move
    if (next==null) return this;
    next.sib = null;
    return next;
  }

  public Position move(int pit) {
  // return the position resulting from sow(pit) (if legal)
  // else return this.
    Position choice;
    for (choice=next; choice!=null; choice=choice.sib) {
      if (choice.lastmove == pit) break;
      }
    if (choice == null) return this;
    next = choice;
    choice.sib = null;
    return choice;
  }

}