
//
// This file contains the main search functions, (ID, the AB search, the Q search)
//
// ----------------------------
//
// Generate all the pseudo-legal moves for color. If in check, generate legal moves
// Sort: previous/predicted bestmoves first.
// 
// ----------------------------
int inline GenerateAndSortMoves (  const int color, const int ahead, const short alpha, const short beta, int &bestmove )
{
if (color == WHITE) 
		{if ( (MATE-ahead) <= alpha) return alpha; // we already know white can mate sooner (value can't be > alpha)
         if (MoveStack[ahead].ischeck==0) FindMovesWhite(SearchBoard, MoveStack[ahead]);
			else InCheckMoveGenW ( SearchBoard, MoveStack[ahead]);
        }
     else  {
         	if ( (-MATE+ahead) >= beta) return beta; // (value can't be < beta)
            if (MoveStack[ahead].ischeck==0) FindMovesBlack(SearchBoard, MoveStack[ahead]);
				else InCheckMoveGenB ( SearchBoard, MoveStack[ahead]);
           }

// In Check, discard illegal moves
if (MoveStack[ahead].ischeck!=0) 
	{
	if ((MoveStack[ahead].nummoves + MoveStack[ahead].numAttackmoves) == 0) // 0 moves == CheckMate
		{
		PV[ahead-1][1] = 255; PV[ahead-1][0] = 1; // Add mate to PV
		return (color == WHITE) ? (-MATE+ahead) : (MATE-ahead);
		}
	AddMoves (MoveStack[ahead], bestmove);
	return 0;
	}

// Sort Attacks by MVVLVA, put Hash move first and Killer move after the attacks.
SortAttacks ( MoveStack[ahead], SearchBoard );
AddUnderPromos ( MoveStack[ahead], SearchBoard );
SortMoveList (bestmove, MoveStack[ahead], KillerMoves[ahead]);
return 0;
}

// ----------------
// Set HashValue and info displaying globals
// ----------------
// Called before each iteration
void InitIterationGlobals ( SBoard &Board )
{
	 SearchBoard = Board;

	 // Calculate initial hash values
	 SearchBoard.HashKey  = Hash_Board (SearchBoard);
     SearchBoard.HashCheck = Hash_Board2 (SearchBoard);
	 SearchBoard.PawnHash = Pawn_HashBoard ( SearchBoard );

	 // Maximum depth, the fullwidth search will kick out after this depth no matter what.
	 g_MaxDepth = 3*SearchDepth + 6;
	 if ( (g_MaxDepth%2) == 0) g_MaxDepth++;

	 if (g_MaxDepth >= MAXDEPTH -3) g_MaxDepth = MAXDEPTH-4;

	 // Set Move Stack Checking Square variable
	 MoveStack [0].numAttackmoves = 0;
	 SetIsCheck ( MoveStack[0], Board);

	 // More Move Stack
	 MoveStack[ 0 ].extended = 0;
	 MoveStack[ 0 ].recap = NO_EXT;
	 MoveStack[ 1 ].eChecks = 2;

	 // To time how long the first move takes at this depth
	 if (SearchDepth > 4) MoveTm = clock ();
	 g_nFail = 0;
	 CurrentMoveNum = 1;
	 g_bPanic = FALSE;
}

// Called before each search
void InitSearchGlobals ( SBoard &Board )
	{
	 g_nNoChange = 0;
	 g_fTimeDisplay = 0;
	 g_ucAge++;

	 g_bDoNull = TRUE;
	 if (Board.nBPawns == 0 && Board.nWPawns == 0 && (Board.nWP == 0 || Board.nBP==0) ) g_bDoNull = FALSE;
	 if (bDoNull == FALSE) g_bDoNull = FALSE;

	 for (int i = 0; i < MAXDEPTH; i++) KillerMoves[i] = NO_BEST;

	 DRAWSCORE = 0;
	 SBoard TempBoard;
	 Setup_StartBoard (TempBoard, 0);
	 if (Board.GameTime < 60 && memcmp ( &TempBoard, &g_StartBoard, sizeof (SBoard)) == 0 ) DRAWSCORE = -20;
	 if ((Board.GameTime > 120 && Board.nWP < 3 && Board.nBP < 3) || (Board.nWP <2 && Board.nBP < 2) ) DRAWSCORE = 28;
	 if (Board.SideToMove == BLACK) DRAWSCORE *=-1;
	}

/* ===============================================================
 *  Check if Eval has dropped almost a pawn or more (nMargin) since last iteration
  ================================================================ */
int g_nPanicMargin = 0;

int IsPanic ( int CurrentEval )
{
  if (abs(CurrentEval) < 19000) // This just means we have a value (NOVALUE constant is outside this range.)
	{
	int nMargin = 80/2;
	if ( abs (g_lasteval) < 300) nMargin = 50/2;

	if ( GameBoard.SideToMove == WHITE && g_lasteval > -800 && CurrentEval < 550 && CurrentEval < (g_lasteval-nMargin) ) 
		{
		g_nPanicMargin = abs(g_lasteval-CurrentEval); 
		if (CurrentEval < g_lasteval-nMargin*2) g_bPanic = 1; else g_bPanic = 2;
		return TRUE;
		}
	if ( GameBoard.SideToMove == BLACK && g_lasteval < 800 && CurrentEval > -550 && CurrentEval > (g_lasteval+nMargin))
		{
		 g_nPanicMargin = abs(g_lasteval+CurrentEval); 
		 if (CurrentEval > g_lasteval+nMargin*2) g_bPanic = 1; else g_bPanic = 2;
		 return TRUE;
		}
	}
  return FALSE;
}


// On a ponder hit, extend thinking time a bit
void ExtendThinkTime ( )
{
  endtime = clock ();
  Thinktime += float(endtime - starttime) / (CLOCKS_PER_SEC * 3);
}

/* ===============================================================
 *
 * Computer Move
 * have the computer do a search to find its move, then perform the move on Board
 *
 ================================================================ */
int CompMove (SBoard& Board, int nFlags, int MaxAhead)
        {
        unsigned char  Ocolor;
        int Eval, nBestMove, nTime;
		int u1, u2;
		int bTimeUp = TRUE, bTimeExtended = FALSE;
		g_LastBest = 0;
        
        nodes = 0;   
		nodes2 = nodes + 25000;
		g_lasteval = 0; g_fMoveTm = 0.0f;
		if (nFlags == 1) g_bAnalyze = TRUE; else g_bAnalyze = FALSE;
              
        upgrade = WQUEEN; // pawn promotion
        stopthinking = 0; // Changes to stop the search.
        
        SearchBoard = Board;

        starttime = clock();
		Ocolor = Board.SideToMove;
		g_SearchColor = Board.SideToMove;

		SetEvent ( hEngineReady ); // Started thinking, can receive more commands.

		// Check in the Opening book for first 70 half-moves
        if (g_bAnalyze==FALSE && Board.GameTime < 70 && (g_lasteval = pNewBook->DoMove (SearchBoard, nBestMove)) != NOVAL) 
			{
			g_lasteval *= 10;
			SearchDepth = 1;
			PV[ 0 ][1] = nBestMove;
			PV[ 0 ][0] = 1;
			}
        else	// Do an Alpha-Beta Search
           {	 g_lasteval = 0;
                 Eval = 0;
				 SearchDepth = 1;
                 nBestMove = NO_BEST;
               	 ClearHistory ( );
				 InitSearchGlobals ( Board );
				 InitIterationGlobals ( Board );
				 GenerateAndSortMoves ( Ocolor, 1, -MATE, MATE, nBestMove  );
				 // -----  Iterative Deepening -----------------------
                 while ( SearchDepth <= MaxAhead)
                      {
						InitIterationGlobals ( Board );
					 	MoveToFront ( nBestMove, MoveStack[1], SearchDepth );
						// Aspiration Search
						Eval = ABSearch (Ocolor, 0, SearchDepth, -9998 + SearchDepth, 9998 - SearchDepth, nBestMove, TRUE);

 						if (g_bWinBoard == TRUE && (SearchDepth >3 || abs(Eval) >= (9997 - SearchDepth - 1)) && Eval!=TIMEOUT) 
							{
							nTime = (100*(clock() - starttime))/( CLOCKS_PER_SEC );
							CurrentMove = nBestMove;
							CurrentMoveNum = 1;
							wbSendThinking (SearchDepth, Eval, nTime, nodes, TRUE, FALSE, TRUE);
							}
						if (Eval != TIMEOUT) // Store this move in the hash
							{
							int nHashKey = SearchBoard.HashKey ^ HashFunction[SearchBoard.EnPassant] ^ HashFunction[SearchBoard.WCastle + (SearchBoard.BCastle<<3)];
							TT_Store ( SearchBoard.HashCheck, TranspositionTable [ nHashKey & g_nHashSize ], Eval, nBestMove, -9998 + SearchDepth, 9998 - SearchDepth,  0, SearchDepth);
							}

						// ----------------------
						// TIME CONTROL STUFF
						// ----------------------
						SearchDepth++;
                        if (Eval == TIMEOUT) 
							{
							if (CurrentMoveNum==1) SearchDepth--; // Didn't finish any searching this depth before time up
							break;
							}
						float fTimeTaken = float(clock() - starttime)/( CLOCKS_PER_SEC );

						// Extend thinking time if we experienced a big drop recently
						if ( g_bPanic==1 && g_nPanicMargin >= 85 && fTimeTaken > Thinktime * .33f && !bTimeExtended )
							{Thinktime += fPanicTime * .6f;
							 fPanicTime -= fPanicTime * .6f;
							 bTimeExtended = TRUE;
							}

						// Extend thinking time if we experienced big fail-high eval increase
						if ( abs (g_lasteval-Eval) >= 95 && abs(g_lasteval) < 400 && fTimeTaken > Thinktime * .27f && !bTimeExtended )
							{Thinktime += fPanicTime * .4f;
							 fPanicTime -= fPanicTime * .4f;
							 bTimeExtended = TRUE;
							}

						g_lasteval = Eval;			
						if ( abs(Eval) >= (9997 - SearchDepth)) break; // CheckMate, don't search further

						if ( SearchDepth >4 && g_ponder == 0)
							{
							// only 1 move, just do it.
							if ( MoveStack[1].nummoves == 1 && nFlags !=1) break; 

							// Stop now if very likely won't finish searching first move on next depth anyway
							if ( (Thinktime - fTimeTaken) < (g_fMoveTm * 1.22f)) 
								{
								break;
								}
							// Stop search quicker if this move is a recap, and best move has been steady
							if ( MDst (nBestMove) == g_RecapSquare && PieceValues [ SearchBoard.Sq [ MDst (nBestMove) ]&7 ] > 200 
								&& g_nNoChange >= 4	&& g_bPanic!=1 && fTimeTaken > (Thinktime *.20f) )
								break; 
							}
						g_nNoChange++;
						// ----------------------
                       }
				 if (SearchDepth > MaxAhead || (g_nMaxNodes !=0 && nodes > g_nMaxNodes) ) bTimeUp = FALSE;
				 // ---------------------------------------------------

				if (abs(CurrentEval) < MATE) g_lasteval = CurrentEval;
				if (stopthinking == 3) {return 0;}
				SearchBoard = Board;
				
				if (nBestMove != NO_BEST && nFlags!=1) // Do the Best Move Found
					{
					if (abs( g_lasteval) < (MATE-1) && (nFlags == 0 || (nFlags==2 && g_ponder==2)) ) 
						{
						 // Add move to transcript then do it.
						 upgrade = MPromo ( nBestMove );
						 AddTranscript (NULL, nBestMove,  SearchBoard);
						 Do_Move(SearchBoard, nBestMove, u1, u2, upgrade);
						 g_GameResult = NONE;
						}
					}
           }
		endtime = clock();
            
        if ((nFlags == 0 || (nFlags==2 && g_ponder==2))) 
				{
				ResetEvent ( hEngineReady ); // Finish everything related to this move before processing more engine input
				nTime = (100*(clock() - starttime))/( CLOCKS_PER_SEC );
				wbSendThinking (SearchDepth - 1, g_lasteval, nTime, nodes, TRUE, FALSE, FALSE);
				Board = SearchBoard;
				wbSendMove ( );
				if (g_GameResult == NONE) ResignOrDraw ( g_lasteval, Ocolor );
				wbTestSendResult ( Board );
				return g_lasteval;
				}
	
        return g_lasteval;
        }
				
// ------------------------
// QSearch Helper to evade checks
// part of the qsearch alpha beta
// ------------------------
int QuiesceBoard( int color, int alpha, int beta, int ahead, int depth);

int inline CheckEvade ( const int &color, int &alpha, int &beta, const int &ahead, const int &depth)
{
	int u1, u2, Value;
	int nLimit = 51+MoveStack[ahead].nummoves;
	int i = 1;
	if (i > MoveStack[ahead].numAttackmoves) { i=51;}

	// Mates
	if ((MoveStack[ahead].numAttackmoves + MoveStack[ahead].nummoves) == 0) 
		{PV[ahead-1][1] = 255; PV[ahead-1][0] = 1; return (-MATE+ahead);}

	Copy_Board2 (BoardStack[ahead], SearchBoard);

	while ( i < nLimit)
		{
		int MMove = MoveStack[ahead].Moves[i];
		MoveStack[ahead+1].ischeck = CheckingMove (color, SearchBoard, MMove );
		Do_Move(SearchBoard, MMove , u1, u2, WQUEEN); 

		Value = -QuiesceBoard( color^3, -beta, -alpha, ahead+1, depth+1);

		Undo_Move (SearchBoard, BoardStack[ahead], u1, u2);

		if ( Value >= beta) {return beta;}
		if ( Value > alpha) 
			{alpha = Value;
			AddPV ( ahead, MMove, 0, 0, SearchBoard );
			}
		
		if (i == MoveStack[ahead].numAttackmoves) i=51; else i++;
		}
	return alpha;
}

const int WPawnRank[10] = { 0, 0, 0, 0, 0, 0, 85, PieceValues [WQUEEN]-PieceValues [WPAWN], 0, 0};
const int BPawnRank[10] = { 0, 0, PieceValues [WQUEEN]-PieceValues [WPAWN], 85, 0, 0, 0, 0, 0, 0};
// ------------------------
//  Quiescence Search  
//
//  Cycles through all attacks or pawn promos by color, does the move
//  returns best possible value for color
// ------------------------
int QuiesceBoard( int color, int alpha, int beta, int ahead, int depth)
{
int Value;
int MMove, u1, u2, nP, nNeededVal;

if (color == WHITE)		Value =  EvaluateBoard ( SearchBoard, alpha, beta );
				else	Value = -EvaluateBoard ( SearchBoard, -beta, -alpha );

if (ahead >= MAXDEPTH) return Value;

if (MoveStack[ahead].ischeck == 0)	
	{
	if ( Value >= beta) return Value;
	if (color==WHITE) 	FindAttackMovesWhite(SearchBoard, MoveStack[ahead] );
	else				FindAttackMovesBlack(SearchBoard, MoveStack[ahead] );
	}
else
	{
	if (color==WHITE)	InCheckMoveGenW ( SearchBoard, MoveStack[ahead] );
    else				InCheckMoveGenB ( SearchBoard, MoveStack[ahead] );

	if ((MoveStack[ahead].numAttackmoves + MoveStack[ahead].nummoves) < 3) 
		return CheckEvade (color, alpha, beta, ahead, depth);

	if (Value >= beta) return Value;
	}

 // Store no move for PV
 PV[ahead-1][1] = 254;
 PV[ahead-1][0] = 1;

 if (Value > alpha) alpha = Value;
 if (MoveStack[ahead].numAttackmoves == 0) return alpha; // No moves, return static eval

 SortAttacks ( MoveStack[ahead], SearchBoard);
 Copy_Board2 (BoardStack[ahead], SearchBoard);

 nNeededVal = (alpha-Value) - FUTILE_MARGIN;
 // If capturing to less than 2 pieces, don't do futility
 nP = (color == WHITE) ? SearchBoard.nBP : SearchBoard.nWP;
 if (nP == 2 && nNeededVal > 230) nNeededVal = 230;
 if (nP < 2) nNeededVal = 0;

 for (int i = 1; i <= MoveStack[ahead].numAttackmoves; i++)
	{
	MMove = MoveStack[ahead].Moves[i];
	nodes++;

	// Calculate material value gained
	Value = PieceValues[ (SearchBoard.Sq [ MDst (MMove) ]&7) ];

	//Pawn Promos
	if ( SearchBoard.Sq[ MSrc(MMove) ]==WPAWN) { Value+= WPawnRank [SQRANK [MSrc(MMove)]];} 
	if ( SearchBoard.Sq[ MSrc(MMove) ]==BPAWN) { Value+= BPawnRank [SQRANK [MSrc(MMove)]];}

	if (Value == 100 && Value < nNeededVal) continue;
	MoveStack[ahead+1].ischeck = CheckingMove (color, SearchBoard, MMove );

	// Futility -- Skip the move if material gained doesn't come close enough to the alpha-beta window 
	if (MoveStack[ahead+1].ischeck == 0 && Value < nNeededVal) continue;

	// Skip Illegal Moves
	if ( !MoveStack[ahead].ischeck ) // (InCheckGen generates only legal moves)
		{
		if (MPiece(MMove) == 15) {if ( IsAttacked ( SearchBoard, MDst(MMove), color) ) continue;}
			else if (DiscoveredCheck (color, SearchBoard, MMove) ) continue;
		}

	Do_Move(SearchBoard, MMove , u1, u2, WQUEEN); 
	Value = -QuiesceBoard( color^3, -beta, -alpha, ahead+1, depth+1);
	Undo_Move (SearchBoard, BoardStack[ahead], u1, u2);

	if ( Value >= beta) return Value;
	if ( Value > alpha) 
		{alpha = Value;
		 AddPV ( ahead, MMove, 0, MoveStack[ahead+1].ischeck, SearchBoard );
		}
 	}
 return alpha;
}

// -------------------------------------
// Queen is pinned to the king by a rook or bishop
// -------------------------------------
int inline QueenThreat ( unsigned char *pPieces, const int Piece, const int nDst, const int nSide )
{
register int nQueenSq = pPieces[14];
if (nQueenSq == CAPTURED) return 0;

int nDirec = acDirec [pPieces[15] + (nQueenSq<<7)];
if (nDirec != 0 )
	{
	int TempSq = pPieces[15] + nDirec;
	while (SearchBoard.Sq[TempSq] == EMPTY) TempSq+=nDirec;
	if (SearchBoard.Sq[TempSq] == (BQUEEN-nSide)) 
		{
		TempSq+=nDirec;
		while (SearchBoard.Sq [TempSq] == EMPTY) TempSq+=nDirec;
		if (DiagDir [ nDirec +12]) 
			{if ( SearchBoard.Sq[TempSq] == (WBISHOP+nSide)) return 1;}
		else
			{if ( SearchBoard.Sq[TempSq] == (WROOK+nSide)) return 1;}
		}
	}
return 0;
}

//
// Check for time up and display search info every 25,000 nodes 
//
int inline CheckTimeUp ()
{
endtime = clock ();
nodes2 = nodes + 25000;
if ( g_bPanic == 1 ) endtime-= (long)(CLOCKS_PER_SEC * (fPanicTime));
if ( g_bPanic == 2 ) endtime-= (long)(CLOCKS_PER_SEC * (fPanicTime * .20f));
if ( (g_ponder !=1 && (endtime - starttime > CLOCKS_PER_SEC * Thinktime)) ) return 1; 

return 0;
}
// ----------------
// Do Fractional Extensions
// ----------------
void inline DoExtensions (const int &depth, const int &ahead, const int &Ext, int &nextDepth, const int &dstSq)
{
	nextDepth = depth-1;
	int extended = MoveStack[ahead-1].extended;

	if ( Ext == KINGPAWNS && MoveStack[ahead-1].recap <= CAPTURE) // Extend 2 ply on transition to King and Pawns ending
		{
		if (ahead < 4) {nextDepth+=3;} else nextDepth+=2;
		}
	// Pawn Push or Checked Opponent
	else if ( Ext >= PAWNPUSH || MoveStack[ahead+1].ischeck )
			{
			extended+=PLY;
			}
	// Single Move in check
	else if (MoveStack[ahead].nummoves == 1) 
			{
			if (MDst(MoveStack[ahead].Moves[0]) == MoveStack[ahead].ischeck && MPiece (MoveStack[ahead].Moves[0]) == 15 ) 
				extended+=QUARTPLY; else extended+=THREEQUARTPLY;
			}
	else // Recapture
		if  (dstSq == MoveStack[ahead-1].recap) 
			{
			MoveStack[ahead].recap = NO_EXT; // Don't do 2 recaps in a row
			if (SearchBoard.nWP == 1 && SearchBoard.nBP == 1) extended += PLY; // recap to 1 piece ending
			else if (MoveStack[ahead].ischeck == 0)  extended += THREEQUARTPLY;
				else  extended += QUARTPLY;
			}
	else if (Ext == MATETHREAT )
			{
			extended += HALFPLY;
			}
	else if (MoveStack[ahead].nummoves <= 2) // 2 responses to check
			{
			extended += QUARTPLY;
			}
	// Increment depth if needed
	if (extended >= PLY) 
			{
			 extended -= PLY;
			 nextDepth++;
			}
	MoveStack[ahead].extended = extended;

	// Don't end a search after 2 replies to check, unless we extended past the depth left already
	// (and never stop after 1 reply...)
	if (nextDepth<1 && MoveStack[ahead].recap > RECAP) 
			 MoveStack[ahead+1].eChecks = 1; 
		else MoveStack[ahead+1].eChecks = 2;
}

// ==========================
// GAME TREE SEARCH
// searches to depth
// returns evaluation of the best move found, (the move itself is returned in bestmove)
// BLACK = MIN, WHITE = MAX
// uses SearchBoard as input Board
//
// ==========================
short ABSearch(int color, int ahead, int depth,  short alpha, short beta,  int &bestmove, int bAfterNull)
{
if (stopthinking > 0 || g_ponder == 3 ) return TIMEOUT;
if (g_nMaxNodes && nodes > g_nMaxNodes && SearchDepth > 1 && !g_bAnalyze)  return TIMEOUT;

// Check if search time is used up every 50,000 nodes
if (nodes > nodes2)
	if (CheckTimeUp () ) return TIMEOUT; 

int u1, u2, nHashKeyAndFlags, MMove;
int Max, i, Ext, nMat;
int nextbest, nextDepth;
int nSearched, bPV = FALSE;
short value;

ahead++;
// ------- Try Null Move ---------
if (bAfterNull != TRUE && depth > 2 &&  MoveStack[ahead].ischeck == 0  && g_bDoNull == TRUE)
{ nMat = (color == BLACK) ? SearchBoard.BMat - SearchBoard.nBPawns * 100 : SearchBoard.WMat - SearchBoard.nWPawns * 100;
  if ( nMat > 499 ) 
	{
	// If the static eval isn't crummy, try a null move
	value = EvaluateBoard ( SearchBoard, alpha-210, beta+210 );
	if ( ( (value+200) >= beta && color == WHITE) 
	 || ( (value-200) <= alpha && color == BLACK))
		{
		if (depth > 6 && nMat > 900) nextDepth = depth - 4;
							else  	 nextDepth = depth - 3;
		if (nextDepth < 2) nextDepth = 0;
		MoveStack[ahead+1].ischeck = 0;
		nextbest = NO_BEST;

		int nMoves = 100;
		if (depth>3 && nMat < 1000)
			{if (color == BLACK) 
				{FindMovesBlack(SearchBoard, MoveStack[ahead]);
				 nMoves = (MoveStack[ahead].numAttackmoves + MoveStack[ahead].nummoves);
				}
			else
				{FindMovesWhite(SearchBoard, MoveStack[ahead]);
				nMoves = (MoveStack[ahead].numAttackmoves + MoveStack[ahead].nummoves);
				}
			}
		if (nMoves >= 10)
			{
			BoardSwitchColor ( );
			nHashKeyAndFlags = SearchBoard.HashKey ^ HashFunction[SearchBoard.EnPassant] ^ HashFunction[SearchBoard.WCastle + (SearchBoard.BCastle<<3)];
			value = NOVALUE;
			short nBounds = (color == WHITE) ? beta-1 : alpha;
			TT_Lookup ( SearchBoard.HashCheck, TranspositionTable [ nHashKeyAndFlags & g_nHashSize ], value, nextbest, nBounds, nBounds+1, ahead, nextDepth, bPV);
			if (value == NOVALUE)
				{// ABSearch will search at least 1 ply even if depth is 0 or less
				value =  ABSearch (color^3, ahead, nextDepth, nBounds, nBounds+1, nextbest, TRUE );						
				}
			TT_Store ( SearchBoard.HashCheck, TranspositionTable [ nHashKeyAndFlags & g_nHashSize ], value, nextbest, nBounds, nBounds+1, ahead, nextDepth);
			BoardSwitchColor ( );

			if (value == TIMEOUT) return TIMEOUT;
			if (value >= beta && color == WHITE ) return beta;
			if (value <= alpha && color == BLACK) return alpha; 
			}
		}
	}
}
// --------------------------
// Internal iterative deepening to find a guess for the best move
if (bestmove == NO_BEST && depth >= 3) 
	{
	value = ABSearch( color , ahead-1, depth-2, alpha, beta,  bestmove, FALSE );
	if ( value == TIMEOUT) return TIMEOUT;
	}

// Set Opposite Color var  
Max = (color == WHITE) ? -19999 : 19999;

// Find possible moves if not at root
if (ahead > 1)
	{
	value = GenerateAndSortMoves ( color, ahead, alpha, beta, bestmove  );
	if (value !=0) return value;
	}

// Draw by 50 move rule (here because we have to check for mates first)
if ((SearchBoard.GameTime - SearchBoard.LastReversible) >= 100 ) 
	{PV[ahead-1][1] = 252; PV[ahead-1][0] = 1;return DRAWSCORE;}

// ---
if (color == BLACK && (ahead < 2 || BoardStack[ahead-1].MatVal > beta + 350) )  MoveStack[ahead].eChecks--;
if (color == WHITE && (ahead < 2 || BoardStack[ahead-1].MatVal < alpha - 350))  MoveStack[ahead].eChecks--;

// Save Undo Board & Hash Values
Copy_Board2 (BoardStack[ahead], SearchBoard);
AddRepBoard (SearchBoard.HashKey ^ HashFunction[SearchBoard.EnPassant] ^ HashFunction[SearchBoard.WCastle + (SearchBoard.BCastle<<3)], SearchBoard);

int numMoves = MoveStack[ahead].nummoves;

	// Cycle through the moves and evaluate them
    for (i = 0; i < numMoves; i++)
                 {
				 // Sort by History if Bestmove, captures, and killer all failed
				 if ( depth>1 && ahead<11 && i == MoveStack[ahead].numAttackmoves ) SortByHistory (MoveStack[ahead], color);

				 // At root, update info then check for fail-low
				 if ( ahead == 1 && i == 1 && depth > 5)
					{
					 UpdateDisplayInfo ( i, MMove, Max, bestmove);
					 IsPanic ( CurrentEval );
					}					

				 MMove = MoveStack[ahead].Moves[i];

				 // Is this a legal move? If not skip it
				 if (MoveStack[ahead].ischeck==0)
					{
					 if (MPiece(MMove) == 15) // Moved King?
						{if ( IsAttacked ( SearchBoard, MDst(MMove), color) ) continue;}
					 else if (DiscoveredCheck (color, SearchBoard, MMove) == 1 ) continue;						
					}

				 // The move is legal, so do it
				 MoveStack[ahead+1].ischeck = CheckingMove (color, SearchBoard, MMove  );
                 Ext = Do_Move(SearchBoard, MMove , u1, u2, MPromo (MMove) );
				 MoveStack[ahead].recap = Ext;
                 nodes++;

				 // Set globals for display info, send PV to winboard if it changes
                 if (ahead == 1 )  UpdateDisplayInfo ( i, MMove, Max, bestmove);
				                    
				 nSearched = 1;

				 // Check the board for Mate Threats if it's not one piece or less endgame
				 if (MoveStack[ahead+1].ischeck == 0 && (SearchBoard.nWP > 1 || SearchBoard.nBP > 1))
					{
					if (color == WHITE )
						{
						if (TouchMatesB (SearchBoard, depth)  ) {value = -MATE+ahead+2; nSearched = 4; nodes++;}
						if (Ext <= NO_EXT)
							{if (MoveStack[ahead-1].recap == MDst(MMove) && BoardStack[ahead].BPiece[14] == MDst(MMove) ) Ext = QUEENRECAP;
							 if (depth > 1 && TouchMatesW (SearchBoard, depth) ) Ext = MATETHREAT;
							}
						 if (depth == 1 || bAfterNull == TRUE || (MoveStack[ahead].ischeck != 0 && depth == 0))
							if (QueenThreat ( SearchBoard.BPiece, MPiece(MMove), MDst (MMove), 0) == 1 ) Ext = QUEENTHREAT;

						}
					else
						{
						if (TouchMatesW (SearchBoard, depth) ) {value = MATE-ahead-2; nSearched = 4; nodes++; }
						if (Ext <= NO_EXT)
							{if (MoveStack[ahead-1].recap == MDst(MMove) && BoardStack[ahead].WPiece[14] == MDst(MMove) ) Ext = QUEENRECAP;
							 if (depth > 1 && TouchMatesB (SearchBoard, depth)  ) Ext = MATETHREAT;
							}
						if (depth == 1 || bAfterNull == TRUE || (MoveStack[ahead].ischeck != 0 && depth == 0))
							if (QueenThreat ( SearchBoard.WPiece, MPiece(MMove), MDst (MMove), 8) == 1) Ext = QUEENTHREAT;
						}
					}

				 if (nSearched == 1)
				 {
			     // Update HashValues
                 HashUpdate (u1, u2, SearchBoard );
				 nHashKeyAndFlags = SearchBoard.HashKey ^ HashFunction[SearchBoard.EnPassant] ^ HashFunction[SearchBoard.WCastle + (SearchBoard.BCastle<<3)];

                 // Draw by repetition
				 int Reps = DrawByRepetition (nHashKeyAndFlags, SearchBoard);
                 if ( (Reps > 1 || (ahead > 2 && Reps > 0) ) 
					  || (MoveStack[ahead+1].ischeck == 0 && NoMatingMaterial ( SearchBoard)) ) 
					{
					 value = DRAWSCORE; nSearched = 2;
					}
                 // If there is no depth left in the search, and the opponent isn't in check, evaluate the board position
				 else if ( ( depth <= 1 && MoveStack[ahead+1].ischeck== 0 && Ext<=NO_EXT && MoveStack[ahead].nummoves > MoveStack[ahead].eChecks) || (ahead > g_MaxDepth ) )
                       {
					 	nSearched = 0;
						if ( color==WHITE && alpha > (MATE-100) ) value = alpha;
						else if ( color==BLACK && beta < (-MATE+100) ) value = beta;
						else 		
							{
							if (color == WHITE) value = -QuiesceBoard( color^3, -beta, -alpha, ahead+1, 0);
								else value = QuiesceBoard( color^3, alpha, beta, ahead+1, 0);
							}
						}

                  //Look ahead to all possible moves if search hasn't stopped yet
                  else { 
                        value = NOVALUE;
                        nextbest = NO_BEST;

						DoExtensions ( depth, ahead, Ext, nextDepth, MDst (MMove) );
							
						TT_Lookup ( SearchBoard.HashCheck, TranspositionTable [ nHashKeyAndFlags & g_nHashSize ], value, nextbest, alpha, beta, ahead, nextDepth, bPV);

                        if (value == NOVALUE) // No value found in TT
                                {
								if (bPV == TRUE) // Ugly looking PV search code.
									{
									if (color == WHITE) 
										{
										value = ABSearch( color^3 , ahead, nextDepth, alpha, alpha+1,  nextbest, FALSE ); 
										if (value > alpha && value!=TIMEOUT )  // Fail High
											{
											if (ahead == 1) { CurrentBest = MMove; g_nFail = 1; g_nNoChange = 0; 
															  AddPV ( MAXDEPTH, MMove, 1, MoveStack[ahead+1].ischeck, GameBoard );
															  if (SearchDepth > 3) wbSendThinking (SearchDepth, Max, (100*(clock() - starttime))/( CLOCKS_PER_SEC ), nodes, TRUE, TRUE, FALSE);}
											value = ABSearch( color^3 , ahead, nextDepth, alpha, beta,  nextbest, FALSE ); 
											if (value > alpha || value == TIMEOUT) {bestmove = MMove;} else if (ahead==1) {CurrentBest = bestmove;}
											}
										}
									else 
										{
										value = ABSearch( color^3 , ahead, nextDepth, beta-1, beta,  nextbest, FALSE ); 
										if (value < beta && value!=TIMEOUT ) 
											{
											if (ahead == 1) { CurrentBest = MMove; g_nFail = 1; g_nNoChange = 0; 
															  AddPV ( MAXDEPTH, MMove, 1, MoveStack[ahead+1].ischeck, GameBoard );
															  if (SearchDepth > 3) wbSendThinking (SearchDepth, Max, (100*(clock() - starttime))/( CLOCKS_PER_SEC ), nodes, TRUE, TRUE, FALSE);}
											value = ABSearch( color^3 , ahead, nextDepth, alpha, beta,  nextbest, FALSE );
											if (value < beta || value == TIMEOUT) {bestmove = MMove;} else if (ahead==1) {CurrentBest = bestmove;}
											}
										}
									}
								else
									{
									value = ABSearch( color^3 , ahead, nextDepth, alpha, beta,  nextbest, FALSE ); 
									}
                                if (value == TIMEOUT) return TIMEOUT; // Time limit reached, bail out
				
								TT_Store ( SearchBoard.HashCheck, TranspositionTable [ nHashKeyAndFlags & g_nHashSize ], value, nextbest, alpha, beta, ahead, nextDepth);
								nSearched = 0;
                               }

						// reduce a 2nd repetition to 7/8ths
						if (Reps == 1 && value != DRAWSCORE && abs(value)<9000 ) value = (value>>1) + (value>>2) + (value>>3); 
                       }
				 } // end if nSearched

			 // Restore Board & Hash Values
             Undo_Move (SearchBoard, BoardStack[ahead], u1, u2);

              // Keep Track of Best Move and Alpha-Beta Prune
             if (color == WHITE &&  value > Max) 
					{
                     Max = value;
                     bestmove = MMove;
					 
					 if (value >= beta || value == (MATE-ahead-1) ) 
						{
						 AddHistory ( bestmove, depth, ahead, WHITE);
						 if (ahead == 1) {CurrentEval = value;}
						 AddPV ( ahead, MMove, nSearched, MoveStack[ahead+1].ischeck, SearchBoard );
                         return value;
						}
                     if (value > alpha ) 
						{
						 AddPV ( ahead, MMove, nSearched, MoveStack[ahead+1].ischeck, SearchBoard );
						 bPV = TRUE;
						 alpha = value;
						}
					}	
              else if (color == BLACK &&  value < Max) 
                    {
                     Max = value;
                     bestmove = MMove;
                                                                          
					 if (value <= alpha || value == (-MATE+ahead+1 )  )  
						{
						 AddHistory ( bestmove, depth, ahead, BLACK); 
						 if (ahead == 1) {CurrentEval = value;}
						 AddPV ( ahead, MMove, nSearched, MoveStack[ahead+1].ischeck, SearchBoard );
						 return value;
						}
                     if (value < beta ) 
						{
	 					 AddPV ( ahead, MMove, nSearched, MoveStack[ahead+1].ischeck, SearchBoard  );
						 bPV = TRUE;
						 beta = value;
						 }
				    }
                 }

// ---------- Done going through all the moves (No alpha/beta cuts) ------------
if (ahead==1) {CurrentEval = Max;}
else // StaleMate? (No moves found)
    {
	if ( abs(Max) == 19999 ) return DRAWSCORE;
    }

AddHistory ( bestmove,  depth, ahead, color); 

return Max;
}

