#include "bitboard.h"
#include "bitsearch.h"
#include "bitmovegen.h"
#include "bitmagic.h"
#include "search.h"			// stupid -- just because of searchcallback!
#include "gtbwrapper.h"
#include "bitpsq.h"
#include "bitpersonality.h"
#include <math.h>
#include <memory.h>
#include <stdio.h>

// FIXME: hashfull sucks...

//#define DEBUG_CUTOFF

u64 cutoffMoves = 0;
u64 cutoffCount = 0;

// debug (log) root moves
//#define DEBUG_ROOT

#if defined(DEBUG) || defined(_DEBUG)
#define DEBUG_EVAL
#endif

//#define DISABLE_PRUNING

#ifdef DISABLE_PRUNING
enum
{
	useLMR			=	0,
	useNull			=	0,
	useFutility		=	0,
	useRazoring		=	0,
	useDelta		=	0,
	useNullVer		=	1,
	useTransPV		=	1,
};
#else
enum
{
	useLMR			=	1,
	useNull			=	1,
	useFutility		=	1,
	useRazoring		=	1,
	useDelta		=	1,
	useNullVer		=	1,
	useTransPV		=	1,
};
#endif

// doesn't work for me
//#define USE_COUNTER

#define USE_TB

enum
{
	tbDepth			=	4,			// minimum tb-probe depth
};

#define VALIDATE_HASHMV

// hope this fixes a bug in my old MDP
#define NEW_MDP

//#define OLD_CHECKS			// use old check handling

// use single reply extensions 1 ply?
//#define USE_SINGLEREPLY

// give more time to avoid a blunder (might lose on time in such case)
#define USE_AVOIDBLUNDER

// FIXME: seems to be a bug here! (isLegalMove bug?!)
// seems ok but no speed gain?
#define USE_DELAYED_MOVEGEN

#define USE_MATEKILLER

#define USE_IID

#define USE_LMR
#define SAFE_LMR
i32 LMR_NULL_MOVES =	4;
i32 LMR_MOVES = 15;
#define LMR_DEPTH		2
#define LMR_REDUCTION	1
#define LMR_REDUCTION_FRAC 0x100

#ifdef SAFE_LMR
#define didLMRMoves didQuietMoves
#else
#define didLMRMoves didMoves
#endif

// use full eval for futility pruning?
//#define USE_FUTIL_EVAL

//#define EXTEND_ONLY_CHECKS

// use potential recapture extension
#define USE_POT_RECAP

// use LMR at root node?
// FIXME: doesn't seem to play at different strength, but I might be wrong...
//#define USE_LMR_ROOT

// use razoring? (FIXME: seems to play worse...)
// I still don't know...
// finally it seems better anyway...
#define USE_RAZORING

// qsearch as soon as possible?
// FIXME: seems to play worse... (really?)
// NO! seems better (scored 56% in 40 games; 14 wins, 9 losses)
// it seems that there's something wrong with my search and/or transtbl...
// but that's hard to say...
#define QS_ASAP

// hash nullmoves?
#define HASH_NULL

// hash quiescence search?
#define HASH_QS

#define USE_CHECK_QSEARCH

// use nullmove reductions instead of pruning!
// seems much worse? (worse at longer time limits)
//#define USE_NMR

// full qsearch (incl. bad caps)
// NOTE!: check bitmovegen.cpp! these defines MUST match!
// FIXME: seems better. but why?! SEE broken?!
//#define USE_FULL_QS

// use delta pruning (seems better at short time control)
#define USE_DELTA

i32	deltaMargin		=		50;			// delta pruning margin
i32 razorMargin		=		325;		// razor margin

// FIXME: doesn't seem to work (SHIT!)
//#define USE_QS_FUTIL

// extend passed pawn moves a bit
#ifndef EXTEND_ONLY_CHECKS
#define USE_PASSED_EXT
#endif

#define CLEAR_PV

#define CLAMP_AB(t) (t)
//#define CLAMP_AB(t) ((t) < oalpha ? oalpha : (t) > beta ? beta : (t))
//#define CLAMP_AB(t) ((t) < oalpha ? oalpha : (t))

#ifdef DEBUG_ROOT
typedef struct SearchStats
{
    i64 nodesSearched;
    i64 ttCuts;				// transposition table cuts
    i64 qttCuts;			// transposition table qsearch cuts
    i64 iids;				// IID calls
    i64 nullCuts;			// nullmove cuts
    i64 nullVers;			// nullmove verification searches
    i64 reductions;			// number of moves reduced
} SearchStats;

static SearchStats searchStats;

static void dumpStats()
{
    logFmt("\tTT Cuts: %I64d\n", searchStats.ttCuts );
    logFmt("\tquiescent TT Cuts: %I64d\n", searchStats.qttCuts );
    logFmt("\treductions: %I64d\n", searchStats.reductions );
    logFmt("\tnullCuts: %I64d\n", searchStats.nullCuts );
    logFmt("\tnullVers: %I64d\n", searchStats.nullVers );
    logFmt("\tIIDs: %I64d\n", searchStats.iids );
}

#endif

// draw by repetition score (cp)
#define DRAW_REP	0
// draw by material/50 counter (cp)
#define DRAW_MAT	0

#define getMilisec getMillisec

enum depth_Shift
{
	bdepthConst = 1*255,
    bdepthShift = 8
};

static i32 counter = 0;

inline i32 sgetMilisec()
{
    static i32 last;
    if ( --counter <= 0 )
    {
        counter = 100;
        last = getMilisec();
    }
    return last;
}

// make_first_move
static void makeFirst( const BitMove &bm, i32 vm, BitMove *m, i32 killer = 0 )
{
    if ( bm.packed )
    {
        i32 i;
        i32 dest = 0;
        for (i=0; i<vm; i++)
        {
            if ( killer && (m[i].promo == queen || (m[i].flags & bgoodcap)) )
            {
                dest = i+1;
            }
            if ( m[i].packed == bm.packed )
            {
                i32 j;
                for (j=i; j>dest; j--)
                {
                    m[j].packed = m[j-1].packed;
                }
////				std::swap( m[0], m[i] );
                m[dest].packed = bm.packed;
                return;
            }
        }
    }
}

// BitSearchStackEntry

BitSearchStackEntry::BitSearchStackEntry()
{
    // hack!
    memset( this, 0, sizeof(*this) );
}

// returns true if move is a killer move
bool BitSearchStackEntry::isKiller( const BitMove &bm ) const
{
    i32 i;
    if ( bm.packed == mateKiller.packed )
    {
        return 1;
    }
    for (i=0; i<bkillers; i++)
    {
        if ( bm.packed == killers[i].packed )
        {
            return 1;
        }
    }
    return 0;
}

// BitSearchMode

BitSearchMode::BitSearchMode() : mateSearch(0), maxDepth( bmaxDepth ), maxNodes(0), maxTime(0), 
	absLimit(0), native(0), ponder(0), multiPV(1)
{
}

// BitSearch

void boardFromBitBoard( Board &b, const BitBoard &bb )
{
    i32 turn = bb.flags().turn;
    i32 i;
    b.clear(turn);
    for (i=white; i<=black; i++)
    {
        i32 j;
        for (j=pawn; j<king; j++)
        {
            const u64 &m = bb.bits[ INDEX(i, j) ];
            u8 pos[64];
            i32 npos = getPos( m, pos );
            i32 k;
            for (k=0; k<npos; k++)
            {
                Piece &p = b.pieces[ pos[k] ];
                p.color = i;
                p.type = j;
                p.moved = bb.pieceMoved( pos[k] ) ? 1 : 0;
            }
        }
        u8 pos = bb.flags().kingPos[ i ];
        Piece &p = b.pieces[ pos ];
        p.color = i;
        p.type = king;
        u8 cr = bb.flags().castRights[ i ];
        if ( !cr )
        {
            b.flags.castled |= (1 << i);
        }
        p.moved = !cr ? 1 : 0;
        b.flags.kingPos[i] = bb.flags().kingPos[ i ];
    }
    b.flags.lastMoved = 255;		// dunno
    b.flags.ep = bb.flags().ep;
    b.flags.fiftyCounter = bb.flags().fiftyCounter;
    b.update( turn );
}

Move BitSearch::getStdMove( const BitBoard &b, const BitMove &bm ) const
{
    Move res;
    res.packed = 0;
    if ( bm.from == bm.to )
    {
        return res;
    }
    Board ob;
    boardFromBitBoard( ob, b );
    Move m[ maxMoves ];
    i32 vm = ob.moves( m, b.flags().turn );
    i32 i;
    for (i=0; i<vm; i++)
    {
        if ( m[i].from == bm.from && m[i].to == bm.to && m[i].promo == bm.promo )
        {
            break;
        }
    }
    if ( i >= vm )
    {
//		logFmt("illegal_move_found!\n");
        return res;
    }
    return m[i];
    return res;
}

void BitSearch::nativeCallback( i32 depth, i32 curmove, i32 nummoves, const BitMove &best, const BitMove &cur,
                                i32 scorecp, bool full )
{
    if ( searchCallback )
    {
        i32 progress = curmove * 100 / nummoves;
        Move bestmove;
        Move curmove;
        PVMoves pv;
        bestmove = getStdMove( board, best );
        curmove = getStdMove( board, cur );
        getBestLine( &pv );

        i32 oldsc;
        if ( abs(scorecp) >= bmate - 1000 )
        {
            oldsc = scorecp;
            if ( scorecp > 0 )
            {
                oldsc += mate - bmate;
            }
            else
            {
                oldsc -= mate - bmate;
            }
        }
        else
        {
            oldsc = scorecp * 10;
        }

        Move nullmove;
        nullmove.packed = 0;

        searchCallback( depth, oldsc, progress, full ? bestmove : nullmove, curmove, full ? &pv : 0, nodes, searchCallbackParam );
    }
}

// init stack at ply
inline void BitSearch::initPly( i32 ply )
{
    BitSearchStackEntry &se = stack[ ply ];
#ifdef CLEAR_PV
    if ( ply > 0 )
    {
        se.pv[ ply ].packed = se.pv[ ply+1 ].packed = 0;
    }
#endif
    se.move.packed = 0;
    BitSearchStackEntry &se2 = stack[ ply + 2 ];
    se2.mateKiller.packed = 0;
    i32 i;
    for ( i=0; i<bkillers; i++ )
    {
        se2.killers[i].packed = 0;
    }
    nodes++;
}

// note: called AFTER move has been made!
static bool canReduce( const BitMove &bm, const BitBoard &board )
{
    if ( (bm.flags & (bcastling|bcapture)) || bm.promo )
    {
        return 0;		// shouldn't reduce this
    }
    // don't reduce passed pawn push!
    i32 turn = board.flags().turn ^ 1;
    if ( !(ONESHL( bm.to ) & board.bits[ wpawn + turn ]) /*(board.pieces[ bm.to ] & 127) != 1*/ )
    {
        return 1;		// no pawn move -- ok to reduce
    }
    return (passPawnMask[turn][bm.to] & board.bits[ bpawn - turn ]) != 0;
}

// note: called BEFORE move has been made!
static bool canReduceBefore( const BitMove &bm, const BitBoard &board )
{
    if ( (bm.flags & (bcastling|bcapture)) || bm.promo
#ifndef OLD_CHECKS
            || board.flags().check
#endif
       )
    {
        return 0;		// shouldn't reduce this
    }
    // don't reduce passed pawn push!
    i32 turn = board.flags().turn;
    if ( !(ONESHL( bm.from ) & board.bits[ wpawn + turn ]) /*(board.pieces[ bm.from ] & 127) != 1*/ )
    {
        return 1;		// no pawn move -- ok to reduce
    }
    return (passPawnMask[turn][bm.from] & board.bits[ bpawn - turn ]) != 0;
}

// nullver: seems better WITHOUT it! (actually WITH it)
// transpv: seems better WITHOUT it! (?because of extensions?) (no seems better with it...) (actually WITH it)
// singularext off: cheng vs cheng: good, cheng vs wjc: bad! (will have to test more)
BitSearch::BitSearch( RepHash *rh_, BitEval *eval_ ) : rh( rh_ ), evaluator( eval_ ), stopSearch(false),
        numMoves(0), ownrh(0), owneval(0), quiet(0), tbMen(0), tbUsage(2), tb(0)
{
    if ( !rh )
    {
        rh = new RepHash;
        ownrh = 1;
    }
    if ( !evaluator )
    {
        evaluator = new BitEval;
        owneval = 1;
    }
    lastScore = 0;
    board.reset();
    rboard.reset();
	rturn = 0;
    clearSlots();
    i32 evl = eval( board );
}

BitSearch::~BitSearch()
{
    if ( owneval )
    {
        delete evaluator;
    }
    if ( ownrh )
    {
        delete rh;
    }
}

// sort noncap moves using history table
// FIXME: obsolete...
void BitSearch::sortHistory( i32 vm, BitMove *m ) const
{
}

// add cutoff move to history table
void BitSearch::addHistory( i32 depth, const BitMove &bm )
{
    hist.add( bm, board, depth );
}

// update killer move for a given height
void BitSearch::updateKiller( i32 ply, const BitMove &bm )
{
    if ( (bm.flags & (bcapture|bcastling)) || bm.promo/* == queen*/ )
        return;			// don't waste killer slots!
    BitSearchStackEntry &se = stack[ ply ];
    i32 i;
    for (i=0; i<bkillers; i++)
    {
        if ( se.killers[ i ].packed == bm.packed )
        {
            if ( i > 0 )
            {
                // make_first
                std::swap( se.killers[ 0 ].packed, se.killers[ i ].packed );
            }
            return;
        }
    }
    // add new
    for ( i = bkillers - 1; i > 0; i-- )
    {
        se.killers[ i ].packed = se.killers[ i - 1 ].packed;
    }
    se.killers[ 0 ].packed = bm.packed;
}

// advance search one move forward. this will shift killer/pv buffers
void BitSearch::advance()
{
    // no longer used
}

// clear history table
void BitSearch::clearHistory()
{
    hist.clear();
}

// clear all slots
void BitSearch::clearSlots()
{
    clearHistory();
    memset( stack, 0, sizeof(stack) );
}

// store PV back into transposition table
void BitSearch::storePV( i32 depth )
{
    return;
    BitBoard b( board );
    u64 pvhashes[ bmaxPV ];
    i32 i, j;
    for (i=0; i<bmaxPV; i++)
    {
        if ( !b.isLegal( stack[0].pv[i] ) )
        {
            break;
        }
        pvhashes[i] = b.hash();
        b.move( stack[0].pv[i] );
    }
    // FIXME/TODO: this is WRONG!!! must debug!
    // OR maye it's just the same stupid annoying bug when using transpv?!

    // store in reverse order. this is because we want the root move to be first at all times
    // it should happen very rarely that a simple pv_list would get hashtable collisions, just
    // to make sure it's ok at all times...
    // NEW: don't store pv[0], should be already stored by the search!
    for (j=i-1; j>=1; j--)
    {
        // check if same move in trans_table
        const u64 &h = pvhashes[j];
        BitTransEntry *te = trans.entry( h );
        if ( !te )
        {
            te = trans.firstEntry( h );
            if ( !te )
            {
                break;			// unexpected... (this means there's no transposition table)
            }
        }
        if ( te->hash != h || te->move.packed != stack[0].pv[j].packed )
        {
            // FIXME: hack!
            // new: depth should be rootdepth - j
            te->depth = depth - j;
            te->hash = h;
            te->move.packed = stack[0].pv[j].packed;
            // FIXME!!!
            te->value = -bmate+1001;
            te->type = bttBeta | (trans.searchid << 2);
        }
    }
}

void BitSearch::updatePV( i32 ply, const BitMove &mv )
{
    i32 i;
    stack[ ply ].pv[ ply ] = mv;
    for (i = ply+1; i < bmaxPV; i++)
    {
        if ( !(stack[ ply ].pv[ i ].packed = stack[ ply + 1 ].pv[i].packed) )
            break;
    }
}

#define updatePVHash( ply, mv ) se.pv[ply].packed = mv.packed
/*void BitSearch::updatePVHash( i32 ply, const BitMove &mv )
{
    stack[ ply ].pv[ ply ].packed = mv.packed;
//    stack[ ply ].pv[ ply+1 ].packed = 0;
}*/

// make_first_move
void BitSearch::makeFirstRoot( const BitMove &bm, i32 killer )
{
    if ( bm.packed )
    {
        i32 i;
        i32 dest = 0;
        for (i=0; i<rvm; i++)
        {
            if ( killer && (rm[i].promo == queen || (rm[i].flags & bgoodcap)) )
            {
                dest = i+1;
            }
            if ( rm[i].packed == bm.packed )
            {
                i32 j;
                i32 tmps = rs[i];
                i32 tmpn = rn[i];
                for (j=i; j>dest; j--)
                {
                    rm[j].packed = rm[j-1].packed;
                    rs[j] = rs[j-1];
                    rn[j] = rn[j-1];
                }
////				std::swap( m[0], m[i] );
                rm[dest].packed = bm.packed;
                rs[dest] = tmps;
                rn[dest] = tmpn;
                return;
            }
        }
    }
}

// root scoring helper
void BitSearch::setRootScore( const BitMove &bm, i32 score )
{
    i32 i;
    for (i=0; i<rvm; i++)
    {
        if ( rm[i].equal( bm ) )
        {
            break;
        }
    }
    i32 j;
    for (j=0; j<rvm; j++)
    {
        rs[j] = -bmate;
        rn[j] = 0;
    }
    if ( i < rvm )
    {
        rs[i] = score;
        // FIXME: ok to clear nodes?
        rn[i] = 0;
    }
}

void BitSearch::sendPVToGUI( i32 depth, i32 score, i32 alpha, i32 beta )
{
    if ( mode.native )
    {
        BitMove nullm;
        nullm.packed = 0;
        nativeCallback( depth, -1, -1, stack[0].pv[0], nullm, score );
        return;
    }
    if ( quiet )
    {
        return;
    }
    i32 t = score;
    String pvstr;
    getBestLine( pvstr, 0 );
    i32 ms = getMilisec();
    lastReport = ms;
    i32 dt = ms - startTicks;
    u32 nps = (u32)floor(dt ? (double)nodes * 1000.0 / dt : 0);
	u32 hashfull = trans.getFullnessPermill();

	i32 mpvi = -1;		// multiPV index
	if ( multiPV > 1 )
	{
		// handle_multipv_here
		i32 i, j;
		i32 bscore = bmate;
		for (i=0; i<multiPV; i++)
		{
			if ( multiPVData[i].move.packed == stack[0].pv[0].packed )
			{
				mpvi = i;
				break;
			} else if ( mpvi < 0 && !multiPVData[i].move.packed )
			{
				mpvi = i;
				break;
			}
			else if ( multiPVData[i].depth < depth )
			{
				if ( multiPVData[i].score < bscore )
				{
					bscore = multiPVData[i].score;
					mpvi = i;
				}
			}
		}
		if ( mpvi < 0 )
		{
			// find line to replace
			i32 bscore = bmate;
			i32 bdepth = bmaxPV;
			for (i=0; i<multiPV; i++)
			{
				if ( !multiPVData[i].move.packed )
					break;
				if ( multiPVData[i].depth < depth || multiPVData[i].score < score )
				{
					if ( multiPVData[i].depth < bdepth || multiPVData[i].score < bscore )
					{
						mpvi = i;
						bscore = multiPVData[i].score;
						bdepth = multiPVData[i].depth;
					}
				}
			}
		}
		if ( mpvi < 0 )
			return;			// nothing new
		ASSERT( mpvi >= 0 );
		// ok have multipv index now
		BitMultiPV &mpv = multiPVData[ mpvi ];
		mpv.depth = depth;
		mpv.score = score;
		mpv.move.packed = stack[0].pv[0].packed;
		mpv.ponder.packed = stack[0].pv[1].packed;
		mpv.tbHits = tbHits;
		mpv.nodes = nodes;
		mpv.nps = nps;
		mpv.hashFull = hashfull;
		mpv.time = dt;
		mpv.line = pvstr;
		// sort multipv
		for (i=0; i<multiPV; i++)
		{
			i32 &i0 = multiPVSort[i];
			if ( !multiPVData[i0].move.packed )
				break;
			for (j=i+1; j<multiPV; j++)
			{
				i32 &j0 = multiPVSort[j];
				if ( !multiPVData[j0].move.packed )
					break;
				if ( multiPVData[i0].depth < multiPVData[j0].depth || multiPVData[i0].score < multiPVData[j0].score )
				{
					std::swap( i0, j0 );
				}
			}
		}
		i32 mpvAlpha = bmate;
		i32 mpmoves = 0;
		for (i=0; i<multiPV; i++)
		{
			const BitMultiPV &mpv = multiPVData[i];
			if ( mpv.move.packed && mpv.depth == depth )
			{
				mpmoves++;
				if ( mpvAlpha > mpv.score )
					mpvAlpha = mpv.score;
			}
		}
		multiPVAlpha = mpmoves < multiPV ? -bmate : mpvAlpha;
	}
	if ( multiPV > 1 && depth <= 1 )
		return;		// wait for all mpv moves to report

	i32 i;
	const char *nompv ="";
	char mpvbuf[64];
	const char *mpvptr = multiPV > 1 ? mpvbuf : nompv;
	const String *line = &pvstr;
	i64 nodes = this->nodes;
	i64 tbHits = this->tbHits;
	for (i=0; i<multiPV; i++)
	{
		if ( multiPV > 1 )
		{
			i32 ind = multiPVSort[i];
			const BitMultiPV &mpvd = multiPVData[ind];
			if ( !mpvd.move.packed )
				break;		// nothing more to send
			line = &mpvd.line;
			depth = mpvd.depth;
			selDepth = mpvd.selDepth;
			t = score = mpvd.score;
			nodes = mpvd.nodes;
			nps = mpvd.nps;
			hashfull = mpvd.hashFull;
			dt = mpvd.time;
			sprintf( mpvbuf, "multipv %d ", 1 + i );
		}
	    bool isMate = t >= bmate - bmaxPV || t <= -bmate + bmaxPV;
		const char *bound;
		if ( score > alpha && score < beta )
		{
			bound = " ";
		}
		else if ( score <= alpha )
		{
			bound = " upperbound ";
		}
		else
		{
			bound = " lowerbound ";
		}

		if ( isMate )
		{
			i32 msc = t >= 0 ? (bmate - t)/2 + 1 : (-bmate - t)/2 - 1;
			if ( selDepth > depth )
			{
				printf("info %sdepth %d seldepth %d score mate %d%stime %d nodes %lld nps %d hashfull %d tbhits %lld pv %s\n",
					mpvptr,
					depth, selDepth, msc, bound, dt, nodes, nps, hashfull, tbHits, line->ansi()
					);
			}
			else
			{
				printf("info %sdepth %d score mate %d%stime %d nodes %lld nps %d hashfull %d tbhits %lld pv %s\n",
					mpvptr,
					depth, msc, bound, dt, nodes, nps, hashfull, tbHits, line->ansi()
					);
			}
		}
		else
		{
			if ( selDepth > depth )
			{
				printf("info %sdepth %d seldepth %d score cp %d%stime %d nodes %lld nps %d hashfull %d tbhits %lld pv %s\n",
					mpvptr,
					depth, selDepth, t, bound, dt, nodes, nps, hashfull, tbHits, line->ansi()
					);
			}
			else
			{
				printf("info %sdepth %d score cp %d%stime %d nodes %lld nps %d hashfull %d tbhits %lld pv %s\n",
					mpvptr,
					depth, t, bound, dt, nodes, nps, hashfull, tbHits, line->ansi()
					);
			}
		}
	}
}

static const i32 gainPromoTbl[] = {
    0, 0, 225, 225, 400, 875
};

static const i32 gainCapTbl[] = {
    100, 100, 325, 325, 500, 975
};

// FIXME: doesn't handle ep captures!
i32 moveGain( const BitBoard &b, const BitMove &m )
{
    i32 res = 0;
/*	if ( m.flags & benpassant )
		return 100;*/
    if ( m.promo )
    {
        res += gainPromoTbl[m.promo];
    }
    if ( m.flags & bcapture )
    {
        res += gainCapTbl[ b.pieces[ m.to ] & 127 ];
    }
    return res;
}

i32 BitSearch::qsearch( i32 depth, i32 ply, i32 alpha, i32 beta )
{
    qnodes++;
    i32 oalpha = alpha;
    BitSearchStackEntry &se = stack[ ply ];
#ifdef COPY_MOVE
    const BitBoard &board = se.board;
#endif

    initPly( ply );
    if ( ply > selDepth )
    {
        selDepth = ply;
    }

    if ( /*!checks &&*/ board.isDraw() )
    {
        drawCuts++;
        return CLAMP_AB( DRAW_MAT );
    }

    const u64 &h = board.bits[ bhash ];

    ASSERT( ply > 0 );

    i32 repCnt = rh ? rh->get( h ) : 0;
    if ( repCnt >= 2 )
    {
        drawCuts++;
        return CLAMP_AB( DRAW_REP );
    }

#if 1
#ifdef NEW_MDP
    alpha = std::max( alpha, -bmate + ply );
    beta = std::min( beta, bmate - ply - 1 );
    if ( alpha >= beta )
        return alpha;
#else
    if ( alpha >= bmate - bmaxPV )
    {
        // mate distance pruning!
        if ( /*ply > 0 && */ply > bmate - alpha + 1 )
            return alpha;
    }
    if ( beta <= -bmate + bmaxPV )
    {
        // mate distance pruning!
        if ( /*ply > 0 && */ply > beta + bmate + 1 )
            return beta;
    }
#endif
#endif

    BitMove hashmv;
    hashmv.packed = 0;

#ifdef HASH_QS
    const BitTransEntry *te = trans.entry( h );
    if ( te )
    {
		if ( (useTransPV || oalpha + 1 == beta ) && (te->type & 3) && te->depth >= (depth >= 0 ? 0 : -1) /*&& te->hash == h*/
                /*&& trans.isCurrent( te )*/
           )
        {
            // potential trans_table hit!
            i32 val = te->getValue( ply );
            switch ( te->type & 3 )
            {
            case bttFull:
#ifdef DEBUG_ROOT
                searchStats.ttCuts++;
                searchStats.qttCuts++;
#endif
                se.move.packed = te->move.packed;
                updatePVHash( ply, te->move );
                return CLAMP_AB(val);
            case bttAlpha:
                if ( val <= alpha )
                {
#ifdef DEBUG_ROOT
                    searchStats.ttCuts++;
                    searchStats.qttCuts++;
#endif
                    se.move.packed = te->move.packed;
                    updatePVHash( ply, te->move );
                    return CLAMP_AB(val);//alpha;
                }
                break;
            case bttBeta:
                if ( val >= beta )
                {
#ifdef DEBUG_ROOT
                    searchStats.ttCuts++;
                    searchStats.qttCuts++;
#endif
                    se.move.packed = te->move.packed;
                    updatePVHash( ply, te->move );
					updateKiller( ply, te->move );
                    return CLAMP_AB( val );
                }
                break;
            }
            hashmv.packed = te->move.packed;
        }
        else
        {
            if ( (te->type & 3) /*&& te->hash == h*/ )
            {
                hashmv.packed = te->move.packed;
            }
        }
    }
#endif

    i32 t = eval( board, alpha, beta );
//	return t;		// FIXME: no_qs!
    i32 safetyEval[2] = { evaluator->safetyEval[0], evaluator->safetyEval[1] };
    const BitFlags &bf = board.flags();
//    bool loneKing = 0;

    i32 evl = t;
#ifdef DEBUG_EVAL
    BitBoard iboard(board);
    iboard.swap();
    i32 t2 = eval( iboard, alpha, beta );
    if ( t * t2 < 0 || abs(t - t2) > 1 )
    {
        i32 t0 = eval( board, -bmate, +bmate );
        i32 t1 = eval( iboard, -bmate, +bmate );
        if ( t0 * t1 < 0 || abs(t0 - t1) > 1 )
        {
            logFmt("eval_symm_bug\n");
            board.dump();
            logFmt("swapped:\n");
            iboard.dump();
            // clear_eval_cache!
            evaluator->clearCache();
            evaluator->setDebugFlag(1);
            i32 t0 = eval( board, -bmate, +bmate );
            i32 t1 = eval( iboard, -bmate, +bmate );
            evaluator->setDebugFlag(0);
            logFmt("final_t0, t1=%d %d\n", t0, t1);
        }
    }
#endif

    bool check = bf.check != 0;

    i32 best = t;
#ifdef USE_CHECK_QSEARCH
    if ( check )
    {
        best = -bmate;
    }
    else
#endif
        if ( t > alpha )
        {
            alpha = t;
            if ( t >= beta )
                return CLAMP_AB( best );			// too good
        }

    if ( ply >= bmaxPly )
        return CLAMP_AB(evl);//alpha;

    BitMoveGen mg( board, ply, *this, hashmv, check ? mgtQEvasions : (depth >= 0 ? mgtQCapturesWithChecks : mgtQCaptures) );
    i32 vm = mg.count();
    if ( !vm )
    {
        // stalemate or checkmate
        if ( check )
        {
////			board.dump();
            return CLAMP_AB(-bmate + ply);
        }
        // FIXME: how to handle stalemate?! (later, when no more moves remain... OR: not at all?!)

//		BitMove m[256];
//		vm = board.moves( m );
//        if ( !vm )
//        {
            return CLAMP_AB(0);		// stalemate...
//        }
//        return CLAMP_AB(t);
    }

    i32 i;
    i32 qm = 0;					// num_quiesc_moves
    u64 undoBuf[ bundomax ];	// move_undo buffer

    BitMove m;
    i32 count = 0;
    while ( mg.next(m) )
    {
        count++;
        se.move.packed = m.packed;
        if ( stopSearch )
            return CLAMP_AB(alpha);	// abort -- external flag set

        i32 dt = timeLimit - sgetMilisec();
        if ( dt < 0 && !mode.ponder )
        {
            stopSearch = true;
            return CLAMP_AB(alpha);	// abort -- time is up!
        }

        bool castling = m.flags & bcastling;

#ifdef DEBUG
        bool pruneCand = 0;
        static i64 pruneFails = 0, pruneSucc = 0, pruneTot = 0;
        const i64 pruneDumpMax = 500;
        static i32 pruneDump = pruneDumpMax;
#endif


		{		// skip if NOT special move!
        if ( depth < 0 && !check )
        {
            if ( !(m.flags & bcapture) && !m.promo && !castling )
                continue;
#ifndef USE_FULL_QS
            if ( (m.flags & (bcapture | bgoodcap)) == bcapture )
                continue;		// skip bad captures
#else
            if ( oalpha + 1 == beta && (m.flags & (bcapture | bgoodcap)) == bcapture )
                continue;		// skip bad captures
#endif
#ifdef USE_DELTA
			i32 val;
			if ( useDelta && oalpha + 1 == beta && !castling && (val = moveGain(board, m) + 
				deltaMargin + safetyEval[ board.flags().turn ]/10/*+ std::max( safetyEval[0], safetyEval[1] )*/ + evl) < beta )
			{
				if ( val > best )
					best = val;
				continue;
			}
#endif
        }

		i8 chm = -1;
		if ( !check && !castling && (m.promo != queen) && (!(m.flags & bcapture)
#ifndef USE_FULL_QS
                                          || !(m.flags & bgoodcap)
#else
                                          || (oalpha + 1 == beta && !(m.flags & bgoodcap))
#endif
                                         )
			&& !board.isCheck( m, mg.discovered )
		)
		{
			continue;
		}
		}

#ifdef COPY_MOVE
        stack[ ply+1 ].board = board;
        stack[ ply+1 ].board.move( m );
#else
        i32 undoMask = board.move( m, undoBuf );
#endif

#if 0
        i32 isPPush = -1;			// -1 => don't know, 1 = yes

        if ( !check && !castling && (m.promo != queen) )
        {
/*#ifdef USE_CHECK_QSEARCH
            if ( depth < 0 && !(m.flags & bcapture) )
            {
#ifndef COPY_MOVE
                board.undo( undoMask, undoBuf );
#endif
                continue;
            }
#endif*/
            if ( !board.flags().check && (!(m.flags & bcapture)
#ifndef USE_FULL_QS
                                          || !(m.flags & bgoodcap)
#else
                                          || (oalpha + 1 == beta && !(m.flags & bgoodcap))
#endif
                                         ) )
            {
#ifdef USE_PASSED_EXT
                bool skip = 1;
#if 0
                i32 turn = board.flags().turn ^ 1;	// move_turn
                const u64 &mt = ONESHL( m.to );
                if ( /*checks depth == 0 &&*/ (mt & board.bits[ wpawn + turn ] ) )
                {
                    // pawn move
                    if ( !(passPawnMask[ turn ][ m.to ] & board.bits[ bpawn - turn ]) )
                    {
                        /*						BitBoard bb(board);
                        						bb.dump();
                        						char buf[32];
                        						m.describeUCI( buf );
                        						logFmt("move: %s\n", buf);*/
                        // new: don't skip pawn pushes at depth 0!
                        // FIXME: ok?!
                        isPPush = 1;
                        skip = 0;
                    }
                }
#endif
                if ( skip )
#endif
                {
                    // skip non-checking move/nonchecking bad capture!
//					t = alpha;
//					goto skipMove;
#ifndef COPY_MOVE
                    board.undo( undoMask, undoBuf );
#endif
                    continue;
                }
            }
        }
#endif

        if ( rh )
#ifndef COPY_MOVE
            rh->push( board.hash(), board.flags().fiftyCounter == 0 );
#else
            rh->push( stack[ ply+1 ].board.hash(), stack[ ply+1 ].board.flags().fiftyCounter == 0 );
#endif

        t = -qsearch( depth-1, ply+1, -beta, -alpha );

        if ( rh )
            rh->pop();

skipMove:
#ifndef COPY_MOVE
        board.undo( undoMask, undoBuf );
#endif

        if ( t > best )
        {
#ifdef DEBUG
            if ( pruneCand )
            {
                pruneFails++;
            }
#endif
            best = t;
            if ( t > alpha )
            {
                alpha = t;

                if ( oalpha + 1 != beta )
                {
                    updatePV( ply, m );
                }
				else
				{
					updatePVHash( ply, m );
				}

#ifdef USE_MATEKILLER
                if ( t == bmate - ply - 1 )
                {
                    se.mateKiller = m;
                }
#endif
                if ( t >= beta )
                {
                    updateKiller( ply, m );

                    ////				alpha = beta;
                    break;				// too good
                }
            }
        }
#ifdef DEBUG
        else if ( pruneCand )
        {
            pruneSucc++;
        }
        if ( --pruneDump <= 0 )
        {
            pruneDump = pruneDumpMax;
//			printf("info qpruning efficiency: %I64d succ, %I64d fails\n",
//				pruneSucc, pruneFails);
        }
#endif

    };

    if ( !count /*best == -bmate*/ )
    {
        if ( check )
        {
            return -bmate + ply;
        }
//		/*return */best = (check ? -bmate + ply : evl);
//		board.dump();
////		logFmt("FATAL: qsearch_bug!\n");
    }

	best = CLAMP_AB(best);

#ifdef HASH_QS
    trans.store( h, ply, depth < 0 ? -1 : 0, best <= oalpha ? bttAlpha : best >= beta ? bttBeta : bttFull, best, se.pv[ ply ] );
#endif

    return best;
}

/*static i32 recapExt[] =
{
	0, 
	0, 
	(1 << bdepthShift)*1/4,		// knight
	(1 << bdepthShift)*1/4,		// bishop
	(1 << bdepthShift)*1/2,		// rook
	(1 << bdepthShift)*1/1,		// queen
	(1 << bdepthShift)*1/1		// king
};
*/

i32 BitSearch::extend( i32 fdepth, const BitBoard &b, const BitMove &m, bool mateThreat, bool nullw, bool isCheck ) const
{
//	return fdepth;
//	bool extended = 0;
//	i32 extsum = 0;
    bool pawnMove = 0;
    i32 turn = b.flags().turn;
	if (
#ifndef OLD_CHECKS
        isCheck
#else
        b.flags().check
#endif
    )
    {
        return fdepth += (1 << bdepthShift)*8/8;		// extend checks 8/8 ply
//		extended = 1;
//		return fdepth;							// don't care for more (note: only if extending checks full ply!)
    }
    else
    {
#ifdef EXTEND_ONLY_CHECKS
        return fdepth;
#endif
        if ( b.bits[ wpawn + turn ] & ONESHL( m.from ) )
        {
            pawnMove = 1;
            if ( turn == white )
            {
                if ( (m.to >> 3) == 1 )
                {
                    return fdepth += (1 << bdepthShift)*1/2;		// extend wpawn move to 7th rank
//					extended = 1;
                }
            }
            else
            {
                if ( (m.to >> 3) == 6 )
                {
                    return fdepth += (1 << bdepthShift)*1/2;		// extend bpawn move to 2nd rank
//					extended = 1;
                }
            }
        }
    }
#if 1		// FIXME: slows down too much?! BUT: finds mates sooner so keeping!
    if ( /*!extended &&*/ mateThreat )
    {
        return fdepth += (1 << bdepthShift)*1/2;		// extend (nullmove) mate threats 1/1 ply
        // (?seems equal or tiny better than 1/2 ply at short time limit)
        // can't extend by full ply => might cause infinite search!
//		extended = 1;
    }
#endif
    if ( /*!extended &&*/ (m.flags & bcapture) )
    {
        i32 pt = b.pieceType( m.to );
        if ( pt > pawn && b.mat().tmat == tmatTab[ pt ] && !m.promo )
        {
            return fdepth += (1 << bdepthShift)*4/4;	// extend pawn ending 4/4 ply
//			extended = 1;
        }
        // FIXME: ok to do this? (don't know, seems equal or tiny better at short time limit)

#if 0
		if ( 0&&/*!nullw &&*/ ply > 0 && (m.flags & bgoodcap) )
		{
			const BitMove &pm = stack[ ply-1 ].move;
			if ( pm.flags & bcapture )
			{
				if ( pm.to == m.to && tmatTab[ board.pieces[ pm.to ] & 127 ] == tmatTab[ board.pieces[ m.from ] & 127 ] )
				{
					return fdepth += (1 << bdepthShift)*1/2;	// extend recaptures 1/2 ply
				}
			}
		}
#endif
#ifdef USE_POT_RECAP
        if ( /*!extended &&*/ !nullw && pt != pawn && (m.flags & bgoodcap)/*b.see( m, 1 ) >= 0*/ )
        {
            // recapture ext
            return fdepth += (1 << bdepthShift)*1/2;	// extend potential recaptures 1/2 ply
//			extended = 1;
        }
#endif
    }
#ifdef USE_PASSED_EXT
    if ( /*!extended &&*/ pawnMove && (passPawnMask[ turn ][ m.from ] & board.bits[ bpawn - turn ]) == 0
                          && ((m.flags & bgoodcap) || b.see(m, 1) >= 0)
       )
    {
        return fdepth +=  (1 << bdepthShift)*1/4;		// extend passed pawn move by 1/4 ply
//		extended = 1;
    }
#endif
    return fdepth;
}

i32 BitSearch::isearch( i32 fdepth, i32 ply, i32 alpha, i32 beta )
{
    i32 oalpha = alpha;
    i32 depth = (fdepth + bdepthConst) >> bdepthShift;

#ifdef QS_ASAP
    if ( ply >= bmaxPly || depth <= 0 )
    {
//		if ( rh )
//			rh->push( board.hash(), board.flags().fiftyCounter == 0 );
        i32 res = qsearch( 0, ply, alpha, beta );
//		if ( rh )
//			rh->pop();
        return CLAMP_AB(res);
    }
#endif

    BitSearchStackEntry &se = stack[ ply ];
#ifdef COPY_MOVE
    const BitBoard &board = se.board;
#endif
    initPly( ply );

    if ( board.isDraw() )
    {
        drawCuts++;
        return CLAMP_AB( DRAW_MAT );
    }

    const u64 &h = board.bits[ bhash ];

    i32 repCnt = rh ? rh->get( h ) : 0;
    if ( repCnt >= 2 && ply > 0 )
    {
        drawCuts++;
        return CLAMP_AB( DRAW_REP );
    }

#ifdef NEW_MDP
    alpha = std::max( alpha, -bmate + ply );
    beta = std::min( beta, bmate - ply - 1 );
    if ( alpha >= beta )
        return alpha;
#else
    if ( alpha >= bmate - bmaxPV )
    {
        // mate distance pruning!
        if ( ply > 0 && ply > bmate - alpha + 1 )
            return alpha;
    }
    if ( beta <= -bmate + bmaxPV )
    {
        // mate distance pruning!
        if ( ply > 0 && ply > beta + bmate + 1 )
            return beta;
    }
#endif

    BitMove hashmv;
    hashmv.packed = 0;

    const BitTransEntry *te = trans.entry( h );
    if ( te )
    {
        if ( useTransPV && (te->type & 3) && te->depth >= depth /*&& te->hash == h*/
                /*&& trans.isCurrent( te )*/
           )
        {
            // potential trans_table hit!
            i32 val = te->getValue( ply );
            switch ( te->type & 3 )
            {
            case bttFull:
#ifdef DEBUG_ROOT
                searchStats.ttCuts++;
#endif
                se.move.packed = te->move.packed;
                updatePVHash( ply, te->move );
                return CLAMP_AB(val);
            case bttAlpha:
                if ( val <= alpha )
                {
#ifdef DEBUG_ROOT
                    searchStats.ttCuts++;
#endif
                    se.move.packed = te->move.packed;
                    updatePVHash( ply, te->move );
                    return CLAMP_AB(val);//alpha;
                }
                break;
            case bttBeta:
                if ( val >= beta )
                {
#ifdef DEBUG_ROOT
                    searchStats.ttCuts++;
#endif
                    se.move.packed = te->move.packed;
                    updatePVHash( ply, te->move );
					updateKiller( ply, te->move );
					addHistory( depth, te->move );
                    return CLAMP_AB( val );
                }
                break;
            }
            hashmv.packed = te->move.packed;
        }
        else
        {
            if ( (te->type & 3) /*&& te->hash == h*/ )
            {
                hashmv.packed = te->move.packed;
            }
        }
    }

#ifdef USE_TB
	if ( tbUsage && tbMen > 2 && (tbUsage == 1 ? ply == 1 : depth >= tbDepth) && board.numMen() <= tbMen )
	{
		i32 res = tbProbe( ply, board );
		if ( res != -1 )
		{
			tbHits++;
//			return res;
/*			alpha = CLAMP_AB(res);
		    trans.store( h, ply, depth, alpha <= oalpha ? bttAlpha : alpha >= beta ? bttBeta : bttFull,
                 alpha, se.pv[ ply ] );

			return alpha;*/
			alpha = std::max( alpha, res-1 );
			beta = std::min( beta, res+1 );
		}
	}
#endif

#ifndef QS_ASAP
    if ( ply >= bmaxPly || depth <= 0 )
    {
        nodes--;		// FIXME: HACK!
//		if ( rh )
//			rh->push( board.hash(), board.flags().fiftyCounter == 0 );
        i32 res = qsearch( 0, ply, alpha, beta );
//		if ( rh )
//			rh->pop();
        return CLAMP_AB(res);
    }
#endif

#ifdef USE_IID
    // iid
    if ( !hashmv.packed && depth > 2/*2*/ )
    {
#ifdef DEBUG_ROOT
        searchStats.iids++;
#endif
        isearch( fdepth - (2 << bdepthShift), ply, alpha, beta );
        hashmv.packed = stack[ ply ].pv[ ply ].packed;
    }
#endif

    BitMove m;
    bool check = board.flags().check != 0;
    i32 i;

	i32 best = -bmate;

    BitMoveGen mg( board, ply, *this, hashmv, check ? mgtEvasions : mgtCaptures );
    i32 vm = mg.count();

#ifdef USE_SINGLEREPLY
    if ( !vm )
    {
        // stalemate or checkmate
        if ( check )
        {
            return CLAMP_AB(-bmate + ply);
        }
        return CLAMP_AB(0);		// stalemate...
    }

    if ( vm == 1 )
    {
        fdepth += 1 << bdepthShift;
    }
#endif

#ifndef COPY_MOVE
    u64 undoBuf[ bundomax ];
#endif

    bool havepv = false;

    i32 t = alpha;

    bool wasCheck = board.flags().check;

    i32 didMoves = 0;
#ifdef SAFE_LMR
	i32 didQuietMoves = 0;
#endif
    while ( mg.next( m ) )
    {
        /*		// TEST
        		if ( depth >= 8 ) {
        			char buf0[64], buf1[64];
        			stack[ply-1].move.describeUCI( buf0 );
        			m.describeUCI( buf1 );
        			if ( strcmp( buf0, "d6d7" ) == 0 && strcmp( buf1, "e8f8" ) == 0 )
        			{
        				printf("");
        			}
        		}

        		// !TEST*/

#ifdef SAFE_LMR
		if ( !(m.flags & (bcapture|bcastling)) )
			didQuietMoves++;
#endif
        didMoves++;
        se.move.packed = m.packed;
        if ( stopSearch )
            return CLAMP_AB(alpha);	// abort -- external flag set

        i32 ms = sgetMilisec();
        i32 dt = timeLimit - ms;
        if ( (dt < 0 && !mode.ponder) || (nodeLimit && nodes >= nodeLimit) )
        {
            stopSearch = true;
            return CLAMP_AB(alpha);	// abort -- time is up!
        }

        if ( !mode.native && ms - lastReport >= 2000 )
        {
            i32 dt = ms - startTicks;
            double nps = dt ? (double)nodes * 1000.0 / dt : 0;
            printf("info time %d nodes %lld nps %d hashfull %d\n",
                   dt, nodes, (int)floor(nps), trans.getFullnessPermill() );
            lastReport = ms;
        }

        // handle extensions
        bool isCheck =
#ifdef OLD_CHECKS
            0;
#else
            board.isCheck( m, mg.discovered );
#endif

        i32 newDepth = extend( fdepth - (1 << bdepthShift), board, m, 0, 0, isCheck );
        u8 extended = newDepth > fdepth - (1 << bdepthShift) ? 1 : 0;

#ifndef COPY_MOVE
        i32 undoMask = board.move( m, undoBuf, (i8)isCheck );
#else
        stack[ ply+1 ].board = board;
        stack[ ply+1 ].board.move( m );
#endif

        if ( rh )
#ifndef COPY_MOVE
            rh->push( board.hash(), board.flags().fiftyCounter == 0 );
#else
            rh->push( stack[ ply+1 ].board.hash(), stack[ ply+1 ].board.flags().fiftyCounter == 0 );
#endif

#ifdef USE_LMR
        if ( useLMR && /*ply > 0 &&*/ !extended && depth > LMR_DEPTH/*newDepth >= (LMR_REDUCTION << bdepthShift)*/ &&
                didLMRMoves >= LMR_MOVES && !wasCheck/*board.flags().check*/ && canReduce(m, board )//(!(m.flags & (bcapture|bcastling))) && !m.promo
                && !se.isKiller( m ) )
        {
#ifdef DEBUG_ROOT
            searchStats.reductions++;
#endif
			t = - isearchNull( newDepth - (LMR_REDUCTION_FRAC * (didLMRMoves >= 2*LMR_MOVES ? 2 : 1)), ply+1, -alpha-1, useNull );
        }
        else t = alpha+1;
        if ( t > alpha )
        {
#endif
			if ( havepv )
            {
                // first try a null-window search around alpha
                t = -isearchNull( newDepth, ply+1, -alpha-1, useNull );
            }

            if ( !havepv || t > alpha /*&& t < beta*/ )
            {
                // either we didn't find the pv yet or we have to research
                t = -isearch( newDepth, ply+1, -beta, -alpha );
                havepv = 1;
            }
#ifdef USE_LMR
        }
#endif

        if ( rh )
            rh->pop();

#ifndef COPY_MOVE
        board.undo( undoMask, undoBuf );
#endif

        if ( stopSearch )
            return CLAMP_AB(alpha);

		if ( t > best )
		{
			best = t;
			if ( t > alpha )
			{
				// new bestmove found
				//// 			havepv = true;		// for some reason this is stronger! (MS compiler bug?!)

				updatePV( ply, m );

				alpha = t;

#ifdef USE_MATEKILLER
				if ( t == bmate - ply - 1 )
				{
					se.mateKiller = m;
				}
#endif
				if ( alpha >= beta )
				{
#ifdef DEBUG_CUTOFF
					cutoffMoves += didMoves;
					cutoffCount++;
#endif
					// cutoff!
					updateKiller( ply, m );
					addHistory( depth, m );
#ifdef USE_COUNTER
					if ( !(m.flags & (bcapture|bcastling)) && !m.promo )
					{
						hist.counter[board.flags().turn][ stack[ply-1].move.from ][ stack[ply-1].move.to ].packed = m.packed;
					}
#endif
					break;
				}
			}
		}
    }

    if ( !didMoves )
    {
        // FIXME: assume mate or stalemate!
        return CLAMP_AB( check ? -bmate + ply : 0 );
    }

	best = CLAMP_AB(best);

    trans.store( h, ply, depth, best <= oalpha ? bttAlpha : best >= beta ? bttBeta : bttFull,
                 best, se.pv[ ply ] );

    return best;
}

static i32 futMargin[] = {0, 100, 150, 200, 250};

i32 BitSearch::isearchNull( i32 fdepth, i32 ply, i32 alpha, bool usenull )
{
    i32 oalpha = alpha;
    i32 depth = (fdepth + bdepthConst) >> bdepthShift;
    i32 beta = alpha + 1;
#ifdef QS_ASAP
    if ( ply >= bmaxPly || depth <= 0 )
    {
//		if ( rh )
//			rh->push( board.hash(), board.flags().fiftyCounter == 0 );
        i32 res = qsearch( 0, ply, alpha, beta );
//		if ( rh )
//			rh->pop();
        return CLAMP_AB(res);
    }
#endif
    BitSearchStackEntry &se = stack[ ply ];
#ifdef COPY_MOVE
    BitBoard &board = se.board;
#endif
    initPly( ply );

    if ( board.isDraw() )
    {
        drawCuts++;
        return CLAMP_AB( DRAW_MAT );
    }

    const u64 &h = board.bits[ bhash ];

    i32 repCnt = rh ? rh->get( h ) : 0;
    if ( repCnt >= 2 && ply > 0 )
    {
        drawCuts++;
        return CLAMP_AB( DRAW_REP );
    }

#ifdef NEW_MDP
    alpha = std::max( alpha, -bmate + ply );
    beta = std::min( beta, bmate - ply - 1 );
    if ( alpha >= beta )
        return alpha;
#else
    if ( alpha >= bmate - bmaxPV )
    {
        // mate distance pruning!
        if ( ply > 0 && ply > bmate - alpha + 1 )
            return alpha;
    }
    if ( beta <= -bmate + bmaxPV )
    {
        // mate distance pruning!
        if ( ply > 0 && ply > beta + bmate + 1 )
            return beta;
    }
#endif

    BitMove hashmv;
    hashmv.packed = 0;

    const BitTransEntry *te = trans.entry( h );
    if ( te )
    {
        if ( (te->type & 3) && te->depth >= depth /*&& te->hash == h*/
                /*&& trans.isCurrent( te )*/ )
        {
            // potential trans_table hit!
            i32 val = te->getValue( ply );
            switch ( te->type & 3 )
            {
            case bttFull:
#ifdef DEBUG_ROOT
                searchStats.ttCuts++;
#endif
                se.move.packed = te->move.packed;
                return CLAMP_AB(val);
            case bttAlpha:
                if ( val <= alpha )
                {
#ifdef DEBUG_ROOT
                    searchStats.ttCuts++;
#endif
                    se.move.packed = te->move.packed;
                    return CLAMP_AB(val);	//alpha;
                }
                break;
            case bttBeta:
                if ( val >= beta )
                {
#ifdef DEBUG_ROOT
                    searchStats.ttCuts++;
#endif
                    se.move.packed = te->move.packed;
					updateKiller( ply, te->move );
					addHistory( depth, te->move );
                    return CLAMP_AB(val);	//beta;
                }
                break;
            }
        }
        else
        {
            if ( (te->type & 3) /*&& te->hash == h*/ )
            {
                hashmv.packed = te->move.packed;
            }
        }
        hashmv.packed = te->move.packed;
    }

#ifdef USE_TB
	if ( tbUsage && tbMen > 2 && (tbUsage == 1 ? ply == 1 : depth >= tbDepth) && board.numMen() <= tbMen )
	{
		i32 res = tbProbe( ply, board );
		if ( res != -1 )
		{
			tbHits++;
			return res;
		}
	}
#endif

#ifndef QS_ASAP
    if ( ply >= bmaxPly || depth <= 0 )
    {
        nodes--;		// FIXME: HACK!
//		if ( rh )
//			rh->push( board.hash(), board.flags().fiftyCounter == 0 );
        i32 res = qsearch( 0, ply, alpha, beta );
//		if ( rh )
//			rh->pop();
        return CLAMP_AB(res);
    }
#endif

    bool check = board.flags().check != 0;
    bool mateThreat = 0;

    i32 matEval;

    {
        matEval =
#ifdef USE_FUTIL_EVAL
            eval( board );
#else
            board.mat().dmat;
		{
			i32 score[2] = { matEval*10, matEval*10 };
			u64 all = board.bits[wall];
			while( all )
			{
				i8 pos = popLSB(all);
				i8 piece = board.pieces[ pos ] & 127;
				score[0] += bonusTablePSQ[0][ white ][ piece ][ pos ]; score[1] += bonusTablePSQ[1][ white ][ piece ][ pos ];
			}
			all = board.bits[ball];
			while( all )
			{
				i8 pos = popLSB(all);
				i8 piece = board.pieces[ pos ] & 127;
				score[0] -= bonusTablePSQ[0][ black ][ piece ][ pos ]; score[1] -= bonusTablePSQ[1][ black ][ piece ][ pos ];
			}
			const BitMat &bm = board.mat();
			i32 scale = 256 * (bm.tmat - 2200) / (6550 - 2200);
			if ( scale < 0 )
				scale = 0;
			else if ( scale > 256 )
				scale = 256;

			matEval = (score[1] + (scale * (score[0] - score[1]) >> 8))/10;
		}
        if ( board.flags().turn == black )
        {
            matEval = -matEval;
        }
#endif
    }

#ifdef USE_RAZORING
    if ( useRazoring && !check && depth <= 3 && abs(beta) < bmate - 1000 )
    {
//		i32 razEval = matEval == -bmate ? eval( board ) : matEval;
        i32 razEval = matEval;
        if ( razEval + razorMargin < beta )
        {

            i32 res = qsearch( 0, ply, alpha, beta );
            if ( res < beta )
            {
                return CLAMP_AB(res);
            }
        }
    }
//	matEval = razEval;
#endif

    if ( !check && usenull && depth > 1 && matEval >= beta - 325 && board.nullMoveOk() )
    {
        BitMove nm;
        nm.packed = 0;
        i32 R = 3 + (depth > 6 ? /*depth/4*/1 : 0);

        u64 undoBuf[ bundomax ];
        i32 undoMask = board.nullMove( undoBuf );

        if ( rh )
            rh->push( board.hash(), 1/*board.flags().fiftyCounter == 0*/ );

//		se.move.packed = 0;

#ifdef COPY_MOVE
        stack[ ply+1 ].board = board;
#endif
        i32 t = -isearchNull( (depth  - R - 1) << bdepthShift, ply+1, -beta, 0 );

        if ( rh )
            rh->pop();

        board.undo( undoMask, undoBuf );
        if ( t >= beta )
        {
#ifdef USE_NMR
            fdepth -= (4 << bdepthShift);
            if ( (fdepth >> bdepthShift) <= 0 )
            {
                return qsearch( 0, ply, alpha, beta );
            }
#else
            // null move cutoff!
            i32 verDepth = 5;
            if ( useNullVer && depth > verDepth )
            {
#ifdef DEBUG_ROOT
                searchStats.nullVers++;
#endif
                // null verification
                int tt = isearchNull( (depth - verDepth) << bdepthShift, ply, alpha, 0 );
                if ( tt >= beta )
                {
#ifdef DEBUG_ROOT
                    searchStats.nullCuts++;
#endif
#ifdef HASH_NULL
                    trans.store( h, ply, depth, bttBeta, t, nm );
#endif
                    return CLAMP_AB(t);//beta;
                }
            }
            else
            {
#ifdef DEBUG_ROOT
                searchStats.nullCuts++;
#endif
#ifdef HASH_NULL
                trans.store( h, ply, depth, bttBeta, t, nm );
#endif
                return CLAMP_AB(t);	//beta;
            }
#endif
        }
        else
        {
            if ( t == -bmate + (ply+2) )
            {
                // mate_threat
                // it seems better to extend...
                mateThreat = 1;
                /*				{
                					BitMove m0 = stack[ ply - 1 ].move;
                					BitMove m1 = se.threat;
                					BitBoard bb(board);
                					bb.dump();
                					char buf0[32], buf1[32];
                					m0.describeUCI( buf0 );
                					m1.describeUCI( buf1 );
                					logFmt("m0: %s m1: %s\n", buf0, buf1);
                				}*/
            }
        }
    }


    // IID at null window doesn't seem to help
    /*#ifdef USE_IID
    	// iid
    	if ( !hashmv.packed && depth > 2 )
    	{
    		isearch( fdepth - (2 << bdepthShift), ply, alpha, beta );
    		hashmv.packed = se.pv[ ply ].packed;
    	}
    #endif*/

    BitMove m;

	i32 best = -bmate;

    BitMoveGen mg( board, ply, *this, hashmv, check ? mgtEvasions : mgtCaptures );
    i32 vm = mg.count();

    i32 i;

#ifdef USE_SINGLEREPLY
    if ( !vm )
    {
        // stalemate or checkmate
        if ( check )
        {
            return CLAMP_AB(-bmate + ply);
        }
        return CLAMP_AB(0);		// stalemate...
    }

    if ( vm == 1 )
    {
        fdepth += 1 << bdepthShift;
    }
#endif

    u64 undoBuf[ bundomax ];

    i32 t = alpha;

    i32 didMoves = 0;
#ifdef SAFE_LMR
	i32 didQuietMoves = 0;
#endif

    u8 wasCheck = board.flags().check;
    while ( mg.next(m) )
    {
#ifdef SAFE_LMR
		if ( !(m.flags & (bcapture|bcastling)) )
			didQuietMoves++;
#endif
        didMoves++;
        se.move.packed = m.packed;
        if ( stopSearch )
            return CLAMP_AB(alpha);	// abort -- external flag set

        i32 ms = sgetMilisec();
        i32 dt = timeLimit - ms;
        if ( (dt < 0 && !mode.ponder) || (nodeLimit && nodes >= nodeLimit) )
        {
            stopSearch = true;
            return CLAMP_AB(alpha);	// abort -- time is up!
        }
        if ( !mode.native && ms - lastReport >= 2000 )
        {
            i32 dt = ms - startTicks;
            double nps = dt ? (double)nodes * 1000.0 / dt : 0;
            printf("info time %d nodes %lld nps %d hashfull %d\n",
                   dt, nodes, (int)floor(nps), trans.getFullnessPermill() );
            lastReport = ms;
        }

        bool isCheck =
#ifdef OLD_CHECKS
            0;
#else
            board.isCheck( m, mg.discovered );
#endif

        // handle extensions
        i32 newDepth = extend( fdepth - (1 << bdepthShift), board, m, mateThreat, 1, isCheck );
        i8 extended = newDepth > fdepth - (1 << bdepthShift) ? 1 : 0;

#if 1
		i32 me;
        if ( useFutility && depth <= 4 && !(extended|wasCheck)
#ifdef OLD_CHECKS
                && !board.isCheck( m, mg.discovered )
#endif
                && abs(alpha) < bmate - 1000
				&& (me = matEval + futMargin[depth] /*/(!didLMRMoves ? 1 : didLMRMoves)*/) < beta
				&& canReduceBefore(m, board)
           )
        {
			if ( me > best )
				best = me;
			if ( hashmv.packed != m.packed && !se.isKiller(m) )
			{
				continue;
			}
        }
#endif

#ifndef COPY_MOVE
        i32 undoMask = board.move( m, undoBuf, (i8)isCheck );
#else
        stack[ ply+1 ].board = board;
        stack[ ply+1 ].board.move( m );
#endif

        if ( rh )
#ifndef COPY_MOVE
            rh->push( board.hash(), board.flags().fiftyCounter == 0 );
#else
            rh->push( stack[ ply+1 ].board.hash(), stack[ ply+1 ].board.flags().fiftyCounter == 0 );
#endif

#ifdef USE_LMR
        if ( useLMR && /*ply > 0 &&*/ !extended && depth > LMR_DEPTH/*newDepth >= (LMR_REDUCTION << bdepthShift)*/ &&
                didLMRMoves >= LMR_NULL_MOVES && !wasCheck/*board.flags().check*/ && canReduce(m, board)//(!(m.flags & (bcapture|bcastling))) && !m.promo
                && !se.isKiller(m) )
        {
#ifdef DEBUG_ROOT
            searchStats.reductions++;
#endif
            t = - isearchNull( newDepth - (LMR_REDUCTION_FRAC * (didLMRMoves >= 2*LMR_NULL_MOVES ? 2 : 1)), ply+1, -alpha-1, useNull );
        }
        else t = alpha+1;
        if ( t > alpha )
        {
#endif

            // null-window search around alpha
            t = -isearchNull( newDepth, ply+1, -alpha-1, useNull );

#ifdef USE_LMR
        }
#endif

        if ( rh )
            rh->pop();

#ifndef COPY_MOVE
        board.undo( undoMask, undoBuf );
#endif

        if ( stopSearch )
            return CLAMP_AB(alpha);

		if ( t > best )
		{
			best = t;
			if ( t > alpha )
			{
				// new bestmove found
				alpha = t;

				updatePVHash( ply, m );
#ifdef USE_MATEKILLER
				if ( t == bmate - ply - 1 )
				{
					se.mateKiller = m;
				}
#endif
				if ( alpha >= beta )
				{
					//				updatePV( ply, m );
					/*				if ( oalpha + 1 != beta )
					{
					updatePV( ply, m );
					}*/
					// cutoff!
#ifdef DEBUG_CUTOFF
					cutoffMoves += didMoves;
					cutoffCount++;
#endif
					updateKiller( ply, m );
					addHistory( depth, m );
#ifdef USE_COUNTER
					if ( !(m.flags & (bcapture|bcastling)) && !m.promo )
					{
						hist.counter[board.flags().turn][ stack[ply-1].move.from ][ stack[ply-1].move.to ].packed = m.packed;
					}
#endif
					break;
				}
			}
		}
    }

    if ( !didMoves )
    {
        // FIXME: assume mate or stalemate!
        return CLAMP_AB( check ? -bmate + ply : 0 );
    }

	best = CLAMP_AB(best);

    trans.store( h, ply, depth, best <= oalpha ? bttAlpha : /*best >= beta ?*/ bttBeta /*: bttFull*/,
                 best, se.pv[ ply ] );

    return best;
}

// FIXME: there's a bug in moveordering somewhere
// I saw it searching for mate while failing low at 1st move with a suboptimal move (!?why?!)
// (maybe it was IID at root?! -- removed!) (reenabled. Think it was a bug width trans_cutoff at root?)
// or maybe with BitSearch::advance()? ??will clear search stack at the start of each search??
i32 BitSearch::isearchRoot( i32 fdepth, i32 alpha, i32 beta )
{
    // clamp first
    if ( alpha < -bmate )
        alpha = -bmate;
    if ( beta > bmate )
        beta = bmate;
    selDepth = 0;
    i32 oalpha = alpha;
    i32 depth = (fdepth + bdepthConst) >> bdepthShift;
    i32 ply = 0;//, maxPly = bmaxPly;///2*depth + 2;
    BitSearchStackEntry &se = stack[ ply ];
#ifdef COPY_MOVE
    se.board = this->board;
#endif
    initPly( ply );

/*    if ( board.isDraw() )
    {
        drawCuts++;
        return CLAMP_AB( DRAW_MAT );
    }*/

    const u64 &h = board.bits[ bhash ];

/*    i32 repCnt = rh ? rh->get( h ) : 0;
    if ( repCnt >= 2 && ply > 0 )
    {
        drawCuts++;
        return CLAMP_AB( DRAW_REP );
    }

#ifdef NEW_MDP
    // FIXME: hope this help to fix a very random bug where it returns best null
    // (happened once when score was +M1!)
    if ( depth > 1 )
    {
        alpha = std::max( alpha, -bmate + ply );
        beta = std::min( beta, bmate - ply - 1 );
        if ( alpha >= beta )
            return alpha;
    }
#else
    if ( alpha >= bmate - bmaxPV )
    {
        // mate distance pruning!
        if ( ply > 0 && ply > bmate - alpha + 1 )
            return alpha;
    }
    if ( beta <= -bmate + bmaxPV )
    {
        // mate distance pruning!
        if ( ply > 0 && ply > beta + bmate + 1 )
            return beta;
    }
#endif
*/
    BitMove hashmv;
    hashmv.packed = 0;

    const BitTransEntry *te = trans.entry( h );
    if ( te && multiPV <= 1 )
    {
        if ( (te->type & 3) && te->depth >= depth && te->hash == h )
        {
            // potential trans_table hit!
            hashmv.packed = te->move.packed;
            i32 val = te->getValue( ply );
            switch ( te->type & 3 )
            {
            case bttFull:
#ifdef DEBUG_ROOT
                searchStats.ttCuts++;
#endif
                se.move.packed = te->move.packed;
                updatePVHash( ply, te->move );
                setRootScore( te->move, CLAMP_AB(val) );
                if ( !maxTime || depth==1 )
                    sendPVToGUI( depth, val, oalpha, beta );
                return CLAMP_AB(val);
            case bttAlpha:
                if ( val <= alpha )
                {
#ifdef DEBUG_ROOT
                    searchStats.ttCuts++;
#endif
                    se.move.packed = te->move.packed;
                    updatePVHash( ply, te->move );
                    setRootScore( te->move, alpha );
                    if ( !maxTime || depth==1 )
                        sendPVToGUI( depth, alpha, oalpha, beta );
                    return CLAMP_AB( val );	//alpha;
                }
                break;
            case bttBeta:
                if ( val >= beta )
                {
#ifdef DEBUG_ROOT
                    searchStats.ttCuts++;
#endif
                    se.move.packed = te->move.packed;
                    updatePVHash( ply, te->move );
					updateKiller( ply, te->move );
					addHistory( depth, te->move );
                    setRootScore( te->move, beta );
                    if ( !maxTime || depth==1 )
                        sendPVToGUI( depth, beta, oalpha, beta );
                    return CLAMP_AB( val );	//beta;
                }
                break;
            }
        }
        else if ( (te->type & 3) && te->hash == h )
        {
            hashmv.packed = te->move.packed;
            if ( !se.pv[0].packed )
            {
                se.pv[0].packed = hashmv.packed;
            }
        }
    }

    ASSERT( depth > 0 );

#ifdef USE_IID
    // iid
    if ( !hashmv.packed && depth > 2/*2*/ )
    {
#ifdef DEBUG_ROOT
        searchStats.iids++;
#endif
        isearch( fdepth - (2 << bdepthShift), ply, alpha, beta );
        hashmv.packed = stack[ ply ].pv[ ply ].packed;
    }
#endif

    bool check = board.flags().check != 0;

    i32 i;
    if ( !rvm )
    {
        // stalemate or checkmate
        if ( check )
        {
            return CLAMP_AB(-bmate + ply);
        }
        return CLAMP_AB(0);		// stalemate...
    }

#ifdef USE_SINGLEREPLY
    if ( rvm == 1 )
    {
        fdepth += 1 << bdepthShift;
    }
#endif

    // sort root moves
    {
        i32 i, j;
        for (i=0; i<rvm; i++)
        {
            if ( rs[i] != -bmate )
                break;
        }
        if ( i>=rvm )
        {
            for (i=0; i<rvm; i++)
            {
                rn[i] = 0;
            }
            // unsorted root moves -- try to help a bit...
            for (i=bkillers-1; i>=0; i--)
            {
                makeFirstRoot( se.killers[ i ], 1 );
            }
            makeFirstRoot( se.mateKiller );
            makeFirstRoot( hashmv );
//			makeFirstRoot( se.pv[ ply ] );
        }

        for (i=0; i<rvm; i++)
        {
            for (j=i+1; j < rvm; j++)
            {
                if ( rs[i] < rs[j] || (rs[i] == rs[j] && rn[i] < rn[j]) )
                {
                    std::swap( rm[i], rm[j] );
                    std::swap( rs[i], rs[j] );
                    std::swap( rn[i], rn[j] );
                }
            }
            rs[i] = -bmate;
            rn[i] = 0;
        }
    }

#ifndef COPY_MOVE
    u64 undoBuf[ bundomax ];
#endif

    bool havepv = false;

    i32 t = alpha;

    BitMove msearched;
    msearched.packed = 0;

    bool avoidingBlunder = 0;				// 1 if we are searching for a move which is better than a blunder

    enum
    {
        blunderDelta = 30,						// 30 cp should do	(originally: 50, 25)
        noBlunderDelta = 10						// 10 cp should do
    };

    i32 otimeLimit = timeLimit;				// save old time limit

    i32 didMoves = 0;
//	BitMove moves[ bmaxMoves ];

#ifdef DEBUG_ROOT
    logFmt("ROOT_DEPTH = %d\n", depth);
#endif

    u64 discovered = board.discoveredCheckers();

	multiPVAlpha = alpha;

	i32 best = -bmate;

    for ( i=0; i<rvm; i++ )
    {
        moves[ didMoves++ ].packed = rm[i].packed;
        se.move.packed = rm[i].packed;

		if ( multiPV > 1 )
		{
			best = alpha = multiPVAlpha;
			t = alpha+1;
		}

#ifdef DEBUG_ROOT
        memset( &searchStats, 0, sizeof(searchStats) );
        char buf[32];
        rm[i].describeSAN( board, buf );
        logFmt("root_searching %s\n", buf );
        /*		if ( depth > 6 && strcmp( buf, "d3" ) == 0 )
        		{
        			logFmt("");
        		}*/
        i32 root_ms = getMilisec();
#endif

        i64 onodes = nodes;
        if ( stopSearch )
            return CLAMP_AB(alpha);	// abort -- external flag set

        i32 dt = timeLimit - sgetMilisec();
        if ( (dt < 0 && !mode.ponder) || (nodeLimit && nodes >= nodeLimit) )
        {
            stopSearch = true;
            return CLAMP_AB(alpha);	// abort -- time is up!
        }

        if ( !quiet )
        {
            i32 ms = getMilisec();
            if ( i == 0 || ms - currMoveTicks >= 250 )
            {
//				currMoveTicks += 250;
                char buf[32];
                if ( !mode.native )
                {
                    rm[i].describeUCI( buf );
                }
                i32 dt = ms - startTicks;
                double nps = dt ? (double)nodes * 1000.0 / dt : 0;
                if ( mode.native )
                {
                    if ( i > 0 )
                    {
                        nativeCallback( depth, i, rvm, stack[0].pv[0], rm[i], alpha, i > 0 );
                    }
                }
                else
                {
                    printf("info depth %d currmove %s currmovenumber %d time %d nodes %lld nps %d hashfull %d\n",
                           depth, buf, 1+i, dt, nodes, (int)floor(nps), trans.getFullnessPermill());
                }

                /*			rm[i].describeSAN( board, buf );
                logFmt("%s ", buf);*/
//				if ( i == 0 )
//				{
                currMoveTicks = ms;
//				}
            }
        }

        bool isCheck =
#ifdef OLD_CHECKS
            0;
#else
            board.isCheck( rm[i], discovered );
#endif

        // handle extensions
        i32 newDepth = extend( fdepth - (1 << bdepthShift), board, rm[i], 0, 0, isCheck );
        u8 extended = newDepth > fdepth - (1 << bdepthShift) ? 1 : 0;

#ifndef COPY_MOVE
        i32 undoMask = board.move( rm[i], undoBuf, (i8)isCheck );
#else
        stack[ ply+1 ].board = se.board;
        stack[ ply+1 ].board.move( rm[i] );
#endif

        if ( rh )
            rh->push( board.hash(), board.flags().fiftyCounter == 0 );

#ifdef USE_LMR_ROOT	// never at rootnode!
#ifdef USE_LMR
        if ( useLMR && /*ply > 0 &&*/ !extended && depth > LMR_DEPTH/*newDepth >= (LMR_REDUCTION << bdepthShift)*/ &&
                didMoves >= LMR_MOVES && !board.flags().check && canReduce(rm[i], board)//(!(rm[i].flags & (bcapture|bcastling))) && !rm[i].promo
                && !se.isKiller( rm[i] ) )
        {
#ifdef DEBUG_ROOT
            searchStats.reductions++;
#endif
            t = - isearchNull( newDepth - (LMR_REDUCTION << bdepthShift), ply+1, -alpha-1, useNull );
        }
        else t = alpha+1;
        if ( t > alpha )
        {
#endif
#endif

#if 0
			if (rm[i].from == D8 && rm[i].to == D3)
			{
                t = -isearch( newDepth, ply+1, -beta, -alpha/*-alpha*/ );		// this finds it
				printf("d8d3 score: %d; alpha = %d, beta = %d\n", t, alpha, beta);
			}
			else
#endif
			{

            if ( i >= multiPV )
            {
                // first try a null-window search around alpha
                t = -isearchNull( newDepth, ply+1, -alpha-1, useNull );
//                t = -isearch( newDepth, ply+1, -alpha-1, -alpha );
            }

            if ( i < multiPV || t > alpha /*&& t < beta*/ )
            {
                // either we didn't find the pv yet or we have to research
                t = -isearch( newDepth, ply+1, -beta, -alpha );
            }

			}
#ifdef USE_LMR_ROOT	// never at rootnode!
#ifdef USE_LMR
        }
#endif
#endif

        if ( rh )
            rh->pop();

#ifndef COPY_MOVE
        board.undo( undoMask, undoBuf );
#endif

        rn[i] = nodes - onodes;

#ifdef DEBUG_ROOT
        root_ms = getMilisec() - root_ms;

        logFmt("%I64d nodes, %d ms, score = %d\n", rn[i], root_ms, t );
        dumpStats();
        {
            char buf[32];
            rm[i].describeSAN( board, buf );
            logFmt("line: %s ", buf);
            // dump_pv!
            BitBoard bb( board );
            bb.move( rm[i] );
            i32 j;
            bool lupHash = 0;
            for (j=ply+1; j<bmaxPV; j++)
            {
                BitMove bm;
                if ( lupHash )
                {
                    BitTransEntry *e = trans.entry( bb.hash() );
                    if ( !e )
                    {
                        break;
                    }
                    bm = e->move;
                }
                else
                {
                    bm = stack[ ply+1 ].pv[ j ];
                }
                if ( bm.from == bm.to )
                {
                    if ( lupHash )
                    {
                        break;
                    }
                    lupHash = 1;
                    j--;
                    continue;
                }
                bm.describeSAN( bb, buf );
                logFmt("%s ", buf);
                bb.move( bm );
            }
            logFmt("\n");
        }
#endif

#if 0	// FIXME: ?doesn't seem to work?
		if ( multiPV <=1 && i == 0 && t <= alpha )
		{
			se.pv[ply].packed = se.move.packed;
			se.pv[ply+1].packed = 0;
			sendPVToGUI( depth, t, alpha, beta );
			return CLAMP_AB(t);
		}
#endif

        if ( stopSearch )
            return CLAMP_AB(alpha);

		if ( t > best )
		{
			best = t;
			if ( t > alpha )
			{
				// new bestmove found
				////			havepv = true;			// for some reason this is stronger! (MS compiler bug?!)

				updatePV( ply, rm[i] );
				sendPVToGUI( depth, t, oalpha, beta );

				alpha = t;

				rs[i] = t;

#ifdef USE_AVOIDBLUNDER
				if ( !absLimit )
				{
					if ( !avoidingBlunder && maxTime && lastRootScore != -bmate && t <= lastRootScore - blunderDelta )
					{
						// give more time to avoid playing a blunder, but up to 1.5*thinklimit
						timeLimit = sgetMilisec() + 3*maxTime/2;//0x3fffffff;
						avoidingBlunder = 1;
						//					printf("#avoidingBlunder!\n");
					}
					else
					{
						if ( avoidingBlunder && t >= lastRootScore - noBlunderDelta )
						{
							// assuming blunder avoided -- stop search if time is up
							timeLimit = otimeLimit;
							i32 dt = timeLimit - sgetMilisec();
							if ( dt < 0 )
							{
								break;
							}
						}
					}
				}
#endif

#ifdef USE_MATEKILLER
				if ( t == bmate - ply - 1 )
				{
					se.mateKiller = rm[i];
				}
#endif
				if ( alpha >= beta )
				{
#ifdef DEBUG_CUTOFF
					cutoffMoves += didMoves;
					cutoffCount++;
#endif
					// cutoff!
					updateKiller( ply, rm[i] );
					addHistory( depth, rm[i] );
					break;
				}
			}
		}
    }

	if ( multiPV > 1 )
	{
		ASSERT( multiPVData[ multiPVSort[0] ].move.packed );
		se.pv[0].packed = multiPVData[ multiPVSort[0] ].move.packed;
		se.pv[1].packed = multiPVData[ multiPVSort[0] ].ponder.packed;
		best = CLAMP_AB( multiPVData[ multiPVSort[0] ].score );
	}

    if ( best <= oalpha )
    {
        sendPVToGUI( depth, best, oalpha, beta );
    }

    if ( se.pv[ply].from != se.pv[ply].to )
    {
        storePV( depth );

        trans.store( h, ply, depth, best <= oalpha ? bttAlpha : best >= beta ? bttBeta : bttFull,
                     best, se.pv[ ply ] );
    }

    if ( avoidingBlunder )
    {
        timeLimit = otimeLimit;
        i32 dt = timeLimit - sgetMilisec();
        if ( dt < 0 && !mode.ponder )
        {
            stopSearch = 1;
        }
    }

    if (!se.pv[0].packed )
    {
        logFmt("FATAL ERROR: no pv move! stopSearch = %d\n", stopSearch ? 1 : 0);
    }

#ifdef DEBUG_CUTOFF
	printf("everage cutoff on move %0.2lf\n", (double)cutoffMoves / cutoffCount );
#endif

    return best;
}

void BitSearch::reconstructPV()
{
    BitBoard bb( board );
    u64 pins = bb.pinned();
    i32 i;
    for (i=0; i<bmaxPV; i++)
    {
        if ( !stack[0].pv[i].packed )
        {
            break;
        }
        // FIXME: this sucks but it happens rarely (endgame), sometimes the pv is screwed, but it shouldn't be!
        if ( !bb.isLegal( stack[0].pv[i], &pins ) )
        {
            break;
        }
        bb.move( stack[0].pv[i] );
    }
    for (; i<bmaxPV; i++)
    {
        BitTransEntry *e = trans.entry( bb.hash() );
        if ( !e || !e->move.packed
#ifdef VALIDATE_HASHMV
                || !bb.isLegal( e->move, &pins )
#endif
           )
        {
            break;
        }
        stack[0].pv[i] = e->move;
        bb.move( e->move );
    }
}

// alternate version
void BitSearch::getBestLine( PVMoves *pv )
{
    if ( !pv )
    {
        return;
    }
    reconstructPV();
    i32 turn = board.flags().turn;
    Board b;
    boardFromBitBoard( b, board );
    (*pv)[0].m.packed = 0;
    i32 i;
    BitSearchStackEntry &se = stack[ 0 ];
    BitBoard tb( board );
    u64 hashes[ bmaxPV ];
    // FIXME: assume bmaxPV <= maxPV (old_const)
    for (i=0; i<bmaxPV; i++)
    {
        if ( !se.pv[i].packed )
            break;
        hashes[i] = tb.hash();
        Move sm = getStdMove( tb, se.pv[i] );
        Move m[ maxMoves ];
        i32 vm = b.moves( m, turn );
        i32 j;
        for (j=0; j<vm; j++)
        {
            if ( m[j].equalUCI( sm ) )
            {
                break;
            }
        }
        if ( j >= vm )
        {
            /*			Board ob;
            			boardFromBitBoard( ob, tb );
            			ob.dump();
            			b.dump();*/
            break;
        }
        (*pv)[i].m.packed = m[j].packed;
        (*pv)[i].score = 0;
        b.move( m[j] );
        turn ^= 1;
        tb.move( se.pv[i] );
        u64 h = tb.hash();
        for ( j=i-1; j>=0; j-=2 )
        {
            if ( hashes[j] == h )
                break;
        }
        if ( j >= 0 )
            break;
    }
    if ( i >= bmaxPV )
        i = bmaxPV-1;
    (*pv)[i].m.packed = 0;
    (*pv)[i].score = 0;
}

// useSAN: true => SAN, otherwise UCI style
void BitSearch::getBestLine( String &line, bool useSAN )
{
    reconstructPV();

    BitBoard tb( board );

    line.clear();

    i32 i;
    BitSearchStackEntry &se = stack[ 0 ];
    u64 hashes[ bmaxPV ];
    for (i=0; i<bmaxPV; i++)
    {
        hashes[i] = tb.hash();
        if ( !se.pv[i].packed )
            break;
        BitMove m[ bmaxMoves ];
        i32 vm = tb.moves( m );
        i32 j;
        for (j=0; j<vm; j++)
        {
            if ( m[j].equal( se.pv[i] ) )
                break;
        }
        if ( j >= vm )
        {
            // bad bestpv!
            se.pv[i].packed = 0;
            break;
        }
        char buf[32];
        if ( useSAN )
        {
            m[j].describeSAN( tb, buf );
        }
        else
        {
            m[j].describeUCI( buf );
        }
        if ( !line.empty() )
            line += " ";
        line += buf;
        tb.move( m[j] );
        u64 h = tb.hash();
        for (j=i-1; j>=0; j-=2)
        {
            if ( hashes[j] == h )
                break;
        }
        if ( j >= 0 )
            break;
    }
}

i32 BitSearch::search( BitSearchMode mode )
{
////	rh = 0;		// FIXME: try not using rephash! (FOR DEBUGGING REPETITIONS ONLY!)

    ::counter = 0;
    i32 ms = getMilisec();

    stopSearch = false;
    startTicks = currMoveTicks = lastReport = ms;
    i32 timeLimit_ = mode.maxTime;
    maxTime = mode.maxTime;
	absLimit = mode.absLimit;
	multiPV = mode.multiPV;
	if ( multiPV < 1 )
		multiPV = 1;
	else
	{
		i32 i;
		for (i=0; i<multiPV; i++)
		{
			multiPVData[i].line = String();
			multiPVData[i].move.packed = 0;
			multiPVData[i].ponder.packed = 0;
			multiPVData[i].score = 0;
			multiPVData[i].depth = 0;
			multiPVData[i].selDepth = 0;
			multiPVSort[i] = i;
		}
	}
    if ( timeLimit_ )
    {
        timeLimit = ms + timeLimit_;
    } else timeLimit = ms + 0x3fffffff;
    i32 itl = ms + 0x3fffffff;

//	i64 us = getMicrosec();

    this->mode = mode;

    trans.newSearch();

    i32 res;

    drawCuts = 0;
    nodes = 0;
    qnodes = 0;
    evals = 0;
	tbHits = 0;
    nodeLimit = 0;
    selDepth = 0;

    i32 bestValue = 0;

    i32 i, idepth;
    i32 otl = timeLimit;

    bool searchingSubset = 0;

    if ( mode.searchMoves.empty() )
    {
        rvm = board.moves( rm );
    }
    else
    {
        rvm = board.moves( rm );
        i32 orvm = rvm;
        i32 i;
        std::vector< BitMove > newmv;
        for (i=0; i<rvm; i++)
        {
            i32 j;
            for (j=0; j<mode.searchMoves.size(); j++)
            {
                if ( mode.searchMoves[j].equal( rm[i] ) )
                    break;		// found!
            }
            if ( j < mode.searchMoves.size() )
            {
                // add_new!
                i32 k;
                for (k=0; k<newmv.size(); k++)
                {
                    if ( mode.searchMoves[j].equal( newmv[k] ) )
                        break;			// already_here!
                }
                if ( k >= newmv.size() )
                {
                    newmv.push_back( mode.searchMoves[j] );
                }
            }
        }
        if ( newmv.empty() )
        {
//			logFmt("warning: no valid moves to search, searching all moves!\n");
        }
        else
        {
            rvm = newmv.size();
            memcpy( rm, &newmv[0], rvm * sizeof(BitMove) );
        }
        if ( rvm != orvm )
        {
            // FIXME: better!
            trans.clear();
            searchingSubset = 1;
        }
    }

    for (i=0; i<rvm; i++)
    {
#if 0
        // new: initialize using qsearch (=>hashmv first!)
        // FIXME: buggy! crashes!
        u64 undoBuf[ bundomax ];
        i32 undo = board.move( rm[i], undoBuf );
        rs[i] = -qsearch(0, 0);
        board.undo( undo, undoBuf );
#endif
        rs[i] = -bmate;
        rn[i] = 0;
    }


    if ( mode.maxDepth < 0 )
        mode.maxDepth = 1;			// at least 1 ply always!
    if ( mode.maxNodes < 0 )
        mode.maxNodes = 0;			// don't allow invalid node counts!

    bool useasp = multiPV <= 1;		// default: only use aspiration windows when not in k-best mode
    lastRootScore = -bmate;			// last ply root score
////	stack[0].pv[0].packed = 0;		// FIXME: ok?!
    bool aspiteration = 0;			// use asp_search for this (=next) iteration?

    i32 ticksPerMove = 0;				// ticks per move (last search)

    clearSlots();

    for ( idepth = 1; idepth <= mode.maxDepth; idepth++ )
    {
        i32 lastStart = getMilisec();
        if ( idepth > 1 && mode.maxTime && !mode.ponder )
        {
            i32 tc = getMilisec();
            tc -= startTicks;
#if 1
            if ( ticksPerMove * 2 * rvm > mode.maxTime - tc )
            {
                // don't search any further!
                break;
            }
#endif
        }
        /*		if ( !quiet )
        		{
        			printf("info depth %d\n", idepth);
        		}*/
        timeLimit = idepth == 1 ? itl : otl;
        nodeLimit = idepth == 1 ? 0 : mode.maxNodes;
        i32 a = -bmate;
        i32 b = +bmate;
        i32 aspWindow = 15;
        if ( useasp && idepth > 1 && aspiteration )
        {
            // use aspiration window!
            // aspiration loop
            a = bestValue - aspWindow;
            b = bestValue + aspWindow;
            i32 lastFail = -1;
            i32 lasta = 0;
            i32 lastb = 0;
			// FIXME: a bug somewhere?!
			// it often happens that a score drops for one ply then recovers back
			// with aspiration search, when we drop from mate score this means huge slowdown
			// it might be (besides other bugs) a problem which always occurs with fail-lows. way too slow!
			if ( abs(bestValue) >= bmate - 1000 )
			{
				// use full window in this case
				a = -bmate;
				b = +bmate;
			}
            for (;;)
            {
                if ( a < -bmate )
                    a = -bmate;
                if ( b > +bmate )
                    b = +bmate;
                if ( (a == lasta && b == lastb) || a == b )
                {
                    a = -bmate;
                    b = +bmate;
                }
#ifdef DEBUG
                printf("depth: %d, aspwindow: %d .. %d\n", idepth, a, b );
#endif
                res = isearchRoot( idepth << bdepthShift, a, b );
                lasta = a;
                lastb = b;
                if ( stopSearch )
                    break;
                if ( res > a && res < b )
                {
                    break;
                }
                if ( a == -bmate && b == +bmate )
                {
                    break;
                }
                if ( res <= a )
                {
                    if ( lastFail == 1 )
                    {
//						printf("info ERROR: faillow after failhigh!\n");
//						logFmt("info ERROR: faillow after failhigh!\n");
                    }
                    lastFail = 0;
                }
                else
                {
                    if ( lastFail == 0 )
                    {
//						printf("info ERROR: failhigh after faillow!\n");
//						logFmt("info ERROR: failhigh after faillow!\n");
                    }
                    lastFail = 1;
                }
                if ( res <= a )
                {
                    a = res - (aspWindow <<= 1);
                }
                else
                {
                    b = res + (aspWindow <<= 1);
                }
                /*				a = -bmate;
                				b = bmate;*/
            }
            if ( stopSearch )
                break;
        }
        else
        {
            res = isearchRoot( idepth << bdepthShift, a, b );
        }
        if ( useasp )
        {
            aspiteration = 1;
        }
        if ( !stopSearch )
        {
            bestValue = res;
            lastRootScore = res;
        }
        else break;
        if ( mode.mateSearch > 0 && res >= bmate - bmaxPV )
        {
            if ( (bmate - res)/2 + 1 == mode.mateSearch )
                break;
        }

        ticksPerMove = (getMilisec() - lastStart) / (rvm ? rvm : 1 );
    }

#ifdef DEBUG
    {
        String bl;
        getBestLine( bl );
        logFmt("search finished. bestline = %s\n", bl.ansi());
        logFmt("mode.native = %d\n", mode.native != 0 ? 1 : 0 );
        logFmt("quiet flag = %d\n", quiet ? 1 : 0 );
    }
#endif

    if ( mode.native )
    {
        BitMove nullm;
        nullm.packed = 0;
        nativeCallback( idepth, -1, -1, stack[0].pv[0], nullm, res );
    }
    else
    {
        String line;
        getBestLine( line );
        char buf[32], pbuf[32];

        ASSERT( stack[0].pv[0].packed );

        if ( !quiet )
        {
            i32 dt = getMilisec() - startTicks;
            double nps = dt ? (double)nodes * 1000.0 / dt : 0;
            printf("info time %d nodes %lld nps %d hashfull %d\n",
                   dt, nodes, (int)floor(nps), trans.getFullnessPermill());
        }

        stack[0].pv[0].describeUCI( buf );

//	bool showBest = 1;
        if ( this->mode.ponder )
        {
            // wait for stop or ponderhit!
            while ( !stopSearch && this->mode.ponder )
            {
                Thread::sleep(1);
            }
//            if ( stopSearch )
//	      showBest = 0;
        }

        if ( !quiet /*&& showBest*/ )
        {
            if ( stack[0].pv[1].packed )
            {
                stack[0].pv[1].describeUCI( pbuf );
                printf("bestmove %s ponder %s\n", buf, pbuf);
#ifdef DEBUG
                logFmt("bestmove %s ponder %s\n", buf, pbuf);
#endif
            }
            else
            {
                printf("bestmove %s\n", buf);
#ifdef DEBUG
                logFmt("bestmove %s\n", buf);
#endif
            }
        }
    }

    lastScore = bestValue;

    res = bestValue;

    /*	us = getMicrosec() - us;
    	logFmt("search (%d nodes, %d qnodes, %d evals, %d drawcuts) took %0.2lf sec\n",
    		nodes, qnodes, evals, drawCuts, (double)us / 1000000.0);*/

    if ( searchingSubset )
    {
        // FIXME: better!
        trans.clear();
    }

    return res;
}

// replace current evaluator with a new one
// owned: owned_flag (delete when done)
bool BitSearch::setEvaluator( BitEval *evl, bool owned )
{
    if ( !evl )
    {
        return 0;
    }
    if ( owneval )
    {
        delete evaluator;
    }
    evaluator = evl;
    owneval = owned;
    return 1;
}

// tell the search the we have a ponderhit
void BitSearch::ponderHit()
{
    mode.ponder = 0;
}

// 0 = draw, otherwise mate
// -1 = failure
i32 BitSearch::tbProbe( i32 ply, const BitBoard &board )
{
	if ( !tb )
		return -1;
	i32 res = tb->probe( board, ply );
	if ( res == -1 )
	{
		tbMen--;
		printf("info string tb max men set to %d\n", tbMen);
	}
	return res;
}

static AutoBitParameter _ppars[] =
{
	AutoBitParameter("DeltaMarginCP", &deltaMargin, 0, 2000 ),
	AutoBitParameter("FutilityMargin1CP", &futMargin[1], 0, 2000 ),
	AutoBitParameter("FutilityMargin2CP", &futMargin[2], 0, 2000 ),
	AutoBitParameter("FutilityMargin3CP", &futMargin[3], 0, 2000 ),
	AutoBitParameter("FutilityMargin4CP", &futMargin[4], 0, 2000 ),
	AutoBitParameter("RazorMarginCP", &razorMargin, 0, 2000 ),
	AutoBitParameter("LMRMovesPV", &LMR_MOVES, 0, 256 ),
	AutoBitParameter("LMRMovesNonPV", &LMR_NULL_MOVES, 0, 256 )
};
