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

	Checkers learning program. The target function is:

	V^(b) = w_0 + sum(1 <= i <= 6, w_i x_i)

	x_1 is the number of black checkers
	x_2 is the number of red checkers
	x_3 is the number of black kings
	x_4 is the number of red kings
	x_5 is the number of black pieces threatened by
      	red
	x_6 is the number of red pieces threatened by
	black.

	Least means square training is used.

	1 black checker
	2 black king
	3 red checker
	4 red king
*/

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

class CheckersPanel extends JPanel {
	int deltaX, deltaY;
	int x0, x1, y0, y1;
	int[][] board = null;
	
	public CheckersPanel(int iWidth, int iHeight) {
		x0 = iWidth / 8;
		x1 = 7 * x0;
		y0 = iHeight / 8;
		y1 = 7 * y0;
		deltaX = (x1 - x0) / 8;
		deltaY = (y1 - y0) / 8;
		board = new int[8][8];
		for (int i = 0; i < 8; i++)
			for (int j = 0; j < 8; j++)
				board[i][j] = 0;
	}
	
	public void paintComponent(Graphics g) {
		int i, j, piece, x, y;
  		int xUnit = deltaY / 9;
  		int yUnit = deltaY / 15;
		int[] triangle1x = new int[3], triangle1y = new int[3];
		int[] triangle2x = new int[3], triangle2y = new int[3];
		int[] triangle3x = new int[3], triangle3y = new int[3];
		
		super.paintComponent(g);
		x = x0;
		for (i = 0; i < 8; i++) {
			y = y0;
			if (i % 2 == 0) {
				for (j = 0; j < 8; j++) {
					if (j % 2 == 0) {
						g.setColor(Color.black);
						g.drawRect(x, y, deltaX, deltaY);
						g.setColor(Color.red);
						g.fillRect(x, y, deltaX, deltaY);
					}
					else {
						g.setColor(Color.black);
						g.drawRect(x, y, deltaX, deltaY);
						g.setColor(Color.black);
						g.fillRect(x, y, deltaX, deltaY);
					}
					y += deltaY;
				}
			}
			else {
				for (j = 0; j < 8; j++) {
					if (j % 2 == 0) {
						g.setColor(Color.black);
						g.drawRect(x, y, deltaX, deltaY);
						g.setColor(Color.black);
						g.fillRect(x, y, deltaX, deltaY);
					}
					else {
						g.setColor(Color.black);
						g.drawRect(x, y, deltaX, deltaY);
						g.setColor(Color.red);
						g.fillRect(x, y, deltaX, deltaY);
					}
					y += deltaY;
				}
			}
			x += deltaX;
		}
		for (i = 7; i >= 0; i--) {
			for (j = 0; j < 8; j++) {
				piece = board[i][j];
				if (piece != 0) {
					x = x0 + j * deltaX + deltaX / 4;
					y = y0 + (7 - i) * deltaY + deltaY / 4;
					if (piece == 1) {
						g.setColor(Color.blue);
						g.drawArc(x, y, deltaX / 2, deltaY / 2, 0, 360);		
						g.fillArc(x, y, deltaX / 2, deltaY / 2, 0, 360);
					}
					else if (piece == 3) {
						g.setColor(Color.red);
						g.drawArc(x, y, deltaX / 2, deltaY / 2, 0, 360);		
						g.fillArc(x, y, deltaX / 2, deltaY / 2, 0, 360);
					}
					else {
						x = x + xUnit - deltaX / 4;
						y = y + yUnit - deltaY / 4;
						if (piece == 2)
							g.setColor(Color.blue);
						else
							g.setColor(Color.red);
  						triangle1x[0] = x + xUnit;
  						triangle1y[0] = y + 13 * yUnit;
  						triangle1x[1] = x + 7 * xUnit;
  						triangle1y[1] = triangle1y[0];
  						triangle1x[2] = x + 4 * xUnit;
  						triangle1y[2] = y + 7 * yUnit;
  						triangle2x[0] = triangle1x[2];
  						triangle2y[0] = triangle1y[2];
  						triangle2x[1] = x + 2 * xUnit;
  						triangle2y[1] = y + 3 * yUnit;
  						triangle2x[2] = x + 6 * xUnit;
  						triangle2y[2] = triangle2y[1];
  						triangle3x[0] = triangle1x[2];
  						triangle3y[0] = y + 3 * yUnit;
  						triangle3x[1] = x + 3 * xUnit;
  						triangle3y[1] = y + yUnit;
  						triangle3x[2] = x + 5 * xUnit;
  						triangle3y[2] = triangle3y[1];
						g.fillPolygon(triangle1x, triangle1y, 3);
						g.fillPolygon(triangle2x, triangle2y, 3);
						g.fillPolygon(triangle3x, triangle3y, 3);
					}
				}
			}
		}
	}

	public void setBoard(int[][] b) {
		board = b;
	}
}

class CheckersFrame extends JFrame implements Runnable {
	boolean next;
	int iHeight, iWidth;
	JButton jButton1 = new JButton();
	JButton jButton2 = new JButton();
	JPanel jPanel = new JPanel();
	BorderLayout borderLayout = new BorderLayout();
	CheckersPanel checkersPanel = null;
	
	// 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 CheckersFrame() {
		String title = "Checkers by James Pate Williams, Jr. (c) 1998-2001";
		next = false;
		jButton1.setToolTipText("Next Move");
		jButton1.setText("Next Move");
		jButton1.setVerticalAlignment(SwingConstants.BOTTOM);
		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);
		checkersPanel = new CheckersPanel(iWidth, iHeight);
		contentPane.add(checkersPanel, 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) {
		checkersPanel.setBoard(board);
		checkersPanel.paintComponent(getGraphics());
	}
}

class Checkers implements Runnable {
	int jump, n;
	CheckersFrame checkersFrame = null;
	Date date = null;
	Random random = null;

	public Checkers() {
		n = 8;
		checkersFrame = new CheckersFrame();
		date = new Date();
		random = new Random(date.getTime());
	}

	boolean blackWins(int[][] board) {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (board[i][j] == 3 || board[i][j] == 4)
					return false;
		return true;
	}

	boolean redWins(int[][] board) {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (board[i][j] == 1 || board[i][j] == 2)
					return false;
		return true;
	}

	boolean blackKingJump(int r, int c, int[][] board) {
		boolean found = true, flag = false;
		int col = c, row = r;

		for (; found && row >= 0;) {
			if ((row - 2 >= 0 && col - 2 >= 0) &&
				(board[row - 1][col - 1] == 3 ||
				 board[row - 1][col - 1] == 4) &&
				 board[row - 2][col - 2] == 0) {
				board[row][col] = 0;
				board[row - 1][col - 1] = 0;
				board[row - 2][col - 2] = 2;
				flag = true;
				row = row - 2;
				col = col - 2;
			}
			else if ((row - 2 >= 0 && col + 2 < 8) &&
				(board[row - 1][col + 1] == 3 ||
			 	 board[row - 1][col + 1] == 4) &&
			 	 board[row - 2][col + 2] == 0) {
				board[row][col] = 0;
				board[row - 1][col + 1] = 0;
				board[row - 2][col + 2] = 2;
				flag = true;
				row = row - 2;
				col = col + 2;
			}
			else if ((row + 2 < 8 && col - 2 >= 0) &&
				(board[row + 1][col - 1] == 3 ||
 			 	 board[row + 1][col - 1] == 4) &&
			 	 board[row + 2][col - 2] == 0) {
				board[row][col] = 0;
				board[row + 1][col - 1] = 0;
				board[row + 2][col - 2] = 2;
				flag = true;
				row = row + 2;
				col = col - 2;
			}
			else if ((row + 2 < 8 && col + 2 < 8) &&
				(board[row + 1][col + 1] == 3 ||
			 	 board[row + 1][col + 1] == 4) &&
			 	 board[row + 2][col + 2] == 0) {
				board[row][col] = 0;
				board[row + 1][col + 1] = 0;
				board[row + 2][col + 2] = 2;
				flag = true;
				row = row + 2;
				col = col + 2;
			}
			else
				found = false;
		}
		return flag;
	}

	boolean blackCheckerJump(int r, int c, int[][] board) {
		boolean found = true, flag = false;
		int col = c, row = r;

		for (; found && row >= 0;) {
			if ((row - 2 >= 0 && col - 2 >= 0) &&
				(board[row - 1][col - 1] == 3 ||
			 	 board[row - 1][col - 1] == 4) &&
			 	 board[row - 2][col - 2] == 0) {
				board[row][col] = 0;
				board[row - 1][col - 1] = 0;
				board[row - 2][col - 2] = 1;
				flag = true;
				row = row - 2;
				col = col - 2;
			}
			if ((row - 2 >= 0 && col + 2 < 8) &&
				(board[row - 1][col + 1] == 3 ||
				 board[row - 1][col + 1] == 4) &&
				 board[row - 2][col + 2] == 0) {
				board[row][col] = 0;
				board[row - 1][col + 1] = 0;
				board[row - 2][col + 2] = 1;
				flag = true;
				row = row - 2;
				col = col + 2;
			}
			else
				found = false;
		}
		return flag;
	}

	boolean redKingJump(int r, int c, int[][] board) {
		boolean found = true, flag = false;
		int col = c, row = r;
		
		for (; found && row < 8;) {
			if ((row - 2 >= 0 && col - 2 >= 0) &&
				(board[row - 1][col - 1] == 1 ||
			 	 board[row - 1][col - 1] == 2) &&
			 	 board[row - 2][col - 2] == 0) {
				board[row][col] = 0;
				board[row - 1][col - 1] = 0;
				board[row - 2][col - 2] = 4;
				flag = true;
				row = row - 2;
				col = col - 2;
			}
			else if ((row - 2 >= 0 && col + 2 < 8) &&
				(board[row - 1][col + 1] == 1 ||
				 board[row - 1][col + 1] == 2) &&
				 board[row - 2][col + 2] == 0) {
				board[row][col] = 0;
				board[row - 1][col + 1] = 0;
				board[row - 2][col + 2] = 4;
				flag = true;
				row = row - 2;
				col = col + 2;
			}
			else if ((row + 2 < 8 && col - 2 >= 0) &&
				(board[row + 1][col - 1] == 1 ||
			 	 board[row + 1][col - 1] == 2) &&
			 	 board[row + 2][col - 2] == 0) {
				board[row][col] = 0;
				board[row + 1][col - 1] = 0;
				board[row + 2][col - 2] = 4;
				flag = true;
				row = row + 2;
				col = col - 2;
			}
			else if ((row + 2 < 8 && col + 2 < 8) &&
				(board[row + 1][col + 1] == 1 ||
				 board[row + 1][col + 1] == 2) &&
				 board[row + 2][col + 2] == 0) {
				board[row][col] = 0;
				board[row + 1][col + 1] = 0;
				board[row + 2][col + 2] = 4;
				flag = true;
				row = row + 2;
				col = col + 2;
			}
			else
				found = false;
		}
		return flag;
	}

	boolean redCheckerJump(int r, int c, int[][] board) {
		boolean found = true, flag = false;
		int col = c, row = r;

		for (; found && row < 8;) {
			if ((row + 2 < 8 && col - 2 >= 0) &&
				(board[row + 1][col - 1] == 1 ||
			 	 board[row + 1][col - 1] == 2) &&
			 	 board[row + 2][col - 2] == 0) {
				board[row][col] = 0;
				board[row + 1][col - 1] = 0;
				board[row + 2][col - 2] = 3;
				flag = true;
				row = row + 2;
				col = col - 2;
			}
			else if ((row + 2 < 8) && (col + 2 < 8) &&
				(board[row + 1][col + 1] == 1 ||
			 	 board[row + 1][col + 1] == 2) &&
			 	 board[row + 2][col + 2] == 0) {
				board[row][col] = 0;
				board[row + 1][col + 1] = 0;
				board[row + 2][col + 2] = 3;
				flag = true;
				row = row + 2;
				col = col + 2;
			}
			else
				found = false;
		}
		return flag;
	}		

	boolean mandatoryJump(Color color, int[][] board) {
		//returns true if jump is made, 0 otherwise
  		int i, j;
	
		jump = 0;
		//check for black to move
		if (color == Color.black) {
			//look for a mandatory jump among black checkers 
			for (i = 7; i >= 0; i--)
				for (j = i & 1; j < 8; j += 2)
					if (board[i][j] == 1)
						if (blackCheckerJump(i, j, board))
							return true;
			// check for mandatory jump among black kings
			for (i = 0; i < 8; i++)
				for (j = i & 1; j < 8; j += 2) 
					if (board[i][j] == 2)
						if (blackKingJump(i, j, board))
							return true;
		}
		else {
			// look for a mandatory jump among red checkers
			for (i = 0; i < 8; i++) 
				for (j = i & 1; j < 8; j += 2)
					if (board[i][j] == 3)
						if (redCheckerJump(i, j, board))
							return true;
			// check for mandatory jump among red kings
			for (i = 0; i < 8; i++)
				for (j = i & 1; j < 8; j += 2)
					if (board[i][j] == 4)
						 if (redKingJump(i, j, board))
							return true;
		}
		return false;
	}

	double target(double[] w, int[][] board) {
		double t = w[0];
		int i, j;
		int[] x = new int[8];
		int[][] temp = new int[8][8];

		x[0] = 1;
		for (i = 1; i < 7; i++)
			x[i] = 0;
  		//count the number of pieces on the board
  		for (i = 0; i < 8; i++) {
   			 for (j = i & 1; j < 8; j += 2) {
      				if (board[i][j] == 1)
					x[1]++;
      				else if (board[i][j] == 2)
					x[3]++;
      				else if (board[i][j] == 3)
					x[2]++;
      				else if (board[i][j] == 4)
					x[4]++;
			}
		}
		//black threatened by red
		for (i = 7; i >= 0; i--) {
			for (j = i & 1; j < 8; j += 2) {
				copyBoard(temp, board);
				if (board[i][j] == 1) 
					if (blackCheckerJump(i, j, temp))
						x[5]++;
				else if (board[i][j] == 2)
					if (blackKingJump(i, j, temp))
						x[5]++;
			}
		}
		//red threatened by black
		for (i = 0; i < 8; i++) {
			for (j = i & 1; j < 8; j += 2) {
				copyBoard(temp, board);
				if (board[i][j] == 3) 
					if (redCheckerJump(i, j, temp))
						x[6]++;
				else if (board[i][j] == 4)
					if (redKingJump(i, j, temp))
						x[6]++;
			}
		}	
		for (i = 0; i < 7; i++)
			t += w[i] * x[i];
		return t;
	}

	int move(Color color, double[] w, int[][] board) {
		// returns 1 if black wins, 2 if red wins, 0 otherwise
		double dTemp, t0;
		double[] t = new double[48];
		int count = 0, i, j;
		int[] x = new int[7];
  		//struct {int row, col;} position[48], p_temp;
		int[][] bTemp = new int[8][8];
  		int[][][] bInp = new int[48][8][8];
		int[][][] bOut = new int[48][8][8];

		if (mandatoryJump(color, board)) {
			// test for new kings
			for (i = 0; i < 8; i++) {
				if (board[0][i] == 1)
					board[0][i] = 2;
				if (board[7][i] == 3)
					board[7][i] = 4;
			}
			if (blackWins(board))
				return 1;
			if (redWins(board))
				return 2;
			return 0;
		}
		for (i = 0; i < 48; i++) {
			copyBoard(bInp[i], board);
			copyBoard(bOut[i], board);
		}
		if (color == Color.black) {
			// find all black checker moves
			for (i = 7; i >= 1; i--) {
				for (j = i & 1; j < 8; j += 2) {
					if (bInp[count][i][j] == 1) {
						if (j - 1 >= 0 && board[i - 1][j - 1] == 0) {
							bOut[count][i][j] = 0;
							bOut[count][i - 1][j - 1] = 1;
							count++;
						}
						if (j + 1 < 8 && board[i - 1][j + 1] == 0) {
							bOut[count][i][j] = 0;
							bOut[count][i - 1][j + 1] = 1;
							count++;
						}
					}
				}	
			}
			// find all black king moves
			for (i = 0; i < 8; i++) {
				for (j = i & 1; j < 8; j += 2) {
					if (bInp[count][i][j] == 2) {
						if (i - 1 >= 0 && j - 1 >= 0 &&
							bInp[count][i - 1][j - 1] == 0) {
							bOut[count][i][j] = 0;
							bOut[count][i - 1][j - 1] = 2;
							count++;
						}
						if (i - 1 >= 0 && j + 1 < 8 &&
							bInp[count][i - 1][j + 1] == 0) {
							bOut[count][i][j] = 0;
							bOut[count][i - 1][j + 1] = 2;
							count++;
						}
						if (i + 1 < 8 && j - 1 >= 0 &&
							bInp[count][i + 1][j - 1] == 0) {
							bOut[count][i][j] = 0;
							bOut[count][i + 1][j - 1] = 2;
							count++;
						}
						if (i + 1 < 8 && j + 1 < 8 &&
							bInp[count][i + 1][j + 1] == 0) {
							bOut[count][i][j] = 0;
							bOut[count][i + 1][j + 1] = 2;
							count++;
						}
					}
				}
			}
			if (count == 0)
				return 2;
		}
		else {
			// find all red checker moves
			for (i = 0; i < 7; i++) {
				for (j = i & 1; j < 8; j += 2) {
					if (bInp[count][i][j] == 3) {
						if (j - 1 >= 0 && bInp[count][i + 1][j - 1] == 0) {
							bOut[count][i][j] = 0;
							bOut[count][i + 1][j - 1] = 3;
							count++;
						}
						if (j + 1 < 8 && bInp[count][i + 1][j + 1] == 0) {
							bOut[count][i][j] = 0;
							bOut[count][i + 1][j + 1] = 3;
							count++;
						}
					}
				}
			}
			// find all red king moves
			for (i = 0; i < 8; i++) {
				for (j = i & 1; j < 8; j += 2) {
					if (bInp[count][i][j] == 4) {
						if (i - 1 >= 0 && j - 1 >= 0 &&
							bInp[count][i - 1][j - 1] == 0) {
							bOut[count][i][j] = 0;
							bOut[count][i - 1][j - 1] = 4;
							count++;
						}
						if (i - 1 >= 0 && j + 1 < 8 &&
							bInp[count][i - 1][j + 1] == 0) {
							bOut[count][i][j] = 0;
							bOut[count][i - 1][j + 1] = 4;
							count++;
						}
						if (i + 1 < 8 && j - 1 >= 0 &&
							bInp[count][i + 1][j - 1] == 0) {
							bOut[count][i][j] = 0;
							bOut[count][i + 1][j - 1] = 4;
							count++;
						}
						if (i + 1 < 8 && j + 1 < 8 &&
							bInp[count][i + 1][j + 1] == 0) {
							bOut[count][i][j] = 0;
							bOut[count][i + 1][j + 1] = 4;
							count++;
						}
					}
				}
			}
			if (count == 0)
				return 1;
		}
		for (i = 0; i < count; i++)
			t[i] = target(w, bOut[i]);
		// sort by target function value 
		for (i = 0; i < count - 1; i++) {
			for (j = i + 1; j < count; j++) {
				if (t[i] > t[j]) {
					dTemp = t[i];
					t[i] = t[j];
					t[j] = dTemp;
					bTemp = bOut[i];
					bOut[i] = bOut[j];
					bOut[j] = bTemp;
				}
			}
		}
		j = 0;
		t0 = t[0];
		for (i = 0; i < count; i++)
			if (t0 == t[i])
				j++;
			else
				break;
		copyBoard(board, bOut[random.nextInt(j)]);
		// test for new kings
		for (i = 0; i < 8; i++) {
			if (board[0][i] == 1)
				board[0][i] = 2;
			if (board[7][i] == 3)
				board[7][i] = 4;
		}
		if (blackWins(board))
			return 1;
		if (redWins(board))
			return 2;
		return 0;
	}

	void copyBoard(int[][] destin, int[][] source) {
		for (int i = 0; i < 8; i++)
			for (int j = 0; j < 8; j++)
				destin[i][j] = source[i][j];
	}

	void initBoard(int[][] board) {
		int i;

	 	zeroBoard(board);
  		for (i = 0; i < 8; i += 2) {
			board[0][i] = 3;
			board[2][i] = 3;
			board[6][i] = 1;
  		}
  		for (i = 1; i < 8; i += 2) {
			board[1][i] = 3;
			board[5][i] = 1;
			board[7][i] = 1;
  		}
	}

	void zeroBoard(int[][] board) {
		for (int i = 0; i < 8; i++)
			for (int j = 0; j < 8; j++)
				board[i][j] = 0;
	}

	public void run() {
		double[] w = new double[7];
		int m;
		int[][] board = new int[8][8];

		w[0] = 2970821.387271;
		w[1] = 3004848.086621;
		w[2] = 3013328.744006;
		w[3] = 3020611.008753;
		w[4] = 3056966.210776;
		w[5] = 3026257.028194;
		w[6] = 3032073.551093;
		initBoard(board);
		checkersFrame.draw(board);
		for (;;) {
			while (!checkersFrame.getNext())
				Thread.yield();
			m = move(Color.black, w, board);
			checkersFrame.draw(board);
			checkersFrame.setNext(false);
			if (m != 0)
				break;
			while (!checkersFrame.getNext())
				Thread.yield();
			m = move(Color.red, w, board);
			checkersFrame.draw(board);
			checkersFrame.setNext(false);
			if (m != 0)
				break;
		}
	}

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