The Inferno project: hook moves

[hgm]

Hook Movers

Now that an incrementally updated attack table for Tenjiku Shogi works like a charm, I started thinking how to make the engine also suitable for other large Shogi variants. These variants do not have jumping sliders (which are unique to Tenjiku Shogi), but they have other pieces that require special treatment. In particular 'hook movers', which are sliders that can turn one 90-degree corner along their trajectory.

Such hook movers potentially have an enormously large number of attacks. The orthogonal version would attack every square on an empty board, along two different paths, and the diagonal version all squares of one shade. Moving them would keep a very large number of those attacks unchanged. So only updating the attacks that actually change when the piece moves, rather than deleting all the hook mover's old attacks, and then generating all attacks from the new location, can save a large amount of work.

Indicating hook attacks

Because hook movers are small in number, we can afford to dedicate two bits in the attack-map elements to each individual hook mover: one for each of the two paths through which it could attack the target. This then immediately identifies the orientation from which the attack is coming (i.e. the second leg of the bent trajectory): line or file for orthogonal hook movers, diagonal or anti-diagonal for the diagonal one. This is helpful when such an attack gets discovered by moving away the target, to know how it has to be displaced 'down-stream'.

Second-leg views

The squares on which the hook moves turn a corner ('the knee') are always empty squares. This means the normal view-distance tables do not store any information on them. Yet it would be very desirable to know the view distances in both directions perpendicular to the primary leg. Any square on the primary leg is a potential knee, and the primary leg can potentially span the whole board.

For each hook mover we therefore keep a dedicated table that for the two rays through the primary legs holds the view distances to the nearest perpedicular obstruction on either side of its squares. For an NxN board this would require 4N bytes per hook mover. Only the squares that can be reached by the primary leg (i.e. up to the first obstacle) will contain valid information. The invalid part is supposed to remain undisturbed by a MakeMove - UnMake combination, so when a primary leg gets elongated by withdrawal of its blocker, the slots in the hook-views table it adds will have to be saved before the newly computed ones are written there, so they can later be restored.

This data makes it possible to loop through all hook attacks in an easy way (e.g. for removing them when the responsible hook mover gets captured). We just step through the squares of the primary legs, and the tabulated view distances for that square will then tell us where to find the two targets in the perpendicular direction. A similar procedure would be applied when a primary leg gets blocked, and attacks through knees on the now unreachable part have to be removed.

[hgm]

Updating on hook moves

When a hook mover moves without turning a corner, all hook attacks that have their primary leg along the ray of movement will remain possible. Some of those will turn into a straight attack, however, and vice versa. Because such straight attacks are already included in the attack map amongst the normal slider attacks, it means their dedicated hook-move bits woould have to be cleared in the targets on the ray perpendicular to the movement through the final square, and have to be set in the targets on the perpendicular ray through the square of origin.

The primary legs perpedicular to a straight move will be shifted to a new location, where it will run parallel to the old ray. This does not necessarily mean that the hook attacks starting in this direction will change: as long as the ray does not pass over any obstacle during the shifting to the new location, they still hit the same targets. Only the distance to these targets will change by the amount the ray gets shifted, added on one side, and subtracted on the other. Only squares on the ray that pass through an occupied square during the shift will see new targets for the hook moves that use it as a knee. These new targets will have to be determined by scaning the board from the new location of the knee.

The shifted primary leg can be longer or shorter than the original one. If one of the knee-squares on the old one is shifted exactly on an obstacle, the primary leg will now be cut short there. If that never happens, we would have to scan the board starting just beyond the end of the shifted ray, to see how far it continues, and scan the board perpendicularly from each added square to determie the new view distances there, and add the attacks at their end point. This is in fact the same as what one would have to do when creating the hook attacks from scratch (e.g. during position setup), or when a primary leg gets discovered.

On a general hook move, both things happen to each primary ray: the ray shifts sideways, and the hook mover moves along the ray. The latter, which just corrects for hook attacks turing into straight ones, is relatively simple. It can be implemented by first adding the existing straight perpedicular attacks as hook attacks, before shiftig the ray to the new location. Afterwards, the hook attacks can then be removed again from the attack map where they would be straight attacks based on the new location of the hook mover along the ray.

So the procedure would start with running through the view-distance table dedicated to the hook mover, starting from its original square, and compare the perpendicular view distance in the direction of the shift with the magnitude of the shift. If the latter is smaller, the attacks over that knee would be unaffected, but the view distances would have do be changed by the shift. By storing the distances on either side of the ray as different bytes in one word, they can both be adapted at the same time with one ADD operation to the word. If the shift is larger than the perpendicular view distance, the old attacks through that knee square have to be removed, and new targets and view distances would have to be determined by a board scan. This can lead to an abort of the scan along the primary leg, when it is found blocked.

[hgm]

After a short pause, I return to this problem. It has become somewhat clearer to me now how exactly to represent the information that must be maintained for efficient generation of the hook moves. I will use the following position as an example:

[d]5b2/1b1pp3/b5p1/5p2/8/2P2R1P/1b1P3P/4P3 w - - 0 1
Here the Rook represents an orthogonal hook mover, which makes up to two perpendicular Rook moves (but cannot continue after making a capture). So it attacks/protects all the Pawns in the diagram.

Attack map

In the attack map there will be two bits associated with this particular hook mover, which we will call H and V. The H bit flags hook attacks that start along a file, the V bit those that start along a rank. In deviation to what I stated in a previous post, the H or V bit will also be used to record straight-line attacks; these will be treated as if they had a first leg of length zero. These attacks will not be recorded as normal slider attacks; the ranges listed for hook movers in the move-description table will thus all be set to zero, as if it has no (normal) moves at all.

This means that all squares on which there are black Pawns, and those with white Pawns on 1st and 2nd rank will have their V bit set, and all white Pawns (but no black Pawns) will have the H bit set. (Note that in the engine there will also be a rim of edge guards around the board, many of those attacked as well, but I could not show that here.)

Second-leg view distances ('hook views')

For this hook mover there will be two tables with 8 entries, for keeping track of the view distances from the knee squares. As an example, let us focus on the table for the V bit. In the current position these are the squares on the 3rd rank. Currently only the entries for d3, e3, f3 and g3 are valid, as these are the only reachable knee squares. (Yes, the square of the hook mover, f3, is amongst those too, as we allowed first-legs of length 0.) Info held in this tables would be as follows:

Code: Select all

square             d3  e3  f3  g3
entry   0   1   2   3   4   5   6   7
+ dir   x   x   x  60  60  40  50   x
- dir   x   x   x -10  00  10  10   x

Here 'x' represents an invalid value, perhaps left there from a previous ply (which we should leave undisturbed in case we want to UnMake back to that play). The numbers are in hexadecimal, corresponding to the rank part of the 0x88-type numbering used to indicate the board squares (a1 = 00, b1 = 01, a2 = 10). So the table for the + direction (towards high rank number) contains numbers corresponding to 7th rank (60, for d7, e7), 6th rank (50, g6) or 5th rank (40, for f5).

For the - direction (towards low rank number), we adopted the convention to store the value negated. So the numbers correspond to d2 (10), e1 (00), and two edge guards (-10, f0 and g0).

Move along primary leg

For a move of the hook mover along a rank, no update of this table is required at all. The 3rd rank will keep containing the sideway primary legs. The Pawn at f5 and edge guard at f0, which were hit straight on, are still hit by a V-type hook move, but with a primary leg of length > 0 instead of 0. So their H bits were, and remain set. This is the advantage of considering the straight moves as having a primary leg of length 0 rather than as having no secondary leg.

Hook move

As an example now let us move the hook mover from f3 to d6. The table there now will have to be:

Code: Select all

square     b6  c6  d6  e6  f6
entry   0   1   2   3   4   5   6   7
+ dir   x  60  80  60  60  70   x   x
- dir   x -10 -20 -10  00 -40   x   x

That is, the table now represents knee squares on 6th rank. The knees d6 and e6 still hit exactly the same targets, and thus do not require update, neither in the hook-view table, nor in the attack map. The new and old primary ray will always have such a common part (even if it is just a single square), or the hook move would not have been possible. Note that the valid parts of old and new ray have a larger overlap, also encompassing the f-file. The views from f3 and f6 are different, however, because the primary ray shifted beyond f5, which was one of the targets.

So the update starts by determining the ends of the valid parts. Note that these ends can easily be obtained from the normal view-distance tables in the directions along the primary ray for the from- or to-square. Beyond the ends of this common validity region, we might have to extend the ray, (to the left in the exampl), adding info on the knee squares c6 and b6. For this we would scan the board along the (new) primary ray, to find empty squares, which are new knee squares. For each such new knee square we would have to scan perpendicularly to find a hook target, set its V-bit, and put its rank code in the hook-view table for the + direction. The normal view distance in the - direction at that square then brings us imemdiately to the second hook target from that knee. We also set the V-bit for that, and store its negated rank number in the hook-view table for the - direction. The values thus overwritten in the hook-view table must be saved somewhere, so UnMake() can resore them. This procedure is in fact what we would have to do for the entire reachable primary ray when we want to generate hook moves from scratch (e.g. because a hook mover was dropped during position setup).

Then we have to attend to the region of common validity. The primary ray is shifted in the + direction, to 6th rank (coordinate code 60). Any target in the shift direction that has a lower rank is thus 'passed', i.e. the new primary ray runs along the other side of it. So that it can now at most be target in the - direction, but never in the + direction. That means that for knee squares that list a target with rank < rank-of-new-primary-ray, we will have new targets. These can be obtained in exactly the same way as for new knee squares due to elongation of the primary ray. When old target rank > rank-of-new-primary-ray, we don't have to do anything, because the knee square remained between the same two targets. Note that the old target can never be on the new knee square, as then the knee square would not have been in the region of common validity.

Since we do the same thing to obtain new targets in all cases, we could all do this in a single loop over knee squares on the new primary ray. We would just have to suppress the action when the knee square is inside the region of common validity (and since we only loop over the region of validity of the new primary ray, that means it must be in the region of validity of the old ray), AND the new rank code is smaller than the rank of the hook target. For shifts of the primary ray in the other (-) direction, it would be the same, except that we have to (1) compare to targets in the - direction, and (2) test for larger rank instead of smaller. The latter is achieved by comparing (and storing) the negated values, so that only the rank code of the new primary ray has to be negated before looping over the knee squares. This way there doesn't have to be separate code for handling shifts in the + or - direction.

Note

I assumed here that the 'ray code' would be stored in the hook-view tables, i.e. rayNumber times boardWidth. This because that makes it easier to reconstruct the complete square number of the targets, (as rayCode + kneeIndex, without needing an extra multiplication), which is needed to access their attack-map elements. But this would be a bit undesirable if the board is so large that the square numbers no longer fit into a single byte. And it would not work for the H-type hook attacks anyway, as there the index of the hook-view table would correspond to the rank of the knee square (and the targets reached through it), so that you would have to multiply to get the square number anyway. So it just makes it more difficult to handle H and V attacks with the same code. So perhaps this is a dumb idea, and it is better to store plain file and rank numbers.