//retrieve best move;
    if(depth==IdDepth) //TODO check whether I could do this from the callee
        bestMove=actualbtt.BestMove();

    return g;
}

int Thinker::MTD(int f, int depth)
{
    int g=f;
    int upperbound=+infinity;
    int lowerbound=-infinity;
    int beta;
    do
    {
        if(g==lowerbound)
            beta=g+1;
        else
            beta=g;
        g=AlphaBeta(beta-1, beta, depth);
        if(g<beta)
            upperbound=g;
        else
            lowerbound=g;
        //assert(lowerbound<=upperbound);
    }while(lowerbound!=upperbound);

    return g;
}

void Thinker::Think()
{
    assert(actualb.empties==Count(empty));
    assert(actualb.blacks==Count(black));
    
    //first move
    if(actualb.CountEmpty()==60)
    {
        bestMove=firstmoves[rand() % 4];
        _lastbestMove=bestMove;
        return;
    }

    //book lookup
    bestMove=_book.AdvisedMove(actualb);
    _lastbestMove=bestMove;
    if(-1!=TTBoard::Persil[bestMove])
        return;


    //allocate time for this search
    _timescheduler.AllocTarget(actualb.CountEmpty());

    int startDepth=1;

    bestMove=-1;
    IsLegalMove legal; 
    int dir;
    TTBoard *prev=_ttable.Retrieve();
    if(prev!=NULL && prev->GetDepth()!=0 
       && actualb.table[prev->BestMove()]==empty
       && legal(prev->BestMove(), dir))
    {
        //assert(prev->HasExact());
        startDepth=prev->GetDepth()+1;
        gamevalue=prev->Value();

        bestMove=prev->BestMove();
        _lastbestMove=bestMove;

        //low on time situations
        if(MSecRemaining()<=3)
        {
            if(bestMove!=-1)
                return;
        }
        if(_isdoublemove && 2*_avaible_time<=_init_totaltime)
        {
            if(bestMove!=-1)
            {
                _isdoublemove=false;
                return;
            }
        }

    }
    else
        gamevalue=NaiveBestMoveSearch();

#if defined _ENDGAME_TEST_

    if(actualb.CountEmpty()<=20)
        if(actualb.CountEmpty()>17)
        {
            IdDepth=actualb.CountEmpty();
            gamevalue=AlphaBeta(-1, 1, actualb.CountEmpty());
            _lastbestMove=bestMove;
            return;
        }
        else
            if(actualb.CountEmpty()>10) //stupid (best move isn't captured in endgame)
            {
                IdDepth=actualb.CountEmpty();
                gamevalue=AlphaBeta(-infinity, infinity, actualb.CountEmpty());
                _lastbestMove=bestMove;
                return;
            }

#endif

    //can we play perfectly? 
    bool perfect_play=(gamevalue>63 || gamevalue<-63);
     
    //do iterative deepening
    unsigned int maxdepth=MAXDEPTH;
    if(maxdepth > actualb.CountEmpty())
        maxdepth = actualb.CountEmpty(); 
    
    int prevvalue=gamevalue;
    for(IdDepth=startDepth; IdDepth<=maxdepth; IdDepth++)
    {
        actualbtt.SetDepth(0);
        int tmp=MTD(prevvalue, IdDepth);
        prevvalue=gamevalue ; gamevalue=tmp; _lastbestMove=bestMove;
        if(!perfect_play)
        {
            if(gamevalue>63 || gamevalue<-63 || _timescheduler.TimeIsUp(IdDepth))
            {
                IdDepth++; break;
            }
        }
        else
        {
            if(IdDepth==actualb.CountEmpty() ||_timescheduler.TimeIsUp(IdDepth))
            {
                IdDepth++; break;
            }
        }
    }
    IdDepth--;
    _ttable.AdvanceSearchStamp();
}


void Thinker::TTChangeSize(unsigned int logsize)
{
    _ttable.ReAlloc(logsize);
}

unsigned int Thinker::TTLogSize()
{
    return _ttable.LogSize();
}


void Thinker::SetTotalTime(unsigned int min_per_game)
{
    _avaible_time=min_per_game*1000*60;
    _init_totaltime=_avaible_time;
}

unsigned int Thinker::MSecRemaining() 
{
    return _timescheduler.MSecRemaining();
}


void Thinker::DispatchResultsToGui()
{
    //stop execution until controller says GO!
    _event.RedLight();
    AddMove(bestMove, actualb.isblacksturn);
    newBoard=actualb;
    GuiMoveExecuter(newBoard, bestMove);

    //check if I can make another move
    Board tmp=newBoard;
    MoveEnumerator opponentmoves(tmp);
    if(opponentmoves.Empty())
    {
        Board tmp2=newBoard;
        tmp2.isblacksturn=!tmp2.isblacksturn;
        MoveEnumerator mymoves(tmp2);
        if(mymoves.Empty())
        {
            //game over
            ::SendMessage(_hwnd, WM_CALC_DONE, 0, 0);
            return;
        }
        //yes I can take another move 
        Go();
        newBoard.isblacksturn=!newBoard.isblacksturn;
        _isdoublemove=true;
        ::SendMessage(_hwnd, WM_UPDATE_VIEW, 0, 0);
        return;
    }
    //say: We are Done!
    ::SendMessage(_hwnd, WM_CALC_DONE, 0, 0);
}


int Thinker::Hint()
{
    assert(_thinking==false);

    if(newBoard.CountEmpty()==60)
        return firstmoves[rand() % 4];
    
    Board tmp=newBoard;
    actualb=newBoard;
    InitBoards();

    int hintmove=-1;

    if(!_book.OutOfBook())
    {
        hintmove=_book.AdvisedMove(actualb);
        if(-1!=TTBoard::Persil[hintmove])
        {
            newBoard=tmp;
            InitBoards();
            return hintmove;
        }
    }

    TTBoard *prev=_ttable.Retrieve();
    IsLegalMove legal; 
    int dir;
    hintmove=-1;
    if(prev!=NULL 
        && actualb.table[prev->BestMove()]==empty
        && legal(prev->BestMove(), dir))
        hintmove=prev->BestMove();
    newBoard=tmp;
    InitBoards();
    return hintmove;
    //add a shallow search here
}


int Thinker::NaiveBestMoveSearch()
{
    bool ismaxplayer=actualb.isblacksturn;
    IsLegalMove legal;
    int dir;
    UndoData udata;
    int act_best_move=-1;
    int act_best_val=ismaxplayer?-infinity:+infinity;
    for(unsigned int i=p11; i<s89; i++)
    {
        if(actualb.table[i]==empty && legal(i, dir))
        {
            FullMoveExecuter exec(i, udata, dir);
            int g=evaluator.Evaluate();
            if(ismaxplayer)
            {
                if(act_best_val<=g)
                {
                    act_best_val=g;
                    act_best_move=i;
                }
            }
            else
            {
                if(act_best_val>=g)
                {
                    act_best_val=g;
                    act_best_move=i;
                }
            }
        }
    }

    if(act_best_move!=-1)
    {
        bestMove=act_best_move;
        _lastbestMove=bestMove;
        return act_best_val;
    }
    return evaluator.Evaluate();
}

void Thinker::InitThread()
{
    srand(time(0));
    ResetGame();
}

int Thinker::deep_enough[]=
{
    10, 10, 10, 10, 10, 11, 11, 11, 11, 11,
    11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
    11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
    10, 10, 10, 10, 10, 10, 10, 10, 10, 9,
    9,  9,  9,  9,  9,  9,  9,  10,  10, 10,
    10,  9,  8,  7,  6,  5,  4,  3,  2,  1
};

squareindex Thinker::firstmoves[]=
{
    p43, p34, p56, p65
};

void Thinker::CheckTime()
{
    if(_thinking)
    {
       if(!_timescheduler.TimeOk())
            _stop=timeOut;
    }
}

HistoryHeuristic& Thinker::_hheuristic=HistoryHeuristic::Instance();
TranspositionTable& Thinker::_ttable=TranspositionTable::Instance();