The Inferno thread

hgm · Post by **hgm** » Wed Mar 15, 2017 4:12 pm

Promotions

Some thoughts

Now that the infra-structure is largely decided, we can start to think about search strategies. One aspect of Shogi that is different from orthodox Chess is that all (or at least most) pieces can promote. In Chess promotion is rare: only Pawns can do it, on the last rank, and they are very immobile. So they can reach the promotion square only with grave difficulty. And on promotion they increase hugely in value, enough to decide the game.

In Shogi most promotions are much more modest. A Pawn promotes to a Gold General, worth less than a Chess Knight. Rook and Bishop gain the 4 moves of a King that they did not have yet, which on an 8x8 board would up their value by about 2 Pawns. So in general the promotion gain is not spectacularly large. But it is still equivalent to trading a Pawn for a Gold, or a Bishop for a Rook. But in a game like Tenjiku, with pieces that capture several Queen-class pieces at once, such a material gain is almost insignificant background noise. At least in the beginning. When all the ultra-strong pieces have disappeared from the board, scores swing less dramatically from move to move, and a gain of the order of the Rook-Bishop difference might become significant.

In later game stages promotion is not very difficult, however. The promotion zone consists of the 5 furthest ranks, not just the last one. And imagine how easy it is to move a Queen to one of those squares. At some point it becomes a near certainty a Queen will promote, and it is only a matter of when. So the value of a Queen will approach that of a promoted Queen with progress of the game phase, and that also holds for any other piece with forward sliding moves. It becomes just a temporary positional disadvantage that you have not promoted it yet, similar to having a piece on a unfavorable square.

So promotions are probably not worth to be searched in Quiescence Search, anymore than Pawn advances on earlier ranks would be in Chess. They would gain some score, but not really more than can be expected from having the move. Which is just as well, because generating all non-capture promotions could be quite expensive.

Captures can of course also be combined with a promotion. In cases where the promotion produces an upward-compatible piece, there is no reason to refrain from promoting. It would be like opting for a Rook when you can have a Queen. (Stalemate is not a draw in Tenjiku Shogi!) So in many cases we should automatically generate only the promoting move, and ignore the possibility to defer promotion.

There are a few exceptions to the rule that promotions are insignificant, though. Water Buffalos promote to Fire Demons, a huge increase in value, as the latter will easily take down 3 or 4 Water-Buffalo equivalents. (And the Water Buffalo is a 'nearly-Queen'!) This makes that you can also not take it for granted that it will promote sooner or later, as all the opponent's efforts will be directed against preventing this promotion. (With other pieces it is often that if promotion of one can be prevented, another one will slip through, and reap a similar gain.) So you should detect the rare possibility to promote a Water Buffalo as early as possible, and seize the opportunity immediately. So 'decisive promotions' should be considered in QS.

Fortunately promotion moves of a few selected pieces can be generated selectively without too much effort, by using the view distances. So you don't have to generate all non-captures and test them for ending in the zone. Each slider/stepper has a mask byte tabulated for it, which indicates the directions it moves in (as bits set to 1), and you can mask out the 3 forward directions, as only moves in this direction could conceivably enter the promotion zone. Then it becomes just a matter of looking up the view distance in those directions, and test whether the square just before the nearest obstacle is inside the promotion zone. (If the nearest obstacle is an enemy, you would already have considered going there to capture it, while if it is an own piece or edge, you could not go there anyway.) If it is, you have a non-capture promotion to that square, and you can start stepping your way back towards the piece to test how long you stay inside the zone, and also generate promotion moves to there. Area moves occur only on pieces that do not promote, and pieces with Knight jumps do not promote decisively. Two pieces that promote to Lion and Queen might qualify as 'decisive', and they have jumps to the 2nd square. But we also can easily test the one or two forward ones of those for reaching the zone pseudo-legally.

Unfortunately no attack information is available on the empty promotion squares. If you would be captured immediately there, it doesn't have any effect whether you promote or not, and the move becomes indistinguishable from any other non-capture (which you also would not want to search in QS). MakeMove() collects attack info on the to-square, however. So it seems useful to build in an 'emergency abort' for when you went in blindly with a promotion that turns out to be a suicide after you open your eyes. The heuristic for pruning captures in QS will pretty much be to only try those that capture a better or equal piece (which would never be the case when moving to an empty square), capture an unprotected piece, or have multiple attackers. The latter two conditions follow quite easily from the attack-map elements collected by MakeMove: if the opponent had any attacks on it, and you now have no attacks left, (after the promotion move used up one), your freshly promoted piece hangs and the promotion was in vain. Even if you do have attacks left that support the promoted piece, it seems illogical to start with the piece that will make the decisive promotion; you would want to only move that there when the opponent has used up all its protectors. (Compare a last-rank Knight attacked by P and R, and protected by B: after PxN=Q, BxQ, RxB you are left with a Rook, while after RxN, BxN PxB=Q you are left with a Queen. Of course the opponent does not have to play BxN, but then you would keep the 7th-rank Pawn, which might promote later) So if after MakeMove() of a decisive non-capture promotion in QS it turns out the promotion square was protected, we should probably not search, but immediately UnMake() the move.

[d]3nn3/4P3/8/b7/8/3R4/8/8 w
RxN or PxN=Q?

hgm · Post by **hgm** » Sat Mar 18, 2017 6:44 pm

Non-capture Generation

The engine will generate captures by running through the victims in the opponent's piece list in MVV order, to test in the attack map if they can be captured, and generating the captures the map indicates if it can. (Apart from the Fire-Demon burns, which will be generated from scratch.) Non-captures, OTOH, are generated by running through the side-to-move's piece list.

For a game as large as Tejiku Shogi this can be tedious. The piece lists are 150 entries long, because they also contain promoted pieces (to maintain MVV order when pieces promote). So more than half of the pieces are marked as absent, and will have to be skipped. When a piece is present, we have to generate all its moves to empty square. The large majority of the pieces slides one or more squares along orthogonals or diagonals. The jumping sliders are not in any way special here, as they can only jump when capturing.

In priciple there are 8 directions to slide in, and a table ranges[piece][directionNumber] tells how far you slide in each of those. (0, 1, 2 or 15 squares). There are many pieces that do not move in certain direction (i.e. range = 0), and to avoid wasting time on those, there is a byte quantity dirMask[piece] that tells which directions have a non-zero move, so that you only have to spend time on those by extracting the set bits from the mask. That saves some time, but there are also many pieces that have moves in all 8 directions. And initially the 60 pieces pieces are densely packed in 4 ranks behind a rank of 16 Pawns. So many pieces that in principle can move in all directions actually cannot move at all, because they are completely smothered by surrouding own pieces. Of course the dirMask cannot know this, and you would spend a lot of time in testing the adjacent squares on the board only to conclude there is an own piece there blocking the move.

But this can be largely remedied at fairly low cost! For the purpose of fast detection of Fire-Demon burns, we already maintain a set of 'bitstrips', which are 'white' and 'black' bitboards of a 3x16 strip of the 16x16 board along a file. A single such bitstrip contains information on pieces of a given color in a 3x3 area around a given square. This is exactly the information we need to decide which of the sliding directions will be blocked on the first square already! So we can do

Code: Select all

int fromSqr = location&#91;piece&#93;;
int rank = SQR2RANK&#40;sqr&#41;;
int file = SQR2FILE&#40;sqr&#41;;
int neighborhood = &#40;burns&#91;file&#93; | 0700000000000000007LL&#41; >> 3*rank & 0757; // extract 3x3 area from bitstrip
int mask = dirMask&#91;piece&#93; & env&#91;neighborhood&#93;;

where the env[] table would translate the pattern of 3 neighboring bitstrip ranks to a direction mask. For most pieces in the initial position this would leave a mask with no bits set. (And it will take very many moves to free those pieces, so this situation will last for a long time.) Meaning you are done with them immediately.

Hmm, this does take a fair amount of calculation, to save a number of times (possibly 8 times):

Code: Select all

int d = lowBit&#91;mask&#93;;
int vec = step&#91;d&#93;;
int toSqr = fromSqr + vec;
int victim = board&#91;toSqr&#93;;
mask -= 1 << d;
if&#40;victim != 0&#41; continue; // to-square occupied; not a non-capture
... // step further in this direction if range allows it, generating moves

Which also is not that much. So I hope that it pays off.

Perhaps a smarter way to generate non-captures is by scanning the board, rather than running through the piece list. Normally (in orthodox Chess) this is the stupid way. But when the piece list is half empty because of all the slot reservations for promoted pieces, and your own half of the board is 62% filled (and initially the 5 rank of your own camp 95% filled), this could reverse.

The advantage of scanning the board is that you would not have to calculate rank and file of a square all the the time. Your outer loop could run through the file numbers, and you could use the bitstrip centered on the current file to scan over ranks along that file (possibly even using bit extraction, although that is only helpful for sparse populations). In fact it seems more important to test whether the adjacent squares are not all filled, rather than whether you have a piece on the square in its center. So you could do:

Code: Select all

int f;
for&#40;f=0; f<FILES; f++) &#123;
  int64 strip = burns&#91;file&#93;&#91;stm&#93;; // occupied squares in 3x16 strip
  int64 holes = ~strip & 077777777777777770LL; // invert, and make sure off-board is not considered a hole
  int r = 0;
  do &#123;
    if&#40;holes & 0757 &&    // there are adjacent empty squares
       !&#40;holes & 020&#41;) &#123;  // and a piece in center
      int fromSqr = f + r;
      int piece = board&#91;fromSqr&#93;;
      int mask = dirMask&#91;piece&#93; & env&#91;holes & 0757&#93;;
      while&#40;mask&#41; &#123; // all directions in which piece moves and is not immediately blocked
        int d = lowBit&#91;mask&#93;;
        int vec = step&#91;d&#93;;
        int toSqr = fromSqr + vec;
        ...
        mask -= 1 << d;
      &#125;
    &#125;
    r += WIDTH; // next rank
    holes >>= 3;
  &#125; while&#40;&#40;holes & 022222222222222220LL&#41; != 022222222222222220LL&#41;;

A problem is that for black you would want to scan in the opposite direction, starting with the high bits of 'holes'. Then you first scan through the dense population in your own camp, quickly dispensing with all pieces that are smothered, and occasionally examine one direction of a piece that borders a hole and can actually move there. And when your 'focus of attention' finally hits the enemy camp, the whole remaining file will be considered a hole, and you stop immediately without having to finish the entire file. Even in the no-man's land between the camps (a 16x6 area) there is a good chance there is nothing in the file.

[Edit]
To make this work for black as well as white, the burn[] information could be stored per rank, rather than per file. (Which was an arbitrary choice.) Then the outer loop runs over ranks, in particular the ranks in the camps of both players. In your own camp the pieces will be densely backed for a large part (probably the decisive part) of the game, so the above code would rapidly scan through each rank because it skips all smothered pieces after a simple test. And in the enemy camp there would hardly be any of your own pieces, so the rank scan would terminate immediately.

The question is how to treat the no-man's land between the camps, which for a large part of the game is mostly empty. Note that scanning a sparsely populated board in search of your own pieces needs not be more expensive than scanning a crowded board, because of the availability of view distances. You can use these to directly hop from piece to piece, skipping all empty squares. The inefficiency comes from the fact that this also visits opponent pieces. In a region where pieces are mixed this still gives you a 50% hit rate. Only in the enemy camp it would be a very poor method.

hgm · Post by **hgm** » Sun Mar 19, 2017 12:53 am

With the burns[rank][color] table for detecting the Demon burns (i.e. squares with neighbors of a given color) organized per rank, so that they are 16x3 strips of the board rather than 3x16 strips, white and black can use the same code to scan the board for their own pieces:

Code: Select all

#define ONBOARD (&#40;1LL << 3*&#40;FILES+1&#41;) - 8&#41; /* mask for on-board part of strip */
#define ONRANK &#40;ONBOARD*2/7&#41; /* mask for central rank only */

int r;
for&#40;r=0;r<RANKS; r++) &#123;
  int64 strip = burns&#91;r&#93;&#91;stm&#93;; // occupied squares in 16x3 strip &#40;by stm piece&#41;
  int64 holes = ~strip & ONBOARD; // invert, and make sure off-board is not considered a hole
  int f = 0;
  while&#40;~holes & ONRANK&#41; &#123; // while own piece present on the rank
    int b;
    while&#40;holes & 020&#41; &#123; // first in line is not our piece
      static int oneThird&#91;&#93; = &#123; 1, 0, 0, 2, 0, 0, 3, 0, 0, 4 &#125;;
      int b = lowBit&#91;~holes >> 7 & 0111&#93;; // 0, 3, 6 or 9
      holes >>= b + 3; // skip first in line plus up to 3 other empty/enemy squares
      f += oneThird&#91;b&#93;;
    &#125; // repeat this until our piece comes up
    if&#40;holes & 0757&#41; &#123;    // there are adjacent empty squares
      int fromSqr = f + WIDTH*r;
      int piece = board&#91;fromSqr&#93;;
      int mask = dirMask&#91;piece&#93; & env&#91;holes & 0757&#93;;
      while&#40;mask&#41; &#123; // all directions in which piece moves and is not immediately blocked
        int d = lowBit&#91;mask&#93;;
        int vec = step&#91;d&#93;;
        int toSqr = fromSqr + vec;
        ...
        mask -= 1 << d;
      &#125;
    &#125;
    f++; // next file
    holes >>= 3;
  &#125;
&#125;

This code is still efficient for empty / enemy ranks (without any own pieces), because the outer 'while' will skip these immediately, as well as for very crowded ranks (where nearly every square is an own piece, but smothered pieces are rapidly skipped).

But it is also made efficient for ranks with just a few pieces (as are to be expected in the no-man's land between the camps), by adding an inner 'while' loop, which detects the situation that the next file on the rank will not contain another piece. In that case the next piece on the rank is found by LSB extraction, and a contiguous group of empty squares is skipped in one action. (Using the existing lowBit[] table instead of relying on a BSF instruction limits this to skipping 4 empty squares per iteration of a loop. With BSF the inner 'while' could just be an 'if', and we would always arrive to the next piece in a single shift. As ranks measure 16 squares in Tenjiku, you would find a single piece on a rank on the average in 2 steps, however, and immediately terminate the rank scan after treating that piece, so the overhead for not using BSF is only small.)

Note this does not find moves of pieces that can jump (initially 2 Knights, 1 Lion, 1 Lion Hawk, 2 Falcons, 3 Eagles, 1 Phoenix and 1 Kirin, so 11 out of 78), and thus could escape the smothering. It seems best to generate the jumping moves of these pieces by running through the subset of the piece list formed by them.

hgm · Post by **hgm** » Sun Mar 19, 2017 9:53 am

Magic board scan

Although the method described in the previous posting is probably fast enough, I always like to push things to their limit. It occurred to me one could collect the bits corresponding to the central file of the bitstrip (i.e. after masking with 022222222222222220LL) with the aid of a 'magic multiplier', to form a contiguous set that can be used as table index. Note that it is not possible to assign the ranks in the bitstrip as contiguous bits, because the main (and most time-critical) application of this data structure is to extract burn victims in a 3x3 section of the strip, so such sections have to be represented by contiguous bits.

Multiplication of the rank population by (1 | 1<<8 | 1<<16) would interleave 3 copies of the data set shifted by about 3 files, to make the 'friendly occupancy' for the next nine squares on the rank contiguous. These could then be used to index a table to extract the nearest square. magic multiplication did not preserve the order of the bits, so we cannot extract the bits in BSF order. But the lowBit[] table could actually be sorted in the required order (no loger living up to its name), as in all other bit-extraction scans so far the order in which the bits are treated was irrelevant.

So we would get:

Code: Select all

#define MAGIC &#40;1 | 1<<8 | 1<<16&#41;

int file = 0;
while&#40;~holes & ONRANK&#41; &#123; // pieces left on rank
  while&#40;holes & 020&#41; &#123; // next square not ours
    static int skip&#91;&#93; = &#123; 1, 4, 7, 2, 5, 8, 3, 6, 9, 10 &#125;; // bit number to distance
    int collect = &#40;unsigned int&#41; (~holes & ONRANK&#41; * MAGIC >> 32-9; // keep highest 9 bits
    int b = lowBit&#91;collect&#93;; // extract in priority order 0, 3, 6, 1, 4, 7, 2, 5, 8
    holes >>= 3*skip&#91;b&#93;;
    file += skip&#91;b&#93;;
  &#125;
  ...

This examines the 9 squares on the rank following the one we just concluded was not our piece, and can thus skip up to 10 squares in a single try. Only if the first piece on the rank is on the 12th-16th file a second iteration would be needed. Entirely empty ranks are immediately discarded by the while(~holes & ONRANK). Ranks that are crammed with pieces will almost always skip the while(holes & 020), because the next square in line will not be a 'hole' but a piece of ours. So this code is basically only executed on ranks in the no-man's land, on which it can take strides towards the next friendly piece of upto 10 squares in a single iteration.

This looks like a very efficient way to loop through your own pieces. Much more efficient than looping through the piece list. (Which will contain many holes for pieces captured in the search, and slots for promoted pieces waiting to be activated at the expense of the base piece.)

hgm · Post by **hgm** » Tue Mar 21, 2017 11:21 pm

Attack-map Updating (again)

After some debugging I am happy to announce that the incremental update of all data structures now actually works in so far placing pieces on empty, uninformed squares is concerned: The FEN reader uses PlacePiece() to add the pieces one by one, and incrementally update everything after each piece. After each piece it then compares them with data created from scratch, from the total position as it is at that point. (I have written routines to generate the maps from scratch for that purpose.) This now works.

I experienced some problems I had not foreseen. E.g. my distance[sqr1-sqr2] table worked up to distance 15. But the code sometimes used it to get the distance between an edge cell and a board square, when you place a piece next to the edge on a empty board, and happen to do a ray scan in the direction of the other edge. So I had to extend it to vectors of length 16. This was a bit awkward, because I am working with a 32x16 board format. So the distance table that runs up to 15 must be 32x31, with one unused 'file'. But a table that runs up to 16 needs 'ranks' of length 33, which do not fit. Fortunately neighboring ranks overlap their end squares, which both need to contain distance = 16. So luck is with the stupid...

The code I presented previously for PlacePiece() was not very smart. For blocking slider attacks you don't need a loop over colors: you look around on the board (in 8 directions) to see what comes in your direction (so you can intercept it), and while you do that you automatically get to know the color of the piece making the attack. Only attacks that you want to deduce from the attack map need to access both the white and black attacks in it.This is used for attacks with jumping sliders, to avoid the need to locate them through a board scan. (Which would be inefficient even with a view-distance table, as they can be behind many other pieces.) So I get them through the attacks they make on the neighboring pieces.

Ayway, the tested code is now this:

Code: Select all

void
PlacePiece &#40;int sqr, int piece&#41;
&#123; // puts piece on an empty square on which no information was available
  static int64 jumpType&#91;&#93; = &#123; A_ORTHO, A_DIAG &#125;; // masks for orthogonal and diagonal jumping-slider attacks
  int d;
  int64 att&#91;2&#93;;                                  // new attack-table entries &#40;white & black&#41; for this square
  BlockView&#40;sqr&#41;;                                // update view-distances &#40;creating entry for this square&#41;
  // leaper attacks are always up to date
  att&#91;0&#93; = attacks&#91;sqr&#93;       & A_LEAPS;         // inherit them
  att&#91;1&#93; = attacks&#91;sqr+ASIZE&#93; & A_LEAPS;         // for attackers of both colors
  // blocking of slider moves passing over the square
  for&#40;d=0; d<8; d++) &#123; // look in all 8 directions for attacks to block
    int64 slide = A_SLIDE << d;                  // bit indicating normal slide in this direction
    int vec = step&#91;d&#93;;
    int dnDist = viewDist&#91;sqr&#93;.d&#91;d&#93;;
    int s = sqr + dnDist*vec;                    // down-stream obstacle
    int upDist = viewDist&#91;sqr&#93;.d&#91;d^4&#93;;
    int t = sqr - upDist*vec;                    // upstream obstacle
    if&#40;d<4&#41; &#123; // only four direction pairs
      int side;
      int64 antiSlide = slide << 4;              // bit indicating normal slide in opposite direction
      for&#40;side=0; side<2; side++) &#123;              // for attacks of both colors
        int color = side*ASIZE;
        int64 dnAttacks = attacks&#91;s+color&#93;;      // attacks on down-stream obstruction
        int64 upAttacks = attacks&#91;t+color&#93;;      // attacks on up-stream obstruction
        int64 dnSlide = dnAttacks & slide;       // slider attack coming from our direction on down-stream target
        int64 upSlide = upAttacks & antiSlide;   // and in opposite direction from other side
        attacks&#91;s+color&#93; = dnAttacks - dnSlide;  // both these are now blocked, remove them
        attacks&#91;t+color&#93; = upAttacks - upSlide;
        att&#91;side&#93; |= dnSlide | upSlide;          // and both now attack us instead
        upAttacks &= jumpType&#91;d & 1&#93;;            // jump-slide attacks in current direction set &#40;orth or diag&#41;
        att&#91;side&#93; |= upAttacks & dnAttacks;      // those that attack targets on both sides must also attack us
      &#125;
    &#125; // slides hitting obstacles beyond us are now done, except direct attacks by jumping sliders
    // next check for Tetrarch attacks from behind the up-stream neighbor
    if&#40;nrTetrarchs&#41; &#123;                              // Tetrarchs on the board! &#40;rare&#41;
      int lurker = board&#91;t - vec&#93;;                 // check out the piece just behind up-stream
      if&#40;lurker > 1 &&                             // there is a piece there
         jumpMask&#91;lurker&#93; == JC_TETR&#41; &#123;            // and it is a Tetrarch jumping over the up-stream piece 
        int side = lurker & 1;                     // player owning the Tetrarch
        if&#40;d & 1 ||                                // diagonal; Tetrarchs have unlimited range
           d & 2 && upDist < 3&#41; &#123;                  // sideway; Tetrarchs have range 3 here
          int b = type&#91;lurker&#93; << 4 & 0xF0;        // kludge&#58; bit representing this Tetrarch hidden in type&#91;&#93;
          attacks&#91;s+side*ASIZE&#93; &= ~b;             // the attack on down-stream gets blocked &#40;in case it reached it&#41;
          att&#91;side&#93; |= b;                          // as it now hits us
        &#125;
      &#125;
    &#125;
    // next do sliding attacks that did not hit down-stream because of range limitation
    if&#40;(&#40;att&#91;0&#93; | att&#91;1&#93;) & slide&#41; == 0&#41; &#123;      // sliding attack in this direction not yet detected
      int attacker = board&#91;t&#93;;                  // detect it the hard way&#58; examine piece up-stream of us
      int range = ranges&#91;attacker&#93;&#91;d&#93;;          // to see how far it moves in our direction (= 0 for edge guard!)
      if&#40;range&#41; &#123;                               // can move towards us
        int side = attacker & 1;                // player owning attacker
        if&#40;range > X&#41; &#123;                         // attacker is jumping slider &#40;medium rare&#41;
          att&#91;side&#93; |= gen2bit&#91;attacker&#93; << range - Y;  // record attack by jumping slider &#40;GG orthogonal have range = Y+3&#41;
        &#125; else if&#40;range >= upDist&#41; &#123;            // move reaches us
          att&#91;side&#93; += slide;                   // add normal slide to our attack map &#40;note it did not reach down-stream!)
        &#125; else                                  // not in range &#40;so certainly not an adjacent Tetrarch!)
        if&#40;jumpMask&#91;attacker&#93; == JC_TETR&#41; &#123;     // the up-stream piece is a Tetrarch &#40;rare&#41;
          if&#40;d & 1 || d & 2 && upDist < 4&#41; &#123;    // and it reachs us through its unlimited diagonal slide, or 3-step sideway
            int b = type&#91;attacker&#93; << 4 & 0xF0; // kludge&#58; bit indicating this Tetrarch in attack map is hidden in type&#91;&#93;
            att&#91;side&#93; |= b;                     // record attack on current piece
            attacks&#91;s+side*ASIZE&#93; &= ~b;        // and remove it from down-stream &#40;if there&#41;
          &#125;
        &#125;
      &#125;
    &#125;
  &#125; // next direction

  attacks&#91;sqr&#93; = att&#91;0&#93;;       // store newly calculated attack-map elements for this square
  attacks&#91;sqr+ASIZE&#93; = att&#91;1&#93;;
  if&#40;piece < CRAWLERS && gen2level&#91;piece&#93;) &#123;    // piece is a jumping slider &#40;somewhat expensive, but rare&#41;
    int l;
    for&#40;l=gen2level&#91;piece&#93;; l>0; l--)
      BlockJumperView&#40;viewDist + l*DSIZE, sqr&#41;; // update affected high-level views
    LevelChange&#40;sqr, 0, gen2level&#91;piece&#93;, -1&#41;;  // block attacks upto level of blocker
  &#125;
  AddMoves&#40;sqr, piece, 1&#41;;
&#125;

hgm · Post by **hgm** » Thu Mar 23, 2017 11:09 pm

To test the MakeMove() logic, I am now running a tree walk with a special 'perft' routine. For now this only generates and makes non-captures (and the Fire Demons do not move at all). After every MakeMove() and UnMake() it compares view-distance and attack maps calculated from scratch with the incrementally updated versions. This is of course excessively slow. But it is a good test for whether the incremental stuff does its work properly.

I can also get some vague impression of what performance to expect. For that I remove the checking of the view distance and attack map, and let it run:

Code: Select all

 l  n  f  i  c  s  g  e  k  g  s  c  i  f  n  l    16
 a  .  c! c! .  t  x  q  l! o  t  .  c! c! .  a    15
 s' v' b  h  d  w! d! e! h! d! w! d  h  b  v' s'   14
 m  v  r  f! s! b! r! v! g! r! b! s! f! r  v  m    13
 p  p  p  p  p  p  p  p  p  p  p  p  p  p  p  p    12
 .  .  .  .  d' .  .  .  .  .  .  d' .  .  .  .    11
 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .    10
 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .     9
 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .     8
 .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .     7
 .  .  .  .  D' .  .  .  .  .  .  D' .  .  .  .     6
 P  P  P  P  P  P  P  P  P  P  P  P  P  P  P  P     5
 M  V  R  F! S! B! R! G! V! R! B! S! F! R  V  M     4
 S' V' B  H  D  W! D! H! E! D! W! D  H  B  V' S'    3
 A  .  C! C! .  T  O  L! Q  X  T  .  C! C! .  A     2
 L  N  F  I  C  S  G  K  E  G  S  C  I  F  N  L     1

 a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p 

perft&#40;1&#41; =     47   2209 &#40;0.000 sec&#41;
perft&#40;2&#41; =   2209 109729 &#40;0.000 sec&#41;
perft&#40;3&#41; = 109729 5448501 &#40;0.270 sec&#41;
perft&#40;4&#41; = 5448501 291943287 &#40;13.690 sec&#41;

This 'perft' does not care about legality. (In fact there is no such thing in Tenjiku Shogi; you win by capturing the King. So moving into check is not illegal, just a poor move.) Perft(1) makes all 47 pseudo-legal non-captures from the initial position, and then runs a move generation in the thus reached leaves, bulk counting the generated moves (i.e. adding the size of the move stack to the total after generation), and doing nothing else with them. So I guess it is really a perft(2). In any case, the first number is the number of move generations, the second number the number of generated moves.

So it does about 400,000 move generations (non-captures only) per second. (No quick filtering of smothered pieces is done yet.) With fewer pieces this goes up, even when the total number of moves goes up as well. (I tried a position with 2x8 pieces, which had 148 moves because most of the pieces were highly mobile sliders, and it did about 800,000 generations/sec there.) This number will go down a bit when I will also generate captures. OTOH, in a real engine most nodes are QS, which will only have to generate captures. Which should be faster than the non-captures. Because there are fewer, and because the staged move generation (victim by victim) makes that you often don't have to generate all of them. In fact when you stand pat in QS, you generate nothing at all. So I hope that 1Mnps will be possible.

Of course the perft numbers are meaningless, with only non-captures, and ignoring promotions and Demon moves. But I would not know what the correct numbers should be, even if I would have those...

hgm · Post by **hgm** » Tue Mar 28, 2017 1:51 pm

After some debugging and a self-testing perft with all moves (captures, non-captures, Demon burns, promotions) now seems to work. At least up to perft(5), which took about 6 hours from my favorite test position (which now also includes a Tetrarch). That is, no deviations between the incrementally updated data structures and those generated from scratch are detected.

That means it is time to move on to a new subject. (I will probably discuss a bit on promotions later.)

Testing for Check

In principle the attack map should make in-check detection trivial: just look up if there are any attacks to the square your King is on in the map, and if there are, you are in check. There are several complications, though:
1) Attacks by area moves of Vice Generals indicated in the map are only potential attacks, and have to be vetted for not being blocked.
2) The King could be under threat to be burned by a Fire Demon that lands on a square next to it, either sliding there or by an area move. The attack map will not indicate such 'burn checks'.
3) For the Demon area moves the attack map does not even record the potential direct attacks (i.e. marks quares that are in range of the Demon's area move).

So even if no attacks on the King are found in the attack map, we have to test for these other cases before we can conclude we are not in check. (And unfortunately being not in check is the common case.) The Demon burns have the additional complication that a Demon landing next to an enemy Demon will evaporate without burning any bystanders. So it is not enough to test if a Demon can land next to the King; we also have to check no other Demon evaporates it there.

Area moves

Area moves (up to 3 King steps) have time-reversal symmetry. I.e. when a valid area move goes from A to B, a valid move will also go from B to A. So to know if a VG can capture a King that is in the range of its area move (as flagged in the attack map), we can generate area moves of the VG to see if the King square is in the set of attacked squares, but we can also generate area moves from the King square, to see if they hit the VG. The advantage is that you can test all VGs against a single 'area map', instead of generating a map for each VG. It is not completely sure this is a smart thing to do, though. You only start with 1 VG (although you can get two more by promotiong your 'flying Bishops'), and you might need the area map for this VG (or any other VG) later on anyway (e.g. for vetting other attacks it makes, or generating its non-captures).

An area map around the King can also be used to test if Demons have a direct area-move attack on the King, however. It is important to know whether a Demon can actually capture the King by landing on it, rather than burning it by landing next to it, because such burns can be thwarted by an adjacent Demon that sides with the King, while the direct capture can not. And you start with Two Fire Demons each, so it would be nice if both of these (as well as any VG) could all be checked against the same area map for the King. OTOH, it is not often that the King will be in area-move range, so the chance that you do need to use the map multiple times are only slim. But that also means the chances you don't have to generate it at all are pretty good, so worrying whether you could have saved you the effort to generate it might be a moot point.

Anyway, for now I generate an area map around the King, through the routine I already had for that, which would flag all squares reachable by 3 King steps in the 7x7 King neighborhood. The more interesting issue is that of the Demon burns. Because a Demon burns all squares adjacent to its to-square, you can be burned by a 3-step area move when you could be captured by a 4-step area move. If we would retrogradely generate these 4-steps move (i.e. starting from King), their first step would visit the burn square. So it would be OK if this first retrograde step passes over a piece allied to the King, as the Demon would capture it to burn the King. The path from the burn site to the Demon must be clear, however, as usual. And the burn site, whether it is empty or a friendly piece, must not be adjacent to a friendly Demon for the enemy Demon to burn us from there.

I don't have a routine to generate 4-step area maps, and such maps, covering a 9x9 area, would not fit in a 64-bit integer. Plus that it would be rather expensive. So what I did is slightly generalize the 3-step area-map generator, equipping it with an extra argument, which indicates adjacent pieces of what color should be considered 'transparent' in the first step. And it excludes first steps over squares bordering a Demon of that color (the 'if(tunnel)' part is new):

Code: Select all

int64
GenAreaMap &#40;int sqr, int side&#41;
&#123; // return map of squares &#40;pseudo-&#41;reachable by area move considering board occupation
  int h, d;
  int tunnel = &#40;side >= 0&#41;; // called for retrograde generation of Demon area-move burns
  int offs = 0;
  int   reachable2 = 0;     // set of squares reachable by 2nd step
  int64 reachable3 = 0;     // set of squares reachable by 3nd step
  int64 corners = CORNERS3; // 3rd-ring corners
  // do all first steps, starting with first step, recording reachability of 2nd ring
  for&#40;d=0; d<8; d++) &#123;
    int vec = step&#91;d&#93;;
    int s = sqr + vec;                       // try all first-ring squares
    int victim = board&#91;s&#93;;
    int transp = &#40;victim < 1&#41;;               // empty squares do not block area moves
    if&#40;tunnel&#41; &#123;                             // must also pass through valid burn squares
      transp |= victim > 1 & &#40;victim & 1&#41; == side;   // 1st-ring pieces of given side transparent
      if&#40;transp&#41; &#123;                                   // this is a potential burn site
        int r = SQR2RANK&#40;s&#41;;
        int f = SQR2FILE&#40;s&#41;;
        if&#40;demons&#91;r&#93;&#91;side&#93; & 0757 << 3*f&#41; continue;  // but not if adjacent to a Demon
      &#125;
    &#125;
    reachable2 |= rMask2&#91;d&#93;*transp;          // when empty, schedule continuation to 2nd rank
  &#125;
  corners |= reachable2 & CORNERS2;          // add 2nd-ring corners reachable in 2 steps
  // do second step now we know which 2nd-ring squares are reachable
  h = reachable2;
  while&#40;h&#41; &#123;                                 // with BSF this could be done single pass
    int todo = h & 0xFF;                     // treat in two groups of 8
    while&#40;todo&#41; &#123;
      int b = lowBit&#91;todo&#93;;
      int vec = ringStep&#91;b+offs&#93;;
      int s = sqr + vec;                     // reachable second-ring squares only
      int victim = board&#91;s&#93;;
      reachable3 |= rMask3&#91;b+offs&#93;*!victim;  // when empty, schedule continuation by 3rd step
      todo -= 1 << b;
    &#125;
    h >>= 8; offs += 8;                      // next group of 8
  &#125;
  reachable3 |= reachable2; // total set reachable in 2 or 3 steps
  reachable3 &= ~corners;   // remove corner squares already reached by diagonal slides
  return reachable3;        // bitmap of all reachable squares other than 1st ring & corners
&#125;

As the area map only extends 3 steps, a burn would be possible if a 3-step move from the King reaches next to a Demon. And that square must be empty then, so that the Demon could use it as its first step. To test this, I added a new pre-calculated table, areaContact[], which as a function of the vector from the source of the area move to some other square stores an area map of the squares adjacent to that other square. By intersecting the area map around the King with the areaContact[demonSqr - kingSqr] we get the set of squares that the Demon could use as a first step to burn the King.

GenAreaMap() did not look what was on those squares; its function is just to calculate if they are attacked. So the squares the Demon could step to to then reach a valid burn site in two more steps should be extracted from the area map, and then checked for emptiness. As soon as one of the squares is found empty, we are in 'burn check' by the Demon. Making the intersection and finding the first empty square in it is a whole lot less work than generating all 4th steps from the squares that the area map indicates reachable in 3 steps, to see if a Demon is on one of those.

Sliding burns

When a Demon is outside the range of an area-move burn (so more than 4 King steps away), it might still be able to slide to a square next to the King with one of its long-range moves. Fortunately there is at most one direction it could use for that, when it is so far away. So we added two more vector-indexed tables, towards[] and crossDist[]. These tabulate the direction (if any) in which you would pass through the 3x3 neighborhood of the given target, and the distance to the closest square of the neighborhood in that direction, respectively.

This distance can then be compared to the view distance in that direction, to see if we can actually reach the square. If we can just reach it (i.e. if it is not empty) we have to worry whether there is something on it that would stop us (a border guard or own piece). Even if we can reach it, (i.e. it is empty or an enemy piece) we have to worry whether we would evaporate there (i.e. land next to a royalist Demon). If we would evaporate on an empty square, it might be possible that a more-distant square on the same ray would still be adjacent to the target, but not to the Demon, so we can burn the target there. All these complications make it a pretty cumbersome procedure:

Code: Select all

int
CheckTest &#40;int sqr&#41;
&#123; // test if 'sqr' is attacked by 'side'.
  int xstm = &#40;board&#91;sqr&#93; & 1&#41;;               // color of sqr occupant &#40;King&#41;
  int stm = xstm ^ 1;                        // color of enemies trying to capture it
  int64 att = attacks&#91;sqr + ASIZE*stm&#93;;      // PBeM rules&#58; King can be jump-captured
//  int att = attacks&#91;sqr + ASIZE*stm&#93;;      // Historic rules&#58; King immune to jumping slides
  int64 kingMap = 0;
  int demonStack&#91;4&#93;, nearDemons = 0;         // stack of Demons in area-move burn range
  int areaDemons = 0;                        // number of Demons in area-move capture range
  int todo, demon;
  if&#40;att & !A_VICE&#41; return 1;                // incontrovertable direct attacks &#40;including Demon slides&#41;
  for&#40;demon=2+stm; demon<10; demon+=2&#41; &#123;     // loop through all Fire Demons
    int s = location&#91;demon&#93;;
    if&#40;s != CAPTURED&#41; &#123;                      // found one that is present
      int vec = sqr - s;
      int dist = distance&#91;vec&#93;;              // determine distance &#40;to check later if in area-move range&#41;
      int d = towards&#91;vec&#93;;                  // direction towards sqr's 3x3 neighborhood
      if&#40;d >= 0&#41; &#123;                           // a ray though 's' intersects it &#40;only if outside area range&#41;
        int dist = crossDist&#91;vec&#93;;           // distance to first-encountered square in there
        int view = viewDist&#91;s&#93;.d&#91;d&#93;;         // distance to first obstacle in that direction
        if&#40;dist <= view&#41; &#123;                   // path to King neighborhood is clear
          int v = step&#91;d&#93;;
          int t = s + v*dist;                // first square on the ray that is adjacent to King
          do &#123;
            int r, f;
            if&#40;dist == view&#41; &#123;               // square is not empty
              int victim = board&#91;t&#93;;         // examine what is there
              if&#40;victim == 1&#41; break;         // off board, terminates ray
              if&#40;&#40;victim & 1&#41; == stm&#41; break; // friend of Demon, inaccessible and blocks deeper access
            &#125;
            r = SQR2RANK&#40;s&#41;;                 // square is accessible, check whether it is survivable
            f = SQR2FILE&#40;s&#41;;
            if&#40;!&#40;demons&#91;r&#93;&#91;xstm&#93; & 0757 << 3*f&#41;) // reachable square is not in burn zone of any Demon befriended to King
              return 1;                      // so we can burn King from there
            if&#40;view == dist&#41; break;          // the square was passively guarded by a Demon, but no alternative
            t += v; dist++;                  // try the next square along the ray
          &#125; while&#40;distance&#91;sqr-t&#93; < 2&#41;;      // as long as it is still adjacent to King
        &#125; 
      &#125;
      if&#40;dist < 5&#41; &#123;                         // is in area-move burning range
        demonStack&#91;nearDemons++&#93; = s;        // remember such Demons
        areaDemons += &#40;dist < 4&#41;;            // and count those that are close enough to have direct attacks
      &#125;
    &#125;
  &#125;
  todo = att & 7;                            // VG area-attack bits
  if&#40;todo | areaDemons&#41; &#123;                    // one or more VGs / FDs in area-move range
    kingMap = GenAreaMap&#40;sqr, -1&#41;;           // construct all clear paths from King &#40;as they work both ways&#41;
    while&#40;todo&#41; &#123;                            // extract VGs
      int b = lowBit&#91;todo&#93;;                  // VG number &#40;0-2&#41;
      int bit = 1 << b;
      int piece = bit2vice&#91;b&#93; + stm;         // piece-list index of VG
      int s = location&#91;piece&#93;;               // source of its attack
      if&#40;kingMap & 1LL << sqr2area&#91;s-sqr&#93;)   // VG square in map, so path exists
        return 1;                            // hence in check
      todo -= bit;                           // was blocked, next
    &#125; // next VG
  &#125;
  if&#40;nearDemons&#41; &#123;                           // one or more FD are in area-move burning range
    int64 burnMap = GenAreaMap&#40;sqr, xstm&#41;;   // pass through 1st-ring friendly neighbors, which are burn targets
    int i;
    for&#40;i=0; i<nearDemons; i++) &#123;            // for all Demons in range
      int g = 0;
      int s = demonStack&#91;i&#93;;                 // get location
      int64 adjacent;
      if&#40;distance&#91;s-sqr&#93; < 4 &&              // Demon is in area-move direct-capture range
         burnMap & 1LL << sqr2area&#91;s-sqr&#93;)   // direct path between King and Demon
        return 1;                            // is always check
      adjacent = areaContact&#91;s-sqr&#93;;         // squares in area adjacent to this Demon
      adjacent &= burnMap;                   // set of squares to which Demon could step first to burn King
      while&#40;adjacent&#41; &#123;
        int todo = adjacent & 0x1FF;
        while&#40;todo&#41; &#123;                        // loop through these squares
          int b = lowBit&#91;todo&#93;;
          int s = sqr + ringStep&#91;b+g&#93;;
          int piece = board&#91;s&#93;;              // examine square
          if&#40;!piece&#41; return 1;               // if it is empty, Demon can pass to burn us
        &#125;
        g +=9; adjacent >>= 9;
      &#125;
    &#125;
  &#125;

  return 0;
&#125;

hgm · Post by **hgm** » Wed Mar 29, 2017 11:57 am

Promotions

Promotion rules

The promotion rules of Tenjiku Shogi are somewhat complicated (and cotroversial, because everyone believes them to be the same as the Chu-Shogi rules, which were originally misunderstood in the west.) Most pieces can promote, on two occasions
1) when entering the 5-rank-wide promotion zone from outside of it
2) when making a capture starting inside the zone.
Promotion is optional, which explains why (2) is needed; if it were mandatory there could never be any promotable pieces inside the zone. Some pieces lose some of their moves o promotion, so that it can make sense to defer promotion. But some of these pieces move irreversibly forward, and then can never leave the zone again. In Chu Shogi there is therefore a special rule that a Pawn reaching last rank can promote there, despite the fact that he already was in the zone. I analogy, the Iron General and Knight should be allowed to promote on the last and forelast rank, respectively, in Tenjiku Shogi. (These pieces do not occur in Chu Shogi.)

Often people use the promotion rule of modern Shogi in Tenjiku Shogi, which does not restrict (2) to captures, so that any move that ends or starts in the zone can promote. This then does not need an exception for irreversible pieces, although it specifies that they must promote when they reach the point they would have no moves left. (But you would be a fool not to, in that case, and the ancients in general did not provide special rules only to stop you from being a fool!)

Non-captures

Fortunately captures and non-captures are already generated by different sets of routines (by victim or by mover, respectively), so we don't have to examine the to-square occupant to decide what we are dealing with. The low-level routine for pushing non-captures on the move stack (GenMove) can simply use (1) only, or optionally use the modern rule, while the routine for pushing captures (GenCapt) can always use the modern rule.

Where promotion only adds capabilities, you would not want to consider the option of deferring. So the routine should push the requested move as a promotion in that case, whenever promotion is allowed. Otherwise, when promotion is allowed, it should both push the promotion and the deferral. Promotion is indicated by a single bit (M_PROMOTE) in the move format, as there is no promotion choice other than doing it or not. So there is a table promote[piece] that for each piece lists what promoted piece should replace it.

The exceptions for irreversible pieces are handled by defining 5 promotion zones, and tabulate for each piece in promoCode[piece] by 5 bit flags in which of the zones it can promote. These are the regular zones for white and black, and the special zones formed by the last ranks and forelast ranks, used by the irreversible pieces next to the regular zones. Finally there is zone that covers the entire board. A board-size table zoneTab[sqr] idicates through the same 5 bit flags to which zones the square belongs.

Code: Select all

#define PR_WHITEZONE   0x01 /* promotion zones to which Chu rules may be applied ('on entry')         */
#define PR_BLACKZONE   0x02
#define PR_LASTRANK    0x04 /* special promotion zone for Pawn &#40;Chu&#41; or Iron General &#40;Tenjiku&#41;        */
#define PR_FORELAST    0x08 /* special promotion zone for Knight                                      */
#define PR_EVERYWHERE  0x10 /* set everywhere, and on pieces where deferral never makes sense         */
#define PR_NODEFERRAL  0x1C /* bits to suppress deferral &#40;the special zones always do!)               */

char zoneTab&#91;BSIZE&#93;;     /* board-size table with promotion flags per square */
char promoCode&#91;NPIECES&#93;; /* flags which promotion zones piece can use        */

void
ZoneInit &#40;int zoneSize&#41;
&#123; // initialize the table that indicates promotion zones;
  int r;
  for&#40;r=0; r<RANKS; r++) &#123;
    int f, code = 0;
    int rr = RANKS - 1 - r;                    // rank as counted from black side
    if&#40;r  < zoneSize&#41; code |= PR_BLACKZONE;    // mark promotion zones
    if&#40;rr < zoneSize&#41; code |= PR_WHITEZONE;
    if&#40;r == 0 || rr == 0&#41; code |= PR_LASTRANK; // NOTE&#58; white and black share the special zones
    if&#40;r == 1 || rr == 1&#41; code |= PR_FORELAST; // &#40;pieces using those cannot enter them in their own camp&#41;
    code |= PR_EVERYWHERE;                     // set everywhere, to match piece's deferral-suppression bit
    for&#40;f=0; f<FILES; f++) &#123;
      zoneTab&#91;VEC&#40;f,r&#41;&#93; = code;
    &#125;
  &#125;
&#125;

The bits of the 3 special zones can be set in the promoCode of the piece to indicate deferral is pointless in the given zone. This is tested in the to-square. The possibility to promote on last or forelast rank always implies that deferral is pointless there, and for pieces where deferral is pointless in general, the all-board zone can be used.

Code: Select all


void
GenMove &#40;int fromSqr, int toSqr&#41;
&#123; // push non-capture on move stack
  int fromCode = zoneTab&#91;fromSqr&#93;;
  int toCode   = zoneTab&#91;toSqr&#93;;
  int touched  = fromCode | toCode;
  int r = SQR2RANK&#40;toSqr&#41;;
  int f = SQR2FILE&#40;toSqr&#41;;
  moveStack&#91;msp++&#93; = MOVE&#40;fromSqr, toSqr&#41;;     // generate move
  if&#40;demons&#91;r&#93;&#91;2-zoneSide&#93; & 0757LL << 3*f&#41; &#123;  // test if we land next to Demon
    moveStack&#91;msp-1&#93; |= M_EVAPORATE;           // flag evaporation. &#40;Should we prune this?)
  &#125; else                                       // don't consider promotion if we evaporate
  if&#40;touched & zoneSide&#41; &#123; // applicable promotion zone touched; test if we can / must promote
    int piece = board&#91;fromSqr&#93;;                // retrieve piece
    int code = promoCode&#91;piece&#93;;               // and promotion info for it
    if&#40;promotionOnEntry&#41; touched &= ~fromCode; // erase bits of zones we are already in
    if&#40;code & touched&#41; &#123;                       // piece can promote in the entered zone
      if&#40;code & toCode & PR_NODEFERRAL&#41; &#123;      // deferral makes no sense for this piece in this place
        moveStack&#91;msp-1&#93; |= M_PROMOTE;         // convert the already generated move to a promotion
      &#125; else &#123;                                 // piece can also defer in this location
        moveStack&#91;msp&#93; = moveStack&#91;msp-1&#93;;     // duplicate move
        moveStack&#91;msp++ - 1&#93; |= M_PROMOTE;     // convert first of the two to a promotion
      &#125;
    &#125;
  &#125;
&#125;

Captures

For captures the zoneTab entries of from- and to-squares can be ORed, to indicate where promotion is possible, and then ANDed with the promoCode to see whether the piece is promotable. As promotions are relatively rare, we only bother to look up the piece's promoCode when the move actually touches the regular zone of the player we are generating moves for. This weeds out false promotions through the all-board zone. The bottom half of the GenCapt() routine takes care of this:

Code: Select all

void
GenCapt&#40;int from, int to&#41;
&#123; // push indicated capture on move stack, but detect if attacker can make multi-captures,
  // and generate these first if we haven't already done so.
  int attacker = board&#91;from&#93;;
  int jumps = jumpMask&#91;attacker&#93;;
  int val = qval&#91;board&#91;to&#93;&#93;;
  int touched;
  if&#40;jumps & 0x8F&#41; &#123; // attacker is special &#40;test ignores fN, bN &#40;Knight&#41; and all-D &#40;Kirin, TSA FE&#41;) &#40;rare&#41;
    if&#40;jumps == JC_DEMON&#41; return;     // all captures by FD have already been generated with burns; suppress
    if&#40;jumps == JC_TETR&#41; &#123;            // piece is Tetrarch
      if&#40;distance&#91;to-from&#93; < 2&#41; &#123;     // captures adjacent piece, so must be rifle capture
        int d = direction&#91;to-from&#93;;
        to = M_SPECIAL + &#40;9*d ^ 4&#41;    // encoding for rifle capture
             - evaporate;             // and suppress possible evaporation on to-square
      &#125;                               // other Tetrarch moves are normal captures
    &#125; else if&#40;jumps != 3&#41; &#123;           // is not Phoenix, so has lion power &#40;Ln, LH, FE, HF, SE&#41;
      int64 b = 1LL << &#40;attacker>>1&#41;; // bit representing it in done-flags
      if&#40;!&#40;specialsDone & b&#41;) &#123;       // first time we see this attacker
        GenLionCapts&#40;from, jumps&#41;;    // generate all its e.p. captures
        specialsDone |= b;            // and mark this as done, so we won't do it again
      &#125;
    &#125; // &#40;the Phoenix is not special, and is the only piece that has all A moves, and no D or N&#41;
  &#125;
  moveStack&#91;msp++&#93; = KEYMOVE&#40;from, to, 5*val - qval&#91;attacker&#93;) + evaporate; // MVV part of key needed to compare with double capts
  if&#40;evaporate&#41; return;                     // no promotion possible when we evaporate
  touched = zoneTab&#91;from&#93; | zoneTab&#91;to&#93;;    // all promotion zones that are touched
  if&#40;touched & zoneSide&#41; &#123; // the capture touched the applicable promotion zone
    int code = promoCode&#91;attacker&#93;;         // zones relevant to the attacker
    if&#40;touched & code&#41; &#123;                    // piece is promotable, and touches its zone
      if&#40;touched & code & PR_NODEFERRAL&#41; &#123;  // defferral is nonsensical for this piece here
        moveStack&#91;msp-1&#93; |= M_PROMOTE;      // convert the move to a promotion
      &#125; else &#123;                              // promoted piece not upward compatible
        moveStack&#91;msp&#93; = moveStack&#91;msp-1&#93;;  // duplicate move
        moveStack&#91;msp++ - 1&#93; |= M_PROMOTE;  // and convert first to promotion
      &#125;
    &#125;
  &#125;
&#125;

hgm · Post by **hgm** » Wed Mar 29, 2017 12:34 pm

Evaporation

Pieces landing next to an enemy Fire Demon evaporate. This can be considered a special kind of promotion, to an empty square. A separate bit (M_EVAPORATE) is used to indicate this in the move format. It interacts with promotion, because when the piece evaporates you should not worry about whether it can promote or defer, and you always get only a single move.

The routines in the previous posting therefore test for evaporation before getting to the promotion part. This has also to be done when generating Fire-Demo burning moves, which is done by yet another routine. This latter routine did not have to worry about promotions, because a Fire Demon does not promote. But a Fire Demon landing next to an enemy counterpart does evaporate like any other piece, and this even suppresses its ability to burn other neighbors.

Currently I have implemented the test for evaporation through the demons[rankNr][color] bitstrips that record Demon presence in the 3x16 board strips. This table was easy to update (and only had to be updated on Demon moves). Testing for this on every move you want to generate is pretty cumbersome, though: you have to take apart the to-square into a rank and file part, and use the latter to shift a bit-test mask. For the captures this can be done 'in bulk', as these are generated per victim, so that you get a number of moves with the same to-square in a row. (But how many victims can be captured in more than one way?) The non-captures and burns are geerated per attacker, though, so no two successive to-squares will be the same.

Perhaps it would have been faster to occupy the empty squares next to the enemy Fire Demons with boundary guards (or at least something distinguishable from a empty square), during non-capture generation. The GenMove routine could then just test board[toSqr]. After move generation you would clear the squares again. For GenCapt it is more tricky, as the intention here is that it should be used in staged move generation, searching captures as soon as all captures on the same victim have been generated. You don't want to alter and restore all board squares around Demons for every new victim.

But perhaps the node could maintain a local array "hot[NPIECES]" in which it would mark all potential victims next to a Demon (by setting hot[victim] = nodeCount;). Because the array is local, there is no reason to clear anything when you start searching moves. When running through the victims you could simply test the hot[] value for being equal to the nodeCount (at least its value when the node was entered, which should be remembered). Problem is that with NPIECE ~300 this is rather space-wasting.

hgm · Post by **hgm** » Thu Mar 30, 2017 8:53 pm

Search

Now that perft with all move types implemented seems to work correctly, I am close to trying an actual search. The Search() routine itself is not very special, because the decisions about what moves to search are delegated to subroutines, in particular the MoreMoves() routine that fills the move stack i stages.

My first attemped will be something like this:

Code: Select all

typedef struct &#123; // to pass data back and forth between parent and its children
  // retured from child
  Move bestMove;
  Move gainMove;
  int depth;     // true depth of result after reductions
  // passed to child
  int64 hashKey;
  int pstEval;
  int cnt50;
&#125; Stairway;

int keyStack&#91;MAXPLY&#93;;
Move pvStack&#91;100*MAXPLY&#93;;
int pvPtr;
int nodeCount;
int abortFlag;

#define ROOT          0
#define QSDEPTH       5
#define NULLREDUCTION 2
#define LMRLIMIT     &#40;QSDEPTH+3&#41;
#define MARGIN        50

char *MoveToText&#40;Move m&#41;;

int kings&#91;2&#93;;

int
Search &#40;Stairway *parent, int alpha, int beta, int redRequest, int minDepth, int maxDepth&#41;
&#123;
  Stash stash;               // holds prematurely generated moves &#40;Demon burns&#41;
  Stairway child;            // for two-way communication with child
  int64 areaMaps&#91;4&#93;;         // for each of our VG, the target set of its area moves
  int oldMsp = msp;          // save move stack pointer
  int firstMove;             // start of the node's move list in the move stack
  int pvStart = pvPtr;       // start of the node's PV in the pvStack
  int inCheck;
  int startAlpha;
  int originalAlpha;
  int bestScore;
  int startScore;
  int currentEval;
  int futile;                // futility limit&#58; minimal victim value required to surpass alpha
  int resultDepth;           // depth to which the calculated score is valid
  int reduction;             // depth reduction we apply on behalf of the preceding &#40;late&#41; move
  int iterDepth = QSDEPTH;   // IID iteration depth, set up to start iterating at 1 ply
  int bestNr = 0;            // index of best move in move stack &#40;starts in unused part, which holds 0 move&#41;
  int xking = location&#91;kings&#91;stm^1&#93;&#93;; // square number of enemy King &#40;stm has not changed yet!)
  int king = location&#91;kings&#91;stm&#93;&#93;;// square of own King &#40;flips side to move!)
  int i;
  int64 hashKey = parent->hashKey + 2*stm;
  int slot = 0;
  HashEntry *entry = hashTable + (&#40;int&#41;parent->hashKey & hashMask&#41;;
  Move hashMove;

  stash.best = stash.stage = 0;   // initialize move stash

  // Hash probe
  if&#40;entry&#91;0&#93;.lock == hashKey || entry&#91;++slot&#93;.lock == hashKey&#41; &#123; // hash hit
    int score = entry&#91;slot&#93;.score;
    int flags = entry&#91;slot&#93;.flags;
    int depth = entry&#91;slot&#93;.depth;
    hashMove  = entry&#91;slot&#93;.move;
    if&#40;&#40;score <= alpha || flags & H_LOWER&#41; &&
       &#40;score >= beta  || flags & H_UPPER&#41;   ) &#123; // usable bound type
      int needed;                                // depth required to satisfy current search request
      if&#40;score <= alpha&#41;    needed = maxDepth;   // fail lows &#40;fail highs in parent&#41; need maximum depth
      else if&#40;score < beta&#41; needed = minDepth;   // PV scores need not go deeper than the parent's IID depth
      else &#123; // score >= beta                    // fail highs &#40;low in parent&#41; can be subject to LMR
        if&#40;depth>=LMRLIMIT&#41; depth += redRequest; // depth that it can actually satisfy
        needed = minDepth;
      &#125;
      pvStack&#91;pvStart&#93; = 0;                      // return empty PV
      parent->depth = depth + 1;                 // depth it can satisfy in parent
      if&#40;depth >= needed&#41; return score;          // hash cutoff
      if&#40;flags & H_UPPER && score < alpha&#41;       // all moves were already searched at 'depth'
        iterDepth = depth;                       // so start IID at depth+1 to prevent redoing that
    &#125;
    entry += slot;                               // for storing new result
    inCheck = flags & H_INCHECK;                 // inCheck info stored in hash table
    currentEval = parent->pstEval + Evaluate&#40;);  // to keep in phase with hash-miss case

  &#125; else &#123; // hash miss; must test legality of preceding move, with some side effects

    slot = -1;                                   // request replacement when storing in hash table
    parent->depth = MAXPLY;                      // King captures are valid to any depth

    // legality test&#58; try to capture King &#40;unlikely, but very cheap&#41;
    if&#40;KingCapt&#40;xking, areaMaps&#41;) return INF;    // direct capture of opponent King possible

    // check test &#40;must be done before we decide if we can stand pat&#41;
    inCheck = CheckTest&#40;king&#41;;

    // try stand pat &#40;cheaper and more likely than King burn&#41;
    currentEval = parent->pstEval + Evaluate&#40;);  // evaluate current position
    if&#40;!inCheck && currentEval >= beta &&        // stand-pat would be possible
       minDepth <= QSDEPTH&#41; &#123;                    // and QS depth is satisfactory for a fail high
      parent->depth = QSDEPTH + 1;               // so parent gets 1-ply result
      return currentEval;                        // and we take the cutoff
    &#125;

    // load move stash with Demon burns &#40;can be rather expensive&#41;
    if&#40;GenAllBurns&#40;&stash, stm&#41;) return INF;     // abort if King could be burned
    stash.stage = 1;                             // first stage of move generation done

    hashMove = 0;                                // no hash move on hash miss
  &#125;

  // check extension or LMR on behalf of parent node
  if&#40;inCheck&#41; minDepth++, maxDepth++, reduction = redRequest = 0; // check extension, not reduced
  else &#123;
    reduction = minDepth - LMRLIMIT;                              // maximum possible reduction
    reduction *= &#40;reduction >= 0&#41;;                                // clip to 0 if negative
    if&#40;reduction > redRequest&#41; reduction = redRequest;            // do not reduce more than requested
    minDepth -= reduction;                                        // apply reduction
  &#125;

  // precompensate search window for delayed-loss bonus
  originalAlpha =
  alpha -= &#40;alpha < currentEval&#41;;
  beta  -= &#40;beta <= currentEval&#41;;
  if&#40;(++nodeCount & 0xFFF&#41; == 0&#41; abortFlag |= StopEvent&#40;3&#41;;

  pvStack&#91;pvPtr++&#93; = 0;     // create empty PV
  startScore = -INF;        // value for full-width search
  startAlpha = alpha;       // remember how alpha should start in every depth iteration

  // stand pat &#40;QS&#41; or null move &#40;elsewhere&#41;
  if&#40;!inCheck&#41; &#123; // but not if we are in check
    if&#40;currentEval < beta&#41; &#123; // we are behind; doing nothing is not a good idea
      if&#40;minDepth <= QSDEPTH&#41; &#123; // QS might do, and will only be deepened when it fails low. Which can only happen if eval <= alpha
        startScore = currentEval;                         // stand-pat score substitutes for non-captures in QS iteration
        if&#40;currentEval > alpha&#41; startAlpha = currentEval; // adjust alpha accordingly
      &#125;
    &#125; else // currentEval >= beta                 // we are ahead, and we may stay so by sitting idle
    if&#40;minDepth <= QSDEPTH&#41; &#123;                     // stand-pat is of satisfactory depth for a fail high
      parent->depth = QSDEPTH + 1;                // here QS, in parent good for 1-ply search
      return currentEval;                         // take stand-pat cutoff here after hash hit
    &#125; else if&#40;1&#41; &#123; // full width&#58; try null move
      int nullDepth = minDepth - NULLREDUCTION - 1;
      if&#40;nullDepth < QSDEPTH&#41; nullDepth = QSDEPTH;
      stm ^= 1; path&#91;ply++&#93; = 0;
      child.pstEval = -parent->pstEval;           // flip eval sign
      child.hashKey = parent->hashKey;            // same hash key
      child.cnt50 = 0;                            // suppress null-move-spanning repeats
      bestScore = -Search&#40;&child, -beta, 1-beta, 0, nullDepth, nullDepth&#41;;
      stm ^= 1; ply--;
      resultDepth = child.depth + NULLREDUCTION;
      if&#40;bestScore >= beta&#41; &#123; bestScore = beta; goto cutoff; &#125;         // null-move pruning; bestNr still at 0
    &#125;
  &#125;

  firstMove = msp += 30; // we are going to search; allocate new space on move stack
  areaMaps&#91;3&#93; = 0;       // mark all VG area moves as 'not done'

  if&#40;hashMove&#41; &#123;
    if&#40;maxDepth > QSDEPTH || hashMove & M_KEY&#41; &#123; // if the move has a non-zero sort key, it is a capture and OK in QS
      moveStack&#91;msp++&#93; = hashMove;               // first move to go on move stack is hash move &#40;if any&#41;
    &#125;
  &#125;

  if&#40;maxDepth <= QSDEPTH&#41; iterDepth = &#40;maxDepth - 1&#41;*&#40;maxDepth > 0&#41;; // no IID in pure QS nodes &#40;start at maxDepth or 1&#41;
  futile = &#40;alpha - currentEval - MARGIN&#41; * (&#40;1 << 16&#41;/50&#41; >> 16;
  if&#40;futile <= 0&#41; futile = -&#40;minDepth <= QSDEPTH&#41;; // when non-captures not futile, QS must be requested explicitly

  do &#123; // Internal Iterative Deepening
    int currentMove = firstMove;
    int highDepth = &#40;iterDepth < minDepth ? minDepth - 1 &#58; iterDepth&#41;; // note&#58; always >= replyDepth
    int replyDepth = iterDepth++;    // next depth; replies searched 1 ply less deep
    if&#40;iterDepth > QSDEPTH+1&#41; futile = 0; // switch off futility pruning after 1-ply search
    bestScore = startScore;
    alpha = startAlpha;
    resultDepth = &#40;alpha > originalAlpha ? QSDEPTH &#58; // keep track of depth to which result valid
                   maxDepth < QSDEPTH ? QSDEPTH + 2 &#58; maxDepth + 2&#41;; // do not poison hash table with d=INF entries for mates
    if&#40;highDepth <= 0&#41; &#123; resultDepth = 1; break; &#125;

    for&#40;;; currentMove++) &#123; // loop over moves
      UndoInfo u;
      Move move;
      int score;
      int sort = 1;

      // pick next move to search
      if&#40;currentMove >= msp&#41; &#123; // out of generated moves, generate next batch
        sort = MoreMoves&#40;&stash, areaMaps, futile&#41;;               // generates moves and returns how many need sorting
        if&#40;sort < 0&#41; &#123;                                            // all &#40;non-futile&#41; moves exhausted
          if&#40;futile < 0&#41; &#123;                                        // kludge to indicate we are doing QS
            if&#40;maxDepth <= QSDEPTH ||                             // QS was all that is requested
               alpha > originalAlpha ) &#123;                          // deepening requests are only serviced on fail lows
              if&#40;resultDepth > QSDEPTH&#41; resultDepth = QSDEPTH;    // so we won't search captures, making this a QS result
              break;
            &#125;
            sort = MoreMoves&#40;&stash, areaMaps, 0&#41;;                // generate non-captures after all
            futile = 0;                                           // and flag we are now at 1 ply
            if&#40;sort < 0&#41; break;                                   // still no moves &#40;can this happen?)
          &#125; else &#123;
            if&#40;sort == -3&#41; &#123;                                      // some moves were futile
              if&#40;resultDepth > QSDEPTH&#41; resultDepth = QSDEPTH + 1;// which would not happen at depth > 1
              if&#40;bestScore < alpha&#41; bestScore = alpha;            // so give them virtual &#40;score, depth&#41; = &#40;alpha, 1&#41;
            &#125;
            break;                                                // termiates non-QS iteration
          &#125;
        &#125;
      &#125;

      // at this point we have a non-empty move stack, but it still may have to be sorted LVA-wise
      if&#40;sort > 1&#41; &#123;
        ExtractBest&#40;currentMove&#41;;    // swaps the remaining move with least-valuable attacker to current
        sort--; // one less to sort
      &#125;
      move = moveStack&#91;currentMove&#93;; // next move
      if&#40;move == 0&#41; continue;        // zapped move
      if&#40;move > &#40;1<<M_MOVSIZE&#41; && move < &#40;2<<M_MOVSIZE&#41; && iterDepth <= QSDEPTH+1&#41; continue; // skip bad captures in QS &#40;and for consistency at d=1&#41;

      MakeMove&#40;&u, move&#41;;
      child.pstEval = -&#40;u.gain + parent->pstEval&#41;;
      child.hashKey = parent->hashKey ^ u.keyChange;

      // repetition check
      child.cnt50 = &#40;parent->cnt50 + 1&#41; * &#40;u.gain < 50&#41;; // reset on captures
      for&#40;i=ply-&#40;child.cnt50-2 | 1&#41;; i<ply; i++)
        if&#40;keyStack&#91;i&#93; == &#40;int&#41; child.hashKey&#41; break;
      
      if&#40;i >= ply&#41; &#123; // no repetition
        int red = &#40;currentMove >= stash.late&#41;; // non-captures get reduction 1
        stm ^= 1; path&#91;ply++&#93; = move;
        keyStack&#91;ply&#93; = child.hashKey;
        score = -Search&#40;&child, -beta, -alpha, red, replyDepth, highDepth&#41;;
        stm ^= 1; ply--;
      &#125; else &#123;
        score = -INF; child.depth = iterDepth; pvStack&#91;pvPtr&#93; = 0; // repetition loses
        if&#40;type&#91;u.piece&#93; == T_KING&#41; score = &#40;inCheck ? INF &#58; 0&#41;;   // but not through King moves
      &#125;

      UnMake&#40;&u&#41;;

      if&#40;abortFlag&#41; goto abort; // unwind search

      if&#40;child.depth < resultDepth&#41; resultDepth = child.depth; // worst child depth

      // minimaxing
      if&#40;score > bestScore&#41; bestScore = score;
        if&#40;score > alpha&#41; &#123;
          int p;
          alpha = bestScore;
          bestNr = currentMove;
          parent->bestMove = move;
          if&#40;score >= beta&#41; &#123;
            // TODO&#58; killers and history update
            resultDepth = child.depth;
            goto cutoff; // valid to minDepth, so stop depth iteration
          &#125;

          // new PV
          p = pvPtr;                                  // returned PV of daughter
          pvPtr = pvStart;                            // pop old PV
          pvStack&#91;pvPtr++&#93; = moveStack&#91;currentMove&#93;;  // start new one with the new PV move
          while&#40;&#40;pvStack&#91;pvPtr++&#93; = pvStack&#91;p++&#93;)) &#123;&#125; // and copy daughter's PV behind it

          if&#40;ply == ROOT&#41; &#123; // new PV in root; print it
            static int oldNr;
            int cecpScore = score;
            if&#40;score < bestScore&#41; bestNr = oldNr; oldNr = bestNr; // undo false best in multi-PV
            if&#40;iterDepth > QSDEPTH+5 && bestScore > 100-INF&#41; alpha -= multiMargin;
            printf&#40;"%d %d %d %d", iterDepth - QSDEPTH, cecpScore, ElapsedTime&#40;0&#41;/10, nodeCount&#41;;
            for&#40;p=pvStart; p<pvPtr-1; p++) printf&#40;" %s", MoveToText&#40;pvStack&#91;p&#93;));
            printf&#40;"\n"); fflush&#40;stdout&#41;;
          &#125;
        &#125;
    &#125; // next move

    // if we get here the iteration failed low

    // check if we reached the required depth
    if&#40;iterDepth < resultDepth&#41; iterDepth = resultDepth;       // we got more than we bargained for!
    if&#40;iterDepth >= minDepth && reduction&#41; minDepth += reduction, reduction = redRequest = 0; // no LMR requested if parent fails high
    if&#40;iterDepth >= minDepth && alpha > originalAlpha ) break; // move is PV; nominal depth suffices
 
    // put best move in front
    if&#40;bestNr > firstMove&#41; &#123;
      int bestMove = moveStack&#91;bestNr&#93;;
      if&#40;bestNr == firstMove+1&#41; moveStack&#91;bestNr&#93; = moveStack&#91;firstMove&#93;; // swap first two
      else firstMove--, moveStack&#91;bestNr&#93; = 0;                            // or prepend and zap original
      moveStack&#91;bestNr = firstMove&#93; = bestMove;
    &#125;

    startScore = -INF;

    if&#40;ply == ROOT&#41; &#123;
      int t = ElapsedTime&#40;0&#41;;
      if&#40;untimed == 1 && t > 10000 || resultDepth > iterDepth&#41;
        printf&#40;"%d %d %d %d <done>\n", resultDepth-QSDEPTH, bestScore, t/10, nodeCount&#41;, fflush&#40;stdout&#41;;
    &#125;

  &#125; while&#40;iterDepth < maxDepth&#41;; //next depth

 cutoff&#58;

  resultDepth -= inCheck;        // store unextended depth

  // hash store
  if&#40;slot < 0&#41; &#123; // miss; decide which one to replace
    static int cnt;
    if&#40;resultDepth != entry&#91;0&#93;.depth - 1 || cnt++ & 3&#41;     // &#40;sometimes&#41; stick to primary slot when we 'undercut' it
      entry += &#40;entry&#91;0&#93;.depth > entry&#91;1&#93;.depth&#41;;          // but usually replace shallowest of two
  &#125;
  entry->lock  = hashKey;                                  // allocate entry
  entry->flags = H_UPPER*&#40;bestScore < beta&#41; + H_LOWER*&#40;bestScore > originalAlpha&#41; + H_INCHECK*inCheck;
  entry->depth = resultDepth;
  entry->score = bestScore += &#40;bestScore < currentEval&#41;;   // store score after delayed-loss bonus
  entry->move  = moveStack&#91;bestNr&#93;;                        // can be 0 is bestNr was left at 0

  parent->depth = resultDepth + 1 + &#40;resultDepth >= LMRLIMIT ? redRequest &#58; 0&#41;; // add the ply that led to this node, and reduction
 abort&#58;
  pvPtr = pvStart; // pop PV &#40;but leave it for caller&#41;
  msp = oldMsp;
  return bestScore;
&#125;

Self Deepening

This uses plain alpha-beta, not PVS. Two things make it a bit different from the standard implementation: it avoids re-searching the same move twice in a row, (e.g. for LMR), because that would mean all the effort spend on move generation and ordering in the first search are abandoned, and have to be done again. So it delegates the decision to re-search unreduced to the daughter node ('Self deepening'), by passing it the nominal reduction (in the redRequest parameter) of the move being searched (depending o its ordering in the parent node).

Internal Iterative Deepening

This self-deepening is also used to refine the IID scheme: all moves will always be searched in every iteration, because a beta cutoff in any iteration will only be accepted as a cutoff after verifying the cutoff holds out to the ultimate depth. So if we must search, say, 8 ply, and at the 4-ply iteration a move scores above beta, we first try that move at 5, 6, 7, 8 ply, and take the beta cutoff on the 8-ply result. If it would stop to fail high at, say, 7 ply, the 4-ply iteration would be finished for the other moves.

Depth bootstrapping

Search() does not only return the score, but also the depth to which this score is valid. Sometimes this is higher than the requested depth, e.g. when you get a hash hit on an over-deep entry. By taking the minimum of the validity depth of all daughters, it can calculate to which depth its own result is valid. When you do IID this is often much deeper than what you intended in the iteration, because you start iterating at a very low depth, and get all hash hits from the previous search, which are much deeper. So althrough it always starts iterating at d=1 for a (say) d=8 search, in a stable search this is likely to give a hash hit valid for 7 ply. So after completing the d=1 iteration, it will realize that it actually got a d=7 result, (without doing ay real work, as it were all immediate hash hits) and contiue with the d=8 iteration instead of the d=2 iteration.

Quiescence Search

To avoid negative depths, the depths are offsetted by QSDEPTH. This allows us to do special things in the first few levels of QS (like searching checks), which would have depths QSDEPTH-1, QSDEPTH-2 etc. So IID will nominally start at depth = QSDEPTH+1, doing QS on the reply. At QS depths IID is effectively disabled by starting it at the final depth.

The self-deepening makes QS a bit tricky, because a call to Search() can be a 'conditional QS', that is, specify a minimum depth of QS, and a maximum depth that is higher. This can for instance happen if a parent that eventually needs to do a 4-ply search starts IID with a 1-ply iteration. The daughter nodes then should do QS. But if that QS happens to fail low, the move in the parent fails high, so that the search in the daughter will have to be deepened to 3 ply (if the fail low there persists) to make the parent happy. So the daughter doesn't really know in advance whether it will stick to QS; this depends on the result of the QS iteration (stand-pat + captures).

Now the 1-ply iterations has the captures in common with the QS iteration, in both cases searched with QS replies, and it would be silly to actually do that twicet. So in practice there is no separate QS iteration; you just abort the searching of moves in the 1-ply iteration when you get to the non-captures, if you want to stop after QS. But this means it is tricky how to handle stand-pat, as that does not belong in a 1-ply search. A stand-pat (=evaluation) score <= alpha has never any effect on any iteration, though. And when eval > alpha the QS iteration will not fail low, and will thus not have to be deepened further. So stand pat can safely be used as starting point for the score. If it is >= beta it will even immediately cause a stand-pat cutoff. So when the minimum requested depth is QS, we start with a normal QS iteration (including stand pat), and only if the score stays below alpha we should continue searching the captures, turning it into a 1-ply search.

The Inferno thread

The Inferno thread: Promotions

Re: The Inferno thread: Non-capture generation

The Inferno thread: Non-capture generation

Re: The Inferno thread: Non-capture generation

The Inferno thread: Piece Placement Revisited

Re: The Inferno thread: Perft

The Inferno thread: Check Test

The Inferno thread: Promotions

The Inferno thread: Promotions

The Inferno thread: Search