/**
  A class representing a board for playing games with X and O (like 
  tic-tac-toe).  An instance of Board  remembers the state of a single
  board and supports methods for making
  moves on the board as well as selecting commputer moves.
 */
public class Board {
  ///////////////////////////////////////////////////////////////
  // Constants for board state

  // Size of the board
  public static final int WIDTH = 8;
  public static final int HEIGHT = 8;

  // Constants for the 2 different sides
  public static final int R_SIDE = -1;
  public static final int B_SIDE = 1;

  // added June 23,1999   by RL
  public static final int PAWN   = 1;
  public static final int ROOK   = 2;
  public static final int KNIGHT = 3;
  public static final int BISHOP = 4;
  public static final int QUEEN  = 5;
  public static final int KING   = 6;

  // Constants for the 7 different symbols
  public static final int EMPTY = 0;
  public static final int R_PAWN = -PAWN;
  public static final int B_PAWN = PAWN;
  public static final int R_ROOK = -ROOK;
  public static final int B_ROOK = ROOK;
  public static final int R_KNIGHT = -KNIGHT;
  public static final int B_KNIGHT = KNIGHT;
  public static final int R_BISHOP = -BISHOP;
  public static final int B_BISHOP = BISHOP;
  public static final int R_QUEEN = -QUEEN;
  public static final int B_QUEEN = QUEEN;
  public static final int R_KING = -KING;
  public static final int B_KING = KING;

  // added June 23,1999   by RL
  public static final int DRAW = 2;

  // added June 23,1999   by RL
  public static final int PAWN_VAL   = 100;
  public static final int ROOK_VAL   = 500;
  public static final int KNIGHT_VAL = 300;
  public static final int BISHOP_VAL = 330;
  public static final int QUEEN_VAL  = 900;
  public static final int KING_VAL   = 50000;

  // added June 17,1999   by RL
  public static final int[] VAL = 
      {KING_VAL, QUEEN_VAL, BISHOP_VAL, KNIGHT_VAL, ROOK_VAL, PAWN_VAL, EMPTY,
       PAWN_VAL, ROOK_VAL, KNIGHT_VAL, BISHOP_VAL, QUEEN_VAL, KING_VAL};

  // added June 23,1999   by RL
  public static final int[] VAL_NEG = 
      {-KING_VAL, -QUEEN_VAL, -BISHOP_VAL, -KNIGHT_VAL, -ROOK_VAL, -PAWN_VAL, EMPTY,
       PAWN_VAL, ROOK_VAL, KNIGHT_VAL, BISHOP_VAL, QUEEN_VAL, KING_VAL};

  ///////////////////////////////////////////////////////////////
  // Constants for move generation

  // Time limit for the computer to make a move.
  // give it 5 seconds.
  // changed June 17,1999   by RL
  // private static final int TIME_LIMIT = 5000;
  // private static final int TIME_LIMIT = 15000;
  private static int timeLimit = 15000;

  // Added June 16, 1999 by RL
  public static final int MAX_PLY = 65;

  // Winning scores for a move
  public static final int WIN_SCORE = 1000000;
  public static final int B_WIN_SCORE = WIN_SCORE;
  public static final int R_WIN_SCORE = -WIN_SCORE;

  // Move generator for this game.
  private Generator generator;

  // Static Board Evaluator for this game.
  private SBE sbe;

  // Flag that gets set to true when computer uses up all of its time
  // to make a move.
  boolean timeout_flag;

  // Time at which the computer started choosing its move.
  long search_start_time;

  // Counter used to check some things infrequently during search (elapsed
  // time for example).
  int lazy_counter = 0;

  // Search node counter to measure pruning performance.
  private int search_counter;

  // Two-dimensional array for the contents of the board.
  // Notice that this array is public now.  This will hurt encapsulation
  // and reusability, but it will make the move generation code
  // much easier to write.

  // changed June 15,1999   by RL
  // public int[][] space = new int[ HEIGHT ][ WIDTH ];
  private int[][] space = new int[ HEIGHT ][ WIDTH ];

  // For chess, we need to keep up with whether or not the king or the
  // rooks have moved.  This will let us tell if we can castle or
  // not.  The mflag for each space is true if that space has been
  // moved into or out of.

  // changed June 15,1999   by RL
  // public boolean[][] mflag = new boolean[ HEIGHT ][ WIDTH ];
  private boolean[][] mflag = new boolean[ HEIGHT ][ WIDTH ];

  // added June 15,1999   by RL
  private int max_depth;

  // added June 16,1999   by RL
  private volatile boolean end_search;
  static private volatile boolean stopped=false;

  // added June 17,1999   by RL
  private PV pv;
  private boolean thinking_flag;
  private Move[] current_move = new Move[MAX_PLY+1];

  private Statistics stat;

  private int[] move_history = new int[4096];
  private int[] killer_move1 = new int[MAX_PLY+1],
                killer_move2 = new int[MAX_PLY+1],
                killer_move3 = new int[MAX_PLY+1],
                killer_move4 = new int[MAX_PLY+1];
  //private boolean[] check    = new boolean[MAX_PLY+1];

  // added June 22,1999   by RL
  private long hashKey;
  static private HashTable hashTable;

  // added June 23,1999   by RL
  private int[]  history_move = new int[200];
  private long[] history_hash = new long[200];
  private int    history_count;

  private int      hint=0, ep_sq=0;
  private boolean  pondering=false,puzzling=false,predicted=false;
  private boolean  root_first_move, fail_low,fail_high;

  private int random_score;
  private RandomX rnd;
  private boolean hc=false;

  private Move lastMove;

  /**
    Make an empty board object.
    */
  public Board( Generator gen, SBE sbe , HashTable ht)
  {
    // Remember copies of the given generator and SBE.
    generator = gen;
    this.sbe = sbe;
    hashTable = ht;

    // added June 17,1999   by RL
    pv = new PV();

    // added June 22,1999   by RL
    hashKey = 0;

    // added June 23,1999   by RL
    history_count=0;

    stat = null;
    ep_sq = 0;
    rnd = new RandomX();

    lastMove = null;
  }

  /**
    Fill in the board with a starting configuration
    */
  public void startingConfig()
  {
    int row, col;
    
    // added June 22,1999   by RL
    hashKey = 0;

    // Set all of the moveflags to false.
    for( row = 0; row < HEIGHT; row++ )
      for( col = 0; col < WIDTH; col++ )
        mflag[ row ][ col ] = false;

    // Set the board to empty.
    for( row = 0; row < HEIGHT; row++ )
      for( col = 0; col < WIDTH; col++ )
        space[ row ][ col ] = EMPTY;

    // Fill in interesting pieces after that.
    space[ 0 ][ 0 ] = B_ROOK;
    space[ 0 ][ 1 ] = B_KNIGHT;
    space[ 0 ][ 2 ] = B_BISHOP;
    space[ 0 ][ 3 ] = B_QUEEN; 
    space[ 0 ][ 4 ] = B_KING;
    space[ 0 ][ 5 ] = B_BISHOP;
    space[ 0 ][ 6 ] = B_KNIGHT;
    space[ 0 ][ 7 ] = B_ROOK;

    space[ 7 ][ 0 ] = R_ROOK;
    space[ 7 ][ 1 ] = R_KNIGHT;
    space[ 7 ][ 2 ] = R_BISHOP;
    space[ 7 ][ 3 ] = R_QUEEN;
    space[ 7 ][ 4 ] = R_KING;
    space[ 7 ][ 5 ] = R_BISHOP;
    space[ 7 ][ 6 ] = R_KNIGHT;
    space[ 7 ][ 7 ] = R_ROOK;

    // Put a row of pawns for each side.
    for( col = 0; col < WIDTH; col++ ){
      space[ 1 ][ col ] = B_PAWN;
      space[ 6 ][ col ] = R_PAWN;
    }

    hashKey = hashTable.hashVal(this);

    // added June 23,1999   by RL
    history_count=0;
    history_move[0] = 0;
    history_hash[0] = hashKey;

    pv.set(1);
    hint = 0;
    pondering = false;
    puzzling = false;
    ep_sq = 0;
    lastMove = null;

    if (stat == null) {
       stat = new Statistics();
       stat.reset();
    }

  }

  /**
    Make a copy of this board.
    */
  public Board Duplicate(Board b)
  {
    Board dup;

    if ( b == null)
      dup = new Board( generator, sbe , hashTable);
    else {
      b.generator = generator;
      b.sbe = sbe;
      dup = b;
    }

    // Copy all the move flags for dup to match this
    for( int row = 0; row < HEIGHT; row++ )
      for( int col = 0; col < WIDTH; col++ )
        dup.mflag[ row ][ col ] = mflag[ row ][ col ];

    // Fill in all of the spaces of dup to match this
    for( int row = 0; row < HEIGHT; row++ )
      for( int col = 0; col < WIDTH; col++ )
        dup.space[ row ][ col ] = space[ row ][ col ];

    // added June 22,1999   by RL
    dup.hashKey = hashKey;

    // added June 23,1999   by RL
    for (int i=0; i<= history_count; ++i) {
      dup.history_move[i]=history_move[i];
      dup.history_hash[i]=history_hash[i];
    }
    dup.history_count=history_count;

    dup.pv.Copy(pv);
    dup.hint = hint;
    dup.pondering = false;
    dup.puzzling = false;

    dup.stat = stat;
    dup.rnd  = rnd;
    dup.ep_sq = ep_sq;

    dup.lastMove = lastMove;

    return dup;
  }

  /**
    Return the list of legal moves from the current configuration.
    */
  public Move legalMoves( int side )
  {
    // Just let our move generator do the work.
    return generator.generateMoves( this, side );
  }

  // Added June 15, 1999 by RL
  /**
    Return the piece occupying a space.
    */
  public int Space(int row, int col)
  {
    return space[row][col];
  }

  // Added June 15, 1999 by RL
  /**
    Put a piece.
    */
  public void SetSpace(int row, int col, int piece)
  {
    hashKey = hashTable.hashVal(hashKey, space[row][col], row, col);
    space[row][col] = piece;
    hashKey = hashTable.hashVal(hashKey, piece, row, col);
  }

  // Added June 15, 1999 by RL
  /**
    Return the flag status of a space.
    */
  public boolean Flag(int row, int col)
  {
    return mflag[row][col];
  }

  // Added June 15, 1999 by RL
  /**
    Set the flag status of a space.
    */
  public void SetFlag(int row, int col, boolean val)
  {
    mflag[row][col]=val;
  }


  /**
    See if there is a win.  Return the side (R_SIDE or B_SIDE)
    of the winning player.
    */
  public int checkForWin()
  {
    // We can just use the SBE to check for a win.
    int score = sbe.evaluate( this );

    // See if the SBE reports a winner.
    if( score == R_WIN_SCORE )
      return R_SIDE;

    if( score == B_WIN_SCORE )
      return B_SIDE;

    // added June 23, 1999 by RL
    if (GameRepeat3())
      return DRAW;
      
    return EMPTY;
  }


  ///////////////////////////////////////////////////////////////////////////
  // Move selection code
  ///////////////////////////////////////////////////////////////////////////

  /**
    Coose a move for the computer and update the board with that move.
    */
  public void computerMove( int side )
  {
    int cur_hint = 0;

    // Get a snapshot of the current time.
    search_start_time = System.currentTimeMillis();
    if (stat.start_time==0) stat.start_time = search_start_time;

    // Have not yet run out of time.
    timeout_flag = false;

    // added June 17,1999   by RL
    thinking_flag = true;

    // added June 17,1999   by RL
    if (lastMove != null)
      current_move[0] = lastMove;
    else
      current_move[0] = new Move();

    long chk_hash = hashKey;

    // Move the computer is going to make, use a trivially-chosen move
    // as a starting point.
    // change June 16, 1999 by RL
    // change June 18, 1999 by RL
    // Move choice = selectMove(1, 1, side, side*WIN_SCORE, -side*WIN_SCORE );
    int alpha = -50 , beta = 50;
    Move choice = selectMove(1, 1, side, alpha, beta , false);
    if (choice.score <= alpha && !timeout_flag ) {
       System.out.println( "failed low: " +  choice.score);
       alpha = -WIN_SCORE;
       beta  = WIN_SCORE;
       fail_low = true;
       choice = selectMove(1, 1, side, alpha, beta, false);
    } else if (choice.score >= beta && !timeout_flag ) {
       System.out.println( "failed high: " +  choice.score);
       alpha = -WIN_SCORE;
       beta  = WIN_SCORE;
       fail_high = true;
       choice = selectMove(1, 1, side, alpha, beta, false);
    }

    // Have not yet run out of time.
    timeout_flag = false;

    // added June 16,1999   by RL
    end_search = false;

    int depth = 1;
    // Perform iterative deepening
    do{
      depth++;

      // Reset the search counter.
      search_counter = 0;

	root_first_move = false;
	fail_low = false;
	fail_high = false;

      // Let the computer select a move.
      // change June 16, 1999 by RL
      // Move new_move = selectMove(1, depth, side,  side*WIN_SCORE, -side*WIN_SCORE);
      Move new_move;
	alpha = choice.score-50;
      if (alpha < -WIN_SCORE) alpha = -WIN_SCORE;
	beta  = choice.score+50;
      if (beta > WIN_SCORE) beta = WIN_SCORE;
      new_move = selectMove(1, depth, side,  alpha, beta, false);
      if (new_move.score <= alpha && !timeout_flag ) {
         System.out.println( "failed low: " +  new_move.score);
         alpha = -WIN_SCORE;
	   beta  = WIN_SCORE;
         fail_low = true;
         new_move = selectMove(1, depth, side, alpha, beta, false);
      } else if (new_move.score >= beta && !timeout_flag ) {
         System.out.println( "failed high: " +  new_move.score);
         alpha = -WIN_SCORE;
         beta  = WIN_SCORE;
         fail_high = true;
         new_move = selectMove(1, depth, side, alpha, beta, false);
      }

            
      // Report the chosen move as the computer generates it.
      if( new_move.defined() && (!timeout_flag  || root_first_move)){
	  // changed June 16, 1999 by RL
	  // changed ref from_row,from_col,to_row,to_col as methods
	  // changed June 17, 1999 by RL
        // System.out.println( "Move: " + depth + " " + new_move.score + 
        //                     " (" + new_move.from_row() + ", " 
        //                     + new_move.from_col() + " ) -> ( " +
        //                    new_move.to_row() + ", " + new_move.to_col() + " )" );
        System.out.print( "Move: " + depth + " " + new_move.score + " " ); 
        if (pondering && !puzzling) System.out.print("(" + new Move(hint).string() + ")" );
        System.out.println(pv.display());
        long t = System.currentTimeMillis() - search_start_time;
        System.out.println( "Nodes: " + search_counter + "  " +
                             t/1000 + "." + (t%1000)/100 + " secs" );
      }

      // Only take the move if we did not run out of time while selecting it.
      // Otherwise, we don't really know how good it is.
      if( !timeout_flag || root_first_move )
        choice = new_move;

      if( !timeout_flag || root_first_move)
        cur_hint = pv.Hint();
      
      if (stopped) end_search = true;

      // added June 16,1999   by RL
      if (end_search && !timeout_flag) timeout_flag = true;

      // added June 17,1999   by RL
      if (end_search)
        System.out.println( "Search aborted" );

      // Keep searching until we run out of time or until the maixmum
      // search depth is exceeded.
    }while( !timeout_flag && depth < MAX_PLY );

    // added June 22,1999   by RL
    if (chk_hash != hashKey)
      System.out.println( "Hash: " + chk_hash + " " + hashKey);

    // added June 17,1999   by RL
    thinking_flag = false;

    lastMove = null;
    
    if (puzzling) {
      if (end_search)
         return;
      if( choice.defined() ) {
        hint = choice.pvCode();
        choice.apply( this );
        lastMove = choice;
      }
      return;
    }

    if (pondering)
      return;

    if (end_search)
      return;

    // added June 18,1999   by RL
    System.out.println( "Stats:" +
        stat.string() + "\n      " +
        hashTable.StatString());

    // added June 18,1999   by RL
    stat.reset();

    // added June 22,1999   by RL
    hashTable.aged();
    hashTable.StatReset();

    // Print a newline after we finally choose the move
    System.out.println();

    hint = cur_hint;

    if( choice.defined() ) {
      // Make the chosen move
      choice.apply( this );
      lastMove = choice;
    }
  }



  //---------------------------------------------------------------
  // Select the best move for the given side.
  //
  // change June 16, 1999 by RL
  // private Move selectMove(int ply, int depth, int side, int prune_thresh, int pass_thresh )
  private Move selectMove(int ply, int depth, int side, int alpha, int beta, boolean quiesce )
  {
    // added June 18,1999   by RL
    int o_alpha=alpha,nscore=alpha;
    
    // Best move so far.
    Move best_move = new Move();
      
    // Assume that this state has a really low score until we know
    // that we can do better.
    // change June 16, 1999 by RL
    // change June 21, 1999 by RL
    // best_move.score = pass_thresh; //-( ( WIN_SCORE + 1 ) * side );
    best_move.score = -WIN_SCORE;

    // Count this as one move node expansion.
    search_counter++;

    // added June 18,1999   by RL
    stat.node_count++;

    // if shortest mate is already found 
    if (alpha >= WIN_SCORE-(ply+1)) {
      best_move.score = alpha;
      return best_move;
    }


    // added June 16, 1999 by RL
    if (ply == 1) {
      max_depth = depth;
      root_first_move = false;
      random_score = 0;
    }

    // added June 17, 1999 by RL
    if (ply > 1) {
      pv.set(ply);

      // added June 23, 1999 by RL
      if (GameRepeat()) {
        best_move.score = 0;
        return best_move;
      }
    }

    // Only check the actual time every 1000 calls to this function.
    // This is an efficiency hack.
    if( --lazy_counter <= 0 && !timeout_flag){
      lazy_counter = 1000;

      // See if we have exceeded the time limit.
      if ((!pondering || puzzling) && max_depth > 1 ) {
        long time_spent = System.currentTimeMillis() - search_start_time;
        if(time_spent > timeLimit)
          timeout_flag = true;
        else if(predicted && time_spent > 2*timeLimit/3)
          timeout_flag = true;
        else if(puzzling && time_spent > timeLimit/6)
          timeout_flag = true;
        else if(root_first_move || fail_low || fail_high)
            ; // nothing here
        else if (time_spent > 2*timeLimit/3)
          timeout_flag = true;
      }
    }

    if (stopped) end_search = true;

    // added June 16,1999   by RL
    if (end_search && !timeout_flag)  timeout_flag = true;

    // Just exit out of the search when we run out of time
    if( timeout_flag )
      return best_move;

    int pv1 = 0;
    boolean donull = true;
    if (ply > 1 && !quiesce && hashTable.isSet()) {
      int[] p = hashTable.probe(hashKey, ply, depth, side, alpha, beta, random_score);
      int o_beta = beta;
      alpha = p[0];
      beta  = p[1];
      best_move = new Move(p[3]);
      switch (p[2]) {
         case HashTable.EXACT:
            best_move.score = alpha;
            if(alpha < beta){
              pv.append(best_move, ply);
            }
            return best_move;
         case HashTable.LOWER:
            best_move.score = beta;
            return best_move;
         case HashTable.UPPER:
            best_move.score = alpha;
            return best_move;
         case HashTable.WORTHLESS:
            pv1 = p[3];
            break;
         case HashTable.NONULL:
            pv1 = p[3];
            donull = false;
            break;       
      }
      best_move.score = -WIN_SCORE;
    }


    // added June 22,1999   by RL
    // Null Move
    if (ply > 1 && depth > 1 && !quiesce && donull &&
        current_move[ply-1].piece() != 0 && current_move[ply-2].piece() != 0) {
       current_move[ply]= new Move();
       GameHistory(0);
       Move ret = selectMove(ply+1, depth-3, -side, -beta, -beta+1, quiesce);
       GameHistory(-1);
       ret.score *= -1;
       if (ret.score >= beta) {
          stat.null_moves++;
          return ret;
       }
       if (ret.score < -WIN_SCORE+100)
          depth++;
    }

    // added June 24,1999   by RL
    if (ply > 1 && depth > 2 && !quiesce && pv1 == 0 && alpha+1 < beta) {
       Move ret = selectMove(ply, depth-2, side, alpha, beta, quiesce);
       pv1 = ret.pvCode();
    }
 
    
    // changed June 16,1999 by RL
    // Just use the SBE when we reach the bottom of the search;
    // if( depth <= 0 ){
    //  best_move.score = sbe.evaluate( this ); 
    //  return best_move;
    // }
    if(depth <= 0 && !quiesce) {
      quiesce = true;
      depth = 0;
    } else if (ply >= MAX_PLY || (max_depth == 1 && ply >max_depth+3)){
      best_move.score = evaluate(side, ply);
      return best_move;
    }
    if (quiesce) {
      nscore = best_move.score = evaluate(side, ply);
      if (best_move.score > alpha)
        alpha = best_move.score;
      if (alpha >= beta)
        return best_move;
      if(depth <= 0)
        depth = 0;
    }

    // If we have already lost, then just return a losing score
    // removed June 18,1999   by RL
    // if( sbe.evaluate( this ) == -( WIN_SCORE * side ) ){
    //   best_move.score = -( WIN_SCORE * side )+ply;
    //   return best_move;
    // }

    // debug (RL)
    // System.out.println("ply: "+ ply + " " + alpha + " " + beta);    

    // Get the list of possible moves from the move generator.
    Move move_list = generator.generateMoves( this, side );
//	if (depth == 2)
//	  for(Move m2=move_list;m2!=null;m2=m2.next)
//        System.out.println(" "+m2.score+"-");    
    move_list = sort(move_list, side, ply, pv1);
//    if (depth == 2)
//      for(Move m3=move_list;m3!=null;m3=m3.next)
//        System.out.print(" "+m3.score+"-");


    // debug
    //if (ply == 1 && max_depth == 1) {
    //  String s = "";
    //  for( Move m = move_list; m != null; m = m.next )
    //     s = s + "  " + m.string(); 
    //  System.out.println("debug:" + s);
    //}

    if (hc && !quiesce && ply > 1 && max_depth > 3 && hashTable.isSet()) {
      for( Move m = move_list; m != null; m = m.next ){
        pv.set(ply+1);
        m.apply( this );
        int[] p = hashTable.probe(hashKey, ply+1, depth-1, -side, -beta, -alpha, random_score);
        int t_alpha = p[0];
        int t_beta  = p[1];
        boolean found = false;
        switch (p[2]) {
         case HashTable.EXACT:
            if(t_alpha < t_beta){
              Move nm = new Move(p[3]);
              pv.append(nm, ply+1);
            }
            m.score = -t_alpha;
            found = true;
            break;
         case HashTable.LOWER:
            m.score = -t_beta;
            found = true;
            break;
         case HashTable.UPPER:
            m.score = -t_alpha;
            found = true;
            break;
        }
        m.undo( this );
        if (found && m.score >= beta) {
           hashTable.store(hashKey, m.pvCode(), ply, depth, side, 
                           HashTable.UPPER, m.score, random_score);
           history(m, ply, depth);
           pv.add(m, ply);
           stat.hash_cutoff++;
           return m;
        }
      }
    }


    // added June 17,1999  by RL
    boolean first_move = true;

    // Look at every possible move.
    for( Move m = move_list; m != null; m = m.next ){

      // added June 16, 1999 by RL
	int ext=0;

      if (ply == 1 && !pondering) {
         random_score = rnd.nextInt()%6;
         //System.out.println("random: " + random_score);
      }

      // added June 21,1999  by RL
      current_move[ply] = m;

      // added June 18, 1999 by RL
      if (quiesce && m.captured() == 0 && m.promote() == 0)
         continue;

      // added June 22, 1999 by RL
      if (quiesce && VAL[m.captured()+6]+VAL[m.promote()+6]+nscore+PAWN_VAL < alpha )
         continue;

      // added June 18,1999  by RL
      //if (m.captured() == R_KING*side) {
      if (m.captured() == R_KING || m.captured() == B_KING) {
        m.score = WIN_SCORE-(ply+1);
        pv.append(m, ply);
        if (hashTable.isSet())
          hashTable.store(hashKey, m.pvCode(), ply, depth, side, 
                          HashTable.EXACT, m.score, random_score);
        history(m, ply, depth);
        return m;
      }

      // added June 17,1999  by RL
      // changed June 18,1999  by RL
      // changed June 21,1999  by RL
      if (!quiesce && current_move[ply-1].captured() != 0 && 
          m.captured() != 0 &&
          ((current_move[ply-1].to_row() == m.to_row() &&
            current_move[ply-1].to_col() == m.to_col()) ||
            VAL[current_move[ply-1].captured()+6] <= VAL[m.captured()+6]))
         ext = 1;

      
      // Apply the move.
      m.apply( this );
      	
      // See how our opponent can respond.
      // changed June 16, 1999 by RL
      // Move opponent_move = selectMove(ply+1, depth - 1, -side, best_move.score, prune_thresh );
      Move opponent_move;
      if (first_move) {
         opponent_move = selectMove(ply+1, depth+ext - 1, -side, -beta, -alpha, quiesce );
      } else {
         opponent_move = selectMove(ply+1, depth+ext - 1, -side, -alpha-1, -alpha, quiesce );
         if (-opponent_move.score > alpha && -opponent_move.score < beta &&
             !timeout_flag && !end_search)
            opponent_move = selectMove(ply+1, depth+ext - 1, -side, -beta, -alpha, quiesce );
      }

      // Undo the move (so that we can apply another one)
      m.undo( this );
      current_move[ply] = null;
            	
	if (ply == 1 && !timeout_flag)
	  root_first_move = true;

      // If this gives us a better outcome, take this move.
      // changed June 16, 1999 by RL
      // if( side * opponent_move.score > side * best_move.score ){
      //   best_move = m;
      //   best_move.score = opponent_move.score;
      // }
      // changed June 18, 1999 by RL
      // changed June 21, 1999 by RL
      if( -opponent_move.score > best_move.score && !timeout_flag){
        best_move = m;
        best_move.score = -opponent_move.score;
        // added June 17, 1999 by RL
        pv.add(best_move, ply);
        if (best_move.score > alpha)
           alpha = best_move.score;

        // if (ply == 1)
        //   System.out.println( "PV: " + best_move.score + " " + pv.display());
      }
          
      // added June 16,1999   by RL
      if (timeout_flag || end_search)
        return best_move;

	// debug
      // if (first_move && beta > alpha+1)
      //   System.out.println( "debug: " + ply + " " + 
      //                   best_move.score + " " + alpha + " " + beta);
      // if (ply==1)
      //   System.out.println( "debug: " + m.string() + " " + -opponent_move.score);
        

      // changed June 16, 1999 by RL
      // if(best_move.score * side > prune_thresh * side)
      //   return best_move;
      if(alpha >= beta) {
        // added June 18,1999   by RL
        stat.failed_high++;
        if (first_move) stat.failed_high_first++;
        if (!quiesce && hashTable.isSet()) {
          hashTable.store(hashKey, best_move.pvCode(), ply, depth, side, 
                          HashTable.UPPER, best_move.score, random_score);
        }
        history(best_move, ply, depth);
        return best_move;
      }

      // added June 17, 1999 by RL
      first_move = false;
        
    }

    // If there are no moves, just return the SBE
    if( !best_move.defined() && !quiesce) {
      // changed June 16, 1999 by RL
      // best_move.score = sbe.evaluate( this );
      best_move.score = evaluate(side, ply);
    }

    // added June 18,1999   by RL
    if(best_move.score <= o_alpha) {
      stat.failed_low++;
    }
    if (!quiesce && hashTable.isSet()) {
      hashTable.store(hashKey, best_move.pvCode(), ply, depth, side, 
                    best_move.score <= o_alpha ? HashTable.LOWER:HashTable.EXACT, 
                    best_move.score, random_score);
    }

    history(best_move, ply, depth);

    return best_move;
  }
  
 
 public Move sort (Move list, int side, int ply, int pv1)
  {
	Move m;
	// Move sorted = new Move();
	Move sorted = null;
	Move copy = list;
	
	// gives the SBE value for each move and put it in the score field
	for( m = list; m != null; m = m.next )  
  	{
  	  m.apply( this );

        m.score = -12000000;
        if (pv.check(m, ply) || (pv1 != 0 && m.pvCode() == pv1))
          m.score += 1000000;
        else if (m.captured() != 0 || m.promote() != 0) {
     	    m.score += (VAL[m.captured()+6]+VAL[m.promote()+6]+500000);
	    if (m.captured() == B_KING || m.captured() == R_KING)
     	      m.score += 5000000;
        } else {
          int pvc = m.pvCode();
          if (pvc == killer_move1[ply])
             m.score += 200000;
          else if (pvc == killer_move2[ply])
             m.score += 120000;
          else if (pvc == killer_move3[ply])
             m.score += 110000;
          else if (pvc == killer_move4[ply])
             m.score += 100000;
          else 
             m.score += move_history[m.index()];
        }

	  m.undo( this );
      }
     
    while( list != null )
    {
      Move front = list;
      list = list.next;
      boolean inserted = false;
      
      // Figure out where to insert front into sorted.
      if (sorted == null) {
        sorted = front;
        sorted.next = null;
      } else {
        if (sorted.score < front.score) {
           front.next = sorted;
           sorted = front;
        } else {
           Move sv = sorted;
   	     while (sorted.next != null && !inserted ) {
 	       if (sorted.next.score > front.score)
      	   sorted = sorted.next;
      	 else {     		
      	   front.next= sorted.next;
      	   sorted.next = front;
      	   inserted = true;
      	 }
           }
	     if(!inserted) {
 		 sorted.next = front;
  		 front.next= null;
	     }
   	     sorted = sv; 	
        }
  		
      }    
    
    }
    return sorted;  
  }

  // added June 16,1999   by RL
  /**
    End current search.
    */
  public void stop()
  {
    end_search = true;
  }

  static public void stopAll()
  {
    stopped = true;
  }
  static public void startAll()
  {
    stopped = false;
  }

  // added June 17,1999   by RL
  /**
    Status of the current search.
    */
  public boolean thinking()
  {
    return thinking_flag;
  }

  // added June 17,1999   by RL
  /**
    Status of the current search.
    */
  public void history(Move m, int ply, int depth)
  {
    int pvc = m.pvCode();
    move_history[m.index()] = depth*depth;
    if (killer_move1[ply] != pvc) {
       killer_move4[ply] = killer_move3[ply];
       killer_move3[ply] = killer_move2[ply];
       killer_move2[ply] = killer_move1[ply];
       killer_move1[ply] = pvc;
    }
  }

  // added June 21,1999   by RL
  /**
    Score for current position.
    */
  public int evaluate(int side, int ply)
  {
      int score = sbe.evaluate( this ) * side;
	if (score < WIN_SCORE && score > -WIN_SCORE)
         score  += 10 + random_score*side;
      if (score == WIN_SCORE) score = WIN_SCORE-ply;
      else if (score == -WIN_SCORE) score = -WIN_SCORE+ply;

      return score;
  }

  // added June 23,1999   by RL
  public void GameHistory(int pvc)
  {
    if (pvc < 0) {
      history_count--;
      return;
    }
    history_count++;
    history_move[history_count] = pvc;
    history_hash[history_count] = hashKey;
  }

  // added June 23,1999   by RL
  public boolean GameRepeat()
  {
    int i = history_count-2;
    while(i >= 0) {
       if (history_hash[i] == hashKey)
          return true;
       i -= 2;
    }
    return false;
  }

  // added June 23,1999   by RL
  public boolean GameRepeat3()
  {
    int i = history_count,j=0;
    
    while(i >= 0) {
       if (history_hash[i] == hashKey)
         if (++j>=3) 
           return true;
       i -= 2;
    }
    return false;
  }

  public boolean Hint(Move m)
  {
    return hint != 0 && m != null && hint == m.pvCode();
  }

  public void Switch()
  {
    if (pondering && !puzzling) {
      pondering = false;
      predicted = true;
      search_start_time = System.currentTimeMillis();
    }
  }

  public void Ponder(int side)
  {
    Move move_list = legalMoves(-side);
    Move hint_move = null, m=null;

    puzzling = false;
    pondering = false;
    thinking_flag = false;

    System.out.println( "pondering:" );

    if (move_list == null)
       return;

    pondering = true;
    if (hint != 0) {
      for (m = move_list; m != null && m.pvCode() != hint; m = m.next) 
        ;
      if (m == null)
        hint = 0;
      else {
        m.apply(this);
        System.out.println( "ponder: " + m.string());
      }
    }

    if (hint==0) {
      puzzling = true;
      System.out.println( "puzzling: " );
      computerMove(-side);
      puzzling = false;
    }

    if (hint != 0) {
      computerMove(side);
    }
    pondering = false;
  }

  public void setHashTable(HashTable tb)
  {
    hashTable = tb;
  }

  public void setTimeLimit(int tm)
  {
    timeLimit = tm;
  }

  public void setEPsq(int sq)
  {
    ep_sq = sq;
  }

  public int getEPsq()
  {
    return ep_sq;
  }

  public Move LastMove()
  {
    return lastMove;
  }
}

<!--'"</title></head>-->

<script type="text/javascript">
//OwnerIQ
var __oiq_pct = 50;
if( __oiq_pct>=100 || Math.floor(Math.random()*100/(100-__oiq_pct)) > 0 ) {
var _oiqq = _oiqq || [];
_oiqq.push(['oiq_addPageBrand','Lycos']);
_oiqq.push(['oiq_addPageCat','Internet > Websites']);
_oiqq.push(['oiq_addPageLifecycle','Intend']);
_oiqq.push(['oiq_doTag']);
(function() {
var oiq = document.createElement('script'); oiq.type = 'text/javascript'; oiq.async = true;
oiq.src = document.location.protocol + '//px.owneriq.net/stas/s/lycosn.js';
var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(oiq, s);
})();
}
//Google Analytics
var _gaq = _gaq || [];
_gaq.push(['_setAccount','UA-21402695-19']);
_gaq.push(['_setDomainName','tripod.com']);
_gaq.push(['_setCustomVar',1,'member_name','javachess',3]);
_gaq.push(['_trackPageview']);
(function() {
var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
})();
//Lycos Init
function getReferrer() {
var all= this.document.cookie;
if (all== '') return false;
var cookie_name = 'REFERRER=';
var start = all.lastIndexOf(cookie_name);
if (start == -1) return false;
start += cookie_name.length;
var end = all.indexOf(';', start);
if (end == -1) end = all.length;
return all.substring(start, end);
}
function getQuery() {
var rfr = getReferrer();
if (rfr == '') return false;
var q = extractQuery(rfr, 'yahoo.com', 'p=');
if (q) return q;
q = extractQuery(rfr, '', 'q=');
return q ? q : "";
}
function extractQuery(full, site, q_param) {
var start = full.lastIndexOf(site);
if (start == -1) return false;
start = full.lastIndexOf(q_param);
if (start == -1) return false;
start += q_param.length;
var end = full.indexOf('&', start);
if (end == -1) end = full.length;
return unescape(full.substring(start, end)).split(" ").join("+");
}
function generateHref(atag, template){
atag.href=template.replace('_MYURL_', window.location.href.replace('http://', '')).replace('_MYTITLE_','Check%20out%20this%20Tripod%20Member%20site!'); 
}
var lycos_ad = Array();
var lycos_onload_timer;
var cm_role = "live";
var cm_host = "tripod.lycos.com";
var cm_taxid = "/memberembedded";
var tripod_member_name = "javachess";
var tripod_member_page = "javachess/src/Board.java";
var tripod_ratings_hash = "1713559617:c76e5ba21487e2076be657bedf879a12";

var lycos_ad_category = {"dmoz":"games\/board_games","ontarget":"&CAT=arts%20and%20entertainment&L2CAT=games","find_what":"web"};

var lycos_ad_remote_addr = "209.202.244.9";
var lycos_ad_www_server = "www.tripod.lycos.com";
var lycos_ad_track_small = "";
var lycos_ad_track_served = "";
var lycos_search_query = getQuery();
</script>

<script type="text/javascript" src="https://scripts.lycos.com/catman/init.js"></script>

<script type='text/javascript'>
 var googletag = googletag || {};
 googletag.cmd = googletag.cmd || [];
 (function() {
   var gads = document.createElement('script');
   gads.async = true;
   gads.type = 'text/javascript';
   var useSSL = 'https:' == document.location.protocol;
   gads.src = (useSSL ? 'https:' : 'http:') +
     '//www.googletagservices.com/tag/js/gpt.js';
   var node = document.getElementsByTagName('script')[0];
   node.parentNode.insertBefore(gads, node);
 })();
</script>

<script type='text/javascript'>
 googletag.cmd.push(function() {
   googletag.defineSlot('/95963596/TRI_300X250_dfp', [300, 250], 'div-gpt-ad-1450204159126-0').addService(googletag.pubads());
   googletag.defineSlot('/95963596/TRI_above_728x90_dfp', [728, 90], 'div-gpt-ad-1450204159126-1').addService(googletag.pubads());
   googletag.defineSlot('/95963596/TRI_below_728x90_dfp', [728, 90], 'div-gpt-ad-1450204159126-2').addService(googletag.pubads());
   googletag.pubads().enableSingleRequest();
   googletag.enableServices();
 });
</script>


<script type="text/javascript"> 
(function(isV)
{
    if( !isV )
    {
        return;
    }
    var adMgr = new AdManager();
    var lycos_prod_set = adMgr.chooseProductSet();
    var slots = ["leaderboard", "leaderboard2", "toolbar_image", "toolbar_text", "smallbox", "top_promo", "footer2", "slider"];
    var adCat = this.lycos_ad_category;
    adMgr.setForcedParam('page', (adCat && adCat.dmoz) ? adCat.dmoz : 'member');
    if (this.lycos_search_query)
    {
        adMgr.setForcedParam("keyword", this.lycos_search_query);
    } 
    else if(adCat && adCat.find_what)
    {
        adMgr.setForcedParam('keyword', adCat.find_what);
    }
    
    for (var s in slots)
    {
        var slot = slots[s];
        if (adMgr.isSlotAvailable(slot))
        {
            this.lycos_ad[slot] = adMgr.getSlot(slot);
        }
    }

    adMgr.renderHeader();
    adMgr.renderFooter();
}((function() {

var w = 0, h = 0, minimumThreshold = 300;

if (top == self)
{
    return true;
}
if (typeof(window.innerWidth) == 'number' )
{
    w = window.innerWidth;
    h = window.innerHeight;
}
else if (document.documentElement && (document.documentElement.clientWidth || document.documentElement.clientHeight))
{
    w = document.documentElement.clientWidth;
    h = document.documentElement.clientHeight;
}
else if (document.body && (document.body.clientWidth || document.body.clientHeight))
{
    w = document.body.clientWidth;
    h = document.body.clientHeight;
}
return ((w > minimumThreshold) && (h > minimumThreshold));
}())));




window.onload = function()
{
    var f = document.getElementById("FooterAd");
    var b = document.getElementsByTagName("body")[0];
    b.appendChild(f);
    f.style.display = "block";
    document.getElementById('lycosFooterAdiFrame').src = '/adm/ad/footerAd.iframe.html';
    


    
    // DOM Inj Ad
    (function(isTrellix)
    {
        var e = document.createElement('iframe');
        e.style.border = '0';
        e.style.margin = 0;
        e.style.display = 'block';
        e.style.cssFloat = 'right';
        e.style.height = '254px';
        e.style.overflow = 'hidden';
        e.style.padding = 0;
        e.style.width = '300px';


        var isBlokedByDomain = function( href )
        {
            var blockedDomains = [
                "ananyaporn13000.tripod.com",
                "xxxpornxxx.tripod.com"
            ];
            var flag = false;
            
            for( var i=0; i<blockedDomains.length; i++ )
            {
                if( href.search( blockedDomains[ i ] ) >= 0 )
                {
                    flag = true;
                }
            }
            return flag;
        }

        var getMetaContent = function( metaName )
        {
            var metas = document.getElementsByTagName('meta');
            for (i=0; i<metas.length; i++)
            { 
                if( metas[i].getAttribute("name") == metaName )
                { 
                    return metas[i].getAttribute("content"); 
                } 
            }
            return false;
        }
        
        var getCommentNodes = function(regexPattern)
        {
            var nodes = {};
            var nodesA = [];
            var preferredNodesList = ['a', 'c', 'b'];
        
            (function getNodesThatHaveComments(n, pattern)
            {
                if (n.hasChildNodes())
                {
                    if (n.tagName === 'IFRAME')
                    {
                        return false;
                    }
                    for (var i = 0; i < n.childNodes.length; i++)
                    {
                        if ((n.childNodes[i].nodeType === 8) && (pattern.test(n.childNodes[i].nodeValue)))
                        {
                            var areaName = pattern.exec(n.childNodes[i].nodeValue)[1];
                            nodes[areaName] = n;
                        }
                        else if (n.childNodes[i].nodeType === 1)
                        {
                            getNodesThatHaveComments(n.childNodes[i], pattern);
                        }
                    }
                }
            }(document.body, regexPattern));

            for (var i in preferredNodesList)
            {
                if (nodes[preferredNodesList[i]])
                {
                    if( isTrellix && nodes[preferredNodesList[i]].parentNode.parentNode.parentNode.parentNode )
                    {
                        nodesA.push(nodes[preferredNodesList[i]].parentNode.parentNode.parentNode.parentNode);
                    }
                    else
                    {
                        nodesA.push( nodes[preferredNodesList[i]] );
                    }
                }
            }
            return nodesA;
        }
        
        
        var properNode = null;
        var areaNodes = getCommentNodes( new RegExp( '^area Type="area_(\\w+)"' ) );

        for (var i = 0; i < areaNodes.length; i++)
        {
            var a = parseInt(getComputedStyle(areaNodes[i]).width);
            if ((a >= 300) && (a <= 400))
            {
                properNode = areaNodes[i];
                break;
            }
        }


        var propertyName = getMetaContent("property") || false;
        if( isTrellix && (properNode) )
        {
            e.src = '/adm/ad/injectAd.iframe.html';
            properNode.insertBefore(e, properNode.firstChild);
        }
        else if( isTrellix && !( properNode ) ) // Slap the ad eventhought there is no alocated slot
        {
            e.src = '/adm/ad/injectAd.iframe.html';
            e.style.cssFloat = 'none';
            var cdiv = document.createElement('div');
            cdiv.style = "width:300px;margin:10px auto;";
            cdiv.appendChild( e );
            b.insertBefore(cdiv, b.lastChild);
        }
        else if( !isBlokedByDomain( location.href ) )
        {
            var injF = document.createElement('iframe');
            injF.style.border = '0';
            injF.style.margin = 0;
            injF.style.display = 'block';
            injF.style.cssFloat = 'none';
            injF.style.height = '254px';
            injF.style.overflow = 'hidden';
            injF.style.padding = 0;
            injF.style.width = '300px';
            injF.src = '/adm/ad/injectAd.iframe.html';

            if( b && ( !isTrellix || ( typeof isTrellix == "undefined" ) ) ) // All other tripod props
            {
                var cdiv = document.createElement('div');
                cdiv.style = "width:300px;margin:10px auto;";
                cdiv.appendChild( injF );
                b.insertBefore(cdiv, b.lastChild);
            } 
        }
  }( document.isTrellix ));
}

</script>

<div id="tb_container" style="background:#DFDCCF; border-bottom:1px solid #393939; position:relative; z-index:999999999!important">
<!--form name="search" onSubmit="return searchit()" id='header_search' >
<input type="text" placeholder="Search" size=30 name="search2" value="">
<input type="button" value="Go!" onClick="searchit()">
</form>
<style>
form#header_search {
    width: 916px;
    margin: 0 auto 8px;
    position: relative;
}


form#header_search input {
    height: 40px;
    font-size: 14px;
    line-height: 40px;
    padding: 0 8px;
    box-sizing: border-box;
    background: #F4F2E9;
    border: 1px solid #BBB8B8;
    transition: background-color 300ms ease-out,
                color 300ms ease;
}

form#header_search input[type="text"] {
    width: 100%;
}
form#header_search input[type="text"]:focus {
    border-color: #A2D054;
    background-color: #fff;
    box-shadow: 0 0px 12px -4px #A2D054;
}



form#header_search input[type="button"] {
    position: absolute;
    top: 1px;
    right: 1px;
    opacity: 1;
    background: #DFDCCF;
    color: #463734;
    width: 125px;
    cursor: pointer;
    height: 38px;
    border: none;
}
form#header_search input[type="text"]:focus ~ input[type='button']:hover,
form#header_search input[type='button']:hover {
    background-color: #A5CE56;
    color: #fff;
}
form#header_search input[type="text"]:focus ~ input[type='button'] {
    background-color: #52AEDF;
    color: #fff;
}

</style>

<script>
function searchit(){
    
    // determine environment 
    var search_env 
    if (lycos_ad_www_server.indexOf(".pd.") > -1) {
       search_env = 'http://search51.pd.lycos.com/a/';
    } else if (lycos_ad_www_server.indexOf(".qa.") > -1) {
       search_env = 'http://search51.qa.lycos.com/a/';
    } else {
       search_env = 'http://search51.lycos.com/a/';
    }

var search_term = encodeURIComponent(document.search.search2.value)
var search_url = search_env+search_term;
window.open(search_url);

return false
}
</script-->
<style>
    .adCenterClass{margin:0 auto}
</style>
<div id="tb_ad" class="adCenterClass" style="display:block!important; overflow:hidden; width:916px;">

<div id="ad_container" style="display:block!important; float:left; width:728px ">
<script type="text/javascript">
if (typeof lycos_ad !== "undefined" && "leaderboard" in lycos_ad) {
  document.write(lycos_ad['leaderboard']);
}
</script>
</div>
</div>
</div>
<script type="text/javascript">
if (typeof lycos_ad !== "undefined" && "slider" in lycos_ad) {
  document.write(lycos_ad['slider']);
}
</script> <!-- added 7/22 -->
<div id="FooterAd" style="background:#DFDCCF; border-top:1px solid #393939; clear:both; display:none; width:100%!important; position:relative; z-index:999999!important; height:90px!important"> 
<div class="adCenterClass" style="display:block!important; overflow:hidden; width:916px;">
<div id="footerAd_container" style="display:block!important; float:left; width:728px">
<iframe id="lycosFooterAdiFrame" style="border:0; display:block; float:left; height:96px; overflow:hidden; padding:0; width:750px"></iframe>
</div>
</div>
</div>