The Inferno thread

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
hgm
Posts: 25088
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: The Inferno thread

Post by hgm » Wed Mar 08, 2017 10:17 pm

The ideas on the attack map are starting to converge. Especially the Tetrarchs were giving me trouble. They skip the first square, in the sense that they cannot be blocked there. But they actually do attack what is on there as well. (By a rifle capture! Although that is not relevant for the attack map.) To compound the disaster, their moves has a finite range in some directions, where they are allowed to move only one more step after jumping to the second square (when that is empty). So when a distant attack by a Tetrarch is discovered, it does not necessarily attack the piece behind the previous blocker, because that could be out of range. So you really have to figure out where that Tetrarch is, and measure the distances.

Fortunately the Tetrarchs are the only pieces that have such a weird move, and you can at most have 4 of them, and only by promotions; initially you have none at all. So whatever nastiness you have to do to handle them, it won't affect efficiency much. And because there are fewer Tetrarchs than directions, it seems better to asign bits in the attack map to individual Tetrarchs, rather than to a move of an unspecified Tetrarch in a given direction. (In which case you might have to look behind the first piece in the direction the attack is coming from to find the Tetrarch.)

The best solution seems to only use the Tetrarch bits for their distant moves, and indicate the (rifle) attacks to the adjacent squares by the ordinary slider-attack bits. This is possible because these moves cannot occur in combination with other slider attacks (from the same direction); such a combination (and thus the extra bit flag) is only possible if the Tetrarch is directly behind another piece that attacks you (so it can jump over it).

This brings me to the following format of the attack-map elements:

Code: Select all

// Attack map. Packed as follows:

#define GEN3  0xFF000000000000LL /* 4 bits flagging GG jump attacks               */
#define GEN2    0xFF0000000000LL /* 4 bits flagging VG jump attacks               */
#define GEN1      0xFF00000000LL /* 8 bits flagging RG + BG jump attacks          */
#define RAYS        0xFF000000   /* 8 bits flagging slider attacks per direction  */
#define JUMPS         0xFF0000   /* 8 bits flagging 2-square jumps per direction  */
#define OBLIQUES        0x3FFF   /* 14 bits flagging off-ray attacks per attacker */
#define A_KNIGHTS       0x3000   /* Knights                             */
#define A_LIONS          0xC00   /* Lions with Knight attacks           */
#define A_HAWKS          0x300   /* Lion-Hawks with Knight attacks      */
#define A_TETRARCHS       0xF0   /* Tetrarchs that have distant attack  */
#define A_VICES           0x07   /* Vice Generals that have area attack */

int64 attacks[2*ASIZE];
The format of the attack table is also an issue; it turns out to be rather inconvenient to limit the table to real board squares. Because this would force you to first test if a certain move (obtained by extending a discovered slider move to the next obstacle, or by jump moves from a piece that you just placed) lands on board, before you can access the corresponding attack-map element. It would be much easier (and probably faster) to just set the bit indicating the attack, also for off-board squares. So I will probably extend the attack map to also cover the two-row-wide guard band around the board, which is capable to catch all moves that start on the board.

[Edit]
I am afraid this still needs some modification: even though only a single attack by a jumping slider of a given level can come from any direction, it is inconvenient to indicate those per direction. This because when we want to generate captures on a piece, we would have to know where the attack came from. (For discovering the attack during attack-map update this is not needed, as all jumpig sliders have infinite range.) And we cannot easily get that information: the normal view-distances only record the nearest occupied square, while the jumping attack might have jumped over that and many others. While the view-distance tables for the higher levels do not contain any information on the square of the victim, because as far as the higher level is concerned, this square is empty.

So it is better to indicate attacks by jumping generals per piece, rather than per direction. This actually requires fewer bits, as there can be at most 8 level-1 jumping sliders (4, plus 4 through promotion), 3 level-2 jumping sliders (1 + 2 through promotion of level-1 jumping sliders), and 3 level-3 (same).

Code: Select all

#define GEN3 &#40;0x7LL << 44&#41;
#define GEN2 &#40;0x7LL << 40&#41;
#define GEN1 &#40;0xFFLL << 32&#41;
Note that indicating the Tetrarch attacks per piece rather than per direction is the only way, as two Tetrarch attacks could come from the same direction (one Tetrarch directly behind the other, and thus jumping over it).

User avatar
hgm
Posts: 25088
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: The Inferno thread

Post by hgm » Fri Mar 10, 2017 11:18 am

Capture Generation

We will need two methods to generate captures: per victim or per attacker. The per-victim generation is used when generating captures for the purpose of searching them. Usually it is the less efficient way of generation, but as the captures can be generated already in MVV order, you earn part of that back in move sorting. And unlike the per-attacker generation, it can be used for staged move generation, where a cutoff on a capture of a valuable victim would save you the work of generating captures on all the rest. (With 78 pieces that is not insignificant!). And the main source of inefficiency, that even for pieces with very few moves you have to look in all directions powerful pieces can move in to detect the attackers (or test all possible attackers from the piece list), is supposed to be remedied by the attack map. Because the latter specifies exactly from where actual attacks are coming in, so that you won't waste time looking where there turns out to be nothing.

Per-attacker capture generation is needed for updating the attack map. It must be used to generate attacks from the new location of pieces that have been moved, and can also be used to remove attackes that were made from the old location (or when a piece is captured). This does not have to use information from the attack map, but it still can conveniently use the information in the view-distance table: there is no need to make a ray scan to search for a victim when you already know where your sliding move ends, and can directly examine what is at the end of it. (And for updating the attack map you don't really care what is there, as the map should contain also 'friendly fire', so that you can see whether a piece is protected. Which will turn into real attacks when the piece sitting there gets captured.)

The per-attacker generation must apply the game rules to arrive at the piece moves. For efficient access (preventing an extra level of indirection through piece type) the rules on piece movement are stored as part of the piece list, i.e. indexed by piece number. A bit space-wasting, but except for Pawns there are at most 4 copies of any piece, so this is affordable. The movement data for a single piece consists of 3 elements: a table that for each direction indicates the range of the piece in that direction, where 0 indicates the piece does not move in that direction at all. (In Tenjiku Shogi ranges 1, 2 and infinite = X = 16 occur.) Normally I encode movement data as a zero-terminated list of steps + ranges, but for incremental update of the attack map it is important to have random access to the ranges. (You often want to know how far a given piece can move in a given direction.) To not waste time on directions the piece does not move in, each piece also has a 'dirMask', a byte quantity that idicates the non-zero direction. Looping over directions is then replaced by next-bit extraction from this byte (through a lowBit[] table) to only treat relevant directions. For each direction the view distance and range tell you if there is something to attack, and the elementary step for that direction plus the view distance bring you to it. If the piece was a jumping slider, it does not only attack the piece at the end of its normal view, but possibly many pieces behind it, so you have to hop from obstacle to obstacle until you reach the full extent of the high-level view distance for that jumping slider.

That still leaves a number of pieces with 'odd-bal' moves. These include jumps to the 2nd square (diagonal, orthogonal or hippogonal), area moves (1-3 King steps), and ski-slides of the Tetrarchs (skipping the adjacent squares). A byte 'jumpMask' for each piece indicates these moves. The orthogonal and diagonal jumps to the 2nd square always occur as the full set of four, so they each need only a single bit to indicate them. Not all pieces that have Knight jumps have all of them, though: Shogi Knights only have the two most-forward jumps. (And for black this looks like backward jumps.) For convenience we use 4 bits that each indicate a pair of Knight jumps, so that the Kights can have the bit for the forward (or backward) pair set, and other pieces (Lions and Lion Hawks) set all 4 bits. The remaining 2 bits in jumpMask indicate the piece has an area move (Vice General only, as the Fire Demon is treated by dedicated code), or a ski-slide (Tetrarch only). It is hard-coded in which directions these ski-slides go, and how far.

This produces the following code:

Code: Select all

#define NPIECES 4*78 /* 78 base pieces + 78 promoted pieces for both players */

char ranges&#91;NPIECES&#93;&#91;8&#93;; /* range of sliding moves &#40;level 0-3&#41;    */
char dirMask&#91;NPIECES&#93;;   /* flags non-zero directions in ranges&#91;&#93; */
char jumpMask&#91;NPIECES&#93;;  /* flags 2nd-square jumps and area moves */

int knightJump&#91;&#93; = &#123; VEC&#40;-1,2&#41;, VEC&#40;-1,-2&#41;, VEC&#40;2,1&#41;, VEC&#40;2,-1&#41;, VEC&#40;1,2&#41;, VEC&#40;1,-2&#41;, VEC&#40;-2,1&#41;, VEC&#40;-2,-1&#41; &#125;;

// per-attacker move generation &#40;uses game rules, writes attack map&#41;

void
AddMoves &#40;int sqr, int piece, int sgn&#41;
&#123;  // Add &#40;or remove, when sgn = -1&#41; captures of the given piece to attack map
   int specials;
   int color = ASIZE*&#40;piece & 1&#41;;   // offset of black attacks in mapp
   int csqr = sqr + color;          // entry for sqr in the attack map for the applicable color
   int todo = dirMask&#91;piece&#93;;
   while&#40;todo&#41; &#123; // first do normal sliding/stepping attacks
     int d = lowBit&#91;todo&#93;;          // a direction into which we move
     int vec = step&#91;d&#93;;
     int range = ranges&#91;piece&#93;&#91;d&#93;;  // how far we move
     int dist = viewDist&#91;sqr&#93;.d&#91;d&#93;; // distance to obstacle in that direction
     todo -= 1 << d;
     if&#40;range > X&#41; &#123; // this indicates the move is a jumping slide &#40;rare&#41;
       int64 bit = gen2bit&#91;piece&#93;;  // bit representing this jumping slider in attack map
       int l = piece2level&#91;piece&#93;;  // level of opacity
       int stop = sqr + viewDist&#91;sqr + l*DSIZE&#93;.d&#91;d&#93;;
       int s = sqr;
       bit *= sgn;                  // set up for addition or removal
       do &#123; // flag jumping attacks on all down-stream pieces
         s += viewDist&#91;s&#93;.d&#91;d&#93;*vec;
         attacks&#91;s+color&#93; += bit;
       &#125; while&#40;s != stop&#41;;
     &#125; else if&#40;range >= dist&#41;       // target is within range
       attacks&#91;csqr + dist*vec&#93; += sgn*&#40;0x1000000 << d&#41;;
   &#125;
   specials = jumpMask&#91;piece&#93;;
   if&#40;specials&#41; &#123;  // piece &#40;also&#41; has non-sliding moves &#40;rare&#41;
     int todo = specials & 0xF0; // Knight jumps &#40;Knights and Lion&#40;Hawk&#41;s&#41;
     int bit = piece2bit&#91;piece&#93;; // single-bit mask indicating the piece &#40;if any&#41;
     bit *= sgn;   // determines if we set or clear the attack-map bits
     while&#40;todo&#41; &#123; // Loop over move pairs. &#40;Knights do only 1 pair, Lions all pairs&#41;
       int d = lowBit&#91;todo&#93;;        // 4-7
       attacks&#91;csqr + knightJump&#91;d&#93;  &#93; += bit;
       attacks&#91;csqr + knightJump&#91;d-4&#93;&#93; += bit;
       todo -= 1 << d;
     &#125;
     if&#40;specials & 3&#41; &#123;   // Piece has jumps to 2nd square. &#40;Always all four symmetry-equivalent ones.)
       if&#40;specials & 1&#41; &#123; // diagonals &#40;on Phoenix & Lion&#40;Hawk&#41;s&#41;
         attacks&#91;csqr+2*jump&#91;1&#93;&#93; += sgn*&#40;0x10000 << 1&#41;;
         attacks&#91;csqr+2*jump&#91;3&#93;&#93; += sgn*&#40;0x10000 << 3&#41;;
         attacks&#91;csqr+2*jump&#91;5&#93;&#93; += sgn*&#40;0x10000 << 5&#41;;
         attacks&#91;csqr+2*jump&#91;7&#93;&#93; += sgn*&#40;0x10000 << 7&#41;;
       &#125;
       if&#40;specials & 2&#41; &#123; // orthogonals &#40;on Kirin, Lion&#40;Hawk&#41;s and Free Eagle&#41;
         attacks&#91;csqr+2*jump&#91;0&#93;&#93; += sgn*&#40;0x10000 << 0&#41;;
         attacks&#91;csqr+2*jump&#91;2&#93;&#93; += sgn*&#40;0x10000 << 2&#41;;
         attacks&#91;csqr+2*jump&#91;4&#93;&#93; += sgn*&#40;0x10000 << 4&#41;;
         attacks&#91;csqr+2*jump&#91;6&#93;&#93; += sgn*&#40;0x10000 << 6&#41;;
       &#125;
     &#125;
     if&#40;specials & 4&#41; &#123; // piece has area move &#40;Vice General&#41;
       MarkArea&#40;sqr, bit, color&#41;;   // flag *potential* area attacks in attack map
     &#125;
     if&#40;specials & 8&#41; &#123; // Piece is Tetrarch. &#40;At this point efficiency hardly matters.)
       int d;
       for&#40;d=0; d<8; d++) &#123; // only two directions done in vain &#40;and even that only in PBeM rules&#41;
         int dist = viewDist&#91;sqr&#93;.d&#91;d&#93;;
         if&#40;dist > 1&#41; &#123;     // contact attacks are treated with the normal slides
           if&#40;d & 1 || d & 2 && dist <= 3&#41; &#123; // hard-coded move&#58; diagonals, and ranks if target within range
             int vec = step&#91;d&#93;;
             attacks&#91;csqr + dist*vec&#93; += bit;
           &#125;
         &#125;
       &#125;
     &#125;
   &#125;
 &#125;

// per-victim move generation &#40;uses attack map&#41;

void
Capture &#40;int sqr, int stm&#41;
&#123;
  int64 att = attacks&#91;sqr + ASIZE*stm&#93;; // access attack map
  unsigned int plainAttacks = att;
  unsigned int jumpAttacks = att >> 32;
  if&#40;plainAttacks&#41; &#123; // there are plain attacks
    if&#40;plainAttacks & A_RAYS&#41; &#123;
      int todo = plainAttacks >> 24; // up to 8 normal sliding attacks
      do &#123;
        int d = lowBit&#91;todo&#93;;
        GenCapt&#40;sqr - viewDist&#91;sqr&#93;&#91;d^4&#93;*step&#91;d&#93;, sqr&#41;;
        todo -= &#40;1<<d&#41;;
      &#125; while&#40;todo&#41;;
    &#125;
    if&#40;plainAttacks & &#40;OBLIQUES|JUMPS&#41;) &#123; // pretty rare, as very few pieces have them, and they are short range
      // jumps to 2nd square
      int todo = plainAttacks >> 16 &0xFF; // up to 8 direct leaps to 2nd square
      while&#40;todo&#41; &#123;
          int d = lowBit&#91;todo&#93;;               // extract directions
          GenCapt&#40;sqr - 2*step&#91;d&#93;, sqr&#41;;
          todo -= &#40;1<<d&#41;;
        &#125;
      &#125;
      // Knight jumps
      todo = plainAttacks >> 8 & 0x3F; // Knight-jumpers
      while&#40;todo&#41; &#123;
        int b = lowBit&#91;todo&#93;;
        int piece = bit2knight&#91;b&#93;;  // piece-list index
        int from = location&#91;piece&#93;;
        GenCapt&#40;from, sqr&#41;;
        todo -= &#40;1<<b&#41;;
      &#125;
     // next area-move attacks
      todo = plainAttacks & A_VICE;
      while&#40;todo&#41; &#123;
        int b = lowBit&#91;todo&#93;;
        int mask = 1 << b;
        int piece = bit2vice&#91;b&#93;;
        int from = location&#91;piece&#93;;
        if&#40;!&#40;mask & vetted&#41;) &#123;
          if&#40;!&#40;vetted & A_VICE&#41;) ClearArea&#40;);
          SetAreaMap&#40;from, mask&#41;;
          vetted |= mask;
        &#125;
        if&#40;areaMap&#91;sqr - from&#93;) GenCapt&#40;from, to&#41;;
        todo -= mask;
      &#125;
      // next Tetrarch attacks
      todo = plainAttacks & A_TETRARCH;
      while&#40;todo&#41; &#123;
        int b = lowBit&#91;todo&#93;;
        int piece = bit2vice&#91;b&#93;;
        int from = location&#91;piece&#93;;
        GenCapt&#40;from, to&#41;;
        todo -= 1<<b;
      &#125;
    &#125;
  &#125;
  // now test for attacks by jumping generals
  if&#40;jumpAttacks&#41; &#123;
    int g;
    for&#40;g=0; g<16; g+=8&#41; &#123; // split in two groups
      int todo = jumpAttacks & 0xFF; // upto 8 jumping-slider attacks
      while&#40;todo&#41; &#123;
        int b = lowBit&#91;todo&#93;;
        int attacker = bit2gen&#91;b+g&#93;;
        int from = location&#91;attacker&#93;;
        GenCapt&#40;from, sqr&#41;;
        todo -= &#40;1<<b&#41;;
      &#125;
      jumpAttacks >>= 8; // next group of 8
    &#125;
  &#125;
  // next we do attacks through area moves
&#125;
Note that this code only deals with normal (single-victim) captures. There are several pieces that can combine a Knight jump with a step, (or two step attacks) to make a double capture. Or after a step capture move on to an empty square, or return to where they came from (rifle capture). Per-victim generation of such captures makes little sense. It is assumed that such moves (as well as the Fire-Demon burns) are generated through another method. There are not too many pieces that could make such moves (initially only 6 of the 78), and then they can only make them if adjacent to an enemy piece.

Perhaps it is an idea to have the GenCapt routine test if the attacker is a piece that in principle is capable of double-capture, and in the rare case it is, not just generate the requested move, but all double and hit&run captures as well (stashing the ones with inferior booty somewhere, for later release when such inferior victims come up). Then you would become aware of such moves first time the multi-capturerers can capture something of interest.

User avatar
hgm
Posts: 25088
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

The Inferno thread: Staged Move Generation

Post by hgm » Fri Mar 10, 2017 5:58 pm

Staged Move Generation

The code providing the moves to be searched is a bit more complex than I am used to, because it needs to splice two sources of moves together: those generated victim by victim for single-victim captures, and the multiple captures from Fire-Demon burns and multi-leg movers. The Fire-Demon burns are generated before anything else, as there are likely to be moves along those that capture more than any single victim is worth.

(Well, perhaps we could make an exception for captures of the King, and other Fire Demons: King captures can of course fail high without further search. And amongst the searched moves captures of a Demon should probably be generated immediately after that. Demon x Demon is a problem, though, as attacks by Demons are not recorded in the attack table, so when we are generating attacks on a Demon, we would miss those. Fortunately Demons cannot burn other Demons, so they have to land exactly on them. Hmm, something to think about, I guess.)

The design below assumes there is a second move list local to the node, (the 'stash') which initially will be filled with all the multi-captures. Moves from there will be added to the move list only when there are no higher-valued single victims available that will earn is more as the total of the multi-capture. The sort key for this is supposed to be in the high bits of the move (not needed for encoding the move itself), so that we can do direct comparison of the moves to find the most-profitable one.

Code: Select all

  // local variables
  int bestStash, stashedMoves, victimVal, stashVal, nextVictim, color, currentMove, firstMove;
  int moveStash&#91;200&#93;;

  // before move loop
  nextVictim = xstm+2;      // position just before highest-valued piece of opponent &#40;2 or 3&#41;
  victimVal = qval&#91;victim&#93;; // normally a Fire Demon
  color = ASIZE * xstm;
  bestStash = 0;
  currentMove = firstMove = msp; // allocate empty move list on move stack &#40;msp = move stack pointer&#41;

  // at top of loop over moves
  if&#40;currentMove >= msp&#41; &#123; // reached end of move stack
    // if we have any stashed moves &#40;Demon burns or Lion 2-leg captures&#41;, make sure we know the best one
    if&#40;bestStash == 0&#41; &#123;   // we do not know it, so extract it
      int i, j;
      for&#40;i=0; i<stashedMoves; i++) &#123; // search best of the stashed moves &#40;sort-key wise&#41;
        unsigned int move = moveStash&#91;i&#93;;
        if&#40;move > bestStash&#41; bestStash = move, j = i;
      &#125;
      if&#40;bestStash&#41; moveStash&#91;j&#93; = moveStash&#91;--stashedMoves&#93;;  // remove from stash
    &#125;
    // then make sure we know the most-valuable attacked victim
    stashVal = bestStash >> 24;                               // sort key of best stashed move &#40;total value captured&#41;
    do &#123; // choose between a stashed &#40;multi-leg&#41; move, or an ordinary capture of a new victim from the piece list
      while&#40;victimVal > stashVal &&                           // more juicy not-yet-considered victims are conceivable
            (&#40;nextSqr = location&#91;nextVictim&#41; == CAPTURED ||   // but this one is not present on the board
             &#40;attacks&#91;nextSqr + color&#93; == 0&#41; )                // or not attacked, so we search on
         victimVal = qval&#91;nextVictim += 2&#93;;                   // remember the value of the first tentative victim in line            
      // here we end up with a valuable attacked piece, or with a piece of unspecified status worth too little 
      // &#40;can even be sentinel, which has qval&#91;&#93; = 0, and can thus never be > stashVal&#41;
      if&#40;victimVal < stashVal&#41; &#123; // stashed multi-capture seems better than any still-available single victim
        moveStack&#91;msp++&#93; = bestStash; bestStash = 0;          // release best stashed move and mark it gone
      &#125; else if&#40;victimVal > 0&#41; &#123; // the next-in-line single victim exists and is most-valuable
        Capture&#40;nextSqr, stm&#41;;                                // generate all captures on it
        while&#40;qval&#91;nextVictim += 2&#93; == victimVal&#41;             // and as long as victims have the same value
          if&#40;&#40;nextSqr = location&#91;nextVictim&#93;) != CAPTURED && attacks&#91;nextSqr+color&#93;) // and have attacks on them
            Capture&#40;nextVictim, stm&#41;;                         // also capture those
        &#125;
        victimVal = qval&#91;nextVictim&#93;; // we arrived at a lower-valued victim &#40;could be sentinel with qval&#91;&#93; = 0&#41;
        sort = msp - currentMove;     // request sorting of what we generated
      &#125; else if&#40;victimVal == 0&#41; &#123; // we ran out of both stashed captures and victims
        // HERE WE GENERATE KILLERS AND NON-CAPTURES
        break;
      &#125;
    &#125; while&#40;currentMove >= msp&#41;; // current value group did not produce any moves; choose again
  &#125;
  // at this point we have a non-empty move stack, but it still has to be sorted LVA-wise
  if&#40;sort > 1&#41; &#123;
    int i, j = currentMove;
    unsigned int best = moveStack&#91;j&#93;;
    for&#40;i=j+1; i<msp; i++) &#123; // search move with best LVA key &#40;in upper bits!)
      unsigned int move = moveStack&#91;i&#93;;
      if&#40;move > best&#41; best = move, j = i;
    &#125;
    moveStack&#91;j&#93; = moveStack&#91;currentMove&#93;; // swap to front
    moveStack&#91;currentMove&#93; = best;
    sort--; // one less to sort
  &#125;

User avatar
hgm
Posts: 25088
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: The Inferno thread: Demon Trading

Post by hgm » Sat Mar 11, 2017 9:33 am

Demon Trading

So far my idea was to keep Fire Demons out of the attack map, (because the burning of bystanders in moves to empty squares would not be in there anyway), and start every node by generating all Demon moves that burn something. The latter can already be pretty expensive, though, and even burning a large group of Queen-class pieces is not worth as much as capturing a single Fire Demon. While a special rule of Tenjuku Shogi is that a Demon landing next to another does not burn the latter, (as it would do to other enemies), but instead burns itself without burning anything else.

So Demons can only destroy opponent Demons by ordinary (replacement) capture. These would be found too in the process of generating all burns, but likely quite late in a rather expensive process. So it would be much better if you could see the direct Demon attacks in the attack map. (On other Demons and anything else.) Then the possibility to capture FD x FD would not be missed of you checked for attacks on opponent Demons (and search those with priority) before starting to generate all your own Demon burns. It also would make the test whether you can capture the King more accurate, as this would now see the direct Demon attacks on it too. (It would still miss that you might be able to burn the King by landing next to it, though; this would only be discovered while generating all Fire-Demon burns after the direct captures.)

So I will include direct Demon attacks in the attack table after all. (This is just a matter of putting the true move in the ranges[] table, rather than faking they are zero and hard-coding generation of Demon moves without using that table.) This poses the risk of duplicats, however: once we get to generating captures of (say) a Queen, which will occur after generation of all Demon burns, the move FD x Q (burning who knows what on adjacent squares) will already have been generated and searched. So when Demon attacks are in the attack map (as ordinary sliding attacks, organized per direction), capture by a Demon will have to be suppressed (if the victim is not King or Demon itself).

Now I had foreseen a mechanism anyway to intervene when a capture is made by certain piece types (in the routine GenCapt(from, to) above). This is necessary because for some pieces the capture is special. E.g. Tetrarchs capture adjacent pieces by 'rifle capture', not moving there but staying in place), and will need special encoding so that MakeMove will perform them correctly. Lions can do this in as an alternative to normal capture, and could also decide to move on to a third square after the capture. So the plan was to keep identity info on all pieces in a table type[NPIECES], and assign the type numbers such that the pieces that need special attention during generation (a small minority) can be easily recognized by it. (E.g. by testing "if(type[attacker] >= WEIRDOS)"). Fire Demons could then also be included in that group, and the rarely executed code for the treatment of the group could then test for them, and suppressing the move alltogether.

Code: Select all

void
Sting &#40;int fromSqr, int dir, int stm&#41;
&#123; // exert linear lion power
  int vec = step&#91;dir&#93;;
  int first = board&#91;fromSqr + step&#93;;
  int firstVal = qVal&#91;first&#93;;
  if&#40;first & &#40;first & 1&#41; != stm&#41; &#123;
    EmitMove&#40;fromSqr, M_SPECIAL + &#40;9*d^4&#41;); // rifle capture
    EmitMove&#40;fromSqr, M_SPECIAL + 9*d&#41;;     // hit & run or double capt
  &#125;
&#125;

void
GenCapt&#40;int from, int to&#41;
&#123;
  int attacker = board&#91;from&#93;;
  int pieceType = type&#91;attacker&#93;;
  if&#40;pieceType >= T_WEIRDOS&#41; &#123; // piece has special moves
    if&#40;pieceType = T_DEMON&#41; return;   // captures by FD have already been generated with burns
    if&#40;pieceType == T_TETRARCH&#41; &#123;     // piece is Tetrarch
      if&#40;distance&#91;to-from&#93; < 2&#41; &#123;     // capture of adjacent piece
        int d = direction&#91;to-from&#93;;
        to = M_SPECIAL + 8*d + d ^ 4; // replace by encoding for rifle capture
      &#125;
    &#125; else &#123;
      int b = 1 << attacker;    // bit that represents attacker
      if&#40;!&#40;b & specialsDone&#41;) &#123; // special moves not yet generated for this piece in this node
        specialsDone |= b;      // generate all its special moves at once, and mark piece as done
        if&#40;pieceType >= T_LION&#41; &#123;                       // Lion or Lion Hawk
          for&#40;d=0; d<8; d++) &#123;
            int neighbor = board&#91;from + step&#91;d&#93;;
            if&#40;neighbor > 1 && &#40;neighbor & 1&#41; != stm&#41; &#123; // adjacent enemy makes two-leg possible
              int i;
              int firstVal = qval&#91;first&#93;;
              for&#40;i=0; i<8; i++) &#123;                      // all possible second steps
                EmitMove&#40;from, SPECIAL + 8*d + i&#41;;
              &#125;
            &#125;
          &#125;
        &#125; else if&#40;pieceType == T_FALCON&#41; &#123;              // Horned Falcon
          Sting&#40;from, 4*color, stm&#41;;                    // forward sting &#40;direction 0 or 4&#41;
        &#125; else if&#40;pieceType == T_EAGLE&#41; &#123;               // Soaring Eagle
          Sting&#40;from, 4*color + 1, stm&#41;;                // diagonally forward stings &#40;1 & 7 or 3 & 5&#41;
          Sting&#40;from, 4*color - 1 & 7, stm&#41;;
        &#125; else if&#40;pieceType == T_FREEE&#41; &#123;               // twice Cat Sword part of Free Eagle &#40;not used on PBeM&#41;
          for&#40;d=1; d<8; d+=2&#41; &#123;                         // diagonal steps only
            int first = board&#91;from + step&#91;d&#93;;
            if&#40;neighbor > 1 && &#40;neighbor & 1&#41; != stm&#41; &#123; // adjacent enemy makes two-leg possible
              int i;
              for&#40;i=1; i<8; i+=2&#41; &#123;                     // diagonal steps only
                EmitMove&#40;from, SPECIAL + 8*d + i&#41;;
              &#125;
            &#125;
          &#125;
        &#125;
      &#125;
    &#125;
  &#125;
  EmitMove&#40;from, to&#41;;
&#125;
This code suppresses all captures with Demons, replaces all adjacent captures by Tetrarchs with rifle captures, and does one-time generation of all double and hit&run captures of pieces when their most-valuable victim come up (and then marks that piece as done). The latter could generate captures more profitable than the MVV of this piece, by capturing something together with it; these will then receive sort keys that will cause them to head the LVA sorting that still has to take place after generation of all captures of a certain victim class. They might also produce double and hit&run captures less interesting than the current MVV, though (e.g. capturing two Pawns, or even just one with a rifle capture). Such captures could be emitted to the 'move stash' that already holds the FD burns, with a sort key based on the victim value.

The procedure in a node then becomes this:
1) test for direct attacks on opponent King in attack map (fail high if any)
2) test for attacks on enemy Demons, and generate their moves
3) stash all captures/burns with our own Demons
4) if the enemy King could be burned in (3), fail high
5) start the move loop, which now first searches the captures of the FD, and then chooses between stashed burns and generating moves of other victims.

We have to do the rather expensive (3) before we can search any moves, in order to know if we can burn the King. Otherwise, in cases where an enemy FD is capturable we could just have searched that capture, and likely fail high before having to generate burns. Perhaps a special test should be devised to quickly determine when we cannot burn a King. Such tests are conceivable: we could make a table that as a function of relative distance of King and Demon tells us in which direction we would have to move, and how far minimally to land next to the King. We could then test the view-distance in that direction to see if we can get there. If not, we should also be out of reach of the area move. We leave this for later.

User avatar
hgm
Posts: 25088
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: The Inferno thread: Burn Generation

Post by hgm » Sun Mar 12, 2017 9:40 am

Burn Generation

Each node will start with generating from scratch all Fire-Demon moves that capture or burn something. This is an expensive part: a Demon moves as Queen except sideways, or can make up to 3 King steps in independently chosen directions. The latter move alone would make it reach 48 squares on an empty board (a 7x7 area), and the slides easily give an actively positioned Demon 30 more moves. For each of these it will have to be tested whether they land on or next to an opponent. So any inefficiency in testing will hurt badly. Especially since most of the moves will not burn anything. (E.g. the backward moves, and those that do not reach forward far enough to reach the enemy lines.)

So eaxamining all 8 neighbor squares for every pseudo-legal Demon move to hunt for enemies is not a good idea; most of the time you would have to examine all 8 before you can conclude there were none. To speed this up we keep a data structure that already pre-calculates which squares border on pieces of a given color. With bitboards you would just intersect a King neighborhood of the target square with the usual 'white' or 'black' bitboards. But in Tenjuku Shogi the board is 16x16, and even in 64-bit arithmetic a simple intersection needs four steps.

In contrast to what I proposed earlier in this thread, I will use a bit set for keeping track of pieces in the neighborhood. Basically these are bitboards representing a 3x16 strip of the 16x16 board. This requires 48 bits, and thus fits in an int64. There is one such 'bitstrip' for each file, in an array burns[fileNr][color]. So the bitstrips overlap, and each square occurs in three of them. Each strip contains the entire environment of each square on its cetral file. So you only have to test a single bitstrip to determine if a move to that square is a burn. And such a test not only reveals if there are burns, but also provides you with a bit set that tell you where the burn victims are located!

This is important, because we want to generate the moves with a sort key that indicates the value of the burned pieces. So we do have to examine those. Also because there could be a King amongst them, and we do't want to continue with nodes where we can capture the enemy King. And it is also relevant of there is an enemy Demon amongst the adjacent pieces. Because according to the rules of Tenjiku Shogi, in such a case we would not burn anything, but on the contrary evaporate ourselve.

Code: Select all

// Accounting of burn squares.

#define burns &#40;rawBurns + 1&#41;

int64 rawBurns&#91;FILES+2&#93;&#91;2&#93;; /* for each file and color the bitboard of a 3x16 strip */

// Burn generation

static int kingSqr, enemy, demonSqr; // for parameter bypassing

int
GenBurn&#40;int toSqr&#41;
&#123; // generate proposed move if it burns something
  static int burnStep&#91;&#93; = &#123; VEC&#40;-1,-1&#41;, VEC&#40;0,-1&#41;, VEC&#40;1,-1&#41;, VEC&#40;-1,0&#41;, VEC&#40;0,0&#41;, VEC&#40;1,0&#41;, VEC&#40;-1,1&#41;, VEC&#40;0,1&#41;, VEC&#40;1,1&#41; &#125;;
  int f = SQR2FILE&#40;toSqr&#41;;
  int r = 3*SQR2RANK&#40;toSqr&#41;;
  int neighbors = burns&#91;f&#93;&#91;enemy&#93;;
  int todo = neighbors >> r & 0777;
  int value, v;
  if&#40;!todo&#41; return 0;             // nothing to burn
  value = v = qval&#91;board&#91;toSqr&#93;&#93;; // direct capture victim
  todo &= ~020;                   // is now done
  while&#40;todo&#41; &#123; // loop over burn victims
    int b = lowBit&#91;todo&#93;;
    int s = toSqr + burnStep&#91;b&#93;;
    int victim = board&#91;s&#93;;        // retrieve them
    value += qval&#91;victim&#93;;        // and sum their value
    todo -= b;    
  &#125;
  if&#40;value & ~0x7F&#41; &#123; // there are Demons and/or Kings amongst adjacent pieces! &#40;Have qval&#91;&#93; = 0x80&#41;
    int dist = distance&#91;toSqr - kingSqr&#93;; // distance from King
    if&#40;dist < 2&#41; &#123;                        // King in neighborhood!
      if&#40;value < 0x100&#41; return 1;         // no adjacent Demons, so burns King
      if&#40;dist == 0&#41; return 1;             // direct hit on King fatal even with adjacent Demon
    &#125;
    if&#40;qs&#41; return 0;                      // in QS this is pointless &#40;at best a tempo-losing equal trade&#41;
//    value = v - DEMON_VALUE;              // adjacent Demon, we don't burn anything, just capture and self-destruct
    StashMove&#40;demonSqr, toSqr + M_BURNED, 0&#41;;
    return 0;
  &#125;
  if&#40;value&#41; StashMove&#40;demonSqr, toSqr + M_BURN*&#40;value != v&#41;, value&#41;;
  return 0;
&#125;
The burns[] array can be updated incrementally quite easily. Each square that gets occupied or evacuated occurs in three bitstrips (for adjacent files). This could have been limited to two, by using 4x16 board sections. But that would complicate the logic for which bits to test, and would need exceptional treatment of rank 0 (because there is no room to fit in rank -1). So we have incremental updates for every placed or lifted piece like:

Code: Select all

  int f =   SQR2FILE&#40;sqr&#41;;
  int r = 3*SQR2RANK&#40;sqr&#41;;
  burns&#91;f&#93;&#91;stm&#93;   += 020 << r; // set the bit for this square in 3 adjacent bitstrips
  burns&#91;f+1&#93;&#91;stm&#93; += 010 << r; // NOTE&#58; must correspond to burnStep&#91;&#93; element order
  burns&#91;f-1&#93;&#91;stm&#93; += 040 << r;
The generation of area moves is a head-ache. Eventually I found a reasonably efficient way, using a kind of temporary bitboard for the 7x7 environment of the Demon, or actually just the 40 squares of the 2nd and 3rd ring of it (16 + 24 squares). By tabulating which squares are reachable (as bitboard) from other squares (used for indexing), in terms of these bitboard, and an ad-hoc square numbering in this environment, it is possible to generate the area moves step by step: the squares reached by the previous step are extracted from the bitboard, and when they are empty, the squares that are reachable from there (from the pre-calculated table) are ORed into the bitboard for the next step. The first step always reaches all squares of the inner ring. This way each board square has to be tested for occupancy only once.

Code: Select all

// tables for efficient generation of area moves

int rMask2&#91;8&#93;;
int64 rMask3&#91;16&#93;;
signed char ringStep&#91;&#93; = &#123; VEC&#40;0,2&#41;, VEC&#40;1,2&#41;, VEC&#40;2,2&#41;, VEC&#40;2,1&#41;, VEC&#40;2,0&#41;, VEC&#40;2,-1&#41;, VEC&#40;2,-2&#41;, VEC&#40;1,-2&#41;, /* 2nd ring */
                           VEC&#40;0,-2&#41;, VEC&#40;-1,-2&#41;, VEC&#40;-2,-2&#41;, VEC&#40;-2,-1&#41;, VEC&#40;-2,0&#41;, VEC&#40;-2,1&#41;, VEC&#40;-2,2&#41;, VEC&#40;-1,2&#41;,
                           VEC&#40;0,3&#41;, VEC&#40;1,3&#41;, VEC&#40;2,3&#41;, VEC&#40;3,3&#41;, VEC&#40;3,2&#41;, VEC&#40;3,1&#41;, VEC&#40;3,0&#41;, VEC&#40;3,-1&#41;,   /* 3rd ring */
                           VEC&#40;3,-2&#41;, VEC&#40;3,-3&#41;, VEC&#40;2,-3&#41;, VEC&#40;1,-3&#41;, VEC&#40;0,-3&#41;, VEC&#40;-1,-3&#41;, VEC&#40;-2,-3&#41;, VEC&#40;-3,-3&#41;,
                           VEC&#40;-3,-2&#41;, VEC&#40;-3,-1&#41;, VEC&#40;-3,0&#41;, VEC&#40;-3,1&#41;, VEC&#40;-3,2&#41;, VEC&#40;-3,3&#41;, VEC&#40;-2,3&#41;, VEC&#40;-1,3&#41; &#125;;

void
AreaInit ()
&#123; // create area 'bitboards' at program startup
  int d, i;
  for&#40;d=0; d<8; d++) &#123;
    int sqr1 = step&#91;d&#93;;                 // all 1st-ring squares
    int mask = 0;
    for&#40;i=0; i<16; i++) &#123;
      int sqr2 = ringStep&#91;i&#93;;           // all 2nd-ring squares
      int dist = distance&#91;sqr2 - sqr1&#93;;
      if&#40;dist < 2&#41; mask |= 1 << i;      // mark adjacent 2nd-ring squares
    &#125;
    rMask2&#91;d&#93; = mask;
  &#125;
  for&#40;d=0; d<16; d++) &#123;
    int sqr1 = ringStep&#91;d&#93;;             // all 2nd-ring squares
    int64 mask = 0;
    for&#40;i=0; i<40; i++) &#123;
      int sqr2 = ringStep&#91;i&#93;;           // all 2nd- & 3rd-ring squares
      int dist = distance&#91;sqr2 - sqr1&#93;;
      if&#40;dist < 2&#41; mask |= 1LL << i;    // mark squares adjacent to 2nd ring
    &#125;
    rMask3&#91;d&#93; = mask;
  &#125;
&#125;

int
DemonBurns &#40;int sqr, int stm&#41;
&#123; // generate demon moves that burn something
  int h, d, i;
  int   reachable2 = 0; // set of squares reachable by 2nd step
  int64 reachable3 = 0; // set of squares reachable by 3nd step
  enemy = !stm; kingSqr = location&#91;enemy + P_KING&#93;; demonSqr = fromSqr; // parameter bypassing
  // now do area moves, starting with first step, recording reachability of 2nd ring
  for&#40;d=2; d<10; d++) &#123;
    int vec = step&#91;d-2&#93;;
    int s = sqr + vec;                  // try all first-ring squares
    int victim = board&#91;s&#93;;
    if&#40;victim == 1&#41; continue;           // off board
    if&#40;victim > 1&#41; &#123;                    // occupied board square
      if&#40;&#40;victim & 1&#41; == stm&#41; continue; // own piece; cannot move there
    &#125; else reachable2 |= rMask2&#91;d-2&#93;;   // empty, so we can pass through to 2nd ring
    if&#40;GenBurn&#40;s&#41;) return 1;            // King was burned, abort &#40;or move stashed&#41;
    if&#40;d & 3&#41; &#123;                         // we also have a slide in this direction
      int dist = viewDist&#91;sqr&#93;&#91;d-2&#93;;    // how far that extends
      dist -= &#40;board&#91;s&#93; == 1&#41;;          // decrease one if it hits edge cell
      while&#40;dist > 3&#41; &#123;                 // for all squares on it beyond range of area move
        if&#40;GenBurn&#40;vec*dist--)) return 1; // King-burn detected
      &#125;
    &#125;
  &#125;
  // do second step now we know which 2nd-ring squares are reachable
  h = reachable2;
  for&#40;i=0; i<=8; i+=8&#41; &#123;                  // with BSF this could be done single pass
    int todo = h & 0xFF;                  // treat in groups of 8
    while&#40;todo&#41; &#123;
      int b = lowBit&#91;todo&#93;;
      int s = sqr + ringStep&#91;b+i&#93;;        // reachable second-ring squares only
      int victim = board&#91;s&#93;;
      if&#40;victim == 1&#41; continue;           // off board
      if&#40;victim > 1&#41; &#123;                    // occupied board square
        if&#40;&#40;victim & 1&#41; == stm&#41; continue; // own piece; cannot move there
      &#125; else reachable3 |= rMask3&#91;d&#93;;     // empty, so we can continue with 3rd step from there
      if&#40;GenBurn&#40;s&#41;) return 1;            // King was burned, abort &#40;or move stashed&#41;
      todo -= 1 << b;
    &#125;
    h >>= 8;                              // next group of 8
  &#125;
  // do third step now we know which 2nd/3rd-ring squares were reachable in 2 steps
  reachable3 &= ~reachable2;              // remove squares we have already visited from step-3 targets
  for&#40;i=0; i<=32; i+=8&#41; &#123;                 // with BSF this could be done single pass
    int todo = reachable3 & 0xFF;         // treat in groups of 8
    while&#40;todo&#41; &#123;
      int b = lowBit&#91;todo&#93;;
      int s = sqr + ringStep&#91;b+i&#93;;        // newly reachable 2nd- & 3rd-ring squares only
      int victim = board&#91;s&#93;;
      if&#40;victim == 1&#41; continue;           // off board
      if&#40;victim > 1 &&                    // occupied board square
         &#40;victim & 1&#41; == stm&#41; continue;   // own piece; cannot move there
      if&#40;GenBurn&#40;s&#41;) return 1;            // King was burned, abort &#40;or move stashed&#41;
      todo -= 1 << b;
    &#125;
    reachable3 >>= 8;                     // next group of 8
  &#125;
  return 0;                               // Demon burns generated without frying King
&#125;

User avatar
hgm
Posts: 25088
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: The Inferno thread: Incremental Update of Attacks

Post by hgm » Sun Mar 12, 2017 12:56 pm

Incremental Update of Attacks, part I

Now it is time to get to the icing on the cake: incremental update of the attack map. Without this, when the attack map would have to be generated from scratch in every node, it woul just be an expensive way of sorting moves generated by attacker to by-victim (MVV) order.

The attack map was designed to be helpful in its own incremental update: by containing all attacks to a square you know exactly which moves can be discovered by evacuating it. These can then be displaced to the target down-stream, which is easily located through the view-distance in that direction. This is cheap mainly because we do not store information on empty squares, so that we only have to record the discovered attack on the end of the ray, where it hits its new target. Otherwise we would have to access and alter the attack map also for all empty squares along the ray.

This has one drawback, however: when a piece lands on a empty square, we know nothing about it. In particular, we have no ideas which sliding moves pass over it, and how far away the potential sources for such attacks are removes from us in the various directions. So we have to collect all that information, which makes occupying empty squares moderately expensive. This is the price we pay for making updates (and downdates during UnMake!) of the attack map cheap. This trade-off was resolved in the described way based on the idea that most nodes of the tree are QS nodes, in which only captures are searched. And captures never occupy empty squares, they just evacuate squares, and replace a victim by your own piece. Occupying empty squares only occurs on non-captures in the much less numourous nodes of the full-width search. (And possibly on a few Demon burns and check evasions in QS.) So we rather move the cost there.

Unmaking of a move also occupies an empty square, when we put the moving piece back onto its from-square. But in that case we can rely on the information present there when the move was origially made to still be available, both for the attacks and the view distances. This assumes such information would not be destroyed when a move deeper in the tree would put a piece on that square. So we have to save and restore this information. Again we have the choice to do that when the square gets evacuated, or just before it gets re-occupied. We choose here to do it just before it gets occupied, so that it would not have to be done on captures.

Anyway, there must be two different routines for occupying a square, one fornon-captures in MakeMove(), and another, more efficient one for taking back moves in UnMake(). I will call those PlacePiece() and PutBack(), respecively. In this posting we discuss the routines LiftPiece() and PutBack(), which are each other's inverse, PutBack() exactly undoing what an earlier LiftPiece() did to the attack map.

Code: Select all

// Attack map

#define ASIZE &#40;WIDTH*&#40;RANKS+2*RIM&#41;)
#define attacks &#40;rawAttacks + 2*RIM*WIDTH + RIM&#41;

typedef long long int int64;

int64 rawAttacks&#91;2*ASIZE&#93;;

// Format of attack-map elements&#58;

#define A_GENERALS3 &#40;0x70LL << 40&#41; /* jump-attacks by GG/+RG, per piece                 */
#define A_GENERALS2 &#40;0x07LL << 40&#41; /* jump-attacks by VG/+BG, per piece                 */
#define A_GENERALS1 &#40;0xFFLL << 32&#41; /* jump-attacks by BG/+HF and RG/+SE, per piece      */
#define A_SLIDES    &#40;0xFF << 24&#41;   /* 8 bits indicating sliding attacks, per direction  */
#define A_JUMPS     &#40;0xFF << 16&#41;   /* 8 bits indicating 2nd-square jumps, per direction */
#define A_OBLIQUES   0xFFFF        /* off-ray moves, per piece&#58;                         */
#define A_HAWKS     &#40;0x30 << 8&#41;    /* 2 Lion Hawks &#40;LH/+Ln&#41;                             */
#define A_LIONS     &#40;0x0C << 8&#41;    /* 2 Lions &#40;Ln,+Kn&#41;                                  */
#define A_KNIGHTS   &#40;0x3F << 8&#41;    /* 6 Knights-jump attacks &#40;2N, Ln/+Kn, LH/+Ln&#41;       */
#define A_TETRARCH  &#40;0xF0 << 0&#41;    /* 4 ski-slides attacks &#40;4 +CS&#41;                      */
#define A_KNIGHTS   &#40;0x03 << 0&#41;    /* 3 area-moves potential attacks &#40;VG/+BG&#41;           */
#define A_SLIDE     &#40;1 << 24&#41;      /* slide flag for direction 0                        */
#define A_JUMP      &#40;1 << 16&#41;      /* jump flag for direction 0                         */

void
LiftPiece &#40;int sqr&#41;
&#123;
  int piece = board&#91;sqr&#93;; // piece that is lifted
  int f =   SQR2FILE&#40;sqr&#41;;
  int r = 3*SQR2RANK&#40;sqr&#41;;
  burns&#91;f&#93;&#91;stm&#93;   += 020 << r; // increment rank count for this rank in the file and its two neighbors
  burns&#91;f+1&#93;&#91;stm&#93; += 010 << r;
  burns&#91;f-1&#93;&#91;stm&#93; += 040 << r;
  ExtendView&#40;viewDist, sqr&#41;;   // update view-distace of normal pieces
  AddMoves&#40;sqr, piece, -1&#41;;    // removes the moves of the piece itself
  // discovering slider moves
  for&#40;color=0; color<=ASIZE; color+=ASIZE&#41; &#123; // for both colors
    int csqr = sqr + color;                  // element for 'sqr' in attack map for applicable color
    unsigned int att = attacks&#91;csqr&#93;;        // attacks by this color
    int todo = att >> 24;                    // ordinary sliding attacks
    while&#40;todo&#41; &#123;
      int d = lowBit&#91;todo&#93;;                  // direction of next incoming attack
      int dist = viewDist&#91;sqr&#93;.d&#91;d^4&#93;;       // up-stream view
      int vec = step&#91;d&#93;;
      int attacker = board&#91;sqr - dist*vec&#93;;  // attacker must be up-stream obstacle
      int left = ranges&#91;attacker&#93;&#91;d&#93; - dist; // how much of its range is left beyond us
      if&#40;left > 0&#41; &#123;                         // to waste less time on the ubiquitous stepper attacks
        int dist = viewDist&#91;sqr&#93;.d&#91;d&#93;;       // attack reaches beyond us, so might now hit something
        if&#40;left >= dist&#41; &#123;                   // the discovered move reaches the target behind us
          int s = csqr + dnDist*vec;         // new down-stream target
          attacks&#91;s&#93; |= A_SLIDE << d;
        &#125;
      &#125;
      todo -= &#40;1<<d&#41;;
    &#125;
    todo = att & A_TETRARCHS; // get Tetrarch attacks &#40;all in lowest byte&#41;
    while&#40;todo&#41; &#123; // there are Tetrarch attacks &#40;rare, as usually there are no Tetrarchs&#41;
      int b = lowBit&#91;todo&#93;;            // next Tetrarch attack
      int tetrarch = bit2vice&#91;b&#93;;      // get Tetrarch piece-list index
      int s = location&#91;tertarch&#93;;      // square it is on
      int d = direction&#91;sqr - s&#93;;      // direction of the attack &#40;must be a valid one!)
      int dist = viewDist&#91;sqr&#93;.d&#91;d&#93;;   // distance to next obstacle beyond us
      todo -= 1 << b;
      if&#40;&#40;d-2 & 3&#41; == 0&#41; &#123;             // sideway movement &#40;d = 2 or 6&#41;, Tetrarch has limited range
        int dtet = distance&#91;sqr - s&#93;;  // distance to the Tetrarch &#40;must be > 1!)
        if&#40;dist > 3 - dtet&#41; continue;  // out of Tetrarch range
      &#125;
      s = sqr + dist*step&#91;d&#93;;          // location of new target
      attacks&#91;s+color&#93; |= 16 << b;     // extend the attack to down-stream obstacle
    &#125;
    if&#40;level&#91;piece&#93;) &#123; // piece is a jumping general &#40;somewhat expensive, but rare&#41;
      int mask = 1;
      int l;
      for&#40;l=1; l <= level&#91;piece&#93;; l++)
        ExtendView&#40;viewDist + l*DSIZE, sqr&#41;;
      att = attacks&#91;csqr&#93; >> 32; // jumping-slider attacks
      do &#123; // treat in two groups to keep the lowBit&#91;&#93; table small &#40;would not needed with BSF&#41;
        int todo = att & 0xFF; // first level&#58; jumping Bishops and Rooks
        int offs = 0;
        while&#40;todo&#41; &#123;
          int b = lowBit&#91;todo&#93;;
          int attacker = bit2gen&#91;b+offs&#93;;        // piece-list index
          int l = gen2level&#91;attacker&#93;;           // level of this attack
          int s = location&#91;attacker&#93;;            // origin of attack
          int d = direction&#91;sqr - s&#93;;            // direction of attack
          int vec = step&#91;d&#93;;                     // base step in that direction
          int sd = viewDist&#91;s + l*DSIZE&#93;.d&#91;d&#93;;   // unobstructed down-stream distance &#40;from level-l view distances&#41;
          int stop = sqr + sd*vec;               // obstacle capable of stopping it
          int64 bit = &#40;1LL<<32&#41; << b + offs;
          s = sqr;                               // starting at the evacuated square ...
          do &#123;                                   // ... run through all down-stream targets
            s += viewDist&#91;s&#93;.d&#91;d&#93;*vec;           // hop to next target
            attacks&#91;s+color&#93; += bit; 
          &#125; while&#40;s != stop&#41;;                    // until the level-1 blocker is marked
          todo -= 1 << b;
        &#125;
        att >>= 8; offs += 8;
      &#125; while&#40;att&#41;;
    &#125;
  &#125;
&#125;

void
PutBack &#40;int sqr, int piece&#41;
&#123; // Undo a Lift&#40;)
  int f =   SQR2FILE&#40;sqr&#41;;
  int r = 3*SQR2RANK&#40;sqr&#41;;
  burns&#91;f&#93;&#91;stm&#93;   += 020 << r; // increment rank count for this rank in the file and its two neighbors
  burns&#91;f+1&#93;&#91;stm&#93; += 010 << r;
  burns&#91;f-1&#93;&#91;stm&#93; += 040 << r;
  UnExtendView&#40;viewDist, sqr&#41;;    // update view-distace of normal pieces
  // undo discovering of slider moves
  for&#40;color=0; color<=ASIZE; color+=ASIZE&#41; &#123; // for both colors
    unsigned int att = attacks&#91;sqr+color&#93;;   // these were the attacks on the square when we evacuated it
    todo = att >> 24;                        // ray part
    while&#40;todo&#41; &#123;
      int d = lowBit&#91;todo&#93;;                  // direction of incoming attack that might have been extended
      int dist = viewDist&#91;sqr&#93;.d&#91;d&#93;;
      int vec = step&#91;d&#93;;
      int s = sqr + dist*vec;                // down-stream obstacle
      attacks&#91;s+color&#93; &= ~&#40;A_SLIDE << d&#41;;   // in any case this attack no longer hits that &#40;perhaps it never did&#41;
      todo -= &#40;1<<d&#41;;
    &#125;
    // Tetrarch misery
    todo = att & A_TETRARCHS;
    while&#40;todo&#41; &#123; // there were Tetrarch attacks, undo their extension
      int b = lowBit&#91;todo&#93;;           // next Tetrarch attack
      int tetrarch = bit2vice&#91;b&#93;;     // get Tetrarch piece-list index
      int s = location&#91;tertarch&#93;;     // square it is on
      int d = direction&#91;sqr - s&#93;;     // direction of the attack &#40;must be a valid one!)
      int dist = viewDist&#91;sqr&#93;.d&#91;d&#93;;  // distance to next obstacle in that direction beyond us
      s = sqr + dist*step&#91;d&#93;;         // down-stream obstacle
      attacks&#91;s_color&#93; &= ~&#40;16 << b&#41;; // in any case the attack no longer hits that
      todo -= 1<<b;
    &#125;
    if&#40;level&#91;piece&#93;) &#123; // piece is a jumping general &#40;somewhat expensive, but rare&#41;
      int mask = 1;
      int l;
      for&#40;l=1; l <= level&#91;piece&#93;; l++)
        UnExtendView&#40;viewDist + l*DSIZE, sqr&#41;;
      att = attacks&#91;csqr&#93; >> 32; // jumping-slider attacks
      do &#123; // treat in two groups to keep the lowBit&#91;&#93; table small &#40;would not needed with BSF&#41;
        int todo = att & 0xFF; // first level&#58; jumping Bishops and Rooks
        int offs = 0;
        while&#40;todo&#41; &#123;
          int b = lowBit&#91;todo&#93;;
          int attacker = bit2gen&#91;b+offs&#93;;        // piece-list index
          int l = gen2level&#91;attacker&#93;;           // level of this attack
          int s = location&#91;attacker&#93;;            // origin of attack
          int d = direction&#91;sqr - s&#93;;            // direction of attack
          int vec = step&#91;d&#93;;                     // base step in that direction
          int sd = viewDist&#91;s + l*DSIZE&#93;.d&#91;d&#93;;   // unobstructed down-stream distance &#40;from level-l view distances&#41;
          int stop = sqr + sd*vec;               // obstacle capable of stopping it
          int64 bit = &#40;1LL<<32&#41; << b + offs;
          s = sqr;                               // starting at the evacuated square ...
          do &#123;                                   // ... run through all down-stream targets
            s += viewDist&#91;s&#93;.d&#91;d&#93;*vec;           // hop to next target
            attacks&#91;s+color&#93; -= bit; 
          &#125; while&#40;s != stop&#41;;                    // until the level-1 blocker is marked
          todo -= 1 << b;
        &#125;
        att >>= 8; offs += 8;
      &#125; while&#40;att&#41;;
    &#125;
  &#125;
  AddMoves&#40;sqr, piece, 1&#41;; // add back moves of piece itself
&#125;

The basic idea of this code is quite simple, but the presence of so many different attacks (different levels of jumping sliders, Tetrarchs) requires it to be applied to may different sets of attacks that could all coexist, and just need a little bit of different treatment than the others.

User avatar
hgm
Posts: 25088
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

The Inferno thread: Incremental Update of Attacks

Post by hgm » Mon Mar 13, 2017 11:03 am

Incremental update of attacks, part II

Now we get to the difficult part, when a non-capture occupies a previously empty square. As we had seen in one of the early postings here, updating the view distances requires four ray scans, and some occupant hopping for the higher levels. But we also lack information on what moves attack the newly occupied square (which might have to be blocked if they are sliding moves with a range extending beyond the square). This will have to be reconstructed from scratch too.

So we will have to look in all 8 directions, to test the nearest neighbor there (to which the freshly updated view distance directly points us) for having moves (of sufficient range) in our direction, to add them to the attack-map entry for the freshly occupied square we are building from scratch. And possibly remove attacks on the target in the opposite direction, which is now blocked. And we would have to do the same for Tetrarch attacks, when there is a Tetrarch just behind that nearest neighbor, jumping over it to attack us. (In addition, the nearest piece could be a Tetrarch that attacks us through its ski-slide, rather than a normal slider, so that its attack would have to be flagged by another bit in the attack map. If the nearest neighbor is a jumping sliders its attack would also have to be indicated by a different bit.)

Attacks by direct leaps to the 2nd square, or potential area-move attacks, are supposed to be always indicated in the attack map, even for empty squares. So these should already be there, and we have to do nothing for them (other than keeping them) when occupying the square.

All this is pretty straightforward, and the Tetrarch drudgery can all be put in an if clause that is virtually never executed, (as Tetrarchs are almost never present on the board). The jumping-slider attacks pose a nastier problem, though. They need not come from a neighbor, but can come from behind many other pieces, flying over those. Even if the piece we place is not a jumping slider itself (so that it would never block any such moves), it still exposes itself to such over-flying attacks, which should be recorded in the attack map. We can look in each direction if there are such attacks on the piece there. But because jumping-slider attacks are flagged per piece, rather than per direction, there is no quick way to see where they came from, and if they indeed were passing over the freshly occuppied square. A nearest neighbor could have many jumping-slider attacks on it, none of those passing over the current square. It would be time-wasting to trace the source of all those attacks. (This would go through the chain attack bit -> bit number -> piece -> location -> attack direction.)

We could try to be a bit more selective in what jumping sliders to check. If a jumping slide is attacking the freshly occupied square, it would attack an obstacle down-stream of it in some direction, as all jumping slides have infinite range. We are checking the attacks on all nearest neighbors anyway, for the purpose of blocking normal sliding attacks on them, and we could check for recorded attacks by jumping sliders as well. If no such attacks exist, we don't have to do anything. And it is easy to restrict the tested sliding attacks to pieces that can indeed move along the direction of that nearest neighbor.

The nearest neighbor on our opposite side of the one receiving the jumping-slider attack passing over us, should either receive it too, or be the source of it. As we already do check all our nearest neighbors for having sliding moves towards us (and will be forced to decide if we will put those in the map as normal slides per direction, or jumping slice per source piece), we only need to address the former case. So we can AND the attack-map elements of opposite neighbors (and there are only 4 such pairs!), and only jumping-sliders that attack both would survive that.

Having a jumping-slide attack on both antiposed is still not iron-clad proof that it goes over the intermediate squares, however: a Jumping Queen could attack up to three pieces on a ray along which it can move, from a location not on that ray. For jumping Rooks and Bishops this is not possible: they only have one other direction of attack, perpedicular to the attack ray, which can only intersect it in a single square.

This problem could be solved by indicating attacks by a given Jumping Queen through two different bits, depending on the attack being orthogonal or diagonal. Or, in other words, treat a Jumping Queen as if it is a separate Jumping Rook and a Jumping Bishop, which happen to sit on the same square. Squares on the ray we are investigating attacked by the same Jumping Queen would then be indicated by different bits, and disappear in the ANDing of those attacks. Or, when (say) two different orthogonal moves of the same Jumping Queen would attack both our nearest neighbors on a diagonal (so they survive the ANDing), they would be ignored because they were not diagonal moves, and we are examining a diagonal.

Yet another problem occurs when the placed piece is a jumping slider itself, so that it will block jumping slides that went over the square before. But once we established which jumping slides do attack the placed piece, we are back to the situation of the PutBack() case, where we did have valid set of attacks on the square. So we can use the same method of removing such attacks that we block from all down-stream targets upto its next blocker.

Code: Select all

// Bit assignment in attack-map elements&#58;

#define A_GEN3ORTHO &#40;0x38LL << 44&#41; /* jump-attacks by GG/+RG, per piece &#40;orthogonal&#41;    */
#define A_GEN3DIAG  &#40;0x07LL << 44&#41; /* jump-attacks by GG/+RG, per piece &#40;diagonal&#41;      */
#define A_GENERALS3 &#40;0x3FLL << 44&#41; /* jump-attacks by GG/+RG, 2 per piece &#40;orth/diag&#41;   */
#define A_GENERALS2 &#40;0x0ELL << 40&#41; /* jump-attacks by VG/+BG, per piece                 */
#define A_GEN1ORTHO &#40;0xF0LL << 32&#41; /* jump-attacks by RG/+SE, per piece &#40;orthogonal&#41;    */
#define A_GEN1DIAG  &#40;0x0FLL << 32&#41; /* jump-attacks by BG/+HF, per piece &#40;diagonal&#41;      */
#define A_GENERALS1 &#40;0xFFLL << 32&#41; /* jump-attacks by BG/+HF and RG/+SE, per piece      */
#define A_SLIDES    &#40;0xFF << 24&#41;   /* 8 bits indicating sliding attacks, per direction  */
#define A_JUMPS     &#40;0xFF << 16&#41;   /* 8 bits indicating 2nd-square jumps, per direction */
#define A_OBLIQUES   0xFFFF        /* off-ray moves, per piece&#58;                         */
#define A_HAWKS     &#40;0x30 << 8&#41;    /* 2 Lion Hawks &#40;LH/+Ln&#41;                             */
#define A_LIONS     &#40;0x0C << 8&#41;    /* 2 Lions &#40;Ln,+Kn&#41;                                  */
#define A_KNIGHTS   &#40;0x3F << 8&#41;    /* 6 Knights-jump attacks &#40;2N, Ln/+Kn, LH/+Ln&#41;       */
#define A_TETRARCH  &#40;0xF0 << 0&#41;    /* 4 ski-slides attacks &#40;4 +CS&#41;                      */
#define A_VICE      &#40;0x03 << 0&#41;    /* 3 area-moves potential attacks &#40;VG/+BG&#41;           */
#define A_SLIDE     &#40;1 << 24&#41;      /* slide flag for direction 0                        */
#define A_JUMP      &#40;1 << 16&#41;      /* jump flag for direction 0                         */
#define A_LEAPS     &#40;A_JUMPS | A_KNIGHTS | A_VICE&#41;
#define A_ORTH      &#40;A_GEN3ORTHO | A_GEN1ORTHO&#41;
#define A_DIAG      &#40;A_GEN3DIAG | A_GENERALS2 | A_GEN1DIAG&#41;

// Attack-map updating
// The routines Lift, PutBack and Drop deal with square evacuation, undoing of it, and occupying an empty square, respectively

void
PlacePiece &#40;int sqr, int piece, int side&#41;
&#123;
  static int64 jumpType&#91;&#93; = &#123; A_ORTO, A_DIAG &#125;; // masks for orthogonal and diagonal jumping-slider attacks
  int blockLevel = level&#91;piece&#93;;
  int f =   SQR2FILE&#40;sqr&#41;;
  int r = 3*SQR2RANK&#40;sqr&#41;;
  burns&#91;f&#93;&#91;stm&#93;   += 020 << r; // increment rank count for this rank in the file and its two neighbors
  burns&#91;f+1&#93;&#91;stm&#93; += 010 << r;
  burns&#91;f-1&#93;&#91;stm&#93; += 040 << r;
  BlockView&#40;sqr, blockLevel&#41;; // update view-distances
  // discovering slider moves
  for&#40;color=0; color<=ASIZE; color+=ASIZE&#41; &#123;      // both colors
    int csqr = sqr + color;
    uint64 att = attacks&#91;csqr&#93; & A_LEAPS;         // leaper attacks are already OK
    for&#40;d=0; d<8; d++) &#123; // all 8 directions
      int vec = step&#91;d&#93;;
      int dnDist = viewDist&#91;sqr&#93;&#91;d&#93;;
      int64 slide = A_SLIDE << d;                    // bit indicating normal slide in this direction
      int s = sqr + dnDist*vec;
      int upDdist = viewDist&#91;sqr&#93;&#91;d^4&#93;;
      int t = sqr - upDist*vec;
      int attacker = board&#91;t&#93;;                       // up-stream piece
      int64 dnAttacks = attacks&#91;s+color&#93;;            // sliding attacks on down-stream neighbor, which must have passed us
      att |= dnAttacks & slide;                      // so they now attack us
      if&#40;nrTetrarchs&#91;color&#93;) &#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;type&#91;lurker&#93; == T_TETRARCH&#41; &#123;             // it is a Tetrarch that jumps over the up-stream piece
          if&#40;d & 1 ||                                // diagonal; Tetrarchs have unlimited range
             d & 2 && upDist < 3&#41; &#123;                  // sideway; Tetrarchs have range 3 here
            int b = 1 << lurker - tetrarchs&#91;color&#93;;  // bit representing this Tetrarch
            attacks&#91;s+color&#93; &= ~b;                  // the attack on down-stream is blocked
            att |= b;                                // as it now hits us
          &#125;
        &#125;
      &#125;
      if&#40;dnAttacks & slide&#41;                             // we blocked a normal slide that reached down-stream
        attacks&#91;s+color&#93; = dnAttacks - slide;           // remove it down-stream
      else &#123;                                            // we could be hit by a slider that did not reach down-stream
        int range = ranges&#91;attacker&#93;&#91;d&#93;;                // how far it moves in our direction
        if&#40;type&#91;attacker&#93; == T_TETRARCH&#41; &#123;              // the up-stream piece is a Tetrarch &#40;rare&#41;
          if&#40;upDist > 1 &&                              // it does not jump over us
             d & 1 ||
             d & 2 && upDist < 3&#41; &#123;
            int b = 1 << attacker - tetrarchs&#91;color&#93;;   // bit indicating this Tetrarch in attack map
            att |= b;                                   // record attack on current piece
            attacks&#91;s+color&#93; &= ~b;                     // and remove it from down-stream &#40;if there&#41;
          &#125;                                             // &#40;for the purpose of the normal slide the Tetrarch has range 1&#41;
        &#125; else if&#40;range > X&#41; &#123;                          // attacker is jumping slider
          att |= gen2bit&#91;attacker&#93; & jumpType&#91;d & 1&#93;;   // record attack by jumping slider &#40;for the current direction&#41;
        &#125; else if&#40;range >= dist&#41; &#123;                      // move reaches us
          att += slide;                                 // add it to our attack map
          attacks&#91;s+color&#93; &= ~slide;                   // and remove it down-stream
        &#125;
      &#125;
      if&#40;d < 4&#41; &#123; // only four direction pairs
        int64 upAttacks = attacks&#91;t+color&#93;;             // attacks on up-stream obstruction
        upAttacks &= jumpType&#91;d & 1&#93;;                   // jump-slide attacks in current direction set &#40;orth or diag&#41;
        upAttacks &= dnAttacks;                         // keep those that also hit down-stream obstruction
        att |= dnAttacks;                               // these must also attack us
      &#125;
    &#125; // next direction
    attacks&#91;csqr&#93; = att;
    if&#40;level&#91;piece&#93;) &#123; // piece is a jumping slider &#40;somewhat expensive, but rare&#41;
      int mask = 1;
      int l;
      if&#40;color == 0&#41; for&#40;l=1; l <= level&#91;piece&#93;; l++)
        BlockView&#40;viewDist + l*DSIZE, sqr&#41;;  // update affected high-level views
      att >>= 32; // jumping-slider part of just-determined attacks to 'sqr'
      do &#123; // treat in two groups to keep the lowBit&#91;&#93; table small &#40;would not be needed with BSF&#41;
        int todo = att & 0x1FF;  // first level&#58; jumping Bishops and Rooks
        int offs = 0;
        while&#40;todo&#41; &#123;
          int b = lowBit&#91;todo&#93;;
          int attacker = bit2gen&#91;b+offs&#93;;        // piece-list index
          int l = gen2level&#91;attacker&#93;;           // level of this attack
          int s = location&#91;attacker&#93;;            // origin of attack
          int d = direction&#91;sqr - s&#93;;            // direction of attack
          int vec = step&#91;d&#93;;                     // base step in that direction
          int sd = viewDist&#91;s + l*DSIZE&#93;.d&#91;d&#93;;   // unobstructed down-stream distance &#40;from level-l view distances&#41;
          int stop = sqr + sd*vec;               // obstruction capable of stopping it
          int64 bit = &#40;1LL<<32&#41; << b + offs;
          s = sqr;                               // starting at the evacuated square ...
          do &#123;                                   // ... run through all down-stream targets
            s += viewDist&#91;s&#93;.d&#91;d&#93;*vec;           // hop to next target
            attacks&#91;s+color&#93; -= bit; 
          &#125; while&#40;s != stop&#41;;                    // until the level-1 blocker is marked
          todo -= 1 << b;
        &#125;
        att >>= 9; offs += 9;
      &#125; while&#40;att&#41;;
    &#125;
  &#125; // other color
  AddMoves&#40;piece, side, 1&#41;;
&#125;
Note that the bit-assignment of the jumping sliders changed a bit compared to the previous posting, so that I included it again: the level-1 (Jumping Rook and Bishop) and level-3 (Jumping Queen) flags are now split into diagonal and orthogonal attacks. This brings up their total to 17, so that they have to be extracted as two groups of nine rather than eight in the loop that blocks the corresponding attacks down-stream. That should also be done in the LiftPiece() and PutBack() routines. In fact this code of this loop is now exactly the same as in PutBack, and should perhaps be located in a separate sub-routine that both can call.

A consequence of having separate flags for Jumping Queen orthogonal and diagonal attacks means that when we generate attacks of a jumping slider appearing somewhere (in AddMoves()) we cannot simply look up the bit corresponding to its attacks (as there could be two), but will have to make that depend on the direction of the attack. To revisit that code:

Code: Select all

     if&#40;range > X&#41; &#123; // this indicates the move is a jumping slide &#40;rare&#41;
       int64 bit = gen2bit&#91;piece&#93;;  // bit representing this jumping slider in attack map
       int l = piece2level&#91;piece&#93;;  // level of opacity
       int stop = sqr + viewDist&#91;sqr + l*DSIZE&#93;.d&#91;d&#93;*vec;
       bit <<= range - Y;         // adjust Jumping Q orthogonal moves, which have range = Y + 3 <----------- new
       int s = sqr;
       bit *= sgn;                  // set up for addition or removal
       do &#123; // flag jumping attacks on all down-stream pieces
         s += viewDist&#91;s&#93;.d&#91;d&#93;*vec;
         attacks&#91;s+color&#93; += bit;
       &#125; while&#40;s != stop&#41;;
     &#125; else if&#40;range >= dist&#41;       // target is within range
This can be done by defining the range of the orthogonal moves of Jumping Queen in the move-description table to 40 (where normal slides have X=36, and other jumping slides Y=37). Note that all values larger than the board size in principle are equivalent here, and can be used to indicate such distinctions. The gen2bit[] table then lists the bit for the three Jumping Queens their diagonal moves, and the orthogonal moves use a bit 3 places higher up in the attack set.

User avatar
hgm
Posts: 25088
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

The Inferno thread: Incremental Update of Attacks

Post by hgm » Mon Mar 13, 2017 7:07 pm

Incremental Update of Attacks, part III

The idea to locate the code for blocking slider moves that PlacePiece() and PutBack have in common in a separate routine, which I coined above, seems a useful one. With minimal overhead (one extra multiplication in the inner loop), the routine can even be used to discover these moves as well.

Code: Select all

void
LevelChange&#40;int sqr, int lowLevel, int highLevel, int sgn&#41;
&#123; // discover or block &#40;for sgn = -1&#41; jumping slides over 'sqr' caused by level change of the occupant
  static int levelMask&#91;&#93; = &#123; 0, A_GENERALS1>>32, &#40;A_GENERALS1|A_GENERALS2&#41;>>32, &#40;A_GENERALS1|A_GENERALS2|A_GENERALS3&#41;>>32 &#125;;
  int color;
  for&#40;color=0; color<= ASIZE; color+=ASIZE&#41; &#123;
    int csqr = sqr + color;
    unsigned int att = attacks&#91;csqr&#93; >> 32;                 // jumping-sliders part of attacks to 'sqr'
    int mask = levelMask&#91;highLevel&#93; & ~levelMask&#91;lowLevel&#93;; // jumping attacks that can be discovered or blocked
    att &= mask;                                            // jumping attacks that actually are affected
    do &#123; // treat in two groups to keep the lowBit&#91;&#93; table small &#40;would not be needed with BSF&#41;
      int todo = att & 0x1FF;  // first level&#58; jumping Bishops and Rooks
      int offs = 0;
      while&#40;todo&#41; &#123;
        int b = lowBit&#91;todo&#93;;
        int attacker = bit2gen&#91;b+offs&#93;;        // piece-list index
        int l = gen2level&#91;attacker&#93;;           // level of this attack
        int s = location&#91;attacker&#93;;            // origin of attack
        int d = direction&#91;sqr - s&#93;;            // direction of attack
        int vec = step&#91;d&#93;;                     // base step in that direction
        int sd = viewDist&#91;s + l*DSIZE&#93;.d&#91;d&#93;;   // unobstructed down-stream distance &#40;from level-l view distances&#41;
        int stop = sqr + sd*vec;               // obstruction capable of stopping it
        int64 bit = &#40;1LL<<32&#41; << b + offs;     // bit representing this attacker
        b *= sgn;
        s = sqr;                               // starting at the evacuated square ...
        do &#123;                                   // ... run through all down-stream targets
          s += viewDist&#91;s&#93;.d&#91;d&#93;*vec;           // hop to next target
          attacks&#91;s+color&#93; += bit;             // and apply change there
        &#125; while&#40;s != stop&#41;;                    // until the level-l blocker has been marked
        todo -= 1 << b;
      &#125;
      att >>= 9; offs += 9;
    &#125; while&#40;att&#41;;
  &#125; // other color
&#125;
With his routine the "if(level[piece])" (I really should have written "if(gen2level[piece])" there) parts of LiftPiece(), PutBack() and PlacePiece() can be replaced by code like

Code: Select all

  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--)
      BlockView&#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;
at the end of the routines.

The routine LevelChange() can even be used for a task we so far did not mention: when a capture takes place, one piece is replaced by another on the capture square. Normally this would not lead to blocking or discovering of any moves, but when jumping sliders of different levels are involved, it can. If the new occupant of the square has a higher level, moves upto that level that used to pass over the square would be blocked. And when the new occupant has a lower level, attacks to that square of the levels that lie in between are discovered. This could of course be achieved by first doing a LiftPiece() of the old piece, and then a PutBack() of the new one. But that would do a lot of unnecessary work, first discovering moves that then have to be blocked again.

For this reason the LevelChange() routine accepts two levels as argument, and then only acts on the attacks on the levels which lie in between. In LiftPiece() and PutBack() it can then be used with the lower level set to 0. But in a new routine, ReplacePiece(), it can also be used when one jumping slider replaces another. Note that we expect to use this routine a lot, as most nodes will be QS nodes that search captures only. To perform such moves, we need to do a LiftPiece() on the from-square, and a ReplacePiece() on the to-square. And to'downdate' the attack map on UnMake, we would need the reverse ReplacePiece(), plus a PutBack(). Also note that if the level of the captured piece is the same as that of the attacker, which is the common case as more than 90% of the pieces are not jumping sliders and all have level 0, the discover-or-block part of ReplacePiece() is no-op. (Only replacing the moves of one piece by that of the other needs to be done, then. And this cannot be avoided, as the pieces are of opposite color, so that their moves will have to go to different halves of the attack map.)

Code: Select all

void
ReplacePiece &#40;int sqr, int oldPiece, int newPiece&#41;
&#123; // replace one piece by another on capture square. 'undo' indicates it is for UnMake
  int oldLevel = &#40;oldPiece < CRAWLERS&#41;; // could be jumping slider
  int newLevel = &#40;newPiece < CRAWLERS&#41;;
  AddMoves&#40;sqr, oldPiece, -1&#41;; // remove moves of old piece
  AddMoves&#40;sqr, newPiece, 1&#41;;  // add moves of new piece
  if&#40;oldlevel | newLevel&#41; &#123;    // jumping sliders involved
    if&#40;oldLevel&#41; oldLevel = gen2level&#91;oldPiece&#93;; // get their true levels
    if&#40;newLevel&#41; newLevel = gen2level&#91;newPiece&#93;;
    if&#40;oldLevel != newLevel&#41; &#123; // if same level, nothing to change
      if&#40;oldLevel > newLevel&#41; &#123;
        int l;
        for&#40;l=oldLevel; l>newLevel; l--) &#123;
          if&#40;undo&#41; UnextendView&#40;viewDist + l*DSIZE, sqr&#41;; // in UnMake we can rely on viewDist&#91;&#93;
          else BlockView&#40;viewDist + l*DSIZE, sqr&#41;;        // but in MakeMove not
        &#125;
        LevelChange&#40;sqr, newLevel, oldLevel, -1&#41;; // block some moves
      &#125; else &#123;
        int l;
        for&#40;l=newLevel; l>oldLevel; l--) ExtendView&#40;viewDist + l*DSIZE, sqr&#41;;
        LevelChange&#40;sqr, oldLevel, newLevel, 1&#41;;  // discover some moves
      &#125;
    &#125;
  &#125;
&#125;
(A short remark: because each side starts with 78 pieces of which 72 are promotable, the piece list is 2x150 pieces long, which is not negligible. In order to not waste too much space on all kind of infos about the pieces that the bulk of the ordinary pieces would never have (such as their 'level' of jumping slide attacks, or which bits in the attack map are used to represent them), we only keep such infos on pieces at the start of the list, with index < CRAWLERS. The common case would be that this test fails, and comparing with a small integer constant is about the cheapest test you can imagine. The jumping sliders are amongst the most valuable pieces, and since the piecelist is sorted in descending order, they will all be in near the start of the piece list. Only when the piece belongs in that section of the list further info will be sought to confirm the piece indeed satisfies the criteria we were looking for, and acquire info on it required for the task at hand.)

User avatar
hgm
Posts: 25088
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

The Inferno thread: Incremental Update of Attacks

Post by hgm » Mon Mar 13, 2017 10:22 pm

Incremental Update of Attacks, final remarks

Stepper Attacks

I am still in doubt whether it would be beneficial to treat captures to adjacent squares differently. Like the jumps to the 2nd square, such moves are unblockable. For the jumps I adopted the strategy to always put them in the map, even when they hit empty squares. Because so few pieces have such moves, this cannot be very expensive. And it saves you the trouble of 'feeling around' for such attacks every time you land a piece on an empty square, which you would have to do for all pieces you move if these attacks were not already in the map.

For attacks on adjacent squares the stats are a bit different: almost all pieces have at least some of those, and many pieces have nearly all. Because you have to test for sliding attacks in all directions, you would find adjacent attackers anyway, when landing on an empty square, so this is no extra work. Setting attack flags in all surrounding empty squares in directions you can move in is extra work.

There still could be some benefit in this if you only did it for pieces with range 1. This would reduce the number of pieces you would have to do it for by a sizable factor (as most moves have larger range). You would have to test for each direction if the range was 1 in order to know when to do it, but in that case you would not have to retrieve the view distance and compare it to the range to test if you hit a distant target. Once the range is determined to be 1, you can unconditionally write the attack. So it could be a wash, cost-wise.

And the advantage would be that every time you land on or evacuate a square on which there are such range-1 attacks, you would not have to make any attempt to discover or block them on down-stream targets. As this discovering of attacks is done through bit extraction of their directions from the attack set, you could just ANDNOT the set of range-1 attacks (one bit per direction) with the normal sliding attacks (as used now), to eliminate all moves with range 1 from them. Your pieces are very often protected by your own steppers and each time you move such a piece you would save work on futile attempts to 'discover' the stepper moves. So there seems some merit in this. But not enough to bother with it now.

Mobility

A second remark is that mobility can be cheaply calculated incrementally as a side effect of the attack-map update: you can keep track of the number of moves of every piece in the piece list. Each time you discover or block a slider move, you can adjust the move count of the source piece accordingly. In addition you could adjust the total mobility with the mutation of the number of moves multiplied by the piece's mobility weight.

When a piece moves to a new location, you could simply subtract its old contribution to total mobility, as its number of moves was known. And when you generate the attacks from the new location, you could count those, store it with the piece, and add the weighted number to the total mobility.

Mobility also changes by occupying targets of leaper moves by own pieces, so when occupying or evacuating a target square of such an attack (2nd-square jump) you could add or subtract a move to the source piece of this attack. (note that mobility loss by leaper moves falling off board can simply be taken care of in the piece-square tables.) Currently such attacks are ignored on the attack-map update (they just stay there), so this does represent some extra work in testing for their presence. (Few pieces have such moves, so usually they would not be there, so that after the test you would not have to do anything.)

But all in all it seems pretty cheap and easy. I will keep this in mind once I get to the more subtle evaluation terms. For now my purpose is to get a program that does not blunder away material (or get mated).

User avatar
hgm
Posts: 25088
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: The Inferno thread: MakeMove / UnMake

Post by hgm » Tue Mar 14, 2017 12:17 pm

Search: Making Moves

Now that all support functions for incremetally updating the attack map (and associated view-distances and burn locations), we can get an idea how MakeMove() should look. Apart from the attack-map updates, this is basically a quite normal mailbox (with piece-list) MakeMove(), which updates both piece list and board square for every mutation.

Several issues complicate this in Tenjiku Shogi, though:
1) (Almost) all pieces can promote, to a single new type. (No promotion choice other than to do it or not.) As the piece list is supposed to be ordered by victim value, the promoted versions have their own slots reserved for them in the list, initially marked as absent, to avoid we would have to move stuff to insert them. On promotion the base piece gets marked as absent, and the promoted version is activated in the piece list (and put on the board).
2) Pieces can 'evaporate', when they land next to an enemy Fire Demon. This is equivalent to 'promotion' to an empty square. We suppose this is indicated by a flag in the move encoding (M_BURNED).
3) Fire-Demon moves can burn all enemy neighbors. This is indicated in the move encoding by a flag M_BURN. All the burned neighbors have to be remembered to put them back during UnMake(). There can be up to 7 of those. (Because the Fire Demon cannot jump, at least one square around its new location must be empty to reach it.)
4) Some pieces have e.p.-capture capability in addition to a normal capture, on a square that is not implied by their final destination. These need special encoding, to indicate two squares in the space of one. MakeMove have to decode that, and can remember the extra victim as a burn victim.
5) These pieces also can end on the square they started, while taking out the e.p. victim ('rifle capture'). They must not think they capture themselves in that case!

The code below handles all these rare events. The most complex part is where it decides what is the most efficient way to update the attack map for the mutation on the target square, which can be an occupation (non-capture), a no-op (non-capture landing next to a Demon), an evacuation (a capture landing next to a Demon) or a replacement (a normal capture).

Code: Select all

// Move encoding

#define SQSIZE    10                  /* ample space */
#define SQUARE    (&#40;1<<SQSIZE&#41; - 1&#41;
#define M_FROMSQR &#40;SQUARE << SQSIZE&#41;
#define M_TOSQR   SQUARE
#define M_PROMOTE &#40;1 << 2*SQSIZE&#41;
#define M_BURN    &#40;1 << 2*SQSIZE+1&#41;
#define M_BURNED  &#40;1 << 2*SQSIZE+2&#41;
#define M_SPECIAL &#40;SQUARE - 63&#41;       /* 64 highest codes used for multi-leg */

typedef struct &#123;
  int fromSqr;
  int toSqr;
  int piece;         // piece removed from from-square
  int promo;         // piece appearing on to-square
  int victim;        // replacement victim
  int burns;         // number of adjacent victims
  int burnVictim&#91;7&#93;; // adjacent victims
  int burnSqr&#91;7&#93;;    // location of adjacent victims
  int gain;          // value of all material captured
  int64 keyChange;   // hash key
&#125; UndoInfo;

int leg1&#91;64&#93;;  /* first step of 2-leg move    */
int leg2&#91;64&#93;;  /* final square fof 2-leg move */

int
MakeMove &#40;UndoInfo *u, int move, int stm&#41;
&#123;
  int rifle;
  u->gain = 0;
  u->keyChange = 0;
  u->fromSqr = move >> SQSIZE & SQUARE;
  u->toSqr   = move & SQUARE;
  if&#40;u->toSqr >= M_SPECIAL&#41; &#123; // multi-leg move; decode it &#40;rare&#41;
    u->burnSqr&#91;0&#93; = u->fromSqr + leg1&#91;u->toSqr - SPECIAL&#93;;
    u->toSqr      = u->fromSqr + leg2&#91;u->toSqr - SPECIAL&#93;;
    u->burned = 1; // one extra &#40;e.p.) victim
    u->burnVictim&#91;0&#93; = board&#91;u->burnSqr&#91;0&#93;;  // remember it
    u->gain += pieceValue&#91;u->burnVictim&#91;0&#93;&#93;; // accumulate its value
    u->keyChange = ZOBRIST&#40;u->burnVictim&#91;0&#93;, u->burnSqr&#91;0&#93;);
    LiftPiece&#40;u->burnSqr&#91;0&#93;);                // update attacks &#40;e.p. victim -> empty&#41;
    board&#91;u->burnSqr&#91;0&#93;&#93; = 0;                // remove it from the board
    location&#91;burnVictim&#91;0&#93;&#93; = CAPTURED;      // and from the piece list
  &#125; else if&#40;move & M_BURN&#41; &#123; // burn neighbors &#40;rare&#41;. &#40;multi-leg moves are never burns!)
    int d;
    u->burned = 0;
    for&#40;d=0; d<8; d++) &#123; // burn all adjacent enemies
      int s = u->toSqr + step&#91;d&#93;;
      int bv = board&#91;s&#93;;
      if&#40;bv < 2 || &#40;bv & 1&#41; == stm&#41; continue; // empty, edge guard or own piece
      u->burnVictim&#91;u->burned&#93; = bv;          // remember enemy on burn stack
      u->burnSqr&#91;u->burned++&#93; = s;
      u->gain += pieceValue&#91;bv&#93;;              // accumulate its value
      u->keyChange ^= ZOBRIST&#40;bv, s&#41;;         // hash-key update for disappearance of burn victim
      LiftPiece&#40;s&#41;;                           // update attack map &#40;burn victim -> empty&#41;
      board&#91;s&#93; = 0;                           // remove it from board
      location&#91;bv&#93; = CAPTURED;                // and from piece list
    &#125;
  &#125;
  // remove piece from old location
  rifle = &#40;u->fromSqr == u->toSqr&#41;;              // rifle captures
  u->piece = u->promo = board&#91;u->fromSqr&#93;;       // first remember it &#40;and assume it does not promote&#41;
  u->keyChange ^= ZOBRIST&#40;u->piece, u->fromSqr&#41;; // hash-key update for picking up piece
  if&#40;!rifle&#41; LiftPiece&#40;u->fromSqr&#41;;              // update attack map &#40;piece -> empty&#41;, if not rifle capture
  board&#91;u->fromSqr&#93; = 0;                         // remove it from board
                                                 // &#40;piece list will be updated later, depending on promotion&#41;
  // remove the replacement victim
  u->victim = board&#91;u->toSqr&#93;;                   // remember victim &#40;can be empty square&#41;
  u->gain += pieceValue&#91;u->victim&#93;;              // accumulate its value
  u->keyChange ^= ZOBRIST&#40;u->victim, u->toSqr&#41;;  // hash-key update for disappearence of victim
                                                 // on the board it will be overwritten later
  location&#91;u->victim&#93; = CAPTURED;                // remove it from piece list
  // put piece in new location &#40;or its promoted version, or evaporate the piece&#41;
  if&#40;move & M_BURNED&#41; &#123; // piece evaporates &#40;because of adjacent FD&#41; &#40;rare&#41;
    u->promo = 0;       // promote to empty square! &#40;so UnMake knows&#41;
    if&#40;u->victim&#41; LiftPiece&#40;u->toSqr&#41;; // update attack map &#40;victim -> empty&#41;
    board&#91;u->toSqr&#93; = 0;               // remove victim from board
    location&#91;u->piece&#93; = CAPTURED;     // and piece from piece list
    u->gain -= pieceValue&#91;u->piece&#93;;   // and accumulate its loss
  &#125; else &#123; // normal move; something will appear on the to-square
    if&#40;move & M_PROMOTE&#41; &#123;                             // move is promotion &#40;medium rare&#41;
      u->promo = promote&#91;u->piece&#93;;                    // see what it promotes to
      location&#91;u->piece&#93; = CAPTURED;                   // mark base piece as absent in piece list
      u-gain += pieceValue&#91;u->promo&#93; - pieceValue&#91;u->piece&#93;; // accumulate promotion gain
    &#125;
    if&#40;u->victim&#41; &#123;                                    // move is capture
      ReplacePiece&#40;u->toSqr, u->victim, u->promo, 0&#41;;  // update attack map &#40;victim -> promo&#41;
    &#125; else &#123;                                           // move is non-capture &#40;or rifle capture!)
      if&#40;rifle&#41; &#123;                                      // was rifle capture &#40;rare&#41;
        if&#40;u->promo != u->piece&#41;                       // that involved promotion &#40;otherwise no-op&#41;
          ReplacePiece&#40;u->fromSqr, u->piece, u->promo&#41;;// promoted replaces base piece
      &#125; else                                           // non-capture
      PlacePiece&#40;u->toSqr, u->promo&#41;;                  // update attack map &#40;empty -> promo&#41;
    &#125;
    board&#91;u->toSqr&#93; = u->promo;                        // put piece on new position &#40;overwrites victim&#41;
    location&#91;u->promo&#93; = u->toSqr;                     // update location of &#40;promoted?) piece in piece list
  &#125;
  u->keyChange ^= ZOBRIST&#40;u->promo, u->toSqr&#41;;         // hash-key update for moved &#40;and promoted?) piece
&#125;

void
UnMake &#40;UndoInfo *u&#41;
&#123; // put back pieces in reverse order, as PutBack calls do not commute!
  int d;
  int rifle = &#40;u->fromSqr == u->toSqr&#41;;
  if&#40;u->victim&#41; &#123; // capture, replace capturer by victim
    if&#40;u->promo&#41;
      Replace&#40;u->toSqr, u->promo, u->victim, 1&#41;; // restore attack map (&#40;promoted?) piece -> victim&#41;
    else
      PutBack&#40;u->toSqr, u->victim&#41;;        // capturer evaporated &#40;empty => victim&#41;
    board&#91;u->toSqr&#93; = u->victim;           // put victim back on board
    location&#91;u->victim&#93; = u->toSqr;        // and in piece list
  &#125; else &#123; // non-capture &#40;or rifle capture!)
    if&#40;rifle&#41; &#123;                            // rifle capture
      if&#40;u->promo != u->piece&#41;             // was promotion &#40;otherwise no-op&#41;
        ReplacePiece&#40;u->toSqr, u->promo, u->piece&#41;;
    &#125; else                                 // non-capture
    if&#40;u->promo&#41; LiftPiece&#40;u->toSqr&#41;;      // remove mover attacks &#40;if it wasn't already evaporated, empty -> victim&#41;
    board&#91;u->toSqr&#93; = 0;                   // remove also from board
    location&#91;u->promo&#93; = CAPTURED;         // remove promoted version &#40;will be overwritten below on non-promotion&#41;
  &#125;
  if&#40;!rifle&#41; PutBack&#40;u->fromqr, u->piece&#41;; // restore attack map &#40;empty => piece&#41;
  board&#91;u->fromSqr&#93; = u->piece;            // put back on board
  location&#91;u->piece&#93; = u->fromSqr;         // and in piece list
  while&#40;u->burned&#41; &#123; // all burn &#40;and other e.p.) victims
    int s = u->burnSqr&#91;--u->burned&#93;;
    int bv = burnVictim&#91;u->burned&#93;;
    PutBack&#40;s, bv&#41;;                        // restore their attacks &#40;empty => burn victim&#41;
    board&#91;s&#93; = bv;                         // put them on the board
    location&#91;bv&#93; = s;                      // and in the piece list
  &#125;
&#125;

Post Reply