import java.util.Vector;
import java.util.Random;
import java.util.List;

interface SystemConstants
{ public static final int NONE = 0;
  public static final int NOUGHT = 1;
  public static final int CROSS = 2;

  public static final String[] symbol = { " ", "O", "X" };
}

abstract public class Game 
implements SystemConstants
{ protected Position position = new Position();
  protected Vector freePlaces = new Vector(); // of Place
  protected int nextPlayer = CROSS; 
                             // The users player
  private GuiInterface gui;
  private Persistency persistency = new Persistency(); 
  private List history = new Vector(); // of Moves

  public Game(GuiInterface g)
  { gui = g;
    for (int i = 0; i < 3; i++)
    { for (int j = 0; j < 3; j++)
      { Place pl = new Place(i,j); 
        freePlaces.add(pl);
      }
    }
  }

  private void makeMove(Place pl)
  { position.move(nextPlayer,pl);
    freePlaces.remove(pl);
    gui.setPlace(pl.getX(), pl.getY(),
                 symbol[nextPlayer]);
    history.add(new Move(nextPlayer,pl)); 
    changePlayer();
    System.out.println("New board:");
    System.out.println(position);
  }

  public void makeFirstMove()
  { if (freePlaces.size() < 9)
    { System.err.println("Can't re-make 1st move!");
      return; 
    }
    nextPlayer = NOUGHT;
    Place pl = selectFirstMove();
    makeMove(pl);
  }

  protected abstract Place selectFirstMove();

  private void changePlayer()
  { if (nextPlayer == NOUGHT)
    { nextPlayer = CROSS; }
    else
    { nextPlayer = NOUGHT; }
  }

  public boolean userMove(int x, int y)
  { Place pl = new Place(x,y);
    if (nextPlayer != CROSS)
    { System.err.println("Cannot move -- not your turn!");
      return false;
    }
    if (! freePlaces.contains(pl))
    { System.err.println("Place already occupied!");
      return false;
    }
    makeMove(pl);
    boolean over = detectWinDraw();
    if (over)  // Win or draw
    { return true; }
    Place p2 = selectMove();
    if (p2 != null)
    { makeMove(p2);   // System's response move
      detectWinDraw();
    }
    return true;
  }

  abstract protected Place selectMove();

  private boolean detectWinDraw()
  { String s = position.detectWin();
    if (s == null)  // No-one has won yet
    { boolean draw = position.detectDraw();
      if (draw)
      { gui.displayDraw();
        return true;
      }
      return false; // Neither win or draw
    }
    gui.displayWin(s);
    return true;
  }

  public void save(String file)
  { persistency.save(history,file); } 

  public void restore(String file)
  { history = persistency.restore(file); } 

  public void replay()
  { 
    position = new Position();
    ReplayThread replayer = new ReplayThread(1000,history,this); 
    replayer.start(); 
  }

  public void replayMove(Move mv)
  { int player = mv.getPlayer();
    Place pl = mv.getPlace();
    position.move(player,pl);
    System.out.println(position);
    gui.setPlace(pl.getX(), pl.getY(), symbol[player]);
  } 

  /* public static void main(String[] args)
  { Game g = new Game();
    g.makeFirstMove(); // 1,1
    g.userMove(2,0);   // 0,0
    g.userMove(2,2);   // 2,1
    g.userMove(0,1);
  } */

}

class OptimalGame extends Game 
{ public OptimalGame(GuiInterface g)
  { super(g); }

  protected Place selectFirstMove()
  { return new Place(1,1); }
  
  protected Place selectMove()
  { int bestval = 0;
    Place bestPlace = null;
    for (int i = 0; i < freePlaces.size(); i++)
    { Place pl = (Place) freePlaces.get(i);
      Position newpos = (Position) position.clone();
      newpos.move(nextPlayer,pl);
      int val = newpos.evaluate(nextPlayer);
      if (val > bestval)
      { bestPlace = pl; 
        bestval = val;
        System.out.println(newpos);
        System.out.println(val);
      }
    }
    return bestPlace;
  }
}

class MinMaxGame extends Game
{ public MinMaxGame(GuiInterface g)
  { super(g); }

  protected Place selectFirstMove()
  { return new Place(1,1); }
 
  protected Place selectMove()
  { /* Assume current turn is same as nextPlayer == NOUGHT */ 
    int bestval = -1;
    Place bestPlace = null;
    Vector free = (Vector) freePlaces.clone(); 

    // Find the best move that the player can make, out of those possible: 
    for (int i = 0; i < freePlaces.size(); i++)
    { Place pl = (Place) freePlaces.get(i);
      Position newpos = (Position) position.clone();
      free.remove(pl); 
      newpos.move(nextPlayer,pl);
      int val = evaluate(newpos,nextPlayer,3-nextPlayer,free); 
      if (val > bestval)
      { bestPlace = pl;
        bestval = val;
        System.out.println(newpos);
        System.out.println(val);
      }
    }
    return bestPlace;
  }

  private int evaluate(Position pos, int player, int turn, Vector free)
  { System.out.println("Evaluate: " + player + " " + turn + " " + free); 
    String s = pos.detectWin(); 
    if (pos.detectDraw())
    { return 0; } 

    if (s != null && s.equals(symbol[player]))
    { return 1; }
    if (s != null)
    { return -1; }   // Win for opponent


    if (player == turn) 
    { 
      int bestval = -1; 
      Place bestPlace = null; 

      for (int i = 0; i < free.size(); i++) 
      { Place pl = (Place) free.get(i); 
        Position newpos = (Position) position.clone();
        free.remove(pl); 
        Vector free1 = (Vector) free.clone(); 
        newpos.move(player,pl); 
        int val = evaluate(newpos,player,3-turn,free1); 
        if (val > bestval)
        { bestPlace = pl;
          bestval = val;
        } 
      } 
      System.out.println(bestval); 
      return bestval; 
    }

    if (player != turn)  // Find the worst possible move (for player) that 
    { int worstval = 1;  // opponent can make. 
      Place worstPlace = null; 

      for (int i = 0; i < free.size(); i++)
      { Place pl = (Place) free.get(i);
        Position newpos = (Position) position.clone();
        free.remove(pl);
        Vector free1 = (Vector) free.clone(); 
        newpos.move(turn,pl); 
        int val = evaluate(newpos,player,3-turn,free1); 
        if (val < worstval)
        { worstPlace = pl;
          worstval = val;
        }
      } 
      System.out.println(worstval); 
      return worstval; 
    }

    return 0; 
  }
    
} 

        
    
    



class RandomGame extends Game
{ Random generator = new Random();

  public RandomGame(GuiInterface g)
  { super(g); }

  protected Place selectFirstMove()
  { int index = generator.nextInt(9);
    return (Place) freePlaces.get(index);
  } // or just return selectMove(); 

  protected Place selectMove()
  { int free = freePlaces.size();
    Place bestPlace = null;
    if (free > 0)
    { int index = generator.nextInt(free);
      bestPlace = (Place) freePlaces.get(index);
    }
    return bestPlace;
  }
}

class Move implements SystemConstants
{ private int player;
  private Place place;

  public Move(int mover, Place destination)
  { player = mover;
    place = destination;
  }

  public int getPlayer()
  { return player; }

  public Place getPlace()
  { return place; } // or clone it

  public String toString()
  { return symbol[player] + " moves to " + place; }

  public String toXml()
  { return "<move> \n" + 
           "  <player>" + symbol[player] + "</player>\n" +
           "  " + place.toXml() + "\n" +
           "</move>";
  }
}
  
class Position
implements SystemConstants
{ private int[][] places = new int[3][3];

  public Position() {}

  public Position(int[][] board)
  { places = (int[][]) board.clone(); }

  public void move(int player, Place pl)
  { int x = pl.getX();
    int y = pl.getY();
    places[x][y] = player;
  }

  public int evaluate(int player)
  { if (number3lines(player) > 0)
    { return 100; } 
    else
    { return number2lines(player) + 
             (-50)*intersectingUnblockedLines() +  
             numberBlockingLines(player) +
             2*numberBlocking3lines(player);
    }
  }

  private int number3lines(int player)
  { int res = 0;

    if (places[0][0] == player &&
        places[0][1] == player &&
        places[0][2] == player)
    { res++; }
    if (places[1][0] == player &&
        places[1][1] == player &&
        places[1][2] == player)
    { res++; }
    if (places[2][0] == player &&
        places[2][1] == player &&
        places[2][2] == player)
    { res++; }
    if (places[0][0] == player &&
        places[1][0] == player &&
        places[2][0] == player)
    { res++; }
    if (places[0][1] == player &&
        places[1][1] == player &&
        places[2][1] == player)
    { res++; }
    if (places[0][2] == player &&
        places[1][2] == player &&
        places[2][2] == player)
    { res++; }
    if (places[0][0] == player &&
        places[1][1] == player &&
        places[2][2] == player)
    { res++; }
    if (places[0][2] == player &&
        places[1][1] == player &&
        places[2][0] == player)
    { res++; }
    return res;
  }

  private int number2lines(int player)
  { int res = 0;

    if (unblocked2line(places[0][0], places[0][1],
                       places[0][2], player))
    { res++; }
    if (unblocked2line(places[1][0], places[1][1],
                       places[1][2], player))
    { res++; }
    if (unblocked2line(places[2][0], places[2][1],
                       places[2][2], player))
    { res++; }
    if (unblocked2line(places[0][0], places[1][0],
                       places[2][0], player))
    { res++; }
    if (unblocked2line(places[0][1], places[1][1],
                       places[2][1], player))
    { res++; }
    if (unblocked2line(places[0][2], places[1][2],
                       places[2][2], player))
    { res++; }
    if (unblocked2line(places[0][0], places[1][1],
                       places[2][2], player))
    { res++; }
    if (unblocked2line(places[0][2], places[1][1],
                       places[2][0], player))
    { res++; }
    return res;
  }

  private int numberBlockingLines(int player)
  { int res = 0;

    if (blockingline(places[0][0], places[0][1],
                     places[0][2], player))
    { res++; }
    if (blockingline(places[1][0], places[1][1],
                     places[1][2], player))
    { res++; }
    if (blockingline(places[2][0], places[2][1],
                     places[2][2], player))
    { res++; }
    if (blockingline(places[0][0], places[1][0],
                     places[2][0], player))
    { res++; }
    if (blockingline(places[0][1], places[1][1],
                     places[2][1], player))
    { res++; }
    if (blockingline(places[0][2], places[1][2],
                     places[2][2], player))
    { res++; }
    if (blockingline(places[0][0], places[1][1],
                     places[2][2], player))
    { res++; }
    if (blockingline(places[0][2], places[1][1],
                     places[2][0], player))
    { res++; }
    return res;
  }

  private int numberBlocking3lines(int player)
  { int res = 0;

    if (blocking3line(places[0][0], places[0][1],
                      places[0][2], player))
    { res++; }
    if (blocking3line(places[1][0], places[1][1],
                      places[1][2], player))
    { res++; }
    if (blocking3line(places[2][0], places[2][1],
                      places[2][2], player))
    { res++; }
    if (blocking3line(places[0][0], places[1][0],
                      places[2][0], player))
    { res++; }
    if (blocking3line(places[0][1], places[1][1],
                      places[2][1], player))
    { res++; }
    if (blocking3line(places[0][2], places[1][2],
                      places[2][2], player))
    { res++; }
    if (blocking3line(places[0][0], places[1][1],
                      places[2][2], player))
    { res++; }
    if (blocking3line(places[0][2], places[1][1],
                      places[2][0], player))
    { res++; }
    return res;
  }

  private int intersectingUnblockedLines() 
  { // Identifies the danger situation where opponent has two unblocked 
    // 1 lines which intersect with the free place in my own unblocked 
    // 2 line: if opponent moves to that place we have lost. 
    if (places[0][0] == CROSS && places[2][2] == CROSS && places[1][1] == NOUGHT)
    { if (places[0][2] == NONE && places[0][1] == NONE && places[1][2] == NONE &&
          places[2][0] == NOUGHT)  // The wrong place to move to! 
      { return 1; } 
      if (places[2][0] == NONE && places[2][1] == NONE && places[1][0] == NONE &&
          places[0][2] == NOUGHT) 
      { return 1; }  
    } 
    else if (places[2][0] == CROSS && places[0][2] == CROSS && places[1][1] == NOUGHT)
    { if (places[2][2] == NONE && places[2][1] == NONE && places[1][2] == NONE &&
          places[0][0] == NOUGHT) 
      { return 1; } 
      if (places[0][0] == NONE && places[1][0] == NONE && places[0][1] == NONE && 
          places[2][2] == NOUGHT) 
      { return 1; } 
    } 
    return 0; 
  } 

  private boolean unblocked2line(int a, int b, int c,
                                 int player)
  { if (a == player && b == player && c == NONE)
    { return true; }
    if (a == player && b == NONE && c == player)
    { return true; }
    if (a == NONE && b == player && c == player)
    { return true; }
    return false;
  }

  
  private boolean blockingline(int a, int b, int c,
                               int player)
  { if (a == player || b == player || c == player)
    { return true; }
    return false;
  }

  private boolean blocking3line(int a, int b, int c,
                                int player)
  { int other = 3 - player; // Count
    // lines containing both player and other:
    if (a == player && b == other && c == other)
    { return true; }
    if (b == player && a == other && c == other)
    { return true; }
    if (c == player && a == other && b == other)
    { return true; }
    return false;
  }


  private boolean is3line(int a, int b, int c)
  { return a != NONE && a == b && b == c; }


  public String detectWin()
  { String res = null;
    if (is3line(places[0][0],places[0][1],places[0][2]))
    { return symbol[places[0][0]]; }
    if (is3line(places[1][0], places[1][1],
                places[1][2]))
    { return symbol[places[1][0]]; }
    if (is3line(places[2][0], places[2][1],
                places[2][2]))
    { return symbol[places[2][0]]; }
    if (is3line(places[0][0], places[1][0],
                places[2][0]))
    { return symbol[places[0][0]]; }
    if (is3line(places[0][1], places[1][1],
                places[2][1]))
    { return symbol[places[0][1]]; }
    if (is3line(places[0][2], places[1][2],
                places[2][2]))
    { return symbol[places[0][2]]; }
    if (is3line(places[0][0], places[1][1],
                places[2][2]))
    { return symbol[places[0][0]]; }
    if (is3line(places[0][2], places[1][1],
                places[2][0]))
    { return symbol[places[0][2]]; }
    return res;
  }

  public boolean detectDraw()
  { int blocksX = numberBlockingLines(CROSS);
    if (blocksX < 8) { return false; }
    int blocksO = numberBlockingLines(NOUGHT);
    if (blocksO < 8) { return false; }
    return true;  // No possibility of 3-line for either
  }

  public String toString()
  { return symbol[places[0][0]] + " | " + 
           symbol[places[1][0]] + " | " +
           symbol[places[2][0]] + "\n" +
           "---------\n" + 
           symbol[places[0][1]] + " | " + 
           symbol[places[1][1]] + " | " +
           symbol[places[2][1]] + "\n" +
           "---------\n" + 
           symbol[places[0][2]] + " | " + 
           symbol[places[1][2]] + " | " +
           symbol[places[2][2]] + "\n";
  }
 
  public Object clone()
  { int[][] copy = new int[3][3];
    for (int i = 0; i < 3; i++)
    { for (int j = 0; j < 3; j++)
      { copy[i][j] = places[i][j]; }
    }
    return new Position(copy);
  }
}


class Place
{ private int x;  /* 0..2 */
  private int y;  /* 0..2 */

  public Place(int xc, int yc)
  { x = xc;
    y = yc;
  }

  public int getX()
  { return x; }

  public int getY()
  { return y; }

  public String toString()
  { return "(" + x + "," + y + ")"; }

  public String toXml()
  { return "<place> \n" +
           "  <x>" + x + "</x>\n" +
           "  <y>" + y + "</y>\n" +
           "</place>";
  } 

  public boolean equals(Object obj)
  { if (obj instanceof Place)
    { Place other = (Place) obj;
      return other.getX() == x &&
             other.getY() == y;
    }
    return false;
  }
}