/*
 SEARCH
 =================================================================
 depth - remaining
 alpha - lower bound, [best so far]
 beta - upper bound, [-best for xside]
 ntype - -1 0 +1
 flags -
 1 parent extended,
 2 line is reduced
 4 Do Null search
 8 IID search
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 */

#include "search.h"

int full_search(int depth, int alpha, int beta, int ntype, int flags)
{
	
	sMOVES *m;
	sMOVES *l;
	//sMOVES *k;
	
	int opti = MATE;
	int oflags = flags;
	int j, v = -MATE, legal = 0, ext, red;
	int node_type = FAIL_LOW;
	int best = -MATE;
	int hashmove = 0;
	int draft = 0;
	int etcmove = 1;
	int do_null = ((flags >> 2) & 1);
	int do_lmr = 0;
	int hashvalue;
	int threat = 0;
	//int onerep = 0;
	int bm = 0;
	int phase = 3;
	int k0, k1, k2;
	int nulldepth;
	sHASHENTRY *hentry = 0;
	
	int flag = 0;
	int moves_played = 0;
	
	
	assert(depth > 0);
	assert(depth < MAXPLY);
	assert(ntype >= -1);
	assert(ntype <= 1);
	//assert((ntype == 0 && beta > alpha+1) || (ntype != 0 && beta == alpha+1)); can fail
	assert(alpha < beta);
	assert(alpha >= -MATE);
	assert(alpha < MATE);
	assert(beta > -MATE);
	assert(beta <= MATE);
	assert(!inCheck(stm ^ 1));
	assert(!checkboard());
	
	++nodes;
	
	pvl[ply] = ply;
	
	mhs->threat &= IN_CHECK;
	
	mhs->nm_refutation = 0;
	
#ifndef FAST
	if (ply > sdepth)
		sdepth = ply;
#endif
	
	if (nodes > marker) {
		marker = nodes + TIMECHECK;
		if (_tick() > st) {
			stop_search = 1;
			return 0;
		}
		if (Bioskey()) {
			stop_search = 1;
			return 0;
		}
	}
	if (ply > MAXPLY - 3) {
		return beta;
	}
	
	phase = 2;
	
	nulldepth = depth - REDUCE;
	
	if ((flags & 8) == 0) {
		
#ifdef HASH
#ifndef FAST
		++probes;
#endif
		
		hentry = probe();
		if (hentry) {
			hashmove = hentry->best_move;
			
			if (hashmove)
				phase = 1;
			
			threat = (hentry->data >> 16) & ALL_THREATS;
			
			mhs->threat |= threat;
			
			hashvalue = hentry->value;
			if (hashvalue > MATE - MAXPLY)
				hashvalue -= ply;
			else if (hashvalue < -MATE + MAXPLY)
				hashvalue += ply;
			
			draft = (hentry->data & 63);
			
			if (draft >= depth) {
				
				switch ((hentry->data >> 6) & 3) {
					case NO_ENTRY:
						break;
						
					case FAIL_LOW: /* UPPER BOUND - -MATE < exact value <= hashvalue */
						
						if (hashvalue <= alpha && fifty < 99) {
							freshen(hentry);
							return hashvalue;
						}
						++fails;
						
						if (threat & NM_TRIED) {
							do_null = 0;
						}
						break;
						
					case EXACT_PV:
						
						if (hashvalue <= beta) {
							if (hashvalue >= alpha) {
								
#ifdef RETURNEXACT
								freshen(hentry);
								
								if (hentry->best_move) {
									pv[ply][ply].asint = hentry->best_move;
								}
								return hashvalue;
#else
								
#ifndef HASHQ
								if (depth == 1 && fifty < 99) {
									freshen(hentry);
									
									mhs->move.asint = hashmove;
									
									/*
									 if (v > MATE - MAXPLY) {
									 
									 if (mhs->move.data.type > CAQ) {
									 killer0[ply] = mhs->move.asint;
									 hbump(&mhs->move, depth);
									 }
									 } else if (mhs->move.data.type > CAQ) {
									 
									 hbump(&mhs->move, depth);
									 
									 if (mhs->move.asint != killer1[ply]) {
									 killer2[ply] = killer1[ply];
									 killer1[ply] = mhs->move.asint;
									 }
									 }
									 */
									
									return hashvalue;
								}
#endif
								if (threat & NM_TRIED) {
									do_null = 0;
								}
#endif
								
								
								
							} else {
								
								++fails;
							}
						} else {
							++fails;
						}
						
						
						
						
#ifdef RETURNEXACT
						return hashvalue;
#endif
						
						
						
						break;
						
					case FAIL_HIGH: /* LOWER BOUND */
						
						if (hashvalue >= beta && fifty < 99) {
							
#ifdef RETURNBOUNDS
							freshen(hentry);
							mhs->move.asint = hashmove;
							
							
#endif
							
							/*
							 if (v > MATE - MAXPLY) {
							 
							 if (mhs->move.data.type > CAQ) {
							 killer0[ply] = mhs->move.asint;
							 hbump(&mhs->move, depth);
							 }
							 } else if (mhs->move.data.type > CAQ) {
							 
							 hbump(&mhs->move, depth);
							 
							 if (mhs->move.asint != killer1[ply]) {
							 killer2[ply] = killer1[ply];
							 killer1[ply] = mhs->move.asint;
							 }
							 }
							 */
							
							return hashvalue;
							
							
						}
						
						++fails;
						
						break;
					default:
						printf("corrupt data in hash");
				}
				
				
			}
			/*
			 if searched to nulldepth and DID NOT FH, then niether should NM.
			 
			 *** below apply to MATE THREAT extension ***
			 PROBLEM: We didnt NM before, so threat is missed
			 PROBLEM: Or, mate might be deeper than NM saw before
			 
			 */
			else {
#ifndef FAST
				++shallow;
#endif
				
				if (draft >= nulldepth && do_null && (threat & NM_TRIED)) {
					ext = ((hentry->data >> 6) & 3);
					if (ext == FAIL_LOW || ext == EXACT_PV) {
						if (hashvalue < beta) {
							do_null = 0;
							
						}
					}
				}
			}
		}
#ifndef FAST
		else
			++misses;
#endif
#endif
		
		
		
		killer0[ply + 4] = 0;
		killer1[ply + 4] = 0;
		killer2[ply + 4] = 0;
		
		
		
		/*
		 Check for mate and One Reply extensions
		 
		 NB. if phase==1 we have PV move. so if legal .....
		 */
		
		if (mhs->threat & IN_CHECK) {
			gen();
			legal = 0;
			l = last_move[ply];
			m = last_move[ply - 1];
			j = beta;
			while (m < l) {
				if (pseudoev[128 + kingsq[stm] - m->move.data.dest] == 0) {
					--l;
					*m = *l;
					continue;
				}
				/*
				 if king is immobilized by own pieces and board,
				 single reply to check means less, than if king
				 has many otherwise pseudo legal moves. It means
				 the opponent has control of his squares! More pieces in play.
				 
				 Adjacent Q can rob king of 6 squares [if she is protected]
				 Rook 4 if protected [not check], 3 if check
				 bishop 3 if checking, 2 if not
				 Knight = 2
				 
				 If King has eg 7 pseudo moves, only a protected Q
				 or 2R or 3m could rob it of all but 1 move!
				 
				 if K is on edge, 2 pcs are required to rob of 2/3
				 */
				
				
				
				domove(&m->move);
				
				if (inCheck(stm ^ 1)) {
					unmove();
					--l;
					*m = *l;
					
					continue;
				}
				m->score -= fval[m->move.data.piece];
				
#ifdef ETC
				/*
				 Early Transposition Cut-off
				 If a move from this position, leads to a position who's upper bound is
				 hashed, AND -val >= beta
				 */
				
				if (draft < depth) { /* hashmove is from shallow search*/
					
					if (0 > j && ply > 3 && fifty > 7 && (fifty > 99 || rep3())) {
						j = 0;
						phase = 0;
						etcmove = m->move.asint;
					}
					
					hentry = probe();
					if (hentry) {
						if ((int)(hentry->data & 63) >= depth - 1) {
							ext = (hentry->data >> 6) & 3;
							if (ext) {
								
								if (ext < FAIL_HIGH) {
									
									hashvalue = -hentry->value;
									if (hashvalue > MATE - MAXPLY)
										hashvalue -= ply;
									else if (hashvalue < -MATE + MAXPLY)
										hashvalue += ply;
									
									if (hashvalue >= j) {
										j = hashvalue;
										etcmove = m->move.asint;
										phase = 0;
									}
								}
							}
						}
					}
				}
#endif
				unmove();
				
				++legal;
				++m;
			};
			
			last_move[ply] = l;
			
			
			if (legal == 0) {
				
				best = -MATE + ply;
				store(EXACT_PV, depth, best, 0, 0);
				return best;
			}
			if (fifty > 99) {
				return 0;
			}
#ifdef ONEREPLY
			
			if (legal == 1
				) {
				mhs->threat |= ONE_REPLY;
				threat |= ONE_REPLY;
				onerep = 1;
				
			}
#endif
			
		}
#ifdef MATEDISTPRUNE
		/*
		 CREDIT to Fabien Letouzey, the author of Fruit for this idea
		 
		 If not already mated[we're not. DW], the absolute bounds on this position are:
		 lower bound: MATED in 1 and upper bound: MATE in 1
		 if beta <= lower or alpha >= upper, search will certainly fail
		 also, we can adjust alpha up to lowerb and beta down to upperb
		 note: -MATE+ply == mated now. edit dw
		 But why is A so oft < WORST (or, B > best) ???
		 */
		
		v = -MATE + ply + 2;
		if (v > alpha) {
			if (v >= beta) {
				return v;
			}
			alpha = v;
		}
		v = MATE - ply - 1;
		if (v < beta) {
			if (v <= alpha) {
				return v;
			}
			beta = v;
		}
#endif
		
		
#ifdef NULLMOVE
		/*
		 NULL MOVE
		 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
		 depth nulldepth opponent
		 6 4 3
		 */
		(mhs + 1)->move.asint = 0;
		mhs->nm_refutation = 0;
		
		if (nulldepth > 0
			&& do_null
			&& (mhs->threat & IN_CHECK) == 0
			&& beta > -MATE + MAXPLY
			//&& alpha < MATE - MAXPLY
			&& (force[stm] > 3 /* || types[BB|stm] */)
			&& (fifty < 99 || beta > 0)
			) {
			
			
			{
				
				assert(!inCheck(stm));
				assert(!inCheck(stm^1));
				
				last_move[ply] = last_move[ply - 1];
				npush();
				stm ^= 1;
				++ply;
				
				mhs->threat &= (ALL_THREATS - IN_CHECK);
				
				key ^= zobrist[8][epsquare];
				
				key = ~key;
				
				epsquare = 0;
				
				fifty = 0;
				
				if (nulldepth > 1)
					v = -full_search(nulldepth - 1, -beta, -beta + 1, 1, 3);
				
				else {
					v = -squies(-beta, -beta + 1);
#ifndef QMATE
					if (v >= beta) {
						v = -full_search(1, -beta, -beta + 1, 1, 3);
					}
#endif
				}
				
				
				threat |= NM_TRIED;
				
				--ply;
				
				stm ^= 1;
				npop();
				
				if (stop_search)
					return 0;
				
#ifdef MATETHREAT
				
				/*
				 If depth remaining is sufficient for snm to actually affect a win
				 [w/ checks and single replies] then the mate-threat should
				 be discovered to be real without the extension
				 
				 when is 'mate-threat'
				 a. not as menacing
				 - very long mate .:. more to thwart with real move.
				 - involves >1 NM in line ???
				 
				 b. particularly menacing
				 - mated in 1
				 */
				
				if (v < -MATE + MAXPLY) {
					threat |= MATE_THREAT;
					mhs->threat |= MATE_THREAT;
					
				} else {
					threat &= (ALL_THREATS - MATE_THREAT);
					mhs->threat &= (ALL_THREATS - MATE_THREAT);
				}
#endif
				/*
				 we passed, and though it wasnt good for us, it wasnt great for them
				 either. 'almost' a fail high.
				 if position fails low. we research for ... what?
				 */
				
				
				if (v >= beta) {
					++red_null_fh;
					
					//if (v > MATE - MAXPLY)
					//        v = MATE - MAXPLY;
					store(FAIL_HIGH, depth, beta, 0, threat);
					
					
					
					return beta;
				}
				/*
				 When hard to refute NM, it may be hard to refute innocuous moves too ... Why?
				 Because the position is closed or drawish, and niether side can win ... even when
				 we skip turns
				 */
				/*
				 if(v > beta-5)
				 {
				 
				 
				 mhs->nm_refutation = 1;
				 if((mhs-1)->nm_refutation)
				 {
				 printf("*");
				 strong_nm = 1;
				 return alpha;
				 }
				 
				 
				 }
				 */
				
#ifdef RTD
				/*
				 Botvinnik-Markoff
				 
				 If NM loses badly now AND 2 ply earlier, to the same move
				 
				 Two ply earlier a loss was threatened, which still exists:
				 A. Are we 'hiding' it?
				 B. Scouting inferior moves?
				 
				 -Did we ignore it, by trying a pointless move? Or,
				 -Is a piece trapped?
				 
				 Additional limts may be necessary:
				 o same square
				 o immediate captures only
				 o same piece
				 
				 */
				
				if (v + 100 < alpha
					&& v > -MATE + MAXPLY
					
					) {
					mhs->nm_refutation = (mhs + 1)->move.asint;
					if ((mhs - 2)->nm_refutation == (mhs + 1)->move.asint) {
						mhs->threat |= REAL;
						threat |= REAL;
					}
				}
#endif
				
#ifdef ETD
				/*
				 Empty Threat Delay (horizon move detection)
				 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
				 If Null-Move(2) is refuted decisively by a move(3) made possible by move(1)
				 prior to NM, then move(1) is a THREAT [legitimate or empty] which ought
				 to be examined more closely for iether possibility:
				 
				 */
				if (v > -MATE + MAXPLY
					&& (mhs + 1)->move.asint
					&& (mhs + 1)->victim > WP
					) {
					
					threat |= EMPTY;
					mhs->threat |= EMPTY;
					
					
					
				} else {
					threat &= ALL_THREATS - EMPTY;
				}
				
#endif
			}
		}
#endif
		
		
		
		if (mhs->threat & IN_CHECK)
			l = last_move[ply];
		else { /* 5? slots for etc, hash, killer0 moves to hide in */
			l = last_move[ply - 1] + 5;
			last_move[ply] = l; /* artificial */
		}
		
		node_type = FAIL_LOW;
		bm = 0;
		legal = 0;
		
		
		
	} else { // end IID
		l = last_move[ply];
		phase = 3;
	}
	
	k0 = killer0[ply];
	k1 = killer1[ply];
	k2 = killer2[ply];
	
	
	
	for (m = last_move[ply - 1]; m < l; ++m) {
		
		switch (phase) {
			case 0: /* ETC */
				++phase;
				
				if (etcmove) { /* We ARE in check and moves HAVE been gen */
					if (next(m, etcmove))
						break;
				}
			case 1: /* Hash */
				++phase;
				
				if (hashmove && hashmove != etcmove) {
					if ((mhs->threat & IN_CHECK) || (oflags & 8)) {
						if (next(m, hashmove))
							break;
						
					} else {
						m->move.asint = hashmove;
						if (move_is_legal(&m->move))
							break;
					}
				}
			case 2: /* Mate Killer*/
				++phase;
				if (k0 && k0 != etcmove && k0 != hashmove) {
					if ((mhs->threat & IN_CHECK) || (oflags & 8)) {
						if (next(m, k0))
							break;
						
					} else {
						m->move.asint = k0;
						if (move_is_legal(&m->move))
							break;
						
					}
				}
			case 3:
				++phase;
				
				if (mhs->threat & IN_CHECK);
				else if (oflags & 8);
				else {
					gen();
					m = last_move[ply - 1];
					l = last_move[ply];
					
					
					if (etcmove && (etcmove = next(m, etcmove)))
						++m;
					if (hashmove && (hashmove = next(m, hashmove)))
						++m;
					if (k0 && (k0 = next(m, k0)))
						++m;
					
				}
#ifdef IID
				
				
				if (depth > 2
					
					&& etcmove == 0
					&& hashmove == 0
					&& k0 == 0
					&& ntype == 0
					/* && beta > alpha + 1 */
					) {
					
					assert(!inCheck(stm^1));
					
					v = full_search(depth - 2, alpha, beta, ntype, 8);
					if (stop_search)
						return 0;
					
					if (v >= beta) {
						v = full_search(depth - 2, alpha, MATE, ntype, 8);
					}
					if (stop_search)
						return 0;
					
					hashmove = pv[ply][ply].asint;
					if (hashmove && next(m, hashmove))
						break;
				}
#endif
				
				
			case 4: /* Prepare for futility [calc opti] and Tag Killers */
				++phase;
				
				if (k2 && k2 != hashmove && k2 != etcmove)
					tagpv(m, k2, 6300000);
				if (k1 && k1 != hashmove && k1 != etcmove)
					tagpv(m, k1, 6400000);
				
			case 5: /* Captures, Killers and 1st history*/
				sorthmvs(m);
				if (m->score < 6300000)
					++phase;
				//if (m->score < 5100000)
				//	do_lmr = ((mhs->threat & IN_CHECK) == 0);
				if (m->score < 5000000) {
					++phase;
					do_lmr = ( /* ntype != 0 && */ depth > LMR_DEPTH && (mhs->threat & IN_CHECK) == 0);
#ifdef FUTILITY
					
					if(mhs->threat & IN_CHECK);
					//else if(force[stm^1] < 5 && (types[BP|stm] || force[stm] > 3));
					//else if(ntype == 0);
					//else if(beta < -MATE + MAXPLY);
					//else if(alpha > MATE - MAXPLY);
					else if (depth == 1) {
						{
							/* positional gain of otherwise quiet move */
							if(ntype != 0)
							opti = evaluate() + max(6 * force[stm], 100 * (types[BP|stm] > 0));
						}
					}
#ifdef XFUTILITY
					else if (depth <= 3) {
						
						{
							/* positional gain of otherwise quiet move PLUS another*/
							opti = evaluate() + /* (depth-1) * */ max(12*force[stm],opti_cap(stm));
						}
					}
#endif
#endif
				}
				break;
				
			case 6: /* 2nd Capture / 1st History*/
				sorthmvs(m);
				//if (m->score < 5100000)
				//	do_lmr = ((mhs->threat & IN_CHECK) == 0);
				if (m->score < 5000000) {
					++phase;
					do_lmr = ( /* ntype != 0 && */ depth > LMR_DEPTH && (mhs->threat & IN_CHECK) == 0);
#ifdef FUTILITY
					
					if(mhs->threat & IN_CHECK);
					//else if(force[stm^1] < 5 && (types[BP|stm] || force[stm] > 3));
					//else if(ntype == 0);
					//else if(beta < -MATE + MAXPLY);
					//else if(alpha > MATE - MAXPLY);
					else if (depth == 1) {
						{
							/* positional gain of otherwise quiet move */
							if(ntype != 0)
							opti = evaluate() + max(6 * force[stm], 100 * (types[BP|stm] > 0));
						}
					}
#ifdef XFUTILITY
					else if (depth <= 3) {
						
						{
							/* positional gain of otherwise quiet move PLUS another*/
							opti = evaluate() + /* (depth-1) * */ max(12*force[stm], opti_cap(stm));
						}
					}
#endif
#endif
				}
				break;
				
			case 7: /* 2nd History*/
				++phase;
				
				sorthmvs(m);
				
				break;
				
			case 8: /* 3rd History */
				++phase;
				
				sorthmvs(m);
				
				break;
				
			case 9:
				++phase;
				
				sorthmvs(m);
				break;
				
			default:
				++phase;
				
				sorthmvs(m);
				
				break;
		}
		
		
		domove(&m->move);
		
		/*
		 if(m->move.data.type == NOM && depth == 1 && phase >= 4) {
		 v = -evaluate(-MATE, MATE)-opti;
		 if(v > most) {
		 printf("[[[%d]]]", v);
		 most = v;
		 }
		 }
		 */
		
		/* 
		 * If in check, legals were generated, otherwise we just need to weed out moves into check 
		 */
		if (((mhs - 1)->threat & IN_CHECK) == 0) {
			
			if (m->move.data.piece == (WK - stm)) {
				if (inCheck(stm ^ 1)) {
					phase -= (phase > 5);
					unmove();
					continue;
				}
			} else if (raytrace(m->move.data.from)) {
				phase -= (phase > 5);
				unmove();
				continue;
			}
		}
		
		++moves_played;
		
		ext = red = 0;
		
		flag = 0;
		
		flags = oflags;
		if ((fifty > 3 && ((ply > 4 && rep2()) || (fifty>7 && rep3()))) || (m->move.data.type < ENP && force[stm]<8 && isdrawn())) {
			ext = 1;
			red = 0;
			v = 0;
			++nodes;
		} else {
			/*
			 the only way this move could have checked is if:
			 from or dest is pseudo OR A CASTLE MOVE!!!
			 OR AN ENPASSANT!!!!!!!!!!!!!!!
			 */
			mhs->threat &= (ALL_THREATS - IN_CHECK);
			
			
			if (pseudoev[128 + kingsq[stm] - m->move.data.from] == 1
				|| pseudoev[128 + kingsq[stm] - m->move.data.dest] == 1
				|| (m->move.data.type == CAK && pseudoev[128 + kingsq[stm] - (m->move.data.dest - 1)] == 1)
				|| (m->move.data.type == CAQ && pseudoev[128 + kingsq[stm] - (m->move.data.dest + 1)] == 1)
				|| (m->move.data.type == ENP && pseudoev[128 + kingsq[stm] - (m->move.data.dest + (16 - (stm << 5)))] == 1)
				) {
				mhs->threat |= inCheck(stm);
			}
			/*
			 mhs->threat |= inCheck(stm);
			 */
			assert((mhs->threat & IN_CHECK) == inCheck(stm));
			
			if ((mhs->threat & IN_CHECK) == 0 && fifty>99) {
				v = 0;
				ext = 1;
				flags &= 12;
				
				++nodes;
				goto DRAWN;
			}
			
			
			/*
			 EXTENSIONS
			 
			 Seeker: Check, Pawn to 7th
			 
			 Mostly *Always* extend.
			 Unless it seems we are already WON! May work only for pawn27th.
			 
			 Threat: Mate, One reply
			 
			 If these fail low already, we need _NOT_ extend.
			 But if >alpha, we need to 'verify' with extended research
			 
			 Suspect: recap/ETD
			 
			 Extend PV alpha < v < beta. Ie parent node 'aproves' move
			 */
			
#ifdef CHECK
			if ((mhs->threat & IN_CHECK)
				) {
				++ext_check;
				ext = 1;
			}
#else
			if ((mhs->threat & IN_CHECK) && depth == 1) {
				++ext_check;
				ext = 1;
			}
#endif
			
			
			
#ifdef PAWN27TH
			if (passer_move(&m->move)
				) {
				++ext_pawn;
				ext = 1;
				
				
				
			}
#endif
			
#ifdef ENDGAME
			if ((mhs - 1)->victim > WP
				&& ntype == 0
				&& types[BP + stm] > 0
				&& (force[0] + force[1]) == 0
				
#ifdef LIMIT_END
				&& LIMIT_CHECK_2(depth, ply, idepth)
#endif
				) {
				ext = 1;
				++ext_end;
			}
#endif
			
			
			
			
			
			/*
			 Black threatened. It's Whites turn. White is searching a move. so, stm == Black.
			 Black is being investigated for ETD, so White will no longer be suspect.
			 If the ETD/Recap succeeds in hiding the 'win' we may fail low unless we extend
			 W==2(2^1) B==1(2^0) stm=suspect [after domove()]
			 */
			
#ifdef RECAPTURE
			
			if (m->move.data.type < CAK
				&& ntype == 0
				&& (mhs - 2)->move.data.dest == m->move.data.dest
				&& mval[(mhs - 1)->victim] == mval[(mhs - 2)->victim]
				) {
				ext = 1;
				++ext_recap;
				
			}
#endif
			
#ifdef ETD
			if ((threat & EMPTY)
				&& ntype == 0
				
				
				) {
				++ext_etd;
				ext = 1;
				/*
				 If BP has threatened WN, it may be a delay tactic; we extend.
				 But later [in PV], if WB threatens BR, we do not want to ext
				 Because it is unlikely that both sides are trying to delay.
				 */
				
			}
#endif
			
			
#ifdef LMR
			/*
			 * Late Move REDUCTION [NOT pruning]
			 */
			if (do_lmr
				//&& (depth > LMR_DEPTH)
				//&& do_lmr
				//&& ((oflags >> 2) & 1)  // parent NOT null-move
				&& m->move.data.type > CAQ
				//&& !big_potential_move(&m->move)
				&& ext == 0                                     
				
#ifndef PAWN27TH
				//&& !passer_move(&m->move)
#endif
				) {
				
				{
					flag = 1;
					red = LMR_RED;
					++red_nohist;
					
				}
			}
#endif
			
			
#ifdef FUTILITY
			/*
			 * FUTILITY PRUNING
			 * 
			 * Based upon eval PLUS estimate of move, 
			 * excepting special cases where opti may be underestimated: 
			 */
			
			if (depth == 1) {
				if (opti /* + mval[m->move.data.piece] */ < alpha
					&& ext == 0
					&& m->move.data.type > CAQ
					//&& ntype != 0
					//&& (v = opti) <= alpha
					//&& !big_potential_move(&m->move) // moves which defy a 50 point gain
					
					) {
#ifndef FAST
					++red_futile;
					
					
#endif
					flag = 1;
					red = 1;
					v = opti;// + mval[m->move.data.piece];
					goto DRAWN;
					
				}
			}
#endif
#ifdef XFUTILITY
			else if (depth <= 3
					 //&& phase > 6
					 && ext == 0
					 && m->move.data.type > CAQ
					 && opti < alpha
					 //&& opti + mval[m->move.data.piece] < alpha
					 //&& (v = opti) <= alpha
					 && !big_potential_move(&m->move)
					 
					 ) {
				
				red_xfutile += (depth == 2);
				red_razor += (depth == 3);
				flag = 1;
				red = depth-1;
				//v = opti;
				//goto DRAWN;
				
			}
#endif
			
			
			
//		RESEARCH:
			/* 
			 If a parent is scouting [ntype != 0; beta == alpha+1] and search FH
			 a. we reduced - maybe normal depth will not fail high
			 b. we did not reduce - NO research
			 */
			assert(!inCheck(stm^1));
			
#ifdef PVSs
			if (moves_played == 0) { /* FIRST MOVE */
				if (depth - red + ext > 1)
					v = -full_search(depth - red + ext - 1, -beta, -alpha, -ntype, 0 | ext);
				else
					v = -squies(-beta, -alpha);
				
				
			} else { /* ALL THE REST */
				
				if (depth - red + ext > 1)
					v = -full_search(depth - red + ext - 1, -(alpha+1), -alpha, 1, 4 | ext);
				else
					v = -squies(-(alpha+1), -alpha);
				
				/* re-search */
				if (!stop_search && v > alpha && (v < beta || red > 0)) {
					++researches;
					if (depth /* - red */ + ext > 1)
						v = -full_search(depth /* - red */ + ext - 1, -beta, -alpha, -ntype, 0 | ext);
					else
						v = -squies(-beta, -alpha);
				}
			}
#else
			if (depth - red + ext > 1)
				v = -full_search(depth - red + ext - 1, -beta, -alpha, -ntype, 4 | ext);
			else
				v = -squies(-beta, -alpha);
			
#endif
		}
		
		
		
	DRAWN:
		/*  200 for creating passer on 6th
		 if(flag)
		 {
		 if(v > alpha)
		 {
		 printf("\a}===> (%d) <==={\n", v-flag);
		 display();
		 }
		 }
		 //*/
		
		
		unmove();
		++moves_played;
		
#ifdef TRACE
		fprintf(trace, "\n");
#endif
		
		if (stop_search)
			return 0;
		
		
		if (v > best) {
			
			
			if (v > alpha) {
				
				//hbump(&m->move, depth+flag+(v<beta));
				
				if (v > MATE - MAXPLY) {
					
					{
						/* killer0[ply] = m->move.asint; */
						if (m->move.data.type > CAQ) {
							killer0[ply] = m->move.asint;
							
						}
					}
				} else { /* mate is forced, even if
						  * reduced or under threat */
					
					/*
					 * a move thought unworthy of normal
					 * consideration becomes best move
					 */
					
					
					/* THIS IS TAKEN CARE OF EARLIER!
					if (red) {
						red = 0;
						domove(&m->move);
						++researches;
						
						goto RESEARCH;
					}
					*/
					
					/* extend late move which turns up
					 * good else if(flag) { ++researches;
					 * domove(&m->move); ext = 1; flag =
					 * 0; goto RESEARCH; }
					 */
					
					/* && offender>2 */
					
					/*
					 if (ext == 0 && ((threat & (MATE_THREAT | REAL)) || onerep)) {
					 ext = 1;
					 ext_threat += ((threat & MATE_THREAT) > 0);
					 ext_real += ((threat & REAL) > 0);
					 --moves_played;
					 ext_1rep += onerep;
					 ++researches;
					 domove(&m->move);
					 goto RESEARCH;
					 }
					 */
					/*
					 if(flag2)
					 {
					 oalpha = v - opti-mval[mhs->victim];
					 if(oalpha > most[depth])
					 {
					 most[depth] = oalpha;
					 printf("[D=%d high=%d AB=%d %d]\n", depth, most[depth], alpha, beta);
					 }
					 }
					 */
					
				}
				
				
				if (v >= beta) {
					
					if (m->move.data.type > CAQ
						
						) {
						
						//if(v > beta + 50)
						hbump(&m->move, depth+flag);
						
						if (m->move.asint != killer1[ply]) {
							killer2[ply] = killer1[ply];
							killer1[ply] = m->move.asint;
						}
					}
#ifndef FAST
					++fhn;
					fh1 += (int) (m == last_move[ply - 1]);
#endif
					store(FAIL_HIGH, depth, v, m->move.asint, threat);
					
					while(--m >= last_move[ply - 1])
						if(m->move.data.type > CAQ)
							htry(&m->move, depth+flag);
					
					
					return v;
				}
				alpha = v;
				node_type = EXACT_PV;
				if(m->move.data.type > CAQ) {
					hbump(&m->move, depth+flag);
					/*
					 k = m;
					 while(--k >= last_move[ply-1])
					 if(k->move.data.type > CAQ)
					 htry(&k->move, depth+flag);
					 //*/
				}
				
				/* update the PV */
				pv[ply][ply] = m->move;
				for (j = ply + 1; j < pvl[ply + 1]; ++j)
					pv[ply][j] = pv[ply + 1][j];
				pvl[ply] = pvl[ply + 1];
				
				
			} //else if (m->move.data.type > CAQ) htry(&m->move, depth+flag);
			best = v;
			bm = m->move.asint;
			
		}
		
		//if (m->move.data.type > CAQ) htry(&m->move, depth+flag);
		
		++legal;
		
		
		/*
		 Use IID to order moves by score of 3 ply search
		 In the event that the IID bm is NOT a cut or PV
		 
		 NOTE: good captures have 5m added
		 */
		
		/*
		 * if(v < alpha-50) { if(flags&8) {
		 * 
		 * {
		 * m->score = v + (v+50>alpha && m->move.data.type < CAK) *
		 * 5000000; } } }
		 */
		
		
		if (ntype == 1)
			ntype = -1;
		
	};
	
	if (legal == 0) {
		assert((mhs->threat & IN_CHECK) == 0);
		return 0;
		best = 0;
		bm = 0;
		if (best >= beta)
			node_type = FAIL_HIGH;
		if (best > alpha)
			node_type = EXACT_PV;
	}
	
	/*
	 if (bm && node_type == EXACT_PV) {
	 best_move.asint = bm;
	 if (best_move.data.type > CAQ
	 
	 ) {
	 
	 hbump(&best_move, depth + flag);
	 
	 if (bm != killer1[ply]) {
	 killer2[ply] = killer1[ply];
	 killer1[ply] = bm;
	 }
	 }
	 }
	 */
	
	store(node_type, depth, best, (node_type == FAIL_LOW) ? 0 : bm, threat);
	
	
	/*
	 TEST evaluate() against score
	 
	 lots of back rank and rook+bishop type mates [also like back rank ... hmmm]
	 
	 Q. Why are there so many mated-in-n positions with 'won' material?
	 A. King safety is being hammered by 'MATERIAL'
	 */
	
	/*
	 if(best < -MATE+MAXPLY && beta > alpha+1 && ((mhs->threat & IN_CHECK) == 0))
	 {
	 v = evaluate(-MATE, MATE);
	 if(v > 500)
	 {
	 buildepd(ms);
	 fprintf(trace, "%d %d %d %d %s\n", MATE+best-ply, v, alpha, beta, ms);
	 }
	 }
	 */
	
	
	
	
	return best;
}
