Efficient capture generation in the game of Thud

[koedem]

Before I start, sorry if this is too offtopic, it's not directly related to chess though I can't think of better people to answer this than chess programmers.

Thud is a board game played on an octagonal 15x15 board. (for implementation purposes it might be useful to consider it as square and just never move onto the non existing squares) One player plays with 32 dwarfs as pieces, the other one has 8 troll pieces.
I am wondering how to efficiently generate captures. E.g. the dwarfs can capture like a queen, however only as many squares away as they have dwarfs behind them backing it up. I.e.
captures possible: DT ; DD-T ; DDD--T ; DDD-T
not possible: D-T ; DD--T etc. (D = dwarf, T = troll, - = empty square; these captures work in all 8 queen directions like that)

I never worked with the magic numbers for chess move generation, would something like that be applicable here? Seems tricky due to the large board size.
One idea would be to have a bitboard with all squares we can capture on, and on making a move update the affected regions of the board. (which shouldn't be that much effort, though still the question how to do this most efficiently)

Alternatively since there's only 8 trolls, maybe one could look from their POV in all 8 directions to see if there's a dwarf line that could capture that troll. If done naively (i.e. for each troll and each direction first check if the position is D , then -DD, then --DDD ) that would be quite slow, but maybe there's some tricks to speed this up?

Any other ideas what could work? And once again, if this is too offtopic please tell me, then I will refrain from such posts in the future.

[hgm]

With a mailbox board a 'neighbor table' could be useful: this would, for each occupied square, contain the number of the nearest occupied square in each of the eight directions. It is not very expensive to update such a table incrementally, if you postpone the update to the point where you are sure you would need it. You could then use the table to immediately examine the piece nearest in each direction from a Troll, to test if it is a Dwarf, and when it is test if the required number of Dwarfs is behind it.

You could also represent the board by 'bit rays': for each square you would have a (fixed) table to get the ray number of all 4 rays that pass through the square (so you can update them when the square gets occupied or evacuated). You would then have tables indexed by ray number that keep track of the squares that are occupied by Dwarfs or by Trolls, by setting the bits corrsponding to the occupied squares). Each ray would have at most 15 squares, and you could use it as an index in a table of 32K attack rays, getting the potentially attacked squares (i.e. if not blocked by the opposite color) on that ray. For each Troll you would look up the Dwarf occupancy of the 4 rays going through it, and use these to look up the potential attacks, and intersect those with the Troll occupancy of that ray. If there is a match, it could still be blocked by another Troll. You could facilitate testing of that by having a 2d table indexed by the square number of the potential attack and the dwarf occupancy (so 15 x 30K = 450K entries). This could then contain the set of bits that must be Troll-free for the attack to be valid, an after its lookup you would intersect it with the Troll occupancy.

Note that for such big boards entirely incremental methods are often very competitive. You could for instance keep an attack map for the Trolls, 8 bit per Troll, to indicate from which of the 8 directions they are attacked. This packs nicely into a 64-bit word, so you can 'generate' the captures of them by simply extracting the set bits from an int64. Moves only change things on the rays that go through their from- and to-square, which together make only a small fraction of the total board area. So even implementations that just 'look around' in all directions from the two mutated squares by scanning a mailbox board often do very well. E.g. for the evacuated square any captures by the former occupant should be deleted, captures over it get discovered, and adjacent rows of friendly pieces see their capture in the opposite direction shift to a less distant square. All that isn't terribly hard to calculate.

[Edit] It says here that the Dwarfs can also capture at any distance less than the length of the Dwarf line. That would make the capture more like a slide instead of a lame leap, which would highly simplify incremental update of an attack map. (Because pieces that could discover moves are then always attacked themselves, so that you can do the discovery based on the former attacks to the evacuated square.) In fact the game will have a lot in common with Tenjiku Shogi (where Fire Demons can also burn all adjacent enemies). So perhaps the contents of the 'Inferno Threat' I once posted here could be relevant.

[koedem]

Note that for such big boards entirely incremental methods are often very competitive. You could for instance keep an attack map for the Trolls, 8 bit per Troll, to indicate from which of the 8 directions they are attacked. This packs nicely into a 64-bit word, so you can 'generate' the captures of them by simply extracting the set bits from an int64.

That seems like the logical combination of the two things that I suggested, except it's quite obviously way better than either one. Not sure how I didn't see that myself but thanks for pointing it out. I will probably go with that since it's easy to do and should still give good performance. (instead of looking up such rays one could probably just calculate them on the fly too)

[Edit] It says here that the Dwarfs can also capture at any distance less than the length of the Dwarf line. That would make the capture more like a slide instead of a lame leap, which would highly simplify incremental update of an attack map. (Because pieces that could discover moves are then always attacked themselves, so that you can do the discovery based on the former attacks to the evacuated square.) In fact the game will have a lot in common with Tenjiku Shogi (where Fire Demons can also burn all adjacent enemies). So perhaps the contents of the 'Inferno Threat' I once posted here could be relevant.

Yes, I thought my example DDD-T made that clear but I guess I could have also stated it explicitly. Will have a look at that post once I find the time.


I thought whatever I decided on would apply to troll captures too. As you mentioned those work similarly, except you don't land on the enemy piece but instead have to land adjacent to it. (and then you capture all adjacent pieces)
However looking in all directions from each dwarf, for only 8 opponent trolls seems like overkill. In that case my original suggestion of keeping track of all squares that could be captured might be better? (for trolls those look slightly different of course because of that "areal" attack)

One could also use modified versions of the suggested rays thing though that seems a bit more tricky to me.

[hgm]

Yes, I thought my example DDD-T made that clear but I guess I could have also stated it explicitly. Will have a look at that post once I find the time.

Oh, sorry, I missed that. BTW, even when the distance had to be exactly the number of backing Dwarfs, efficient updating of an attack map would be possible if the map also indicates 'blocks' in addition to actual attacks (so use 2 bits per directin instead of 1); when a square gets evacuated you can then displace the marked blocks outward to the next obstacle (if in range), where they could either stay blocks, or turn into actual attacks. This would be needed, for instance, for the Elephants in Xiangqi. But in Thud you won't have that complication.

The 'explosion captures' of the Trolls are a pain, because so many targets will change due to a moving Troll that incremental updating is hardly competitive. In my Tenjiku Shogi engine I therefore generate all Fire Demon moves from scratch in every node. Even though each player in general has at most 2 Fire Demons, these are extremely mobile pieces, (unlike the Trolls), which can have more than 100 moves each. To easily test whether a generated move is a 'burn' (i.e. lands next to an enemy piece), I defined 'strips' as 3x16 sub-areas of 3 adjacent files of the 16x16 board. A bitmap for each strip then fits in a 64-bit int, and indicates the squares in that strip occupied by either white or black pieces. Each square will be covered by 3 strips, each of which will have to be updated when the square mutates.

For each move I then split the to-square in a file and rank number, and consult the (opponent) strip that is centered on that file (which also contains the population of opponent pieces on the two adjacent files). I then intersect this with a mask for the to-rank that indicates the squares in the 3x3 neighborhood; if there was any enemy presence there the move was a capture. This speed up the testing a lot, compared to examining all adjacent squares of the to-square in the mailbox board itself. (Which otherwise would have to be done for hundreds of moves, so that you very easily gain back the investment of the update of the strips.)

I don't kow how this would work out for Thud; the number of Troll moves might be too low there to earn back the investment of updating the strip populations.