/*
 * CChess    Copyright (C) 2006  wesley.wang lily.ru
 * wq1977@gmail.com rujingli@163.com
 * 
 * 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
 * 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 St, Fifth Floor, Boston, MA  02110-1301 USA
 *
 */

#define DEBUGMODE

#include "aihomesdk.h"
#include "defs14.h"
#include "cstdlib"
#include "cstring"

using namespace std;

#define PX 80
#define PY 80
#define QIZI_WIDTH 50
#define PAN_WIDTH 9
#define PAN_HEIGHT 10

char aicolor[BOARD_SIZE]= {
		0, 0, 0, 0, 0, 0, 0, 0, 0,
		7, 7, 7, 7, 7, 7, 7, 7, 7,
		7, 0, 7, 7, 7, 7, 7, 0, 7,
		0, 7, 0, 7, 0, 7, 0, 7, 0,
		7, 7, 7, 7, 7, 7, 7, 7, 7,
		7, 7, 7, 7, 7, 7, 7, 7, 7,
		1, 7, 1, 7, 1, 7, 1, 7, 1,
		7, 1, 7, 7, 7, 7, 7, 1, 7,
		7, 7, 7, 7, 7, 7, 7, 7, 7,
		1, 1, 1, 1, 1, 1, 1, 1, 1};

int aipiece[BOARD_SIZE]= {
		5, 3, 2, 1, 6, 1, 2, 3, 5,
		7, 7, 7, 7, 7, 7, 7, 7, 7,
		7, 4, 7, 7, 7, 7, 7, 4, 7,
		0, 7, 0, 7, 0, 7, 0, 7, 0,
		7, 7, 7, 7, 7, 7, 7, 7, 7,
		7, 7, 7, 7, 7, 7, 7, 7, 7,
		0, 7, 0, 7, 0, 7, 0, 7, 0,
		7, 4, 7, 7, 7, 7, 7, 4, 7,
		7, 7, 7, 7, 7, 7, 7, 7, 7,
		5, 3, 2, 1, 6, 1, 2, 3, 5};

char aimaterialnumber[2][7] = {{5, 2, 2, 2, 2, 2, 1}, {5, 2, 2, 2, 2, 2, 1}};

DATAFILE* data=NULL;
char aipointtable[7][2][90] =
	 {{{0,  0,  0,  0,  0,  0,  0,  0,  0, 			/* PAWN*/
		0,  0,  0,  0,  0,  0,  0,  0,  0,
		0,  0,  0,  0,  0,  0,  0,  0,  0,
		10,  0, 12,  0, 15,  0, 12,  0, 10,
		10,  0, 13,  0, 10,  0, 13,  0, 10,
		20, 20, 20, 20, 20, 20, 20, 20, 20,
		20, 21, 21, 22, 22, 22, 21, 21, 20,
		20, 21, 21, 23, 23, 23, 21, 21, 20,
		20, 21, 21, 23, 22, 23, 21, 21, 20,
		11, 12, 13, 14, 14, 14, 13, 12, 11},

	  {11, 12, 13, 14, 14, 14, 13, 12, 11,          /* PAWN*/
		20, 21, 21, 23, 22, 23, 21, 21, 20,
		20, 21, 21, 23, 23, 23, 21, 21, 20,
		20, 21, 21, 22, 22, 22, 21, 21, 20,
		20, 20, 20, 20, 20, 20, 20, 20, 20,
		10,  0, 13,  0, 10,  0, 13,  0, 10,
		10,  0, 12,  0, 15,  0, 12,  0, 10,
		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, 20,  0, 20,  0,  0,  0, 			/* BISHOP */
		0,  0,  0,  0, 22,  0,  0,  0,  0,
		0,  0,  0, 19,  0, 19,  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,          /* BISHOP */
		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, 19,  0, 19,  0,  0,  0,
		0,  0,  0,  0, 22,  0,  0,  0,  0,
		0,  0,  0, 20,  0, 20,  0,  0,  0}},

	  {{0,  0, 25,  0,  0,  0, 25,  0,  0, 			/* ELEPHAN */
		0,  0,  0,  0,  0,  0,  0,  0,  0,
		23,  0,  0,  0, 28,  0,  0,  0, 23,
		0,  0,  0,  0,  0,  0,  0,  0,  0,
		0,  0, 22,  0,  0,  0, 22,  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,          /* ELEPHAN */
		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, 22,  0,  0,  0, 22,  0,  0,
		0,  0,  0,  0,  0,  0,  0,  0,  0,
	   23,  0,  0,  0, 28,  0,  0,  0, 23,
		0,  0,  0,  0,  0,  0,  0,  0,  0,
		0,  0, 25,  0,  0,  0, 25,  0,  0}},

	  {{40, 35, 40, 40, 40, 40, 40, 35, 40, 		/* KNIGHT */
		40, 41, 42, 40, 20, 40, 42, 41, 40,
		40, 42, 43, 40, 40, 40, 43, 42, 40,
		40, 42, 43, 43, 43, 43, 43, 42, 40,
		40, 43, 44, 44, 44, 44, 44, 43, 40,
		40, 43, 44, 44, 44, 44, 44, 43, 40,
		40, 43, 44, 44, 44, 44, 44, 43, 40,
		40, 43, 44, 44, 44, 44, 44, 43, 40,
		40, 41, 42, 42, 42, 42, 42, 41, 40,
		40, 40, 40, 40, 40, 40, 40, 40, 40},

	   {40, 40, 40, 40, 40, 40, 40, 40, 40, 		/* KNIGHT */
		40, 41, 42, 42, 42, 42, 42, 41, 40,
		40, 43, 44, 44, 44, 44, 44, 43, 40,
		40, 43, 44, 44, 44, 44, 44, 43, 40,
		40, 43, 44, 44, 44, 44, 44, 43, 40,
		40, 43, 44, 44, 44, 44, 44, 43, 40,
		40, 42, 43, 43, 43, 43, 43, 42, 40,
		40, 42, 43, 40, 40, 40, 43, 42, 40,
		40, 41, 42, 40, 20, 40, 42, 41, 40,
		40, 35, 40, 40, 40, 40, 40, 35, 40}},

	  {{50, 50, 50, 50, 50, 50, 50, 50, 50, 		/* CANNON */
		50, 50, 50, 50, 50, 50, 50, 50, 50,
		50, 51, 53, 53, 55, 53, 53, 51, 50,
		50, 51, 50, 50, 50, 50, 50, 51, 50,
		50, 51, 51, 51, 51, 51, 51, 51, 50,
		50, 51, 50, 50, 50, 50, 50, 51, 50,
		50, 51, 50, 50, 50, 50, 50, 51, 50,
		50, 51, 50, 50, 50, 50, 50, 51, 50,
		50, 51, 50, 50, 50, 50, 50, 51, 50,
		50, 50, 50, 50, 50, 50, 50, 50, 50},

	   {50, 50, 50, 50, 50, 50, 50, 50, 50, 		/* CANNON */
		50, 51, 50, 50, 50, 50, 50, 51, 50,
		50, 51, 50, 50, 50, 50, 50, 51, 50,
		50, 51, 50, 50, 50, 50, 50, 51, 50,
		50, 51, 50, 50, 50, 50, 50, 51, 50,
		50, 51, 51, 51, 51, 51, 51, 51, 50,
		50, 51, 50, 50, 50, 50, 50, 51, 50,
		50, 51, 53, 53, 55, 53, 53, 51, 50,
		50, 50, 50, 50, 50, 50, 50, 50, 50,
		50, 50, 50, 50, 50, 50, 50, 50, 50}},


	  {{89, 92, 90, 90, 90, 90, 90, 92, 89, 		/* ROOK */
		91, 92, 90, 93, 90, 93, 90, 92, 91,
		90, 92, 90, 91, 90, 91, 90, 92, 90,
		90, 91, 90, 91, 90, 91, 90, 91, 90,
		90, 94, 90, 94, 90, 94, 90, 94, 90,
		90, 93, 90, 91, 90, 91, 90, 93, 90,
		90, 91, 90, 91, 90, 91, 90, 91, 90,
		90, 91, 90, 90, 90, 90, 90, 91, 90,
		90, 92, 91, 91, 90, 91, 91, 92, 90,
		90, 90, 90, 90, 90, 90, 90, 90, 90},

	   {90, 90, 90, 90, 90, 90, 90, 90, 90, 		/* ROOK */
		90, 92, 91, 91, 90, 91, 91, 92, 90,
		90, 91, 90, 90, 90, 90, 90, 91, 90,
		90, 91, 90, 91, 90, 91, 90, 91, 90,
		90, 93, 90, 91, 90, 91, 90, 93, 90,
		90, 94, 90, 94, 90, 94, 90, 94, 90,
		90, 91, 90, 91, 90, 91, 90, 91, 90,
		90, 92, 90, 91, 90, 91, 90, 92, 90,
		91, 92, 90, 93, 90, 93, 90, 92, 91,
		89, 92, 90, 90, 90, 90, 90, 92, 89}},

	  {{0,  0,  0, 30, 35, 30,  0,  0,  0, 			/* KING */
		0,  0,  0, 15, 15, 15,  0,  0,  0,
		0,  0,  0,  1,  1,  1,  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,          /* KING */
		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,  1,  1,  1,  0,  0,  0,
		0,  0,  0, 15, 15, 15,  0,  0,  0,
		0,  0,  0, 30, 35, 30,  0,  0,  0}}};

short aioffset[7][8] =
		{{-1, 1,13, 0, 0, 0, 0, 0},		/* PAWN {for REDSIDE side} */
		{-12,-14,12,14,0,0,0,0},		/* BISHOP */
		{-28,-24,24,28, 0, 0, 0, 0 },	/* ELEPHAN */
		{-11,-15,-25,-27,11,15,25,27},	/* KNIGHT */
		{-1, 1,-13,13, 0, 0, 0, 0},		/* CANNON */
		{-1, 1,-13,13, 0, 0, 0, 0},		/* ROOK */
		{-1, 1,-13,13, 0, 0, 0, 0}};	/* KING */

short aimailbox182[182] =
		{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
		-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
		-1,-1, 0, 1, 2, 3, 4, 5, 6, 7, 8,-1,-1,
		-1,-1, 9,10,11,12,13,14,15,16,17,-1,-1,
		-1,-1,18,19,20,21,22,23,24,25,26,-1,-1,
		-1,-1,27,28,29,30,31,32,33,34,35,-1,-1,
		-1,-1,36,37,38,39,40,41,42,43,44,-1,-1,
		-1,-1,45,46,47,48,49,50,51,52,53,-1,-1,
		-1,-1,54,55,56,57,58,59,60,61,62,-1,-1,
		-1,-1,63,64,65,66,67,68,69,70,71,-1,-1,
		-1,-1,72,73,74,75,76,77,78,79,80,-1,-1,
		-1,-1,81,82,83,84,85,86,87,88,89,-1,-1,
		-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
		-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};

short aimailbox90[90] =
		{28, 29, 30, 31, 32, 33, 34, 35, 36,
		 41, 42, 43, 44, 45, 46, 47, 48, 49,
		 54, 55, 56, 57, 58, 59, 60, 61, 62,
		 67, 68, 69, 70, 71, 72, 73, 74, 75,
		 80, 81, 82, 83, 84, 85, 86, 87, 88,
		 93, 94, 95, 96, 97, 98, 99,100,101,
		106, 107,108,109,110,111,112,113,114,
		119, 120,121,122,123,124,125,126,127,
		132, 133,134,135,136,137,138,139,140,
		145, 146,147,148,149,150,151,152,153};

short ailegalposition[90] =
		{1, 1, 5, 3, 3, 3, 5, 1, 1,
		1, 1, 1, 3, 3, 3, 1, 1, 1,
		5, 1, 1, 3, 7, 3, 1, 1, 5,
		1, 1, 1, 1, 1, 1, 1, 1, 1,
		9, 1,13, 1, 9, 1,13, 1, 9,
		9, 9, 9, 9, 9, 9, 9, 9, 9,
		9, 9, 9, 9, 9, 9, 9, 9, 9,
		9, 9, 9, 9, 9, 9, 9, 9, 9,
		9, 9, 9, 9, 9, 9, 9, 9, 9,
		9, 9, 9, 9, 9, 9, 9, 9, 9};

short aimaskpiece[7] = {8, 2, 4, 1, 1, 1, 2},
	aiknightcheck[8] = {1,-1,-9,-9,-1,1,9,9},
	aielephancheck[8] = {-10,-8,8,10,0,0,0,0},
	aikingpalace[2][9] = {{3,4,5,12,13,14,21,22,23},{66,67,68,75,76,77,84,85,86}};


class CChessAI{
public:
  int	side, xside, computerside;
  char color[BOARD_SIZE];
  int piece[BOARD_SIZE];
  move	newmove;
  double tickstart, tickend;
  unsigned long 	nodecount, brandtotal, gencount;
  char mply, follow_pv;
  char materialnumber[2][7];
  move pv[HIST_STACK];
  int history[BOARD_SIZE][BOARD_SIZE];
  int ply;
  char pointtable[7][2][90];
  short	gen_begin[HIST_STACK], gen_end[HIST_STACK];
  short offset[7][8];
  short mailbox182[182];
  short mailbox90[90];
  short legalposition[90];
  short maskpiece[7],knightcheck[8],elephancheck[8],kingpalace[2][9];
  hist_rec hist_dat[HIST_STACK];
  short	hdp;
  gen_rec	gen_dat[MOVE_STACK];
  long	capbrandtotal, capgencount;
  struct node *book, *t1, *t2;
  short	ss[4][52],  /* save 4 symmetrical kinds of line */
		nm;		/* working pointer of line */
  bool ReadingBook;

  CChessAI();
  short UpdateNewMove(void);
  void ComputerThink(void);
  short AlphaBeta(short alpha, short beta, short depth);
  short Quiescence(short alpha, short beta);
  short Eval(void);
  short GenCapture(void);
  void Gen_push(short from, short dest);
  short MoveSave (int from, int dest);
  short MakeMove(move m);
  short IsInCheck (int side);
  short Attack (int pos, int side);
  int CheckMoveLoop(void);
  void UnMakeMove(void);
  short Gen(void);
  void Check_pv (void);
  void Sort(void);
  void Quicksort(short q, short r);
  int InitGame(bool AiRed);
  void InitGen(void);
  short Readbook(void);
  void DelBook(void);
  short GetBook(void);
  short SymmetricConvert(short m, short k);
  void NextStep(void);
};

class CChess : public aihomegame{
public:
  virtual bool ProcInput(int keycode);
  virtual void Draw();
  virtual bool Init();
  virtual void Quit();
  virtual void Update();
private:
  CChessAI *ai;
  int State; //0:WaitGameStart 1:Gaming 2: Wait Game Restart
  bool AiTurn;
  bool AiRed;
  bool Selected;
  bool Moving;
  int FromX,FromY,ToX,ToY,MoveQizi;
  int HumenMoveTag,from;
  int Win,Lose,Friend;
  DATAFILE* data;
  BITMAP *qizi,*bg;
  SAMPLE *jiang;

  void DrawBoard();
  void DrawCell(short pos, short mode);
  void DrawHumenMoveTag();
  void DrawFromSelectTag();
};

short CChessAI::SymmetricConvert(short m, short k)
{
	switch (k) {
		case 0: return m;
		case 1: return m+SIZE_X-1-2*(m%SIZE_X);
		case 2: return m + (SIZE_Y-1 - 2*(m/SIZE_X))*SIZE_X;
		case 3: return BOARD_SIZE-1-m;
	}
	return m;
}

void CChessAI::NextStep(void){
	if (ReadingBook){
		if (!GetBook()) {
			ReadingBook=false;
			DelBook();
			ComputerThink();
		}
		else{
			for (int i=0; i<4; i++) {
				ss[i][nm] = SymmetricConvert(newmove.from, i);
				ss[i][nm+1] = SymmetricConvert(newmove.dest, i);
			}
			nm += 2;
		}
	}
	else{
	    ComputerThink();
	}
}

short CChessAI::GetBook(void)
{
	short k=0, sk=0, g = 0;			/* sk: symmetrical kind */
	struct node *t1;

	t1 = book;

	if (!book) return 0;

	/* Computer go first */
	if (!nm) {
		if (computerside==REDSIDE) sk = 2; else sk = 0;
		k = 0; g = 1;
	} else
		while (t1 != NULL) {
			if (nm < t1->len) {
				for(sk=0; sk<4; sk++) {
					for (k=0,g=1; k<nm; k++)
						if (ss[sk][k]!=t1->line[k]) { g=0; break;}
					if (g) break;
				}
				if (g) break;
			}
			t1 = t1->next;
		}

	/* Convert new move into normal */
	if (g) {
		newmove.from = SymmetricConvert(t1->line[k], sk);
		newmove.dest = SymmetricConvert(t1->line[k+1], sk);
	}
	return g;
}

void CChessAI::DelBook(void)
{
  if (!book) return;
  t1 = book; t2 = book->next;
  while (t1 != NULL) { free(t1); t1 = t2; if (t2) t2 = t2->next; }
  book =NULL;
}


short CChessAI::Readbook(void)
{
	short i, j, len;
	char s[255], line[52], ch;
	FILE *f;

	if ((f = fopen("BOOK.DAT", "rt"))== NULL) return 0;
	while(1) {
		/* Read a book line */
		for (j=0, ch=0; ch!='\n'; j++) {
			ch = fgetc(f); s[j] = ch;
			if (feof(f)) break;
		}
		if (feof(f)) break;

		/* Convert string into position */
		for (i=0, len=0; i<j && s[i] !=';'; i++)
			if (s[i] >= 'A') {
				line[len] = s[i]-65 + (SIZE_X-s[i+1]+48)*SIZE_X;
				i++; len++;
			}

		if (len) { 	/* save in single linked list */
		  t1 = (struct node *) malloc(sizeof(struct node));
		  t1->next = NULL; t1->len = len;
		  for (i=0; i<len; i++) t1->line[i] = line[i];
		  if (book==NULL) book = t1; else t2->next = t1;
		  t2 = t1;
		}
	}
	fclose(f);
	t1 = book;
	while (t1) {
		t1=t1->next;
	}
	return 1;
}

int CChessAI::InitGame(bool AiRed){
	nm=0;
  InitGen();
  if (AiRed){
    side = REDSIDE; 
    xside = BLACKSIDE; 
    computerside = side;
    ReadingBook=true;
	if (!Readbook()) 
	{
		ReadingBook=false;
	}
	NextStep();
	/*
	if (ReadingBook){
		if (!GetBook()) {
			ReadingBook=false;
			DelBook();
			ComputerThink();
		}
		else{
			for (int i=0; i<4; i++) {
				ss[i][nm] = SymmetricConvert(newmove.from, i);
				ss[i][nm+1] = SymmetricConvert(newmove.dest, i);
			}
			nm += 2;
		}
	}
	else{
	    ComputerThink();
	}*/
  }
  else {
    side = BLACKSIDE; 
    xside = REDSIDE; 
    computerside = xside;
	Gen();
  }
  return 0;
}

void CChessAI::InitGen(void)
{
	gen_begin[0] = 0; ply = 0; hdp = 0;
}

void CChessAI::Quicksort(short q, short r)
{
	short 	i, j, x;
	gen_rec g;

	i = q; j = r; x = gen_dat[(q+r)/2].prior;

	do {
		while (gen_dat[i].prior > x) i++;
		while (gen_dat[j].prior < x) j--;
		if (i <= j) {
			g = gen_dat[i]; gen_dat[i] = gen_dat[j];
			gen_dat[j] = g; i++; j--;
		}
	} while (i<=j);

	if (q < j) Quicksort(q, j); if (i < r) Quicksort(i, r);
}

void CChessAI::Sort(void)
{
	Quicksort(gen_begin[ply], gen_end[ply]-1);
}

void CChessAI::Check_pv (void)
{
	short i;
	for (follow_pv=0, i=gen_begin[ply]; i<gen_end[ply]; i++)
		if (gen_dat[i].m.from==pv[ply].from && gen_dat[i].m.dest==pv[ply].dest) {
			follow_pv = 1; gen_dat[i].prior += 1000; return;
		}
}

void CChessAI::UnMakeMove(void)
{
	short from, dest;
	hdp--; ply--; side = xside; xside = 1-xside;
	from = hist_dat[hdp].m.from; dest = hist_dat[hdp].m.dest;
	piece[from] = piece[dest]; color[from] = color[dest];
	piece[dest] = hist_dat[hdp].capture;
	if (piece[dest] == EMPTY) color[dest] = EMPTY; else color[dest] = xside;
	if (piece[dest] != EMPTY) materialnumber[xside][piece[dest]]++;
}

#define MAXREP 30
int CChessAI::CheckMoveLoop(void)
{
	short hdmap[MAXREP];
	short c, f, i, j, k, m, p, b;
	move cm;

	/* if (one side has not any attack pieces, it can make any move */
	if ((hdp<3) ||
	   (materialnumber[xside][ROOK]+materialnumber[xside][CANNON]+
		materialnumber[xside][KNIGHT]+materialnumber[xside][PAWN]==0))
		return 0;

	for (i=0; i<MAXREP; i++) hdmap[i] = 0;
	if (hdp>MAXREP) m = MAXREP; else m = hdp;
	c = 0; i = 0; k = 0;

	while (i<m) {
		if (hist_dat[hdp-1-i].capture!=EMPTY) return 0;
		if (hdmap[MAXREP-i]==0) {
			c++; hdmap[MAXREP-i] = c;
			p = hist_dat[hdp-1-i].m.dest; f = hist_dat[hdp-1-i].m.from;

			j = i+1;
			while (j<m) {
				if (f==hist_dat[hdp-1-j].m.dest) {
					f = hist_dat[hdp-1-j].m.from;
					hdmap[MAXREP-j] = c;
					if (p==f) {
						if (k<j) k = j;
						break;
					}
				} /* if (f */
				j++;
			} /* while (j<m) */

			if (j>m) break;
		} /* if (hdmap */
		i++;

		if (i>2 && i==k) {
			b = Attack (hist_dat[hdp-1].m.dest, xside);
			if (!b) {
				cm = hist_dat[hdp-1].m; UnMakeMove();
				b = Attack (cm.from, side);
				MakeMove (cm);
				if (b) return 0;
			}
			return 1;
		}
	} /* while (i<m) */
	return 0;
}


short	knightcheck2 [8] = {-8,-10,-8,-10,8,10,8,10};
short CChessAI::Attack (int pos, int side)
{
	short j, k, x, y, fcannon;
	char sd, xsd;

	sd = side; xsd = 1 - sd;

	for (j=0; j<4; j++) {			// ROOK, CANNON, PAWN, KING
		x = mailbox90[pos]; fcannon = 0;
		for (k=0; k<9; k++) {
			x = x + offset[ROOK][j]; y = mailbox182[x]; if (y==-1) break;
			if (!fcannon) {
				if (color[y]==xsd)
					switch (piece[y]) {
					case ROOK: return 1;
					case KING: if (piece[pos]==KING) return 1;
					case PAWN: if (k==0 &&
								  ((sd==REDSIDE && j!=2) ||
								   (sd==BLACKSIDE && j!=3))) return 1;
					}
				if (color[y]!=EMPTY) fcannon = 1;
			} else 	// CANNON case
				if (color[y] != EMPTY) {
					if (color[y]==xsd && piece[y]==CANNON) return 1;
					break;
				}
		} // for k
	} // for j

	for (j = 0; j < 8; j++)	{				// Knight Check
		y = mailbox182[mailbox90[pos]+offset[KNIGHT][j]];
		if (y==-1) continue;
		if (color[y]==xsd && piece[y]==KNIGHT && color[pos+knightcheck2[j]]==EMPTY)
			return 1;
	}
	return 0;
}

short CChessAI::IsInCheck (int side)
{
	int i, pos;
	i = 0;
	do { pos = kingpalace[side][i]; i++; } while (piece[pos]!=KING);
	return Attack(pos, side);
}


short CChessAI::MakeMove(move m)
{
	short from, dest, p;
	from = m.from; dest = m.dest; p = piece[dest];
	if (p != EMPTY) materialnumber[xside][p]--;
	hist_dat[hdp].m = m; hist_dat[hdp].capture = p;
	piece[dest] = piece[from]; piece[from] = EMPTY;
	color[dest] = color[from]; color[from] = EMPTY;
	hdp++; ply++; side = xside; xside = 1-xside;
	return p == KING;
}


short CChessAI::MoveSave (int from, int dest)
{
	move ms;
	short k;

	if (piece[dest]==KING) return 1;
	ms.from = from; ms.dest = dest;
	MakeMove (ms);
	k = IsInCheck (xside);
	if (!k) k = CheckMoveLoop();
	UnMakeMove();
	return !k;
}

void CChessAI::Gen_push(short from, short dest)
{
	if (MoveSave(from, dest)) {
		gen_dat[gen_end[ply]].m.from = from;
		gen_dat[gen_end[ply]].m.dest = dest;
		if (piece[dest]!=EMPTY)
			 gen_dat[gen_end[ply]].prior = (piece[dest]+1)*100 - piece[from];
		else gen_dat[gen_end[ply]].prior = history[from][dest];
		gen_end[ply]++;
	}
}


short CChessAI::GenCapture(void)
{
	short i, j, k, n, p, x, y, t, fcannon;

	gen_end[ply] = gen_begin[ply];

	for (i=0; i<BOARD_SIZE; i++)
		if (color[i]==side) {
			p = piece[i];
			for (j=0; j<8; j++) {
				if (offset[p][j]==0) break;
				x = mailbox90[i]; fcannon = 0;

				if (p==ROOK || p==CANNON) n = 9; else n = 1;
				for (k=0; k<n; k++) {
					if (p==PAWN && side==BLACKSIDE) x -= offset[p][j]; else x += offset[p][j];

					y = mailbox182[x];
					if (side == REDSIDE) t = y; else t = 89-y;
					if (y==-1 || (legalposition[t] & maskpiece[p])==0) break;
					if (!fcannon) {
						if (color[y] != side) {
							switch (p) {
							case KNIGHT: if (color[i+knightcheck[j]]==EMPTY && color[y]==xside) Gen_push(i, y); break;
							case ELEPHAN:if (color[i+elephancheck[j]]==EMPTY && color[y]==xside) Gen_push(i, y); break;
							case CANNON: break;
							default: if (color[y]==xside) Gen_push(i, y);
							}
						}
						if (color[y]!=EMPTY) { if (p==CANNON) fcannon = 1; else break; }
					}
					else {	/* CANNON switch */
						if (color[y]!=EMPTY) {
							if (color[y]==xside) Gen_push(i, y);
							break;
						}
					}
				} /* for k */
			} /* for j */
		}
	gen_end[ply+1] = gen_end[ply]; gen_begin[ply+1] = gen_end[ply];


	capbrandtotal += (unsigned long)gen_end[ply] - gen_begin[ply];
	if (gen_end[ply] > gen_begin[ply]) capgencount++;
	return  (gen_begin[ply] < gen_end[ply]);
}


short CChessAI::Eval(void)
{
	short i, s = 0;
	nodecount++;
	for(i=0; i<BOARD_SIZE; i++) {
		if (color[i]==REDSIDE) s += pointtable[piece[i]][REDSIDE][i];
		else if (color[i]==BLACKSIDE) s -= pointtable[piece[i]][BLACKSIDE][i];
	}
	if (side==BLACKSIDE) s = -s;
	return s; // + Bonous();
}

short CChessAI::Gen(void)
{
	short i, j, k, n, p, x, y, t, fcannon;

	gen_end[ply] = gen_begin[ply];

	for(i=0; i < BOARD_SIZE; i++)
		if (color[i]==side) {
			p = piece[i];
			for(j=0; j<8; j++) {
				if (!offset[p][j]) break;
				x = mailbox90[i]; fcannon = 0;
				if (p==ROOK || p==CANNON) n = 9; else n = 1;
				for (k=0; k<n; k++) {
					if (p==PAWN && side==BLACKSIDE) x -= offset[p][j]; else x += offset[p][j];

					y = mailbox182[x];
					if (side == REDSIDE) t = y; else t = 89-y;
					if (y==-1 || (legalposition[t] & maskpiece[p])==0) break;
					if (!fcannon) {
						if (color[y]!=side)
							switch (p) {
							case KNIGHT: if (color[i+knightcheck[j]]==EMPTY) Gen_push(i, y); break;
							case ELEPHAN:if (color[i+elephancheck[j]]==EMPTY) Gen_push(i, y); break;
							case CANNON: if (color[y]==EMPTY) Gen_push(i, y); break;
							default: Gen_push(i, y);
							}
						if (color[y]!=EMPTY) { if (p==CANNON) fcannon++; else break; }
					}
					else {	/* CANNON switch */
						if (color[y] != EMPTY) {
							if (color[y]==xside) Gen_push(i, y);
							break;
						}
					}
				} /* for k */
			} /* for j */
	}

	gen_end[ply+1] = gen_end[ply]; gen_begin[ply+1] = gen_end[ply];
	brandtotal += gen_end[ply] - gen_begin[ply]; gencount++;
	return (gen_end[ply]>gen_begin[ply]);
}

short CChessAI::Quiescence(short alpha, short beta)
{
	short i, value, best;

	if (mply < ply) {
		mply = ply;
		//gotoxy(50,13); printf("Quiescen depth   : %d  ", mply);
	}

	value = Eval();
	if (value >= beta) return value; if (value > alpha) alpha = value;

	if (!GenCapture()) {
		if (!IsInCheck(side)) return value;
		if (!Gen()) return -1000+ply;
	}

	if (follow_pv) Check_pv(); Sort(); best = -INFINITY;

	for (i=gen_begin[ply];i<gen_end[ply] && best<beta && (clock()-tickstart)<=MOVETIME; i++) {
		if (best > alpha) alpha = best;

		if (MakeMove(gen_dat[i].m)) value = 1000-ply;
		else value = -Quiescence(-beta, -alpha);
		UnMakeMove();

		if (value > best) {
			best = value; pv[ply] = gen_dat[i].m;
		}
	}

	return best;
}

short CChessAI::AlphaBeta(short alpha, short beta, short depth)
{
	short i, value, best;

	if (!depth) return Quiescence(alpha, beta);

	if(!Gen()) return -1000+ply;
	if (follow_pv) Check_pv(); Sort();
	best = -INFINITY;

	for (i=gen_begin[ply]; i<gen_end[ply] && best<beta; i++) {
		if (best > alpha) alpha = best;

		if (MakeMove(gen_dat[i].m)) value = 1000-ply;
		else value = -AlphaBeta(-beta, -alpha, depth-1);
		UnMakeMove();

		if (value > best) {
			history[gen_dat[i].m.from][gen_dat[i].m.dest] = depth;
			pv[ply] = gen_dat[i].m;
			best = value; if (!ply) newmove = gen_dat[i].m;
		}
	}

	return best;
}


CChessAI::CChessAI(){
  capbrandtotal = 0;
  capgencount = 0;
  brandtotal = 0;
  gencount = 0;
  book = NULL;
  ReadingBook=true;

  memcpy(color,aicolor,sizeof(color));
  memcpy(piece,aipiece,sizeof(aipiece));
  memcpy(materialnumber,aimaterialnumber,sizeof(aimaterialnumber));
  memcpy(pointtable,aipointtable,sizeof(aipointtable));
  memcpy(offset,aioffset,sizeof(aioffset));
  memcpy(mailbox182,aimailbox182,sizeof(aimailbox182));
  memcpy(mailbox90,aimailbox90,sizeof(aimailbox90));
  memcpy(legalposition,ailegalposition,sizeof(ailegalposition));
  memcpy(maskpiece,aimaskpiece,sizeof(aimaskpiece));
  memcpy(knightcheck,aiknightcheck,sizeof(aiknightcheck));
  memcpy(elephancheck,aielephancheck,sizeof(aielephancheck));
  memcpy(kingpalace,aikingpalace,sizeof(aikingpalace));

}

void CChessAI::ComputerThink(void)
{
	short best, i;
	tickstart = clock(); nodecount = 0;

	pv[0].from = -1;
	memset(&history, 0, sizeof(history));
	newmove.from = -1;

	for (i=1; i<=MAX_PLY; i++) {
		follow_pv = 1;
		best = AlphaBeta(-INFINITY, INFINITY, i);
	}

	/* Display some information */
	tickend = clock(); //textcolor(7);
	//gotoxy(50, 4); printf("Depth            : %d", MAX_PLY);
	//gotoxy(50, 5); printf("Node total       : %ld ", nodecount);
	//gotoxy(50, 6); printf("Brand factor     : %.2f ", (float)brandtotal/gencount);
	//gotoxy(50, 7); printf("Time (second)    : %.2f ", (tickend-tickstart)/18.23);
	//gotoxy(50, 8); printf("Nodes per second : %ld ", (long)(nodecount*18.23/(tickend-tickstart+1)));
	//gotoxy(50, 9); printf("Score            : %d ", best);
	//gotoxy(50,11); 
	//printf("Computer move    : %c%d%c%d \n", (char)(newmove.from%SIZE_X+65), (short)(SIZE_X-newmove.from/SIZE_X),
	//     (char)(newmove.dest%SIZE_X+65), (short)(SIZE_X-newmove.dest/SIZE_X));

	//	gotoxy(50,13); printf("Quiescen depth   : %d  ", mply);
	//gotoxy(50,14); printf("Quie brand factor: %.2f ", (float)capbrandtotal/capgencount);
}

short CChessAI::UpdateNewMove(void)
{
	short from, dest, p;
	from = newmove.from; dest = newmove.dest; p = piece[dest];
	if (from==-1) return 1;
	if (p != EMPTY) materialnumber[side][p]--;
	piece[dest] = piece[from]; piece[from] = EMPTY;
	color[dest] = color[from]; color[from] = EMPTY;
	return p == KING;
}

void CChess::DrawCell(short pos, short mode)
{
  
  int piece_char[] = {6,5,4,3,2,1,0};//"PBENCRK+"; /* the piece letters */
  int col;
  if (AiRed){
	  if (ai->color[pos]==REDSIDE) col=0;
  	    else col=1;
  }
  else{
	  if (ai->color[pos]==REDSIDE) col=1;
  	    else col=0;
  }

  //if (mode==NORMAL) textbackground(0); else textbackground(1);
  int x=pos%9;
  int y=pos/9;
  //MoveTo(pos%9, pos/9);
  //cprintf("%c", piece_char[piece[pos]]);*/
  if (ai->piece[pos] != 7){
    if ((Moving) && (MoveQizi==pos)){
      masked_stretch_blit(qizi,active_page,piece_char[ai->piece[pos]]*54,col*54,54,54,
			  FromX,FromY,QIZI_WIDTH,QIZI_WIDTH);
    }
    else{
      masked_stretch_blit(qizi,active_page,piece_char[ai->piece[pos]]*54,col*54,54,54,
			  PX+x*QIZI_WIDTH,PY+y*QIZI_WIDTH,QIZI_WIDTH,QIZI_WIDTH);
    }
  }
}

void CChess::DrawBoard(){
  /*
  for (int i=0;i<10;i++){
    int CurY=i*QIZI_WIDTH+QIZI_WIDTH/2;
    line(active_page, PX+QIZI_WIDTH/2,PY+CurY,PX+PAN_WIDTH*QIZI_WIDTH - QIZI_WIDTH/2, PY+CurY,0);
  } 
  
  line(active_page,PX+QIZI_WIDTH/2,PY+QIZI_WIDTH/2, PX+QIZI_WIDTH/2, PY+PAN_HEIGHT*QIZI_WIDTH - QIZI_WIDTH/2,0);
  line(active_page,PX+PAN_WIDTH*QIZI_WIDTH-QIZI_WIDTH/2,PY+QIZI_WIDTH/2, PX+PAN_WIDTH*QIZI_WIDTH-QIZI_WIDTH/2, 
       PY+PAN_HEIGHT*QIZI_WIDTH - QIZI_WIDTH/2,0);
  
  for (int i=1;i<8;i++){
    int CurX=i*QIZI_WIDTH+QIZI_WIDTH/2;
    line(active_page,PX+CurX,PY+QIZI_WIDTH/2,PX+CurX, PY+5*QIZI_WIDTH - QIZI_WIDTH/2,0);
    line(active_page,PX+CurX,PY+6*QIZI_WIDTH - QIZI_WIDTH/2,PX+CurX, PY+10*QIZI_WIDTH - QIZI_WIDTH/2,0);
  }

  line(active_page,PX+4*QIZI_WIDTH - QIZI_WIDTH/2,PY+QIZI_WIDTH/2 ,PX+6*QIZI_WIDTH - QIZI_WIDTH/2, PY+3*QIZI_WIDTH - QIZI_WIDTH/2,0);
  line(active_page,PX+6*QIZI_WIDTH - QIZI_WIDTH/2,PY+QIZI_WIDTH/2 ,PX+4*QIZI_WIDTH - QIZI_WIDTH/2, PY+3*QIZI_WIDTH - QIZI_WIDTH/2,0);
  line(active_page,PX+4*QIZI_WIDTH - QIZI_WIDTH/2,PY+10*QIZI_WIDTH - QIZI_WIDTH/2 ,PX+6*QIZI_WIDTH - QIZI_WIDTH/2, PY+8*QIZI_WIDTH - QIZI_WIDTH/2,0);
  line(active_page,PX+6*QIZI_WIDTH - QIZI_WIDTH/2,PY+10*QIZI_WIDTH - QIZI_WIDTH/2 ,PX+4*QIZI_WIDTH - QIZI_WIDTH/2, PY+8*QIZI_WIDTH - QIZI_WIDTH/2,0);
  */  
  for (int i=0; i<BOARD_SIZE; i++) DrawCell(i, NORMAL);

}

void CChess::Update(){
  int pan = 128;
  int pitch = 1000;

  if (State != 1) return;
  if (Moving){
    if ((FromX != ToX) || (FromY != ToY)){
      if (ToX>FromX) { 
	FromX+=3;
	if (FromX>ToX) FromX=ToX;
      }
      if (ToX<FromX) {
	FromX-=3;
	if (ToX>FromX) FromX=ToX;
      }
      if (ToY>FromY) {
	FromY+=3;
	if (FromY>ToY) FromY=ToY;
      }
      if (ToY<FromY){
	FromY-=3;
	if (ToY>FromY) FromY=ToY;
      }
    }
    else {
      Moving=false;

      

      if ((!AiTurn) && (ai->ReadingBook)){
      	for (int i=0; i<4; i++) {
			ai->ss[i][ai->nm] = ai->SymmetricConvert(ai->newmove.from, i);
			ai->ss[i][ai->nm+1] = ai->SymmetricConvert(ai->newmove.dest, i);
		}
		ai->nm += 2;
      }

      if (ai->UpdateNewMove()){
	State=2;
	if (!AiTurn){
	  Lose++;
	}
	else{
	  Win++;
	}
	return;
      }

      if ((ai->IsInCheck(BLACKSIDE)) || (ai->IsInCheck(REDSIDE))){
	play_sample(jiang, 255, pan, pitch, false);
      }

      AiTurn = !AiTurn;
      ai->side = ai->xside; ai->xside = 1-ai->xside;
      if (AiTurn){
	ai->NextStep();
	Moving=true;
	MoveQizi = ai->newmove.from;
	FromX = PX+ai->newmove.from % 9 *QIZI_WIDTH;
	FromY = PY+ai->newmove.from / 9 *QIZI_WIDTH;
	ToX = PX+ai->newmove.dest % 9 *QIZI_WIDTH;
	ToY = PY+ai->newmove.dest / 9 *QIZI_WIDTH;		
      }
      else{
	ai->Gen();
	if (ai->gen_end[ai->ply] - ai->gen_begin[ai->ply] == 0){
	  Lose++;
	  State=2;
	}
	Selected=false;
	}
    }
  }
}

bool CChess::ProcInput(int keycode){
  switch (keycode >> 8){
  case KEY_F2:
    {
    	if ((State==1)&&(!AiTurn)){
    		State = 2;
    		Friend++;
    	}
    }
  	break;
  case KEY_ENTER:
    if ((State==0) || (State==2)){      
      if (ai) delete(ai);
      ai = new (CChessAI);
      AiRed = !AiRed;
      AiTurn = AiRed;
      HumenMoveTag=49;
      ai->InitGame(AiRed);
      Selected =false;
      if (AiRed) {
	Moving=true;
	MoveQizi = ai->newmove.from;
	FromX = PX+ai->newmove.from % 9 *QIZI_WIDTH;
	FromY = PY+ai->newmove.from / 9 *QIZI_WIDTH;
	ToX = PX+ai->newmove.dest % 9 *QIZI_WIDTH;
	ToY = PY+ai->newmove.dest / 9 *QIZI_WIDTH;	
      }
      else{
	Moving =false;
      }
      State=1;
    }
    else {
      if (!AiTurn){
	if (!Selected){
	  if (ai->color[HumenMoveTag]==ai->side) {
	    Selected = true; from = HumenMoveTag;
	  }
	}
	else{
	  int i,t = HumenMoveTag;
	  if (ai->color[t]==ai->side) {
	    from = t; 
	  } else {
	    ai->newmove.from = from; ai->newmove.dest = t;
	    for (i=ai->gen_begin[ai->ply]; i<ai->gen_end[ai->ply]; i++){
	      if (ai->gen_dat[i].m.from==ai->newmove.from && ai->gen_dat[i].m.dest==ai->newmove.dest){
		HumenMoveTag=49;
		Moving=true;
		MoveQizi = ai->newmove.from;
		FromX = PX+ai->newmove.from % 9 *QIZI_WIDTH;
		FromY = PY+ai->newmove.from / 9 *QIZI_WIDTH;
		ToX = PX+ai->newmove.dest % 9 *QIZI_WIDTH;
		ToY = PY+ai->newmove.dest / 9 *QIZI_WIDTH;			
		from = -1;
	      }
	    }
	  }
	}
      }
    }
    return true;
  case KEY_UP:
    if ((!AiTurn) &&(HumenMoveTag>=9)) HumenMoveTag-=9;
    return true;
  case KEY_DOWN:
    if ((!AiTurn) &&(HumenMoveTag<(BOARD_SIZE-9))) HumenMoveTag+=9;
    return true;
  case KEY_LEFT:
    if ((!AiTurn) &&(HumenMoveTag>0)) HumenMoveTag-=1;
    return true;
  case KEY_RIGHT:
    if ((!AiTurn) &&(HumenMoveTag<(BOARD_SIZE-1))) HumenMoveTag+=1;
    return true;
  }
  return false;
}

void CChess::DrawFromSelectTag(){
  if (from<0) return;
  int x=from%9;
  int y=from/9;
  rect(active_page,PX+x*QIZI_WIDTH,PY+y*QIZI_WIDTH,PX+(x+1)*QIZI_WIDTH,PY+(y+1)*QIZI_WIDTH,makecol(255,0,0));
  rect(active_page,PX+x*QIZI_WIDTH+1,PY+y*QIZI_WIDTH-1,PX+(x+1)*QIZI_WIDTH-1,PY+(y+1)*QIZI_WIDTH+1,makecol(255,0,0));
  rect(active_page,PX+x*QIZI_WIDTH+2,PY+y*QIZI_WIDTH-2,PX+(x+1)*QIZI_WIDTH-2,PY+(y+1)*QIZI_WIDTH+2,makecol(255,0,0));
}

void CChess::DrawHumenMoveTag(){
  int x=HumenMoveTag%9;
  int y=HumenMoveTag/9;
  rect(active_page,PX+x*QIZI_WIDTH,PY+y*QIZI_WIDTH,PX+(x+1)*QIZI_WIDTH,PY+(y+1)*QIZI_WIDTH,makecol(255,0,0));
  rect(active_page,PX+x*QIZI_WIDTH+1,PY+y*QIZI_WIDTH-1,PX+(x+1)*QIZI_WIDTH-1,PY+(y+1)*QIZI_WIDTH+1,makecol(255,0,0));
  rect(active_page,PX+x*QIZI_WIDTH+2,PY+y*QIZI_WIDTH-2,PX+(x+1)*QIZI_WIDTH-2,PY+(y+1)*QIZI_WIDTH+2,makecol(255,0,0));
}

void CChess::Draw(){
  blit(bg, active_page, 0, 0, 0, 0, bg->w, bg->h);
  //clear_to_color(active_page,makecol(255,255,255));
  if (State>0){
    DrawBoard();
    if ((!AiTurn)&&(!Moving)){
      DrawHumenMoveTag();
      DrawFromSelectTag();
    }
  }
  textprintf_ex(active_page, font, 642, 168, 0, -1,
		"%d", Win);
  textprintf_ex(active_page, font, 642, 213, 0, -1,
		"%d", Lose);
  textprintf_ex(active_page, font, 642, 261, 0, -1,
		"%d", Friend);
  
}

bool CChess::Init()
{
  ai=NULL;
  State = 0;
  Win=Lose=Friend=0;
  Moving=false;
  data = load_datafile("big.dat");
  if (!data) {
    set_gfx_mode(GFX_TEXT, 0, 0, 0, 0);
    allegro_message("Cannot find unifont.dat in current directory.\n");
    return 1;
  }

  font = (FONT*)data[0].dat;
  qizi = load_bitmap("qizi.bmp",NULL);
  bg = load_bitmap("xqbg.bmp",NULL);
  jiang = load_sample("jiang.wav");
  if (!jiang){
    printf("Error load wav\n");
  }
  AiRed=false;
  return true;
}

void CChess::Quit(){
  if (ai) delete(ai);
  if (data) unload_datafile(data);
  destroy_bitmap(qizi);
  destroy_bitmap(bg);
  destroy_sample(jiang);
}

AIHOME_START(CChess)
/*int main(){
  CChessAI ai;
  ai.Readbook();
  return 0;
  }*/