Board representation

Board representation (see board.h) is the main pillar of the whole program. Several crucial classes are defined here, for instance:

• Board - main class representing the board and providing interface for operations with it (see below)
• Step - one step (including push/pulls) representation with its interface (Step::inversed, equality operator, various constructors, etc.)
• Move - representation of multiple steps forming a move
• Glob - (per thread) storage and access to global variables

Class Board handles various tasks connected to the board abstraction, most important are:

• position initialisation Engine supports initialisation from different formats. Particular formats are handled by dedicated functions: Board::initFromPosition, Board::initFromPositionCompactString, Board::initFromRecord.
• step generation Generating steps for one piece is done via Board::genStepsOne, which is a simple wrapper around Board::genStepsOneTuned. Steps are cummulated in steps array (for performance reasons the steps array is of fixed size and Step objects are not created on-the-fly, rather the existing objects in the array are overwritten via Step::setValues).

Board::genStepsOne wrapper

  //Board::genStepsOne
  ...
  if (bits::getBit(calcMovable(player), coord)){
    u64 victims[7];  
    //calculates weaker (opponent's) bitboards for all piece types for given player
    calcWeaker(player, victims);

    assert(getPlayer(coord) == player); 
    piece_t piece = getPiece(coord, player);
    //generate steps for given piece and store them in steps, victims for actual piece are passed ...
    genStepsOneTuned(coord, player, piece, steps, stepsNum, victims[piece]);
    return;
  }
  ...
  //end Board::genStepsOne
}

single steps generation in Board::genStepsOneTuned

  ... 
  //Board::genStepsOneTuned
  //piece at from must not be frozen (ensured in wrappers)
  //in victims there are already all weaker pieces than given piece (ensured in wrappers)

  u64 empty = ~(bitboard_[0][0] | bitboard_[1][0]);
  u64 whereStep = empty & bits::stepOffset_[player][piece][from];
    
  //single steps
  for (int i = 0; i < 4; i++) {
    coord_t to = from + bdirection[i];
    if (whereStep & BIT_ON(to)) {
      //destination is empty  -> add step
      steps[stepsNum++].setValues(STEP_SINGLE, player, piece, from, to);
    }
  }
  
  //finish if push/pulls are not possible
  if ( piece == RABBIT || stepCount_ >= 3 || 
       ! (bits::stepOffset_[player][piece][from] & bitboard_[OPP(player)][0])) { 
    return;
  }

push/pulls generation

  ...
  //collect potential victims (weaker & neighbours)
  victims &= bits::stepOffset_[player][piece][from];
   
  //cycle through neighbors and perform push/pull if there is a victim 
  //and there is where to push/pull
  for (int i = 0; i < 4; i++) {
    coord_t victimFrom = from + bdirection[i];
    if (! (victims & BIT_ON(victimFrom))) {
      continue;
    }

    //pull
    u64 wherePull = empty & bits::stepOffset_[player][piece][from];          
    for (int j = 0; j < 4; j++) {
      coord_t pullerTo = from + bdirection[j];
      if (! (wherePull & BIT_ON(pullerTo))) {
        continue;
      }

      steps[stepsNum++].setValues(STEP_PULL, player, piece, from, pullerTo, 
                            getPiece(victimFrom, OPP(player)), victimFrom, from); 
    }

    //push
    u64 wherePush = empty & bits::stepOffset_[player][piece][victimFrom]; 
    for (int k = 0; k < 4; k++) {
      coord_t victimTo = victimFrom + bdirection[k];
      if (! (wherePush & BIT_ON(victimTo))) {
        continue;
      }

      steps[stepsNum++].setValues(STEP_PUSH, player, piece, from, victimFrom,
                        getPiece(victimFrom, OPP(player)), victimFrom, victimTo);
    }
  } 
  ...
  //end Board::genStepsOneTuned

All steps might be generated via Board::genSteps, which basically cycles through all pieces belonging to given player and gathers their steps via Board::genStepsOneTuned.

• performing steps Performing steps is tightly connected with updating bitboards (including removing trapped pieces), position signature and current step count. Core function Board::makeStep is usually called via wrapper Board::makeStepTryCommit (which performs step and then tries to switch side to play to other player if possible) or Board::makeMove (performing all steps in the move and then commiting via Board::commit).
  Board::makeStep works as following:

    //Board::makeStep
    ... 
    //handle push/pull steps
    if (step.isPushPull()) {  
      //delSquare/setSquare automatically update position signature
      delSquare(step.oppFrom_, OPP(step.player_), step.oppPiece_);
      setSquare(step.oppTo_, OPP(step.player_), step.oppPiece_);
      stepCount_++;
    }

    //handle single step
    delSquare(step.from_, step.player_, step.piece_);
    setSquare(step.to_, step.player_, step.piece_);
    stepCount_++;
    ...
    //handle deaths in traps
    for (int player = 0; player < 2; player++){
      fullTraps = (TRAPS & bitboard_[player][0]);
      //fullTraps without support
      dieHard = fullTraps ^ (fullTraps & bits::neighbors(bitboard_[player][0]));

      if (dieHard){
        int trap = bits::lix(dieHard);             
        if ( trap != BIT_EMPTY){
          delSquare(trap, player);
          //no more than one dead per player
          assert(bits::lix(dieHard) == BIT_EMPTY); 
        }
      }
    } 
    ...
    //end Board::makeStep

• repetitions filtering All filtering is performed by single method Board::filterRepetitions. This is issued in uct module in Uct::doPlayout right before node expansion. Functions applies following filters:
  • virtual passes - sequence of steps reverting the position to position before the move
  • inverse steps - steps reverting the position to position before the last step
  • steps causing 3rd time repetition - this is done via ThirdRep object which stores all visited positions since the beginning of the game.
• move selection for playout This is done by function Board::findMCmoveAndMake already described in Playouts.
• search extensions Board contains functions for search extensions: goal scoring and trapping. These are implemented as strongly narrowed lookaheads. Goal score extension is handled by funcions Board::goalCheck and Board::reachability. Trapping extension is handled by function Board::trapCheck. These checks are used in MoveAdvisor (both), in Eval::evaluateInPercent(goal check), in Uct::doPlayout(goal check: to perform limited expansion). Moreover they can be explicitly applied to a position via extended AEI (trapcheck and goalcheck commands).