uct.h

Go to the documentation of this file.

#pragma once 

#include <cmath>
#include <queue>
#include <set>

#include "hash.h"

using std::map;
using std::queue;
using std::sqrt;
using std::set;
using std::make_pair;

#define MAX_PLAYOUT_LENGTH 100  //these are 2 "moves" ( i.e. maximally 2 times 4 steps ) 
#define UCT_MAX_DEPTH 30
#define CHILDREN_CACHE_SIZE 5
#define CCACHE_START_THRESHOLD 50 
#define EVAL_AFTER_LENGTH (cfg.playoutLen())
#define FPU 0.9

#define NODE_VICTORY(node_type) (node_type == NODE_MAX ? 2 : -1 )
#define WINNER_TO_VALUE(winner) (winner == GOLD ? 1 : -1 )

enum playoutStatus_e {PLAYOUT_OK, PLAYOUT_TOO_LONG, PLAYOUT_EVAL}; 

class Engine;
class Uct;

enum nodeType_e {NODE_MAX, NODE_MIN};   

#define PLAYER_TO_NODE_TYPE(player) (player == GOLD ? NODE_MAX : NODE_MIN)

class SimplePlayout
{
        public:
                SimplePlayout(Board*, uint maxPlayoutLength, uint evalAfterLength);

                playoutStatus_e doPlayout();    

                uint getPlayoutLength();  

    virtual ~SimplePlayout(){};

  protected:
    virtual void playOne();     

    bool hasWinner();

    SimplePlayout();

    Board*                board_;
    uint        playoutLength_;
    uint        maxPlayoutLength_;
    uint        evalAfterLength_;

};

class AdvisorPlayout : public SimplePlayout
{
  public:
                AdvisorPlayout(Board*, uint maxPlayoutLength, uint evalAfterLength, 
                    MoveAdvisor* advisor);

    void playOne();

  private: 
     MoveAdvisor * advisor_;
};

class TWstep
{
  public:
    TWstep(Step, float, int);
    Step step;
    float value;
    int visits;
} ; 

typedef map<Step, TWstep> TWstepsMap;

class TWsteps: public TWstepsMap
{
  public: 
    TWstep& operator[](const Step& step);
  private:
};

typedef set<Node*> NodeSet;


class TTitem 
{
  public: 
    TTitem(NodeList*); 

    NodeList* getNodes() const;
  private:
    TTitem(); 

    /*Shared number of visits for tt brothers.*/
    int visits_;
    /*Shared average value for tt brothers.*/
    float value_;
    NodeList* nodes_;

    friend class Node;
};

class Node
{
  public:
    Node();

    Node(TWstep*,  float heur=0);

    Node* findUctChild(Node * realFather);

    Node* findRandomChild() const;

    Node* findMostExploredChild() const;

    float exploreFormula(float) const;

    void cCacheInit();

    void cCacheUpdate(float exploreCoeff);

    void uctOneChild(Node* act, Node* & best, float & bestUrgency, float exploreCoeff) const;

    float ucb(float exploreCoeff) const;

    float ucbTuned(float exploreCoeff) const;

    void  addChild(Node* child);

    void  reverseChildren();

    void  delChildrenRec();

    void connectToMaster(const bool lock=true);

    void connectChildrenToMaster();

    void syncMaster();

    void recSyncMaster();

    void  updateTTbrothers(float sample=0, int size=0);

    void  update(float);
    
    void  updateTWstep(float);

    bool  isMature() const;

    bool  hasChildren() const;
    
    //getters/setters
    
    Node* getFather() const;
    void  setFather(Node*);
    Node* getFirstChild() const;
    void  setFirstChild(Node *);
    Node* getSibling() const;
    void  setSibling(Node*);
    TTitem* getTTitem() const;
    void setTTitem(TTitem * node);
    Step  getStep() const;
    TWstep*  getTWstep() const;
    player_t getPlayer() const;
    int   getVisits() const;
    void  setVisits(int visits); 
    float getValue() const;
    void setValue(float value);
    void setMaster(Node* master);
    Node* getMaster();
    void lock();
    void unlock();
    nodeType_e getNodeType() const;

    int getDepth() const;

    int getLocalDepth() const;

    int getLevel() const;

    int getDepthIdentifier() const;

    string toString() const; 

    string recToString(int) const;

  private:
    float       value_; 
    float       heur_;
    float       squareSum_;
    int         visits_;
    TWstep*     twStep_;

    float       masterValue_;

    int         masterVisits_;

    TTitem*       ttItem_;

    Node*       sibling_;
    Node*       firstChild_;  
    Node*       father_;
    int         cCacheLastUpdate_;
    Node**      cCache_; 
    Node*       master_;

    //todo remove !? 
    pthread_mutex_t mutex;
};

class Tree
{

  public:
    Tree(Node * root);   

    Tree(player_t firstPlayer);   

    ~Tree();

    void syncMaster();

    void  expandNode(Node* node, const StepArray& steps, uint len, const HeurArray* heurs=NULL);

    /*
     * Limited Node expansion.
     *
     * Expands node for given move. 
     * I.E. for every step in given move, moves one level deeper.
     */
    void  expandNodeLimited(Node* node, const Move& move);

    void uctDescend();

    void randomDescend();

    void firstChildDescend();

    Node* findBestMoveNode(Node* subTreeRoot);

    Move findBestMove(Node* bestMoveNode);

    void updateHistory(float);

    void historyReset();

    Node* root();

    Node* actNode();

    int getNodesNum();

    int getNodesPrunedNum();

    int getNodesExpandedNum();

    string toString();

    string pathToActToString(bool onlyLastMove = false);

    void updateTT(Node* father, const Board* board);


  private:
    friend class Uct;
    Tree();   

    void init();

    static int calcNodeLevel(Node* father, const Step& step);

    Node*      history[2 * UCT_MAX_DEPTH];
    uint       historyTop;
    int   nodesExpandedNum_;
    int   nodesNum_;
    int nodesPrunedNum_;
    TWsteps  twSteps_;
    TT* tt_;              
    
};

class Uct
{
  public:

    Uct(const Board* board);

    Uct(const Board* board, const Uct* masterUct);

    ~Uct();

    void updateStatistics(Uct* ucts[], int uctsNum);

     void searchTree(const Board*, const Engine*);

    void refineResults(const Board* board); 

    void doPlayout(const Board* board);

    string getStats(float seconds) const;

    string getAdditionalInfo() const;

    string getBestMoveRepr() const;

    int getBestMoveVisits() const;

    float getBestMoveValue() const;

    float getWinRatio() const;

    Tree* getTree() const;

    int getPlayoutsNum() const;

  private:
    Uct();

    void init(const Board* board);

    double decidePlayoutWinner(const Board*) const;

    void fill_advisor(const Board * playBoard);

    Tree* tree_;
    Eval* eval_;
    Node* bestMoveNode_;  
    string bestMoveRepr_;  
    int playouts_;
    int uctDescends_;
    /*Move advisor is filled during the expansion process and is used in th playouts.*/
    MoveAdvisor * advisor_;
};

---