New project: very general engine for variants

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

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

Re: New project: very general engine for variants

Post by hgm »

Filling the moveTable

Since much of the trajectories is pre-calculated, initialization is a tough job. In the real project the engine should be configurable with the strangest moves, and the trajectories would have to be created with great variety, controlled by the move specifications in the variant definition. Most of the complexity of the engine will probably go in there. For the pilot project (orthodox Chess) the army is known at compile time, and creation of the trajectories can be hard-coded. Since leapers are basically limited-range sliders with a range of one step, we only need a routine to create a slider trajectory.

The design is as follows: All potential moves of each piece have a cell representing it in moveTable. There is an array trajectories[] that specifies where the trajectories formed by these moves start in moveTable, by holding the index. The trajectories of a given piece occupy a contiguous stretch in trajectories[], terminated by a zero. In the piece list each piece has an element p_moves[pieceIndex] that specifies where in trajectories[] the list of trajectories for that piece starts.

Code: Select all

// rights flags
#define F_FRIEND 1
#define F_FOE 2
#define F_EMPTY 4
#define F_CAPT 8
#define F_NONC 16

int p_moves[NPIECES]; // part of piece list
int piecePtr = 2; // first piece (index 0 and 1 reserved for empty squares and boundary guards)
int movePtr = 1; // moveTable[0] is a dummy
int trajectoryPtr = 0;

MoveTarget moveTable[512];
int trajectories[320];

int steps[] = { 1, 16, -1, -16, 15, 17, -15, -17,  // orthogonal (0-3) and diagonal (4-7) steps on a 0x88 board
               31, 33, 14, 18, -14, -18, -31, -33 }; // and hippogonal steps (8-15)

void AddSlide(int piece, int step, int range, int rights)
{
  int i;
  trajectories[trajectoryPtr++] = movePtr; // initiate new trajectory
  for(i=1; i<=range; i++) {
    MoveTarget *cell = moveTable + movePtr++; // add new move cell
    cell->leap = i*step;
    cell->piece = piece;
    cell->reference = piece;
    cell->nextRef = 0;
    cell->rights = rights | (i == range ? 0 : F_EMPTY);
    cell->forks[0] = 1; // on empty squares continue with next
    cell->forks[1] = 0; // no alternative continuation;
  }
}

void AddSlider(int a, int b)
{
  int i;
  p_moves[piecePtr] = trajectoryPtr;
  for(i=a; i<b; i++) {
    AddSlide(piecePtr, steps[i], 7, F_CAPT|F_NONC);
    trajectoryPtr++;
  }
  trajectories[trajectoryPtr++] = 0; // sentinel
  piecePtr++;
}

void AddLeaper(int a, int b)
{
  int i;
  p_moves[piecePtr] = trajectoryPtr;
  for(i=a; i<b; i++) {
    AddSlide(piecePtr, steps[i], 1, F_CAPT|F_NONC);
    trajectoryPtr++;
  }
  trajectories[trajectoryPtr++] = 0; // sentinel
  piecePtr++;
}

void AddPawn(int direction, int range)
{
  p_moves[piecePtr] = trajectoryPtr;
  AddSlide(piecePtr, direction+1, 1, F_CAPT);
  AddSlide(piecePtr, direction-1, 1, F_CAPT);
  AddSlide(piecePtr, direction, range, F_NONC);
  trajectories[trajectoryPtr++] = 0; // sentinel
  piecePtr++;
}

void Init()
{
  int i;
  trajectoryPtr = 64; // leave room for 16 Pawns (with 3 trajectories and a terminating zero each)
  for(i=0; i<2; i++) AddLeaper(0, 8); // Kings
  for(i=0; i<2; i++) AddSlider(0, 8); // Queens
  for(i=0; i<4; i++) AddSlider(0, 4); // Rooks
  for(i=0; i<4; i++) AddSlider(4, 8); // Bishops
  for(i=0; i<4; i++) AddLeaper(8,16); // Knights
  // this added 8x 8 + 8 x 4 = 96 trajectories, and 16 terminating zeros
  int forward = 16;
  trajectoryPtr = 0;
  for(i=0; i<16; i++) AddPawn(forward, 1), forward *= -1; // Pawns (alternating white/black
  piecePtr -= 16; trajectoryPtr = 256;
  for(i=0; i<16; i++) AddPawn(forward, 2), forward *= -1; // Double-push Pawns
}
A trick is used here to implement the Pawns initial double-push: there are two trajectory sets for each Pawn; one with the initial double-push, the other without. Initially the Pawns get the double push, for which the trajectory lists sit 256 places further in the trajectory table.

The idea is that MakeMove() would always AND the p_moves field of the moving piece with 0xff (but remember the original value, which would be put back by UnMake()). Which would have no effect on pieces with lists in the first 256 elements. So pieces with extra initial moves can be put just bejond that, and would then lose those moves when moving. The value of the mask that p_moves is ANDed with would depend on the total number of trajectories of the non-virgin pieces, and would be the next-largest power of 2.
User avatar
hgm
Posts: 27898
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: New project: very general engine for variants

Post by hgm »

MakeMove

To keep the code tractable, we divide up MakeMove() into several sub-tasks, delegated to subroutines. There will be routines Lift(sqr) and Put(piece, sqr) for removing and placing pieces, respectively. These will not only update the board and piece list for the location of the piece, but will also perform the update of the attack map. They will be used on the moved piece, but Lift() will also be used to remove any captured piece, in order to delete its moves from the attack map. And if it was an e.p. capture also the moves this discovers over the victim square. And Put() can also be used during position setup, for initializing the attack map.

Code: Select all

void Discover(int ptr, int color) { // extends trajectories that were blocked at an evacuated square
  int p;
  while((p = next[ptr])) { // step through all moves that hit this square
    MoveTarget *cell = moveTable[p];
    if(cell->rights & F_EMPTY) { // trajectory continues in empty square
      Associate(cell->forks[0]); // add downstream part of trajectory
    }
    ptr = p;
  }
}

void Block(int ptr, int color) { // cut off trajectories that are blocked when occupying square
  int p;
  while((p = next[ptr])) { // step through all moves that hit this square
    MoveTarget *cell = moveTable[p];
    if(cell->rights & F_EMPTY) { // trajectory continued when square was empty, but not anymore
      Dissociate(cell->forks[0]); // remove downstream part of trajectory
    }
    ptr = p;
  }
}

void Lift(int sqr)
{
  int piece = board[sqr];
  int trajectory = p_moves[piece];
  int color = COLOR_OF(piece);
  int t;
  while((t = trajectories[trajectory++])) Dissociate(t);
  p_loc[piece] = CAPTURED;
  board[sqr] = 0;
  Discover(sqr+WHITE, color);
  Discover(sqr+BLACK, color);
}

void Put(int sqr, int piece)
{
  int trajectory = p_moves[piece];
  int color = COLOR_OF(piece);
  int t;
  p_loc[piece] = sqr; // enter piece in piece list
  board[sqr] = piece; // and place on board
  while((t = trajectories[trajectory++])) Associate(t); // add moves of placed piece to attack list
  Block(sqr+WHITE, color); // remove the slider moves it blocks of white...
  Block(sqr+BLACK, color); // ... and black sliders
}

void Replace(int sqr, int piece)
{
  int trajectory = p_moves[piece];
  int victim = board[sqr]; // old occupant
  int t;
  p_loc[victim] = CAPTURED; // remove old occupant from piece list
  p_loc[piece] = sqr; // enter piece in piece list
  board[sqr] = piece; // and place on board
  while((t = trajectories[trajectory++])) Associate(t); // add moves of placed piece to attack list
  trajectory = p_moves[victim]; 
  while((t = trajectories[trajectory++])) Dissociate(t); // remove moves of replaced piece from attack list
}

void MakeMove(int m)
{
  MoveTarget *cell = moveTable[m];
  int fromSqr = p_loc[cell->piece];
  int toSqr = p_loc[cell->reference] + cell->leap;
  int victim = board[toSqr];
  Lift(fromSqr); // remove moved piece
  // place piece in new location:
  if(victim) Replace(toSqr, piece); // for capture
  else Put(toSqr, piece); // or non-capture
}
Note that there are different routined for placing a piece on an empty square, and replacing the occupant of af a square. The difference is in that you have to block slider moves over the square in the former case, while during replacement these were already blocked, but you have to remove the moves of the piece that is no longer there.

Associate and Dissociate would do the same tree walk along the indicated trajectory, one to insert the move cells to the squares the trajectory passes through, the other to delete these.

The Lift, Put and Replace routines are highly simplified here for use in the pilot project: they only assume every move cell in the trajectory can only have a single continuation, for the case of an empty square. So Discover() doesn't check for other continuations that should be extended (e.g. if the move of a Xiangqi Horse on e3 would be discovered at e4, continuations would go to d5 as well as f5). It also doesn't test for continuation in case of an occupied square; evacuating the square would have cut off such continuations, as apparently a hopper move was using the former occupant of the square as a mount (e.g. a Xiangqi Cannon). So eventually Discover should be able to block trajectories as well as extend them, and take account of the fact that there could be more than one of each. Likewise, Replace() should tahe notice of the color change of the occupant, as there could be continuations that only are used for one color and not the other. Even a capture could discover or block such color-selective hopping on the to-square. Each such routine should take notice of the full change in occupation, and furthermore test whether that change really causes the continuation to be different. (E.g. a piece that can hop over arbitrary many other pieces could use the same continuation, whether the square is empty or occupied. It would be wasteful to first dissociate that continuation, to immediately associate it again.)

In orthodox Chess all these complications do not occur, so for the pilot project the given routines suffice.
User avatar
xenos1984
Posts: 6
Joined: Mon Feb 19, 2024 7:50 am
Full name: Manuel Hohmann

Re: New project: very general engine for variants

Post by xenos1984 »

This sounds like a very nice project!

Are you also considering chess variants with "wrapped around" boards, such as cylinder, torus etc.? Such variants can still be represented by a simple square board, but with even more extended movements of pieces. For example, ranging pieces which hit one edge of the board can go "off" that edge and enter again on the opposite side of the board, possibly also with a changed direction. I have created some drawings here:

http://xenos1984.github.io/BoardGames/Chess/

Some playable rules for Ludii and Zillions of Games (work in progress) are here:

https://github.com/xenos1984/BoardGames/

Also regarding the JavaScript you mentioned which shows the motion of fairy chess pieces, I found it on chessvariants.com and this is really nice work. I am also trying to visualize such "wrap around" boards, so far only as a very simple tool which "unwraps" them on an infinite plane, but perhaps one could even show the motion of fairy chess pieces on such a board. So far I only have the torus written up, others are still work in progress.

http://xenos1984.github.io/BoardGames/G ... Torus.html
User avatar
hgm
Posts: 27898
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: New project: very general engine for variants

Post by hgm »

Yes, wrapping should be supported too. The Interactive Diagram, which we are trying to implement in a stronger version, does supports both cylinder and toroidal wrapping (by prefixing the move descriptiors with o or oo, respectively).

Cylinder and toroidal boards

I had not really thought about this. I suppose it could be done by making wrapping moves two-leg moves, where transition to the second leg is triggered by hitting the board edge. The reference for that second leg would be the point where the first leg left the board. So the leaps it specifies should just add/subtract one board width from what a normal continuation would do in a second leg after hopping over a piece. That makes it purely a matter for the initialization; during play it would not have to be treated any different from other two-leg moves.

I have never payed very much attention to wrapping variants; I suppose the interface for those could be improved by a special display routine, which allows you to see some of the wrapping files (say two extra files left and write, on squares of a more greyish shade), and buttons to manipulate a 'sideway offset'. This would not be very hard to implement in the Interactive Diagram.

E.g. for a Cylinder Bishop on an 8x8 board with 0x88 layout the NE diagonal slide would be stored in movetable with leap and empty/off-board continuation as:

Code: Select all

 17 1/7
 34 1/6
 51 1/5
 68 1/4
 85 1/3
102 1/2
119 0/0
 -8 1/0
  9 1/0
 26 1/0
 43 1/0
 60 1/0
 77 0/0
The first seven specify the leap w.r.t. the piece, with continuation to the next for empty squares, and to the 8th cell when off board. Only the 7th target has no continuations; it can only be rached on the main diagonal, and no wrapping would occur there.

Say the Bishop stands on square number 4 (e1), which then is the reference for the first leg. That would then be associated with squares 17+4 = 21, 34+4 = 38, 51+4 = 55. The 4th move cell would map to 68+4 = 72 = 0x48 = i5, which is an off-board square, and cannot be associated. This terminates the first leg, but like all other cells it would store its square number in p_loc[cell->nextRef] in the routine that associates the trajectory, even though it doesn't go into any double linked list. The path then follows the continuation for the off-board case, 4 squares further in moveTable, which specifies -8 as leap, and thus maps to -8 + 72 = 64 (a5), as the second leg specifies the p_loc element set by the last move cell in the first leg as reference. As long as the squares are empty the path then continues with 9 + 72 = 81 (b6), 26 + 72 = 98 (c7), and 43 + 72 = 115 (d8). The next move cell maps to 60 + 72 = 132 = 0x84, which is again off board. This causes termination of the path, as the off-board continuation is specified as 0 in this move cell.

The lesson is that the move cells would also need to specify continuations for the off-board case. And that there are actually two types of off-board cases that we want to behave differently: when the first leg would have gone to the 9th rank, rather than the i-file, it should not have continued with the second leg. Even on a toroidal board different continuations would have been needed for the two cases.

To easily distinguish those cases, we will use 3 different kinds of boudary guards on the off-board squares, with encoding 1 to 3. The codes for real pieces will thus start at 4. By testing the 1- or the 2-bit we can deduce along which edge we left the board.
User avatar
hgm
Posts: 27898
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: New project: very general engine for variants

Post by hgm »

(Quiescence) Search

The reason for having the attack map is to make QS fast, even in large games. Engines typically spend most of their time in leaf nodes, generating moves to come to the conclusion that none of those qualifies for being searched. (Well, I am not talking about NNUE engines, which spend their time on running the neural net for evaluation. Neural nets are only useful if they are trained by feeding them millions of games, and the goal of this project it to specify how the pieces move, and then one minute later use it to analyze positions from a game. So the evaluation will be very rudimentary out of necessity; it is pointless to have subtle terms in there that are not tuned.)

In particular all-node leaves can be costly; cut-nodes leaves will often fail high by evaluation alone. And if not, the cut move will often be the capture of the most-valuable victim. To speed that up it is important to quickly find the MVV in the piece list, and then get the attacks on it from the attackes linked lists in the attack map. For all-nodes the time spent on them is cut by staged capture generation and bulk futility pruning; when running through the opponent piece list in MVV order, you can stop when you reach the first futile victim, and won't have to generate captures on that, or any lower-valued piece. In all-node leaves all (attacked) victims will be futile.

It will be usefull to detect this situation as quickly as possible, as updating the attack map is relatively costly. So it would be wasteful to update the attack map, only to discover that there is nothing to do in the current node, and restore the map in en equally costly way to the original state. To judge whether there are moves to search requires the moves of the side -to-move to b available in the attack map, but not so much the moves of his opponent. We can therefore first update the stm's half of the map. And this usually is the least work: for the opponent, who just moved we would have to delete the moves of the moved piece from its old location, and add those from the new location, in addition to discovering and blocking moves of some other pieces. For the stm the preceding move only made the move of the capture victim disappear, in addition to discovering and blocking of his other pieces.

And for figuring out whether we have non-futile captures, it is not really necessary to delete these of the captured piece. We could leave them in while looking for captures, and when we seem to have found one, check whether it was made by the capture victim, and discard in and look on if it was. It would be quite a coincidence if the first capture on the most-valued piece that is attacked was a capture of last move's victim. So usually we would do the test only once, and approve the move as a result.

The procedure thus consists of runnting through the opponent's piece list, high value to low, testing the list of enemy attackers on its square, until we find a non-empty one. Then we step through move cells the list ignoring those without capture rights. (In orthodox Chess that could be at most one, by a Pawn in the same file.) If we find one, we have a capture, and then we test whether the piece that made it is listed as captured. Usually it won't be, and we are done. But if it is we can step through the remainder of the list without such testing (assuming a piece won't have two moves to the same square). If it was the only capture in the list, we must now step to the next victim, and do the same there.

Code: Select all

  int low = FUTILITY_LIMIT(alpha - currentEval); // determine lowest-valued non-futile piece type
  DiscoverBlock(stm, precedingMove);             // update stm part of attack map for discovered and blocked moves
  for(victim=HIGH; victim<=low; victim-=2) {     // loop through opponent pieces, high to low value
    int sqr = p_loc[victim];
    if(sqr != CAPTURED) {                        // ignore victims no longer on the board
      int ptr = next[sqr+stmColor];              // list head for stm moves
      while(ptr) { // step through attackers
        MoveTarget *cell = moveTable[ptr];
        if(cell->rights & F_CAPT]) {             // the move to this square can capture?
          if(p_loc[cell->piece] != CAPTURED) goto found; // break out of two levels of loops
        }
        ptr =  next[ptr]; // next attacker
      }
    }
  }
  
notfound:

  BlockDiscover(stm, precedingMove); // undo what DiscoverBlock() did
  return FAIL_LOW_SCORE;
  
found:

  // finish update of stm part of attack map
  DeleteMoves(precedingMove.toSqr, precedingMove.victim); // remove moves of last move's capture victim
  
  // update opponent part of attack map
  DiscoverBlock(xstm, precedingMove);
  DeleteMoves(precedingMove.fromSqr, precedingMove.mover);
  AddMoves(precedingMove.toSqr, precedingMove.mover);
  
  ... // search code, starting with capture generation
So each QS node starts with a prequel that logically really is part of MakeMove. This minimizes the amount of work spent on the attack map in leaf nodes. Only if there are non-futile captures to search (i.e. the node is not a leaf), the largest part of the attack-map update is finished. Other wise, only the minor part has to be undone.

Note that in orthodox Chess, if the preceding move was a capture, DiscoverBlock() only has to deal with discovered moves over the from-square. (And, very rarely, over the e.p. square.) A capture in orthodox Chess never blocks anything. After a non-capture, however (and you can enter QS through a non-capture!), we would also have to account for blocking of moves over the to-square. (But we would not have to delete any moves of a capture victim!) We could consider to treat this in the same way as the deletion of a capture victim's moves: postpone it, but for every capture you then find test if it was by a a move that really should have been blocked. This could be facilitated by letting each move cell contain a number hat uniquely identifies the trajectory it belongs to; the attackers list for the square that was occupied would then tell you which trajectories were blocked, and the attackers list of the victim would tell you which trajectory makes the capture, and you could compare the two. Still a bit of a hassle, though, as there could be multiple (e.g. crossing) trajectories. But you could still maintain an array that contains a flag for each trajectory, and set the flags for those that are blocked, and then test the flags for the trajectories that make captures. In chess only ~5% of the searched moves are non-captures, though. So it is questionable whether these complications are worth it.

A good question is how evaluation and stand pat fit in. Ideally it would have been done before any of this, so that we can even skip updating the stm discovered moves in case of a stand-pat cutoff. But an exact evaluation might require the full update, as the mobility term would be a side effect of this. But we could use 'lazy eval', which basically is futillity pruning of stand pat: if an approximate evaluation without the more subtle and expensive terms is too far below alpha, we simply forget about it. It will never be so far above beta we can forget about it, because then futility pruning in the parent node would have prevented we came here. So we would have to resort to a full evaluation after a full attack-map update if currentEvaluation and alpha are close. This could also be tested before the shown code, to jump directly to 'found' for completeing the update, and then decide again whether a full evaluation stands any chance.
User avatar
hgm
Posts: 27898
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: New project: very general engine for variants

Post by hgm »

Piece list and Promotions

I am still in doubt as how I should treat promotions. The piece list contains a pointer to the set of trajectories that defines how the piece moves. So in principle you could replace the pointer to make it move differently. But in general changing the move should be accompanied by a change in piece value, PST, Zobrist keys. (Exceptions could be a piece losing an initial move, or a piece that swaps type on every move.) So it might be better to prepare anothe entry in the piece table for the promoted type, that has all this pre-initialized. Then you would only have to replace the piece index on the board to perform the promotion. Disadvantage is that you need more entries in the piece list, and the supply of those was already tight if we want to stick to single-byte encoding. Tenjiku Shogi has 78 pieces, almost all promotable to another type, and that would exceed the 126 entries available per player.

But we want the piece list to be sorted by piece value. So replacing all piece data on promotion (which is likely to be rare in the tree) would lead to the piece being in the wrong location. OTOH, reserving multiple entries for a piece and all its potential promoted forms presorted by value in the list might lead to a very sparse piece list. Which slows down stepping through it.

It thus seems useful to use a more flexible data structure for the piece list. We could again use a doubly-linked list. Captured pieces can then easily be deleted from it, and you only have to follow the list pointers to step through all present pieces. But that only helps if the list is sorted by value. When I delete values from a sorted list it will remain sorted, but when I have to insert a new piece (e.g. resulting from a promotion), I have a problem.

The peiecs only have to be sorted by value group, though. So we could use a two-level organization: an array of value groups, each value group consisting of a doubly linked list of piece entries, and its list head. We can then insert new pieces that belong in that value group between the list head and the old first element. This leaves the order of the pieces within a value group indeterminate, but that doesn't matter, as we want the captures of those pieces to be sorted by attacker value, not by their own value. There will be far fewer value groups then there are pieces (especially in large variants); for Chess there are only 4, against 16 pieces. The chances that a value group is empty are typically smaller than that a piece is captured. (Except for the Queen, which is a singleton.)

So looping through all elements of the value groups for capture generation will never waste much time on empty value groups. Insertion of a promotion piece in the value group it belongs to will be easy, deletion of a captured piece even easier. Within each value group we can step trough the linked list of pieces in it, without encountering any piece that is captured. Each piece will have its list of enemy attackers, and in a capture-generation stage all captures in it will be collected for sorting by victim value minus attacker value, and subsequently they will be searched.

Code: Select all

for(group=0; group<NGROUP; group++) {   // loop through value groups
  int start = nMoves;                   // remember where this stage started
  int victim = group + offset[xstm];    // index of list head in array of piece-list links
  while((victim = nextPiece[victim])) { // loop through victims in value group
    int victimValue = p_value[victim];  // sort key
    int toSqr = p_loc[victim];
    int ptr = sqr + color[stm];
    while((ptr = next[ptr]])) {         // loop through attackers
      MoveTarget *cell = moveTable + ptr;
      if(cell->rights & F_CAPT) {       // move can capture
        moveList[nMoves++] = ptr | (victimValue  - p_value[cell->piece]) << 24; // put sort key in upper byte
      }
    }
  }
  Sort(start, nMoves);                  // sort the extracted moves
  for(currentMove=start; currentMove<nMoves; currentMove++) {
    if(MakeAndSearch(currentMove & 0xffffff) goto cutoff;
  }
}
// handle non-captures
User avatar
hgm
Posts: 27898
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: New project: very general engine for variants

Post by hgm »

Divergent pieces

Pieces that have other captures than non-captures can have trajectories that never make captures. The cells in such trajectories don't really have to be inserted in the linked lists of the square they are associated with, as these lists only serve to quickly get attackers of the victim on that square. In general it can be useful to put moves without capture rights in these lists, if they can make a capture further down-stream. Otherwise we could not dissociate that capture when the trajectory gets blocked on a square where it cannot capture. But for trajectories only consisting of non-captures we don't need to know whether these are blocked; we would ignore them anyway. In orthodox Chess this happens for the double-push of the Pawn; it does not have to be put in the attack map.

So it could be useful to have a flag (in the rights or transit Byte) that indicates the remainder of the trajectory is devoid of capture rights. The Associate and Dissociate routines could use that as a stop signal when they step through the trajectory.
User avatar
xenos1984
Posts: 6
Joined: Mon Feb 19, 2024 7:50 am
Full name: Manuel Hohmann

Re: New project: very general engine for variants

Post by xenos1984 »

cylinder / torus ...

Indeed, the method using boundary guards and having pieces which leave the board on one edge reappear on the other edge would work well for a cylinder or a torus. For a Möbius strip or Klein bottle one also needs to take care of the fact that the edges are turned upside down before gluing, which then also affects the direction in which the pieces are moving. For example, if one glues the left and right edge to form a Möbius strip instead of a cylinder, a bishop moving NE from e1 would move e1-f2-g3-h4-a4-b3-c2-d1, and thus SE after crossing the edge.

spawning pieces

In games like Locusts or Amazons also new pieces appear on the board, so I think this is another interesting aspect to be taken into account. For Amazons, these "new pieces" are non-movers or blocks, so they can just be treated as marking positions as occupied and unavailable for movement, but in Locusts the new pieces have their own way to move.
User avatar
hgm
Posts: 27898
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: New project: very general engine for variants

Post by hgm »

Since the need to specify three different types of continuations for hitting boundary guards sort of wrecked my earlier design of the MoveTarget structure, and since it would not work for Möbius wrapping anyway (where there is no fixed step between the square where you leave the board, and where you re-enter), it might be better to implement wrapping in an independent way. There still would be 3 flavors of boundary guards, but if a flag in the move cell specifies wrapping, it could just call a globally defined routine for calculating a new reference square where it should re-enter, (and whether it should re-enter), and just continue with the move cell that is 1, 2 or 3 places further in the table when it should (also determined by this routine), all depending on the flavor. So a cylinder board or Möbius strip would indicate abortion on vertical and diagonal boundary guards, and continuation with the immediately following move cell according to the globally applicable mapping on sideway boundary guards. I don't think it would be worth it to support having some pieces wrap one way, and other pieces in another; this wrapping is supposed to be a board property.

Another flag that would allow passing through off-board squares could just indicate it is allowed, and then always continue with the immediately following move cell in the moveTable. This would presumably step back to where the move came from to get back on board, and that cell could then specify what to do next, now that it is verified that you are on the extreme end of the slide. E.g. a Reflecting bishop could now take a 90-degree turn, which can be done in two directions, but one of these would immediately leave the board again, and this time not be allowed to do that. An Advancer could just terminate its move there as a non-capture, having verified there was nothing to capture because the next square on the path was off board.

This approach has the advantage of not having to specify any continuation offset for the off-board cases, and thus not bloating the MoveTarget struct. But by now we need so many flags that we should have two Bytes for those. Because I really would like to keep the sizeof MoveTarget to 16 bytes, that means we have to sacrifice yet another element of forks, leaving only 6. This still allows up to 5 different continuations for the on-board cases in total (plus one terminating zero). If I take a look at pieces I encountered in variants, having two continuations on empty squares is common (e.g. the Xiangqi Horse), having 3 occurs now and then (hook movers in the large shogi variants), and I only know one piece with 5 (the Sissa, switching to either all orthogonals or all diagonals, or stay on the ray it was already moving on). All these pieces terminate on occupied squares. For pieces that do continue there (hoppers) they would normally continue in a single way; bifurcating hoppers can fork off in two directions. But these pieces have only a single continuation on empty squares. So it seems 6 entries in forks[] is enough.

I don't know Locust. But Amazons is not really a chess variant. After some time it becomes a combinatoriral game, breaking up into many different and independent areas, and you would need a completely different AI to play that well.
User avatar
hgm
Posts: 27898
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: New project: very general engine for variants

Post by hgm »

This thinking about alternative methods for wrapping inspired an idea for improving the encoding of the trajectory tree. Instead of explicitly specifying an offset for each potential continuation, the offsets could be implied as N+1, N+2, N+3, ..., with N a single specified offset. The only other thing that would have to be specified is how many of such continuations are available for the empty and for the occupied case.

Code: Select all

typedef unsigned char Byte;

typedef struct {
  int leap;          // board step from reference location
  Byte reference;    // index in (extended) piece list ofreference location
  Byte nextRef;      // same for next leg of move
  Byte piece;        // piece-list index of piece making the move 
  Byte rights;       // flags indicating for which occupancy we can terminate
  Byte transits;     // flags indicating for which occupancy we can continue
  Byte lastLocust;   // (negated) offset to cell where locust capture took place
  Byte n_cont;       // number of continuations from empty square
  Byte offset;       // start of continuations (as offset)
} MoveTarget;
When visiting the move cell during Associate, the square it is associated with is stored in p_loc[cell->nextRef], and in the next leg of the trajectory it will be retrieved as p_loc[cell->reference]. Locust capture (or other destructive encounters) must cause transition to a new leg, and p_loc[cell->reference] will contain the capture square. The board will tell us what piece was there (and if the square was empty we will be dealing with the square where the capture victim should be unloaded). But it will not tell us if this was the only locust victim! It could be that the associated move cell also specifies a lastLocust, at its reference square. But it might be hard to find that cell from the square; it should be in the linked list associated with it, but there could be many cells in this list, and we don't want to have to search. So we also store the offset of that move cell in move table, i.e. how many entries we have to go backwards to arrive at it. For capture of many pieces we can then leap backwards from cell to cell, to collect all upstream locust victims during capture generation.

The n_cont byte packs two 4-bit counters, which tell how many continuations there are if the associated square is empty (lower nibble), and how many if it is occupied (upper nibble). The tree walk of a trajectory then works as follows (ignoring the off-board cases):

Code: Select all

void Process(start)
{
  int ptr = start;
  while(1) {
    MoveTarget *cell = moveTable + ptr;            // next move cell
    int sqr = cell->leap + p_loc[cell->reference]; // number of associated square
    int occupant = board[sqr];                     // piece that stands there
    ...                                            // process the cell
    p_loc[cell->nextRef] = sqr;                    // initiate continuation leg
    if(occupant == 0) {                            // square is empty
      int n = cell->n_cont & 0xF;                  // nr of continuations for this
      if(n == 0) break;                            // none: terminate
      ptr += cell->offset;                         // skip to continuations
      while(n-- > 1) Process(ptr++);               // treat the extra ones recursively
      // the one that is left will be treated by this loop
    } else if(cell->transits & (IS_FOE(occupant) ? F_FOE : F_FRIEND)) {
      int n = cell->n_cont;
      ptr += cell->offset + (n & 0xF);             // skip to continuations (ther will be at least one)
      while((n -= 16) >= 16) Process(ptr++);       // treat the extra ones recursively
      // the one that is left will be treated by this loop
    } else break;
  }
}