board.h

Go to the documentation of this file.

#pragma once

#include <queue>
#include <stack>
#include <list>
#include <bitset>
#include <pthread.h>

using std::queue;
using std::stack;
using std::list;
using std::vector;
using std::bitset;

#include "utils.h"
#include "hash.h"
#include "config.h"

#define MAX_PIECES  16      
#define MAX_STEPS  80

#define STEPS_IN_MOVE 4

typedef unsigned long long u64;

#define IS_PLAYER(player) (player == GOLD || player == SILVER)
#define IS_PIECE(piece) ( piece > 0 && piece <= 6)

#define NORTH 8
#define SOUTH -8
#define EAST 1
#define WEST -1

#define BIT_EMPTY -1

#define GOLD        0
#define SILVER      1
#define NO_PLAYER   2

#define NO_SQUARE    -1

#define NO_PIECE    0
#define RABBIT      1
#define CAT         2
#define DOG         3
#define HORSE       4
#define CAMEL       5
#define ELEPHANT    6
#define PIECE_NUM   6

#define OPP(player) (1 - player)                                 //opponent
#define BIT_ON(n) (1ULL << (n))          //creates empty board with one bit set on n

#define BIT_LEN 64
#define SQUARE_NUM 64
#define SIDE_SIZE 8

#define RABBITS_NUM 8

#define STEP_PASS     0
#define STEP_SINGLE   1
#define STEP_PUSH     2
#define STEP_PULL     3
//no step is possible ( not even pass ! - position repetition )
#define STEP_NULL     4   
#define PLAYER_NUM    2

// what row is a square in?  1 = bottom, 8 = top
#define ROW(square) (square/10) 
// what column is a square in?  1 = left (a), 8 = right (h)
#define COL(square) (square%10) 

#define SQUARE_TO_INDEX_64(square) (8*(ROW(square)-1) + (COL(square)-1))
#define INDEX_64_TO_SQUARE(index) ((10 * (index/8 + 1)) + ((index % 8) + 1 ))

#define SQUARE_DISTANCE(s1, s2) (abs(s1/8 - s2/8) + abs(s1%8 - s2%8))

#define OLD_PLAYER_TO_NEW(player) (player == 16 ? GOLD : SILVER)

typedef int player_t;
typedef int piece_t;
typedef int coord_t;

typedef uint stepType_t;


namespace bits{
  #define NOT_A_FILE  0xfefefefefefefefeULL
  #define NOT_H_FILE  0x7f7f7f7f7f7f7f7fULL
  #define NOT_1_RANK  0x00ffffffffffffffULL
  #define NOT_8_RANK  0xffffffffffffff00ULL
  #define MSB         0x8000000000000000ULL
  #define TRAPS       0x0000240000240000ULL
  #define FPARITY     0x5555555555555555ULL
  #define FULL        0xffffffffffffffffULL
  #define EMPTY       0x0ULL
  #define IS_TRAP(coord) (BIT_ON(coord) & TRAPS)
  #define TRAPS_NUM   4
  extern u64 zobrist[2][7][64];     
  const int TRAP_COORDS[TRAPS_NUM] = {45, 42, 21, 18};
  #define TRAP_INDEX_TO_TRAP(index) (bits::TRAP_COORDS[index])
//  #define TRAP_INDEX_TO_TRAP(index) (assert(index < TRAPS_NUM && index >= 0), bits::TRAP_COORDS[index])

  void initZobrist();

  extern u64 winRank[2]; 
  extern u64 stepOffset_[2][7][64]; 
  void buildStepOffsets();

  u64 str2bits(string str);

  int lix(u64& b);

  int lixslow(u64& v);
  
  int  bitCount(u64 b);

  int  bitOnOrder(uint index, u64 b);

  bool getBit(const u64& b, int n);

  bool isTrap(coord_t coord);

  ostream& print(ostream& o, const u64& b);

  u64 neighbors(u64);

  u64 neighborsOne(coord_t coord);

  int neighborsOneNum(coord_t coord, u64 mask);

  u64 sphere(int center, int radius);

  u64 circle(int center, int radius);
}


enum recordAction_e {ACTION_PLACEMENT, ACTION_STEP, ACTION_TRAP_FALL, ACTION_ERROR}; 

void globalStructuresInit();

bool parsePieceChar(char pieceChar, player_t& player, piece_t& piece); 

string coordToStr(coord_t at); 

class Board;
class Eval;

class Soldier
{
  public: 
    Soldier(player_t player, piece_t piece, coord_t coord);

    string toString();

    piece_t  piece() { return piece_; }
    player_t player() { return player_; }
    coord_t  coord() { return coord_; }

  private: 
    Soldier(){};

    player_t player_;
    piece_t piece_;
    coord_t coord_;
};

typedef list<Soldier> SoldierList;
typedef SoldierList::iterator SoldierListIter;

class KillInfo 
{
  public:
    KillInfo();
    KillInfo(player_t player, piece_t piece, coord_t coord);
    void setValues(player_t player, piece_t piece, coord_t coord);
    const string toString() const;

  private:
    bool     active_;
    player_t player_;
    piece_t  piece_;
    coord_t coord_;
};

class OB_BOARD;

class Step
{
  public:
                Step();
                Step(stepType_t, player_t);
    Step(stepType_t, player_t, piece_t, coord_t, coord_t);
    Step(stepType_t, player_t, piece_t, coord_t, coord_t, piece_t, coord_t, coord_t);

    player_t getPlayer() const;
    bool isPass() const;
    bool isNull() const;
    bool isSingleStep() const;
    bool isPushPull() const;

    int count() const;

    Step toNew() const;

    bool inversed(const Step&) const;

                bool pieceMoved() const;
                bool operator== (const Step&) const;
    bool operator<(const Step&) const;

    void setValues( stepType_t, player_t, piece_t, coord_t, coord_t );
    void setValues( stepType_t, player_t, piece_t, coord_t, coord_t, 
                    piece_t, coord_t, coord_t );
    string toString() const;

        protected:
    stepType_t    stepType_;    
    player_t      player_;      
    piece_t       piece_;  
    coord_t      from_;     
    coord_t      to_;        

    piece_t       oppPiece_;  
    coord_t      oppFrom_;
    coord_t      oppTo_;

    friend class Board;
    friend class Eval;
    friend class OB_Board;
    friend class ContextMove;
    friend class Move;
  
  private: 
    const string oneSteptoString(player_t, piece_t, coord_t, coord_t) const;
  
};

class StepWithKills: public Step
{
  public:
    StepWithKills(Step step, const Board* board);

    string toString() const;

  private:
    StepWithKills();

    void addKills(const Board* board);

    KillInfo kills[2];
};

typedef list<Step> StepList;
typedef StepList::iterator StepListIter;


class Move
{
  public:
    Move();

    Move(string moveStr);

    void appendStep(Step);
    
    void prependStep(Step);

    void appendStepList(StepList);

    StepList getStepList() const;

    int getStepCount() const;

    bool isOpening() const;

    player_t getPlayer() const;

    bool operator==(const Move& other) const;

    string toString() const;
    
  private:
    recordAction_e  parseRecordActionToken(const string& token, player_t& player, 
                                           piece_t& piece, coord_t& from, coord_t& to);

    void updateStepCount(const Step& step);

    StepList stepList_;
    int stepCount_;

    bool opening_;
};

typedef list<Move> MoveList;
typedef MoveList::iterator MoveListIter;
typedef vector<Move> MoveVector;
typedef MoveVector::iterator MoveVectorIter;

//steps
typedef Step  StepArray[MAX_STEPS];
//heuristics for steps (separated because used VERY LITTLE)
typedef float  HeurArray[MAX_STEPS];

typedef list<int> intList;

typedef stack<Board*> Bpool;

typedef u64 Bitboard[2][7];

class Glob {
  public:
    Glob();
    void init();
    inline Bpool* bpool() {return bpool_[tti()];}
    inline ThirdRep* thirdRep() {return thirdRep_[tti()];}
    inline Grand* grand() {return grand_[tti()];}

  private:
    int tti();
    
    int add_thread();

    int threadIds_[MAX_THREADS];
    int threadsNum_ ;

    pthread_mutex_t lock;
    Bpool * bpool_[MAX_THREADS];
    ThirdRep * thirdRep_[MAX_THREADS];
    Grand * grand_[MAX_THREADS];
};

extern Glob glob;


class ContextMove 
{ 
  public:  
    ContextMove(Move move, const Bitboard& bitboard);

    bool applicable(const Bitboard& bitboard, int stepsLeft) const;

    Move getMove() const;

    float getValue() const;

    void update(float sample); 

    float urgency(player_t player, int total) const;
  private: 
    ContextMove(){};
    Move move_;
    Bitboard context_;
    u64 mask_;
    float value_;
    int visits_;
};

typedef vector<ContextMove> ContextMoves;
typedef ContextMoves::iterator ContextMovesIter;

class MoveAdvisor 
{
  public: 
    MoveAdvisor(); 
    bool getMove(player_t player, const Bitboard& bitboard, int stepsLeft, Move* move);
    bool getMoveRand(player_t player, const Bitboard& bitboard, int stepsLeft, Move* move);

    bool addMove(const Move & move, const Bitboard& bitboard);

    void update(float sample);

  private:
    bool hasMove(const Move & move, const Bitboard& bitboard);

    //void bubble(player_t player, int index, direction

    ContextMoves contextMoves[2];
    list<int> playedCMs[2];

    bool update_;
    
    int used_;
};
    
class Board
{

  public:

    Board(){};

    void initNewGame();

    bool  initFromRecord(const char* fn, bool init_repetitions=false); 

    bool  initFromPosition(const char* fn); 

    bool initFromPositionCompactString(const string& s); 

                Step findMCstep();

    void findMCmoveAndMake(); 
    
                bool operator== (const Board& board) const;

    void updateThirdRep();

                void makeMove(const string& move);
    
    void makeMove(const Move& move);

    bool makeStepTryCommit(const Step&);

          void commit();

    int filterRepetitions(StepArray&, int ) const;

    bool  isSetupPhase() const;

    bool checkKillForward(coord_t from, coord_t to, KillInfo* killInfo=NULL) const;

    u64 calcAfterStepSignature(const Step& step) const;

        int genStepsNoPass(player_t, StepArray& steps) const;

        int genSteps(player_t, StepArray& steps) const;

    void getHeuristics(const StepArray& steps, uint stepsNum, HeurArray& heurs) const;

    bool canContinue(const Move& move) const;
    
    bool canPass() const;

    Step lastStep() const;

    bool isMoveBeginning() const;


    void updateWinner();

    bool goalCheck(player_t player, int stepLimit, Move* move=NULL) const;

    bool goalCheck(Move* move=NULL) const;

    bool trapCheck( player_t player, coord_t trap, int limit, MoveList* moves, SoldierList* soldiers) const;

    bool trapCheck(player_t player, MoveList* moves=NULL, SoldierList* soldiers=NULL) const;

    bool trapCheck(coord_t pos, piece_t piece, player_t player, 
                   coord_t trap, int limit, int used, Move* move) const;

                static string bitboardToString(const Bitboard & bitb);

          string toString() const;

    string moveToStringWithKills(const Move& m) const;

    u64 getSignature() const;

    player_t getWinner() const;

    player_t gameOver() const; 

    player_t getPlayerToMove() const;

    const Bitboard& getBitboard() const;

    player_t getPlayerToMoveAfterStep(const Step& step) const;

          uint getStepCount() const;

          uint getStepCountLeft() const;


    void *operator new(size_t size);
    void operator delete(void* p);

  private: 

    int reachability(int from, int to, player_t player, 
                    int limit, int used, Move * move) const;

    void genStepsOne(coord_t coord, player_t player,
                        StepArray& steps, int& stepsNum) const;

    inline void genStepsOneTuned(coord_t coord, player_t player, piece_t piece, 
                              StepArray& steps, int& stepsNum, u64 victims) const;

    u64 calcMovable(player_t player) const;

    void calcWeaker(player_t player, u64 (&weaker)[7]) const;

    void        setSquare(coord_t, player_t, piece_t);
    void        delSquare(coord_t, player_t);                                                                                   
    void        delSquare(coord_t, player_t, piece_t);                                                                                  

    piece_t     getPiece(coord_t, player_t) const;

    player_t getPlayer(coord_t) const;

    int strongerDistance(player_t player, piece_t piece, coord_t coord) const;

    u64 strongerWithinDistance(player_t player, piece_t piece, 
                          coord_t coord, int distance) const;

    int equalDistance(player_t player, piece_t piece, coord_t coord) const;

  
    player_t strongestPieceOwner(u64 area) const;

    player_t strongestPiece(player_t player, u64 area) const;

    u64 weaker(player_t player, piece_t piece) const;

    u64 stronger(player_t player, piece_t piece) const;
  
    void  init(bool newGame=false);

    void afterPositionLoad();

    player_t sideCharToPlayer(char side) const; 

    bool findActiveTrapping(MoveVector& moves);

    void  makeSignature();

                void makeStep(const Step& step);

    Step chooseStepWithKnowledge(StepArray& steps, uint stepsNum) const;

    bool stepIsVirtualPass( Step& ) const;

    bool stepIsThirdRepetition(const Step& ) const;

    u64 getPreMoveSignature() const;

    Bitboard bitboard_;

    static bool       classInit;
    static ThirdRep*  thirdRep_;
    static Eval*      eval_;

    u64 signature_;            

    u64 preMoveSignature_;     
    
    u64 preStepSignature_;     

    Step lastStep_;

                // move consists of up to 4 steps ( push/pull  counting for 2 ),
    uint  moveCount_;

                // step is either pass or single piece step or push/pull step,
                // thus stepCount_ takes values 0 - 4 
    uint  stepCount_;

    player_t toMove_;
                player_t winner_;

    friend class Eval;
};

---