model.cpp

c+++ game uploading now

/**
 @file
 Code for search routines, algortihms such as alpha-beta, iterative 
 deepening, MTD(f) and so on.
*/

#include <ctime>
#include <cstdlib>
#include "Model.h"
#include "Boards.h"
#include "MoveExecuter.h"
#include "MoveListGenerator.h"


using namespace Othello;

namespace Othello
{
    /** the board used during search */ 
    Board actualb;
    /** the current board's representation in a TT entry format */
    TTBoard actualbtt;
}

//DEBUG
unsigned int Othello::Count(squarevalue p)
{
    int ret=0;
    for(unsigned int i=p11; i<s89; i++)
        if(actualb.table[i]==p)
            ret++;
    return ret;
}

void Thinker::ResetGame()
{
    actualb.InitBoard();
    actualb.Syncronize();
    newBoard=actualb;
    gamevalue=0;
    bestMove=-1; //??
    _lastbestMove=-1; //??
    _ttable.FreeAll();
    _hheuristic.Reset();
    _stop=noStop;
    posSearched=0;
    ttHits=0;
    ttGHits=0;
    nrMoves=0;
    IdDepth=0;
    _thinking=false;
    timedout=false;
    _book.Reset(actualb);
    _avaible_time=_init_totaltime;
}

void Thinker::InitBoards()
{
    assert(sizeof(TTBoard)==8);
    actualb=newBoard;
    actualbtt.isblacksturn=actualb.isblacksturn;

    posSearched=0;
    ttHits=0;
    ttGHits=0;

    HistoryHeuristic::Instance().Reset();
    actualb.hash32=_ttable.Key32(actualb);
    actualbtt.SetLock32(_ttable.Lock32(actualb));
    actualb.Syncronize();

    _isdoublemove=false;
    _stop=noStop;
}

void Thinker::Stop()
{ 
    _stop=guiBreak;
}

Thinker::Thinker(HWND hwnd)
    :_hwnd(hwnd),
     _avaible_time(0),
     _init_totaltime(0),
     timedout(false),
     _timescheduler(_avaible_time, _init_totaltime, timedout)
{
    ResetGame();
}

Thinker::~Thinker()
{
    Kill();
}


void Thinker::Go()
{
    _event.GreenLight();
    _stop=noStop;
}

//!!!!!!!!!same o same!!!!!!!!!!!!!
void Thinker::FlushThread()
{
    _event.GreenLight();
}

void Thinker::Run()
{
    for(;;)
    {
        _thinking=false;
        _event.Wait();
        _thinking=true;
        if(_isDying)
            return;
        InitBoards();
        try
        {
            Think();
        }
        catch(STOP &stop)
        {
            //if this was a GUI request without further commands 
            //then block and wait until GUI makes a reset!
            if(stop.IsGuiBreak())
            {
                _event.RedLight();
            }
            else
                //otherwise (we had a timeout or a forced stop so send results)
                if(stop.IsForceMove() || stop.IsTimeOut())
                {
                    bestMove=_lastbestMove;
                    _timescheduler.AdjustElapsed();
                    DispatchResultsToGui();
                }
            continue;
        }
        DispatchResultsToGui();
    }
}

void Thinker::Force_Stop()
{
    _stop=forceMove;
}


/*MSC confuses std::max and std::min with his own macros
  so I'll the standard ones only on a less deviant compiler.*/
#if !defined _MSC_VER
#include <algorithm>
using std::max;
using std::min;
#endif



//TODO draw is not handled correctly
//alpha is redundant, this function is intended to be used
//exclusevly with null windows. What a mess!
int Thinker::AlphaBeta(int alpha, int beta, unsigned int depth)
{
    assert(actualb.AssertIsInSync());
    assert(actualb.hash32==_ttable.Key32(actualb));
    posSearched++;

    if(depth==0)
        return evaluator.Evaluate();

    bool leave=false;
    //DEBUG
    assert(depth<=MAXDEPTH);
    
    //current board value
    int g;

    //client peak
    if(_stop!=noStop)
        throw STOP(_stop);
     
    //try to retrive current board from transposition table
    TTBoard *prev=_ttable.Retrieve(); //TODO prev is not used properly
    
    if(prev==NULL)
        actualbtt.Clean();
    else
    {   
        //extract moveinfo
        actualbtt= *prev;

        ttHits++;
        assert((prev->GetDepth()!=0));
        
        //if we are in the same depth then extract game
        //values and use them ???????????
        //(prev->GetDepth()>=depth) seems more logical but if we will fail high using
        //deeper values then there is a chance that when doing the research this value 
        //will no longer be avaible. 
        if(prev->GetDepth()==depth)
        {
            //ttGHits++;
            if(prev->LowerBound() >= beta)
            {
                ttGHits++;
                return prev->LowerBound();
            }
            if(prev->UpperBound() <= alpha)
            {
                ttGHits++;
                return prev->UpperBound();
            }
        }
    }

#if defined _ENDGAME_TEST_
    if(actualb.CountEmpty()<9 && depth<=4 && IdDepth>4)
        return endgame.Solve(alpha, beta, posSearched);
#endif //_ENDGAME_TEST_

    bool hasBestMove=false;

    assert(depth!=0);
    //save alpha, beta (for TT stuff)
    int a=alpha;
    int b=beta;
    
    //generate moves
    MoveListGenerator moves(depth, prev!=NULL );
    if(moves.Empty())
    {   
        leave=true;
        g=evaluator.Evaluate();
    }
    else
    {
        UndoData udata;
        //MAX player (black)
        if(actualb.isblacksturn)
        {
            //at max player, the value of the node increases
            g=-infinity;
            while(g<beta)
            {
                if(!moves.AtEnd()) //!!! exec must have preccisely this scope!!!
                {
                    FullMoveExecuter exec(moves.X(), udata, moves.Dir());
                    //yap we are maximizing
                    int tmp=AlphaBeta(a, beta, depth-1);
                    //did we found a better move?, if yes then update bestmove info
                    if(g<tmp)
                    {
                        exec.MarkAsBestMove();
                        hasBestMove=true;
                        g=tmp;
                    }
                    //and tigthening bounds for the min player
                    a=max(a, g); //TODO can I place this line elsewhere?
                }
                else break;
                //if we allready have a cutoff then avoid further move genration
                if(g<beta)
                    moves.Step(); 
                else break; 
            }
        }
        //MIN player (white)
        else
        {
            //values for min player get smaller
            g=+infinity;
            while(g>alpha)
            {
                if(!moves.AtEnd()) //!!! exec must have preccisely this scope!!!
                {
                    FullMoveExecuter exec(moves.X(), udata, moves.Dir());
                    //this is what min does
                    int tmp=AlphaBeta(alpha, b, depth-1);
                    if(g>tmp)
                    {
                        exec.MarkAsBestMove();
                        hasBestMove=true;
                        g=tmp;
                    }   
                    //tigthen bound for max player
                    b=min(b, g);
                }
                else break;
                //if we allready have a cutoff then avoid further move genration
                if(g>alpha)
                    moves.Step();
                else break;
            }
        }
    } //we had some moves

    /*mark boounds*/
    //leaves always have "exact" value
    if(leave)
        actualbtt.SetExact(g, depth);
    //if failing high then we got a lower bound
    else if(g>=beta)
             actualbtt.SetLowerBound(g, depth);
         //we are failing low ==>> got an upper bound //NOTE beta-alpha==1 no chance for success 
         else 
             actualbtt.SetUpperBound(g, depth);

    //update history heuristic info and store results
    if(hasBestMove)
    {
        _hheuristic.GoodMove(actualbtt.BestMove(), actualb.isblacksturn, depth);
        _ttable.Store();
    }