import java.awt.*;
import java.awt.event.*;
import java.applet.Applet;

public class Tic extends Applet implements MouseListener {

	private TicCell[][] board;
	private int turn, numturn;
	
	public void init() {
		board = new TicCell[3][3];
		setLayout(new MyGridLayout(3, 3, 1f/34, 1f/34, 1, 1));
		setBackground(new Color(102, 153, 102));
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				board[i][j] = new TicCell();
				board[i][j].addMouseListener(this);
				add(board[i][j]);
			}
		}
		addMouseListener(this);
		turn = -1;
	}
	
	public boolean play(int c) {
		return play(board[c/3][c%3]);
	}
	
	public boolean play(TicCell cell) {
		boolean goon = true;
		cell.setState(turn);
		if (turn == board[0][0].getState() && board[0][0].getState() == board[0][1].getState() && board[0][1].getState() == board[0][2].getState()) {
			board[0][0].highlight(); board[0][1].highlight(); board[0][2].highlight();
			reset(1000);
			goon = false;
		}
		else if (turn == board[1][0].getState() && board[1][0].getState() == board[1][1].getState() && board[1][1].getState() == board[1][2].getState()) {
			board[1][0].highlight(); board[1][1].highlight(); board[1][2].highlight();
			reset(1000);
			goon = false;
		}
		else if (turn == board[2][0].getState() && board[2][0].getState() == board[2][1].getState() && board[2][1].getState() == board[2][2].getState()) {
			board[2][0].highlight(); board[2][1].highlight(); board[2][2].highlight();
			reset(1000);
			goon = false;
		}
		else if (turn == board[0][0].getState() && board[0][0].getState() == board[1][0].getState() && board[1][0].getState() == board[2][0].getState()) {
			board[0][0].highlight(); board[1][0].highlight(); board[2][0].highlight();
			reset(1000);
			goon = false;
		}
		else if (turn == board[0][1].getState() && board[0][1].getState() == board[1][1].getState() && board[1][1].getState() == board[2][1].getState()) {
			board[0][1].highlight(); board[1][1].highlight(); board[2][1].highlight();
			reset(1000);
			goon = false;
		}
		else if (turn == board[0][2].getState() && board[0][2].getState() == board[1][2].getState() && board[1][2].getState() == board[2][2].getState()) {
			board[0][2].highlight(); board[1][2].highlight(); board[2][2].highlight();
			reset(1000);
			goon = false;
		}
		else if (turn == board[0][0].getState() && board[0][0].getState() == board[1][1].getState() && board[1][1].getState() == board[2][2].getState()) {
			board[0][0].highlight(); board[1][1].highlight(); board[2][2].highlight();
			reset(1000);
			goon = false;
		}
		else if (turn == board[2][0].getState() && board[2][0].getState() == board[1][1].getState() && board[1][1].getState() == board[0][2].getState()) {
			board[2][0].highlight(); board[1][1].highlight(); board[0][2].highlight();
			reset(1000);
			goon = false;
		}
		else {
			numturn++;
			turn *= -1;
			if (numturn == 9) {
				reset(1000);
				goon = false;
			}
		}
		repaint();
		return goon;
	}
	
	public void mouseClicked(MouseEvent e) {
		if (e.getSource() instanceof TicCell) {
			TicCell cell = (TicCell)e.getSource();
			if (cell.getState() == 0) {
				if (play(cell)) play(think());
			}
		}
	}
	
	public void reset(int w) {
		try { Thread.sleep(w); } catch (InterruptedException ie) {}
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				board[i][j].setState(0);
			}
		}
		turn = -1;
		numturn = 0;
	}
	
	public static int maxRate(int[] board, int turn) { //rate the situation assuming that both players always choose the best move
		int w = won(board);
		if (w != 0) return w;
		int r = -2*turn, m;
		for (int i = 0; i < 9; i++) {
			if (board[i] == 0) {
				board[i] = turn;
				m = maxRate(board, -turn);
				if (turn*m > turn*r) r = m;
				board[i] = 0;
			}
		}
		if (r == -2*turn) return 0;
		return r;
	}
	
	public static double avgRate(int[] board, int turn) { //rate the situation assuming that the computer (1/x) will always choose the best move, while the human player (-1/o) will choose every possible move with equal probability
		if (turn == 1) return maxRate(board, turn);
		int w = won(board);
		if (w != 0) return w;
		double r = 0;
		int c = 0;
		for (int i = 0; i < 9; i++) {
			if (board[i] == 0) {
				board[i] = turn;
				r += avgRate(board, -turn);
				c++;
				board[i] = 0;
			}
		}
		if (c == 0) return 0;
		r /= c;
		return r;
	}
	
	public static int won(int[] board) {
		for (int t = -1; t <= 1; t += 2) {
			if (
				t == board[0] && t == board[1] && t == board[2] ||
				t == board[3] && t == board[4] && t == board[5] ||
				t == board[6] && t == board[7] && t == board[8] ||
				t == board[0] && t == board[3] && t == board[6] ||
				t == board[1] && t == board[4] && t == board[7] ||
				t == board[2] && t == board[5] && t == board[8] ||
				t == board[0] && t == board[4] && t == board[8] ||
				t == board[2] && t == board[4] && t == board[6]
			) return t;
		}
		return 0;
	}
	
	public int think() {
		int[] b = new int[9];
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				b[3*i + j] = board[i][j].getState();
			}
		}
		double[] rs = new double[9];
		double mr = -2;
		int l = -1, c = 0;
		for (int i = 0; i < 9; i++) { //fill rs with ratings and filter out non-maxes, max into mr, location of max into l, number of maxes into c
			if (b[i] == 0) {
				b[i] = turn;
				rs[i] = maxRate(b, -turn);
				b[i] = 0;
				if (rs[i] > mr) {
					mr = rs[i];
					l = i;
					c = 1;
					for (int j = 0; j < i; j++) rs[j] = -2;
				}
				else if (rs[i] == mr) {
					c++;
				}
				else {
					rs[i] = -2;
				}
			}
			else rs[i] = -2;
		}
		if (c > 1) { //if several maxes, avgRate them
			mr = -2;
			l = -1;
			c = 0;
			for (int i = 0; i < 9; i++) { //fill rs with ratings and filter out non-maxes, max into mr, location of max into l, number of maxes into c
				if (rs[i] != -2) {
					b[i] = turn;
					rs[i] = avgRate(b, -turn);
					b[i] = 0;
					if (rs[i] > mr) {
						mr = rs[i];
						l = i;
						c = 1;
						for (int j = 0; j < i; j++) rs[j] = -2;
					}
					else if (rs[i] == mr) {
						c++;
					}
					else {
						rs[i] = -2;
					}
				}
			}
		}
		if (c > 1) { //if still several maxes, randomize
			mr = -2;
			l = -1;
			c = 0;
			for (int i = 0; i < 9; i++) { //fill rs with ratings and filter out non-maxes, max into mr, location of max into l, number of maxes into c
				if (rs[i] != -2) {
					rs[i] = 2*Math.random() - 1;
					if (rs[i] > mr) {
						mr = rs[i];
						l = i;
						c = 1;
						for (int j = 0; j < i; j++) rs[j] = -2;
					}
					else if (rs[i] == mr) {
						c++;
					}
					else {
						rs[i] = -2;
					}
				}
			}
		}
		return l;
	}
	
	public void mousePressed(MouseEvent e) { }
	public void mouseReleased(MouseEvent e) { }
	public void mouseEntered(MouseEvent e) { } 
	public void mouseExited(MouseEvent e) { }
	
}

public class TicCell extends Component {
	
	private int state;
	private boolean highl;
	
	public TicCell() {
		state = 0;
		setBackground(Color.white);
	}
	
	public void paint(Graphics g) {
		int w = getSize().width, h = getSize().height, l = Math.min(w, h);
		Color bg = Color.white;
		Color fg = (state == 1)?Color.red:Color.blue;
		if (highl) bg = new Color((bg.getRed()+fg.getRed())/2, (bg.getGreen()+fg.getGreen())/2, (bg.getBlue()+fg.getBlue())/2);
		g.setColor(bg);
		g.fillRect(0, 0, w, h);
		int dw = w/10, dh = h/10;
		if (dh < 1) dh = 1;
		if (dw < 1) dw = 1;
		if (state == 1) {
			int sw = 71*w/1000, sh = 71*h/1000;
			if (sh < 1) sh = 1;
			if (sw < 1) sw = 1;
			g.setColor(fg);
			int[] xs = {dw+sw, w/2, w-dw-sw, w-dw, w/2+sw, w-dw, w-dw-sw, w/2, dw+sw, dw, w/2-sw, dw};
			int[] ys = {dh, h/2-sh, dh, dh+sh, h/2, h-dh-sh, h-dh, h/2+sh, h-dh, h-dh-sh, h/2, dh+sh};
			g.fillPolygon(xs, ys, 12);
		}
		else if (state == -1) {
			g.setColor(fg);
			g.fillOval(dw, dh, w-2*dw, h-2*dh);
			g.setColor(bg);
			g.fillOval(2*dw, 2*dh, w-4*dw, h-4*dh);
		}
	}
	
	public void update(Graphics g) {
		paint(g);
	}
	
	public void setState(int s) {
		if (s == 0 || s == -1 || s == 1) {
			state = s;
			highl = false;
			update(getGraphics()); //nur "repaint()" reicht bei gewissen VMs nicht, wenn gerade nachher Tic.reset() aufgerufen wird, die den Thread einschlafen lŠsst...
		}
	}
	
	public void highlight() {
		highl = true;
		update(getGraphics()); //dito
	}
	
	public int getState() {
		return state;
	}
	
	public Dimension getPreferredSize() {
		return new Dimension(60, 60);
	}
	
	public Dimension getMinimumSize() {
		return new Dimension(10, 10);
	}

}