OpenChess

Posted: **Thu Feb 03, 2011 7:13 am**

Has anyone taken a look at this: http://borischess.wikispaces.com/

The first task is to reverse-engineer their ь code.
Step one of this, with pedagogy in mind, is to rewrite it in English, and compare it to IPP_ENG.c

A few thoughts from my first glances, before I quit for the day.
ь code is quite compact, with repeated texts (like hashing code) understood, and rejigged with flags when opportune.
But these "flags" tend to be ad hoc to the beginner.
As they say, there is not yet a ь standard, and so it can grow in whatever form or manner they wish.
I would prefer some of the expressions (like |! for applying nullmove) to be expanded out.
Returning again, they prefer the compact.
Also, the logic is often "inversive" from what I would expect.

This is the order of investigations:
Function LowDepth
Function Qsearch in check
Function PV node
Function Root node

* LOW(SCORE,depth)^HISTORY
  < [ BEHIND > 1125 ] (SCORE-1)! | HASH_READ&TRANS |
    [ AHEAD >= 70+10*depth ] (&EVAL)! | %MINIMUM(VALUE,SCORE-1)% |
    [ AHEAD ] + [ MY_NULL ] |! %QSEARCH(1-SCORE,0) |
    #TARGET + DELTA_PRUNING[ TRANS2^(50+8*depth) | pawn^(75+32*depth):#125* |
                           minor^(400+32*depth)+[depth<=3]:+300* | rook^(600+32*depth):+200* ]
            \ [ depth<=3 ] + [ BEHIND > 4*depth ] TRANS3 + REWARD*[BEHIND+4*depth+5]
   << [ REPETITION ] %MAXIMUM(%%,0)% + count! |
      [ count >= depth ] + [ $OTHER_MOVE$ ] + [ !CHECK_OR_CAPTURE ] + [ !XRAY ] + [ HAS_PIECE ]
      + [ 2*depth + MAXIMUM_REWARD + AHEAD < 40 + 2*count ] count! |
      [ CAPTURE += [ [ depth <= 5 ] + [ !TRIVIAL_SEE ] ] ]
      + [ !XRAY ] + [ !KING_MOVE ] + [ !TRANS ] + [ !SEE ] count! ||
      EVAL(150) !! %%LOW(1-SCORE,depth-1) %+
                   [ [ count >= depth ] + [ 2*depth + AHEAD# < count ] ] !count!
                    \ %LOW/QSEARCH(1-SCORE,depth-2) | count >>
   [ !count ] + [ $TRANS2$>= ] (0)! >

Posted: **Thu Feb 03, 2011 7:32 am**

My ь code translation

Code: Select all

* QSEARCH_CHECK(SCORE,depth)
  < | HASH_READ&TRANS | %HEIGHT% | ##TARGET |
    [ BEHIND < 10 ] %(&EVAL+10)% + #TARGET + DELTA_PRUNING[ pawn:200* | minor:500 ] |
    @EVASION(TARGET)^TRANS |
    SORT< [ INTERPOSE ] + [ !CAPTURE_OR_PROMOTION ] + [ !TRANS ]
           + [ MY_NULL ] + [ !MATE ]+ [ MAXIMUM_REWARD + AHEAD < 25 ] count! ||
          EVAL(150) ! %QSEARCH#(1-SCORE,depth) > |
   [ count ] + [ %% < -MATE ] %SCORE-1%
  >

The C code is much expanded

Code: Select all

int
white_qsearching_check (int notch, int deepness)
{
  int sch, score, i, k = tower_dynamics->hash_64bit & hash_mask, itog, best_valuation, transpositional_deepness, move_deepness = 0;
  type_hash *hash;
  UINT64 intention;
  type_move_list movement_listing[0x100], *move_list, *p, *q;
  type_dynamics *tower_structure = tower_dynamics;
  UINT32 move, temp, transpositional_movement = 0;
  if (tower_dynamics->non_permanent >= 100)
    return (0);
  for (i = 4; i <= tower_dynamics->non_permanent && i <= elevation_stack; i += 2)
    if (stack[elevation_stack - i] == tower_dynamics->hash_64bit)
      return (0);
  tower_structure = tower_dynamics;
  if (notch < -30000 + 1)
    return (-30000 + 1);
  if (notch > 30000 - 1)
    return (30000 - 1);
  for (i = 0; i < 4; i++)
    {
      hash = table_hash + (k + i);
      if ((hash->hash_64bit ^ (tower_dynamics->hash_64bit >> 32)) == 0)
        {
          if (hash->deepness_below)
            {
              score = (hash->score_below);
              if (score >= notch)
                return (score);
            }
          if (hash->deepness_above)
            {
              score = (hash->score_above);
              if (score < notch)
                return (score);
            }
          transpositional_deepness = hash->deepness_below;
          move = hash->move;
          if (move && transpositional_deepness > move_deepness)
            {
              move_deepness = transpositional_deepness;
              transpositional_movement = move;
            }
        }
    }
  best_valuation = (tower_structure - (table_dynamics + 1)) - 30000;
  intention = 0xffffffffffffffff;
  if (tower_structure->score_value + 10 < notch)
    {
      best_valuation = tower_structure->score_value + 10;
      itog = notch - 200;
      intention = position_fixed.bitboard[enumerated_occupation_black];
      if (itog > best_valuation)
        {
          intention ^= position_fixed.bitboard[enumerated_black_pawns];
          itog = notch - 500;
          best_valuation += 200;
          if (itog > best_valuation)
            intention ^= (position_fixed.bitboard[enumerated_black_knight] | (position_fixed.bitboard[enumerated_black_bright] | position_fixed.bitboard[enumerated_black_faded]));
        }
    }
  move_list = white_escape (movement_listing, intention);
  if ((move_list - movement_listing) > 1)
    deepness--;
  p = movement_listing;
  while (p->move)
    {
      if ((p->move & 0x7fff) == transpositional_movement)
        p->move |= 0xfff00000;
      p++;
    }
  p = movement_listing;
  sch = 0;
  while (p->move)
    {
      move = p->move;
      q = ++p;
      while (q->move)
        {
          if (move < q->move)
            {
              temp = q->move;
              q->move = move;
              move = temp;
            }
          q++;
        }
      if ((move & (1 << 15)) && notch > -25000 && (move & 0x7fff) != transpositional_movement && !white_trader (move))
        {
          sch++;
          continue;
        }
      if (position_fixed.square[((move) & 077)] == 0 && (move & 0x6000) == 0 && (move & 0x7fff) != transpositional_movement && ((tower_dynamics->flag) & 2) && ((int) increment_maximal[position_fixed.square[(((move) >> 6) & 077)]][move & 07777]) + tower_structure->score_value < notch + 25 && notch > -25000)
        {
          sch++;
          continue;
        }
      move &= 0x7fff;
      white_spell (move);
      evaluation_scoring (notch - 150, notch + 150, move);
      if (((tower_structure + 1)->white_king_check))
        {
          white_unspell (move);
          continue;
        }
      if (((tower_structure + 1)->black_king_check))
        itog = -black_qsearching_check (1 - notch, deepness);
      else
        itog = -black_qsearching (1 - notch, deepness);
      white_unspell (move);
      if (itog <= best_valuation)
        continue;
      best_valuation = itog;
      if (itog >= notch)
        {
          hash_below (tower_dynamics->hash_64bit, move, 1, itog);
          return (itog);
        }
    }
  if (sch && best_valuation < -25000)
    best_valuation = notch - 1;
  hash_above (tower_dynamics->hash_64bit, 1, best_valuation);
  return (best_valuation);
}

The first line * QSEARCH_CHECK(SCORE,depth) defines the function. The first expression on the second line is hidden!

Code: Select all

< | HASH_READ&TRANS | %HEIGHT% | ##TARGET |

The pipe (|) precedes the HASH_READ&TRANS and actuates the boilerplate checks

Code: Select all

  if (tower_dynamics->non_permanent >= 100)
    return (0);
  for (i = 4; i <= tower_dynamics->non_permanent && i <= elevation_stack; i += 2)
    if (stack[elevation_stack - i] == tower_dynamics->hash_64bit)
      return (0);
  tower_structure = tower_dynamics;
  if (notch < -30000 + 1)
    return (-30000 + 1);
  if (notch > 30000 - 1)
    return (30000 - 1);

These check for 50 moves, for repetition, and for a scout value that is out of bounds.

The next expression is the same HASH_READ&TRANS that was in LowDepth

Code: Select all

  for (i = 0; i < 4; i++)
    {
      hash = table_hash + (k + i);
      if ((hash->hash_64bit ^ (tower_dynamics->hash_64bit >> 32)) == 0)
        {
          if (hash->deepness_below)
            {
              score = (hash->score_below);
              if (score >= notch)
                return (score);
            }
          if (hash->deepness_above)
            {
              score = (hash->score_above);
              if (score < notch)
                return (score);
            }
          transpositional_deepness = hash->deepness_below;
          move = hash->move;
          if (move && transpositional_deepness > move_deepness)
            {
              move_deepness = transpositional_deepness;
              transpositional_movement = move;
            }
        }
    }

The C code is exactly the same as for LowDepth!

The next expression is %HEIGHT% and the %...% sets the best_value to be the HEIGHT, and this is the ply count minus 30000

Code: Select all

  best_valuation = (tower_structure - (table_dynamics + 1)) - 30000;

The next expression is ##TARGET, and the double ## means to consider all targets (0xffffffffffffffff). In LowDepth the #TARGET asked with only opposing pieces. The same appears here later below.

Code: Select all

intention = 0xffffffffffffffff;

The next line is a long expression for delta pruning. Ippolit does this even when in check!

Code: Select all

 [ BEHIND < 10 ] %(&EVAL+10)% + #TARGET + DELTA_PRUNING[ pawn:200* | minor:500 ] |

The bracketed term is the if-condition, where BEHIND is the amount between the current evaluation and the scout value. I think it is wrong! It should be [ BEHIND > 10 ] I think. The same condition is also absent in the ь code for PV_QSEARCH_CHECK, though the C code has it. But translating it says that if BEHIND is large, then make the best_value with the %...% operation equal to the evaluation plus 10, and also change the target to #TARGET, so the opposing pieces, and finally do delta pruning of pawns if the BEHIND is 200 and minor if the BEHIND is 500. The * on the 200 with the pawn increases the best_value by 200 when pruning. Compared to LowDepth the condition lacks # in front of the number, so attacking a pawn is not a necessity.

Code: Select all

 if (tower_structure->score_value + 10 < notch)
    {
      best_valuation = tower_structure->score_value + 10;
      itog = notch - 200;
      intention = position_fixed.bitboard[enumerated_occupation_black];
      if (itog > best_valuation)
        {
          intention ^= position_fixed.bitboard[enumerated_black_pawns];
          itog = notch - 500;
          best_valuation += 200;
          if (itog > best_valuation)
            intention ^= (position_fixed.bitboard[enumerated_black_knight] | 
                          (position_fixed.bitboard[enumerated_black_bright] | 
                           position_fixed.bitboard[enumerated_black_faded]));
        }
    }

The next line and expression does the move generation (@) for evasions

Code: Select all

@EVASION(TARGET)^TRANS |

The TARGET here has been set from the pruning, and the TRANS after the caret demands this move go first when the next SORT is applied.

Code: Select all

move_list = white_escape (movement_listing, intention);
  if ((move_list - movement_listing) > 1)
    deepness--;
  p = movement_listing;
  while (p->move)
    {
      if ((p->move & 0x7fff) == transpositional_movement)
        p->move |= 0xfff00000;
      p++;
    }

An addition here is that the depth is decreased only if the move is not forced. The white_escape generator gives only legal moves.

The next three lines make the loop over moves

Code: Select all

SORT< [ INTERPOSE ] + [ !CAPTURE_OR_PROMOTION ] + [ !TRANS ]
           + [ MY_NULL ] + [ !MATE ]+ [ MAXIMUM_REWARD + AHEAD < 25 ] count! ||
          EVAL(150) ! %QSEARCH#(1-SCORE,depth) > |

The first line contains SORT that does better moves first. The best move is the TRANS move, then captures, and then history scores. These are appended in the upper bits within the white_escape. The rest of the first two lines is a long pruning condition (even in check!). It says that if a move is an interposition (with bad SEE) and not a capture or promotion, and not the TRANS move, and I have a piece left (MY_NULL) other than one minor, and the scout value is not a MATE score, and the MAXIMUM_REWARD plus the amount AHEAD is small, then increment the count and skip the move.

Code: Select all

      if ((move & (1 << 15)) && notch > -25000 &&
          (move & 0x7fff) != transpositional_movement && !white_trader (move))
        {
          sch++;
          continue;
        }

This does the interposition, then the MATE check (-25000), then the TRANS move, then the SEE call.

Code: Select all

      if (position_fixed.square[((move) & 077)] == 0 && (move & 0x6000) == 0 &&
         (move & 0x7fff) != transpositional_movement &&
         ((tower_dynamics->flag) & 2) &&
         ((int) increment_maximal[position_fixed.square[(((move) >> 6) & 077)]][move & 07777]) + tower_structure->score_value < notch + 25 &&
         notch > -25000)
        {
          sch++;
          continue;
        }

The first line here checks for capture (square of TO is empty) or promotion (move & 0x6000, with en passant in too), then the second line does the TRANS check again. The (flag & 2) is whether white can do nullmove. The fourth line includes the check of whether the MAXIMAL_REWARD from the move is enough with AHEAD included. This MAXIMAL_REWARD is an expectation of the positional gain (no captures) from a move. Finally the question of whether the scout value is a MATE score is asked again. I don't know if the order of calls is best with SEE here, and there are redundant calls.

Finally we are ready to make the move and iterate the search.

Code: Select all

EVAL(150) ! %QSEARCH#(1-SCORE,depth) > |

The double pipe at the end of the previous ь code is the make_move operator, and here it calls EVAL with a lazy margin of 150. The LowDepth function had a double !! after EVAL, and the difference is not yet clear. Perhaps the move does not need to be checked for legality in evasion? But then it does check that... The other guess is that is has to do with the LowDepth function ignoring checking moves when the search is "type 3" but this is a guess.

Code: Select all

      move &= 0x7fff;
      white_spell (move);
      evaluation_scoring (notch - 150, notch + 150, move);
      if (((tower_structure + 1)->white_king_check))
        {
          white_unspell (move);
          continue;
        }
      if (((tower_structure + 1)->black_king_check))
        itog = -black_qsearching_check (1 - notch, deepness);
      else
        itog = -black_qsearching (1 - notch, deepness);
      white_unspell (move);

The QSEARCH for black is called depending on whether the white move gives check. After this, the compact ь code appears again, as the checks for "itog" more than "notch" (value > beta) occur invisibly

Code: Select all

      if (itog <= best_valuation)
        continue;
      best_valuation = itog;
      if (itog >= notch)
        {
          hash_below (tower_dynamics->hash_64bit, move, 1, itog);
          return (itog);
        }

The hash appears even in QSEARCH. However HISTORY does not, recalling that the function definition did not have a HISTORY caret after it.

Finally outside the move loop, the score is checked against MATE, and hash_above called (again invisible)

Code: Select all

  [ count ] + [ %% < -MATE ] %SCORE-1%

This says when the count of moves is nonzero and the best_value (%%) is a MATE score, then return one less than the scout value. The logic is that moves were "skipped" by the pruning and so MATE should not be returned.

Code: Select all

  if (sch && best_valuation < -25000)
    best_valuation = notch - 1;
  hash_above (tower_dynamics->hash_64bit, 1, best_valuation);
  return (best_valuation);

This ends QSEARCH_IN_CHECK. Other than the problem with the apparent BEHIND reversal, it is easier than others.

Posted: **Thu Feb 03, 2011 7:43 am**

Here is my ь code

Code: Select all

* ROOT_NODE(ALPHA,BETA,depth)&ROOT_MOVELIST^ROOT_HISTORY
  < PRE-ORDERING
   < || EVAL |
     [ [ %% ] + [ depth > 2 ] ]
      %CUT/LOW#(-ALPHA,depth-2+&check)^{ BATTLING_MOVE + !EASY_MOVE } ^
      %PV(-ALPHA-1,-ALPHA,depth-2+&check,&check) ^ %PV(-BETA,-ALPHA,depth-2+&check,&check)
     \ %PV(-BETA,-ALPHA,depth-2+&check,&check) |
     [ (&) > %% ]#
      ![ [ %% ] + [ value<=ALPHA ] ] [ UPDATE | [ (&) >= ROOT_PREVIOUS-25 ] GOOD \ BAD ] |
     [ (&) > ALPHA ]# \ [ count == 0 ] BAD |
     [ (&) >= BETA ] %%! | count > 
   ORDERING
  >

There are two functions that this looks like, both white_top and white_root. The first white_top seems to just handle the PRE-ORDERING and the aspiration. I might be wrong and the PRE-ORDERING is the first bit in white_root.

Code: Select all

int
white_root (int below, int above, int deepness)
/* declarations omitted here */
  if (above > 30000)
    above = 30000;
  if (below < -30000)
    below = -30000;
  counter = 0;
  for (p = rooted_movement_listing; p->move; p++)
    {
      counter++;
      p->move &= 0x7fff;
    }
  previous_below = below;
  p = rooted_movement_listing;
  itog = best_valuation = -32750;
  sch = 0;

The code first checks for above and below (beta and alpha) to be in range, and then counts the moves with setting them to 15 bits for the length. I however don't see any ordering in this place.

Then the move loop begins

Code: Select all

The code first checks for above and below (beta and alpha) to be in range, and then counts the moves with setting them to 15 bits for the length. I however don't see any ordering in this place.

Then the move loop begins

All the moves are legal at the root, so there is no illegality condition. The yes_check variable sees if a move gives check, and the new_depth is then added to by one when this happens. This is given by the ь code as

Code: Select all

   < || EVAL |
     [ [ %% ] + [ depth > 2 ] ]
      %CUT/LOW#(-ALPHA,depth-2+&check)^{ BATTLING_MOVE + !EASY_MOVE } ^
      %PV(-ALPHA-1,-ALPHA,depth-2+&check,&check) ^ %PV(-BETA,-ALPHA,depth-2+&check,&check)
     \ %PV(-BETA,-ALPHA,depth-2+&check,&check) |

The first || (double pipe) already makes the move with no conditions. Then EVAL is called with a full window. The next four lines form an if-then statement. As with other parts, the ь code uses agglutinative constructs and the first line gives the if condition. If the current best_score (given by %%, with nothing intervening the percentages) is available, which means the move is not the first, and the depth exceeds 2 halves-ply, then there is a switching for CUT/LOW depending on depth (the ь parser knows when), with the # flag I think calling the in_check functions when ready, and the &check variable coming from the EVAL call. Everything after the backslash (\) is in the else condition. When the move is the first (best_value is trivial) or the depth is 2 halves-ply or less, then the PV is called directly.

But the CUT/LOW switch has additional conditions. The first caret with the braces is the trigger condition when the fail-high occurs, and it sets that the root move is not easy, and there is a battling move for time constraints. The next caret is an agglutinative function call, of the PV node function but with a null-window, and finally if this also fails high then the full-window PV node function is again called.

Code: Select all

if (best_valuation == -32750 || deepness <= 2)
        itog = -black_pv (-above, -below, novel_deepness, yes_check);
      else
        {
          if (yes_check)
            {
              if (novel_deepness <= 7)
                itog = -black_slide_check (-below, novel_deepness);
              else
                itog = -black_cut_check (-below, novel_deepness);
            }
          else
            {
              if (novel_deepness <= 7)
                itog = -black_slide (-below, novel_deepness);
              else
                itog = -black_cut (-below, novel_deepness);
            }
          if (itog > below)
            {
              move_battle = 1;
              move_easy = 0;
            }
          if (itog > below)
            itog = -black_pv (-below - 1, -below, novel_deepness, yes_check);
          if (itog > below)
            itog = -black_pv (-above, -below, novel_deepness, yes_check);
          if (itog <= below)
            itog = below;
        }

The switching for CUT/LOW (called cut and slide) is 7 halves-ply.

The completion of this function I think is special bookkeeping for the root.

Code: Select all

     [ (&) > %% ]#
      ![ [ %% ] + [ value<=ALPHA ] ] [ UPDATE | [ (&) >= ROOT_PREVIOUS-25 ] GOOD \ BAD ] |

The first line is an if condition that says that if the iterative evaluation (&) is exceeding the best_value (%%), and the # will update the best_value if so. The C translation first includes some work with unmake and move updates.

Code: Select all

      white_unspell (move);
      if (itog <= below)
        temp_valuation = previous_below;
      else
        temp_valuation = itog;
      p->move |= (temp_valuation + 0x8000) << 16;

I am not sure about the next line in the ь code for it is not a then construct, but another if condition.
The ![ [ %% ] + [ value<=ALPHA ] ] demands that the best_value not exist or the iterative evaluation exceed alpha (called below in the C translation). I don't see where the ь code assign the variable "value" either.

Code: Select all

      if (itog > best_valuation)
        {
          best_valuation = itog;
          if (best_valuation == -32750 || itog > below)
            {
              best_move = move;
              best_score = itog;
              best_depth = deepness;
              if (itog > below && itog < above)
                informatory_fullness (clock_time () - clock_beginning, previous_below, itog, above);
              if (itog >= best_score_previous - 25)
                move_drop = 0;
              else
                {
                  move_drop = 1;
                  move_easy = 0;
                }
            }
        }

Maybe the ь code is missing a pipe (|) to divide the two if conditions. The then construct then does UPDATE, which makes all the best_ variables be updated, and informs the user (UCI) on occasion. The further part of the then has [ (&) >= ROOT_PREVIOUS-25 ] GOOD \ BAD ] that determines if the evaluation (&) is too small with the evaluation of the previous iteration by 25, and declares either GOOD or BAD for this. The GOOD sets move_drop as 0, and the opposite sets it as 1 with the move_easy flag forbidden.

The next ь code updates for alpha.

Code: Select all

     [ (&) > ALPHA ]# \ [ count == 0 ] BAD |

The first line demands if the iterative evaluation (&) exceeds ALPHA, and the # on the condition sets it if so. The backslash (\) enters an else condition that if the move is initial (the count is 0) then the BAD occurs, so that move_drop is 1 and move_easy is forbidden.

Code: Select all

      if (itog <= below)
        {
          if (sch == 0)
            {
              move_drop = 1;
              move_easy = 0;
            }
        }
      else
        below = itog;

I cannot see why the 25 limit for the former was necessary as the aspiration window will be smaller after enough iterations occur, and then the fail-low with ALPHA is sufficient. I think it is a low depth condition when the aspiration is still full-width.

The next ь code checks for a beta bound, and if so return the evaluation (%%!), though I think this is ignored. The count is incremented.

Code: Select all

    [ (&) >= BETA ] %%! | count >

This gets reordered in the C translation and the logic inverted.

Code: Select all

      sch++;
      if (itog < above)
        {
          p++;
          continue;
        }
      break;
    }

Finally the ь code ends with the unhelping word ORDERING

Code: Select all

   ORDERING
  >

The root history and root move list that were original flags in the function call are updated for this.

Code: Select all

  for (p = rooted_movement_listing + (counter - 1); p >= rooted_movement_listing; p--)
    {
      move = p->move;
      for (q = p + 1; q < rooted_movement_listing + counter; q++)
        {
          if ((move & 0xffff0000) < (q->move & 0xffff0000))
            (q - 1)->move = q->move;
          else
            break;
        }
      q--;
      q->move = move;
    }
  best_depth = deepness;
  informatory_fullness (clock_time () - clock_beginning, previous_below, best_valuation, above);
  return best_valuation;
}

The top 16 bits of a move are the score from the setting of p->move |= (temp_valuation + 0x8000) << 16 so that this orders the root moves. The UCI is informed about the result, and best_value returned. I don't see the root_history in the C translation, and the white_top is also not a place for it.

This ends the RootNode construct, and I think a lot is hidden by the ь parser, or maybe a different code version was in use.

Posted: **Thu Feb 03, 2011 7:58 am**

I'm not going to give the whole C code at once, but just paste it in as I go. Here is the ь code translated

Code: Select all

* PV_NODE(LOWER,UPPER,depth,check)^HISTORY#
  < [ depth <= 1 ] *%PV_QSEARCH#[check](LOWER,UPPER,depth)! |
    HASH[PV]_READ&TRANS&hashdepth |
    [ [ !TRANS ] + [ depth >= 6] ]
    *%PV[ depth >= 10](LOWER-depth,UPPER+depth,depth-8,check)^TRANS ^ 
     *%PV(LOWER-depth,UPPER+depth,depth-4,check)^TRANS
    \ [ [ depth >= 10 ] + [ depth >= hashdepth + 8] ]
      *%PV(LOWER-depth,UPPER+depth,depth-8,check)^TRANS ^
       *%PV(LOWER-depth,UPPER+depth,depth-4,check)^TRANS |
    [ check ] [ @EVADE() | [ #moves < 2 ] SINGULAR*[ #moves ] ] |
    [ depth >= 16 ] + [ OK_MOVE(TRANS) ] + [ SINGULAR < 2 ]
     [ || EVAL ! %PV(-UPPER,-LOWER,depth-10,&check) @!
       *%EXCLUDE[check]#((&)-depth/2,depth-MINIMUM(12,depth/2),TRANS)^SINGULAR ^
        *%EXCLUDE[check]#((&)-depth,depth-MINIMUM(12,depth/2),TRANS)^SINGULAR ] |
    << [ REPETITION# ] %MAXIMUM(%%,0)% + count! ||
       EVAL() !
       [PASSED_PAWN_PUSH(6th)] EXTENSION + EXTENSION
       \ [ !CAPTURE ] EXTENSION
       \ [ & check ] EXTENSION
       \ [ check ] + [ EARLYGAME ] EXTENSION
       \ [ PASSED_PAWN_PUSH(4th) ] EXTENSION |
       [ TRANS ] + [ depth-2+MAXIMUM(EXTENSION,SINGULAR) > 1 ]
        %CUT/LOW#(-LOWER,&LEFT_VALUE)^%PV(-UPPER,-LOWER,&LEFT_VALUE,&check)
       \ %PV(-UPPER,-LOWER,depth-2+MAXIMUM(EXTENSION,SINGULAR),&check) >>
    [ !%% ] [ [ check ] (0)! \ HEIGHT! ]
  >

I reformatted this to make it more clear somewheres.

The initial line names the function (I called it PV_NODE here, but PV below), and has some flags

Code: Select all

* PV_NODE(LOWER,UPPER,depth,check)^HISTORY#

The first is that the function takes LOWER and UPPER rather than just one value (SCORE), and also that is has a flag for in-check. There is also the HISTORY flag after the caret, and the # makes it use LOWER rather than SCORE (seen below).

The next line and expression calls QSEARCH when depth is small (not more than 1)

Code: Select all

  < [ depth <= 1 ] *%PV_QSEARCH#[check](LOWER,UPPER,depth)! |

The % is a usual function call, but *% makes it a self-call (white to white, rather than white to black). The LOWER and UPPER and depth and passed. The # on PV_QSEARCH plus the [check] seems redundant to me, as I though the # itself did a check splitting. The final ! demands to return the value obtained from PV_QSEARCH. Also the first pipe (|) actuates the 50-move rule and repetition checks

Code: Select all

  if (above < -30000)
    return (-30000);
  if (below > 30000)
    return (30000);
  if (deepness <= 1)
    {
      if (shah)
        return pv_white_qsearching_check (below, above, 1);
      else
        return pv_white_qsearching (below, above, 1);
    }
  if (tower_dynamics->non_permanent >= 100)
    return (0);
  for (i = 4; i <= tower_dynamics->non_permanent && i <= elevation_stack; i += 2)
    if (stack[elevation_stack - i] == tower_dynamics->hash_64bit)
      return (0);

The very first to check is that LOWER and UPPER are in range, and then the depth <= 1 split, with the 50 moves and repetition trailing thereof.

The hash code should be familiar, but has many flags too

Code: Select all

 HASH[PV]_READ&TRANS&hashdepth |

The READ and TRANS are with the same as before. The [PV] ensures that "exact" hash entries have care, and the hashdepth tracks this. I think the &VARIABLE construction means to save VARIABLE

Code: Select all

S->transpositional_movement = 0;
  hash_deepness = 0;
  S->move = 0;
  S->wrong_capturings_enumerator = 0;
  k = tower_dynamics->hash_64bit & hash_mask;
  (tower_structure + 1)->move = 0;
  for (i = 0; i < 4; i++)
    {
      hash = table_hash + (k + i);
      if ((hash->hash_64bit ^ (tower_dynamics->hash_64bit >> 32)) == 0)
        {
          transpositional_deepness = hash->deepness_below;
          move = hash->move;
          if (move && transpositional_deepness > move_deepness)
            {
              move_deepness = transpositional_deepness;
              (tower_structure + 1)->move = transpositional_movement = move;
            }
          if (hash->deepness_below > hash->deepness_above)
            {
              transpositional_deepness = hash->deepness_below;
              score = (hash->score_below);
            }
          else
            {
              transpositional_deepness = hash->deepness_above;
              score = (hash->score_above);
            }
          if (transpositional_deepness > hash_deepness)
            hash_deepness = transpositional_deepness;
          if (((hash)->flag & 16) && transpositional_deepness >= deepness)
            {
              hash->ancientness = AGEDNESS;
              if (!analysis_mode)
                return (score);
            }
        }
    }

The "hash->flag & 16" is the direct [PV] part. The score is given as whichever for the below/above hash depths is greater. If analysis_mode is ON then a hash score from the PV is ignored.

The next lines are the iterative calls to find a quality hash move when none is apparent.

Code: Select all

    [ [ !TRANS ] + [ depth >= 6] ]
    *%PV[ depth >= 10](LOWER-depth,UPPER+depth,depth-8,check)^TRANS ^ 
     *%PV(LOWER-depth,UPPER+depth,depth-4,check)^TRANS
    \ [ [ depth >= 10 ] + [ depth >= hashdepth + 8] ]
      *%PV(LOWER-depth,UPPER+depth,depth-8,check)^TRANS ^
       *%PV(LOWER-depth,UPPER+depth,depth-4,check)^TRANS |

This is six lines, but rather formulaic. First the three beginning lines. The first condition demands that the TRANS move not exist, and that the depth is at least 6 halves-ply. When this is true, there is a splitting. The [depth>=10] conditional on the self-call of PV (from *%) is the first condition. When it is true, PV is iterated at four ply lower, and if this works for a hash move (not failing low), at two ply (4 halves-ply) again. The TRANS after the caret means to append the TRANS move when found. The caret (^) after that is the conjunctive that says to search again when the TRANS appears at the outset.

Code: Select all

  if (!transpositional_movement && deepness >= 6)
    {
      itog = below;
      if (deepness >= 10)
        {
          itog = white_pv (below - deepness, above + deepness, deepness - 8, shah);
          if (itog > below - deepness)
            transpositional_movement = (tower_structure + 1)->move;
        }
      if (itog > below - deepness)
        itog = white_pv (below - deepness, above + deepness, deepness - 4, shah);
      if (itog > below - deepness)
        transpositional_movement = (tower_structure + 1)->move;
    }

From the code the condition for the disjunctive is that the returned value from white_pv must not fail low (with a margin of deepness). When depth is less 10 (five total ply), only the 2 ply reduction is tested, but otherwise the 4 ply is tested first, and must work for the later iteration.

In the other case, in the else conditional with the backslash (\), the condition is that depth be at least 10 halves-ply and the searching depth be 8 halves-ply more than the depth from the hash entry.

Code: Select all

    \ [ [ depth >= 10 ] + [ depth >= hashdepth + 8] ]
      *%PV(LOWER-depth,UPPER+depth,depth-8,check)^TRANS ^
       *%PV(LOWER-depth,UPPER+depth,depth-4,check)^TRANS |

This is the case where a TRANS move exists, but is not very deep. The iterative PV call is as before, with the 8 halves-ply reduction first, and again at 2 full ply when this works.

Code: Select all

 else if (deepness >= 10 && deepness > hash_deepness + 8)
    {
      itog = white_pv (below - deepness, above + deepness, deepness - 8, shah);
      if (itog > below - deepness)
        transpositional_movement = (tower_structure + 1)->move;
      if (itog > below - deepness)
        {
          itog = white_pv (below - deepness, above + deepness, deepness - 4, shah);
          if (itog > below - deepness)
            transpositional_movement = (tower_structure + 1)->move;
        }
    }

Again the condition for benefice with a TRANS move is for it not to fail low. I do not understand why the C code has "deepness > hash_deepness + 8" but the ь code has "depth >= hashdepth + 8" for the comparison should be similar.

I'm not sure I agree with the logic here for the first place. Why do I need check at 2 ply again after it works at 4 ply?

The next ь code condition discerns based upon whether the side is in check

Code: Select all

[ check ] [ @EVADE() | [ #moves < 2 ] SINGULAR*[ #moves ] ] |

The condition of the if-else is simply [check], and when true the EVADE generator (@) is called, with no TARGET element (other than 0xffffffffffffffff). If the #moves is < 2 there is an extension (singular), with one half-ply when there are two moves, and one whole ply on a forced move. I don't see why the condition is "#moves < 2" rather than "#moves <= 2" here, really. The syntax is obscure.

Code: Select all

S->transpositional_movement = transpositional_movement;
  S->phase = transpositional;
  stretches = 0;
  S->target = position_fixed.bitboard[enumerated_occupation_black];
  if (shah)
    {
      move_list = white_escape (S->movement_listing, 0xffffffffffffffff);
      S->phase = rebut_check;
      for (p = move_list - 1; p >= S->movement_listing; p--)
        {
          if ((p->move & 0x7fff) == transpositional_movement)
            p->move |= 0xffff0000;
          else if (p->move <= (0x80 << 24))
            {
              if ((p->move & 0x7fff) == tower_structure->murderer_1)
                p->move |= 0x7fff8000;
              else if ((p->move & 0x7fff) == tower_structure->murderer_2)
                p->move |= 0x7fff0000;
              else
                p->move |= (p->move & 0x7fff) | (history_tabular[position_fixed.square[(((p->move) >> 6) & 077)]][((p->move) & 077)] << 15);
            }
          move = p->move;
          for (q = p + 1; q < move_list; q++)
            {
              if (move < q->move)
                (q - 1)->move = q->move;
              else
                break;
            }
          q--;
          q->move = move;
        }
      if ((move_list - S->movement_listing) <= 1)
        singular = 2;
      if ((move_list - S->movement_listing) == 2)
        singular = 1;
      if ((move_list - S->movement_listing) > 2)
        singular = 0;
    }

The magic expansion happens again here, as the singular condition appears only at the end, after the sorting phase is included after the EVADE. This includes the TRANS move, and killer moves (murderers), and then proceeds to use history values.

There is one more expression before the iterative move loop

Code: Select all

    [ depth >= 16 ] + [ OK_MOVE(TRANS) ] + [ SINGULAR < 2 ]
     [ || EVAL ! %PV(-UPPER,-LOWER,depth-10,&check) @!
       *%EXCLUDE[check]#((&)-depth/2,depth-MINIMUM(12,depth/2),TRANS)^SINGULAR ^
        *%EXCLUDE[check]#((&)-depth,depth-MINIMUM(12,depth/2),TRANS)^SINGULAR ] |

This is another singular extension check. The first line is the conditional (agglutinative via +), and demands the depth be at least 8 full ply, the TRANS move be valid, and the move not already be maximal SINGULAR. When true, the double pipe (||) makes the TRANS move, and EVAL is called with no lazy margin. Below I see EVAL(), and the difference is unclear.
The point of the code is to see if only the TRANS move is useful. This accomplishes by first evaluating the TRANS move at depth-10, or five ply less. This is done via %PV(-UPPER,-LOWER,depth-10,&check) where the &check comes from the result of EVAL I think. The final @! undoes the move, and saves the value of the iterative call in "(&)" it seems. The exclusion search is called, with a [check] splitting, first with a margin of "depth/2" around the "(&)" value and depth reduced by 12 halves-ply (in general), with the excluded move being TRANS. If this fails low then SINGULAR is increased and another call is made for the same with the margin now as "depth" around the "(&)" value, with again SINGULAR increased if it fails low.

Code: Select all

 if (deepness >= 16 && S->transpositional_movement && singular < 2 &&
      white_ok (S->transpositional_movement))
    {
      move = S->transpositional_movement;
      kk = ((move) & 077);
      ot = (((move) >> 6) & 077);
      white_spell (move);
      evaluation_scoring (-0x7fff0000, 0x7fff0000, move);
      if (((tower_structure + 1)->white_king_check))
        {
          white_unspell (move);
          goto zab;
        }
      score = -black_pv (-above, -below, deepness - 10, (((tower_structure + 1)->black_king_check)) != 0);
      white_unspell (move);
      if (shah)
        itog = white_exclustion_check (score - deepness / 2, 
               deepness - (((12) <= (deepness / 2)) ? (12) : (deepness / 2)), move & 0x7fff);
      else
        itog = white_exclustion (score - deepness / 2,
               deepness - (((12) <= (deepness / 2)) ? (12) : (deepness / 2)), move & 0x7fff);
      if (itog < score - deepness / 2)
        {
          singular = 1;
          if (shah)
            itog = white_exclustion_check (score - deepness, 
                   deepness - (((12) <= (deepness / 2)) ? (12) : (deepness / 2)), move & 0x7fff);
          else
            itog = white_exclustion (score - deepness, 
                   deepness - (((12) <= (deepness / 2)) ? (12) : (deepness / 2)), move & 0x7fff);
          if (itog < score - deepness)
            singular = 2;
        }
    }

The idea is that if all other moves than TRANS are bad then the TRANS move is singular. The legality check of TRANS is invisible in the ь code, except maybe for the pipe (|) after EVAL.

The final part of the PV function is the move iterator

Code: Select all

    << [ REPETITION# ] %MAXIMUM(%%,0)% + ct! ||
       EVAL() !
       [PASSED_PAWN_PUSH(6th)] EXTENSION + EXTENSION
       \ [ !CAPTURE ] EXTENSION
       \ [ & check ] EXTENSION
       \ [ check ] + [ EARLYGAME ] EXTENSION
       \ [ PASSED_PAWN_PUSH(4th) ] EXTENSION |
       [ TRANS ] + [ depth-2+MAXIMUM(EXTENSION,SINGULAR) > 1 ]
        %CUT/LOW#(-LOWER,&LEFT_VALUE)^%PV(-UPPER,-LOWER,&LEFT_VALUE,&check)
       \ %PV(-UPPER,-LOWER,depth-2+MAXIMUM(EXTENSION,SINGULAR),&check) >>

The first line is a repetition check, then after the EVAL call there are five lines of EXTENSION concerns. The last three lines determine which search function to call.

The REPETITION check is similar to the one in LowDepth, except that LOWER is used as a base rather than SCORE, which is the # effect I think.

Code: Select all

    << [ REPETITION# ] %MAXIMUM(%%,0)% + count! ||

The determination is made whether the LOWER bound is at least 0, and if so and the move made is invertible, then the move is skipped, with the best value (%%) updated to 0 if not so already via the %...% operation, and finally the move count is increased, and the loop continued (count! with exclam continuing).

Code: Select all

 while ((move = white_next (S)))
    {
      kk = ((move) & 077);
      ot = (((move) >> 6) & 077);
      if (below > 0 && 
          tower_structure->non_permanent >= 2 && 
          ((((move) & 077) << 6) | (((move) >> 6) & 077)) == (tower_structure - 1)->move && 
          position_fixed.square[((move) & 077)] == 0)
        {
          best_valuation = (((0) >= (best_valuation)) ? (0) : (best_valuation));
          continue;
        }

Everything follows as in LowDepth except for "below" other than "notch" in there.

The EVAL() is called, with various conditions for extending added

Code: Select all

       EVAL() !
       [PASSED_PAWN_PUSH(6th)] EXTENSION + EXTENSION
       \ [ !CAPTURE ] EXTENSION
       \ [ & check ] EXTENSION
       \ [ check ] + [ EARLYGAME ] EXTENSION
       \ [ PASSED_PAWN_PUSH(4th) ] EXTENSION |

If a PASSED_PAWN_PUSH to the 6th rank happens, then EXTENSION is incremented twice. I get lost in the next phase, and the C code seems to differ. At the end, a PASSED_PAWN_PUSH to the 4th rank gets a single EXTENSION (half-ply).

Code: Select all

      move &= 0x7fff;
      white_spell (move);
      evaluation_scoring (-0x7fff0000, 0x7fff0000, move);
      if (((tower_structure + 1)->white_king_check))
        {
          white_unspell (move);
          continue;
        }
      yes_check = (((tower_structure + 1)->black_king_check) != 0);

This is just the EVAL part, with the legality check. Then there is

Code: Select all

 stretches = 0;
      if (stretches < 2)
        {
          if ((position_fixed.square[kk] == enumerated_white_pawns && ((kk) >= A6) &&
              (position_fixed.bitboard[enumerated_black_pawns] & passed_pawn_white[kk]) == 0))
            stretches = 2;
        }
      if (stretches < 2)
        {
          if ((tower_structure + 1)->captured != 0 ||
              yes_check ||
              (shah && ((tower_dynamics->material_64bit & 0xff) >= 18)))
            stretches = 1;
          else if ((position_fixed.square[kk] == enumerated_white_pawns && ((kk) >= A4) &&
                   (position_fixed.bitboard[enumerated_black_pawns] & passed_pawn_white[kk]) == 0))
            stretches = 1;
        }
      if (S->transpositional_movement != move)
        singular = 0;

The "stretches" are EXTENSIONS, and the first check is for the PASSED_PAWN_PUSH to the 6th (or 7th), with a double EXTENSION added if so. The next condition is to demand that a move is a capture, or is a check, or the position is already check and the game is "early" (18/32 of force), then make an extension. The final extension addition is when the PASSED_PAWN_PUSH is the 4th or more. The final bit here, an "invisible" line again, sets SINGULAR to zero if the move is not the TRANS move, for bookkeeping.

My guess is that [ !CAPTURE ] should be [ CAPTURE ], as the confusion is that "CAPTURE" involves "!= 0"
I think the original ь code had the three conditions on one line, so maybe that matters too

Code: Select all

       \ [ !CAPTURE ] EXTENSION \ [ & check ] EXTENSION \ [ check ] + [ EARLYGAME ] EXTENSION

Finally other search functions are called

Code: Select all

       [ TRANS ] + [ depth-2+MAXIMUM(EXTENSION,SINGULAR) > 1 ]
        %CUT/LOW#(-LOWER,&LEFT_VALUE)^%PV(-UPPER,-LOWER,&LEFT_VALUE,&check)
       \ %PV(-UPPER,-LOWER,depth-2+MAXIMUM(EXTENSION,SINGULAR),&check) >>

The condition is whether a move is the TRANS move, and if the following depth is at least 1. If so, then either CUT or LOW is called, with an invisible splitting based upon whether the new depth is 8 halves-ply or more. Again I think it should be [ !TRANS ] here, but I don't know. The "LEFT_VALUE" is the left-value from the above condition, and so is "depth-2+MAX(EXT,SING)" in shorthand. The caret (^) in the first call here is triggered when CUT or LOW returns a fail high, and then PV is called. The # after the CUT/LOW is a splitting for if the move is check, and this is in the &check for PV calls. When the condition fails, so the move is TRANS or the following depth is less than one whole ply, then PV is called directly. I don't see why LEFT_VALUE could not be used again, and the C code does so, in gratitude.

Code: Select all

novel_deepness = deepness - 2 + (((stretches) >= (singular)) ? (stretches) : (singular));
      if (S->transpositional_movement != move && novel_deepness > 1)
        {
          if (novel_deepness <= 7)
            {
              if (yes_check)
                itog = -black_slide_check (-below, novel_deepness);
              else
                itog = -black_slide (-below, novel_deepness);
            }
          else
            {
              if (yes_check)
                itog = -black_cut_check (-below, novel_deepness);
              else
                itog = -black_cut (-below, novel_deepness);
            }
          if (itog > below)
            itog = -black_pv (-above, -below, novel_deepness, yes_check);
        }
      else
        itog = -black_pv (-above, -below, novel_deepness, yes_check);
      white_unspell (move);

As can be seen, the TRANS condition is that when the move is the TRANS move (the first move) then PV is called without CUT/LOW first. I don't know what happens if there is no TRANS move. The "itog > below" condition demands that PV be called when CUT/LOW returns a high value.

Next there is the large "magic" block with bookkeeping and history, that is invisible in ь code.

Code: Select all

      if (itog <= below && position_fixed.square[((move) & 077)] == 0 && ((move & 060000) == 0))
        {
          int ist = history_tabular[position_fixed.square[(((move) >> 6) & 077)]][((move) & 077)];
          if (tower_structure->score_value > below - 50)
            history_tabular[position_fixed.square[(((move) >> 6) & 077)]][((move) & 077)] = 
              ist - ((ist * deepness) >> 8);
        }
      if (itog <= best_valuation)
        continue;
      best_valuation = itog;
      if (itog <= below)
        continue;
      below = itog;
      pleasant_move = move;
      hash_below (tower_dynamics->hash_64bit, move, deepness, itog);

When a move fails low, and is not a capture or promotion, and the evaluation is within 50 of the LOWER value, then the history is reduced. The # flag on the original HISTORY caret (^) in the function definition probably uses LOWER rather than SCORE as with LowDepth. The next lines update best_value and LOWER if necessary. If the move beats LOWER, then it is "pleasant", and has its hash updated for that.

Code: Select all

      if (itog >= above)
        {
          if (position_fixed.square[((move) & 077)] == 0 && ((move & 060000) == 0))
            {
              int ist = history_tabular[position_fixed.square[(((move) >> 6) & 077)]][((move) & 077)];
              history_tabular[position_fixed.square[(((move) >> 6) & 077)]][((move) & 077)] = 
                     ist + (((0xff00 - ist) * deepness) >> 8);
              if (move != tower_dynamics->murderer_1)
                {
                  tower_dynamics->murderer_2 = tower_dynamics->murderer_1;
                  tower_dynamics->murderer_1 = move;
                }
            }
          return (itog);
        }
    }

If a move fails high (itog >= above), then the update of history is again, with killer moves also. Again any ь parser "knows" all this.

Finally we get out of the move iteration loop.

Code: Select all

    [ !%% ] [ [ check ] (0)! \ HEIGHT! ]

The !%% determines if best_value has been set (no pruning other than repetition, so no moves if not), and if not, looks if check is set, and returns either 0 or MATE-HEIGHT. The logic again seems reversed?

Code: Select all

  move = pleasant_move;
  (tower_structure + 1)->move = pleasant_move & 0x7fff;
  if (best_valuation == -32750)
    {
      if (!shah)
        return (0);
      return ((tower_structure - (table_dynamics + 1)) - 30000);
    }

The C code also invisibly sets the "good move" at this level (tower+1) to be the pleasant move.

The last thing is to record the hash information when a move exists.

Code: Select all

  if (move)
    {
      if (position_fixed.square[((move) & 077)] == 0 && ((move & 060000) == 0))
        {
          int ist = history_tabular[position_fixed.square[(((move) >> 6) & 077)]][((move) & 077)];
          history_tabular[position_fixed.square[(((move) >> 6) & 077)]][((move) & 077)] = 
                 ist + (((0xff00 - ist) * deepness) >> 8);
          if (move != tower_dynamics->murderer_1)
            {
              tower_dynamics->murderer_2 = tower_dynamics->murderer_1;
              tower_dynamics->murderer_1 = move;
            }
        }
      hash_exactly (move, deepness, best_valuation, 16);
      return (best_valuation);
    }
  hash_above (tower_dynamics->hash_64bit, deepness, best_valuation);
  return (best_valuation);

When a pleasant move exists, its history is upgraded, and killers set, and hash_exactly is called as the value is between LOWER and UPPER. If no move exists, hash_above is called.

This ends the PV code. It seems filled with backwards logic, but the skeleton of it exists well.

Posted: **Thu Feb 03, 2011 8:13 am**

Here is a current understanding of the "LowDepth" function in IPPOLIT.

First for reference is the IPP_ENG.c code for white_slide

Code: Select all

int
white_slide (int notch, int deepness)
{
  int sch, score, best_valuation, itog, k, i, transpositional_movement = 0, move, move_deepness = 0, transpositional_deepness, kk, ot;
  type_next S[1];
  type_dynamics *tower_structure = tower_dynamics;
  type_hash *hash;
  if (notch < -30000 + 1)
    return (-30000 + 1);
  if (notch > 30000 - 1)
    return (30000 - 1);
  (tower_structure + 1)->move = 0;
  itog = tower_structure->score_value + 1125;
  if (itog < notch)
    return (notch - 1);
  if (tower_dynamics->non_permanent >= 100)
    return (0);
  for (i = 4; i <= tower_dynamics->non_permanent && i <= elevation_stack; i += 2)
    if (stack[elevation_stack - i] == tower_dynamics->hash_64bit)
      return (0);
  k = tower_dynamics->hash_64bit & hash_mask;
  for (i = 0; i < 4; i++)
    {
      hash = table_hash + (k + i);
      if ((hash->hash_64bit ^ (tower_dynamics->hash_64bit >> 32)) == 0)
        {
          if (hash->deepness_below >= deepness)
            {
              score = (hash->score_below);
              if (score >= notch)
                {
                  (tower_structure + 1)->move = hash->move;
                  return (score);
                }
            }
          if (hash->deepness_above >= deepness)
            {
              score = (hash->score_above);
              if (score < notch)
                return (score);
            }
          transpositional_deepness = hash->deepness_below;
          move = hash->move;
          if (move && transpositional_deepness > move_deepness)
            {
              move_deepness = transpositional_deepness;
              transpositional_movement = move;
            }
        }
    }
  itog = tower_structure->score_value - (70 + 10 * deepness);
  if (itog >= notch)
    return (tower_structure->score_value);
  best_valuation = (((tower_structure->score_value) <= (notch - 1)) ? (tower_structure->score_value) : (notch - 1));
  if (tower_structure->score_value >= notch && ((tower_dynamics->flag) & 2))
    {
      nullize ();
      itog = -black_qsearching (1 - notch, 0);
      unnullize ();
      if (itog >= notch)
        {
          hash_below (tower_dynamics->hash_64bit, transpositional_movement, deepness, itog);
          return (itog);
        }
    }
  S->phase = transpositional;
  S->target = position_fixed.bitboard[enumerated_occupation_black];
  if (tower_structure->score_value + 50 + 8 * deepness < notch)
    {
      S->phase = transpositional_2;
      if (notch >= tower_structure->score_value + 75 + 32 * deepness)
        {
          S->target ^= position_fixed.bitboard[enumerated_black_pawns];
          if (position_fixed.bitboard[enumerated_black_pawns] & tower_dynamics->white_attackeds)
            best_valuation += 125;
          if (deepness <= 3 && notch >= tower_structure->score_value + 400 + 32 * deepness)
            {
              S->target ^= (position_fixed.bitboard[enumerated_black_knight] | (position_fixed.bitboard[enumerated_black_bright] | position_fixed.bitboard[enumerated_black_faded]));
              best_valuation += 300;
              if (notch >= tower_structure->score_value + 600 + 32 * deepness)
                {
                  S->target ^= position_fixed.bitboard[enumerated_black_rook];
                  best_valuation += 200;
                }
            }
        }
    }
  else if (deepness <= 3 && tower_structure->score_value + 4 * deepness < notch)
    {
      S->phase = transpositional_3;
      S->mask = (notch - tower_structure->score_value) + 4 * deepness + 5;
    }
  S->wrong_capturings_enumerator = 0;
  S->move = 0;
  S->transpositional_movement = transpositional_movement;
  sch = 0;
  while ((move = white_next (S)))
    {
      kk = ((move) & 077);
      ot = (((move) >> 6) & 077);
      if ((notch > 0 && tower_structure->non_permanent >= 2 && ((((move) & 077) << 6) | (((move) >> 6) & 077)) == (tower_structure - 1)->move && position_fixed.square[((move) & 077)] == 0))
        {
          best_valuation = (((0) >= (best_valuation)) ? (0) : (best_valuation));
          sch++;
          continue;
        }
 
      if (sch >= deepness && S->phase == movement_anemic && position_fixed.bitboard[enumerated_occupation_white] ^ (position_fixed.bitboard[enumerated_white_king] | position_fixed.bitboard[enumerated_white_pawns]) && (move & 0xe000) == 0 && bitboard_force[ot] & ~(tower_dynamics->white_encoded_xray))
        {
          if ((2 * deepness) + ((int) increment_maximal[position_fixed.square[(((move) >> 6) & 077)]][move & 07777]) + tower_structure->score_value < notch + 40 + 2 * sch)
            {
              sch++;
              continue;
            }
        }
      if ((position_fixed.square[kk] == 0 || (deepness <= 5 && !(move & 0x300000))) && bitboard_force[ot] & ~(tower_dynamics->white_encoded_xray) && position_fixed.square[ot] != enumerated_white_king && !(((move) & 070000) == 030000) && move != transpositional_movement && !white_trader (move))
        {
          sch++;
          continue;
        }
      move &= 0x7fff;
      white_spell (move);
      evaluation_scoring (notch - 150, notch + 150, move);
      if (((tower_structure + 1)->white_king_check) || (S->phase == gaineds && ((tower_structure + 1)->black_king_check)))
        {
          white_unspell (move);
          continue;
        }
      if (((tower_structure + 1)->black_king_check))
        itog = -black_slide_check (1 - notch, deepness - 1);
      else
        {
          if (sch >= deepness && (2 * deepness) - (tower_structure + 1)->score_value < notch + sch)
            {
              white_unspell (move);
              sch++;
              continue;
            }
          if (deepness <= 3)
            itog = -black_qsearching (1 - notch, 0);
          else
            itog = -black_slide (1 - notch, deepness - 2);
        }
      sch++;
      white_unspell (move);
      if (itog >= notch)
        {
          if ((tower_structure + 1)->captured == 0 && ((move & 060000) == 0))
            {
              int ist = history_tabular[position_fixed.square[(((move) >> 6) & 077)]][((move) & 077)];
              history_tabular[position_fixed.square[(((move) >> 6) & 077)]][((move) & 077)] = ist + (((0xff00 - ist) * deepness) >> 8);
              if (move != tower_dynamics->murderer_1)
                {
                  tower_dynamics->murderer_2 = tower_dynamics->murderer_1;
                  tower_dynamics->murderer_1 = move;
                }
            }
          hash_below (tower_dynamics->hash_64bit, move, deepness, itog);
          return (itog);
        }
      if (itog >= best_valuation)
        best_valuation = itog;
      if ((tower_structure + 1)->captured == 0 && ((move & 060000) == 0))
        {
          int ist = history_tabular[position_fixed.square[(((move) >> 6) & 077)]][((move) & 077)];
          if (tower_structure->score_value > notch - 50)
            history_tabular[position_fixed.square[(((move) >> 6) & 077)]][((move) & 077)] = ist - ((ist * deepness) >> 8);
        }
    }
  if (!sch && S->phase <= transpositional_2)
    return (0);
  hash_above (tower_dynamics->hash_64bit, deepness, best_valuation);
  return (best_valuation);
}

Here is my try at translating the ь code for this LowDepth function:

Code: Select all

* LOW(SCORE,depth)^HISTORY
  < [ BEHIND > 1125 ] (SCORE-1)! | HASH_READ&TRANS |
    [ AHEAD >= 70+10*depth ] (&EVAL)! | %MINIMUM(VALUE,SCORE-1)% |
    [ AHEAD ] + [ MY_NULL ] |! %QSEARCH(1-SCORE,0) |
    #TARGET + DELTA_PRUNING[ TRANS2^(50+8*depth) | pawn^(75+32*depth):#125* |
                           minor^(400+32*depth)+[depth<=3]:+300* | rook^(600+32*depth):+200* ]
            \ [ depth<=3 ] + [ BEHIND > 4*depth ] TRANS3 + REWARD*[BEHIND+4*depth+5]
   << [ REPETITION ] %MAXIMUM(%%,0)% + count! |
      [ count >= depth ] + [ $OTHER_MOVE$ ] + [ !CHECK_OR_CAPTURE ] + [ !XRAY ] + [ HAS_PIECE ]
      + [ 2*depth + MAXIMUM_REWARD + AHEAD < 40 + 2*count ] count! |
      [ CAPTURE += [ [ depth <= 5 ] + [ !TRIVIAL_SEE ] ] ]
      + [ !XRAY ] + [ !KING_MOVE ] + [ !TRANS ] + [ !SEE ] count! ||
      EVAL(150) !! %%LOW(1-SCORE,depth-1) %+
                   [ [ count >= depth ] + [ 2*depth + AHEAD# < count ] ] !count!
                    \ %LOW/QSEARCH(1-SCORE,depth-2) | count >>
   [ !count ] + [ $TRANS2$>= ] (0)! >

Here is the try to break this down

Code: Select all

* LOW(SCORE,depth)^HISTORY

This gives the name of the function, and its inputs. The HISTORY flag determines that history will be used in this function. It does not appear with QSEARCH.

Code: Select all

  < [ BEHIND > 1125 ] (SCORE-1)! | HASH_READ&TRANS |

The "<" starts the function body. The pipes (|) divide up the code into expressions. The first expression seems to be

Code: Select all

[ BEHIND > 1125 ] (SCORE-1)!

This is actually an if-then statement. The first token is in brackets, and the rest is the predicate. Here "BEHIND" is the difference between the SCORE (a beta value) and the current evaluation. If the current evaluation is more than 1125 behind the SCORE, then SCORE-1 is returned (the exclam I think). It becomes

Code: Select all

  itog = tower_structure->score_value + 1125;
  if (itog < notch)
    return (notch - 1);

The first pipe is part of the "magic" of the ь code. The first pipe of every search function seems to retire immediately into checking for repetitions, 50 move rule, and then to hashes.

Code: Select all

  if (tower_dynamics->non_permanent >= 100)
    return (0);
  for (i = 4; i <= tower_dynamics->non_permanent && i <= elevation_stack; i += 2)
    if (stack[elevation_stack - i] == tower_dynamics->hash_64bit)
      return (0);

This appears in many places, and checks first for the 50 move rule, and then for repetitions.

The next block of code appears in similar form in most search functions, and is the hashing, actuated from

Code: Select all

HASH_READ&TRANS

This bit transforms into

Code: Select all

  k = tower_dynamics->hash_64bit & hash_mask;
  for (i = 0; i < 4; i++)
    {
      hash = table_hash + (k + i);
      if ((hash->hash_64bit ^ (tower_dynamics->hash_64bit >> 32)) == 0)
        {
          if (hash->deepness_below >= deepness)
            {
              score = (hash->score_below);
              if (score >= notch)
                {
                  (tower_structure + 1)->move = hash->move;
                  return (score);
                }
            }
          if (hash->deepness_above >= deepness)
            {
              score = (hash->score_above);
              if (score < notch)
                return (score);
            }
          transpositional_deepness = hash->deepness_below;
          move = hash->move;
          if (move && transpositional_deepness > move_deepness)
            {
              move_deepness = transpositional_deepness;
              transpositional_movement = move;
            }
        }
    }

I think the TRANS means to save the transposition move, and READ is an indicator. I think READ always appears with HASH (as an "underscore" option?), though often there is a precedent to it, as in

Code: Select all

HASH[CUT]_READ(NULL,AGE)&TRANS

that appears with the CUT search function.

I think that the LowDepth function has in fact the most direct HASH_READ, as it is unmodified.

The next ь code line contains two expressions

Code: Select all

 [ AHEAD >= 70+10*depth ] (&EVAL)! | %MINIMUM(VALUE,SCORE-1)% |

AHEAD is the opposite of BEHIND. The lack of any divider after the bracketed term aspires for if-then, for

Code: Select all

  itog = tower_structure->score_value - (70 + 10 * deepness);
  if (itog >= notch)
    return (tower_structure->score_value);

The &EVAL tries to be current evaluation (why the ampersand), with the ! implying the return again.

The next expression is surrounded by %...% and this sets the "best value" register.

Code: Select all

  best_valuation = 
  (((tower_structure->score_value) <= (notch - 1)) ?
    (tower_structure->score_value) : (notch - 1));

I don't see the difference with VALUE opposed for EVAL, but the parsing might differ.

The next expression gives the nullmove condition

Code: Select all

    [ AHEAD ] + [ MY_NULL ] |! %QSEARCH(1-SCORE,0) |

The AHEAD is the difference of current evaluation and the scout value. The MY_NULL condition is that a token for my pieces is set, and is false if one minor or less is held. The |! is the "do null move" operator, and then QSEARCH is called with scout of 1-SCORE and depth of 0. I think that LowDepth is only called for depths less than 7 halves-ply, with null reduction directing to QSEARCH. The % preceding the QSEARCH is mysterious, but could be the function call operator?

Code: Select all

  if (tower_structure->score_value >= notch && ((tower_dynamics->flag) & 2))
    {
      nullize ();
      itog = -black_qsearching (1 - notch, 0);
      unnullize ();
      if (itog >= notch)
        {
          hash_below (tower_dynamics->hash_64bit, transpositional_movement, deepness, itog);
          return (itog);
        }
    }

The ь code expands here with the unnullize and hash_below appearing automatically. The derivation will come from the initial |! operate?

The next expression is a large operand that pertains for pruning and move selection

Code: Select all

    #TARGET + DELTA_PRUNING[ TRANS2^(50+8*depth) | pawn^(75+32*depth):#125* |
                           minor^(400+32*depth)+[depth<=3]:+300* | rook^(600+32*depth):+200* ]
            \ [ depth<=3 ] + [ BEHIND > 4*depth ] TRANS3 + REWARD*[BEHIND+4*depth+5]

The TARGET sets the target as the opponent's pieces. The initial # is not yet understood.

Code: Select all

  S->phase = transpositional;
  S->target = position_fixed.bitboard[enumerated_occupation_black];

The DELTA_PRUNING bracket contains four subexpressions. The object before the caret (^) is flipped if the condition after it is met compared to BEHIND. The first TRANS2^(50+8*depth) is

Code: Select all

  if (tower_structure->score_value + 50 + 8 * deepness < notch)
    {
      S->phase = transpositional_2;

The phase is set to a "slim" search (type 2) if the scout value is too much greater than the current valuation. The slim search concentrates more on captures. The second condition pawn^(75+32*depth):#125*
has many flags and is

Code: Select all

      if (notch >= tower_structure->score_value + 75 + 32 * deepness)
        {
          S->target ^= position_fixed.bitboard[enumerated_black_pawns];
          if (position_fixed.bitboard[enumerated_black_pawns] & tower_dynamics->white_attackeds)
            best_valuation += 125;

The target has pawns removed when scout value is at least 75+32*depth more than the evaluation. The 125* here adds 125 to the best valuation if the condition is met. The # before it demands that a pawn actually be attacked for this.

The third condition minor^(400+32*depth)+[depth<=3]:+300* turns into

Code: Select all

         if (deepness <= 3 && notch >= tower_structure->score_value + 400 + 32 * deepness)
            {
              S->target ^= (position_fixed.bitboard[enumerated_black_knight] | 
                            (position_fixed.bitboard[enumerated_black_bright] | 
                             position_fixed.bitboard[enumerated_black_faded]));
              best_valuation += 300;

The fourth condition rook^(600+32*depth):+200* turns into

Code: Select all

              if (notch >= tower_structure->score_value + 600 + 32 * deepness)
                {
                  S->target ^= position_fixed.bitboard[enumerated_black_rook];
                  best_valuation += 200;
                }

The pattern of before again appears with minors then rooks removed if the BEHIND is too great.

Finally there is the "else" condition of the DELTA_PRUNING

Code: Select all

            \ [ depth<=3 ] + [ BEHIND > 4*depth ] TRANS3 + REWARD*[BEHIND+4*depth+5]

The backslash is the else, and the first two brackets are the if of the if-then. When the depth is 3 halves-ply or less, and BEHIND is bigger than 4 times the depth, then the move generation is set to "type 3" with the REWARD value as BEHIND plus 4*depth plus 5. The storage for the REWARD is oddly in the "maska" part of the nextmove structure. The "type 3" search includes the REWARD search and is more robust compared to "type 2" search.

Code: Select all

  else if (deepness <= 3 && tower_structure->score_value + 4 * deepness < notch)
    {
      S->phase = transpositional_3;
      S->mask = (notch - tower_structure->score_value) + 4 * deepness + 5;
    }

The next group of ь code is the move iteration.

Code: Select all

   << [ REPETITION ] %MAXIMUM(%%,0)% + count! |
      [ count >= depth ] + [ $OTHER_MOVE$ ] + [ !CHECK_OR_CAPTURE ] + [ !XRAY ] + [ HAS_PIECE ]
      + [ 2*depth + MAXIMUM_REWARD + AHEAD < 40 + 2*count ] count! |
      [ CAPTURE += [ [ depth <= 5 ] + [ !TRIVIAL_SEE ] ] ]
      + [ !XRAY ] + [ !KING_MOVE ] + [ !TRANS ] + [ !SEE ] count! ||
      EVAL(150) !! %%LOW(1-SCORE,depth-1) %+
                   [ [ count >= depth ] + [ 2*depth + AHEAD# < count ] ] !count!
                    \ %LOW/QSEARCH(1-SCORE,depth-2) | count >>

The first expression checks if there is a repetition, with the %MAXIMUM(%%,0)% + count! as the then part of the if-then as the + is agglutinative. Here REPETITION implies that the opposing side can reverse, that is a clever looking ahead. When REPETITION is true, the best value from %...% is set to the maximum of zero and the current best value, and the count of moves considered is incremented. The ! iterates to the next move.

Code: Select all

  sch = 0;
  while ((move = white_next (S)))
    {
      kk = ((move) & 077);
      ot = (((move) >> 6) & 077);
      if ((notch > 0 &&
           tower_structure->non_permanent >= 2 &&
           ((((move) & 077) << 6) | (((move) >> 6) & 077)) == (tower_structure - 1)->move &&
               position_fixed.square[((move) & 077)] == 0))
        {
          best_valuation = (((0) >= (best_valuation)) ? (0) : (best_valuation));
          sch++;
          continue;
        }

The REPETITION condition is that the scout is positive and the move does not undo the previous move of this side.

The next expressions are complicated prunings

Code: Select all

      [ count >= depth ] + [ $OTHER_MOVE$ ] + [ !CHECK_OR_CAPTURE ] + [ !XRAY ] + [ HAS_PIECE ]
      + [ 2*depth + MAXIMUM_REWARD + AHEAD < 40 + 2*count ] count! |

Everything except the last "count!" is a joint condition from the + agglutination. When the count of moves is at least the depth, and the "phase" is OTHER_MOVE and the move is not a CHECK (direct) or CAPTURE (latter is redundant?) and the move is not an "XRAY" (uncovered check) and the side to move has a piece and the "MAXIMUM_REWARD" for this move is too small compared to the BEHIND margin (as -AHEAD), then the move is skipped and the count is added.

Code: Select all

      if (sch >= deepness && S->phase == movement_anemic && 
          position_fixed.bitboard[enumerated_occupation_white] ^
          (position_fixed.bitboard[enumerated_white_king] |
           position_fixed.bitboard[enumerated_white_pawns]) &&
          (move & 0xe000) == 0 &&
          bitboard_force[ot] & ~(tower_dynamics->white_encoded_xray))
        {
          if ((2 * deepness) +
             ((int) increment_maximal[position_fixed.square[(((move) >> 6) & 077)]][move & 07777]) +
              tower_structure->score_value < notch + 40 + 2 * sch)
            {
              sch++;
              continue;
            }
        }

The order for the C translation is different, as it checks for HAS_PIECE third (enumerated_occupation_white) then CHECK_OR_CAPTURE (move & 0xe000) then XRAY (white_encoded_xray). The MAXIMUM_REWARD here is an expectation for the maximal amount that a given move can gain in the "positional" sense (no material change).
The XRAY is an uncovered attack against the opponent king.

This is followed by another pruning condition

Code: Select all

      [ CAPTURE += [ [ depth <= 5 ] + [ !TRIVIAL_SEE ] ] ]
      + [ !XRAY ] + [ !KING_MOVE ] + [ !TRANS ] + [ !SEE ] count! ||

The += here is another agglutinator that is not understood yet. I think it is a type of "or" with the first object negated. The TRIVIAL_SEE condition looks to see if a move is a positive exchange (like PxQ).

Code: Select all

      if ((position_fixed.square[kk] == 0 || (deepness <= 5 && !(move & 0x300000))) &&
           bitboard_force[ot] & ~(tower_dynamics->white_encoded_xray) &&
           position_fixed.square[ot] != enumerated_white_king &&
           !(((move) & 070000) == 030000) &&
           move != transpositional_movement && !white_trader (move))
        {
          sch++;
          continue;
        }

The white_trader call is the SEE function. The "(move) & 0x70000" with 030000 can include castling and en passant, so it finds both KING_MOVE and CAPTURE when the capture is empty. The overall condition here means that if a move is not a capture, or is a capture at low depth, and is not an XRAY, and is not a KING_MOVE, and is not the TRANS move, then check if has a good SEE value, and if not, ignore the move. The double pipe (||) at the end actuates the make_move.

Finally the code reaches evaluation and iterative function calls

Code: Select all

      EVAL(150) !! %%LOW(1-SCORE,depth-1) %+
                   [ [ count >= depth ] + [ 2*depth + AHEAD# < count ] ] !count!
                    \ %LOW/QSEARCH(1-SCORE,depth-2) | count >>

The 150 with the EVAL is a lazy margin. The !! is a check for legality. In this function, it also checks for whether a "type 3" REWARD move is a check (which is redundant). The first LOW call, with 1-SCORE and depth-1 is done when the move gives check, maybe from the %% condition. The %+ then splits this.

Code: Select all

      move &= 0x7fff;
      white_spell (move);
      evaluation_scoring (notch - 150, notch + 150, move);
      if (((tower_structure + 1)->white_king_check) ||
          (S->phase == gaineds && ((tower_structure + 1)->black_king_check)))
        {
          white_unspell (move);
          continue;
        }
      if (((tower_structure + 1)->black_king_check))
        itog = -black_slide_check (1 - notch, deepness - 1);

Code: Select all

                   [ [ count >= depth ] + [ 2*depth + AHEAD# < count ] ] !count!

For nonchecking moves there is another pruning when the count of moves is as big as the depth and the AHEAD value is too small. The # on the AHEAD is mysterious. The !count! implies undo_move (unspell) before increasing the count and passing to the next move.

Code: Select all

      else
        {
          if (sch >= deepness && (2 * deepness) - (tower_structure + 1)->score_value < notch + sch)
            {
              white_unspell (move);
              sch++;
              continue;
            }

The final call to other function happens in the else condition (backslash)

Code: Select all

                    \ %LOW/QSEARCH(1-SCORE,depth-2) | count >>

Here LOW is called if the depth will be at least 1, else QSEARCH. The depth is diminished by 2 halves-ply. The count of moves is incremented.

Code: Select all

          if (deepness <= 3)
            itog = -black_qsearching (1 - notch, 0);
          else
            itog = -black_slide (1 - notch, deepness - 2);
        }
      sch++;
      white_unspell (move);

The other C code is hidden in the much. When the iterative call returns better than best_value or even the scout, everything is automatic.

Code: Select all

      if (itog >= notch)
        {
          if ((tower_structure + 1)->captured == 0 && ((move & 060000) == 0))
            {
              int ist = history_tabular[position_fixed.square[(((move) >> 6) & 077)]][((move) & 077)];
              history_tabular[position_fixed.square[(((move) >> 6) & 077)]][((move) & 077)] =
                              ist + (((0xff00 - ist) * deepness) >> 8);
              if (move != tower_dynamics->murderer_1)
                {
                  tower_dynamics->murderer_2 = tower_dynamics->murderer_1;
                  tower_dynamics->murderer_1 = move;
                }
            }
          hash_below (tower_dynamics->hash_64bit, move, deepness, itog);
          return (itog);
        }

When the iterative value exceeds scout, and the move does not capture or promote, the history is increased, the killers (murderers) recalled, and hash_below invoked before returning the iterative value. This appears in most functions from the HISTORY switch.

When the iterative value exceeds best_value it is set, plus then the history_bad is applied when the evaluation and the scout are close (50 points). The same appears again in other search functions.

Code: Select all

     if (itog >= best_valuation)
        best_valuation = itog;
      if ((tower_structure + 1)->captured == 0 && ((move & 060000) == 0))
        {
          int ist = history_tabular[position_fixed.square[(((move) >> 6) & 077)]][((move) & 077)];
          if (tower_structure->score_value > notch - 50)
            history_tabular[position_fixed.square[(((move) >> 6) & 077)]][((move) & 077)] =
                            ist - ((ist * deepness) >> 8);
        }
    }

The final ь code is called after move iteration has failed.

Code: Select all

  [ !count ] + [ $TRANS2$>= ] (0)! >

The two brackets are the if, so when the count is zero and the "type 1" search was used (minimum pruning) the function returns zero, for stalemate?

Code: Select all

  if (!sch && S->phase <= transpositional_2)
    return (0);
  hash_above (tower_dynamics->hash_64bit, deepness, best_valuation);
  return (best_valuation);

Also the hash_above is stored in the automatic manner, from the concluding > in the ь code.

This ends the LowDepth description. Maybe tomorrow I will try another function.

Posted: **Fri Feb 04, 2011 5:12 am**

I talked with ZW about this last March when I met him, and we both had the thought that this was just some sort of macro-based condensation of the search functions, and was just as likely to be written ex post facto as being of any real merit. Maybe if a "ь parser" were to appear I would think differently. "Boris Korol" just means "Boris the King" -- or maybe "Boris is King": http://www.boris-is-king.com/homepage.htm

OpenChess

ь code

ь code

Re: ь code

Re: ь code

Re: ь code

Re: ь code

Re: ь code