Duck Chess

[xr_a_y]

Thanks a lot !

Any chance I can get a linux version ? or the source ?

[hgm]

I am not sure the Alien Edition fork would build as XBoard. It is a pretty old fork. It failed to rebase on a modern XBoard, because the front-end of the latter has completely been changed, with many files deleted and replaced by others. And many of the enhancement have been done in the Windows front-end.

It will take some time to transfer the patch to Linux and push it to the repository, as I did all the work on Windows (where I don't have git). The version I had there also contained numerous changes I had made for private use (to better support Tenjiku Shogi), so I will have to sort out which changes belong to which patch, in order to commit them in a sensible way.

[Edit] Umm, there isn't any alien branch on my Linux VM, although it exists in my repository. That doesn't bode well; apparently I have never even tried to build it as XBoard. Anyway, the source files that I had changed compared to the aliennewer branch in my git repository at http://hgm.nubati.net/cgi-bin/gitweb.cgi (common.h, backend.c, moves.c, parser.c, winboard.c and winboard.rc) can all be downloaded from http://hgm.nubati.net/transfer/ .

[hgm]

Well, it appears that the Alien Edition somewhat works for XBoard even in the GTK build. The version I started from in Windows was a lot older than I imagined; there were zillions of small layout changes with the latest version in the aliennewer branch of the repository. I now transferred all back-end changes I made for Duck Chess to the aliennewer branch, and it seems to work. The Duck is displayed as a blacked-out square. (This is actually the internal representation, but in the XBoard front-end I display a DarkSquare as a Duck image in this variant (and then only at the 49x49 square size). For XBoard I have no graphics yet. But it should work.

[dangi12012]

So now that you guys have adapted your code -
what is the average branching factor of duck chess?

[hgm]

That is hard to say without having an engine. N.E.G. has EBF = 0.

[hgm]

The 'aliennewer' branch in my on-line XBoard git repository now also includes an SVG image of a duck, which will be displate for (normally blacked out) 'holes' in the board.

[hgm]

What I missed in the previous description of the algorithm is that the exceptional scores of a position are never higher than the common score. This because the common score returned by a node is the lowest score in the bundle that was maximized over FIDE moves (because that is where the opponent would have placed the Duck, if it was not already there). And the exceptional score is the next lowest. After negamaxing these returned scores, the exceptional score will thus be equal or lower than the common score.

This limits the number of exceptions in the maximum-so-far. The move with the largest common score will have raised the scores of all elements in this bundle to that level, except for the elements that would have blocked this move (which can at best have the second-best common score), and the exception in the move itself. And the longest move in orthodox Chess touches 7 empty squares. So there can be at most 8 Duck locations for which the score is not raised to the common score.

This simplifies the maximization procedure. Of course this procedure would be most simple if we first collected the score bundles of all moves; then we would simply pick the one with the maximum common score, and would only have to determine exceptional scores for the elements where this move was blocked, or the exception for that move. But that would make it impossible to do beta cutoffs. So we want to immediately update the maximum-so-far bundle as the score bundle from the newly searched move comes in.

We can distinguish three cases:
1) The new common score is higher than the common score of the maximum-so-far. All exceptions in the latter that do not block the new move, and are not the exception in the latter's score bundle, will cease to be exceptions. Existing exceptions that do block the move are not touched. Elements that block the move, but were not exceptions, now become exceptions, as they must keep the old common score. Finally the exception in the new score bundle, if it did not block the move, will become an exception if it wasn't one yet (with a score equal to the maximum of the exceptional score and the old common score), or gets its score updated (to the maximum of its old and new score) if it was.
2) The new common score is exactly equal to that of the maximum-so-far. This is very much like case (1), except that non-exceptions that block the move don't become exceptions, but just can keep the (unchanging) common score.
3) The new common score is lower than that of the maximum-so-far. We only have to go through the exceptions in the latter to see whether there score should be increased to the new common score (if they do not block the move and are not the exception of the new bundle), but even in that case they will remain exceptions. If one of the existing exceptions happens to be the new exception, and does not block the move, its score might have to be increased to that of the new exception.

We see that in all cases we have to loop through all exceptions in the maximum-so-far bundle. Sometimes we also have to loop over elements that block the new move, but where not exceptions yet. This could be implemented conveniently as follows:
We keep the exceptions in the maximum-so-far bundle in a doubly linked list of scores, implemented by (local) arrays scores[65], next[65] and prev[65]. The index is the square on which the Duck must sit (just before the FIDE move) for that score to apply. The 65th element can act as list head and tail (so it is really a circular list). The arrays do not have to be initialized, except for the list head, for which the 'pointers' next[64] and prev[64] point to itself (i.e. are set to 64) to represent an empty list. When an exception gets added we link it into the list (next[new] = next[64]; prev[new] = 64; next[64] = new; prev[next[new]] = new;) and set its score. By virtue of the double linking exceptions are easily deleted (next[prev[old]] = next[old]; prev[next[old]] = prev[old]. We can then easily loop through all exceptions by following the next[] links until we return to the list head. They can then easily be deleted if they must to be.

Looping through elements that block the new move to add them as exceptions is harder, as there is no way to see whether an element already is in the exception list without initializing the entire array. But during move generation we determine the squares the move passes through, e.g. as a bitboard. When we loop through the exception list, which we have to do in any case to remove exceptions or udate their score, we can clear the bits for blocking squares that already were exceptions. We can then loop through the remaining bits with the certainty that none of these squares was already in the exception list, and thus simply add them when this is needed (like in case 1).

Even for mailboxers who use 0x88 square numbering there is a reasonably cheap way to do this: keep a table indexed by the difference of from- and to-square of the move that contain a mask indicating how many squares the move passed over (1 for direct leaps, and 3, 7, 15, 31, ... for the more distant moves). Keep a similar table where you can look up the direction of the move (0-7). When we are treating a move we can then look up in which direction it goes. For each of these directions we have a table similar to the mask table, but encoding the distances as ~1, ~2, ~4, ~8, ..., and only for a slide in a single direction (and ~0 for all other squares). By consulting the table appropriate for the direction offsetted with the from-square of the move, we can see which square in the path of the move it was (if any). So if an exception for square s exists, we can AND mask2[direction][s-fromSqr] with the mask originally obtained from mask1[toSqr-fromSqr] to clear the bit of the square in the path that corresponded to s. Bits that remain after we have done this for all s in the exception list can be extracted, and the corresponding elements (fromSqr + (bitNr+1)*step) then added to the exception list. This algorithm requires 10 tables of 240 elements, but since the elements are bytes, this is similar in size to a lookup table of bitboards for indicating which squares a given move passed over.

A leaper move can only be blocked on its to-square, so there it is easier to just compare s with toSqr, and set a flag on a match, which we test afterwards to determine if the toSqr already was exeption or not. This is similar to what we should to for determining whether the exception of the new score bundle already was in the exception list.

Since the common score we are going to return for this move is the lowest score in the bundle, it must be the score of an exception (as the common score is always the highst score in the bundle). So while we loop through exceptions we might as well determine this minimum in the process. This can be used to decide when we can take a beta cutoff.

All this sounds like a big hassle compared to the usual determination of the maximum of a scalar score. But I have the feeling that the number of exceptions in the maximum-so-far will on average not be very high. Many nodes will not even return an exception to their common score, because there were two Duck locations that gave the same lowest score. This tends to happen every time when the best FIDE move can be blocked in two places, and no other relevant moves (in particular not the second-best move) go over these squares. And contact captures cannot be blocked. So if a contact capture returns the best common score so far, only the returned exception could remain in the exception list (and perhaps it does not even have one). Most move will have far fewer than 7 squares where they can be blocked.

Code: Select all

// on entry Search
int scores[64];
char next[65], prev[65];
next[64] = prev[64] = 64;
int commonScore = -INFINITY;

// in move loop
  MakeMove(move);
  new = Search(...); // recursive call
  UnMake();

  new.common *= -1; // negamax common and exception scores
  new.eScore *= -1;

  int d = direction[move.to - move.from];
  char m = mask[move.to - move.from];
  char *t = mask2 + d*240 - fromSqr; // do indexing of 2d array 'by hand'

  int s = next[64];
  while(s != 64) {   // loop through existing exceptions
    m &= t[s];       // remove s from set of squares that would block move
    ...              // process the exception
    Delete(s);       // conditionally remove some exceptions
    ...
    s = next[s];     // next existing exception
  }

  while(m != 0) {
    int n = BSF(m);  // extract remaining squares where Duck blocked
    ...              //
    Add(n);          // conditionally add new exceptions
    m &= m - 1;      // clear treated square
  }

  if(new.common > commonScore) commonScore = new.common;

[JohnWoe]

Added this variant to Mayhem. Will release this to the public sometimes. But there's no GUI support nor cutechess to test so...
I simply search all drops. Instead of white -> white -> black -> black ...

Obviously generating all duck moves doesn't lead to the promised land.
As there's 60 * 62 moves every ply.

Engine is obviously pretty green. Once cutechess has support testing is possible. XBoard testing is too slow...

Search 26MNPS.

Code: Select all

...

Nodes:    101646136
Time(ms): 3786
NPS:      26847896
Mode:     HCE

Perft 200MNPS.

Code: Select all

perft
1. a2a3 -> 276284712 (1445 ms)
2. a2a4 -> 355548802 (1883 ms)
3. b2b3 -> 346618545 (1775 ms)
4. b2b4 -> 347042253 (1701 ms)
5. c2c3 -> 385529671 (1906 ms)
6. c2c4 -> 415890843 (2053 ms)
7. d2d3 -> 604676855 (3013 ms)
8. d2d4 -> 707040172 (3461 ms)
9. e2e3 -> 839184794 (4097 ms)
10. e2e4 -> 841567306 (4029 ms)
11. f2f3 -> 268038745 (1305 ms)
12. f2f4 -> 310782075 (1524 ms)
13. g2g3 -> 353578366 (1702 ms)
14. g2g4 -> 338815910 (1628 ms)
15. h2h3 -> 276185450 (1319 ms)
16. h2h4 -> 358741175 (1737 ms)
17. b1a3 -> 316379757 (1522 ms)
18. b1c3 -> 393805202 (1902 ms)
19. g1f3 -> 389437263 (1882 ms)
20. g1h3 -> 316253959 (1536 ms)

===========================

Nodes:    8441401855
Time(ms): 41420
Depth:    4
NPS:      203800141

[hgm]

Uh? XBoard is a GUI, and it supports is. And XBoard is not any slower than CuteChess, is it?

[abulmo2]

Uh? XBoard is a GUI, and it supports is. And XBoard is not any slower than CuteChess, is it?

Cutechess can run games in parallel. It is also easier to configure a tournament.