/*
Position.java - Source Code for Mobile Chess, Part I

Mobile Chess - a Chess Program for Java ME
Designed by Morning Yellow, Version: 1.05, Last Modified: Mar. 2008
Copyright (C) 2004-2008 www.elephantbase.net

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/
package chess;

import java.io.InputStream;
import java.io.PrintStream;
import java.util.Random;

public class Position {
	/*
	public static void __ASSERT(boolean cond) {
		if (!cond) {
			throw new RuntimeException();
		}
	}
	*/

	public static final int MATE_VALUE = 10000;
	public static final int WIN_VALUE = MATE_VALUE - 100;
	public static final int NULL_SAFE_MARGIN = 1000;
	public static final int NULL_OKAY_MARGIN = 500;
	public static final int DRAW_VALUE = 50;
	public static final int ADVANCED_VALUE = 10;

	public static final int MAX_MOVE_NUM = 256;
	public static final int MAX_GEN_MOVES = 128;
	public static final int MAX_BOOK_SIZE = 16384;

	public static final int PIECE_KING = 0;
	public static final int PIECE_QUEEN = 1;
	public static final int PIECE_ROOK = 2;
	public static final int PIECE_BISHOP = 3;
	public static final int PIECE_KNIGHT = 4;
	public static final int PIECE_PAWN = 5;

	public static final int DIFF_LINE = 0;
	public static final int SAME_RANK = 1;
	public static final int SAME_FILE = 2;
	public static final int SAME_DIAG_A1H8 = 3;
	public static final int SAME_DIAG_A8H1 = 4;

	public static final int RANK_TOP = 0;
	public static final int RANK_BOTTOM = 7;
	public static final int FILE_LEFT = 4;
	public static final int FILE_RIGHT = 11;

	public static final byte[] LEGAL_SPAN = new byte[] {
							 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 2, 1, 1, 1, 2, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 2, 1, 1, 1, 2, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0,
	};

	public static final byte[] SAME_LINE = new byte[] {
							 0, 0, 0, 0, 0, 0, 0, 0, 0,
		4, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 3, 0,
		0, 4, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 3, 0, 0,
		0, 0, 4, 0, 0, 0, 0, 2, 0, 0, 0, 0, 3, 0, 0, 0,
		0, 0, 0, 4, 0, 0, 0, 2, 0, 0, 0, 3, 0, 0, 0, 0,
		0, 0, 0, 0, 4, 0, 0, 2, 0, 0, 3, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 4, 0, 2, 0, 3, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 4, 2, 3, 0, 0, 0, 0, 0, 0, 0,
		1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0,
		0, 0, 0, 0, 0, 0, 3, 2, 4, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 3, 0, 2, 0, 4, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 3, 0, 0, 2, 0, 0, 4, 0, 0, 0, 0, 0,
		0, 0, 0, 3, 0, 0, 0, 2, 0, 0, 0, 4, 0, 0, 0, 0,
		0, 0, 3, 0, 0, 0, 0, 2, 0, 0, 0, 0, 4, 0, 0, 0,
		0, 3, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 4, 0, 0,
		3, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 4, 0,
		0, 0, 0, 0, 0, 0, 0,
	};

	public static final byte[] PAWN_LINE = new byte[] {
		0, 0, 0, 0, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0,
		0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0,
		0, 0, 0, 0, 5, 5, 5, 5, 5, 5, 5, 5, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 6, 6, 6, 6, 6, 6, 6, 6, 0, 0, 0, 0,
		0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0,
		0, 0, 0, 0, 4, 4, 4, 4, 4, 4, 4, 4, 0, 0, 0, 0,
	};

	public static final int[] KING_DELTA = {-17, -16, -15, -1, 1, 15, 16, 17};
	public static final int[] ROOK_DELTA = {-16, -1, 1, 16};
	public static final int[] BISHOP_DELTA = {-17, -15, 15, 17};
	public static final int[] KNIGHT_DELTA = {-33, -31, -18, -14, 14, 18, 31, 33};
	public static final int[] MMV_VALUE = {0, 900, 500, 300, 300, 100};
	public static final int[] CASTLING_DIRECTION = {1, -1, 1, -1};
	public static final int[] CASTLING_KING_SRC = {0x78, 0x78, 0x08, 0x08};
	public static final int[] CASTLING_ROOK_DST = {0x79, 0x77, 0x09, 0x07};
	public static final int[] CASTLING_KING_DST = {0x7a, 0x76, 0x0a, 0x06};
	public static final int[] CASTLING_ROOK_SRC = {0x7b, 0x74, 0x0b, 0x04};

	public static final String PIECE_STRING = "KQRBNP";

	public static final String[] STARTUP_FEN = {
		"rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1",
		"rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/R1BQKBNR w KQkq - 0 1",
		"rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/1NBQKBNR w KQkq - 0 1",
		"rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNB1KBNR w KQkq - 0 1",
	};

	public static boolean IN_BOARD(int sq) {
		return ((sq - 4) & 0x88) == 0;
	}

	public static int RANK_Y(int sq) {
		return sq >> 4;
	}

	public static int FILE_X(int sq) {
		return sq & 15;
	}

	public static int COORD_XY(int x, int y) {
		return x + (y << 4);
	}

	public static int SQUARE_FLIP(int sq) {
		return 127 - sq;
	}

	public static int SQUARE_FORWARD(int sq, int sd) {
		return sq - 16 + (sd << 5);
	}

	public static int FORWARD_DELTA(int sd) {
		return (sd << 5) - 16;
	}

	public static boolean PAWN_INIT(int sq, int sd) {
		return PAWN_LINE[sq] == sd + 1;
	}

	public static boolean PAWN_PROMOTION(int sq, int sd) {
		return PAWN_LINE[sq] == sd + 3;
	}

	public static boolean PAWN_EN_PASSANT(int sq, int sd) {
		return PAWN_LINE[sq] == sd + 5;
	}

	public static boolean KING_SPAN(int sqSrc, int sqDst) {
		return LEGAL_SPAN[sqDst - sqSrc + 128] == 1;
	}

	public static boolean KNIGHT_SPAN(int sqSrc, int sqDst) {
		return LEGAL_SPAN[sqDst - sqSrc + 128] == 2;
	}

	public static int SAME_LINE(int sqSrc, int sqDst) {
		return SAME_LINE[sqDst - sqSrc + 128];
	}

	public static int CASTLING_TYPE(int sd, int sqSrc, int sqDst) {
		return (sd << 1) + (sqDst > sqSrc ? 0 : 1);
	}

	public static int SIDE_TAG(int sd) {
		return 8 + (sd << 3);
	}

	public static int OPP_SIDE_TAG(int sd) {
		return 16 - (sd << 3);
	}

	public static int SRC(int mv) {
		return mv & 127;
	}

	public static int DST(int mv) {
		return mv >> 7;
	}

	public static int MOVE(int sqSrc, int sqDst) {
		return sqSrc + (sqDst << 7);
	}

	public static int PIECE_TYPE(int pc) {
		return pc & 7;
	}

	public static int MVV_LVA(int pc, int lva) {
		return MMV_VALUE[PIECE_TYPE(pc)] - lva;
	}

	public static int PARSE_COORD(String str, int index) {
		int sq = 0;
		if (index == str.length()) {
			return 0;
		}
		int c = str.charAt(index);
		if (c >= 'a' && c <= 'h') {
			if (index + 1 == str.length()) {
				return 0;
			}
			char c2 = str.charAt(index + 1);
			if (c2 >= '1' && c2 <= '8') {
				sq = COORD_XY(c - 'a' + FILE_LEFT, '8' - c2 + RANK_TOP);
			}
		}
		return sq;
	}

	public static int PARSE_MOVE(String str) {
		return PARSE_MOVE(str, 0);
	}

	public static int PARSE_MOVE(String str, int index) {
		return MOVE(PARSE_COORD(str, index), PARSE_COORD(str, index + 2));
	}

	public static String SQUARE_STR(int sq) {
		return "" + (char) ('a' + FILE_X(sq) - FILE_LEFT) + (char) ('8' - RANK_Y(sq) + RANK_TOP);
	}

	public static String MOVE_STR(int mv) {
		return SQUARE_STR(SRC(mv)) + SQUARE_STR(DST(mv));
	}

	public static int PreGen_zobristKeyPlayer;
	public static int PreGen_zobristLockPlayer;
	public static int[][] PreGen_zobristKeyTable = new int[12][128];
	public static int[][] PreGen_zobristLockTable = new int[12][128];

	public static Random random = new Random();

	public static int bookSize = 0;
	public static int[] bookLock = new int[MAX_BOOK_SIZE];
	public static short[] bookMove = new short[MAX_BOOK_SIZE];
	public static short[] bookValue = new short[MAX_BOOK_SIZE];

	static {
		Util.RC4 rc4 = new Util.RC4(new byte[] {0});
		PreGen_zobristKeyPlayer = rc4.nextLong();
		rc4.nextLong(); // Skip ZobristLock0
		PreGen_zobristLockPlayer = rc4.nextLong();
		for (int i = 0; i < 12; i ++) {
			for (int j = 0; j < 128; j ++) {
				PreGen_zobristKeyTable[i][j] = rc4.nextLong();
				rc4.nextLong(); // Skip ZobristLock0
				PreGen_zobristLockTable[i][j] = rc4.nextLong();
			}
		}

		InputStream in = rc4.getClass().getResourceAsStream("/book/BOOK.DAT");
		if (in != null) {
			try {
				while (bookSize < MAX_BOOK_SIZE) {
					bookLock[bookSize] = Util.readInt(in) >>> 1;
					bookMove[bookSize] = (short) Util.readShort(in);
					bookValue[bookSize] = (short) Util.readShort(in);
					bookSize ++;
				}
			} catch (Exception e) {
				// Exit "while" when IOException occurs
			}
			try {
				in.close();
			} catch (Exception e) {
				throw new RuntimeException(e.getMessage());
			}
		}
	}

	public int sdPlayer;
	public byte[] squares = new byte[128];

	public int zobristKey;
	public int zobristLock;
	public int vlWhite, vlBlack;
	public int moveNum, distance;

	public int[] mvList = new int[MAX_MOVE_NUM];
	public int[] pcList = new int[MAX_MOVE_NUM];
	public int[] keyList = new int[MAX_MOVE_NUM];
	public boolean[] chkList = new boolean[MAX_MOVE_NUM];
	public boolean[] specialMoveList = new boolean[MAX_MOVE_NUM];
	public int[] castlingBitsList = new int[MAX_MOVE_NUM];
	public int[] sqEnPassantList = new int[MAX_MOVE_NUM];

	public int[] brWhitePawn = new int[8]; // br = Bit-Rank
	public int[] brBlackPawn = new int[8]; // br = Bit-Rank
	public short[][] vlWhitePiecePos = new short[6][128];
	public short[][] vlBlackPiecePos = new short[6][128];

	public void clearBoard() {
		sdPlayer = 0;
		for (int sq = 0; sq < 128; sq ++) {
			squares[sq] = 0;
		}
		for (int i = 0; i < 8; i ++) {
			brWhitePawn[i] = brBlackPawn[i] = 0;
		}
		zobristKey = zobristLock = 0;
		vlWhite = vlBlack = 0;
	}

	public boolean captured() {
		return pcList[moveNum - 1] > 0;
	}

	public boolean inCheck() {
		return chkList[moveNum - 1];
	}

	public boolean specialMove() {
		return specialMoveList[moveNum - 1];
	}

	public int castlingBits() {
		return castlingBitsList[moveNum - 1];
	}

	public int enPassantSquare() {
		return sqEnPassantList[moveNum - 1];
	}

	public boolean canCastling(int castling) {
		if (!inCheck() && (castlingBits() & (1 << castling)) != 0) {
			int delta = CASTLING_DIRECTION[castling];
			int sqSrc = CASTLING_KING_SRC[castling] + delta;
			int sqDst = CASTLING_ROOK_SRC[castling];
			while (sqSrc != sqDst) {
				if (squares[sqSrc] > 0) {
					return false;
				}
				sqSrc += delta;
			}
			return !checked(CASTLING_ROOK_DST[castling]);
		}
		return false;
	}

	public void setIrrev() {
		setIrrev(castlingBits(), enPassantSquare());
	}

	public void setIrrev(int castlingBits, int sqEnPassant) {
		mvList[0] = pcList[0] = 0;
		castlingBitsList[0] = castlingBits;
		sqEnPassantList[0] = sqEnPassant;
		chkList[0] = checked();
		moveNum = 1;
		distance = 0;
	}

	public void addPiece(int sq, int pc, boolean del) {
		int pcAdjust;
		squares[sq] = (byte) (del ? 0 : pc);
		if (pc < 16) {
			if (pc == 8 + PIECE_PAWN) {
				brWhitePawn[RANK_Y(sq)] ^= 1 << FILE_X(sq);
			}
			pcAdjust = pc - 8;
			vlWhite += del ? -vlWhitePiecePos[pcAdjust][sq] : vlWhitePiecePos[pcAdjust][sq];
		} else {
			if (pc == 16 + PIECE_PAWN) {
				brBlackPawn[RANK_Y(sq)] ^= 1 << FILE_X(sq);
			}
			pcAdjust = pc - 16;
			vlBlack += del ? -vlBlackPiecePos[pcAdjust][sq] : vlBlackPiecePos[pcAdjust][sq];
			pcAdjust += 6;
		}
		zobristKey ^= PreGen_zobristKeyTable[pcAdjust][sq];
		zobristLock ^= PreGen_zobristLockTable[pcAdjust][sq];