/*******************************************************************************
 * Copyright (c) 2000, 2004 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.swt.examples.browser.demos;

public class Pawns {

	/* Current board representation in compacted form */
	byte[] game = new byte[64];
	/* Best move */
	int bestIndex = -1;
	/* Related best score */
	int bestScore = Integer.MIN_VALUE;
	/* Estimated strategic value of each cell based on proximity to walls */
	static int[] gameWallWeight = new int[64];
	Thread thread = null;
	boolean threadStop = false;
	
	final static byte EMPTY = 0;
	final static byte WHITE = 1;
	final static byte BLACK = 2;
	final static byte WALL = 3;
	
public Pawns() {
}

/* Provide the current game and ignitiate the search of the best move for the given type
 * Must return immediately as it will be called from the UI thread.
 * The UI thread will fetch the best move any time thereafter.
 */
public void playRequest(byte[][] game, int type) {
	threadStop = true;
	synchronized (this) {
		bestIndex = -1;
		bestScore = Integer.MIN_VALUE;
		convert(game, this.game);
		initPawnBorders(this.game, gameWallWeight);
		/* Quickly compute a legal move */
		for (int i = 0; i < this.game.length; i++) {
			if (this.game[i] == EMPTY) {
				bestIndex = i;
				break;
			}
		}
		new Thread() {
			public void run() {
				synchronized(Pawns.this) {
					threadStop = false;
					int[] result = new int[2];
					/* if long time, must check for threadStop and exit early */ 
					evalBest(Pawns.this.game, BLACK, 2, result);
					bestIndex = result[0];
					bestScore = result[1];
				}
			}
		}.start();
	}
}

/* Fetch best move in natural coordinates for the board previously given in
 * the call to playRequest.
 */
public void getBestMove(int[] point) {
	convert(bestIndex, point);
	threadStop = true;
}

/* Given an expanded representation of the board, format internal compact mode */
static void convert(byte[][] board, byte[] g) {
	for (int i = 0; i < board.length; i++) System.arraycopy(board[i], 0, g, i * 8, 8);
}
/* Update given compact model based on player move in natural coordinates */
static void set(byte[] g, int x, int y, byte type) {
	g[x*8+y] = type;
}
/* Given an index in compact representation, return natural coordinates */
static void convert(int index, /*out [0] x [1] y */int[] point) {
	point[0] = index / 8;
	point[1] = index % 8;
}
/* Given an index into the compact model and the neighbour code,
 * return the index of the corresponding neighbour index.
 * Returns -1 if there is no neighbour.
 * 
 * Neighbour code for the index X
 * 0 1 2
 * 3 X 4
 * 5 6 7 
 */
static int getNeighbourIndex(byte[] g, int index, int neighbour) {
	if (index < 0 || index >= g.length) return -1;
	int result = -1;
	switch (neighbour) {
		case 0: result = index < 8 || index % 8 == 0 ? -1 : index - 9; break;
		case 1: result = index < 8 ? -1 : index - 8; break;
		case 2: result = index < 8 || index % 8 == 7 ? -1 : index - 7; break;
		case 3: result = index % 8 == 0 ? -1 : index - 1; break;
		case 4: result = index % 8 == 7 ? -1 : index + 1; break;
		case 5: result = index % 8 == 0 || index >= 56 ? -1 : index + 7; break;
		case 6: result = index >= 56 ? -1 : index + 8; break;
		case 7: result = index % 8 == 7 || index >= 56 ? -1 : index + 9; break;
	}
	return result;
}
/* Make the player type play at index on given compact board 
 * Compute all pawns that must be reversed.
 */
static void play(byte[] g, int index, byte type) {
	byte opponentType = type == WHITE ? BLACK : WHITE;
	for (int neighbour = 0; neighbour <= 7; neighbour++) {
		int nIndex = getNeighbourIndex(g, index, neighbour);
		int[] reversiIndeces = new int[6];
		int nReversi = 0;
		while (nIndex != -1 && nReversi < 6 && g[nIndex] == opponentType) {
			reversiIndeces[nReversi] = nIndex;
			nReversi++;
			nIndex = getNeighbourIndex(g, nIndex, neighbour);			
		}
		if (nReversi > 0 && nIndex != -1 && g[nIndex] == type) {
			for (int i = 0; i < nReversi; i++) g[reversiIndeces[i]] = type;
		}
	}
	g[index] = type;
}
/* Evaluate the given compact model based on pawns distribution 
 * High means white has advantage. Below zero means black has advantage.
 */
static int eval(byte[] g) {
	int cntWhite = 0, cntBlack = 0, cntEmpty = 0;
	int cntWhiteWallAdvantage = 0, cntBlackWallAdvantage = 0;
	for (int i = 0; i < 64; i++) {
		if (g[i] == WHITE) {
			cntWhite++;
			cntWhiteWallAdvantage += gameWallWeight[i];
		}
		else if (g[i] == BLACK) {
			cntBlack++;
			cntBlackWallAdvantage += gameWallWeight[i];
		}
		else if (g[i] == EMPTY) cntEmpty++;
	}
	if (cntEmpty == 0) {
		if (cntWhite > cntBlack) return Integer.MAX_VALUE; /* White wins */
		if (cntWhite < cntBlack) return Integer.MIN_VALUE; /* Black wins */
		return 0; /* Stalemate */
	}
	return cntWhite + cntWhiteWallAdvantage - cntBlack - cntBlackWallAdvantage;
}

/* Recognize pawns protected by walls or borders 
 * TBD - note this should be called only once for each cell and stored
 * in a separate byte[] gWallGain
 * */
static void initPawnBorders(byte[] g, int[] gameWallWeight) {
	/* A pawn has 8 neighbours on 4 axes.
	 * Strategic pawns have one side of each axis protected by a wall and the other
	 * side not closed by a wall.
	 * A pawn cannot be reversed when each of its 4 axes are protected by a wall on
	 * one side. Pawns that have more than 4 walls are less interesting since they
	 * are not open enough to the board.
	 * 
	 * Nbr walls, nbr axis covered, estimated value
	 * 0 n/a 0
	 * 1 1 2
	 * 2 1 1
	 * 2 2 6
	 * 3 2 4
	 * 4 2 2
	 * 3 3 9
	 * 4 3 8
	 * 4 4 16
	 * 5 4 14
	 * 6 4 9
	 * 7 4 6
	 * 8 4 0
	 */
	int[] nTypes = new int[8];
	for (int i = 0; i < 64; i++) {
		int nWalls = 0;
		int nAxis = 0;
		for (int n = 0; n < 8; n++) {
			int nIndex = getNeighbourIndex(g, i, n);
			nTypes[n] = nIndex != -1 ? g[nIndex] : WALL;
			if (nTypes[n] == WALL) nWalls++;
		}
		int score = nWalls;
		if (nWalls > 0) {
			if (nTypes[0] == WALL || nTypes[7] == WALL) nAxis++;
			if (nTypes[1] == WALL || nTypes[6] == WALL) nAxis++;
			if (nTypes[2] == WALL || nTypes[5] == WALL) nAxis++;
			if (nTypes[4] == WALL || nTypes[3] == WALL) nAxis++;
			switch (nAxis) {
				case 4: switch (nWalls) { case 4: score = 16; break; case 5: score = 14; break; case 6: score = 9; case 7: score = 6; break; case 8: score = 0; break;} break;
				case 3: switch (nWalls) { case 3: score = 9; break; case 4: score = 8;} break;
				case 2: switch (nWalls) { case 2: score = 6; break; case 3: score = 4; break; case 4: score = 2; } break;
				case 1: switch (nWalls) { case 1: score = 2; break; case 2: score = 1; break;} break;
			}
		}
		gameWallWeight[i] = score;
	}
}

/* Evaluate the best move for player type for the given board, doing a depth 1 search */
static void evalBest(byte[] g, byte type, int depth, /* out [0] best move, [1] minimax */int[] result) {
	byte[] tmp = new byte[64];
	byte opponentType = type == WHITE ? BLACK : WHITE;
	result[0] = -1; result[1] = Integer.MIN_VALUE;
	for (int i = 0; i < 64; i++) {
		if (g[i] == EMPTY) {
			System.arraycopy(g, 0, tmp, 0, 64);
			play(tmp, i, type);
			int score = eval(tmp);
			if (depth > 1) {
				int[] tmpResult = new int[2];
				evalBest(tmp, opponentType, depth - 1, tmpResult);
				score = tmpResult[1];
			}
			if ((type == WHITE && score > result[1]) || (type == BLACK && score < result[1]) || result[0] == -1) {
				result[0] = i;
				result[1] = score;
			}
		}
	}
}
}