/*
	Author:	James Pate Williams, Jr. (c) 2001

	From "Evolutionary Computation Toward a New Philosophy
	of Machine Intelligence" by David B. Fogel second edition

	Rule-based procedure for playing tic-tac-toe

	"1. From the array of all possible moves, select a move
	    	that has not been played
	 2. For subsequent moves:
		(a) with a 10 percent chance, move randomly, else
		(b) if a win is available, place a marker in the
			winning square, else
		(c) if a block is available, place a marker in the
			blocking square, else
		(d) if two open squares are in line with an "O",
			randomly place a marker in either of the
			two squares, else
		(e) randomly move in open square
	3. Continue step 2 until the game is completed.
	4. Continue step 1 until games with all possible second
		moves have been played." David B. Fogel p. 183
*/

import java.util.*;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

class TicTacToePanel extends JPanel {
	int deltaX, deltaY;
	int x0, x1, y0, y1;
	int[] board = null;
	
	public TicTacToePanel(int iWidth, int iHeight) {
		x0 = iWidth / 8;
		x1 = 7 * x0;
		y0 = iHeight / 8;
		y1 = 7 * y0;
		deltaX = (x1 - x0) / 3;
		deltaY = (y1 - y0) / 3;
		board = new int[9];
		for (int i = 0; i < 9; i++)
			board[i] = 0;
	}
	
	public void paintComponent(Graphics g) {
		int i, j, x, y;
		
		super.paintComponent(g);
		y = y0;
		for (i = 0; i < 3; i++) {
			x = x0;
			for (j = 0; j < 3; j++) {
				if (board[i * 3 + j] == 0) {
					g.setColor(Color.white);
					g.fillRect(x, y, deltaX, deltaY);
					g.setColor(Color.blue);
					g.drawRect(x, y, deltaX, deltaY);
				}
				else if (board[i * 3 + j] == 1) {
					g.setColor(Color.black);
					g.fillRect(x, y, deltaX, deltaY);
					g.setColor(Color.blue);
					g.drawRect(x, y, deltaX, deltaY);
				}
				else {
					g.setColor(Color.red);
					g.fillRect(x, y, deltaX, deltaY);
					g.setColor(Color.blue);
					g.drawRect(x, y, deltaX, deltaY);
				}
				x += deltaX;
			}
			y += deltaY;
		}
	}

	public void setBoard(int[] b) {
		board = new int[9];
		for (int i = 0; i < 9; i++)
			board[i] = b[i];
	}
}

class TicTacToeFrame extends JFrame implements Runnable {
	boolean next;
	int iHeight, iWidth;
	JButton jButton1 = new JButton();
	JPanel jPanel = new JPanel();
	BorderLayout borderLayout = new BorderLayout();
	TicTacToePanel ticTacToePanel;
	
	// step 3 - percentage size the window
	void setDesktopSize(JFrame frame, int wPerc, int hPerc) {
		Dimension screen = Toolkit.getDefaultToolkit().getScreenSize();
		iWidth = screen.width * wPerc / 100;
		iHeight = screen.height * hPerc / 100;
		frame.setSize(iWidth, iHeight);
	}
	
	// step 4 - center the window
	void centerOnScreen(JFrame frame) {
		Dimension screen = Toolkit.getDefaultToolkit().getScreenSize();
		Dimension window = frame.getSize();
		int iCenterX = screen.width / 2;
		int iCenterY = screen.height / 2;
		frame.setLocation(iCenterX - window.width / 2, iCenterY - window.height / 2);
	}
	
	public TicTacToeFrame() {
		String title = "TicTacToe by James Pate Williams, Jr. (c) 2001";
		next = false;
		jButton1.setToolTipText("Next Move");
		jButton1.setText("Next Move");
		jButton1.setVerticalAlignment(SwingConstants.CENTER);
		jButton1.addActionListener(new java.awt.event.ActionListener() {
			public void actionPerformed(ActionEvent e) {
				jButton1_actionPerformed(e);
			}
    		});
    		this.getContentPane().setLayout(borderLayout);
		setTitle(title);
		addWindowListener(new WindowAdapter() {
			public void windowClosing(WindowEvent event) {
				System.exit(0);
			}
		});
		setDesktopSize(this, 100, 100);
		centerOnScreen(this);
		Container contentPane = getContentPane();
		contentPane.add(jPanel, BorderLayout.SOUTH);
		jPanel.add(jButton1, BorderLayout.CENTER);
		ticTacToePanel = new TicTacToePanel(iWidth, iHeight);
		contentPane.add(ticTacToePanel, BorderLayout.CENTER);
		this.show();
		(new Thread(this)).run();
	}

	public boolean getNext() {
		return next;
	}

	public void setNext(boolean n) {
		next = n;
	}

	void jButton1_actionPerformed(ActionEvent e) {
		next = true;
	}
	
	public void run() {
		Thread.yield();
	}

	public void draw(int[] board) {
		ticTacToePanel.setBoard(board);
		ticTacToePanel.paintComponent(getGraphics());
	}
}

class TicTacToe implements Runnable {
	int[] board;

	public void run() {
		boolean[] used = null;
		int count, i, j, k, toMove;
		int[] board, move;
		Date date = new Date();
		Random random = new Random(date.getTime());
		TicTacToeFrame ticTacToeFrame = new TicTacToeFrame();

		used = new boolean[9];
		board = new int[9];
		move = new int[9];
		for (i = 0; i < 9; i++)
			board[i] = 0;
		board[random.nextInt(9)] = 1;
		for (count = i = 0; i < 8; i++)
			if (board[i] == 0)
				move[count++] = i;
		for (i = 0; i < 8; i++)
			used[i] = false;
		for (i = 0; i < 1; i++) {
			for (j = 0; j < 9; j++)
				board[j] = 0;
			do
				j = random.nextInt(8);
			while (used[j]);
			used[j] = true;
			board[move[j]] = 1;
			while (!ticTacToeFrame.getNext())
				Thread.yield();
			ticTacToeFrame.setNext(false);
			ticTacToeFrame.draw(board);
			for (count = 0; count < 8; count++) {
				if (count % 2 == 0)
					toMove = 2;
				else
					toMove = 1;
				if (random.nextDouble() < 0.1) {
					do
						j = random.nextInt(9);
					while (board[j] != 0);
					board[j] = toMove;
				}
				else if (board[1] == 1 && board[2] == 1 && board[0] == 0 && toMove == 1) {
					board[0] = 1;
					break;
				}
				else if (board[1] == 2 && board[2] == 2 && board[0] == 0 && toMove == 2) {
					board[0] = 2;
					break;
				}
				else if (board[4] == 1 && board[5] == 1 && board[3] == 0 && toMove == 1) {
					board[3] = 1;
					break;
				}
				else if (board[4] == 2 && board[5] == 2 && board[3] == 0 && toMove == 2) {
					board[3] = 2;
					break;
				}
				else if (board[7] == 1 && board[8] == 1 && board[6] == 0 && toMove == 1) {
					board[6] = 1;
					break;
				}
				else if (board[7] == 2 && board[8] == 2 && board[6] == 0 && toMove == 2) {
					board[6] = 2;
					break;
				}
				else if (board[0] == 1 && board[2] == 1 && board[1] == 0 && toMove == 1) {
					board[1] = 1;
					break;
				}
				else if (board[0] == 2 && board[2] == 2 && board[1] == 0 && toMove == 2) {
					board[1] = 2;
					break;
				}
				else if (board[3] == 1 && board[5] == 1 && board[4] == 0 && toMove == 1) {
					board[4] = 1;
					break;
				}
				else if (board[3] == 2 && board[5] == 2 && board[4] == 0 && toMove == 2) {
					board[4] = 2;
					break;
				}
				else if (board[6] == 1 && board[8] == 1 && board[7] == 0 && toMove == 1) {
					board[7] = 1;
					break;
				}
				else if (board[6] == 2 && board[8] == 2 && board[7] == 0 && toMove == 2) {
					board[7] = 2;
					break;
				}
				else if (board[0] == 1 && board[1] == 1 && board[2] == 0 && toMove == 1) {
					board[2] = 1;
					break;
				}
				else if (board[0] == 2 && board[1] == 2 && board[2] == 0 && toMove == 2) {
					board[2] = 2;
					break;
				}
				else if (board[3] == 1 && board[4] == 1 && board[5] == 0 && toMove == 1) {
					board[5] = 1;
					break;
				}
				else if (board[3] == 2 && board[4] == 2 && board[5] == 0 && toMove == 2) {
					board[5] = 2;
					break;
				}
				else if (board[6] == 1 && board[7] == 1 && board[8] == 0 && toMove == 1) {
					board[8] = 1;
					break;
				}
				else if (board[6] == 2 && board[7] == 2 && board[8] == 0 && toMove == 2) {
					board[8] = 2;
					break;
				}
				else if (board[3] == 1 && board[6] == 1 && board[0] == 0 && toMove == 1) {
					board[0] = 1;
					break;
				}
				else if (board[3] == 2 && board[6] == 2 && board[0] == 0 && toMove == 2) {
					board[0] = 2;
					break;
				}
				else if (board[4] == 1 && board[7] == 1 && board[1] == 0 && toMove == 1) {
					board[1] = 1;
					break;
				}
				else if (board[4] == 2 && board[7] == 2 && board[1] == 0 && toMove == 2) {
					board[1] = 2;
					break;
				}
				else if (board[5] == 1 && board[8] == 1 && board[2] == 0 && toMove == 1) {
					board[2] = 1;
					break;
				}
				else if (board[5] == 2 && board[8] == 2 && board[2] == 0 && toMove == 2) {
					board[2] = 2;
					break;
				}
				else if (board[0] == 1 && board[6] == 1 && board[3] == 0 && toMove == 1) {
					board[3] = 1;
					break;
				}
				else if (board[0] == 2 && board[6] == 2 && board[3] == 0 && toMove == 2) {
					board[3] = 2;
					break;
				}
				else if (board[1] == 1 && board[7] == 1 && board[4] == 0 && toMove == 1) {
					board[4] = 1;
					break;
				}
				else if (board[1] == 2 && board[7] == 2 && board[4] == 0 && toMove == 2) {
					board[4] = 2;
					break;
				}
				else if (board[2] == 1 && board[8] == 1 && board[5] == 0 && toMove == 1) {
					board[5] = 1;
					break;
				}
				else if (board[2] == 2 && board[8] == 2 && board[5] == 0 && toMove == 2) {
					board[5] = 2;
					break;
				}
				else if (board[0] == 1 && board[3] == 1 && board[6] == 0 && toMove == 1) {
					board[6] = 1;
					break;
				}
				else if (board[0] == 2 && board[3] == 2 && board[6] == 0 && toMove == 2) {
					board[6] = 2;
					break;
				}
				else if (board[1] == 1 && board[4] == 1 && board[7] == 0 && toMove == 1) {
					board[7] = 1;
					break;
				}
				else if (board[1] == 2 && board[4] == 2 && board[7] == 0 && toMove == 2) {
					board[7] = 2;
					break;
				}
				else if (board[2] == 1 && board[5] == 1 && board[8] == 0 && toMove == 1) {
					board[8] = 1;
					break;
				}
				else if (board[2] == 2 && board[5] == 2 && board[8] == 0 && toMove == 2) {
					board[8] = 2;
					break;
				}
				else if (board[4] == 1 && board[8] == 1 && board[0] == 0 && toMove == 1) {
					board[0] = 1;
					break;
				}
				else if (board[4] == 2 && board[8] == 2 && board[0] == 0 && toMove == 2) {
					board[0] = 2;
					break;
				}
				else if (board[0] == 1 && board[8] == 1 && board[4] == 0 && toMove == 1) {
					board[4] = 1;
					break;
				}
				else if (board[0] == 2 && board[8] == 2 && board[4] == 0 && toMove == 2) {
					board[4] = 2;
					break;
				}
				else if (board[0] == 1 && board[4] == 1 && board[8] == 0 && toMove == 1) {
					board[8] = 1;
					break;
				}
				else if (board[0] == 2 && board[4] == 2 && board[8] == 0 && toMove == 2) {
					board[8] = 2;
					break;
				}
				else if (board[4] == 1 && board[6] == 1 && board[2] == 0 && toMove == 1) {
					board[2] = 1;
					break;
				}
				else if (board[4] == 2 && board[6] == 2 && board[2] == 0 && toMove == 2) {
					board[2] = 2;
					break;
				}
				else if (board[2] == 1 && board[6] == 1 && board[4] == 0 && toMove == 1) {
					board[4] = 1;
					break;
				}
				else if (board[2] == 2 && board[6] == 2 && board[4] == 0 && toMove == 2) {
					board[4] = 2;
					break;
				}
				else if (board[2] == 1 && board[4] == 1 && board[6] == 0 && toMove == 1) {
					board[6] = 1;
					break;
				}
				else if (board[2] == 2 && board[4] == 2 && board[6] == 0 && toMove == 2) {
					board[6] = 2;
					break;
				}
				else if (board[1] == 1 && board[2] == 1 && board[0] == 0)
					board[0] = 2;
				else if (board[1] == 2 && board[2] == 2 && board[0] == 0)
					board[0] = 1;
				else if (board[4] == 1 && board[5] == 1 && board[3] == 0)
					board[3] = 2;		
				else if (board[4] == 2 && board[5] == 2 && board[3] == 0)
					board[3] = 1;
				else if (board[7] == 1 && board[8] == 1 && board[6] == 0)
					board[6] = 2;		
				else if (board[7] == 2 && board[8] == 2 && board[6] == 0)
					board[6] = 1;
				else if (board[0] == 1 && board[2] == 1 && board[1] == 0)
					board[1] = 2;
				else if (board[0] == 2 && board[2] == 2 && board[1] == 0)
					board[1] = 1;
				else if (board[3] == 1 && board[5] == 1 && board[4] == 0)
					board[4] = 2;
				else if (board[3] == 2 && board[5] == 2 && board[4] == 0)
					board[4] = 1;
				else if (board[6] == 1 && board[8] == 1 && board[7] == 0)
					board[7] = 2;		
				else if (board[6] == 2 && board[8] == 2 && board[7] == 0)
					board[7] = 1;	
				else if (board[0] == 1 && board[1] == 1 && board[2] == 0)
					board[2] = 2;
				else if (board[0] == 2 && board[1] == 2 && board[2] == 0)
					board[2] = 1;
				else if (board[3] == 1 && board[4] == 1 && board[5] == 0)
					board[5] = 2;		
				else if (board[3] == 2 && board[4] == 2 && board[5] == 0)
					board[5] = 1;
				else if (board[6] == 1 && board[7] == 1 && board[8] == 0)
					board[8] = 2;		
				else if (board[6] == 2 && board[7] == 2 && board[8] == 0)
					board[8] = 1;
				else if (board[3] == 1 && board[6] == 1 && board[0] == 0)
					board[0] = 2;
				else if (board[3] == 2 && board[6] == 2 && board[0] == 0)
					board[0] = 1;
				else if (board[4] == 1 && board[7] == 1 && board[1] == 0)
					board[1] = 2;		
				else if (board[4] == 2 && board[7] == 2 && board[1] == 0)
					board[1] = 1;
				else if (board[5] == 1 && board[8] == 1 && board[2] == 0)
					board[2] = 2;		
				else if (board[5] == 2 && board[8] == 2 && board[2] == 0)
					board[2] = 1;
				else if (board[0] == 1 && board[6] == 1 && board[3] == 0)
					board[3] = 2;
				else if (board[0] == 2 && board[6] == 2 && board[3] == 0)
					board[3] = 1;
				else if (board[1] == 1 && board[7] == 1 && board[4] == 0)
					board[4] = 2;		
				else if (board[1] == 2 && board[7] == 2 && board[4] == 0)
					board[4] = 1;
				else if (board[2] == 1 && board[8] == 1 && board[5] == 0)
					board[5] = 2;		
				else if (board[2] == 2 && board[8] == 2 && board[5] == 0)
					board[5] = 1;	
				else if (board[0] == 1 && board[3] == 1 && board[6] == 0)
					board[6] = 2;
				else if (board[0] == 2 && board[3] == 2 && board[6] == 0)
					board[6] = 1;
				else if (board[1] == 1 && board[4] == 1 && board[7] == 0)
					board[7] = 2;		
				else if (board[1] == 2 && board[4] == 2 && board[7] == 0)
					board[7] = 1;
				else if (board[2] == 1 && board[5] == 1 && board[8] == 0)
					board[8] = 2;		
				else if (board[2] == 2 && board[5] == 2 && board[8] == 0)
					board[8] = 1;
				else if (board[4] == 1 && board[8] == 1 && board[0] == 0)
					board[0] = 2;
				else if (board[4] == 2 && board[8] == 2 && board[0] == 0)
					board[0] = 1;
				else if (board[0] == 1 && board[8] == 1 && board[4] == 0)
					board[4] = 2;		
				else if (board[0] == 2 && board[8] == 2 && board[4] == 0)
					board[4] = 1;
				else if (board[0] == 1 && board[4] == 1 && board[8] == 0)
					board[8] = 2;
				else if (board[0] == 2 && board[4] == 2 && board[8] == 0)
					board[8] = 1;
				else if (board[4] == 1 && board[6] == 1 && board[2] == 0)
					board[2] = 2;
				else if (board[4] == 2 && board[6] == 2 && board[2] == 0)
					board[2] = 1;
				else if (board[2] == 1 && board[6] == 1 && board[4] == 0)
					board[4] = 2;		
				else if (board[2] == 2 && board[6] == 2 && board[4] == 0)
					board[4] = 1;
				else if (board[2] == 1 && board[4] == 1 && board[6] == 0)
					board[6] = 2;
				else if (board[2] == 2 && board[4] == 2 && board[6] == 0)
					board[6] = 1;
				else if (board[0] == 2 && board[1] == 0 && board[2] == 0) {
					if (random.nextInt(2) == 0)
						board[1] = toMove;
					else
						board[2] = toMove;
				}
				else if (board[0] == 2 && board[3] == 0 && board[6] == 0) {
					if (random.nextInt(2) == 0)
						board[3] = toMove;
					else
						board[6] = toMove;
				}
				else if (board[0] == 2 && board[4] == 0 && board[8] == 0) {
					if (random.nextInt(2) == 0)
						board[4] = toMove;
					else
						board[8] = toMove;
				}
				else if (board[1] == 2 && board[0] == 0 && board[2] == 0) {
					if (random.nextInt(2) == 0)
						board[0] = toMove;
					else
						board[2] = toMove;
				}
				else if (board[1] == 2 && board[4] == 0 && board[7] == 0) {
					if (random.nextInt(2) == 0)
						board[4] = toMove;
					else
						board[7] = toMove;
				}
				else if (board[2] == 2 && board[0] == 0 && board[1] == 0) {
					if (random.nextInt(2) == 0)
						board[0] = toMove;
					else
						board[1] = toMove;
				}					
				else if (board[2] == 2 && board[5] == 0 && board[8] == 0) {
					if (random.nextInt(2) == 0)
						board[5] = toMove;
					else
						board[8] = toMove;
				}
				else if (board[2] == 2 && board[4] == 0 && board[6] == 0) {
					if (random.nextInt(2) == 0)
						board[4] = toMove;
					else
						board[6] = toMove;
				}
				else if (board[3] == 2 && board[4] == 0 && board[5] == 0) {
					if (random.nextInt(2) == 0)
						board[4] = toMove;
					else
						board[5] = toMove;
				}
				else if (board[3] == 2 && board[0] == 0 && board[6] == 0) {
					if (random.nextInt(2) == 0)
						board[0] = toMove;
					else
						board[6] = toMove;
				}
				else if (board[4] == 2 && board[3] == 0 && board[5] == 0) {
					if (random.nextInt(2) == 0)
						board[3] = toMove;
					else
						board[5] = toMove;
				}
				else if (board[4] == 2 && board[1] == 0 && board[7] == 0) {
					if (random.nextInt(2) == 0)
						board[1] = toMove;
					else
						board[7] = toMove;
				}
				else if (board[4] == 2 && board[0] == 0 && board[8] == 0) {
					if (random.nextInt(2) == 0)
						board[0] = toMove;
					else
						board[8] = toMove;
				}
				else if (board[4] == 2 && board[2] == 0 && board[6] == 0) {
					if (random.nextInt(2) == 0)
						board[2] = toMove;
					else
						board[6] = toMove;
				}
				else if (board[5] == 2 && board[3] == 0 && board[4] == 0) {
					if (random.nextInt(2) == 0)
						board[3] = toMove;
					else
						board[4] = toMove;
				}
				else if (board[5] == 2 && board[2] == 0 && board[8] == 0) {
					if (random.nextInt(2) == 0)
						board[2] = toMove;
					else
						board[8] = toMove;
				}
				else if (board[6] == 2 && board[7] == 0 && board[8] == 0) {
					if (random.nextInt(2) == 0)
						board[7] = toMove;
					else
						board[8] = toMove;
				}
				else if (board[6] == 2 && board[0] == 0 && board[3] == 0) {
					if (random.nextInt(2) == 0)
						board[0] = toMove;
					else
						board[3] = toMove;
				}
				else if (board[6] == 2 && board[2] == 0 && board[4] == 0) {
					if (random.nextInt(2) == 0)
						board[2] = toMove;
					else
						board[4] = toMove;
				}
				else if (board[7] == 2 && board[6] == 0 && board[8] == 0) {
					if (random.nextInt(2) == 0)
						board[6] = toMove;
					else
						board[8] = toMove;
				}
				else if (board[7] == 2 && board[1] == 0 && board[4] == 0) {
					if (random.nextInt(2) == 0)
						board[1] = toMove;
					else
						board[4] = toMove;
				}
				else if (board[8] == 2 && board[6] == 0 && board[7] == 0) {
					if (random.nextInt(2) == 0)
						board[6] = toMove;
					else
						board[7] = toMove;
				}
				else if (board[8] == 2 && board[2] == 0 && board[5] == 0) {
					if (random.nextInt(2) == 0)
						board[2] = toMove;
					else
						board[5] = toMove;
				}
				else if (board[8] == 2 && board[0] == 0 && board[4] == 0) {
					if (random.nextInt(2) == 0)
						board[0] = toMove;
					else
						board[4] = toMove;
				}
				else {
					do
						j = random.nextInt(9);
					while (board[j] != 0);
					board[j] = toMove;
				}
				while (!ticTacToeFrame.getNext())
					Thread.yield();
				ticTacToeFrame.setNext(false);
				ticTacToeFrame.draw(board);
			}
			while (!ticTacToeFrame.getNext())
				Thread.yield();
			ticTacToeFrame.setNext(false);
			ticTacToeFrame.draw(board);
			while (!ticTacToeFrame.getNext())
				Thread.yield();
		}
	}

	public static void main(String[] args) {
		(new TicTacToe()).run();
	}
}