New project: very general engine for variants

[hgm]

To get back to the engine design:

Move trajectories radiate out from a piece. If at every square in the trajectory the choice is only between continue and stop, life is simple, and the trajectory can be stored sequentially in an array (the moveTable). But some pieces will have trajectories that conditionally branch: depending on the occupancy of a square that they reach they could continue in one direction or another. There can even be trajectories that branch unconditionally: a 'Hook Mover', which can make two perpendicular Rook moves over empty squares, in addition to one normal one, can continue in three different directions on any empty square. So basically trajectories are trees, and a tree-walk is necessary to extract the individual moves from them.

The case with conditional branches would specify a single continuation for each of the three occupancies (empty, friend, foe). One of these could be termination rather than continuation. This could be specified by the number of steps in the moveTable we have to advance to get at the next cell of the trajectory. This never needs to be very large, so it could be stored in a byte. Usually it would have value 0 (terminate) or 1 (continue with next); an alternative branch would have to be stored beyond the end of the current one. (If that is out of range because the principal continuation would need more than 256 cells, you could always interleave them, and then step through those in steps of 2 instead of 1.)

Pieces that only branch conditionally follow a single path for any given board occupancy although that path can be different for different occupancies. E.g. consider a piece that starts off like a Rook until it arrives at an occupied square, and then turns 45-degrees left to continue as a Bishop. The squares it visits in this second leg of the move have a different location w.r.t. the piece depending on where it makes the bend. So either we must tabulate different trajectories for this second leg for every point along the first leg where it could bend (in which case we can include the locations relative to the piece as a fixed value), or we would have to specify the squares on the trajectory not relative to the piece, but relative to where the leg started. Then we would have to store only a single trajectory for the second leg in moveTable, which could save appreciable storage on a large board.

Now locations in the moveTable will be relative to something anyway, even if it is only relative to the piece. So it isn't really much extra trouble to let each entry in moveTable specify what its reference location is, e.g. through a pointer. For the first leg of the move (which for the majority of pieces would be the only leg) these would point to the location of the piece they belong to in the piece list. But we could have auxiliary location variables for indicating the start of continuation legs, to which these legs then refer. These would be updated dynamically, as the position on the board changes such that the total trajectory would bend on another square. E.g. if the obstacle that triggered the bending would move away, the path would no longer bend there. So the 2nd leg would have to be dissociated from the board cells it was associated with, the next downstream obstacle on the first leg would have to be identified, its location stored as reference for the new second leg, and finally the cells in that leg should be associated with the new board squares they go to (for as far as that leg now can continue on the board).

Now pieces are usually symmetric. Which means that when their path can bend to the left, it can also bent to the right. This makes it their path bifurcate. This could still use the same scheme, however, provided we allow two different continuation trajectories in the case of an occupied square, both indicating their location to the branching square. (And a single continuation at an empty square.)

If the second leg is colinear with the first there is no branching, and the second leg visits the same squares as the first would have. At first glance it seems wasteful to dissociate the second leg and then associate it further downstream (and associate some more cells of the first leg as well) in case the obstacle that caused the transition moves away. But the rules for what the move could do (e.g. capture and/or non-capture) could be different in the second leg from what it would be in the first, as would be the rules for continuation. (When you are already in a second leg, you won't be able to transition to it like you would be on the first, and a new obstacle would terminate the move.) To change all that information is likely more work than just associating and dissociating the cells containing the information, or at least not much less. And although pieces that need this frequently occur in chess variants, they still will form a small minority in the variants where they do appear. So there would be very little performance benefit in treating them differently from pieces that do change direction at a transition point.

The situation is different for hook movers and the like, where the trajectory branches in many different places from the first leg simultaneously. Then there is no way to avoid that all trajectories after the bending squares have to be separately tabulated in moveTable. In a sense they are not even second legs; they can refer their square locations relative to the piece. The first leg is just one huge tree. Consider a Hook Mover (making two perpendicular Rook moves) on a 19x19 board. (Yes, there is a game that has that: Maka Dai Dai Shogi.) For each of the 4 directions a move could start in it would have 18 cells in the straight-line trajectory, and from each of these cells there are two perpendicular trajectories, each also 18 cells long. So in tyotal 37x18 = 306 entries in moveTable, for each of the 4 (initial) move directions. Is this outside the range of a byte-size indication for how far down-stream to continue? Not at all: all 36 perpendicular trajectories could be interleaved, so that they specify continuation 36 entries further in moveTable in an empty square (and termination in an occupied one), and all start within a distance 36 from the last cell in the primary part of the trajectory. As this is pretty much a 'worst case', it justifies use of 8-bit continuation 'pointers'.

So it seems we need the following:

Code: Select all

typedef struct {
  int next, prev; // for doubly linked square-association lists
  int leap;       // relative location
  int piece;      // index of piece that makes this move
  int reference;  // index of location reference in (extended) piece list
  char rights;    // flags indicating for which square occupancy the move can end here
  char n_empty;   // number of continuations at empty square
  char n_friend;  // number of continuations at occupied square
  char n_foe;     // number of continuations at occupied square
  char empty[4];  // offsets of 'empty' continuations
  char occup[4];  // offsets of 'occupied' continuations
} MoveTarget;

MoveTarget moveTable[MAXPOTENTIALMOVES];

* Using 8 bits for 'piece' and 'reference' might put too tight a limit on the maximum number of pieces (127 per players), so I used ints.
* I combined the continuations for friend and foe, as I have never seen a variant where the path of a piece would continue in a different way depending on whether it hopped over a friend or foe.
* It is common that you can only hop over friends or foes, but it could be indicated in the 'rights' flags whether this is the case.
* But I think it is better to have separate n_friend and n_foe, which both would refer to the same occup[] table when non-zero.
* The flags can also indicate whether the hopping is destructive or not (i.e. whether the hopped-over piece should be removed).
* I took up to 4 possible continuations for each occupancy; this covers the case of making both 45-degree and 135-degree turns.
* These MoveTarget cells use 32 bytes of storage

[MTaktikos]

Hello HGM,
the infos from your messages are exciting
First I have examined the game Hekatomb which you mentioned. Although it differs from chess only in the start position, I could play it only in your Winboard GUI with Lc0 chess engine, all other pure chess engines crashed so far. Also I implemented it in Ludii and found out that, at least in the opening, the UBMF algorithm plays reasonable.


About BattleOTK:
Wow, that fast, how you implemented it in the ID engine!

Of course the play sucks. But it does play. And (playing with white) it did beat the Dagaz AI

Not only that, it beats also the Zillions engine! For a first attempt very successful:

Code: Select all

BattleOTK
ID engine (2.5 ply) vs Zillions (15 s/move) 

1. bxb4 fxf5 2. Nxb2-d3 Nxf7-d6 3. Bxb2-d4 Bxf7-c4 4. Rxb2-b1 Bxc4xd3 5. Bxd4-c3 Rxf7-f8 6. Rxd4xc4 Qxf7-h5 7. cxd3 Qxh5-g4 8. Rxc4-c5 exe6 9. Rxc5xc7 Nxd6xc4 10. Rxc7xd7 Rxf8-c8 11. Rxd7xd6 Nxc4xd6 12. Rxb1-c1 Qxf8-e8 13. dxc4 Nxd6xc4 14. Nxd3-e5 Nxc4xe5 15. Bxd3xc4 gxg6 16. Rxd3-h3 Kg5 17. Rxh3xh7 Qxe8xd7 18. Rxh7-h8 Nxe7-g8 19. Rxh8xg8#

Well done!

any case extra royals in a game with absolute royalty would have to be negatively valued

Yes, in my prototype engine, Kings got a big negative value and even Queens are valued negative.

Tenjiku Shogi is the most complex of the games you mentioned. Here I have no idea about good play, but if I had to bet on one algorithm to be competent for this game, I would chose McGrave, which I tested against the UBMF algorithm:



The algorithms implemented in Ludii are single-threaded, and possible cooperations with neural nets of open_spiel or Polygames don't really work so far, so I think Ludii won't become a threat to your human-beating engine Inferno (about which I have never read before).

The case with conditional branches would specify a single continuation for each of the three occupancies (empty, friend, foe).

Better to consider some more occupancies:
Number 4 is "transparent", that are pieces, which are like air (empty) for friendly sliders, but friends cannot land on them, and they can be captured.
And number 5 is the "Wall", which can serve to define holes/rocks on the board or to design irregular boards.

[hgm]

Capture generation

Captures would be generated in a staged way, per victim value class, in MVV order. This can be stopped when after searching one of the generated captures turns out to be a cut-move. Or, in all-nodes at depth <= 1, when you reach a victim with such a low value that further moves would be futile; you can then return a fail-low immediately. The code would look somewhat like:

Code: Select all

for(victim=classStart[vclass]; victim<classStart[vclass+1]; victim++) { // loop through value classes
  if(locals.childDepth <= 0 && p_value[victim] < futilityLimit)     // remaining moves are futile
    return locals.bestScore;                                        // prune them by returning a fail low
  int groupStart = nMoves;                                          // remember what we add
  int toSqr = p_loc[victim];
  int capt = attackers[stm][toSqr];                                 // doubly linked list of attackers starts here
  while(capt) {                                                     // there (still) might be attackers
    int rights = moveTable[capt].rights;                            // look what their move to here can do
    if(rights & F_CAPTURE) {                                        // it can capture!
      int piece = moveTable[capt].piece;                            // attacker
      int fromSqr = p_loc[piece];                                   // get its location from piece list
      locals.moveList[nMoves++] = ForgeMove(fromSqr, toSqr, piece); // add the capture to the move list
    }
    capt = moveTable[capt].next;                                    // next potential attacker (if any)
  }
  for(currentMove=groupStart; currentMove<nMoves; currentMove++) {  // search the moves generated in this stage
    SwapLVAtoFront(currentMove, nMoves);
    if(MakeAndSearch(currentMove, &locals))                         // MakeMove, Search, UnMake and alpha-beta stuff
      return locals.bestScore;                                      // move failed high; take beta cutoff
  }
}

Note that the common case is that moves have both capture and non-capture rights. So the condition in the inner loop is usually fulfilled, and the branch for the if-statement is easily predicted.

The value classes contain all pieces that are close enough in value that you'd rather try to capture the lowest-valued one with a lower-valued attacker than that you would capture the highest-valued one with a higher-valued attacker. In orthodox Chess that would for instance be Knights and Bishops.

The while-loop in general would not do many iterations; multiple attacks are usually rare (just a few squares on the board have them), many pieces will have no attackers at all, and often there will only be a single attacker. The LVA extraction is thus typically also very cheap.

Note that the attackers list make it comparatively easy to test whether a piece is protected; just examin protectors = attackers[xstm][toSqr]. If it is zero, the victim is unprotected, and you might as well skip the LVA sorting, as capturing with a low-valued piece is only useful when you expect to be recaptured. Unfortunately a non-zero value of protectors does not guarantee yet that the piece is proteced, because the move to the square might not have capture rights. To figure that out you would have to examin the rights, and in case they do not include capture, loop further through the list to see if other moves have it. This could be prevented by keeping counters for each board square of the number of white and black attackers. But these would have to be updated each time you associate or dissociate a move with/from a square.

But this might be reasonably cheap, something like attackCount[color] += rights & F_CAPTURE. The idea of the incremental update is that you would only associate / dissociate moves of the moved and captured piece, and the moves that are discovered or blocked(/activated), which is probably a lower number than the number of potential victims you will be trying to capture. (And for which you thus would want to know whether they are protected.) So it is preferable to move the work to the update.

The proposed code still has an omission; it only deals correctly with replacement captures. There could be locust captures as well, e.g. en-passant capture. For pieces captured as a side effect rather than by replacement the toSqr would be different from the square on which the victim is (and to which the move was associated.) It is in fact questionable whether a move marked as having locust-capture rights would result in a capture: this could depend on whether the remaing part of the move can be realized. E.g. a Checker would capture the piece on an adjacent square, but then has to move on to the empty square behind it. And if that square is not empty, the capture is also off the table.

Such "captures with mandatory continuation" would be followed by a second leg. So when they are encountered in the attackers list, we should generate all moves from the following leg(s), even if these go to empty squares. All squares where this leg could be potentially terminated (i.e. on an empty square if it has non-capture rights, on an opponent if it has capture rights, for a double capture) should now be used as to-square for the locust capture. To prevent duplicat generation of multiple captures we could test whether additional victims come before the locust victim in the piece list, in which case they would have already been generated earlier when that piece was victim.

But during those generations it should also have been noticed that there was a move upstream in the trajectory that did the locust capture as a side catch. What gives that away is that the capture is made by a move in the second leg; such legs must indicate in their rights whether they are continuation of a leg that locust-captured, so that the piece at their reference location could be added to the move as locust victim.

[hgm]

Hello HGM,
the infos from your messages are exciting
First I have examined the game Hekatomb which you mentioned. Although it differs from chess only in the start position, I could play it only in your Winboard GUI with Lc0 chess engine, all other pure chess engines crashed so far. Also I implemented it in Ludii and found out that, at least in the opening, the UBMF algorithm plays reasonable.

My guess is that they all get stuck in QS forever, trying to search 62 ply deep until all Queens are traded.

About BattleOTK:
Wow, that fast, how you implemented it in the ID engine!

Well, like I said the Interactive Diagram is very versatile. You pointed out an impressive display of variants from Dagaz on GitHub, and I pointed out a (by now no so complete anymore) list of variants implemented in the ID at CVP. But actually the lists don't tell the most important thing: how much effort it took to support any of these variants. For the ID this is almost nothing: just provide the board dimensions, a list of the participating pieces that specifies their name, move, image and start squares (the move and image possibly defaults for the most common (fairy) pieces), and perhaps some rule details. (E.g. whether stalemate is a win or draw, if there is a baring rule for some or all pieces, if multiple royals are absolute or extinction royalty, how many piece types can promote if that isn't just one, what they can promote to if that isn't all non-royals, how many ranks there are in the promotion zone if that isn't one. And optionally some colors for making the Diagram look pretty.) For a regular chess variant that is all, and it often takes only a few minutes to get the ID to play it.

In this case it was a bit more complex, because BattleOTK had a feature that wasn't supported by the ID, although the AI could in principle handle it. (Often the biggest problem is not how the program should handle a feature, but to find a user-friendly method through which this feature could be enabled.) So it took a little longer, and even some changes to the engine core to allow it to play without Kings without claiming game end.

Not only that, it beats also the Zillions engine! For a first attempt very successful:

Code: Select all

BattleOTK
ID engine (2.5 ply) vs Zillions (15 s/move) 

1. bxb4 fxf5 2. Nxb2-d3 Nxf7-d6 3. Bxb2-d4 Bxf7-c4 4. Rxb2-b1 Bxc4xd3 5. Bxd4-c3 Rxf7-f8 6. Rxd4xc4 Qxf7-h5 7. cxd3 Qxh5-g4 8. Rxc4-c5 exe6 9. Rxc5xc7 Nxd6xc4 10. Rxc7xd7 Rxf8-c8 11. Rxd7xd6 Nxc4xd6 12. Rxb1-c1 Qxf8-e8 13. dxc4 Nxd6xc4 14. Nxd3-e5 Nxc4xe5 15. Bxd3xc4 gxg6 16. Rxd3-h3 Kg5 17. Rxh3xh7 Qxe8xd7 18. Rxh7-h8 Nxe7-g8 19. Rxh8xg8#

Well done!

Oh, that is surprising. But I guess it is mostly a matter of evaluation. Zillions probably also tries to get as many Queens as possible as quickly as possible. The ID too, b.t.w.

Yes, in my prototype engine, Kings got a big negative value and even Queens are valued negative.

I also tried the ID against your prototype engine, and it was interesting to see how they had completely opposit strategies. The prototype tried to produce as many Knights as possible and then not move those, the ID tried to graze them off the board with a Rook, leaving a trail of immobile Queens. At some point the ID was so stupid to trap its only remaining Rook between Queens, while there had been many more Knights it could have captured. It then moved a Queen to create a King in a completely unsafe place, and was quicly checkmated.

I guess future move opportunity is indeed the main evaluation term, so that N > B > R > Q. I am not sure about Pawns; these don't guarantee move opportunities, as they are so easily blocked.

Tenjiku Shogi is the most complex of the games you mentioned. Here I have no idea about good play, but if I had to bet on one algorithm to be competent for this game, I would chose McGrave, which I tested against the UBMF algorithm:

Modern Tenjiku Shogi is extremely tactical, and MCTS is not so good at tactics. So I expect that conventional alpha-beta search would be the best algorithm.

The algorithms implemented in Ludii are single-threaded, and possible cooperations with neural nets of open_spiel or Polygames don't really work so far, so I think Ludii won't become a threat to your human-beating engine Inferno (about which I have never read before).

I have never released that engine. But it participated in the on-line championship at gamerz.net as bot_hachu, and one year even won it. I once wrote a very long thread on TalkChess to explain how it was designed, many years ago. (Much like I am starting here now.)

Better to consider some more occupancies:
Number 4 is "transparent", that are pieces, which are like air (empty) for friendly sliders, but friends cannot land on them, and they can be captured.
And number 5 is the "Wall", which can serve to define holes/rocks on the board or to design irregular boards.

Well, the Walls would be automatic, as there would also be walls around the board in the case of rectangular boards. And as to transparency: Tenjiku Shogi has what you could describe as 'levels of transparency'. There are pieces that can jump over arbitrary many occupied squares, but not always over each other, subject to a certain ranking. Lower rank is transparent to higher rank, and normal pieces could be assigned rank 1. There are then pieces of rank 2, 3, 4 and 5.

The ID implements this through a general mechanism called the captureMatrix, which can specify a relation for each pair of (colored) piece types independently. Such a relation can for instance be "A cannot capture B", "A changes into C when capturing B", but also "A cannot hop over B". Each capture or hop would always be tested against this captureMatrix, to see if it was allowed. Transparent pieces would be implemented by defining all pieces as hoppers, but then banning the hop over almost any piece type other than the transparent one.

[hgm]

Locust captures

Extracting the multiple captures from the attack map still seems problematic. For one, there is a question in which order we should search those compared to single captures. When there is a move that captures two minors, should that be searched before or after a move that captures a single Rook? It is hard to answer that, as raising the current evaluation is not the only factor in limiting the opponent's options (by making more of his captures futile). It also matters how dangerous the pieces are he is left with. And if the power he has is distributed over several pieces... Well, he can only move one at the time. A Rook is much better at doing plunder raids than a Bishop. That argues for capturing the most-valuable piece first, irrespective of any side catch with less valuable pieces. Since this is also simpler to implement, (and multiple captures will be quite rare in the tree anyway), we will take the latter approach.

This means the multiple captures come up naturally when we loop through the attackers list of the next-highest victim. The question is, how do we know the move that made this capture is a multi-capture, and what the other victim(s) are?

Multi-captures in general will be multi-leg moves, where the first leg of the path will end on the piece that will be captured as the side effect, and from there embark on the second leg which is able to capture another piece, but would have to stop there. So moves in the first leg should be allowed to continue after hitting a square occupied by a foe, the second leg shouldn't. This is why they would have to be different legs. There is the theoretical possibility of 'juggernaut' pieces, though, which can capture arbitrarily many pieces along a certain path. In principle their moves can be described as a single leg, every move in the trajectory having the option to continue from a square that contained a foe.

In any case moves should indicate in their rights field whether enemy occupation of the square allows termination there (i.e. a normal displacement capture), and / or whether that allows locust capture, i.e. continuation after capturing that piece. (Not to be confused with hopping, which is continuation without disturbing the piece.) If the locust-capture option exists, the path must be continued for finding a square the move is allowed to terminate on; every such square in the remaining path would produce a move that locust-captures the passed victim.

If such a termination happens at another square with enemy occupation, we are dealing with a multi-capture. If that second piece is of higher value (or in any case comes earlier in the piece list, which is sorted by value, but can act as a tie breaker for equal-valued piece) this multi-capture would already have been encountered earlier, and we can ignore it. If not, we add the double capture to the move list for the current move-generation stage (i.e. all captures of pieces in the current value class). During the sorting the value of the side catch should prevail over the normal LVA key.

But when we find a capture by a move of a later leg of a multi-leg move, the situation is more problematic. The earlier leg could already have made a locust capture. (But it could also have been an innocent change of direction triggered by the presence of an obstace in the path.) If we allow juggernaut trajectories, any capture along the path could have been preceded by another capture. How could we find out? We should either set up something to follow the trajectory backwards, or retrace it forwards starting at the piece (which every move in the trajectory does mention, but it doesn't mention which trajectory originating from that piece is the current one).

So it seems we need to store extra info in the move cells to make this possible. Note that ging through the trajectory step by step now is a waste of time, where doing that in the forward direction was necessary for also finding non-capture terminations of the locust-capture move. We are only interested in what the preceding locust capture was. So the logical solution is to include a field in every move cell for pointing out the previous cell on that trajectory where a 'destructive encounter' took place. When the move cells of a continuation leg get associated with squares during the incremental update of the attack map, this field should be made to point to the move cell responsible for this capture, e.g. as a byte-size (negative) offset in the moveTable (or a recognizably invalid value if there is no earlier victim). This applies to associations with empty squares as well as occupied squares, as squares could get occupied later.

On discovery of a capture in the list for the square of the victim whose MVV-wise turn has come up, we can then follow this pointer to the move cell that did an additional locust capture, without having to go through the list step by step. That move cell will tell us at what square that capture happened (through its relative location w.r.t. the dynamic 'reference'), and this info should then be included in the generated move. But again, only if this side catch comes later in the piece list. In case of triple (or more) capture, we can hop from locust victim to locust victim with the aid of these backward pointers.

[hgm]

Associating and dissociating trajectories

When updating the attack map, the moves of the moved piece from its new location would have to be put in the map. This is done by associating the move cells in its tabulated trajectory with the squares they now reach, by putting them in the doubly linked list for that square (and player). Something like this:

Code: Select all

int next[2*BOARDSIZE+MOVETABLESIZE];
int prev[MOVETABLESIZE];

void Associate(int start)
{
  do {
    MoveTarget *cell = moveTable + start;                   // next move target on trajectory
    int sqr = p_loc[cell->reference] + cel->leap;           // destination
    int occupant = board[sqr];                              // what stands there
    if(occupant == 1) return;                               // off board
    next[start] = next[sqr+color]; prev[start] = sqr+color; // insert in list of square
    prev[next[sqr+color]] = start; next[sqr+color] = start;
    p_loc[cell->nextRef] = sqr;                             // remember where next leg starts from
    if(occupant == 0) {
      for(i=1; i<n_empty; i++) Associate(empty[i]);         // do any side branches recursively
      start = empty[0];                                     // and continue on main branch
    } else {
      int n = (IS_FOE(occupant) ? n_foe : n_friend);
      for(i=1; i<n; i++) Associate(occup[i]);
      start = occup[0];
    }
  } while(start);
}

In this code the doubly linked lists are defined by separate arrays, next[] and prev[], which contain the index (in moveTable) of the move cells they connect. This instead of using real pointers, in order to save space (and reduce cache pressure) in 64-bit architectures. The disadvantage is that they can only 'point' to elements of the same data structure, which forces the list heads to be similar to the linked cells for efficient insertian and deletion of cells. The list heads must be indexed by square number and color, as for each square each color must have his own list.

This is solved here by taking these links out of the move cells, and put them in a single independent array, which contains the links for the list heads as well as the move cells. It uses the same index as moveTable; next[k] and prev[k] contain the links belonging to moveTable[k]. Beyond the end of moveTable it contains the links of the list heads; these are indexed by square number. These only need next[]. The variable 'color' that is added to the square number will always be so large that it brings the index beyond the range used for move cells, and will have a different value for white and black.

The doubly linked lists also needs a tail cell to which the 'next' link of the last cell in the list can point, and which occasionally will get its 'prev' link changed when a cell is inserted or deleted at the tail. This 'prev' link is never used for finding a cell, so that all lists can use the same dummy for it. To facilitate testing for the end of a list, we will use the cell with index 0 for that. This first cell of moveTable will thus not be used.

Another point that deserves explanation is the addition of a field nextRef to the MoveTarget struct. The move cells all contain a 'reference' field, that tells which entry in the piece list p_loc[] contains their starting square. For simple moves that would just be the piece to which the trajectory belongs. But continuation trajectories of multi-leg moves, that can branch off the initial trajectory in various places, need to refer to the square where they branched off. For uniformity the variable used for this purpose would also be stored in p_loc[], beyond the true piece list. When a path continues with such a second-leg trajectory, that variable would have to be initialized first. That is what this nextRef field is about: it specifies which variable will be used by the continuation legs as reference, and must be set to the current square before these continuation trajectories are processed. If none of the possible continuations needs a reference other than the one already in use, nextRef can be zero. This would do a dummy store into p_loc[0], which is harmless as there is no piece number 0, the code for an empty square.

dissociation - For dissociation we could do something similar. Except that you would have to delete the cell from the list. And it would not be necessary to set the next reference.

[MTaktikos]

Hello HGM,

[MTaktikos wrote:] ↑
[...] Hekatomb [...] could play it only in your Winboard GUI with Lc0

My guess is that they all get stuck in QS forever, trying to search 62 ply deep until all Queens are traded.

You are right. Have found an older SF derivat from 2021 where the QS problem can easily be reduced to reasonable deep. With 24 threads it can search 11 - 12 ply, what is much much deeper than Zillions does. The evaluation fluctuates between +900 and +1100 centipawns, and I am checking to exclude that it appears just due too low QS, my guess is that it has to be taken seriously and indicates a first player win in Hekatomb.
A game theoretical explanation is that White who has the first hit, takes the first Queen, Black has move for move to balance out this huge first-player advantage, and that probably White can manage it that the Queen exchanges come nearer and nearer to the black King, until the point where Black has to move his King and cannot anymore balance out his material disadvantage.
My plan is to make the search easier by disabling castlings and en passant, in the hope to get a more stable evaluation. When ready with my experiments, I will post the "Hekatomb Solver" here (of course, if I get convinced that it really shows a move combination that solves the game)

You pointed out an impressive display of variants from Dagaz on GitHub, and I pointed out a (by now no so complete anymore) list of variants implemented in the ID at CVP [...] For a regular chess variant that is all, and it often takes only a few minutes to get the ID to play it.

Happy that my recommendation was succesful, and also to found in the ID engine such a useful tool. For sure I will use it for testing the complex variants where Zillions' evaluation function has no clue, and the ID engine is more reliable.

About BattleOTK [...]
I guess future move opportunity is indeed the main evaluation term, so that N > B > R > Q. I am not sure about Pawns; these don't guarantee move opportunities, as they are so easily blocked

In my BattleOTK protoype I gave basically to Pawns about 900 centipawns (cp), Knights 800 cp, Bishops 200 cp, Rooks 10 cp, Queens -100 cp and Kings -800 cp. But in the next lines this eval is corrected by the spaces before the Pawns, and enemy pieces between own pieces, and so, as you indicated right, the most important evaluation term is the mobility

Modern Tenjiku Shogi is extremely tactical, and MCTS is not so good at tactics. So I expect that conventional alpha-beta search would be the best algorithm.

Since I never dared to write something so complex, and even until now I didn't know about the difference between Older and Modern Tenjiku Shogi, I cannot disagree, you are the expert here.

Code: Select all

: SELECT ALL
int next[2*BOARDSIZE+MOVETABLESIZE];
int prev[MOVETABLESIZE];

void Associate(int start)
{
  do {
    MoveTarget *cell = moveTable + start;                   // next move target on trajectory
    int sqr = p_loc[cell->reference] + cel->leap;           // destination
    int occupant = board[sqr];                              // what stands there
    if(occupant == 1) return;                               // off board
    next[start] = next[sqr+color]; prev[start] = sqr+color; // insert in list of square
    prev[next[sqr+color]] = start; next[sqr+color] = start;
    p_loc[cell->nextRef] = sqr;                             // remember where next leg starts from
    if(occupant == 0) {
      for(i=1; i<n_empty; i++) Associate(empty[i]);         // do any side branches recursively
      start = empty[0];                                     // and continue on main branch
    } else {
      int n = (IS_FOE(occupant) ? n_foe : n_friend);
      for(i=1; i<n; i++) Associate(occup[i]);
      start = occup[0];
    }
  } while(start);
}

This code is by far more clear and understandable than terrible bitboards. For the slightly faster move generation the bitboards offer, in them are hard coded foes and friends, maximal board sizes, sliding moves etc. They are the main limitation in Fairy-Stockfish and make it extremely difficult to define for example self-captures or boards of sizes bigger than 12x10

[hgm]

Bitboards are not really competitive for boards larger than 64 squares. This could be much faster. Especially in large games. Because it does things incrementally.

[hgm]

Move format and move list

I just had an idea. I was puzzling before about what the best move representation would be for in the move list. This is not trivial for moves that could capture an arbitrary number of pieces. But then it dawned on me: why should I represent the moves at all? If a procedure exists to extract all data that defines the moves from the up-to-date attack map, why cast that information in another form and store it in a move list? I might as well extract it directly from the attack map in MakeMove, when it is time to perform the move.

Of course we want to have some list to define the order in which moves should be searched. But it is enough to store a pointer to, or the index of the MoveTarget cell in the moveTable array to identify the move. An index in this table would not need more than 16 bits; the high-order bits could be used to represent a sort key (attacker value for captures, history for non-captures), so that the key+moveIndex words in the list can be easily sorted without moving around an unwieldly amount of data.

Once a move comes up for searching you would strip off the sort key to leave the moveIndex, and then let MakeMove() process moveTable[moveIndex], applying the board modifications it directly or indirectly specifies. The to-square can be calculated from the move cell's leap and reference fields (cell->leap+p_loc[cell->reference]), the from-square as p_loc[cell->piece]. Locust captures can be obtained by following the backward link to the move cell at the square where that capture takes place (moveTable[cell->lastLocust]), which might again contain a lastLocust link to the locust capture preceding it. So it would just be a matter of following these links iteratively, and calculating the square that the cell is associated with. That might sound like a lot of work, but following the links would not be very much more work than looping through elements of an array of locust squares that represents the move. And you would have to do it once anyway, for extracting the move from the attack table, and then copy the information to such an array before you could read it back that way. And by postponing this process to MakeMove time, you can hope that a beta cutoff makes that it hasn't to be done for most of the moves. The common case would be moves without any locust captures anyway.

Promotions - A possible complication is casued by promotions, in particular promotions with choice. The attack table describes how things move, not how they change type while doing so. A move that would result in promotion would thus have to be placed in the move list multiple times, with different promotion choice. There seems ample room for that in a 32-bit word: the upper byte could hold the sort key, the byte below it the promotion piece type, and the two low-order byte the index of the MoveTarget.

If we do staged move generation per victim in MVV order, we might need some 'lookahead' for finding non-capture promotion moves, which we want to be searched with the captures. This could be done by looking at the attack-map lists for all squares in the promotion zone, to see if any promotable pieces could move there. This seems a very wasteful process, though, and most positions would not have any promoting moves, and the promotion zone could be large. Perhaps the promotions should already be detected when updating the attack table, when a move cell in the trajectory of a promotable piece gets associated with a square in the promotion zone. Such moves could then be inserted in a special list.

[hgm]

Since this is an entirely new design, I am thinking of first implementing the simple case of orthodox Chess, as a proof of principle. This just has leapers and sliders, and a divergent piece / limited-range slider in the Pawns. For the moment forget about castling, e.p. and promotion; these could be added later, I just want to have an idea for the performance.

For Chess a Rook has 28 potential moves, 7 in each of 4 directions. (Never at the same time, of course.) Same for Bishops. (Well, you could do with 26, but which 26 wuld then be different for each Bishop, and the saving is not worth it. The Queen has twice that. So in total 6 x 28 = 168 poetential moves. King and Knights each have 8 moves. Pawns have 3, or in their initial position, 4. The issue of initial moves can be solved by duplicating the piece type, into a version with and a version without these moves, and changing the type when it moves. (This is more economical in terms of types then putting a 'virgin' bit in each piece, which basically duplicates all types.) So there will two types of Pawns, each in 8 copies, together they have 8 x 3 + 8 x 4 = 56 potential moves. That makes a total of 248 potential moves.

So the number of potential moves rises pretty steeply; for a small variant like FIDE already 258. Imagine what that would be on a 16x16 board with 78 pieces for each player, which all can promote to something else! In any case, it seems worthwile to keep the MoveTarget struct in the moveTable as small as possible, to not needlessly increase cache pressure. Therefore some redesign:

Code: Select all

typedef unsigned char Byte;

typedef struct {
  int leap; // to-square relative to trajectory start
  Byte reference; // (extended) piece list element that contains from-square
  Byte nextRef; // same for the continuation leg, to tel it where it starts
  Byte piece; // index of piece that makes the move in piece list
  Byte rights; // flags indicating what the move can do (capture, non-capture, continue...)
  Byte lastLocust; // any locust capture previously made on the trajectory
  Byte forks[7]; // offsets to possible continuations in moveTable
} MoveTarget;

Total size is 16 bytes. This limits us to 127 pieces per player, though. But for most variants that would be more than enough.

The code for walking a trajectory tree now becomes this:

Code: Select all

void Process(int start)
{
  MoveTarget *cell = moveTable;
  int cont = start;
  do {
    cell += cont;
    int sqr = cell->leap + p_loc[cell-reference];
    int occupant = board[sqr];
    if(occupant == 1) return; // off board
    ...
    if(occupant == 0) {
      if(cell->rights & F_EMPTY) {
        int i = 1;
        while((cont = cell->forks[i++])) Process(cont);
        cont = cell->forks[0];
      } else if(cell->rights & (IS_FOE(occupant) ? F_FOE : F_FRIEND)) {
        int i = 5;
        while((cont = cell->forks[i--])) Process(cont);
        cont = cell->forks[6];
    }
  } while(cont);
}

Flags in the 'rights' byte indicate for which occupancies the trajectory continues. All continuations are stored in the same array forks[], either from the start (for continuations at an empty square) or from the end (continuations at a friend or foe). A zero here indicates no continuation, and serves as a sentinel when we are looping through the possible 'side branches', to walk these recursively. The 'principal' continuations are stored in forks[0] and forks[6], and is walked in the routine itself. This scheme allows for maximally 6 different continuations for the empty and occupied cases together. This seems enough; in general moves stop at occupied squares, and when they branch there (e.g. for bifurcating hoppers), they usually do not branch on empty squares. The flags in the rights byte indicate whether the occupied continuations are for friendly or enemy occupation, or both.

In orthodox Chess all moves of course never continue from occupied squares (neiter F_FRIEND or F_FOE would be set), and in empty squares only continue for sliders that could still slide further. From an efficiency POV it is best to treat all sliders as limited range, giving them range 7, so that the 7th cell of the move specifies no continuation even on empty squares. In case the move would really extend 7 steps that would be more efficient than trying another step to discover that has left the board.