Page 1 of 4
The Inferno thread
Posted: Mon Mar 06, 2017 3:31 pm
by hgm
I have finally started building an engine for Tenjiku Shogi, which is about the most violent Chess game ever designed. As it raises many challenges not present in orthodox Chess, it seems fun to start a sort of blog here where such issues can be discussed.
For one, the game is massive: a 16x16 board, with 60 pieces + 18 'pawns' per side. Where 12 of those are at least as powerful as a Queen, (and often hugely more powerful), and 10 nearly so. And almost all pieces can promote, when they enter the enemy camp (which is 6 ranks deep, so not just on last rank). So you have to be very careful that QS will not explode, especially if you also want it to search promotions. The large number of pieces makes incremental techniques very competitive; the number of moves that are enabled or disabled by a single move is only a very small fraction of the total number of moves.
Then there are pieces that can jump over an arbitrary number of other pieces (friend or foe) for capturing; you start with 6 of those, and 4 more can be obtained through promotions. They tend to attack an enormous number of pieces. At least a Queen is limited to eight capture targets, despite its large potential mobility of 27 (on 8x8), but a jumping Queen on a densely-packed 16x16 board can easily attack 25 enemy pieces when it jumps into the enemy camp (15 along a rank alone). Even from the own half of their board these pieces constanly make some ten attacks, mostly bad captures because they are so valuable themselves, but occasionally winning, and you cannot afford to have QS try them all.
The two strongest pieces (of which you can get two more by promotion) do not just capture the occupant of the square they land on, but all adjacent enemies as well. A bit like in Atomic Chess, except that they only 'burn' enemies, and survive themselves to repeat the favor. And they even destroy neigbors outside their turn; no enemy can step next to them without instantly evaporating. (If you captured somethig with it, it could still be worth it, though.) Trading them for 3 Queens is considered a bad trade by most players; it is usually easy to get 3 of these jumping slider (e.g. a jumping Queen, jumping Rook and jumping Bishop) by slamming them into the enemy Pawn wall early in the opening, but by more subtle play you can often destroy 4 or 5 Queen-class pieces with them. Generating the non-local captures they make is not trivial, as even moves to empty squares could take down 6 adjacent enemies. It also raises the question of how to sort captures. E.g. would it be more efficient to first capture a single Queen, of four Knights and Bishops?
Four pieces are 'multi-path', and can make up to 3 King steps in varying directions, sneaking through winding corridors to penetrate behind enemy lines. (And the terrible 'Fire Demons' described in the previous paragraph can do this, to do enormous damage!) The same square can often be reached along many different paths by this move, which makes deciding whether it is blocked or unblocked by other moves (as you would like to do in an incremental scheme) very hard.
Seven pieces are capable of 'hit and run' captures, where they destroy a single piece adjacent to their current location, to move on from there (possibly capturing a second piece, or withdraw to their original position). These pieces are also very difficult to handle in QS, because once they find a safe spot in the enemy camp, they can continue to destroy neghbors without moving for a long time, in hundreds of different orders, before using the space they created that way to move on the a new safe square. MVV sorting doesn't help to stop such plunder raids, causing big problems in QS.
Anyway, there seem to be a lot of interesting problems there, begging for creative solutions.
Re: The Inferno thread
Posted: Mon Mar 06, 2017 4:32 pm
by smatovic
just thinking aloud...
the last time i have read about classic Go engines,
they seemed to divide into tactical and strategic search.
Maybe you can split the board into small subsets to search?
--
Srdja
Re: The Inferno thread
Posted: Mon Mar 06, 2017 5:33 pm
by hgm
Well, I never played Go, but from the rules it seems it is mostly a local game. So I can imagine that treating it as a combinatorial game of many independent localized areas would work. Tenjiku Shogi is more like Chess, however, where most of the pieces are unlimited-range sliders, which can traverse the entire board in a single move. With sliders 'neighborhood' becomes a rather counter-intuitive concept.
So my intention is to do a more-conventional (for Chess) alpha-beta search. QS will take a lot of care to prevent it from consuming more search effort than it is worth, though. Some of these pieces are so powerful that the threats they can make are worth multiple Queens. So non-captures to manoeuvre such pieces in a position where they can pose such a threat is probably much more important than very precise accounting of what you will gain in a deep piece exchange.
So I want to do a lot of pruning in QS. E.g. only search a HxL capture if the victim is unprotected, or if there are multiple attackers. This will usually allow you to ignore all these captures by the jumping sliders that always can penetrate deeply into the enemy camp, but will typically only hit protected pieces (as every piece starts surrounded by 7 or 8 others, and even after developing that will not drop below 4-5, so there will always be something that protects you even if they are all steppers).
And even if you could grab something unprotected there, it is quite unlikely you would survive in the long run, because only these pieces can only jump while capturing. So a counter attack after they penetrated would force them to sacrifice themselves for a second piece, and both pieces they grabbed most be above average to justify the one-for-two trade. This is another situation where the non-capture to threaten the trapped jumping slider that you lured in could be far more profitable than performin any series of existing captures. And you would miss that completely in QS.
For captures that are searched in QS, recapture (on the same square) should probably be tried first, if they penetrated in your own camp. Searching plunder raids (recapture on a different square) should be strongly discouraged, and only tried if there are very good reasons to think that they might be profitable.
Re: The Inferno thread
Posted: Mon Mar 06, 2017 11:45 pm
by hgm
The first thing I am designing is the move generation and making. I want to base it on an attack map, to be able to easily determine which moves in QS I want to search. And for that information on how many attackers and protectors there are would come in very handy. The attack map should be updated incrementally.
My preferred scheme is based on a table viewDistance[square][direction], which for each of the directions 0-7 indicates the number of steps to the nearest obstacle (piece or board edge), for all occupied squares. This is easy to update incrementally, especially in QS, where you only evacuate squares (on which the table already contained information that helps the update), and never occupy empty squares (on which the table contains no information, so that you have to collect it by expensive ray scans).
One of the complications is the presence of these jumping sliders. As they can jump over arbitrary many pieces, it is as if they move on an empty board, not seeing the pieces at all. But unfortunately they do see each other, only the 'normal' pieces are fully transparent to them. But the jumping sliders come in 3 classes (moving as Rook/Bishop, Enhanced Bishop and Queen), and the lower-class members are transparent to the higher classes, but members of the same class block each other, as well as all lower classes.
So I should actually maintain a four-level view distance table, viewDistance[level][square][direction], where level 0 holds data involving all board occupants, level 1 only on all jumping sliders and their distances to the next sich slider, level 2 on the highest two classes of those, and level 3 only on the jumping Queens. Moving a 'normal' piece would then only require update of the level 0 table, as to the higher levels normal pieces are invisible. Only when a jumping slider moves the level to which it belongs, and all lower levels (which also see it as an obstacle) would need to be updated. Fortunately, of the 78 pieces you start with, only 6 are jumping sliders (4 more could promote to those, but with difficulty), only 2 of those are visible on level 2 (four more could promote from level 1 to level 2, though). While level 3 would initially contain 1 piece (two more obtainable by promotion from level 1). So the levels > 0 are sparsely populated, and most moves would not need to update them.
Availability of the viewDistance data makes generation of slider captures just as cheap as that of leaper captures, both direct (i.e. starting from the attacker) and 'inverted' (starting from the victim), as you immediately know the square a possible attack should go to or could come from in every direction. Almost all pieces in Tenjiku Shogi move neatly along orthogonals and diagonals; only very few pieces have different moves. E.g. in the initial setup only 7 pieces are capable of Knight (2,1) jumps, and only 3 of (3,1) or (3,2) moves. Generation of these moves from scratch in every node would not be very expensive. So the incremental stuff only concerns the on-ray attacks.
Re: The Inferno thread
Posted: Tue Mar 07, 2017 12:40 am
by noobpwnftw
Just random thoughts.
You may want to consider some kind of A* search for jumping sliders since it can do both move generation and path evaluation.
Re: The Inferno thread
Posted: Tue Mar 07, 2017 2:09 pm
by hgm
Thanks for the suggestion; I will check how an A* seach works. It has become clear to me that these jumping sliders are the most active pieces, so it would be pretty important to treat them efficiently.
I did conceive a nice data structure to figure out if Fire-Demon moves are captures. Fire Demons usually have many moves, because they move as Queen (except sideways) or make 3 King steps. So having a cheap test for such a move being a capture is very welcome.
The idea is to pack information on how many left and right neighbors each square in a file has into a single word. As (including the occupants of the files itself) this can run upto 3, a 2-bit counter suffices, and 16 such counters (one for each rank) can be packed into a 32-bit int. Because they are counters, they can be updated incrementally, by adding or subtracting one, each time a piece is put down or picked up. Each such action would only require update of the data on 3 files.
The number of neighbors can then be seen by accessing the data on the file where you go, adding the counts there for the rank and its two neighbor ranks. But since we are interested only to see if this sum is zero, we can just test the 6 bits of the 3 relevant counters; the sum can only be zero if these are all zero.
Code: Select all
#define SQR2FILE(x) ((x) & 15)
#define SQR2RANK ((x) >> 5)
int burnMask[16] = {
0x0000000F,
0x0000003F,
0x00000F30,
0x000003F0,
0x0000F300,
0x00003F00,
0x000F3000,
0x0003F000,
0x00F30000,
0x003F0000,
0x0F300000,
0x03F00000,
0xF3000000,
0x3F000000
};
int burns[-1..17][2]; // burns[file][color]
// in MakeMove():
one = 1 << 2*SQR2RANK(from);
burns[SQR2FILE(from)][stm] -= one;
burns[SQR2FILE(from)+1][stm] -= one;
burns[SQR2FILE(from)-1][stm] -= one;
one = 1 << 2*SQR2RANK(to);
burns[SQR2FILE(to)][stm] += one;
burns[SQR2FILE(to)+1][stm] += one;
burns[SQR2FILE(to)-1][stm] += one;
// to test if a Fire-Demon move captures anything:
if(burns[SQR2FILE(to)][xstm] & burnMask[SRQ2RANK(to)]) // move captures something
This is much less work than testing all eight neighbor squares for every pseudo-legal FD move.
[Edit]
I guess this could even be refined by not just counting pieces, but weighting them by value. By using 64-bit int for the burn[][] elements, the count can run upto 15. As 3 squares contribute, this works if the maximum piece weight equals 5. Instead of 'one' in the code above you would then use
Code: Select all
weight = burnValue[piece] << 2*SQR2RANK(sqr);
to mutate the burn[][] elements. For testing during move generation you would first AND with the applicable burnMask like in the code above, to see if there is something to burn. (For most moves there would not be anything.) If there is, you could then derive the total 'value' of the burn (to be used as sort-key) by adding the three counters for the rank and its neighbors.
You could for instance set Pawns = 0, steppers = 1, Rook-class = 2 Queen-class = 3, Lion-class = 4, jumping Queen = 5. Total burn values above 10 would represent a massacre, and be searched with priority over captures of individual victims (which would be generated victim-by-victim, ignoring attacks by Fire Demons). They might even be good moves if the Fire Demon gets recaptured. (Note that the attack map would be pretty useless for deciding if the FD move is safe, as the registered attacks to the square might be by pieces that are burned away, while this burning might now discover sliding attacks by more distant pieces.)
Re: The Inferno thread
Posted: Tue Mar 07, 2017 10:52 pm
by Evert
noobpwnftw wrote:Just random thoughts.
You may want to consider some kind of A* search for jumping sliders since it can do both move generation and path evaluation.
I'm not sure how useful A* is for this. It is very good (optimal? I guess that depends on the heuristic) for finding the fastest path between two nodes, but in this case you don't care about that, just about whether a path exists or not. Unless I misunderstand the rules of the game (which is possible) I think A* would not do anything different from a normal ray-scan until it finds a blocker.
Re: The Inferno thread
Posted: Wed Mar 08, 2017 12:08 am
by hgm
What I have in mind now is roughly this:
In each node the Fire Demon moves will be generated from scratch, like in a naive mailbox program, scanning rays away from the Demon until they hit an obstacle (for the sliding moves), and a 3-level recursion for generating its area moves. There is little to be gained by tricks here, as any move along the path could be a capture through burning adjacent enemies. (Unlike normal sliders, where captures are only found at the end of a ray.) This burning will be detected through the incrementally updated burns[] array as described in an earlier posting.
Leaps to the second square (including Knight jumps) will always be flagged in the attack table. (Even when they hit an empty square.) The on-ray 2-square jumps by a bit indicating the direction they go in, the Knight jumps by a bit indicating the piece that makes them. Only few pieces make Knight jumps: 2 Knights and 2 Lions. As these cannot be blocked they only depend on presence and location of the source, which makes incremental update easy. When a piece with such moves does move, you clear the old moves and add the new.
Apart from the Fire Demons there is only a single piece that has an area move (and promotions can give you two more): the Vice General. For the attack map the area moves are treated like they are direct leaps, and each Vice General has its own bit in the attack map. All bits in the 7x7 area centered on a VG, except the central 3x3 area, will thus be set, and this will alter only when the VG moves or is captured. (The adjacent squares are already taken care of by the on-ray sliding moves.)
This shifts the problem to the actual capture generation, where an area move flagged in the attack map might be a blocked one, and will have to be vetted. When this need arises for a certain VG (i.e. we want to consider capturing a victim that is with the range of the area move), we generate all area moves of the VG from scratch, and mark them in a 7x7 table 'areaMap[]' local to the node with the same bit as the one indicating that VG in the (global) attack map. After that, each flagged area move of that VG can be vetted by
Code: Select all
int todo = attacks[toSqr] & VICEGENERALS;
while(todo) {
int bitNr = lowBit[todo];
int bit = 1<<bitNr;
int piece = bit2leaper[bitNr];
int fromSqr = location[piece];
todo -= bit;
if(unvetted & bit) { GenerateAreaMap(fromSqr, bit); unvetted -= bit; }
if((areaMap[toSqr-fromSqr] & bit) == 0) continue; // area move was blocked
GenerateCapture(fromSqr, toSqr);
}
Re: The Inferno thread
Posted: Wed Mar 08, 2017 10:10 am
by hgm
View Distances
The basis of the incremental updates of the attack map, and slider capture generation, is the view-distance table. This table tells us by a single lookup how far every piece can look in all 8 major directions (orthogonals and diagonals). It is updated incrementally itself; every time a square gets evacuated (by a piece moving away, or a non-local capture like e.p. in Chess, and Fire-Demon burns in this game), diametrically opposed neigbors must be set to view each other, rather than the just evacuted square.
As the table is not supposed to hold information on empty squares, the view distances from the evacuated square can be left in place. This will be very helpful during UnMake, where the square has to be re-occupied. The nearest neighbors should then again be set to all view the square, and the lingering view-distances immediately tell us where these neighbors are. The price is that future occupation of the square by moves to it deeper in the tree must not alter the information, but save and restore the view distances of any empty square they land on. So they can put their own view distances there. (Which could be different, because neighbors moved during the time the square was empty, and thus not updated. Fortunately it happens only rarely in QS that moves to empty squares are performed, and most nodes are QS nodes.
We still must be able to handle occupation of empty squares, even though this happens comparatively rarely. There are two ways to do this:
ray scan or
obstacle hopping. With ray scan you step along the ray in the 'up-stream' direction, testing the board until you meet an obstacle. In that obstacle you have view-distance data, which then immediately tells you how far away in the down-stream direction you will find the obstacle in the opposite direction along the ray. So you only have to scan in 4 of the 8 directions. This assumes that the view-distance table also holds data on 'edge cells', i.e. virtual squares just outside the board that touch a real board square. So the view data is really 18x18, rather than 16x16 in Tenjiku Shogi. Because the board layout is 0x88 style (32x16), the view-index still can be indexed by the regular square numbers.
The second way to do it is obstacle hopping. With this method you need a table that indicates for every board square which edge cell its ray hits in the 'down-stream' direction. You can then start in that edge cell, using the view-distance it stores to find the next obstacle in the up-stream direction from it, and then take the next obstacle from there, and so on, until you overshoot the square that needs to be occupied. The last two obstacles visited in this process will then sandwich the newly occupied square, and the distances to the latter can be looked up in a vector-length table, and stored in the appropriate places in the view-distance table.
The ray-method is efficient on densely populated boards (such as the initial position of Tenjiku Shogi!), but requires long ray scans (mostly all the way to the edge) on very sparsely populated boards. The obstacle hopping has just the reverse; on a sparsely populated board the first obstacle seen from the edge cell is usually the opposite edge, and you can insert the occupant immediately. While on dense board every hop brings you just one square closer to the target in an expensive way (requiring an extra table lookup and multiplication, instead of just adding the step).
Now for Tenjiku we need to maintain view-distances for the three levels of jumping sliders (which look right through normal pieces) as well as for the basic pieces. The boards for these 'higher' levels are only sparsely pouplated, as even after promotions at most 10 out of the 78 pieces are jumping sliders. And most of those would be level 1; the number of level-2 and level-3 sliders is at most 3 (and initially 1) per side. So for the update of the high-level view distances we definitely should use the obstacle-hopping method. For the normal pieces we will use the ray-scan method for now. In theory it would be beneficial to switch to obstacle hopping for those too, in the end-game. But for now we put emphasis on the early middle game, assuming that the game will be decided there, and that a bit of sub-optimal play in the end-game no longer matters.
This gives the following code:
Code: Select all
typedef long long int int64;
typedef union {
int64 t; /* to save and restore all directions at the same time */
char d[8]; /* free view in each direction */
} Views;
#define DSIZE (BSIZE + 2*WIDTH) /* board plus 1-wide edge */
#define viewDist (rawView + WIDTH + 1) /* distance to nearest eighbor in each direction */
Views rawView[4*DSIZE]; /* 8 distances for each occupied square per direction (4 levels) */
int sqr2edge[BSIZE][4];
// viewDistance updates
void
ExtendView (Views *viewDist, int sqr)
{ // let diametrically opposed squares view each other
int d;
for(d=0; d<4; d++) {
int vec = step[d];
int upDist = viewDist[sqr].d[d];
int dnDist = viewDist[sqr].d[d+4];
int upSqr = sqr + upDist*vec;
int dnSqr = sqr - dnDist*vec;
viewDist[upSqr].d[d+4] = viewDist[dnSqr].d[d] = upDist + dnDist;
}
}
void
UnExtendView (View *viewDist, int sqr)
{ // assumes viewDist[sqr] is still valid (as it would be in UnMake), and makes nearest neigbors view it
int d;
for(d=0; d<4; d++) {
int vec = step[d];
int upDist = viewDist[sqr].d[d];
int dnDist = viewDist[sqr].d[d+4];
int upSqr = sqr + upDist*vec;
int dnSqr = sqr - dnDist*vec;
viewDist[upSqr].d[d+4] = upDist;
viewDist[dnSqr].d[d] = dnDist;
}
}
void
BlockView (int sqr, int level)
{ // occupy an empty square with a piece of ranking 'level' (GG=3, VG=2, RG/BG=1, others=0)
int d;
for(d=0; d<4; d++) { // four up-stream directions
int vec = step[d];
int s = sqr;
int t, dist, newDist, l;
while(board[s+=vec]) {} // search first up-stream obstacle on ray (EXPENSIVE on sparse board!)
dist = viewDist[s].d[d+4]*vec; // determine antipode from view distance at up-stream obstacle
t = s - dist*vec;
viewDist[sqr].d[d] = viewDist[s].d[d+4] = newDist = distance[s - sqr]; // obstacle and sqr view each other
viewDist[sqr].d[d+4] = viewDist[t].d[d] = dist - newDist; // antipode and sqr view each other
if(level) { // we placed a jumping general, (rare!), so higher levels will also get blocked
int edge = sqr2edge[sqr][d]; // down-stream edge intersection
for(l=1; l<=level; l++) { // also update the affected higher-level view distances
Views *vD = viewDist + l*DSIZE; // viewDist table for generals of rank l
s = edge; // (we use obstacle hopping rather than ray scan, because board is sparse)
do { t = s; s += vD[s][d]*vec; } while(direction[s-sqr] > 3); // view-hop on this level until s overshoots sqr
vD[sqr].d[d] = vD[s].d[d+4] = newDist = distance[s - sqr];
vD[sqr].d[d+4] = vD[t].d[d] = dist - newDist;
}
}
}
}
Note that the ExtendView() and UnExtendView() routines just treat a single level, (the correspoding viewDist[] array passed as a parameter), and that the caller would have to take care of treating the necessary higher levels in case a jumping slider gets moved, while the BlockView routine takes care of all levels by itself.
Re: The Inferno thread
Posted: Wed Mar 08, 2017 3:04 pm
by hgm
Some preliminary thoughts on the attack map:
The purpose of this map is to provide instant information on the attacks to a given square. This information will then serve to generate captures in victim order. As it contains an enormous amount of information, it must be possible to maintain it incrementally, as generating it from scratch would be very expensive. For Fire-Demon burns this goal seems unachievable, so the Fire Demon will not be accounted for in the table.
To easily convert the attack data into actual captures, it should be easy to derive the attacker from this data. E.g. one could make it a piece set, where each bit indicates a specific piece. In Tenjiku Shogi that is inconvenient, as there are more than 64 pieces. It is also a wasteful representation, as not all pieces could attack you at the same time. Another method would be to let each bit represent a direction from which the attack comes. Together with the view-distance information, this then identifies the attacker. At least when the attacker would be the nearest piece. Which in Tenjiku Shogi, with the jumping sliders, is unfortunately not always the case.
There are in fact 6 different kinds of attacks that can come from a given direction, which can occur in almost any combination: level 3, 2 and 1 jumping sliders, a normal sliding or contact attack, a direct leap to the second square, and by a silly piece called a Tetrarch, which can jump over the adjacent square, and then continue sliding normally in the same direction. (This move is sometimes referred to as the 'Ski-Bishop'.) The Tetrarch could attack both in combination with a normal slider or with a piece that jumps to the 2nd square (in the latter case only if the jumping piece is at distance 2, and the Tetrarch at distance 3), while a 2nd-square jumper and a slider can also combine (if they are at distance 1 and 2, respectively). This in cooperation with any combination of jumping sliders, which just jump over them.
So it seems that to uniquely indicate all attackers, you would need 6 bits per direction, 48 bits in total. And in addition you would have to record oblique attacks, like Knight jumps, and area moves. As there are also only 8 hippogonal directions, and at most 3 pieces that can do area moves, 64-bits do seem sufficient for implementing this scheme. Incidentally, there are also at most 6 pieces capable of making Knight jumps, so it might be smarter to identify hippogonal attackers directly with a bit, rather than by the direction the attack comes from.
So we will aim for an attack map of int64, with 6 groups of different types of on-ray attacks for all 8 directions, 6 bits to indicate hippogonal attackers, and 3 bits to indicate area-move attackers.