#include "think.h"
#include <time.h>
/*
	compare cur_score to 'weighted' average of last 4 scores
*/
int 
trend (int cur_score)
{
	int             i, s;
	s = 0;
	for (i = 1; i < 5; ++i) {
		s += (5 - i) * scores[i - 1];
	}
	s /= 10;
	return (cur_score - s);
}

int think (int maxtime, int reserve, int maxdeep)
{
	int             r = 0, legal = 0, i, best = -MATE, best1 = -MATE,
	                best2 = -MATE;
	sMOVES         *m, *l, *bm;
	int             qm;
	int             lib = scores[0];
	UI64            bt = _tick ();
	sHASHENTRY     *hentry;
	int             bfc = 1;
	UI64            elapsed = 0;
	UI64            lit = 0;
	int             nodesb4;
	int             ext = 0;
	int             nt;
	int             easy;
	int             notbad;
	//int             lps = 0;
	//int             fishy = 0;
	
	rootphase = force[WHITE] + force[BLACK] + types[WP] + types[BP];
	
	bf = 2.0f;
	
	/*
		GEN and filter illegals could have been in xboard() or
		even outside in separate routine
	*/
	
	ply = 1;
	m = last_move[ply - 1];
	l = last_move[ply];
	
	assert(m == move_list);
	assert(l>=m);
	assert(!checkboard());
	
		
	legal = 0;
	while (m < l) {
		domove (&m->move);
		r = inCheck (stm^1);
		if (r) {
			--l;
			*m = *l;
			unmove ();
			continue;
		}
		m->score = -squies (-MATE, MATE);
		unmove ();
		++m;
		++legal;
	}
	last_move[ply] = l;
	
	if (legal == 0) {
		pv[1][1].asint = 0;
		return (inCheck (stm)) ? -MATE : 0;
	}
	
	rootalpha = -MATE;
	rootbeta = MATE;
	idepth = 2;
	easy = 0;
	nt = FAIL_LOW;
	
#ifdef HASH
	if (fifty < 2)
		agehash ();
	hentry = probe ();
	if (hentry) {
		nt = (hentry->data >> 6) & 3;
		if (tagpv (move_list, hentry->best_move, 9000000 + (hentry->data & 63) - (int) (nt != EXACT_PV))) {
			switch (nt) {
			case NO_ENTRY:
				break;
			case FAIL_LOW:
				break;
			case EXACT_PV:
				rootalpha = max (-MATE, hentry->value - RADIUS);
				rootbeta = min (MATE, hentry->value + RADIUS);
				lib = hentry->value;
				idepth = (hentry->data & 63);
				freshen (hentry);
				easy = 1;
				nt = EXACT_PV;
				break;
			case FAIL_HIGH:
				break;
			}
			if (abs (hentry->value) >= MATE - MAXPLY)
				idepth = 2;
			if (idepth < 2)
				idepth = 2;
		}
	}
#endif
	
	/*
	memset(killer0, 0, sizeof(killer0));
	memset(killer1, 0, sizeof(killer1));
	memset(killer2, 0, sizeof(killer2));
	*/
	/*
	memset(history, 0, sizeof(history));
	*/
	
	
	bubblemvs ();
	
	pv[1][1].asint = last_move[0]->move.asint;
	printf ("move=%d maxtime=%d reserve=%d idepth=%d\n", (int)((2 + mhs - move_history) / 2), maxtime, reserve, idepth);
	st = bt + maxtime;
	if (maxtime < 200)
		idepth = 1;
	
	evals = 1;
	nodes = 1;
	marker = TIMECHECK;
	qnodes = 1;
	sdepth = 1;
	qdepth = 1;
	fhn = 1;
	fh1 = 1;
	ext_recap = 0;
	ext_real = 0;
	ext_end = 0;
	ext_pawn = 0;
	ext_check = 0;
	ext_threat = 0;
	ext_1rep = 0;
	ext_etd = 0;
	probes = 1;
	misses = 1;
	shallow = 0;
	fails = 0;
	red_nohist = 0;
	red_null_fh = 0;
	red_futile = 0;
	red_xfutile = 0;
	red_delta = 0;
	red_razor = 0;
	researches = 0;
	stop_search = 0;
	
	/* Main iteration loop */
	
	while (idepth <= maxdeep) {
		best1 = -MATE;
		best2 = -MATE;
		
#ifndef ASPIRATION
		rootalpha = -MATE;
		rootbeta = MATE;
#endif
		
		best = rootalpha;
		pvl[1] = 1;
		m = last_move[ply - 1];
		bm = m;
		notbad = 0;
		qm = 0;
		for (; m < last_move[ply]; m++) {
			sortmvs (m);
			if (console) {
				printf ("%2d %5d %6d %8d ", idepth, best, (int) ((elapsed) / 10), nodes);
				printmv (&m->move);
				printf ("  \t(%2d/%2d)        \r", (int)(m - last_move[0] + 1), (int)(last_move[1] - last_move[0]));
			}
			/*
			else
			{
				printf("stat01: %d %d %d %d %d ", (int)((elapsed)/10), nodes, idepth, last_move[1]-m-1, last_move[1]-last_move[0]);
				printmv(&m->move);
				printf("\n");
				fflush(stdout);
			}
			*/
			
			domove (&m->move);
			
			qm += (m->move.data.type > ENP);
			
			nodesb4 = nodes;
			
			if (fifty > 7 && rep3 ()) {
				r = 0;
				++nodes;
			} else {
				ext = inCheck (stm);
				mhs->threat = (mhs->threat & (ALL_THREATS - IN_CHECK)) | ext;
#ifndef CHECK
				ext = 0;
#endif
#ifdef PAWN27TH
				ext |= passer_move (&m->move);
#endif

				//ext = -(notbad > 2);

#ifdef PVSt
				if (best1 == -MATE) {
					if (idepth + ext > 1)
						r = -full_search (idepth + ext - 1, -rootbeta, -best, 0, 0);
					else
						r = -squies (-rootbeta, -best);
					/*
						If PV fails low, another, within radius, *may* replace it .. but then again, maybe not.
						We ran out of time searching PV. What to do?
						!!!!CRAZY!!!!
					if(stop_search && reserve && (nt != EXACT_PV || best1 > -MATE))
					{
						stop_search = 0;
						st += reserve;
						reserve = 0;
						goto KEEPLOOKING;
					}
					*/
				} else {
					if (idepth + ext > 1)
						r = -full_search (idepth + ext - 1, -best - 1, -best, 1, 4);
					else
						r = -squies (-best - 1, -best);
					if (!stop_search && r > best && r < rootbeta) {
						if (idepth + ext > 1)
							r = -full_search (idepth + ext - 1, -rootbeta, -best, 0, 0);
						else
							r = -squies (-rootbeta, -best);
					}
				}
#else
				if (idepth + ext > 1)
					r = -full_search (idepth + ext - 1, -rootbeta, -best, 0, 4);
				else
					r = -squies (-rootbeta, -best);

#endif
			}
			unmove ();

			if (stop_search) break;

			elapsed = _tick () - bt;
			m->score = (nodes - nodesb4)/100; // hack: prevent scores from exceeding 'markers'

			if (r > best1) {
				bm = m; // bm may have the best move 'so far' but that can be a bad move, if we are resolving a fail-low ...
				best2 = best1;
				best1 = r;
				if (r > best) {
					best = r;
					if (m->move.data.type > CAQ)
						hbump (&m->move, idepth);
					pv[ply][ply] = m->move;

					if (r >= rootbeta)
						break;

					/* update the PV */
					for (i = ply + 1; i < pvl[ply + 1]; ++i)
						pv[ply][i] = pv[ply + 1][i];
					pvl[ply] = pvl[ply + 1];
					printf ("%2d %5d %6d %8d ", idepth, best, (int) ((elapsed) / 10), nodes);
					for (i = 1; i < pvl[1]; ++i) {
						if (move_is_legal (&pv[1][i])) {
							printmv (&pv[1][i]);
							//stuffpv (pv[1][i].asint, pvl[1] - i);
							domove (&pv[1][i]);
							if (inCheck (stm))
								printf ("+ ");
							else
								printf (" ");
							if (console && i % 8 == 0)
								printf ("\n                         ");
						} else {
							break;
						}
					}
					printf ("     \n");
					fflush (stdout);
					/*
					if(console && maxtime == 9999999 && best > -MATE+MAXPLY && best < MATE-MAXPLY)
					{
						if(eval(-MATE, MATE) != ((ply&1)? best : -best))
						{
							printf("\a\n");
							display();
							printf("best:%d SE:%d\n", best, eval(-MATE, MATE));
						}
						else
						{
							report_se(0);
							display();
						}
					}
					*/
					//lps = force[WHITE] + force[BLACK] + types[WP] + types[BP];
					while (ply > 1) {
						unmove ();
					}
					//fishy = (lps < force[WHITE] + force[BLACK] + types[WP] + types[BP]);
				}
			} else {
				if (r > best2)
					best2 = r;
			}
			notbad += (r > rootalpha);
		}
		/*
			stop_search : ran out of time
			best1 == -MATE : did NOT finish searching 1st move
			trend(s) : slope of recent scores (-) decreasing
			nt = node type from previous iteration [not current - yet]
			fishy : PV includes trades
			lib : last iteration best score
		*/
		/*
			Bail early, without 'failing low' when timed out searching PV but all looks ok
		*/
		if (best > rootalpha) {
			if (best < rootbeta) {
				if (stop_search /*&& abs(trend (best)) < 15 && fishy == 0*/ && nt == EXACT_PV) {
					damp_history (idepth);
					break;
				}
				
				/*
					EBF = Time of iteration N / time of iteration N-1
				*/
				if (lit) {
					++bfc;
					bf += (float) ((elapsed - lit + 1) / lit);
				}
				lit = elapsed - lit + 1;
				
				/* resolved */
				if (elapsed > maxtime
				    //&& abs(trend (best)) < 15
				    && nt == EXACT_PV
					) {
					lib = best;
					break;
				}
				
				/* easy choice */
				if ((idepth & 1) == 0
				    && easy
				    && best2 > -MATE && best1 - best2 > 100
				    && nt == EXACT_PV
				     && elapsed > maxtime / 3
				    //&& abs(trend (best)) < 15
				   
					) {
					lib = best;
					break;
				}
				
				/* no choice */
				if (legal < 2)
					break;
				
				
				if (best1 > (MATE - MAXPLY))
					if (idepth > MATE - best1 - 2)
						break;
				
				
				idepth++;
				tagpv (last_move[0], bm->move.asint, 10000000);
				rootalpha = max (-MATE, best - RADIUS);
				rootbeta = min (MATE, best + RADIUS);
				nt = EXACT_PV;
				lib = best;
			} else { // best >= rootbeta
				printf ("%2d %5d %6d %8d +++             \n", idepth, best, (int) ((elapsed) / 10), nodes);
				fflush (stdout);
				
				tagpv (last_move[0], bm->move.asint, 10000000);
				
				/*
				  IF SEARCH BAILED ON TIME, AFTER FINDING BEST MOVE, TAGGING IS POINTLESS UNLESS WE ALSO SORT!!!
		         */
				/*
					we failed high, score exceeded lib+40
					lets try lib+80. why? if we see better already
					lets try best1+40, first
				*/
				if (rootbeta > lib + RADIUS || best > lib + RADIUS2)
					rootbeta = MATE;
				else
					rootbeta = min (MATE, lib + RADIUS2);
				nt = FAIL_HIGH;
			}
		} else if (best1 > -MATE) { // best <= rootalpha though PV was searched!
			printf ("%2d %5d %6d %8d ---             \n", idepth, best1, (int) ((elapsed) / 10), nodes);
			fflush (stdout);
			
			/* PV that failed low, or slightly better choice */
			tagpv (last_move[0], bm->move.asint, 10000000);
			
			if (rootalpha < lib - RADIUS || best1 < lib - RADIUS2)
				rootalpha = -MATE;
			else
				rootalpha = max (-MATE, lib - RADIUS2);
			
			nt = FAIL_LOW;
		}
	

		if (stop_search) {
			if (reserve) {
				if (nt != EXACT_PV || (trend (lib)/15) != 0) {
					st += reserve;
					reserve = 0;
					stop_search = 0;
					continue;
				}
			}
			break;
		}
	};
#ifndef FAST
	bf /= (float) (bfc);
	if (bf > 9.9f)
		bf = 9.9f;
#ifdef LOG
	fprintf (debuglog, "%6d %6d ", maxtime, reserve);
	fprintf (debuglog, "%2d %2d %2d %2d ", (int)(last_move[1] - last_move[0]), idepth - 1, sdepth, qdepth);
	fprintf (debuglog, "%5d %2d %5d ", nodes / 1024, 20 * qnodes / nodes * 5, evals / 1024);
	fprintf (debuglog, "%3d  %1.1f ", 100 * fh1 / fhn, bf);
	fprintf (debuglog, "%8d %8d %7d %6d %6d %8d %7d %7d %7d %6d %7d ", ext_check + ext_recap + ext_etd + ext_pawn + ext_end + ext_1rep + ext_threat + ext_real, ext_check, ext_recap, ext_etd, ext_real, ext_pawn, ext_end, ext_check + ext_recap + ext_etd + ext_pawn + ext_end + ext_real, ext_1rep, ext_threat, ext_1rep + ext_threat);
	fprintf (debuglog, "%7d %7d %7d %7d %7d %7d %7d %7d ", red_null_fh, red_delta, red_futile, red_xfutile, red_razor, red_nohist, red_null_fh + red_delta + red_xfutile + red_futile + red_razor + red_nohist, researches);
	fprintf (debuglog, "%3d%% %3d%%  ", 100 * used / hashsize, 100 * (probes - misses) / probes);
	fprintf (debuglog, "%2d %1d %2d %1d ", force[1], types[WP], force[0], types[BP]);
	move2str (&pv[1][1], ms);
	fprintf (debuglog, "%6s %6d %6d %6d ", ms, max (best, lib), trend (max (best, lib)), lps);
	buildepd (ms);
	fprintf (debuglog, "%d %s\n", r, ms);
#endif
#ifdef BLUNDERS
	if (mhs > move_history + 7 && max (best, lib) > -300 && trend (max (best, lib)) < -40) {
		unmove ();
		unmove ();
		buildepd (ms);
		/*
		fprintf (blunders, "%02d %02d %02d %s\n", force[0] + force[1], types[WP] + types[BP], idepth, ms);
		*/
		fprintf(blunders,"%s; 'D=%d W:%d(%d) B:%d(%d)';\n", ms, idepth, force[WHITE], types[WP], force[BLACK], types[BP]);
		domove (&mhs->move);
		domove (&mhs->move);
	}
#endif
#endif
	if (console) {
		printf ("                                  \nSearch stats\n------------\n");
		printf ("moves: %2d depth: %2d %2d %2d ",
			(int)(last_move[1] - last_move[0]), idepth, sdepth, qdepth);
		printf ("nodes: %5d (%2d%%) evals: %5d\n",
			nodes / 1024, 20 * qnodes / nodes * 5, evals / 1024);
		printf ("EBF %3d%%  %1.1f\n",
			100 * fh1 / fhn, bf);
		printf ("extension: %8d\nchk: %8d rec: %7d etd: %6d  rtd: %6d pawn: %6d end: %6d = %8d\n1rep %7d mat %6d  = %7d\n",
			ext_check + ext_recap + ext_etd + ext_pawn + ext_end + ext_1rep + ext_threat + ext_real,
			ext_check,
			ext_recap,
			ext_etd,
			ext_real,
			ext_pawn,
			ext_end,
			ext_check + ext_recap + ext_etd + ext_pawn + ext_end + ext_real,
			ext_1rep,
			ext_threat,
			ext_1rep + ext_threat);
		printf ("reduction: %7d\nnmp %7d dta %7d fut %7d xfu %7d raz %7d his %7d res %7d\n",
			red_null_fh + red_delta + red_xfutile + red_futile + red_razor + red_nohist,
			red_null_fh,
			red_delta,
			red_futile,
			red_xfutile,
			red_razor,
			red_nohist,
			researches
			);
		printf ("hash: %3d%% %3d%%\n", 100 * used / hashsize, 100 * (probes - misses) / probes);
		printf ("material: W %2d %1d B %2d %1d\n", force[1], types[WP], force[0], types[BP]);
	}
	return lib;
}
