/*****************************************************
** Chess-Rikus version 1.466                        **
**   by Jeff Bischoff                               **
**                                                  **
** Note: Define the proper symbol in your compiler: **
**   UNIX or LINUX for applicable systems           **
**   WIN32 for windows systems                      **
** (ie) gcc -D LINUX ...                            **
**                                                  **
** Or use the makefile and simply choose the target **
******************************************************
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <ctype.h>
#include <errno.h>

#define TRUE 1
#define FALSE 0

#define INFINITY 0x7FFFFFFF
#define UNKNOWN 0x00EFFFFF
#define ILLEGAL 0x00DFFFFF
#define NULLCHAR 'X'
#define MATE 1000000
#define HASHMATE 900000

#define INPUTBUFFERSIZE 100

#define SHOWFULLPV

//Values for gamestate var
#define MIDDLE 1
#define END 2
#define DEEPEND 3

#define FORCEICSMODE FALSE
#define TRUST_HASH TRUE
// (bool) Turn board control scoring on or off
//#define ANALYZE_BOARD_CONTROL TRUE
// (bool) Turn search extensions on or off
#define SEARCH_EXTENSIONS TRUE
// (int) Where a leaf node can have DEPTH/MAXEXTENSIONFRACTION extensions
#define MAXEXTENSIONFRACTION 3

// (int) Max total material value in millipawns for position to be considered in endgame.
// ... Pawns are excluded from the count.
#define MAXENDGAMEVAL 20000
// (int) Max total material value for wing pawns to become more valuable than central pawns.
#define MAXDEEPENDGAMEVAL 14000

// (int) Minimum number of positions in repetitionstack to cause wariness about 3rep draw
#define MIN_ENTRIES_TO_THREATEN_3REPS 7

// (int) Lower values increase the time savings for quiet positions, but increase the number of re-searches when scores change.
#define ASPIRATIONWINDOW 500

// (float) Affects the importance of trading-down material when one side has advantage.
#define ADVANTAGE_WEIGHT 1000.0
// (int) Affects the importance of unresolved threats such as hung pieces and forked pieces.
#define THREAT_WEIGHT 300
// (int) Affects the importance of board control.
#define BOARDCONTROL_WEIGHT 5

// King safety constants
// (int) The bonus for having the right to castle.
#define CASTLINGAVAILABILITYBONUS 150
// (int) The bonus for each pawn protecting a king.
#define FRIENDLYPAWNBONUS 100
// (int) The penalty for each contested square around a king.
#define CONTESTEDSQUAREPENALTY -100
// (int) The penalty for each enemy-controlled square around a king.
#define THREATENEDSQUAREPENALTY -400

// (int) Set piece values in millipawns:
#define KNIGHTVALUE     3200
#define BISHOPVALUE     3330
#define ROOKVALUE       5100
#define QUEENVALUE      8800

// Note: Search function will exit when EITHER maxdepth or maxtime is exceeded.
// Max depth for each move if not changed in xboard mode
#define MAXDEPTH INFINITY

/* Max time for each move if not changed in xboard mode, top line is for debugging */
//static long int MAXTIME = 5000000l;
static long int MAXTIME = 5000l;

// Board control square bonuses:

  int squareProximityToCenter[8][8] = {
  {   1,  1,  1,  1,  1,  1,  1,  1   },
  {   1,  2,  2,  2,  2,  2,  2,  1   },
  {   1,  2,  3,  3,  3,  3,  2,  1   },
  {   1,  2,  3,  4,  4,  3,  2,  1   },
  {   1,  2,  3,  4,  4,  3,  2,  1   },
  {   1,  2,  3,  3,  3,  3,  2,  1   },
  {   1,  2,  2,  2,  2,  2,  2,  1   },
  {   1,  1,  1,  1,  1,  1,  1,  1   } };

// Positional piece bonuses:

  int bishopPlacement[8][8] = {
  {     -25,  -50,  -50,  -50,  -50,  -50,  -50, -25   },
  {	-50,   20,    0,    0,    0,    0,   20, -50   },
  {	-50,    0,   40,   30,   30,   40,    0, -50   },
  {	-50,    0,   30,   60,   60,   30,    0, -50   },
  {	-50,    0,   30,   60,   60,   30,    0, -50   },
  {     -50,    0,   40,   30,   30,   40,    0, -50   },
  {	-50,   20,    0,    0,    0,    0,   20, -50   },
  {	-25,  -50,  -50,  -50,  -50,  -50,  -50, -25   } };
  int knightPlacement[8][8] = {
  {    -100,  -60,  -20,   20,   20,  -20,  -60, -100  },
  {     -60,    0,   40,   80,   80,   40,    0,  -60  },
  {     -20,   40,   80,  120,  120,   80,   40,  -20  },
  {      20,   80,  120,  160,  160,  120,   80,   20  },
  {     -20,   40,   80,  120,  120,   80,   40,  -20  },
  {     -60,    0,   40,   80,   80,   40,    0,  -60  },
  {    -100,  -40,    0,   40,   40,    0,  -40, -100  },
  {    -140, -100,  -60,  -20,  -20,  -60, -100, -140  } };
  int pawnPlacement[8][8] = {
  {       0,    0,    0,    0,    0,    0,    0,    0  },
  {	300,  400,  500,  600,  600,  500,  400,  300  },
  {	 60,  120,  250,  400,  400,  250,  120,   60  },
  {	-30,   30,  170,  280,  280,  170,   30,  -30  },
  {    -100,  -50,  100,  200,  200,  100,  -50, -100  },
  {    -100,  -50,   50,  150,  150,   50,  -50, -100  },
  {    -100,  -50,   50, -100, -100,   50,  -50, -100  },
  {       0,    0,    0,    0,    0,    0,    0,    0  } };
  int pawnPlacementEndgame[8][8] = {
  {       0,    0,    0,    0,    0,    0,    0,    0  },
  {	800,  700,  600,  500,  500,  600,  700,  800  },
  {	450,  290,  160,   50,   50,  160,  290,  450  },
  {	330,  170,   70,    0,    0,   70,  170,  330  },
  {     250,  100,    0,  -50,  -50,    0,  100,  250  },
  {     200,   50,  -50,  -10,  -10,  -50,   50,  200  },
  {     200,   50,  -50,  -10,  -10,  -50,   50,  200  },
  {       0,    0,    0,    0,    0,    0,    0,    0  } };
  int kingPlacement[8][8] = {
  {    -300, -300, -300, -300, -300, -300, -300, -300  },
  {    -300, -300, -300, -300, -300, -300, -300, -300  },
  {    -300, -300, -300, -300, -300, -300, -300, -300  },
  {    -300, -300, -300, -500, -500, -300, -300, -300  },
  {    -300, -300, -300, -500, -500, -300, -300, -300  },
  {    -300, -300, -300, -300, -300, -300, -300, -300  },
  {    -150, -200, -200, -200, -200, -200, -200, -150  },
  {     100,  100,   50, -150, -150, -150,  100,  100  } };
  int kingPlacementEndgame[8][8] = {
  {       0,    0,    0,    0,    0,    0,    0,    0  },
  {       0,   50,   50,   50,   50,   50,   50,    0  },
  {       0,   50,  100,  100,  100,  100,   50,    0  },
  {       0,   50,  100,  150,  150,  100,   50,    0  },
  {       0,   50,  100,  150,  150,  100,   50,    0  },
  {       0,   50,  100,  100,  100,  100,   50,    0  },
  {       0,   50,   50,   50,   50,   50,   50,    0  },
  {       0,    0,    0,    0,    0,    0,    0,    0  } };
  int flipJ[8] = { 7, 6, 5, 4, 3, 2, 1, 0 };

// Sets the size of hash keys:
//typedef unsigned int U64; // 32 bit
typedef unsigned long long int U64; // 64-bit

/***** End of user-defineable values *****/

// a "constant" set at startup based on the other constants
static int MINMATINGVAL;

U64 zobrist[6][2][64];
U64 zobristColor;
U64 zobristCastle[4];

//typedef short int bool;
typedef int bool; // Using full int is faster execution?

typedef struct tagmove{
  int origin[2];
  int target[2];
  int fiftymovecount;
  bool castle[4];
  bool castleChanged[4];
  bool enPassantOccurred;
  char porigin;
  char ptarget;
  char promotion;
} move;

typedef int compactmove; //Used for hash storage and move ordering

typedef struct tagboardcontroldata{
  int threatlevel;
  int boardcontrol;
  int kingsafety;
  bool kingincheck;
} boardcontroldata;

typedef struct tagcoordinates{
  int origin[2];
  int target[2];
} coordinates;

typedef struct tagevaldata{
  int material;
  int totalmaterial;
  int positional;
  int numwpawns;
  int numbpawns;
  int numdarkbishops;
  int numlightbishops;
  int gamestate;
  coordinates kingPosition;
} evaldata;

struct movevectortype {
  int index;
  coordinates ray[7];
  struct movevectortype *next;
};

typedef struct movevectortype *MOVEVECTOR;

MOVEVECTOR mastervectorlist[7][64];
MOVEVECTOR capturevectorlist[7][64];

#define    hashfEXACT   0
#define    hashfALPHA   1
#define    hashfBETA    2
#define    HASHSIZE     0xFFFFF

typedef struct tagHASHE {
  U64 key;
  int depth;
  bool flags;
  bool singular;
  int value;
  int caller; //temp
  compactmove bestmovesig;
} HASHE;

HASHE transposition[HASHSIZE+1];

#define linesizeMAX 64

// PV line
typedef struct tagLINE{
  int cmove;              // Number of moves in the line.
  move argmove[linesizeMAX];  // The line.
} LINE;

LINE PVline;
compactmove PVlinecompact[linesizeMAX];

#define MOVELISTSIZE 5120

move movelist[MOVELISTSIZE];
int sortvallist[MOVELISTSIZE];

move *moveptr = movelist;
int *sortvalptr = sortvallist;

int GLOBAL_nodes;
bool GLOBAL_interrupt;

/***************************/
/* Platform Dependant Code */
/***************************/

//Functions associated with Time
int getTime(void);

//Functions associated with reading input
bool checkInput(void);

/** End Platform Dependant Code **/

//Function called by main program, initializes variables
void initialize(char board[][8], move *lastmove);
char loadPosition(char board[][8], move *lastmove, char FEN[]);

//Functions called by main program, print board or move
void printBoard(char board[][8]);
void printMove(move m);

//Function used by main program to read-in new move
move convertInput(char input[], move lastmove, bool usermove, char board[][8]);

//Function called by main program, reads user input
move getMove(char board[][8], move lastmove, char name[], char player);

//Function called by main program, finds best next move
move nextMove(char brd[][8], move lastmove, int maxlooklevel, char player, U64 repetitionstack[], char input_buffer[], bool pondering);

//Functions build game tree for use by function nextMove
move buildTree(char brd[][8], move lastmove, int maxlooklevel, char player, int *value, U64 repetitionstack[], char input_buffer[], bool pondering);
int determineMateVal(char board[][8], move lastmove, char player, int depth, int plevel);
int generate(move lastmove, move *start, int *valstart, char board[][8], char side, int *mate, compactmove hashmove, compactmove parentmove, int turn);
int generateCheckEvasions(move lastmove, move *start, int *valstart, char board[][8], char side, int *mate, compactmove hashmove, compactmove parentmove, coordinates kingPosition, int turn);
bool isMoveIntoCheck(move lastmove, char board[][8], move thismove, char side, coordinates kingPosition);
int tacticalgen(move lastmove, move *start, int *valstart, char board[][8], char side, int *mate);
move clearHistoryNodes(int *historystackindex, move historystack[], int count);

//Functions evaluate game tree, assisting function nextMove
void miniMax(move lastmove, move *movestart, int *valstart, char board[][8], bool turn, int plevel, int depth, int aval, int bval, char player, move *pbestmove, int *pvalue, time_t timelimit, U64 hashkey, U64 repetitionstack[], int extensionlevel, evaldata *scores, LINE * pline, char input_buffer[], bool pondering);
int evaluate(char brd[][8], char player, move lastmove, int turn, boardcontroldata *bcd, evaldata *stored);
void tacticaleval(move lastmove, move *movestart, int *valstart, char board[][8], bool turn, int aval, int bval, char player, int *pvalue, boardcontroldata *bcd, evaldata *scores);
int checkForExtensions(char side, int depth, int extensionlevel, char board[][8], move lastmove, boardcontroldata *bcd);
bool isNewBest(bool turn, int val, int *pvalue);
bool checkPruning(bool turn, int *pvalue, int *aval, int *bval, int *hashf);
compactmove makeCompactMove(move m);
compactmove makeCompactMoveTarget(move m);
move selectionSort(move *start, int *valstart, int moves);
int moveVal(move m, compactmove hashmove, compactmove parentmove, int turn);
int captureVal(move m);
int pieceValue(char piece);
int positionalValue(int i, int j, char piece, int gamestate);
evaldata buildEvalData(char brd[][8]);
int analyzeBoardControl(char board[][8], char side, int *control, int *kingsafety, bool *kingincheck);
bool isBattery(int i, int j, int atarget, int ntarget, char attacker, char target, bool isupper_attacker);
bool checkExchangeThreat(char attacker, char target, int attackerval);
int determineKingSafety(char board[][8], int attackerdefender[][8], char king, int alpha, int numeric);

//Function to test legality of a move, assists generate and is called by main program
bool isLegal(move m, char brd[][8], move lastmove);

//Helper Functions for isLegal
bool isLegalP(move m, char brd[][8], move lastmove);
bool isLegalp(move m, char brd[][8], move lastmove);
bool isLegalKNight(move m);
bool isLegalBishop(move m, char brd[][8]);
bool isLegalRook(move m, char brd[][8]);
bool isLegalQueen(move m, char brd[][8]);
bool isLegalK(move m, char brd[][8]);
bool isLegalk(move m, char brd[][8]);
coordinates findKings(char brd[][8]);
bool inCheckWrapper(char target, char brd[][8]);
bool inCheck(char target, char brd[][8], coordinates kingPosition);
bool whiteInCheck(char brd[][8]);
bool blackInCheck(char brd[][8]);
bool whiteIsPinned(int alpha, int numeric, char brd[][8]);
bool blackIsPinned(int alpha, int numeric, char brd[][8]);
bool isClearDiagonal(move m, char brd[][8]);
bool isClearFile(move m, char brd[][8]);
bool isClearRank(move m, char brd[][8]);

//Functions to find checkmate, stalemate, and draws
int isMate(char brd[][8], move lastmove);
void setMinMatingVal(void);
bool insufficientMaterial(char brd[][8]);
//RepetitionStack Operations
void addPosition(U64 stack[], U64 key, bool fromSearchTree);
bool isThirdRep(U64 stack[], U64 key);
int findPosition(U64 stack[], U64 key);
void clearStack(U64 stack[]);
U64 removePosition(U64 stack[], bool fromSearchTree);
bool stackReset(move m);

//Function to take a board position and a move and makes a new board position by applying the move
move setCastlingForMove(move newmove, char porigin, char ptarget, int oa, int ta, int tn);
move makeMove(int oa, int on, int ta, int tn, move lastmove, char board[][8]);
move makeMoveFromCompact(compactmove thismove, move lastmove, char board[][8]);
bool isEnPassantAvailable(char brd[][8], move m);
void executeMove(char position[][8], move newmove, evaldata *scores);
void undoMove(char board[][8], move m, evaldata *scores);

//Functions associated with hashing
U64 rand64(void);
bool isZobristUnique(U64 key);
U64 getUniqueZobrist(void);
void fillZobrist(void);
U64 getZobrist(char piece, int file, int rank);
U64 generateHashKey(char brd[][8], move m, char side);
U64 modifyHashKey(U64 key, move m);
char sideToPlay(bool turn, char player);
void recordHash(int caller, U64 key, int depth, int hashf, char player, int value, bool singular, move *best);
int probeHash(int depth, int alpha, int beta, U64 key, char player, bool *singular, compactmove *bestmove);

//Functions associated with move vectors
MOVEVECTOR allocMoveVector(void);
void addCoordinatesToRay(MOVEVECTOR vector, int origin[], int target[]);
MOVEVECTOR addVectorToRootVector(MOVEVECTOR newvector, MOVEVECTOR rootvector);
void buildMoveVectors(void);
MOVEVECTOR getMoveVector(char piece, int file, int rank);
MOVEVECTOR getMoveVectorCapture(char piece, int file, int rank);

//Function associated with move vectors and validity checking
bool targetInbounds(int target[]);
MOVEVECTOR buildSingleSquare(MOVEVECTOR rootvector, int origin[], int achange, int nchange);
MOVEVECTOR buildSingleRay(MOVEVECTOR rootvector, int origin[], int achange, int nchange);
MOVEVECTOR buildVectorp(int origin[]);
MOVEVECTOR buildVectorCapturep(int origin[]);
MOVEVECTOR buildVectorP(int origin[]);
MOVEVECTOR buildVectorCaptureP(int origin[]);
MOVEVECTOR buildVectorKNight(int origin[]);
MOVEVECTOR buildVectorBishop(int origin[]);
MOVEVECTOR buildVectorRook(int origin[]);
MOVEVECTOR buildVectorQueen(int origin[]);
MOVEVECTOR buildVectorKing(int origin[]);
MOVEVECTOR buildVectorCaptureKing(int origin[]);
bool isLegalVector(move m, char brd[][8], move lastmove, char player, bool checkinglogic);
bool isLegalPVector(move m, char brd[][8], move lastmove);
bool isLegalpVector(move m, char brd[][8], move lastmove);
bool isLegalKVector(move m, char brd[][8]);
bool isLegalkVector(move m, char brd[][8]);

//Function polls to see if search needs to be interrupted
bool pollForInterrupt(char input_buffer[], bool pondering);

/***************************/
/* Platform Dependant Code */
/***************************/
#if defined(LINUX)
#  undef WIN32
#  define UNIX
#endif

#if defined(WIN32)
#include <windows.h>
#include <io.h>
#endif

#if defined(UNIX)
#include <sys/time.h>
//#include <thread.h>
//#include <pthread.h>
#endif

int getTime(void) {
#if defined(WIN32)
  return GetTickCount();
#elif defined(UNIX)
  struct timeval timeval;
  gettimeofday(&timeval, NULL);
  return (timeval.tv_sec * 1000 + (timeval.tv_usec / 1000));
#else
  time_t seconds = time(NULL);
  int millisec = seconds * 1000;
  return millisec;
#endif
}

bool checkInput(void) {
#if defined(WIN32)
  //unsigned int dw = 0;
  DWORD dw = 0;
  bool inputReady = FALSE;
  static HANDLE inh;
  int r;
  inh = GetStdHandle(STD_INPUT_HANDLE);
  r = PeekNamedPipe(inh, NULL, 0, NULL, &dw, NULL);
//  printf("Bytes: %d \n", dw);
  if(dw != 0)
    inputReady = TRUE;
  return inputReady;
#elif defined(UNIX)
  fd_set rfds;
  struct timeval tv;
  int retval = FALSE;

  /* Watch stdin (fd 0) to see when it has input. */
  FD_ZERO(&rfds);
  FD_SET(0, &rfds);
  /* Wait zero seconds. */
  tv.tv_sec = 0;
  tv.tv_usec = 0;

  retval = select(1, &rfds, NULL, NULL, &tv);
  return retval;
#else
  return FALSE;
#endif
}
/*
#if defined(UNIX)
void *sub_b(void *);

void spawnThread(void) {
  if (thr_create(NULL, 0, sub_b, NULL, THR_SUSPENDED|THR_NEW_LWP, &thr_b))
    fprintf(stderr,"Can't create thr_b\n"), exit(1);
}
#endif
*/
/** End Platform Dependant Code **/

void initialize(char board[][8], move *lastmove)
{
  int i;
  board[0][7]=board[7][7]='r';
  board[1][7]=board[6][7]='n';
  board[2][7]=board[5][7]='b';
  board[3][7]='q';
  board[4][7]='k';
  for(i=0;i<8;i++)
    board[i][6]='p';
  for(i=0;i<8;i++)
    board[i][5]='-';
  for(i=0;i<8;i++)
    board[i][4]='-';
  for(i=0;i<8;i++)
    board[i][3]='-';
  for(i=0;i<8;i++)
    board[i][2]='-';
  for(i=0;i<8;i++)
    board[i][1]='P';
  board[0][0]=board[7][0]='R';
  board[1][0]=board[6][0]='N';
  board[2][0]=board[5][0]='B';
  board[3][0]='Q';
  board[4][0]='K';
  //lastmove's target implies that it is white's turn to move
  lastmove->target[0]=4;
  lastmove->target[1]=7;
  for(i=0;i<4;i++)
    lastmove->castle[i]=1;
  lastmove->fiftymovecount = 0;
  // several of lastmove's fields are set to null values
  lastmove->origin[0]=4;
  lastmove->origin[1]=7;
  for(i=0;i<4;i++)
    lastmove->castleChanged[i]=FALSE;
  lastmove->porigin = 'k';
  lastmove->ptarget = 'k';
  lastmove->promotion = NULLCHAR;
  lastmove->enPassantOccurred = FALSE;
}

char loadPosition(char board[][8], move *lastmove, char FEN[])
{
  int i, k, index=9; //index is 9 to ignore "SETBOARD "
  char side, token = '-';
  for(i=7; i>=0; i--) {
    int j = 0;
    token = FEN[index++];
    while(token != '/' && token != ' ')
    {
      if(isupper(token) || islower(token)) {
        board[j][i] = token;
        j++;
      }
      else // token should be a number of empty spaces
      {
        int empties = (int)token - 48;
        while(empties--) {
          board[j][i] = '-';
          j++;
        }
      }
      token = FEN[index++];
    }
  }
  token = FEN[index++];
  side = token;
  index++; // skip the white space we know is here!
  token = FEN[index++];
  for(k=0;k<4;k++)
    lastmove->castle[k]=FALSE;
  if(token == '-')
    index++; // skip the white space we know is here!
  else {
    do
    {
      switch (token) {
      case 'K': lastmove->castle[1]=TRUE; break;
      case 'Q': lastmove->castle[0]=TRUE; break;
      case 'k': lastmove->castle[3]=TRUE; break;
      case 'q': lastmove->castle[2]=TRUE; break;
      }
      token = FEN[index++];
    }
    while(token != ' ');
  }
  token = FEN[index++];
  if(token != '-')
  {
    int alpha = (int)token - 97;
    int enpassant, onum, tnum;
    token = FEN[index++];
    enpassant = token - 49; // -48 to adjust for int, -1 to adjust to 0-based
    if(enpassant == 2) {
      onum = 1;
      tnum = 3;
    }
    else {
      onum = 6;
      tnum = 4;
    }
    lastmove->origin[0]=alpha;
    lastmove->origin[1]=onum;
    lastmove->target[0]=alpha;
    lastmove->target[1]=tnum; //Enpassant is available
  }
  else {
    int m,n;
    bool keeplooking = TRUE;
    if(side == 'w')
    {
      for(m=0;m<7 && keeplooking;m++)
        for(n=0;n<7 && keeplooking;n++)
          if(islower(board[m][n]))
          {
            lastmove->target[0]=m;
            lastmove->target[1]=n;
            keeplooking = FALSE;
          }
    }
    else
    {
      for(m=0;m<7 && keeplooking;m++)
        for(n=0;n<7 && keeplooking;n++)
          if(isupper(board[m][n]))
          {
            lastmove->target[0]=m;
            lastmove->target[1]=n;
            keeplooking = FALSE;
          }
    }
  }
  index++; // skip the white space we know is here!
  token = FEN[index++];
  {
    int temp = (int)token - 48;
    if (temp < 0)
      temp = 0;
    lastmove->fiftymovecount = temp;
  }
  index++; // skip the white space we know is here!
  token = FEN[index++];
  // We have full-move number in token here, if we want to use it
  if(side == 'w')
    side = 'W';
  else
    side = 'B';
  return side;
}

void printBoard(char board[][8])
{
  int i, j;
  for(i=7;i>-1;i--){
    printf("\n%i ", i+1);
    for(j=0;j<8;j++)
    printf(" %c", board[j][i]);
  }
  printf("\n\n   A B C D E F G H\n");
}

void printMove(move m)
{
	int oa, on, ta, tn;
	char origin, target;
	oa = m.origin[0];
	on = m.origin[1] + 1;
	ta = m.target[0];
	tn = m.target[1] + 1;
	switch(oa) {
	case 7: origin = 'h'; break;
	case 6: origin = 'g'; break;
	case 5: origin = 'f'; break;
	case 4: origin = 'e'; break;
	case 3: origin = 'd'; break;
	case 2: origin = 'c'; break;
	case 1: origin = 'b'; break;
	case 0: origin = 'a'; break;
	default: origin = ' ';
	  printf("Error: cannot print invalid move");
	}
	switch(ta) {
	case 7: target = 'h'; break;
	case 6: target = 'g'; break;
	case 5: target = 'f'; break;
	case 4: target = 'e'; break;
	case 3: target = 'd'; break;
	case 2: target = 'c'; break;
	case 1: target = 'b'; break;
	case 0: target = 'a'; break;
	default: target = ' ';
	  printf("Error: cannot print invalid move");
	}
	printf("%c%d%c%d", origin, on, target, tn);
}

move getMove(char board[][8], move lastmove, char name[], char player)
{
  int originalpha, originnumeric, targetalpha, targetnumeric;
  char originchar, targetchar, nowhere;
  move newmove;
  printf("\n\nPlease enter your move, %s.\n", name);
  printf("Please enter origin square (ex. e2):");
  scanf("%c%i", &originchar, &originnumeric);scanf("%c", &nowhere);
  printf("Please enter target square (ex. e4):");
  scanf("%c%i", &targetchar, &targetnumeric);scanf("%c", &nowhere);
  originnumeric-=1;
  targetnumeric-=1;
  switch(originchar) {
  case'A':
  case'a': originalpha=0; break;
  case'B':
  case'b': originalpha=1; break;
  case'C':
  case'c': originalpha=2; break;
  case'D':
  case'd': originalpha=3; break;
  case'E':
  case'e': originalpha=4; break;
  case'F':
  case'f': originalpha=5; break;
  case'G':
  case'g': originalpha=6; break;
  case'H':
  case'h': originalpha=7; break;
  default: originalpha=99;
  }
  switch(targetchar) {
  case'A':
  case'a': targetalpha=0; break;
  case'B':
  case'b': targetalpha=1; break;
  case'C':
  case'c': targetalpha=2; break;
  case'D':
  case'd': targetalpha=3; break;
  case'E':
  case'e': targetalpha=4; break;
  case'F':
  case'f': targetalpha=5; break;
  case'G':
  case'g': targetalpha=6; break;
  case'H':
  case'h': targetalpha=7; break;
  default: targetalpha=99;
  }
  if
  (
    (
      (0 <= originalpha &&  originalpha <= 7) &&
      (0 <= originnumeric &&  originnumeric <= 7) &&
      (0 <= targetalpha && targetalpha <= 7) &&
      (0 <= targetnumeric && targetnumeric <= 7)
    ) &&
    (!(board[originalpha][originnumeric]=='-')) &&
    (
      ((player=='W') &&
        !(isupper(board[targetalpha][targetnumeric])) &&
        !(islower(board[originalpha][originnumeric]))
      ) ||
      ((player=='B') &&
        !(islower(board[targetalpha][targetnumeric])) &&
        !(isupper(board[originalpha][originnumeric]))
      )
    )
  ) //end if
  {
    newmove=makeMove(originalpha, originnumeric, targetalpha, targetnumeric, lastmove, board);
    if(isLegal(newmove, board, lastmove))
    {
      if(
         ( (board[originalpha][originnumeric] == 'p') &&
           (targetnumeric == 0)) ||
         ( (board[originalpha][originnumeric] == 'P') &&
           (targetnumeric == 7))
        ) //end if
        {
          char nowhere, promotion = 'q';
          bool done = FALSE;
          while(done == FALSE)
          {
            printf("\nTo promote your pawn, please enter Q, R, B, or N:");
            scanf("%c", &promotion);scanf("%c", &nowhere);
            switch(promotion){
            case 'Q':
            case 'q': promotion = 'q';
                      done = TRUE; break;
            case 'R':
            case 'r': promotion = 'r';
                      done = TRUE; break;
            case 'B':
            case 'b': promotion = 'b';
                      done = TRUE; break;
            case 'N':
            case 'n': promotion = 'n';
                      done = TRUE; break;
            default: printf("\nThat was not a valid entry");
            }
          }
          newmove.promotion = promotion;
        }
      return newmove;
    }
  }
  printf("\nI'm sorry, but that move is not valid");
  printBoard(board);
  if(inCheckWrapper('W', board))
    printf("\nCheck!");
  if(inCheckWrapper('B', board))
    printf("\nCheck!");
  return getMove(board, lastmove, name, player);

}

bool isEnPassantAvailable(char brd[][8], move m)
{
  int oalpha, onumeric, talpha, tnumeric;
  oalpha = m.origin[0];
  onumeric = m.origin[1];
  talpha = m.target[0];
  tnumeric = m.target[1];
  switch(brd[talpha][tnumeric]){
  case 'p':
    if(onumeric == 6 && tnumeric == 4)
      if(brd[oalpha-1][tnumeric] == 'P' ||
         brd[oalpha+1][tnumeric] == 'P' )
         return TRUE;
    break;
  case 'P':
    if(onumeric == 1 && tnumeric == 3)
      if(brd[oalpha-1][tnumeric] == 'p' ||
         brd[oalpha+1][tnumeric] == 'p' )
         return TRUE;
    break;
  }
  return FALSE;
}

void executeMove(char position[][8], move newmove, evaldata *scores)
{
  char porigin, ptarget, movingpiece;
  int oalpha, onumeric, talpha, tnumeric;
  bool enPassantOccurred, promotion = FALSE;
  enPassantOccurred = newmove.enPassantOccurred;
  oalpha = newmove.origin[0];
  onumeric = newmove.origin[1];
  talpha = newmove.target[0];
  tnumeric = newmove.target[1];
  porigin = position[oalpha][onumeric];
  ptarget = position[talpha][tnumeric];
  GLOBAL_nodes++; //Used to count nodes/second
  //Special treatment for promotions
  if(porigin=='P' && tnumeric==7)
  {
    switch(newmove.promotion){
    case 'q': movingpiece='Q'; break;
    case 'r': movingpiece='R'; break;
    case 'b': movingpiece='B'; break;
    case 'n': movingpiece='N'; break;
    default: movingpiece = 'Q';
    }
    promotion = TRUE;
  }
  else if(porigin=='p' && tnumeric==0)
  {
    switch(newmove.promotion){
    case 'q': movingpiece='q'; break;
    case 'r': movingpiece='r'; break;
    case 'b': movingpiece='b'; break;
    case 'n': movingpiece='n'; break;
    default: movingpiece = 'q';
    }
    promotion = TRUE;
  }
  else { movingpiece = porigin; }
  position[oalpha][onumeric]='-';
  position[talpha][tnumeric]=movingpiece;
  //Special conditions for castling moves
  if(porigin=='K')
    if(oalpha==4 && onumeric==0){
      if(talpha==2) {
        position[3][0]='R';
        position[0][0]='-';
      }
      else if(talpha==6) {
        position[5][0]='R';
        position[7][0]='-';
      }
    }
  if(porigin=='k')
    if(oalpha==4 && onumeric==7){
      if(talpha==2) {
        position[3][7]='r';
        position[0][7]='-';
      }
      else if(talpha==6) {
        position[5][7]='r';
        position[7][7]='-';
      }
    }
  //Special conditions for en passant
  if(enPassantOccurred)
  {
    if(porigin=='P')
      position[talpha][4]='-';
    else //if(porigin=='p') this should always be the case here.
      position[talpha][3]='-';
  }
  //The following section used to maintain evaldata
  if(scores != NULL)
  {
    int totalmaterial = scores->totalmaterial;
    int positional = scores->positional;
    int material = scores->material;
    int gamestate = scores->gamestate;
    positional -= positionalValue(oalpha, onumeric, porigin, gamestate);
    positional += positionalValue(talpha, tnumeric, porigin, gamestate);
    if(porigin == 'K')
    {
      scores->kingPosition.origin[0] = talpha;
      scores->kingPosition.origin[1] = tnumeric;
    }
    else if(porigin == 'k')
    {
      scores->kingPosition.target[0] = talpha;
      scores->kingPosition.target[1] = tnumeric;
    }
    if(enPassantOccurred)
    {
       if(porigin=='P')
       {
         scores->numbpawns--;
         positional -= positionalValue(talpha, 4, 'p', gamestate);
         material -= -1000; //value of 'p'
       }
       else  //porigin MUST be 'p' here
       {
         scores->numwpawns--;
         positional -= positionalValue(talpha, 3, 'P', gamestate);
         material -= 1000; //value of 'P'
       }
    }
    else if(ptarget != '-') // capture
    {
      int targetvalue = pieceValue(ptarget);
      positional -= positionalValue(talpha, tnumeric, ptarget, gamestate);
      switch(ptarget) {
        case 'P': scores->numwpawns--; break;
        case 'p': scores->numbpawns--; break;
        case 'b':
        case 'B': if( ((talpha+tnumeric)%2) == 1 ) //light square
                    scores->numlightbishops--;
                  else
                    scores->numdarkbishops--;
        default: break;
      }
      material -= targetvalue;
      if(targetvalue < -1000)
        totalmaterial += targetvalue;
      else if(targetvalue > 1000) // Pawns and kings not counted towards total
        totalmaterial -= targetvalue;
    }
    if(promotion)
    {
      int movingpieceval = pieceValue(movingpiece);
      material -= pieceValue(porigin);
      material += movingpieceval;
      if(movingpieceval < -1000) {
        scores->numbpawns--;
        totalmaterial -= movingpieceval;
      }
      else if(movingpieceval > 1000) { // Pawns and kings not counted towards total
        scores->numwpawns--;
        totalmaterial += movingpieceval;
      }
    }
    scores->positional = positional;
    scores->material = material;
    scores->totalmaterial = totalmaterial;
  }
}

void undoMove(char board[][8], move m, evaldata *scores)
{
  int oalpha, onumeric, talpha, tnumeric;
  char porigin, ptarget, movingpiece;
  bool enPassantOccurred = m.enPassantOccurred;
  oalpha = m.origin[0];
  onumeric = m.origin[1];
  talpha = m.target[0];
  tnumeric = m.target[1];
  porigin = m.porigin;
  ptarget = m.ptarget;
  movingpiece = board[talpha][tnumeric]; //only differs from porigin in promotions.
  //Reset the original move squares to previous values
  board[oalpha][onumeric]=porigin;
  board[talpha][tnumeric]=ptarget;

  if(enPassantOccurred) // Check for enpassant
  {
    if(porigin=='P') {
      ptarget='p';
      board[talpha][4]='p';
    }
    else if(porigin=='p') {
      ptarget='P';
      board[talpha][3]='P';
    }
    else
      printf("Error: enpassant incorrectly reported to undoMove()");
  }
  else  // Check for castling
  {
    if( (porigin=='K') &&
        (oalpha==4 && onumeric==0) )
    {
      if(talpha==2) {
        board[3][0]='-';
        board[0][0]='R';
      }
      else if(talpha==6) {
        board[5][0]='-';
        board[7][0]='R';
      }
    }
    if( (porigin=='k') &&
        (oalpha==4 && onumeric==7) )
    {
      if(talpha==2) {
        board[3][7]='-';
        board[0][7]='r';
      }
      if(talpha==6) {
        board[5][7]='-';
        board[7][7]='r';
      }
    }
  }
  //The following section used to maintain evaldata
  if(scores != NULL)
  {
    int totalmaterial = scores->totalmaterial;
    int positional = scores->positional;
    int material = scores->material;
    int gamestate = scores->gamestate;
    positional += positionalValue(oalpha, onumeric, porigin, gamestate);
    positional -= positionalValue(talpha, tnumeric, porigin, gamestate);
    if(porigin == 'K')
    {
      scores->kingPosition.origin[0] = oalpha;
      scores->kingPosition.origin[1] = onumeric;
    }
    else if(porigin == 'k')
    {
      scores->kingPosition.target[0] = oalpha;
      scores->kingPosition.target[1] = onumeric;
    }
    if(porigin != movingpiece) //promotion
    {
      int movingpieceval = pieceValue(movingpiece);
      material += pieceValue(porigin);
      material -= movingpieceval;
      if(movingpieceval < -1000) {
        scores->numbpawns++;
        totalmaterial += movingpieceval;
      }
      else if(movingpieceval > 1000) { // Pawns and kings not counted towards total
        scores->numwpawns++;
        totalmaterial -= movingpieceval;
      }
    }
    if(enPassantOccurred)
    {
       if(porigin=='P')
       {
         scores->numbpawns++;
         positional += positionalValue(talpha, 4, 'p', gamestate);
         material += -1000; //value of 'p'
       }
       else  //porigin MUST be 'p' here
       {
         scores->numwpawns++;
         positional += positionalValue(talpha, 3, 'P', gamestate);
         material += 1000; //value of 'P'
       }
    }
    else if(ptarget != '-') // capture
    {
      int targetvalue = pieceValue(ptarget);
      positional += positionalValue(talpha, tnumeric, ptarget, gamestate);
      switch(ptarget) {
        case 'P': scores->numwpawns++; break;
        case 'p': scores->numbpawns++; break;
        case 'b':
        case 'B': if( ((talpha+tnumeric)%2) == 1 ) //light square
                    scores->numlightbishops++;
                  else
                    scores->numdarkbishops++;
        default: break;
      }
      material += targetvalue;
      if(targetvalue < -1000)
        totalmaterial -= targetvalue;
      else if(targetvalue > 1000) // Pawns and kings not counted towards total
        totalmaterial += targetvalue;
    }
    scores->positional = positional;
    scores->material = material;
    scores->totalmaterial = totalmaterial;
  }
}

move nextMove(char brd[][8], move lastmove, int maxlooklevel, char player, U64 repetitionstack[], char input_buffer[], bool pondering)
{
  move bestmove;
  int value;
  //float valueprintable;
  bestmove = buildTree(brd, lastmove, maxlooklevel, player, &value, repetitionstack, input_buffer, pondering);
  //valueprintable = (float)value;
  //valueprintable /= 1000;
  //printf("\nComputer has a tactical score of %.2f compared to the player", valueprintable);
  return bestmove;
}

move buildTree(char brd[][8], move lastmove, int maxlooklevel, char player, int *value, U64 repetitionstack[], char input_buffer[], bool pondering)
{
  move bestmove;
  U64 hashkey;
  evaldata rootEvalData;
  hashkey = generateHashKey(brd, lastmove, sideToPlay(1, player));
  rootEvalData = buildEvalData(brd);
  rootEvalData.kingPosition = findKings(brd);
  {
    int alpha = -INFINITY;
    int beta = INFINITY;
    int looklevel = 1;
    time_t timestart, timer, timelimit;
    timestart = timer = getTime();
    if(pondering)
      timelimit = INFINITY - 1;
    else
      timelimit = timestart + MAXTIME;
    GLOBAL_nodes = 0;
    GLOBAL_interrupt = FALSE;
/*    {
      int i;
      bool checked;
      for(i=0;i<0xFFFF;i++)
        checked = inCheck('B', brd, kingPosition);
      timer = getTime();
      printf("telluser Newest took %i milliseconds.\n", (timer-timestart));
      timestart = timer;
      for(i=0;i<0xFFFF;i++)
        checked = inCheckWrapper('B', brd);
      timer = getTime();
      printf("telluser New took %i milliseconds.\n", (timer-timestart));
      timestart = timer;
      for(i=0;i<0xFFFF;i++)
        checked = blackInCheck(brd);
      timer = getTime();
      printf("telluser Old took %i milliseconds.\n", (timer-timestart));
    }
*/
    do
    {
      move *movestart = moveptr;
      int *valstart = sortvalptr;
      move newbest;
      LINE line;
      miniMax(lastmove, movestart, valstart, brd, 1, 0, looklevel, alpha, beta, player, &newbest, value, timelimit, hashkey, repetitionstack, 0, &rootEvalData, &line, input_buffer, pondering);
      timer = getTime();
      if(*value != UNKNOWN || looklevel == 1)
      {
        if( *value >= alpha )
          bestmove = newbest;
        else
          newbest = bestmove; //so we can print the old best
        printf("%i %i %i %i ", looklevel, *value/10 ,(timer-timestart)/10, GLOBAL_nodes);
        if((*value < alpha) || (*value > beta))
          printf("(r) "); //indicates re-search
        else
          printf("- "); //indicates completed depth
        printMove(newbest);
/*        {
          evaldata check = buildEvalData(brd);
          if( (check.material != rootEvalData.material) ||
            (check.totalmaterial != rootEvalData.totalmaterial) ||
            (check.positional != rootEvalData.positional) ||
            (check.numwpawns != rootEvalData.numwpawns) ||
            (check.numbpawns != rootEvalData.numbpawns) ||
            (check.numlightbishops != rootEvalData.numlightbishops) ||
            (check.numdarkbishops != rootEvalData.numdarkbishops) ||
            (check.kingPosition.origin[0] != rootEvalData.kingPosition.origin[0])
            ) printf("Error: eval data does not match.");
        }
*/
#if defined(SHOWFULLPV)
        { int k;
          for(k=1;k<line.cmove;k++)
          {
            printf(" ");
            printMove(line.argmove[k]);
          }
          //printf("PV length: %i\n", line.cmove);
        }
#endif
        printf("\n");
      }
      if((*value < alpha) || (*value > beta))
      {
        alpha = -INFINITY;
        beta = INFINITY;
      }
      else
      {
        int p;
        PVline = line; // equivalent to the next 2 lines.
        //memcpy(PVline.argmove, line.argmove, line.cmove * sizeof(move));
        //PVline.cmove = line.cmove;
        for(p=0;p<PVline.cmove;p++)
          PVlinecompact[p] = makeCompactMove(PVline.argmove[p]);

        alpha = *value - ASPIRATIONWINDOW;
        beta = *value + ASPIRATIONWINDOW;
        looklevel++;
      }
      if(GLOBAL_interrupt)
        break;
    } while(timer < timelimit && looklevel <= maxlooklevel);
    printf("%i %i %i \n", looklevel, (timer-timestart)/10, GLOBAL_nodes);
  }
  return bestmove;
}

// Used in miniMax to determine type of mate and thus value to return.
int determineMateVal(char board[][8], move lastmove, char player, int depth, int plevel)
{
  int mateval = 0;
  if(player=='W')
  {
    if(inCheckWrapper('W', board)) // White Checkmated
      mateval = -MATE + (1000 * plevel);
    else if(inCheckWrapper('B', board)) // Black Checkmated
      mateval = MATE - (1000 * plevel);
    else
      mateval = 0; // Stalemate
  }
  else
  {
    if(inCheckWrapper('B', board)) // Black Checkmated
      mateval = -MATE + (1000 * plevel);
    else if(inCheckWrapper('W', board)) // White Checkmated
      mateval = MATE - (1000 * plevel);
    else
      mateval = 0; // Stalemate
  }
  return mateval;
}

int generate(move lastmove, move *start, int *valstart, char board[][8], char side, int *mate, compactmove hashmove, compactmove parentmove, int turn)
{
  int i, j, moves = 0;
  move newmove;
  move *end = start;
  int *sortend = valstart;
  bool hashmovefound = FALSE;
  *mate=0;
  for(i=0;i<8;i++)
    for(j=0;j<8;j++)
    {
      char origin = board[i][j];
      if(origin != '-')
        if( (side == 'W' && isupper(origin)) ||
            (side == 'B' && islower(origin)) )
        {
          MOVEVECTOR myvector = getMoveVector(origin, i, j);
          while(myvector != NULL)
          {
            int x, max, atarget, ntarget;
            bool rayisclear = TRUE;
            max = myvector->index;
            for(x=0;x<max && rayisclear;x++)
            {
              char target;
              atarget = myvector->ray[x].target[0];
              ntarget = myvector->ray[x].target[1];
              target = board[atarget][ntarget];
              if( (side == 'W' && !isupper(target)) ||
                  (side == 'B' && !islower(target)) )
              {
                if(target != '-') //capture move
                  rayisclear = FALSE;
                newmove = makeMove(i, j, atarget, ntarget, lastmove, board);
                if(isLegalVector(newmove, board, lastmove, side, FALSE))
                {
                  int movesortval = 0;
                  if(target == 'k' || target == 'K')
                  {
                    *mate = 4;
                    return 0;
                  }
                  movesortval = moveVal(newmove, hashmove, parentmove, turn);
                  if(movesortval == INFINITY) //Don't re-search hashmove
                    hashmovefound = TRUE;
                  else {
                  *end++ = newmove;
                  *sortend++ = movesortval;
                  }
                }
              }
              else //We ran into one of our own pieces
                rayisclear = FALSE;
            }
            myvector = myvector->next;
          }
        }
    }
  moves = end - start;
  if( moves == 0 && hashmovefound == FALSE) //no moves possible
  {
    *mate=1;
    return 0;
  }
  return moves;
}

int generateCheckEvasions(move lastmove, move *start, int *valstart, char board[][8], char side, int *mate, compactmove hashmove, compactmove parentmove, coordinates kingPosition, int turn)
{
  int i, j, moves = 0;
  move newmove;
  move *end = start;
  int *sortend = valstart;
  bool hashmovefound = FALSE;
  *mate=0;
  for(i=0;i<8;i++)
    for(j=0;j<8;j++)
    {
      char origin = board[i][j];
      if(origin != '-')
        if( (side == 'W' && isupper(origin)) ||
            (side == 'B' && islower(origin)) )
        {
          MOVEVECTOR myvector = getMoveVector(origin, i, j);
          while(myvector != NULL)
          {
            int x, max, atarget, ntarget;
            bool rayisclear = TRUE;
            max = myvector->index;
            for(x=0;x<max && rayisclear;x++)
            {
              char target;
              atarget = myvector->ray[x].target[0];
              ntarget = myvector->ray[x].target[1];
              target = board[atarget][ntarget];
              if( (side == 'W' && !isupper(target)) ||
                  (side == 'B' && !islower(target)) )
              {
                if(target != '-') //capture move
                  rayisclear = FALSE;
                newmove = makeMove(i, j, atarget, ntarget, lastmove, board);
                if(isLegalVector(newmove, board, lastmove, side, FALSE))
                {
                  int movesortval = 0;
                  if(target == 'k' || target == 'K')
                  {
                    *mate = 4;
                    return 0;
                  }
                  // Extra legality testing for check evasions

/*    {
      int i;
      bool checked;
      time_t timestart, timer;
      timestart = timer = getTime();
      for(i=0;i<0xFFFF;i++)
        checked = isLegal(newmove, board, lastmove);
      timer = getTime();
      printf("telluser isLegal took %i milliseconds.\n", (timer-timestart));
      timestart = timer;
      for(i=0;i<0xFFFF;i++)
        checked = !isMoveIntoCheck(lastmove, board, newmove, side, kingPosition);
      timer = getTime();
      printf("telluser isMoveIntoCheck took %i milliseconds.\n", (timer-timestart));
//      timestart = timer;
//      for(i=0;i<0xFFFF;i++)
//        checked = inCheckWrapper(side, board);
//      timer = getTime();
//      printf("telluser inCheckWrapper took %i milliseconds.\n", (timer-timestart));
    }
*/    //exit(0);

                  if(!isMoveIntoCheck(lastmove, board, newmove, side, kingPosition))
                  {
                    movesortval = moveVal(newmove, hashmove, parentmove, turn);
                    if(movesortval == INFINITY) //Don't re-search hashmove
                      hashmovefound = TRUE;
                    else {
                    *end++ = newmove;
                    *sortend++ = movesortval;
                    }
                  }
                }
              }
              else //We ran into one of our own pieces
                rayisclear = FALSE;
            }
            myvector = myvector->next;
          }
        }
    }
  moves = end - start;
  if( moves == 0 && hashmovefound == FALSE) //no moves possible
  {
    *mate=1;
    return 0;
  }
  return moves;
}

bool isMoveIntoCheck(move lastmove, char board[][8], move thismove, char side, coordinates kingPosition)
{
  bool intocheck = FALSE;
  int oalpha = thismove.origin[0], onumeric = thismove.origin[1];
  int talpha = thismove.target[0], tnumeric = thismove.target[1];
  char movingPiece = board[oalpha][onumeric];
  if(movingPiece == 'K') {
    kingPosition.origin[0] = talpha;
    kingPosition.origin[1] = tnumeric;
  }
  else if(movingPiece == 'k') {
    kingPosition.target[0] = talpha;
    kingPosition.target[1] = tnumeric;
  }
  executeMove(board, thismove, NULL);
  if(inCheck(side, board, kingPosition))
    intocheck = TRUE;
  undoMove(board, thismove, NULL);
  return intocheck;
}

move clearHistoryNodes(int *historystackindex, move historystack[], int count)
{
  move m;
  int i;
  for(i=0;i<count;i++)
  {
    *historystackindex -= 1;
    m = historystack[*historystackindex];
  }
  return m;
}

/* this function returns the number of ply that the branch should be extended */
// Current return possibilities are 0, 1, and ILLEGAL
int checkForExtensions(char side, int depth, int extensionlevel, char board[][8], move lastmove, boardcontroldata *bcd)
{
//  int maxextension = depth / MAXEXTENSIONFRACTION;
//  if(extensionlevel >= maxextension)
//    return 0;
  {
    int boardcontrol = 0, kingsafety = 0;
    bool kingincheck = FALSE;
    int threats = analyzeBoardControl(board, side, &boardcontrol, &kingsafety, &kingincheck);
    if(threats == ILLEGAL)
      return ILLEGAL;
    bcd->threatlevel = threats;
    bcd->boardcontrol = boardcontrol;
    bcd->kingsafety = kingsafety;
    bcd->kingincheck = kingincheck;
    if( side == 'W' && threats < -1)
      return 1; // White is possibly forked, force him to move.
    else if( side == 'B' && threats > 1)
      return 1; // Black is possibly forked, force him to move.
    if(kingincheck)
      return 1;
//    if(kingsafety > 1000 || kingsafety < -1000)
//      return 1;
  }
  return 0;
}

/* this function returns true if the val beats the previous best val */
bool isNewBest(bool turn, int val, int *pvalue)
{
  if(val == ILLEGAL || val == UNKNOWN) //move that created val was illegal or time ran out
    return FALSE;
  if(*pvalue == UNKNOWN) //best is initialized to UNKNOWN
  {
    *pvalue = val;
    return TRUE;
  }
  if(turn == 1) {
    if(val > *pvalue)
    {
      *pvalue = val;
      return TRUE;
    }
  }
  else if(turn == -1)
    if(val < *pvalue)
    {
      *pvalue = val;
      return TRUE;
    }
  return FALSE;
}

/* this function returns true if the node should be pruned from tree */
bool checkPruning(bool turn, int *pvalue, int *aval, int *bval, int *hashf)
{
  if(turn == 1)
  {
    if(*pvalue > *bval)
    {
      if(hashf != NULL)
        *hashf = hashfBETA;
      return TRUE;
    }
    else if(*pvalue > *aval)
    {
      *aval = *pvalue;
      if(hashf != NULL)
        *hashf = hashfEXACT;
    }
  }
  if(turn == -1)
  {
    if(*pvalue < *aval)
    {
      if(hashf != NULL)
        *hashf = hashfALPHA;
      return TRUE;
    }
    else if(*pvalue < *bval)
    {
      *bval = *pvalue;
      if(hashf != NULL)
        *hashf = hashfEXACT;
    }
  }
  return FALSE;
}

void miniMax(move lastmove, move *movestart, int *valstart, char board[][8], bool turn, int plevel, int depth, int aval, int bval, char player, move *pbestmove, int *pvalue, time_t timelimit, U64 hashkey, U64 repetitionstack[], int extensionlevel, evaldata *scores, LINE * pline, char input_buffer[], bool pondering)
{
  bool extended = FALSE;
/*
        bool b1, b2, b3, b4;
        if(
          (whiteInCheck(board) && !inCheck('W', board, scores->kingPosition)) ||
          (!whiteInCheck(board) && inCheck('W', board, scores->kingPosition)) ||
          (blackInCheck(board) && !inCheck('B', board, scores->kingPosition)) ||
          (!blackInCheck(board) && inCheck('B', board, scores->kingPosition))
          )
          printf("tellusererror Check mismatch\n");
          b1 = whiteInCheck(board);
          b2 = inCheckWrapper('W', board);
          b3 = blackInCheck(board);
          b4 = inCheckWrapper('B', board);
*/
  if(plevel != 0)
    executeMove(board, lastmove, scores);
  // Cull moves into check (when side NOT to play is in check)
//  if( ILLEGAL == evaluate(board, player, lastmove, turn, NULL, NULL) )
//    if(!inCheck(sideToPlay(-turn, player), board, scores->kingPosition))
//      printf("tellusererror Disagreement type 2\n");
  if(inCheck(sideToPlay(-turn, player), board, scores->kingPosition))
  {
//     if( ILLEGAL != evaluate(board, player, lastmove, turn, NULL, NULL) )
//       printf("tellusererror Disagreement\n");
     *pvalue = ILLEGAL;
     undoMove(board, lastmove, scores);
     return;
  }
  /*** Leaf***/
  if(plevel == depth)
  {
    boardcontroldata bcd;
    bcd.threatlevel = UNKNOWN;
//    executeMove(board, lastmove, scores);
    if(SEARCH_EXTENSIONS && extensionlevel)
    {
      int extensions = 0;
//      extensions = checkForExtensions(sideToPlay(turn, player), depth, extensionlevel, board, lastmove, &bcd);
//      if(extensions == ILLEGAL) {
//        *pvalue = ILLEGAL;
//        undoMove(board, lastmove, scores);
//        return;
//      }
  extensions = inCheck(sideToPlay(turn, player), board, scores->kingPosition);
      if(extensions) {
        depth++;
        extensionlevel--;
        extended = TRUE;
//      undoMove(board, lastmove, scores);
      }
    }
    if(plevel == depth) //Still a leaf (no extensions)
    {
      int val = 0;
      int scoremultiplier = 110; // For lessening advantages when draw is approaching
      // check the fifty move rule
      {
        int currentmovecount = lastmove.fiftymovecount;
        if(currentmovecount >= 100) // Draw by 50 move rule!!
        {
          if(bcd.threatlevel == UNKNOWN) //the king might be en prise!
            if(inCheck(sideToPlay(-turn, player), board, scores->kingPosition))
            {
              *pvalue = ILLEGAL;
              undoMove(board, lastmove, scores);
              return;
            }
          *pvalue = 0;
          undoMove(board, lastmove, scores);
          return;
        }
        scoremultiplier -= currentmovecount;
      }
      hashkey = modifyHashKey(hashkey, lastmove);
      // check for draw by repetition
      addPosition(repetitionstack, hashkey, TRUE);
      //repval = findPosition(repetitionstack, hashkey);
      //if( 3 <= repval ) //thrice repetition
      if(isThirdRep(repetitionstack, hashkey))
      {
        if(inCheck(sideToPlay(-turn, player), board, scores->kingPosition))
          *pvalue = ILLEGAL;
        else
          *pvalue = 0;
        removePosition(repetitionstack, TRUE);
        undoMove(board, lastmove, scores);
        return;
      }
      // check the transposition table
      val = probeHash(0, aval, bval, hashkey, player, NULL, NULL);
      if(val != UNKNOWN)
      {
        *pvalue = val;
        //printf("\nfound a hash hit\n"); //debug
        removePosition(repetitionstack, TRUE);
        undoMove(board, lastmove, scores);
        return;
      }
      /* ******* */
      tacticaleval(lastmove, movestart, valstart, board, turn, aval, bval, player, pvalue, &bcd, scores);
      /* ******* */
      if(*pvalue == ILLEGAL) { //This move was illegal, return it
        removePosition(repetitionstack, TRUE);
        return;
      }
      //Legit values
      if(scoremultiplier < 100)
        *pvalue = (float)*pvalue * ( (float)scoremultiplier/100.0f );
      removePosition(repetitionstack, TRUE);
      return;
    }
  }
  /*** Root of tree ***/
  if(plevel==0){
    move currentmove;
    int val = UNKNOWN, mate, moves, i;
    int hashf = hashfALPHA;
    compactmove hashmove = UNKNOWN, parentmove = UNKNOWN;
    move *moveend = NULL;
    int *valend = NULL;
    bool singular = FALSE;
    LINE line;
    time_t timer = 0;
    U64 repstack2[101];
    line.cmove = 0;
    clearStack(repstack2);
    if(depth > 1) // prevents early termination on initial 1-ply search
      timer = getTime();
    *pvalue = UNKNOWN; //No best value yet, so mark unknown.
    extensionlevel = depth * 2; //Allow at most d*2 extensions
    // check the transposition table
    val = probeHash(depth-plevel, aval, bval, hashkey, player, NULL, &hashmove);
    //if(val != UNKNOWN)
      //  then this entire search has already been performed!
    if(hashmove != UNKNOWN)
    {
      currentmove = makeMoveFromCompact(hashmove, lastmove, board);
      if(isLegal(currentmove, board, lastmove)) {
        if( stackReset(currentmove))
          miniMax(currentmove, movestart, valstart, board, -turn, plevel+1, depth, aval, bval, player, NULL, &val, timelimit, hashkey, repstack2, extensionlevel, scores, &line, input_buffer, pondering);
        else
          miniMax(currentmove, movestart, valstart, board, -turn, plevel+1, depth, aval, bval, player, NULL, &val, timelimit, hashkey, repetitionstack, extensionlevel, scores, &line, input_buffer, pondering);
      }
      else
        printf("tellusererror Illegal Move found in Hash!  Ply: %i\n", plevel+1);
      if(isNewBest(turn, val, pvalue))
      {
        *pbestmove = currentmove;
        pline->argmove[0] = *pbestmove;
        memcpy(pline->argmove + 1, line.argmove, line.cmove * sizeof(move));
        pline->cmove = line.cmove + 1;
        line.cmove = 0; //Clear line
        if(checkPruning(turn, pvalue, &aval, &bval, &hashf))
          return;
      }
      if(singular)
      {
        //return, as there are no more moves to search
        *pbestmove = currentmove;
        *pvalue = val;
        return;
      }
      if(depth > 1) {
        if(pollForInterrupt(input_buffer, pondering)) {
          GLOBAL_interrupt = TRUE;
        }
        if(GLOBAL_interrupt)
          timer = timelimit+1; //move now
        else
          timer = getTime();
      }
    }
    parentmove = makeCompactMoveTarget(lastmove);
    // generate new moves
    moves = generate(lastmove, movestart, valstart, board, sideToPlay(turn, player), &mate, hashmove, parentmove, turn);
    moveend = movestart + moves;
    valend = valstart + moves;
    if(moves == 0 && mate != 0){
      printf("\n Error (Move Generation Failed): check board position\n");
      printf("tellusererror Illegal position\n");
      exit(EXIT_FAILURE);
    }
    // sort move list
    currentmove = selectionSort(movestart, valstart, moves);
    // Start searching children
    for(i=0; i<moves && (timer <= timelimit); i++ ) {
      if( stackReset(currentmove))
        miniMax(currentmove, moveend, valend, board, -turn, plevel+1, depth, aval, bval, player, NULL, &val, timelimit, hashkey, repstack2, extensionlevel, scores, &line, input_buffer, pondering);
      else
        miniMax(currentmove, moveend, valend, board, -turn, plevel+1, depth, aval, bval, player, NULL, &val, timelimit, hashkey, repetitionstack, extensionlevel, scores, &line, input_buffer, pondering);
      if(val != UNKNOWN && val != ILLEGAL)
      {
        if(val == *pvalue)
          if(rand()%2)  // Randomly pick one of the two equivalent moves
          {
            *pbestmove = currentmove;
            pline->argmove[0] = *pbestmove;
            memcpy(pline->argmove + 1, line.argmove, line.cmove * sizeof(move));
            pline->cmove = line.cmove + 1;
          }
        if(val > *pvalue || *pvalue == UNKNOWN)
        {
          *pvalue = val;
          *pbestmove = currentmove;
          pline->argmove[0] = *pbestmove;
          memcpy(pline->argmove + 1, line.argmove, line.cmove * sizeof(move));
          pline->cmove = line.cmove + 1;
          line.cmove = 0; //Clear line
          if(checkPruning(turn, pvalue, &aval, &bval, &hashf))
            return;
        }
      }
      if(depth > 1) {
        if(pollForInterrupt(input_buffer, pondering)) {
          GLOBAL_interrupt = TRUE;
        }
        if(GLOBAL_interrupt)
          timer = timelimit+1; //move now
        else
          timer = getTime();
      }
      currentmove = selectionSort(movestart, valstart, moves);
    }
    if( timer > timelimit )
      *pvalue = UNKNOWN; // return null
    else if(hashf != hashfALPHA) //Failing low at root causes a re-search at same depth (can only occur using aspiration windows) This data is inaccurate and dangerous to use.
      recordHash(1, hashkey, depth, hashf, player, *pvalue, FALSE, pbestmove);
    return;
  }
  /*** Branches of tree ***/
  else {
    move currentmove;
    int val, mate, moves, i;
    int hashf;
    bool usehash = TRUE;
    compactmove hashmove = UNKNOWN, parentmove = UNKNOWN;
    move *moveend = NULL;
    int *valend = NULL;
    int legalmoves = 0;
    move bestmove = {0};
    LINE line;
    time_t timer = getTime();
    U64 repstack2[101];
    bool incheck = FALSE, hashmoveplayed = FALSE, singular = FALSE;
    line.cmove = 0;
    clearStack(repstack2);
    // Execute move
//    executeMove(board, lastmove, scores);
    // check the fifty move rule
    if(lastmove.fiftymovecount >= 100) // Draw by 50 move rule!!
    {
      // Don't we need to check that the king is not en prise???
      // Since we are detecting moves into check during the search now...
      // Comment added Oct 17, 2003
      if(inCheck(sideToPlay(-turn, player), board, scores->kingPosition))
        {
          *pvalue = ILLEGAL; // Illegal move into check detected.
          undoMove(board, lastmove, scores);
          recordHash(2, hashkey, depth-plevel, hashf, player, *pvalue, FALSE, NULL);
          return;
        }
      *pvalue = 0;
      undoMove(board, lastmove, scores);
      return;
    }
    // Calculate hashkey
    hashkey = modifyHashKey(hashkey, lastmove);
    // check for draw by repetition
    {
      //int repval;
      addPosition(repetitionstack, hashkey, TRUE);
      //repval = findPosition(repetitionstack, hashkey);
      //if( 3 <= repval ) //thrice repetition
      if(isThirdRep(repetitionstack, hashkey))
      {
        *pvalue = 0;
        removePosition(repetitionstack, TRUE);
        undoMove(board, lastmove, scores);
        return;
      }
    }
    if(turn==1)
      hashf = hashfALPHA;
    else
      hashf = hashfBETA;
    *pvalue = UNKNOWN; //No best value yet, so mark unknown.
    /***********************************/
    /** Extend search if king in check */
    if(!extended && extensionlevel && SEARCH_EXTENSIONS)
    {
      incheck = inCheck(sideToPlay(turn, player), board, scores->kingPosition);
      if(incheck) {
        depth++;
        extensionlevel--;
      }
    }
    /***********************************/
    // check the transposition table
    val = probeHash(depth-plevel, aval, bval, hashkey, player, &singular, &hashmove);
    //not using table value on depth 1, done to detect repetition
    if(plevel == 1)
      if(repetitionstack[0] > MIN_ENTRIES_TO_THREATEN_3REPS)
        usehash = FALSE;
    if(val == ILLEGAL || (val != UNKNOWN && usehash))
    {
      *pvalue = val;
      //printf("\nfound a hash hit\n"); //debug
      removePosition(repetitionstack, TRUE);
      undoMove(board, lastmove, scores);
      return;
    }
    val = UNKNOWN;
    // Try playing the hash move before regular movegen.
    if(hashmove != UNKNOWN)
    {
      if(singular && extensionlevel && SEARCH_EXTENSIONS)
      {
        depth++; //extend this move if it is a singular reponse (info from hash)
        extensionlevel--;
      }
      currentmove = makeMoveFromCompact(hashmove, lastmove, board);
      if(isLegal(currentmove, board, lastmove)) {
        if( stackReset(currentmove))
          miniMax(currentmove, movestart, valstart, board, -turn, plevel+1, depth, aval, bval, player, NULL, &val, timelimit, hashkey, repstack2, extensionlevel, scores, &line, input_buffer, pondering);
        else
          miniMax(currentmove, movestart, valstart, board, -turn, plevel+1, depth, aval, bval, player, NULL, &val, timelimit, hashkey, repetitionstack, extensionlevel, scores, &line, input_buffer, pondering);
        legalmoves = 1;
        hashmoveplayed = TRUE;
      }
      else
        //printf("tellusererror Illegal Move found in Hash!  Ply: %i\n", plevel+1);
        printf("Illegal Move found in Hash!  Ply: %i\n", plevel+1);
//      if(val == ILLEGAL)
//        singular = 0;
      if(isNewBest(turn, val, pvalue))
      {
        bestmove = currentmove;
        if(checkPruning(turn, pvalue, &aval, &bval, &hashf))
        {
          recordHash(3, hashkey, depth-plevel, hashf, player, *pvalue, singular, &bestmove);
          removePosition(repetitionstack, TRUE);
          undoMove(board, lastmove, scores);
          return;
        }
        pline->argmove[0] = bestmove;
        memcpy(pline->argmove + 1, line.argmove, line.cmove * sizeof(move));
        pline->cmove = line.cmove + 1;
        line.cmove = 0; //Clear line
      }
      if(singular)
      {
        if(val != UNKNOWN)
          recordHash(8, hashkey, depth-plevel, hashf, player, *pvalue, singular, &bestmove);
        //return, as there are no more moves to search at this ply
        removePosition(repetitionstack, TRUE);
        undoMove(board, lastmove, scores);
        return;
      }
      if(pollForInterrupt(input_buffer, pondering)) {
        GLOBAL_interrupt = TRUE;
      }
      if(GLOBAL_interrupt)
        timer = timelimit+1; //move now
      else
        timer = getTime();
    }
    parentmove = makeCompactMove(lastmove);
    // generate new moves
    if(incheck)
      moves = generateCheckEvasions(lastmove, movestart, valstart, board, sideToPlay(turn, player), &mate, hashmove, parentmove, scores->kingPosition, turn);
    else
      moves = generate(lastmove, movestart, valstart, board, sideToPlay(turn, player), &mate, hashmove, parentmove, turn);
    moveend = movestart + moves;
    valend = valstart + moves;
    if(mate == 1) // mate
    {
      *pvalue = determineMateVal(board, lastmove, player, depth, plevel);
      removePosition(repetitionstack, TRUE);
      undoMove(board, lastmove, scores);
      return;
    }
    if(mate == 4) //Illegal Position, lastmove was move into check
    {
      *pvalue = ILLEGAL;
      removePosition(repetitionstack, TRUE);
      undoMove(board, lastmove, scores);
      recordHash(4, hashkey, depth-plevel, hashf, player, *pvalue, FALSE, NULL);
      return;
    }
    if( hashmoveplayed && moves == 0) //No more moves, return
    {
      if(val != UNKNOWN) //this line required to prevent illegal moves from being stored
        recordHash(9, hashkey, depth-plevel, hashf, player, *pvalue, TRUE, &bestmove);
      removePosition(repetitionstack, TRUE);
      undoMove(board, lastmove, scores);
      return;
    }
    if( !hashmoveplayed && moves == 1 ) //Singular Response
    {
      singular = TRUE;
      // We extend singular response regardless of other extensions performed
      // This stacks with check extensions to find forced mates quickly.
      if(extensionlevel)
      {
        depth++;
        extensionlevel--;
      }
    }
    // sort move list
    currentmove = selectionSort(movestart, valstart, moves);
    // Start searching children
    for(i=0; i<moves && (timer <= timelimit); i++ ) {
/*
      bool dofullsearch = TRUE;
      if(hashf == hashfEXACT) //Perform PV Search
      {
        dofullsearch = FALSE;
        if(turn == 1)
        {
          if( stackReset(p->lastMove))
            miniMax(p->lastMove, moveend, valend, board, -turn, plevel+1, depth, aval, aval+1, player, NULL, &val, timelimit, hashkey, repstack2, extensionlevel, scores, &line);
          else
            miniMax(p->lastMove, moveend, valend, board, -turn, plevel+1, depth, aval, aval+1, player, NULL, &val, timelimit, hashkey, repetitionstack, extensionlevel, scores, &line);
          if(val > aval && val != ILLEGAL && val != UNKNOWN) //Check for failure - if move illegal or time ran out, we don't want to do full search!
            dofullsearch = TRUE;
        }
        else
        {
          if( stackReset(p->lastMove))
            miniMax(p->lastMove, moveend, valend, board, -turn, plevel+1, depth, bval-1, bval, player, NULL, &val, timelimit, hashkey, repstack2, extensionlevel, scores, &line);
          else
            miniMax(p->lastMove, moveend, valend, board, -turn, plevel+1, depth, bval-1, bval, player, NULL, &val, timelimit, hashkey, repetitionstack, extensionlevel, scores, &line);
          if(val < bval && val != ILLEGAL && val != UNKNOWN) //Check for failure - if move illegal or time ran out, we don't want to do full search!
            dofullsearch = TRUE;
        }
      }
      if(dofullsearch)
*/
      {
        if( stackReset(currentmove))
          miniMax(currentmove, moveend, valend, board, -turn, plevel+1, depth, aval, bval, player, NULL, &val, timelimit, hashkey, repstack2, extensionlevel, scores, &line, input_buffer, pondering);
        else
          miniMax(currentmove, moveend, valend, board, -turn, plevel+1, depth, aval, bval, player, NULL, &val, timelimit, hashkey, repetitionstack, extensionlevel, scores, &line, input_buffer, pondering);
      }
      if(val != ILLEGAL)
        legalmoves++;
      if(isNewBest(turn, val, pvalue))
      {
        bestmove = currentmove;
        if(checkPruning(turn, pvalue, &aval, &bval, &hashf))
        {
          // If we were not in check, can't be sure that this move wasn't singular response
          // This might mean singular reponses aren't ALWAYS extended, but it is safe.
          recordHash(5, hashkey, depth-plevel, hashf, player, *pvalue, singular, &bestmove);
          removePosition(repetitionstack, TRUE);
          undoMove(board, lastmove, scores);
          return;
        }
        pline->argmove[0] = bestmove;
        memcpy(pline->argmove + 1, line.argmove, line.cmove * sizeof(move));
        pline->cmove = line.cmove + 1;
        line.cmove = 0; //Clear line
      }
      currentmove = selectionSort(movestart, valstart, moves);
      if(pollForInterrupt(input_buffer, pondering)) {
        GLOBAL_interrupt = TRUE;
      }
      if(GLOBAL_interrupt)
        timer = timelimit+1; //move now
      else
        timer = getTime();
    } // End searching children
    if( timer > timelimit )
    {
      // return null
      *pvalue = UNKNOWN;
    }
    else if(*pvalue == UNKNOWN) // Check for mate (in case all moves generated were into check)
    {
      if(legalmoves > 0)
        printf("tellusererror Check minimax mate detection\n");
      *pvalue = determineMateVal(board, lastmove, player, depth, plevel);
      recordHash(6, hashkey, depth-plevel, hashf, player, *pvalue, FALSE, NULL);
    }
    else
    {
      //U64 key = generateHashKey(board, lastmove, sideToPlay(turn, player));
      //if(key != hashkey)
      //  printf("ZOBRIST ERROR!!\n");
      if(legalmoves == 1)
        singular = TRUE;
      recordHash(7, hashkey, depth-plevel, hashf, player, *pvalue, singular, &bestmove);
    }
    removePosition(repetitionstack, TRUE);
    undoMove(board, lastmove, scores);
  }
}


void tacticaleval(move lastmove, move *movestart, int *valstart, char board[][8], bool turn, int aval, int bval, char player, int *pvalue, boardcontroldata *bcd, evaldata *scores)
{
  move currentmove;
  move *moveend = NULL;
  int *valend = NULL;
  int val, mate = 0, moves = 0, i;
/*
  evaldata check = buildEvalData(board);
  if( (check.material != scores->material) ||
      (check.totalmaterial != scores->totalmaterial) ||
      //(check.positional != scores->positional) ||
      (check.numwpawns != scores->numwpawns) ||
      (check.numbpawns != scores->numbpawns) ||
      (check.numlightbishops != scores->numlightbishops) ||
      (check.numdarkbishops != scores->numdarkbishops)
    ) printf("Error: eval data does not match.");
*/
  // Check current position
  if(bcd == NULL) {
    executeMove(board, lastmove, scores);
    *pvalue = evaluate(board, player, lastmove, turn, NULL, scores);
  }
  else {
    if(bcd->threatlevel == UNKNOWN)
      *pvalue = evaluate(board, player, lastmove, turn, NULL, scores);
    else
      *pvalue = evaluate(board, player, lastmove, turn, bcd, scores);
  }
  if ( *pvalue == ILLEGAL || checkPruning(turn, pvalue, &aval, &bval, NULL) ) {
    undoMove(board, lastmove, scores);
    return;
  }
  // Generate list of possible captures
  moves = tacticalgen(lastmove, movestart, valstart, board, sideToPlay(turn, player), &mate);
  moveend = movestart + moves;
  valend = valstart + moves;
  if(mate == 4) { //Illegal Position: King can be captured.
    *pvalue = ILLEGAL;
    //printf("Illegal position slipped past evaluate!\n");
    undoMove(board, lastmove, scores);
    return;
  }
  for(i=0; i<moves; i++)
  {
    currentmove = selectionSort(movestart, valstart, moves);
    tacticaleval(currentmove, moveend, valend, board, -turn, aval, bval, player, &val, NULL, scores);
    if(val != ILLEGAL) // Skip values returned from illegal moves! (moves into check)
      if(isNewBest(turn, val, pvalue))
        if ( checkPruning(turn, pvalue, &aval, &bval, NULL) )
        {
          undoMove(board, lastmove, scores);
          return;
        }
  }
  undoMove(board, lastmove, scores);
}

int tacticalgen(move lastmove, move *start, int *valstart, char board[][8], char side, int *mate)
{
  int i, j, moves = 0;
  move newmove;
  move *end = start;
  int *sortend = valstart;
  for(i=0;i<8;i++)
    for(j=0;j<8;j++)
    {
      char origin = board[i][j];
      if(origin != '-')
        if( (side == 'W' && isupper(origin)) ||
            (side == 'B' && islower(origin)) )
        {
          MOVEVECTOR myvector = getMoveVector(origin, i, j);
          while(myvector != NULL)
          {
            int x, max, atarget, ntarget;
            bool rayisclear = TRUE;
            max = myvector->index;
            for(x=0;x<max && rayisclear;x++)
            {
              char target;
              atarget = myvector->ray[x].target[0];
              ntarget = myvector->ray[x].target[1];
              target = board[atarget][ntarget];
              if( ( (side == 'W') &&
                    (  (islower(target)) ||
                       (origin == 'P' && (ntarget == 7 || ntarget==6)) )
                  ) ||
                  ( (side == 'B') &&
                    (  (isupper(target)) ||
                       (origin == 'p' && (ntarget == 0 || ntarget==1)) )
                  )
                )
              {
                newmove = makeMove(i, j, atarget, ntarget, lastmove, board);
                if(isLegalVector(newmove, board, lastmove, side, FALSE))
                {
                  int movesortval = captureVal(newmove);
                  if(target == 'k' || target == 'K')
                  {
                    *mate = 4;
                    return 0;
                  }
                  *end++ = newmove;
                  *sortend++ = movesortval;
                }
              }
              if(target != '-') //capture move
                rayisclear = FALSE;
            }
            myvector = myvector->next;
          }
        }
    }
  moves = end - start;
  return moves;
}

compactmove makeCompactMove(move m)
{
  compactmove result = 0;
  int temp = 0;
  temp += m.origin[0];
  temp <<= 8;
  temp += m.origin[1];
  temp <<= 8;
  temp += m.target[0];
  temp <<= 8;
  temp += m.target[1];
  result = temp;
  return result;
}

compactmove makeCompactMoveTarget(move m)
{
  compactmove result = 0;
  int temp = 0;
  temp += m.target[0];
  temp <<= 8;
  temp += m.target[1];
  result = temp;
  return result;
}

move selectionSort(move *start, int *valstart, int moves)
{
  move best;
  int bestval = -1;
  int i, offset = 0;
  for(i=0; i<moves; i++)
  {
    int val = *(valstart + i);
    if(val != UNKNOWN && val > bestval) {
      bestval = val;
      best = *(start + i);
      offset = i;
    }
  }
  *(valstart + offset) = UNKNOWN; //flag this move as already picked.

  return best;
}

int moveVal(move m, compactmove hashmove, compactmove parentmove, int turn)
{
  char killer, victim;
  int aorigin, norigin, atarget, ntarget;
  int val = 0;
  compactmove thismove = makeCompactMove(m);
  killer = m.porigin;
  victim = m.ptarget;
  aorigin = m.origin[0];
  norigin = m.origin[1];
  atarget = m.target[0];
  ntarget = m.target[1];

  if(hashmove == thismove)
    return INFINITY; // Hash table indicates this is best move

  switch(victim){
  case '-':
    switch(killer){
    case 'P':
    case 'p': val += 50; break;
    case 'K':
    case 'k': if(aorigin == 4) //Check out castling moves after captures
                if(atarget == 2 || atarget == 6)
                  val = 75; break;
    default : break;
    }
  case 'P':
  case 'p':
    switch(killer){
    case 'P':
    case 'p': val = 120; break;
    default : val = 100; break;
    } break;
  case 'N':
  case 'n':
    switch(killer){
    case 'P':
    case 'p': val = 370; break;
    default : val = 220; break;
    } break;
  case 'B':
  case 'b':
    switch(killer){
    case 'P':
    case 'p': val = 380; break;
    default : val = 230; break;
    } break;
  case 'R':
  case 'r':
    switch(killer){
    case 'P':
    case 'p': val = 450; break;
    case 'B':
    case 'b': val = 330; break;
    case 'N':
    case 'n': val = 350; break;
    default : val = 300; break;
    } break;
  case 'Q':
  case 'q':
    switch(killer){
    case 'P':
    case 'p': val = 600; break;
    case 'B':
    case 'b': val = 480; break;
    case 'N':
    case 'n': val = 500; break;
    case 'R':
    case 'r': val = 420; break;
    default : val = 400; break;
    } break;
  default:
    switch(killer){
    case 'P':
    case 'p': val += 50; break;
    case 'K':
    case 'k': if(aorigin == 4) //Check out castling moves after captures
                if(atarget == 2 || atarget == 6)
                  val = 75; break;
    default : break;
    }
  }

  if(
    (atarget > 1 && atarget < 6) &&
    (ntarget > 1 && ntarget < 6)
  )
  {
    if(
      (atarget == 3 || atarget == 4) &&
      (ntarget == 3 || ntarget == 4)
    )
      val += 20;
    else
      val += 10;
  }

  if(PVline.cmove)
  { int pv;
    for(pv=1-turn;pv<PVline.cmove;pv=pv+2)
      if(PVlinecompact[pv] == thismove) {
        val += 110;
        break;
      }
  }

  if(parentmove == (thismove & 0xF0F))
    val += 170; // Recapturing the last piece that moved is often beneficial

  return val;
}

int captureVal(move m)
{
  char killer, victim;
  int val = 0;
  killer = m.porigin;
  victim = m.ptarget;
  switch(victim){
  case 'P':
  case 'p':
    switch(killer){
    case 'P':
    case 'p': val = 120; break;
    default : val = 100; break;
    } break;
  case 'N':
  case 'n':
    switch(killer){
    case 'P':
    case 'p': val = 370; break;
    default : val = 220; break;
    } break;
  case 'B':
  case 'b':
    switch(killer){
    case 'P':
    case 'p': val = 380; break;
    default : val = 230; break;
    } break;
  case 'R':
  case 'r':
    switch(killer){
    case 'P':
    case 'p': val = 450; break;
    case 'B':
    case 'b': val = 330; break;
    case 'N':
    case 'n': val = 350; break;
    default : val = 300; break;
    } break;
  case 'Q':
  case 'q':
    switch(killer){
    case 'P':
    case 'p': val = 600; break;
    case 'B':
    case 'b': val = 480; break;
    case 'N':
    case 'n': val = 500; break;
    case 'R':
    case 'r': val = 420; break;
    default : val = 400; break;
    } break;
  default:
    switch(killer){
    case 'P':
    case 'p': val = 50; break;
    default : break;
    }
  }
  return val;
}

/* really old version of evaluate - for comparison
int evaluate(char brd[][8], char player, move lastmove)
{
  int i, j, mate=0, score=0;
//  mate = isMate(brd, lastmove);
//  if(mate==2) {
//    if(blackInCheck(brd, lastmove))
//      score += 99000;
//    if(whiteInCheck(brd, lastmove))
//      score += -99000;
//  }
//  else if(mate==1)
//    return 0;
  if(score == 0)
    for(i=0;i<8;i++)
      for(j=0;j<8;j++) {
        score += pieceValue(brd[i][j]);
        score += positionalValue(i, j, brd[i][j], 90000);
      }
  //score += tacticalValue(brd, lastmove);
  if(player=='B')
    score = -score;
  return score;
}
*/

int evaluate(char brd[][8], char player, move lastmove, int turn, boardcontroldata *bcd, evaldata *stored)
{
  int i, j, score=0, total=0, material = 0;
  int numwpawns = 0, numbpawns = 0;
//  int mate = 0;
  char side = sideToPlay(turn, player);
  if(lastmove.fiftymovecount >= 100) // Draw by 50 move rule!!
  { // Make sure the move wasn't into check before returning Draw!!!
    if(inCheck(sideToPlay(-turn, player), brd, stored->kingPosition))
      return ILLEGAL;
    else
      return 0;
  }
//  mate = isMate(brd, lastmove);
//  if(mate==3) //Black In Check
//      score += MATE;
//  else if(mate==2) //White In Check
//      score += -MATE;
//  else if(mate==1) // Stalemate!
//    return 0;
  if(stored == NULL)
  {
    int k[2]={UNKNOWN,UNKNOWN}, K[2]={UNKNOWN,UNKNOWN};
    int gamestate = MIDDLE;
    for(i=0;i<8;i++)
      for(j=0;j<8;j++)
      {
        char piece = brd[i][j];
        if(piece != '-')
        {
          int pieceVal = pieceValue(piece);
          if(pieceVal < -1000)
            total -= pieceVal;
          else if(pieceVal > 1000) // Pawns and kings not counted towards total
            total += pieceVal;
          material += pieceVal;
          if(piece == 'K' || piece == 'k')
            if(piece == 'K') {
              K[0] = i;
              K[1] = j;
            }
            else {
              k[0] = i;
              k[1] = j;
            }
          else
          {
            if(piece == 'P')
              numwpawns++;
            if(piece == 'p')
              numbpawns++;
          }
        } //end if
      } //end for
    if(K[0] == UNKNOWN || k[0] == UNKNOWN){
      printf("\n Error (Illegal board position): king can be captured\n");
      printf("tellusererror Illegal position\n");
      exit(EXIT_FAILURE);
    }
    if(total <= MAXDEEPENDGAMEVAL)
      gamestate = DEEPEND;
    else if(total <= MAXENDGAMEVAL)
      gamestate = END;
    //Lookup positional bonuses
    for(i=0;i<8;i++)
      for(j=0;j<8;j++)
        if(brd[i][j] != '-')
          score += positionalValue(i, j, brd[i][j], gamestate);
  } //end if (stored == NULL)
  else
  {
    material = stored->material;
    total = stored->totalmaterial;
    numwpawns = stored->numwpawns;
    numbpawns = stored->numbpawns;
    score += stored->positional;
  }
  score += material;
  if(numwpawns == 0 && numbpawns == 0) {
    if(total < MINMATINGVAL) //Draw - Insufficient material
      { // Make sure the move wasn't into check before returning Draw!!!
        if(ILLEGAL == analyzeBoardControl(brd, side, NULL, NULL, NULL))
          return ILLEGAL;
        else
          return 0;
      }
  }
  else // Check if side with material "advantage" has no mating possibilities
  {
    if(numwpawns > 0 && numbpawns == 0 && total < MINMATINGVAL && material < 0) {
      score = 200;
        //we return slight advantage to the player with a pawn,
        //so that the other player has incentive to take it
      material = 0; //to eliminate the "trade-down" bonus further down
    }
    else if(numbpawns > 0 && numwpawns == 0 && total < MINMATINGVAL && material > 0) {
      score = -200;
      material = 0;
    }
  }
  if(lastmove.castle[0] || lastmove.castle[1]) // Bonus if you can still castle
    score += CASTLINGAVAILABILITYBONUS;
  if(lastmove.castle[2] || lastmove.castle[3])
    score -= CASTLINGAVAILABILITYBONUS;
  //score = score + (ADVANTAGE_WEIGHT * (float)material / (float)(total+1)); disabled until it is revised
  //Analyze Board Control
  //if(ANALYZE_BOARD_CONTROL)
/*
  {
    int totalthreat, boardcontrol = 0, kingsafety = 0;
    if(bcd == NULL)
    {
      totalthreat = analyzeBoardControl(brd, side, &boardcontrol, &kingsafety, NULL);
      if(totalthreat == ILLEGAL)
        return ILLEGAL;
    }
    else
    {
      totalthreat = bcd->threatlevel;
      boardcontrol = bcd->boardcontrol;
      kingsafety = bcd->kingsafety;
    }
    score += kingsafety;
    score += (totalthreat * THREAT_WEIGHT);
    score += (boardcontrol * BOARDCONTROL_WEIGHT);
  }
*/
  if(player=='B')
    score = -score;
  return score;
}

evaldata buildEvalData(char brd[][8])
{
  int i, j, total=0, material = 0, positional = 0, gamestate = MIDDLE;
  int numwpawns = 0, numbpawns = 0, numlightbishops = 0, numdarkbishops = 0;
  evaldata myData;
  for(i=0;i<8;i++)
    for(j=0;j<8;j++)
    {
      char piece = brd[i][j];
      if(piece != '-')
      {
        int pieceVal = pieceValue(brd[i][j]);
        if(pieceVal < -1000)
          total -= pieceVal;
        else if(pieceVal > 1000) // Pawns and kings not counted towards total
          total += pieceVal;
        material += pieceVal;
        switch(piece){
        case 'P': numwpawns++; break;
        case 'p': numbpawns++; break;
        case 'b':
        case 'B': if( ((i+j)%2) == 1 ) //light square
                    numlightbishops++;
                  else
                    numdarkbishops++;
        default: break;
        }
      }
    }
  if(total <= MAXDEEPENDGAMEVAL)
    gamestate = DEEPEND;
  else if(total <= MAXENDGAMEVAL)
    gamestate = END;
  //Lookup positional bonuses
  for(i=0;i<8;i++)
    for(j=0;j<8;j++)
      positional += positionalValue(i, j, brd[i][j], gamestate);
  myData.material = material;
  myData.totalmaterial = total;
  myData.positional = positional;
  myData.numwpawns = numwpawns;
  myData.numbpawns = numbpawns;
  myData.numlightbishops = numlightbishops;
  myData.numdarkbishops = numdarkbishops;
  myData.gamestate = gamestate;
  return myData;
}

int pieceValue(char piece)
{
  //Order determined by profiling data
  switch(piece) {
  //case'-': return 0; // We are already checking for blanks before calling this in most cases...
  case'P': return 1000; //Points are in millipawns
  case'p': return -1000;
  case'R': return ROOKVALUE;
  case'r': return -ROOKVALUE;
  case'K': return 0; // do not set to zero ... or maybe we can
  case'k': return 0; // do not set to zero ... or maybe we can
  case'B': return BISHOPVALUE;
  case'b': return -BISHOPVALUE;
  case'N': return KNIGHTVALUE;
  case'n': return -KNIGHTVALUE;
  case'Q': return QUEENVALUE;
  case'q': return -QUEENVALUE;
  default: return 0;
  }
}

int positionalValue(int i, int j, char piece, int gamestate)
{
  //Order determined by profiling data
  switch(gamestate) {
  case MIDDLE:  //Opening/Middlegame
    switch(piece) {
    case'P': return pawnPlacement[ flipJ[j] ][i];
    case'p': return -pawnPlacement[j][i];
    case'R': return 0;
    case'r': return 0;
    case'Q': return 0;
    case'q': return 0;
    case'B': return bishopPlacement[ flipJ[j] ][i];
    case'b': return -bishopPlacement[j][i];
    case'N': return knightPlacement[ flipJ[j] ][i];
    case'n': return -knightPlacement[j][i];
    case'K': return kingPlacement[ flipJ[j] ][i];
    case'k': return -kingPlacement[j][i];
    case'-': return 0; //This won't be reached as much as one might think.
    default: return 0;
    }
  case DEEPEND:  //Wing and advanced pawns become more valuable
    switch(piece) {
    case'K': return kingPlacementEndgame[ flipJ[j] ][i];
    case'k': return -kingPlacementEndgame[j][i];
    case'R': return 50;
    case'r': return -50;
    case'P': return pawnPlacementEndgame[ flipJ[j] ][i];
    case'p': return -pawnPlacementEndgame[j][i];
    case'Q': return 50;
    case'q': return -50;
    case'B': return 0;
    case'b': return 0;
    case'N': return knightPlacement[ flipJ[j] ][i] / 2;
    case'n': return -knightPlacement[j][i] / 2;
    case'-': return 0;
    default: return 0;
    }
  case END:  //Endgame
    switch(piece) {
    case'R': return 50;
    case'r': return -50;
    case'P': return pawnPlacement[ flipJ[j] ][i];
    case'p': return -pawnPlacement[j][i];
    case'K': return kingPlacementEndgame[ flipJ[j] ][i];
    case'k': return -kingPlacementEndgame[j][i];
    case'B': return 0;
    case'b': return 0;
    case'Q': return 50;
    case'q': return -50;
    case'N': return knightPlacement[ flipJ[j] ][i];
    case'n': return -knightPlacement[j][i];
    case'-': return 0;
    default: return 0;
    }
  default: printf("\nError in positionalValue(gamestate)");
    return 0;
  }
}

int analyzeBoardControl(char board[][8], char side, int *control, int *kingsafety, bool *kingincheck) //returns threat level
{
  int attackerdefender[8][8] = { { 0,0,0,0,0,0,0,0 },
                                 { 0,0,0,0,0,0,0,0 },
                                 { 0,0,0,0,0,0,0,0 },
                                 { 0,0,0,0,0,0,0,0 },
                                 { 0,0,0,0,0,0,0,0 },
                                 { 0,0,0,0,0,0,0,0 },
                                 { 0,0,0,0,0,0,0,0 },
                                 { 0,0,0,0,0,0,0,0 },
                               };
  bool threatsquare[8][8] = { { 0,0,0,0,0,0,0,0 },
                              { 0,0,0,0,0,0,0,0 },
                              { 0,0,0,0,0,0,0,0 },
                              { 0,0,0,0,0,0,0,0 },
                              { 0,0,0,0,0,0,0,0 },
                              { 0,0,0,0,0,0,0,0 },
                              { 0,0,0,0,0,0,0,0 },
                              { 0,0,0,0,0,0,0,0 },
                            };
  int totalthreat = 0, squarescontrolled = 0, kingsafetyval = 0;
  int Kalpha = UNKNOWN, Knum = UNKNOWN, kalpha = UNKNOWN, knum = UNKNOWN;
  bool incheck = FALSE;
  int i, j;
  for(i=0;i<8;i++)  // Compute Attacker/Defender Values
    for(j=0;j<8;j++)
    {
      char attacker = board[i][j];
      if(attacker != '-')
      {
        int increment = -1;
        int attackerval = UNKNOWN;
        bool isupper_attacker = isupper(attacker);
        MOVEVECTOR myvector = getMoveVectorCapture(attacker, i, j);
        if(isupper_attacker)
          increment = 1;
        if(attacker == 'K') {
          Kalpha = i;
          Knum = j;
        }
        else if(attacker == 'k') {
          kalpha = i;
          knum = j;
        }
        while(myvector != NULL)
        {
          int x, max;
          max = myvector->index;
          for(x=0;x<max;x++) //&& rayisclear;x++)
          {
            int atarget, ntarget;
            char target;
            atarget = myvector->ray[x].target[0];
            ntarget = myvector->ray[x].target[1];
            target = board[atarget][ntarget];
            attackerdefender[atarget][ntarget] += increment;
            if(target != '-')
            {
              int isupper_target = isupper(target);
              if(isupper_attacker == isupper_target) {
                if(!isBattery(i, j, atarget, ntarget, attacker, target, isupper_attacker))
                  break;
              }
              else // Pieces of different sides
              {
                int threatlevel = 0;
                if(target == 'k' && isupper_attacker)
                {
                  if(side == 'W') // if white to move and black king threatened??
                    return ILLEGAL; // king can be captured in current position - return illegal.
                  threatlevel = 1;
                  incheck = TRUE;
                }
                else if(target == 'K' && !isupper_attacker)
                {
                  if(side == 'B')
                    return ILLEGAL;
                  threatlevel = 1;
                  incheck = TRUE;
                }
                if(threatlevel == 0) {
                  if(attackerval == UNKNOWN)
                    attackerval = pieceValue(attacker);
                  threatlevel = checkExchangeThreat(attacker, target, attackerval);
                }
                if(threatlevel != 0)
                  threatsquare[atarget][ntarget] = threatlevel;
                break;
              }
            }
          } //end ray
          myvector = myvector->next;
        } //end vector
      }
    }
  for(i=0;i<8;i++)  // Tally Threatened Squares and Board Control
    for(j=0;j<8;j++)
    {
      int count = attackerdefender[i][j];
      if(count > 0)
      {
        squarescontrolled += squareProximityToCenter[i][j];
        if(islower(board[i][j]))
          threatsquare[i][j] = 1; //White is attacking a poorly defended black piece
      }
      else if(count < 0)
      {
        squarescontrolled -= squareProximityToCenter[i][j];
        if(isupper(board[i][j]))
          threatsquare[i][j] = -1; //Black is attacking a poorly defended white piece
      }
      totalthreat += threatsquare[i][j];
    }
  /* We now have two useful values:
  ** squarescontrolled, which gives who has the lead in board control and by how much
  ** totalthreat, which gives who has the most threats outstanding and the threat differential
  ** For both variables, positive values favor white and negative values favor black.
  */
  /* Now we must determine if board control threatens either king
  ** We can consider doing this even when kingsafety is a null pointer, since if king safety is bad enough,
  ** we might need to adjust the threat level!
  ** But for now, we're gonna keep it simple.
  */
  if(kingsafety != NULL)
  {
    kingsafetyval += determineKingSafety(board, attackerdefender, 'K', Kalpha, Knum); // + values favour white
    kingsafetyval += determineKingSafety(board, attackerdefender, 'k', kalpha, knum); // + values favour white
  }
  /* We return the useful information:
  ** If a pointer is null, then the caller doesn't need that info.
  */
  if(kingincheck != NULL)
    if(incheck)
      *kingincheck = TRUE;
  if(control != NULL)
    *control = squarescontrolled;
  if(kingsafety != NULL)
    *kingsafety = kingsafetyval;
  return totalthreat;
}
/*
// Original version of isBattery
bool isBattery(int i, int j, int atarget, int ntarget, char attacker, char target, bool isupper_attacker)
{
  if(isupper_attacker)
  {
    if( (attacker == 'R' || attacker == 'Q') &&
        (target == 'R' || target == 'Q') &&
        (i == atarget || j == ntarget)
      )
      return TRUE; // rook-type battery
    if( (attacker == 'B' || attacker == 'Q') &&
        (target == 'B' || target == 'Q') &&
        (i != atarget && j != ntarget)
      )
      return TRUE; // bishop-type battery
  }
  else
  {
    if( (attacker == 'r' || attacker == 'q') &&
        (target == 'r' || target == 'q') &&
        (i == atarget || j == ntarget)
      )
      return TRUE; // rook-type battery
    if( (attacker == 'b' || attacker == 'q') &&
        (target == 'b' || target == 'q') &&
        (i != atarget && j != ntarget)
      )
      return TRUE; // bishop-type battery
  }
  return FALSE;
}
*/
// Alternative version of isBattery
bool isBattery(int i, int j, int atarget, int ntarget, char attacker, char target, bool isupper_attacker)
{
  switch(attacker) {
  case 'R': if(target == 'R' || target == 'Q')
                return TRUE; break;
  case 'r': if(target == 'r' || target == 'q')
                return TRUE; break;
  case 'B': if(target == 'B' || target == 'Q')
                return TRUE; break;
  case 'b': if(target == 'b' || target == 'q')
                return TRUE; break;
  case 'Q': if(target == 'Q')
                return TRUE;
            if(target == 'B' && (i != atarget && j != ntarget))
                return TRUE;
            if(target == 'R' && (i == atarget || j == ntarget))
                return TRUE; break;
  case 'q': if(target == 'q')
                return TRUE;
            if(target == 'b' && (i != atarget && j != ntarget))
                return TRUE;
            if(target == 'r' && (i == atarget || j == ntarget))
                return TRUE; break;
  }
  return FALSE;
}

bool checkExchangeThreat(char attacker, char target, int attackerval)
{
  int targetval = pieceValue(target);
  if( attacker == 'k' || attacker == 'K')
    return 0; // Kings cannot win the exchange
//  if(target == 'k' && isupper(attacker))        - currently done in boardcontrol
//    return 1; // King targets always lose the exchange
//  if(target == 'K' && islower(attacker))
//    return -1; // King targets always lose the exchange
  if(attackerval < 0)
    attackerval = -attackerval;
  if(targetval < 0)
    targetval = -targetval;
  if(targetval > attackerval)
  {
    if(isupper(attacker) && islower(target))
      return 1;
    if(islower(attacker) && isupper(target))
      return -1;
  }
  return 0;
}

int determineKingSafety(char board[][8], int attackerdefender[][8], char king, int alpha, int numeric)
{
  int kingtype = 1, kingsafetyval = 0;
  char friendlypawn = 'P';
  if(king == 'k')
  {
    friendlypawn = 'p';
    kingtype = -1;
  }
  {
    MOVEVECTOR myvector = getMoveVector(king, alpha, numeric);
    while(myvector != NULL)
    {
      int atarget, ntarget, control;
      atarget = myvector->ray[0].target[0];
      ntarget = myvector->ray[0].target[1];
      if(board[atarget][ntarget] == friendlypawn)
        kingsafetyval += FRIENDLYPAWNBONUS;
      control = kingtype * attackerdefender[atarget][ntarget];
      if(control == 0)
        kingsafetyval += CONTESTEDSQUAREPENALTY;
      else if(control < 0)
        kingsafetyval += THREATENEDSQUAREPENALTY;
      myvector = myvector->next;
    }
  }
  if(king == 'k')
    kingsafetyval = -kingsafetyval; // caller expects positive values to favor white.
  return kingsafetyval;
}

// Here is where the fun begins!!
/* note: above comment was written very early in implementation,
     when legality testing was the most daunting task.
*/

bool isLegal(move m, char brd[][8], move lastmove)
{
  char player = 'W';
  int oalpha_m = m.origin[0], onum_m = m.origin[1], talpha_m = m.target[0], tnum_m = m.target[1];
  move nextmove = makeMove(oalpha_m, onum_m, talpha_m, m.target[1], lastmove, brd);
// Can comment out since we trust the movegen and player input
// /*
  if(0 > oalpha_m)
    return FALSE;
  if(oalpha_m > 7)
    return FALSE;
  if(0 > onum_m)
    return FALSE;
  if(onum_m > 7)
    return FALSE;
  if(0 > talpha_m)
    return FALSE;
  if(talpha_m > 7)
    return FALSE;
  if(0 > tnum_m)
    return FALSE;
  if(tnum_m > 7)
    return FALSE;
// */
  if(isupper(brd[lastmove.target[0]][lastmove.target[1]]))
    player = 'B';
  // We now know that the move involves two legit board squares.
  // Additionally we have determined whose turn it is to move.
  if(brd[oalpha_m][onum_m]=='-'){
    //printf(" -'s are being passed to isLegal");
    return FALSE;}
  // The origin is not an empty square.
// /*
  if(player=='W') {
    if(isupper(brd[talpha_m][tnum_m]))
      return FALSE;
    if(islower(brd[oalpha_m][onum_m]))
      return FALSE;
  }
  if(player=='B') {
    if(islower(brd[talpha_m][tnum_m]))
      return FALSE;
    if(isupper(brd[oalpha_m][onum_m]))
      return FALSE;
  }
// */
  // The move does not try to take a piece of the same army or move a piece of the other army
  switch(brd[oalpha_m][onum_m]) {
    case'P':
      if(!isLegalP(m, brd, lastmove))
        return FALSE;
      break;
    case'p':
      if(!isLegalp(m, brd, lastmove))
        return FALSE;
      break;
    case'N':
      if(!isLegalKNight(m))
        return FALSE;
      break;
    case'n':
      if(!isLegalKNight(m))
        return FALSE;
      break;
    case'B':
      if(!isLegalBishop(m, brd))
        return FALSE;
      break;
    case'b':
      if(!isLegalBishop(m, brd))
        return FALSE;
      break;
    case'R':
      if(!isLegalRook(m, brd))
        return FALSE;
      break;
    case'r':
      if(!isLegalRook(m, brd))
        return FALSE;
      break;
    case'Q':
      if(!isLegalQueen(m, brd))
        return FALSE;
      break;
    case'q':
      if(!isLegalQueen(m, brd))
        return FALSE;
      break;
    case'K':
      if(!isLegalK(m, brd))
        return FALSE;
      break;
    case'k':
      if(!isLegalk(m, brd))
        return FALSE;
      break;
    default: printf("\nError: Invalid Piece Type... %c\n", brd[oalpha_m][onum_m]);
    }
  // We now know that the move is to a valid square given piece type.
  executeMove(brd, nextmove, NULL);
  if(player=='W')
    if(inCheckWrapper('W', brd)) {
      undoMove(brd, nextmove, NULL);
      return FALSE;
    }
  if(player=='B')
    if(inCheckWrapper('B', brd)) {
      undoMove(brd, nextmove, NULL);
      return FALSE;
    }
  undoMove(brd, nextmove, NULL);
  // We now know that the move is not a move into check.
  return TRUE;
}

bool isLegalP(move m, char brd[][8], move lastmove)
{
  int oalpha_m = m.origin[0], onum_m = m.origin[1], talpha_m = m.target[0], tnum_m = m.target[1];
  int onum_lastmove = lastmove.origin[1], talpha_lastmove = lastmove.target[0], tnum_lastmove = lastmove.target[1];
  if(oalpha_m==talpha_m)
    if(tnum_m==(onum_m+1))
      if(brd[talpha_m][tnum_m]=='-')
        return TRUE;
  if(talpha_m==(oalpha_m+1) || talpha_m==(oalpha_m-1))
    if(tnum_m==(onum_m+1)) {
      if(islower(brd[talpha_m][tnum_m])) {
        return TRUE; }
      else if(brd[talpha_lastmove][tnum_lastmove]=='p')
        if(tnum_lastmove==4)
          if(onum_lastmove==6)
            if(tnum_m==5)
              if(talpha_m==talpha_lastmove)
                return TRUE;
    }
  if(onum_m==1)
    if(tnum_m==3)
      if(oalpha_m==talpha_m)
        if(brd[talpha_m][tnum_m]=='-')
          if(brd[talpha_m][tnum_m-1]=='-')
            return TRUE;
  return FALSE;
}

bool isLegalp(move m, char brd[][8], move lastmove)
{
  int oalpha_m = m.origin[0], onum_m = m.origin[1], talpha_m = m.target[0], tnum_m = m.target[1];
  int onum_lastmove = lastmove.origin[1], talpha_lastmove = lastmove.target[0], tnum_lastmove = lastmove.target[1];
  if(oalpha_m==talpha_m)
    if(tnum_m==(onum_m-1))
      if(brd[talpha_m][tnum_m]=='-')
        return TRUE;
  if((talpha_m==(oalpha_m+1) || talpha_m==(oalpha_m-1)))
    if(tnum_m==(onum_m-1)) {
      if(isupper(brd[talpha_m][tnum_m])) {
        return TRUE; }
      else if(brd[talpha_lastmove][tnum_lastmove]=='P')
        if(tnum_lastmove==3)
          if(onum_lastmove==1)
            if(tnum_m==2)
              if(talpha_m==talpha_lastmove)
                return TRUE;
    }
  if(onum_m==6)
    if(tnum_m==4)
      if(oalpha_m==talpha_m)
        if(brd[talpha_m][tnum_m]=='-')
          if(brd[talpha_m][tnum_m+1]=='-')
            return TRUE;
  return FALSE;
}

bool isLegalKNight(move m)
{
  int oalpha_m = m.origin[0], onum_m = m.origin[1], talpha_m = m.target[0], tnum_m = m.target[1];
  if(talpha_m==(oalpha_m+2))
    if((tnum_m==(onum_m+1) || tnum_m==(onum_m-1)) )
      return TRUE;
  if(talpha_m==(oalpha_m+1))
    if((tnum_m==(onum_m+2) || tnum_m==(onum_m-2)) )
      return TRUE;
  if(talpha_m==(oalpha_m-1))
    if((tnum_m==(onum_m+2) || tnum_m==(onum_m-2)) )
      return TRUE;
  if(talpha_m==(oalpha_m-2))
    if((tnum_m==(onum_m+1) || tnum_m==(onum_m-1)) )
      return TRUE;
  return FALSE;
}

bool isLegalBishop(move m, char brd[][8])
{
  int oalpha_m = m.origin[0], onum_m = m.origin[1], talpha_m = m.target[0], tnum_m = m.target[1];
  if((oalpha_m-talpha_m==onum_m-tnum_m || oalpha_m-talpha_m==tnum_m-onum_m ))
    if(isClearDiagonal(m, brd) )
      return TRUE;
  return FALSE;
}

bool isLegalRook(move m, char brd[][8])
{
  int oalpha_m = m.origin[0], onum_m = m.origin[1], talpha_m = m.target[0], tnum_m = m.target[1];
  if(oalpha_m==talpha_m)
    if(isClearFile(m, brd) )
      return TRUE;
  if(onum_m==tnum_m)
    if(isClearRank(m, brd) )
      return TRUE;
  return FALSE;
}

bool isLegalQueen(move m, char brd[][8])
{
  if(isLegalRook(m, brd))
    return TRUE;
  if(isLegalBishop(m, brd))
    return TRUE;
  return FALSE;
}

bool isLegalK(move m, char brd[][8])
{
  int oalpha_m = m.origin[0], onum_m = m.origin[1], talpha_m = m.target[0], tnum_m = m.target[1];
  if(talpha_m==(oalpha_m+1) || talpha_m==(oalpha_m-1) || oalpha_m==talpha_m )
    if(tnum_m==onum_m || tnum_m==(onum_m+1) || tnum_m==(onum_m-1) )
      return TRUE;
  if(talpha_m==2)
    if(tnum_m==0)
      if(m.castle[0] || m.castleChanged[0])
        if(brd[1][0]=='-' && brd[2][0]=='-' && brd[3][0]=='-')
          if(!whiteIsPinned(3, 0, brd))
            if(!whiteIsPinned(2, 0, brd))
              if(!inCheckWrapper('W', brd))
                return TRUE;
  if(talpha_m==6)
    if(tnum_m==0)
      if(m.castle[1] || m.castleChanged[1]) //castleChanged may set if king is in process of castling
        if(brd[5][0]=='-' && brd[6][0]=='-')
          if(!whiteIsPinned(5, 0, brd))
            if(!whiteIsPinned(6, 0, brd))
              if(!inCheckWrapper('W', brd))
                return TRUE;
  return FALSE;
}

bool isLegalk(move m, char brd[][8])
{
  int oalpha_m = m.origin[0], onum_m = m.origin[1], talpha_m = m.target[0], tnum_m = m.target[1];
  if(talpha_m==(oalpha_m+1) || talpha_m==(oalpha_m-1) || oalpha_m==talpha_m )
    if(tnum_m==onum_m || tnum_m==(onum_m+1) || tnum_m==(onum_m-1) )
      return TRUE;
  if(talpha_m==2)
    if(tnum_m==7)
      if(m.castle[2] || m.castleChanged[2])
        if(brd[1][7]=='-' && brd[2][7]=='-' && brd[3][7]=='-')
          if(!blackIsPinned(3, 7, brd))
            if(!blackIsPinned(2, 7, brd))
              if(!inCheckWrapper('B', brd))
                return TRUE;
  if(talpha_m==6)
    if(tnum_m==7)
      if(m.castle[3] || m.castleChanged[3])
        if(brd[5][7]=='-' && brd[6][7]=='-')
          if(!blackIsPinned(5, 7, brd))
            if(!blackIsPinned(6, 7, brd))
              if(!inCheckWrapper('B', brd))
                return TRUE;
  return FALSE;
}
/*
bool isLOWER(char c)
{
  if( (int)c > 97 )
   return TRUE;
  return FALSE;
  //return islower(c);
}
*/

coordinates findKings(char brd[][8])
{
  coordinates kingPosition;
  int i, j;
  for(i=0;i<8;i++)
    for(j=0;j<8;j++)
    {
      char piece = brd[i][j];
      if(piece == 'K') {
        kingPosition.origin[0] = i;
        kingPosition.origin[1] = j;
      }
      else if(piece == 'k')
      {
        kingPosition.target[0] = i;
        kingPosition.target[1] = j;
      }
    }
  return kingPosition;
}

bool inCheckWrapper(char target, char brd[][8])
{
  coordinates kingPosition;
  int i, j;
  for(i=0;i<8;i++)
    for(j=0;j<8;j++)
    {
      char piece = brd[i][j];
      if(piece == 'K') {
        kingPosition.origin[0] = i;
        kingPosition.origin[1] = j;
      }
      else if(piece == 'k')
      {
        kingPosition.target[0] = i;
        kingPosition.target[1] = j;
      }
    }
  return inCheck(target, brd, kingPosition);
}

bool inCheck(char target, char brd[][8], coordinates kingPosition)
{
  int i;
  MOVEVECTOR myvector;
  // The pawn values below are not a mistake!
  char black[] = {'n', 'b', 'r', 'P', 'q', 'p'};
  char white[] = {'N', 'B', 'R', 'p', 'Q', 'P'};
  char *piecetype;
  char *queentype;
  char *pawntype;
  //By convention, white king is stored in coord origin, black in target
  int alpha, numeric; //location of king
  int o_alpha, o_numeric; //location of opposing king
  if(target == 'W') {
    alpha = kingPosition.origin[0];
    numeric = kingPosition.origin[1];
    o_alpha = kingPosition.target[0];
    o_numeric = kingPosition.target[1];
    piecetype = black;
  }
  else {
    alpha = kingPosition.target[0];
    numeric = kingPosition.target[1];
    o_alpha = kingPosition.origin[0];
    o_numeric = kingPosition.origin[1];
    piecetype = white;
  }
  queentype = piecetype + 4; //pointer arithmetic
  pawntype = piecetype + 5;

  // Look for knight attacks
  myvector = getMoveVectorCapture(*piecetype, alpha, numeric);
  while(myvector != NULL)
  {
    int atarget, ntarget;
    atarget = myvector->ray[0].target[0];
    ntarget = myvector->ray[0].target[1];
    if(brd[atarget][ntarget] == *piecetype)
      return TRUE;
    myvector = myvector->next;
  }

  //Look for bishop/queen, then rook/queen attacks
  for(i=0;i<2;i++)
  {
    piecetype++;
    myvector = getMoveVectorCapture(*piecetype, alpha, numeric);
    while(myvector != NULL)
    {
      int x, max, atarget, ntarget;
      max = myvector->index;
      for(x=0;x<max;x++)
      {
        char target;
        atarget = myvector->ray[x].target[0];
        ntarget = myvector->ray[x].target[1];
        target = brd[atarget][ntarget];
        if(target == *piecetype || target == *queentype)
          return TRUE;
        if(target != '-')
          break; //rayisclear = FALSE;
      }
      myvector = myvector->next;
    }
  }

  //Look for pawn attacks
  //We can't use vectors here because they don't cover the 1st & 8th ranks
  piecetype++;
  if(target == 'B' && numeric > 1) {
    if(alpha > 0)
      if(brd[alpha-1][numeric-1] == 'P')
        return TRUE;
    if(alpha < 7)
      if(brd[alpha+1][numeric-1] == 'P')
        return TRUE;
  }
  else if(target == 'W' && numeric < 6) {
    if(alpha > 0)
      if(brd[alpha-1][numeric+1] == 'p')
        return TRUE;
    if(alpha < 7)
      if(brd[alpha+1][numeric+1] == 'p')
        return TRUE;
  }

  //Look for king attacks
  {
    int alphadiff = alpha - o_alpha;
    int numdiff = numeric - o_numeric;
    if(abs(alphadiff) < 2 && abs(numdiff) < 2)
      return TRUE; // The kings are within a square of each other.
  }

  //End of function
  return FALSE;
}

bool whiteInCheck(char brd[][8])
{
  int i, j, alpha = UNKNOWN, numeric = UNKNOWN;
  bool kingfound = 0;
  for(i=0;i<8 && kingfound==0;i++)
    for(j=0;j<8;j++)
      if(brd[i][j]=='K') {
        alpha=i;
        numeric=j;
        kingfound=TRUE;
        break;
      }
  if(kingfound == FALSE){
    printf("\nError: White king is missing in whiteInCheck\n");
    return TRUE;
  }
  for(i=0;i<8;i++)
    for(j=0;j<8;j++)
      if(islower(brd[i][j]))
      {
        MOVEVECTOR myvector = getMoveVectorCapture(brd[i][j], i, j);
        while(myvector != NULL)
        {
          int x, max, atarget, ntarget;
          max = myvector->index;
          for(x=0;x<max;x++)
          {
            atarget = myvector->ray[x].target[0];
            ntarget = myvector->ray[x].target[1];
            if(atarget == alpha && ntarget == numeric)
              return TRUE;
            if(brd[atarget][ntarget] != '-')
              break; //rayisclear = FALSE;
          }
          myvector = myvector->next;
        }
      }
  return FALSE;
}

bool blackInCheck(char brd[][8])
{
  int i, j, alpha = UNKNOWN, numeric = UNKNOWN;
  bool kingfound = 0;
  for(i=0;i<8 && kingfound==0;i++)
    for(j=7;j>=0 && kingfound==0;j--)
      if(brd[i][j]=='k') {
        alpha=i;
        numeric=j;
        kingfound=TRUE;
      }
  if(kingfound == FALSE){
    printf("\nError: Black king is missing in blackInCheck\n");
    return TRUE;
  }
  for(i=0;i<8;i++)
    for(j=0;j<8;j++)
      if(isupper(brd[i][j]))
      {
        MOVEVECTOR myvector = getMoveVectorCapture(brd[i][j], i, j);
        while(myvector != NULL)
        {
          int x, max, atarget, ntarget;
          max = myvector->index;
          for(x=0;x<max;x++)
          {
            atarget = myvector->ray[x].target[0];
            ntarget = myvector->ray[x].target[1];
            if(atarget == alpha && ntarget == numeric)
              return TRUE;
            if(brd[atarget][ntarget] != '-')
              break; //rayisclear = FALSE;
          }
          myvector = myvector->next;
        }
      }
  return FALSE;
}

bool whiteIsPinned(int alpha, int numeric, char brd[][8])
{
  int i, j;
  for(i=0;i<8;i++)
    for(j=0;j<8;j++)
      if(islower(brd[i][j]))
      {
        MOVEVECTOR myvector = getMoveVectorCapture(brd[i][j], i, j);
        while(myvector != NULL)
        {
          int x, max, atarget, ntarget;
          max = myvector->index;
          for(x=0;x<max;x++)
          {
            atarget = myvector->ray[x].target[0];
            ntarget = myvector->ray[x].target[1];
            if(atarget == alpha && ntarget == numeric)
              return TRUE;
            else if(brd[atarget][ntarget] != '-')
              break; //rayisclear = FALSE;
          }
          myvector = myvector->next;
        }
      }
  return FALSE;
}

bool blackIsPinned(int alpha, int numeric, char brd[][8])
{
  int i, j;
  for(i=0;i<8;i++)
    for(j=0;j<8;j++)
      if(isupper(brd[i][j]))
      {
        MOVEVECTOR myvector = getMoveVectorCapture(brd[i][j], i, j);
        while(myvector != NULL)
        {
          int x, max, atarget, ntarget;
          max = myvector->index;
          for(x=0;x<max;x++)
          {
            atarget = myvector->ray[x].target[0];
            ntarget = myvector->ray[x].target[1];
            if(atarget == alpha && ntarget == numeric)
              return TRUE;
            else if(brd[atarget][ntarget] != '-')
              break; //rayisclear = FALSE;
          }
          myvector = myvector->next;
        }
      }
  return FALSE;
}

bool isClearDiagonal(move m, char brd[][8])
{
  int i, j, istart, ifinish;
  int oalpha_m = m.origin[0], onum_m = m.origin[1], talpha_m = m.target[0], tnum_m = m.target[1];
  if(oalpha_m > talpha_m) {
    if(onum_m > tnum_m) {
      istart=talpha_m+1;
      ifinish=oalpha_m;
      j=tnum_m+1;
      for(i=istart;i<ifinish;i++) {
        if(brd[i][j]!='-')
          return FALSE;
        j++;
      }
      return TRUE;
    }
    else {
      istart=oalpha_m-1;
      ifinish=talpha_m;
      j=onum_m+1;
      for(i=istart;i>ifinish;i--) {
        if(brd[i][j]!='-')
          return FALSE;
        j++;
      }
      return TRUE;
    }
  }
  if(onum_m > tnum_m) {
    istart=talpha_m-1;
    ifinish=oalpha_m;
    j=tnum_m+1;
    for(i=istart;i>ifinish;i--) {
      if(brd[i][j]!='-')
        return FALSE;
      j++;
    }
    return TRUE;
  }
  else {
    istart=oalpha_m+1;
    ifinish=talpha_m;
    j=onum_m+1;
    for(i=istart;i<ifinish;i++) {
      if(brd[i][j]!='-')
        return FALSE;
      j++;
    }
    return TRUE;
  }
}

bool isClearFile(move m, char brd[][8])
{
  int i, start, finish;
  int oalpha_m = m.origin[0], onum_m = m.origin[1], tnum_m = m.target[1];
  if(onum_m > tnum_m) {
    start=tnum_m+1;
    finish=onum_m;
  }
  else {
    start=onum_m+1;
    finish=tnum_m;
  }
  for(i=start;i<finish;i++)
    if(brd[oalpha_m][i]!='-')
      return FALSE;
  return TRUE;
}

bool isClearRank(move m, char brd[][8])
{
  int i, start, finish;
  int oalpha_m = m.origin[0], onum_m = m.origin[1], talpha_m = m.target[0];
  if(oalpha_m > talpha_m) {
    start=talpha_m+1;
    finish=oalpha_m;
  }
  else {
    start=oalpha_m+1;
    finish=talpha_m;
  }
  for(i=start;i<finish;i++)
    if(brd[i][onum_m]!='-')
      return FALSE;
  return TRUE;
}

int isMate(char brd[][8], move lastmove)
{
  int i, j;
  char player = 'W';
  move newmove;
  if(isupper(brd[lastmove.target[0]][lastmove.target[1]]))
    player = 'B';
  for(i=0;i<8;i++)
    for(j=0;j<8;j++)
      //if((!islower(brd[i][j])) && (!isupper(brd[i][j])) && (brd[i][j] != '-'))
      //  printf("\nError, invalid board on mate check. %c", brd[i][j]);
      if(brd[i][j] != '-')
        if(
          (player == 'W' && isupper(brd[i][j])) ||
          (player == 'B' && islower(brd[i][j])) )
        {
          MOVEVECTOR myvector = getMoveVector(brd[i][j], i, j);
          while(myvector != NULL)
          {
            int x, max, atarget, ntarget;
            bool rayisclear = TRUE;
            max = myvector->index;
            for(x=0;x<max && rayisclear;x++)
            {
              atarget = myvector->ray[x].target[0];
              ntarget = myvector->ray[x].target[1];
              if( (player == 'W' && !isupper(brd[atarget][ntarget])) ||
                  (player == 'B' && !islower(brd[atarget][ntarget])) )
              {
                if(brd[atarget][ntarget] != '-') //capture move
                  rayisclear = FALSE;
                newmove = makeMove(i, j, atarget, ntarget, lastmove, brd);
                if(isLegalVector(newmove, brd, lastmove, player, TRUE))
                  return 0;
              }
              else //We ran into one of our own pieces
                rayisclear = FALSE;
            }
            myvector = myvector->next;
          }
        }
  if(inCheckWrapper('W', brd))
    return 2;
  if(inCheckWrapper('B', brd))
    return 3;
  return 1;
}

void setMinMatingVal(void)
{
  int bishops = 2 * BISHOPVALUE;
  int knights = 2 * KNIGHTVALUE;
  int val = ROOKVALUE;
  if(bishops < val)
    val = bishops;
  if(knights < val)
    val = knights;
  MINMATINGVAL = val; // Works as long as kings are not counted;
  //You'd really have to do a number on the piecevalues to break this.
}


bool insufficientMaterial(char brd[][8])
{
  int i, j, total = 0;
  for(i=0;i<8;i++)
      for(j=0;j<8;j++)
      {
        char piece = brd[i][j];
        int pieceval = pieceValue(piece);
        if(pieceval != 0)
        {
          if(piece == 'P' || piece == 'p')
            return FALSE; //Cannot have insuff. mat. with pawns
          if(pieceval < 0)
            total -= pieceval;
          else
            total += pieceval;
        }
      }
  if(total < MINMATINGVAL)
    return TRUE; //Draw - Insufficient material
  return FALSE;
}

void addPosition(U64 stack[], U64 key, bool fromSearchTree)
{
  stack[(int)stack[1]] = key;
  stack[1] += 1;
  if(!fromSearchTree)
    stack[0] += 1;
}

// isThirdRep and findPosition accomplish the same task
// isThirdRep has extra functionality that only helps during a search.

bool isThirdRep(U64 stack[], U64 key)
{
  int i, count = 0;
  int playedmoves = stack[0]; //index for last move actually played on board
  int endofstack = stack[1]; //index for end of stack, (moves from search)
  if(playedmoves > endofstack)
    printf("tellusererror Error: base moves > entire stack\n");
  for(i=playedmoves; i<endofstack; i++)
    if(stack[i] == key)
    {
      count++;
      if(count == 2)
        return TRUE; //If a position repeats in search even once, the draw is forced!
    }
  for(i=2;i<playedmoves;i++)
    if(stack[i] == key)
      count++;
  if(count >= 3)
    return TRUE;
  return FALSE;
}

int findPosition(U64 stack[], U64 key)
{
  U64 i, count = 0;
  for(i=2;i<stack[0];i++)
    if(stack[(int)i] == key)
      count++;
  return count;
}

void clearStack(U64 stack[])
{
  stack[0] = 2;
  stack[1] = 2;
}

U64 removePosition(U64 stack[], bool fromSearchTree)
{
  if(stack[1] == 2) //Stack already empty
    return 0;
  stack[1] -= 1;
  if(!fromSearchTree)
    stack[0] -= 1;
  return stack[(int)stack[1]+1];
}

bool stackReset(move m)
{
  if(m.porigin == 'P' || m.porigin == 'p')
    return TRUE;
  if(m.ptarget != '-')
    return TRUE;
  return FALSE;
}

move setCastlingForMove(move newmove, char porigin, char ptarget, int oa, int ta, int tn)
{
  if(porigin=='K')
  {
    if(newmove.castle[0]) {
      newmove.castle[0]=FALSE;
      newmove.castleChanged[0] = TRUE;
    }
    if(newmove.castle[1]) {
      newmove.castle[1]=FALSE;
      newmove.castleChanged[1] = TRUE;
    }
  }
  if(porigin=='k')
  {
    if(newmove.castle[2]) {
      newmove.castle[2]=FALSE;
      newmove.castleChanged[2] = TRUE;
    }
    if(newmove.castle[3]) {
      newmove.castle[3]=FALSE;
      newmove.castleChanged[3] = TRUE;
    }
  }
  if(porigin=='R')
  {
    if (oa == 0 && newmove.castle[0] == TRUE) {
      newmove.castle[0]=FALSE;
      newmove.castleChanged[0]=TRUE;
    }
    else if (oa == 7 && newmove.castle[1] == TRUE) {
      newmove.castle[1]=FALSE;
      newmove.castleChanged[1]=TRUE;
    }
  }
  if(porigin=='r')
  {
    if (oa == 0 && newmove.castle[2] == TRUE) {
      newmove.castle[2]=FALSE;
      newmove.castleChanged[2]=TRUE;
    }
    else if (oa == 7 && newmove.castle[3] == TRUE) {
      newmove.castle[3]=FALSE;
      newmove.castleChanged[3]=TRUE;
    }
  }
  if(ptarget=='R' && tn==0)
  {
    if (ta == 0 && newmove.castle[0] == TRUE) {
      newmove.castle[0]=FALSE;
      newmove.castleChanged[0]=TRUE;
    }
    else if (ta == 7 && newmove.castle[1] == TRUE) {
      newmove.castle[1]=FALSE;
      newmove.castleChanged[1]=TRUE;
    }
  }
  if(ptarget=='r' && tn==7)
  {
    if (ta == 0 && newmove.castle[2] == TRUE) {
      newmove.castle[2]=FALSE;
      newmove.castleChanged[2]=TRUE;
    }
    else if (ta == 7 && newmove.castle[3] == TRUE) {
      newmove.castle[3]=FALSE;
      newmove.castleChanged[3]=TRUE;
    }
  }
  return newmove;
}

move makeMove(int oa, int on, int ta, int tn, move lastmove, char board[][8])
{
  move newmove;
  int i;
  bool promotion = FALSE;
  char porigin = board[oa][on], ptarget = board[ta][tn];
  newmove.origin[0]=oa;
  newmove.origin[1]=on;
  newmove.target[0]=ta;
  newmove.target[1]=tn;
  for(i=0;i<4;i++) {
    newmove.castle[i]=lastmove.castle[i];
    newmove.castleChanged[i] = FALSE;
  }
  newmove = setCastlingForMove(newmove, porigin, ptarget, oa, ta, tn);
  newmove.porigin = porigin;
  newmove.ptarget = ptarget;
  newmove.promotion = NULLCHAR;
  if( (porigin == 'p' || porigin == 'P') &&
      (tn == 7 || tn == 0)
    )
  {
    promotion = TRUE;
    newmove.promotion = 'q';
  }
  //Special conditions for en passant
  if( oa != ta && (porigin == 'P' || porigin == 'p') &&  ptarget == '-')
    newmove.enPassantOccurred = TRUE;
  else
    newmove.enPassantOccurred = FALSE;
  //Reset 50movecount if capture or pawn push
  if(ptarget != '-' || porigin == 'p' || porigin == 'P' || promotion)
    newmove.fiftymovecount = 0;  //50 moves WITHOUT a capture...
    //This represents move 0, NOT move 1.
  else
    newmove.fiftymovecount = lastmove.fiftymovecount + 1;
  return newmove;
}

move makeMoveFromCompact(compactmove thismove, move lastmove, char board[][8])
{
  int oa = (thismove & 0xFF000000) >> 24;
  int on = (thismove & 0xFF0000) >> 16;
  int ta = (thismove & 0xFF00) >> 8;
  int tn = thismove & 0xFF;
  return makeMove(oa, on, ta, tn, lastmove, board);
}

move convertInput(char input[], move lastmove, bool usermove, char board[][8])
{
  move newmove;
  int oa, on, ta, tn, adjust = 0;
  if(usermove)
    adjust = 9;
  oa = (int)input[0+adjust];
  oa -= 97;
  on = (int)input[1+adjust];
  on -= 49;
  ta = (int)input[2+adjust];
  ta -= 97;
  tn = (int)input[3+adjust];
  tn -= 49;
  newmove = makeMove(oa, on, ta, tn, lastmove, board);
  switch(input[4+adjust]){
  case 'q': newmove.promotion = 'q'; break;
  case 'r': newmove.promotion = 'r'; break;
  case 'b': newmove.promotion = 'b'; break;
  case 'n': newmove.promotion = 'n'; break;
  }
  return newmove;
}

/* Special thanks to Bruce Moreland, whose website provided the
   sample code and explanations upon which the following functions relating
   to zobrist keys were based.
   http://www.seanet.com/~brucemo/topics/topics.htm
*/

U64 rand64(void)
{
    return rand() ^ ((U64)rand() << 15) ^ ((U64)rand() << 30) ^
        ((U64)rand() << 45) ^ ((U64)rand() << 60);
}

bool isZobristUnique(U64 key)
{
  int i, j, k;
  for(i=0;i<6;i++)
    for(j=0;j<2;j++)
      for(k=0;k<64;k++)
        if(zobrist[i][j][k] == key)
          return FALSE;
  if(zobristColor == key)
    return FALSE;
  for(i=0;i<4;i++)
    if(zobristCastle[i] == key)
      return FALSE;
  return TRUE;
}

U64 getUniqueZobrist(void)
{
  U64 key = rand64();
  while(isZobristUnique(key) != TRUE)
    key = rand64();
  return key;
}

void fillZobrist(void)
{
  int i, j, k;
  for(i=0;i<6;i++)
    for(j=0;j<2;j++)
      for(k=0;k<64;k++)
        zobrist[i][j][k] = getUniqueZobrist();
/*      debug:
        {
        U64 key = 1;
        zobrist[i][j][k] = key << k;
        }
*/
  zobristColor = getUniqueZobrist();
  for(i=0;i<4;i++)
    zobristCastle[i] = getUniqueZobrist();
  //zobristEnPassant = getUniqueZobrist();
}

U64 getZobrist(char piece, int file, int rank)
{
  int index, square = 8 * file + rank;
  bool isBlack = FALSE;
  if(islower(piece))
    isBlack = TRUE;
  switch(piece){
  case 'K':
  case 'k': index = 5; break;
  case 'Q':
  case 'q': index = 4; break;
  case 'R':
  case 'r': index = 3; break;
  case 'B':
  case 'b': index = 2; break;
  case 'N':
  case 'n': index = 1; break;
  case 'P':
  case 'p': index = 0; break;
  case '-': return 0;
  default: return 0;
  }
  return zobrist[index][isBlack][square];
}

U64 generateHashKey(char brd[][8], move m, char side)
{
  U64 key = 0;
  int i, j;
  for(i=0;i<8;i++)
    for(j=0;j<8;j++)
      key = key ^ getZobrist(brd[i][j], i, j);
  if(side == 'B')
    key = key ^ zobristColor;
  for(i=0;i<4;i++)
    if(m.castle[i])
      key = key ^ zobristCastle[i];
  /* This code is unnecessary because en passant positions are always unique
  ** and thus are simply not pushed onto the history stack. (And result in an
  ** empty history stack because it is a pawn move)
  ** Without this code, we shouldn't store en passants in the hash table.
  if(
      (m.porigin == 'p' && m.origin[1] == 6 && m.target[1] == 4) ||
      (m.porigin == 'P' && m.origin[1] == 1 && m.target[1] == 3)
    )
    key = key ^ zobristEnPassant;
  */
  return key;
}

U64 modifyHashKey(U64 key, move m)
{
  int i;
  char movingPiece = m.porigin;
  // Undo old peice positions (blanks will be ignored)
  key = key ^ getZobrist(m.porigin, m.origin[0], m.origin[1]);
  key = key ^ getZobrist(m.ptarget, m.target[0], m.target[1]);
  if(m.enPassantOccurred) {
    if(m.target[1]==5)
      key = key ^ getZobrist('p', m.target[0], 4);
    else if(m.target[1]==2)
      key = key ^ getZobrist('P', m.target[0], 3);
  }
  //Special treatment for castling
  if( (m.porigin == 'k') &&
      (m.origin[0] == 4 && m.origin[1] == 7))
  {
    if(m.target[0] == 2) {
      key = key ^ getZobrist('r', 3, 7);
      key = key ^ getZobrist('r', 0, 7); }
    else if(m.target[0] == 6) {
      key = key ^ getZobrist('r', 5, 7);
      key = key ^ getZobrist('r', 7, 7); }
  }
  if( (m.porigin == 'K') &&
      (m.origin[0] == 4 && m.origin[1] == 0))
  {
    if(m.target[0] == 2) {
      key = key ^ getZobrist('R', 3, 0);
      key = key ^ getZobrist('R', 0, 0); }
    else if(m.target[0] == 6) {
      key = key ^ getZobrist('R', 5, 0);
      key = key ^ getZobrist('R', 7, 0); }
  }
  //Special treatment for promotions
  if(m.porigin == 'P' && m.target[1] == 7)
    switch(m.promotion){
    case 'q': movingPiece='Q'; break;
    case 'r': movingPiece='R'; break;
    case 'b': movingPiece='B'; break;
    case 'n': movingPiece='N'; break;
    default: movingPiece = 'Q';
    }
  if(m.porigin == 'p' && m.target[1] == 0)
    switch(m.promotion){
    case 'q': movingPiece='q'; break;
    case 'r': movingPiece='r'; break;
    case 'b': movingPiece='b'; break;
    case 'n': movingPiece='n'; break;
    default: movingPiece = 'q';
    }
  // Set new peice position (origin is always blank, thus ignored)
  key = key ^ getZobrist(movingPiece, m.target[0], m.target[1]);
  // Side to move always changes, so set that
  key = key ^ zobristColor;
  // Check to see if the castle availability just changed
  for(i=0;i<4;i++)
    if(m.castleChanged[i])
      key = key ^ zobristCastle[i];
  return key;
}

char sideToPlay(bool turn, char player)
{
  if( (turn == 1 && player == 'W' ) ||
      (turn == -1 && player == 'B')
  )
    return 'W';
  return 'B';
}

void recordHash(int caller, U64 key, int depth, int hashf, char player, int value, bool singular, move *best)
{
    HASHE * entry;
    int index = HASHSIZE & key;
    if(best != NULL)
      if(best->enPassantOccurred == TRUE)
        return;
    entry = & transposition[index];
    if(entry->key == key) //don't overwrite mates (w/ full key match)
      if(entry->value == HASHMATE || entry->value == -HASHMATE) {
        if(best != NULL && value == entry->value)
          entry->bestmovesig = makeCompactMove(*best);
        return;
      }
    entry->key = key;
    entry->depth = depth;
    entry->flags = hashf;
    entry->singular = singular;
    entry->caller = caller;
    if(value == ILLEGAL) {
      entry->value = value;
      entry->bestmovesig = UNKNOWN;
      return;
    }
    if(value >= HASHMATE) {
      value = HASHMATE;
      entry->depth = INFINITY;
    }
    else if(value <= -HASHMATE) {
      value = -HASHMATE;
      entry->depth = INFINITY;
    }
    if(player == 'B')
      value = -value;
    entry->value = value;
    if(best == NULL)
      entry->bestmovesig = UNKNOWN;
    else
      entry->bestmovesig = makeCompactMove(*best);
}

int probeHash(int depth, int alpha, int beta, U64 key, char player, bool *singular, compactmove *bestmove)
{
    int index = HASHSIZE & key;
    HASHE * entry = &transposition[index];
    if (entry->key == key) {
while(TRUST_HASH) {
        int val = entry->value;
        int flag = entry->flags;
        if (val == ILLEGAL)
          return val;
        if(player == 'B')
          val = -val;
        if(val == HASHMATE) {
          if(val > beta && flag != hashfALPHA)
            return HASHMATE;
          else
            break; }
        if(val == -HASHMATE) {
          if(val < alpha && flag != hashfBETA)
            return -HASHMATE;
          else
            break; }
        if (entry->depth >= depth)
          switch(flag) {
          case hashfBETA: if(val > beta)
                            return val;
                          else
                            break;
          case hashfALPHA: if(!(val < alpha))
                             break;
          case hashfEXACT: return val;
          }
        break;
}
        if(bestmove != NULL)
        {
          *bestmove = entry->bestmovesig;
          if(singular != NULL && entry->singular == TRUE)
            *singular = TRUE;
        }
    }
    return UNKNOWN;
}

// *** Start of section for Move Vectors ***
// Move Vectors can be single squares or rays (linked list)

MOVEVECTOR allocMoveVector(void)
{
  MOVEVECTOR newvector;
  newvector =(MOVEVECTOR) malloc(sizeof(struct movevectortype));
  newvector->index = 0;
  newvector->next = NULL;
  return newvector;
}

void addCoordinatesToRay(MOVEVECTOR vector, int origin[], int target[])
{
  coordinates coord;
  coord.origin[0] = origin[0];
  coord.origin[1] = origin[1];
  coord.target[0] = target[0];
  coord.target[1] = target[1];
  vector->ray[vector->index++] = coord;
}

MOVEVECTOR addVectorToRootVector(MOVEVECTOR newvector, MOVEVECTOR rootvector)
{
  //It is legal to pass this function a null rootvector, in which case the newvector becomes the root
  //Therefore if you are unsure whether rootvector is null, you should call this function with:
  // rootvector = addVectorToRootVector(a, rootvector);
  if(rootvector == NULL)
    return newvector;
  if(rootvector->next == NULL)
  {
    rootvector->next = newvector;
    return rootvector;
  }
  addVectorToRootVector(newvector, rootvector->next);
  return rootvector;
}

void buildMoveVectors(void)
{
  int origin[2];
  int i, j;
  {
   //Init the masterVectorList to NULL
   int m, n;
   for(m=0;m<7;m++)
     for(n=0;n<64;n++)
     {
       mastervectorlist[m][n] = NULL;
       capturevectorlist[m][n] = NULL;
     }
  }
  for(i=0;i<8;i++)
    for(j=0;j<8;j++)
    {
      int square = 8 * i + j;
      origin[0] = i;
      origin[1] = j;
      mastervectorlist[0][square] = buildVectorp(origin);
      mastervectorlist[1][square] = buildVectorP(origin);
      mastervectorlist[2][square] = buildVectorKNight(origin);
      mastervectorlist[3][square] = buildVectorBishop(origin);
      mastervectorlist[4][square] = buildVectorRook(origin);
      mastervectorlist[5][square] = buildVectorQueen(origin);
      mastervectorlist[6][square] = buildVectorKing(origin);
      capturevectorlist[0][square] = buildVectorCapturep(origin);
      capturevectorlist[1][square] = buildVectorCaptureP(origin);
      capturevectorlist[2][square] = buildVectorKNight(origin);
      capturevectorlist[3][square] = buildVectorBishop(origin);
      capturevectorlist[4][square] = buildVectorRook(origin);
      capturevectorlist[5][square] = buildVectorQueen(origin);
      capturevectorlist[6][square] = buildVectorCaptureKing(origin);
    }
}

MOVEVECTOR getMoveVector(char piece, int file, int rank)
{
  int index, square = 8 * file + rank;
  switch(piece){
  case 'K':
  case 'k': index = 6; break;
  case 'Q':
  case 'q': index = 5; break;
  case 'R':
  case 'r': index = 4; break;
  case 'B':
  case 'b': index = 3; break;
  case 'N':
  case 'n': index = 2; break;
  case 'P': index = 1; break;
  case 'p': index = 0; break;
  case '-': return NULL;
  default: return NULL;
  }
  return mastervectorlist[index][square];
}

MOVEVECTOR getMoveVectorCapture(char piece, int file, int rank)
{
  int index, square;
  switch(piece){
  case 'p': index = 0; break;
  case 'P': index = 1; break;
  case 'N':
  case 'n': index = 2; break;
  case 'B':
  case 'b': index = 3; break;
  case 'R':
  case 'r': index = 4; break;
  case 'Q':
  case 'q': index = 5; break;
  case 'K':
  case 'k': index = 6; break;
  case '-': return NULL;
  default: return NULL;
  }
  square = 8 * file + rank;
  return capturevectorlist[index][square];
}

// Begin subsection(of Move Vectors) for validity checking
// These functions build a vector list of valid target squares for a given piece
// They do not determine legality of a move in the context of a game.

bool targetInbounds(int target[])
{
  if(target[0] >= 0 && target[0] <= 7 && target[1] >= 0 && target[1] <= 7)
    return TRUE;
  return FALSE;
}

MOVEVECTOR buildSingleSquare(MOVEVECTOR rootvector, int origin[], int achange, int nchange)
{
  //This function is for Knights and Kings, which have limited ranges
  //This function takes the rootvector, and passes it back.
  //It may or may not have a new Vector tacked on.
  int target[2];
  target[0] = origin[0] + achange;
  target[1] = origin[1] + nchange;
  if(targetInbounds(target))
  {
    MOVEVECTOR newvector = allocMoveVector();
    addCoordinatesToRay(newvector, origin, target);
    rootvector = addVectorToRootVector(newvector, rootvector);
  }
  return rootvector;
}

MOVEVECTOR buildSingleRay(MOVEVECTOR rootvector, int origin[], int achange, int nchange)
{
  //This function is for Bishops, Rooks, and Queens which move in full length rays.
  //This function takes the rootvector, and passes it back.
  //It may or may not have a new Vector tacked on.
  MOVEVECTOR newvector;
  int target[2];
  target[0] = origin[0] + achange;
  target[1] = origin[1] + nchange;
  if(! targetInbounds(target))
    return rootvector;
  newvector = allocMoveVector();
  addCoordinatesToRay(newvector, origin, target);
  rootvector = addVectorToRootVector(newvector, rootvector);
  target[0] = target[0] + achange;
  target[1] = target[1] + nchange;
  while(targetInbounds(target))
  {
    addCoordinatesToRay(newvector, origin, target);
    target[0] = target[0] + achange;
    target[1] = target[1] + nchange;
  }
  return rootvector;
}

MOVEVECTOR buildVectorp(int origin[])
{
  MOVEVECTOR rootvector;
  int target[2] = {UNKNOWN, UNKNOWN};
  if(origin[1] == 7 || origin[1] == 0)
    return NULL; //Pawns cannot stand on the 1st or 8th rank.
  rootvector = allocMoveVector();
  ta