import java.awt.*;
import java.awt.event.*;

public class TicTacToe extends java.applet.Applet implements MouseListener,Runnable {
	boolean[][][] state;
	boolean turn=false;
	Image offscreen;
	
	public void init() {
		setBackground(Color.white);
		addMouseListener(this);
	}
	
	public void start() {
		synchronized (this) {
			state=new boolean[3][3][2];
		}
		repaint();
		if (turn)
			new Thread(this).start();
	}
	
	public void mouseClicked(MouseEvent evt) {
		try {
			int i=3*evt.getX()/getSize().width,j=3*evt.getY()/getSize().height;
			if (settled(state))
				start();
			else if (!turn && !state[i][j][0] && !state[i][j][1]) synchronized (this) {
				state[i][j][0]=true;
				turn=true;
				repaint();
				new Thread(this).start();
			}
		} catch (ArrayIndexOutOfBoundsException e) {
		}
	}
	public void mouseEntered(MouseEvent evt) {}
	public void mouseExited(MouseEvent evt) {}
	public void mousePressed(MouseEvent evt) {}
	public void mouseReleased(MouseEvent evt) {}
	
	public void run() {
		try {
			Thread.sleep(100);
		} catch (InterruptedException e) {
		}
		synchronized (this) {
			boolean[][][] best=best(state,true,3);
			if (turn && best!=null) {
				state=best;
				turn=false;
			}
		}
		repaint();
	}
	
	private static boolean settled(boolean[][][] state) {
		for (int t=0;t<2;t++)
			if (
				(state[0][0][t] && state[0][1][t] && state[0][2][t]) ||
				(state[1][0][t] && state[1][1][t] && state[1][2][t]) ||
				(state[2][0][t] && state[2][1][t] && state[2][2][t]) ||
				(state[0][0][t] && state[1][0][t] && state[2][0][t]) ||
				(state[0][1][t] && state[1][1][t] && state[2][1][t]) ||
				(state[0][2][t] && state[1][2][t] && state[2][2][t]) ||
				(state[0][0][t] && state[1][1][t] && state[2][2][t]) ||
				(state[0][2][t] && state[1][1][t] && state[2][0][t])
			)
				return true;
		for (int i=0;i<3;i++) for (int j=0;j<3;j++) 
			if (!state[i][j][0] && !state[i][j][1])
				return false;
		return true;
	}
	
	private static boolean[][][] best(boolean[][][] state,boolean turn,int depth) {
		if (settled(state) || depth<0) return null;
		boolean[][][] best=null;
		double best_value=-Integer.MAX_VALUE;
		for (int i=0;i<3;i++) for (int j=0;j<3;j++) 
			if (!state[i][j][0] && !state[i][j][1]) {
				boolean[][][] next=clone(state);
				next[i][j][turn?1:0]=true;
				double value=value(next,turn,depth-1)+Math.random();
				if (value>100)
					return next;
				else if (value>best_value) {
					best=next;
					best_value=value;
				}
			}
		return best;
	}
	
	private static double value(boolean[][][] state,boolean turn,int depth) {
		try {
			return value(best(state,!turn,depth),turn);
		} catch (NullPointerException e) {
			return value(state,turn);
		}
	}
	
	private static double value(boolean[][][] state,boolean turn) {
		double value=0;
		for (int t=0;t<2;t++)
			if (
				(state[0][0][t] && state[0][1][t] && state[0][2][t]) ||
				(state[1][0][t] && state[1][1][t] && state[1][2][t]) ||
				(state[2][0][t] && state[2][1][t] && state[2][2][t]) ||
				(state[0][0][t] && state[1][0][t] && state[2][0][t]) ||
				(state[0][1][t] && state[1][1][t] && state[2][1][t]) ||
				(state[0][2][t] && state[1][2][t] && state[2][2][t]) ||
				(state[0][0][t] && state[1][1][t] && state[2][2][t]) ||
				(state[0][2][t] && state[1][1][t] && state[2][0][t])
			)
				if ((t==0)^turn)
					value+=100;
				else
					value-=100;
		return value;
	}
	
	public static boolean[][][] clone(boolean[][][] state) {
		boolean[][][] clone=new boolean[3][3][2];
		for (int i=0;i<3;i++) for (int j=0;j<3;j++) for (int t=0;t<2;t++)
			clone[i][j][t]=state[i][j][t];
		return clone;
	}
			
	public void paint(Graphics g) {
		offscreen=createImage(getSize().width,getSize().height);
		update(g);
	}
	
	public void update(Graphics g) {
		if (offscreen==null || state==null) return;
		Graphics og=offscreen.getGraphics();
		int w=getSize().width,h=getSize().height;
		og.clearRect(0,0,w,h);
		og.setColor(Color.darkGray);
		drawLine(og,w/3,0,w/3,h);
		drawLine(og,w*2/3,0,w*2/3,h);
		drawLine(og,0,h/3,w,h/3);
		drawLine(og,0,h*2/3,w,h*2/3);
		for (int i=0;i<3;i++) for (int j=0;j<3;j++) {
			if (state[i][j][0]) {
				og.setColor(Color.red);
				drawOval(og,i*w/3,j*h/3,w/3,h/3);
			} else if (state[i][j][1]) {
				og.setColor(Color.blue);
				drawLine(og,i*w/3,j*h/3,(i+1)*w/3,(j+1)*h/3);
				drawLine(og,i*w/3,(j+1)*h/3,(i+1)*w/3,j*h/3);
			}
		}
		og.setColor(Color.orange);
		for (int t=0;t<2;t++) {
			if (state[0][0][t] && state[0][1][t] && state[0][2][t]) drawLine(og,w/6,0,w/6,h);
			if (state[1][0][t] && state[1][1][t] && state[1][2][t]) drawLine(og,w/2,0,w/2,h);
			if (state[2][0][t] && state[2][1][t] && state[2][2][t]) drawLine(og,w*5/6,0,w*5/6,h);
			if (state[0][0][t] && state[1][0][t] && state[2][0][t]) drawLine(og,0,h/6,w,h/6);
			if (state[0][1][t] && state[1][1][t] && state[2][1][t]) drawLine(og,0,h/2,w,h/2);
			if (state[0][2][t] && state[1][2][t] && state[2][2][t]) drawLine(og,0,h*5/6,w,h*5/6);
			if (state[0][0][t] && state[1][1][t] && state[2][2][t]) drawLine(og,0,0,w,h);
			if (state[0][2][t] && state[1][1][t] && state[2][0][t]) drawLine(og,0,h,w,0);
		}
		g.drawImage(offscreen,0,0,this);
	}
	
	private void drawLine(Graphics g,int x1,int y1,int x2,int y2) {
		double r1=0.1+(x1+y1)%7/70.;
		double r2=0.8+(x2+y2)%13/130.;
		double r3=(x1+y1+x2+y2)%17/3.;
		double ds=3./Math.sqrt(Math.pow(x1-x2,2)+Math.pow(y1-y2,2));
		for (double s=r1;s<r2;s+=ds)
			g.fillOval((int)((1-s)*x1+s*x2+Math.cos(s*20+r3)),(int)((1-s)*y1+s*y2+Math.sin(s*20+r3)),6,6);
	}
	
	private void drawOval(Graphics g,int x,int y,int w,int h) {
		double r1=(x+y)%13/2.;
		double r2=0.3+(x+y+w+h)%17/170.;
		double dt=3./Math.max(w/2,h/2);
		for (double t=-Math.PI;t<Math.PI;t+=dt)
			g.fillOval(
				x+w/2+(int)(w*(r2+0.01*Math.cos(t*7+r1))*Math.cos(t)),
				y+h/2+(int)(h*(r2+0.01*Math.sin(t*7+r1))*Math.sin(t)),6,6);
	}
}