Polyglot keys for chess variants.

[Michel]

I guess we need "official" polyglot keys for chess variants.

Does winboard or perhaps the variant-ics already implements this?

I am specifically thinking about the non-shuffle variants (i.e. on FICS: chess, losers, atomic, crazyhouse and suicide). For those you really need an opening book since otherwise people always play the same game against an engine.

[Daniel Shawul]

I don't know about polyglot's book format but it may require a different kind of hashing when holdings are added. Besides the keys for piece type/location combination, the number of pieces in holding will need separate hash keys and probably be composed by adding not xoring. So I do not think polyglot's book format could be extended that easily to crazyhouse or shogi.. The engines usually comes with own book AFAIK, and there aren't many of them. Anyway if you have a move generator for the variant in polyglot, we all can follow that format...

[Michel]

A polyglot book is just a list of records.

zobrist-key move score

The records are ordered according to zobrist-key and the most commonly used access method is binary search (although interpolation search would be faster).

The zobrist-key should be xored with a key corresponding to the variant
(otherwise you could accidentally use a suicide chess book in ordinary chess).
These keys should be standardized for obvious reasons.

And you are right. A crazyhouse book would also have to hash the holdings.
This is a different problem I had not thought of (I am basically new to these variants). I am curious though why you say that one should addition instead of xoring.

[Daniel Shawul]

A polyglot book is just a list of records.

zobrist-key move score

The records are ordered according to zobrist-key and the most commonly used access method is binary search (although interpolation search would be faster).

The zobrist-key should be xored with a key corresponding to the variant
(otherwise you could accidentally use a suicide chess book in ordinary chess).
These keys should be standardized for obvious reasons.

And you are right. A crazyhouse book would also have to hash the holdings.
This is a different problem I had not thought of (I am basically new to these variants). I am curious though why you say that one should addition instead of xoring.

Since you hash by the number of piece types, xoring will cancel out if the same hashkey is used when the number of pawns in holding increases from 2 to 3 for example. Ofcourse if you have separate hash keys for all the possible number of pieces in holding (it is feasible to do it that way) , then xoring would work fine too. Addition works for any number of pieces in holding since you just keep on adding the same key. For that reason I keep two separate keys one for 'regular' hashing and another for 'holdings', which are xored eventually when probing the hash table.

From the games you listed crazyhouse will pose a problem with holdings, and atomic has a nasty move generator, so those may not be worth the effort to do them in polyglot. But I think you can handle the rest of the variants in polyglot.

[ilari]

I guess we need "official" polyglot keys for chess variants.

Does winboard or perhaps the variant-ics already implements this?

I am specifically thinking about the non-shuffle variants (i.e. on FICS: chess, losers, atomic, crazyhouse and suicide). For those you really need an opening book since otherwise people always play the same game against an engine.

Cute Chess GUI can already create Polyglot books for any supported variant (atomic, capablanca, caparandom, crazyhouse, fischerandom, gothic, losers). But it's a bit buggy at the moment for crazyhouse and 10x8 variants because information is lost when it's squeezed into too few bits (as specified in the Polyglot specs). But a fix is coming.

[Michel]

Cute Chess GUI can already create Polyglot books for any supported variant (atomic, capablanca, caparandom, crazyhouse, fischerandom, gothic, losers).

That's very useful!

But people seem to misunderstand my question....

The question is not how to create polyglot books. That I know how to do.

The issue is: a zobrist key encoding the variant type should be xor'ed with the zobrist keys of the positions in a book to avoid the possibility of using a book for a variant different from the one it was created for. Also: the use of such variant keys makes it possible to concatinate books for different variants in one big book.

Something like

Code: Select all

Chess:    0x0000000000000000
Atomic:   0x0123456789abcdef
Suicide:  0xfedcba9876543210
....

So my question is:

Are there already zobrist-variant keys being used in some GUI's?

The reason is of course that these keys should be standardized for otherwise the resulting books can only be used in one GUI.

When an engine plays on a chess server it is imperative to use a book for otherwise people always play the same winning line.

[hgm]

WinBoard has extended Polyglot book format (keys as well as move field) for all variants it currently supports. This requires many more (piece, square) keys, as the number of piece types WinBoard supports is 22, (44 including color), while the 12x8 Courier-Chess board has 96 squares.

All new keys are derived from the existing Polyglot key table, however, by rotating the bits in the 64-bit word. Piece types and squares are numbered, where for backward compatibility the orthodox Chess pieces PNBRQK are numbered 0-5, and board squares are numbered by scanning the board as in Chess (i.e. starting in the lower left corner if you view the board from the side that moves first). The 'base key' picked from the table is then key(color, pieceType%6, squareNr%64).

This base key is then rotated by (squareNr/64) + 2*(pieceType/6) bytes. This means that squareNr can run upto 128 and pieceType upto 24 before running into duplicats. ) Note, however, that in a variant using only orthodox pieces, the square number could run much higher.

Moves are stored as boardSize*fromSquareNr + toSquareNr, which for boardSize=64 means they map to groups of 6 bits for the individual squares. Prootion codes are multiplied by boardSize squared before being added. What the codes mean is variant-dependent. It could be that not all promotions can be encoded, in variants with large boards and/or many piece types.

To avoid confusion between variants that us he same board and pieces (e.g. Suicide, Atomic and normal), WinBoard adds the variant number to the key. For this it uses its internal variant encoding, but some variants are first mapped onto others, if they are not really diffrent (e.g. FRC, nocastle and normal). This seems the actual answer to your question.

For holdings, the 'holding squares' are numbered as if they are additional board ranks (and distinguish piece type, as in-hand pieces are stacked on a joldings square rserved for the type). The holdings key is additive, rather than using XOR, to allow for the stacking. In the and the holdings key is added to the board key.

This is the WB code for calculating the hash key:

Code: Select all

uint64
hash (int moveNr)
{
    int r, f, p_enc, squareNr, pieceGroup;
    uint64 key=0, holdingsKey=0, Zobrist;
    VariantClass v = gameInfo.variant;

    switch(v) {
	case VariantNormal:
	case VariantFischeRandom: // compatible with normal
	case VariantNoCastle:
	case VariantXiangqi: // for historic reasons; does never collide anyway because of other King type
	    break;
	case VariantGiveaway: // in opening same as suicide
	    key += VariantSuicide;
	    break;
	case VariantGothic: // these are special cases of CRC, and can share book
	case VariantCapablanca:
	    v = VariantCapaRandom;
	default:
	    key += v; // variant type incorporated in key to allow mixed books without collisions
    }

    for(f=0; f<BOARD_WIDTH; f++){
        for(r=0; r<BOARD_HEIGHT;r++){
            ChessSquare p = boards[moveNr][r][f];
	    if(f == BOARD_LEFT-1 || f == BOARD_RGHT) continue; // between board and holdings
            if(p != EmptySquare){
		    int j = (int)p;
		    j -= (j >= (int)BlackPawn) ? (int)BlackPawn :(int)WhitePawn;
		    if(j > (int)WhiteQueen) j++;  // make space for King
		    if(j > (int) WhiteKing) j = (int)WhiteQueen + 1;
		    p_enc = 2*j + ((int)p < (int)BlackPawn);
		    // holdings squares get nmbers immediately after board; first left, then right holdings
		    if(f == BOARD_LEFT-2) squareNr = (BOARD_RGHT - BOARD_LEFT)*BOARD_HEIGHT + r; else
		    if(f == BOARD_RGHT+1) squareNr = (BOARD_RGHT - BOARD_LEFT + 1)*BOARD_HEIGHT + r; else
		    squareNr = (BOARD_RGHT - BOARD_LEFT)*r + (f - BOARD_LEFT);
		    // note that in normal Chess squareNr < 64 and p_enc < 12. The following code
		    // maps other pieces and squares in this range, and then modify the corresponding
		    // Zobrist random by rotating its bitpattern according to what the piece really was.
		    pieceGroup = p_enc / 12;
		    p_enc      = p_enc % 12;
		    Zobrist = RandomPiece[64*p_enc + (squareNr & 63)];
		    switch(pieceGroup) {
			case 1: // pieces 5-10 (FEACWM)
				Zobrist = (Zobrist << 16) ^ (Zobrist >> 48);
				break;
			case 2: // pieces 11-16 (OHIJGD)
				Zobrist = (Zobrist << 32) ^ (Zobrist >> 32);
				break;
			case 3: // pieces 17-20 (VLSU)
				Zobrist = (Zobrist << 48) ^ (Zobrist >> 16);
				break;
		    }
		    if(squareNr >= 64) Zobrist = (Zobrist << 8) ^ (Zobrist >> 56);
		    // holdings have separate (additive) key, to encode presence of multiple pieces on same square
		    if(f == BOARD_LEFT-2) holdingsKey += Zobrist * boards[moveNr][r][f+1]; else
		    if(f == BOARD_RGHT+1) holdingsKey += Zobrist * boards[moveNr][r][f-1]; else
                key ^= Zobrist;
            }
        }
    }

    if(boards[moveNr][CASTLING][2] != NoRights) {
	if(boards[moveNr][CASTLING][0] != NoRights) key^=RandomCastle[0];
	if(boards[moveNr][CASTLING][1] != NoRights) key^=RandomCastle[1];
    }
    if(boards[moveNr][CASTLING][5] != NoRights) {
	if(boards[moveNr][CASTLING][3] != NoRights) key^=RandomCastle[2];
	if(boards[moveNr][CASTLING][4] != NoRights) key^=RandomCastle[3];
    }

    f = boards[moveNr][EP_STATUS];
    if(f >= 0 && f < 8){
        if(!WhiteOnMove(moveNr)){
	    // the test for neighboring Pawns might not be needed, 
	    // as epStatus already kept track of it, but better safe than sorry.
            if((f>0 && boards[moveNr][3][f-1]==BlackPawn)||
               (f<7 && boards[moveNr][3][f+1]==BlackPawn)){
                key^=RandomEnPassant[f];
            }
        }else{
            if((f>0 && boards[moveNr][4][f-1]==WhitePawn)||
               (f<7 && boards[moveNr][4][f+1]==WhitePawn)){
                key^=RandomEnPassant[f];
            }
        }
    }

    if(WhiteOnMove(moveNr)){
        key^=RandomTurn[0];
    }
    return key + holdingsKey;
}

The system canot handle the large Shogi variants (Chu Shogi, Tenjiku Shogi) that I have been implementing in WinBoard lately, as these have many more than 22 piece types. (Chu Shogi, the smallest of the large Shogi variants on 12x12, has 36 piece types per side.)

The variants are numbered in WinBoard as:

Code: Select all

typedef enum {
    VariantNormal,       /* Normal chess */
    VariantLoadable,     /* "loadgame" command allowed (not really a variant)*/
    VariantWildCastle,   /* Shuffle chess where king can castle from d file */
    VariantNoCastle,     /* Shuffle chess with no castling at all */
    VariantFischeRandom, /* FischeRandom */
    VariantBughouse,     /* Bughouse, ICC/FICS rules */
    VariantCrazyhouse,   /* Crazyhouse, ICC/FICS rules */
    VariantLosers,       /* Try to lose all pieces or get mated (ICC wild 17)*/
    VariantSuicide,      /* Try to lose all pieces incl. king (FICS) */
    VariantGiveaway,     /* Try to have no legal moves left (ICC wild 26) */
    VariantTwoKings,     /* Weird ICC wild 9 */
    VariantKriegspiel,   /* Kriegspiel; pawns can capture invisible pieces */
    VariantAtomic,       /* Capturing piece explodes (ICC wild 27) */
    Variant3Check,       /* Win by giving check 3 times (ICC wild 25) */
    VariantShatranj,     /* Unsupported (ICC wild 28) */
    Variant29,           /* Temporary name for possible future ICC wild 29 */
    Variant30,           /* Temporary name for possible future ICC wild 30 */
    Variant31,           /* Temporary name for possible future ICC wild 31 */
    Variant32,           /* Temporary name for possible future ICC wild 32 */
    Variant33,           /* Temporary name for possible future ICC wild 33 */
    Variant34,           /* Temporary name for possible future ICC wild 34 */
    Variant35,           /* Temporary name for possible future ICC wild 35 */
    Variant36,           /* Temporary name for possible future ICC wild 36 */
    VariantShogi,        /* [HGM] added variants */
    VariantXiangqi,
    VariantCourier,
    VariantGothic,
    VariantCapablanca,
    VariantKnightmate,
    VariantFairy,        
    VariantCylinder,
    VariantFalcon,
    VariantCapaRandom,
    VariantBerolina,
    VariantJanus,
    VariantSuper,
    VariantGreat,
    VariantTwilight,
    VariantMakruk,
    VariantSChess,
    VariantGrand,
    VariantSpartan,
    VariantUnknown       /* Catchall for other unknown variants */
} VariantClass;

So Suicide would have key 0x00000008.

[Michel]

This is more what I was looking for!

I wonder if you could write this out formally and post it somewhere? I think it is important that polyglot books for variants remain standardized.

I can then link to it from the spec for standard chess

http://hardy.uhasselt.be/Toga/book_format.html

[hgm]

I could, and probably should, but it seems to be a bit arbitrary, and very much based on WinBoard's internal workings. It would probably not be too late to adapt it, as I don't think there already exist any variant books. (Except for the Xiangqi book I distributed, which already required an exception, as at uses the same variant key as orthodox Chess.)

[hgm]

What I worry about specifically is how to assign numbers to piece types. This now (mostly) follows WinBoards internal encoding, which is quite arbitrary.

There are two different philosophies that could be used here:
1) try to keep the piece numbers low, by counting in any variant only the pieces that participate in it. So in normal Chess PNBRQK is 0-5, but in Spartan Chess, where black plays with HCLGWK in stead of PNBRQK, we could still use H=0, C=1, L=2 etc. The inclusion of a variant key would remove the collision with keys for normal Chess.
2) try to give each piece type a unique key

The latter method would in principle allow compatible board keys for positions in different variants that only contain pieces hey have in common (if they have the same board size). Except that a variant key would spoil that. For instance, Seirawan Chess shares part of this game tree (after all Hawks and Elephants have been captured) with normal Chess, as would TwoKings, after the pseudo-Kings have been traded. This would be an argument for giving TwoKings and Seirawan the same variant key as normal Chess.

WinBoard sort of uses philosophy 2, although not rigorously: the Shogi Knight and Xiangqi Horse use the same piece-type number as the orthodox Knight, although they move differently, and the Silver General uses the same number as Ferz in other games, for no other reason than that WinBoard uses the same image to represent them. (And this in itself forced an inconsistency in the representation of the later-added Makruk, where both Ferz and Silver are in the starting position. So Silver is represented there by the piece that in other variants is a Commoner, and in the current code would also use the piece-type key for Commoner...)

The advantage of shared positions is a bit hypothetical, though. The keys are only important in the context of opening books, and for variants like Seirawan and TwoKings it is extremely unlikely you would ever get into a position of normal Chess in any reasonable opening line. So philosophy (1) might actually lead to a better design. Especially if we could devise some canonical way of ordering piece types based on their moves. Like ordering them by the number of moves they have in the center of the board, (providing some tie-breaker rules for when these numbers are equal). That would be more general than just having to exhaustively list the assignment of pieceTypeNr for all pieces in all variants that happen to be supported by WinBoard today.

Another shortcoming of the current WinBoard system is that the mapping of piece types to holdings square is a bit arbitrary, and even impossible if there are more different (capturable) piece types than board ranks (preventing WinBoard to implement Wa Shogi with drops, for instance). A canonical ordering would also help to clean that up. An extra complication is that WinBoard sometimes displays holdings that aren't really holdings from which you can drop, but just as an aid to see and select what is captured (in variants where promotion rules specify you can only promote to a captured piece, such as Grand Chess or Superchess). Such pseudo-holdings should really not be encoded in the key, as the captured material is implied by what is left on the board.

So perhaps I should formalize the system it in a way different from what WinBoard does now, and adapt WinBoard accordingly. That of course does not have to stop us from already formally defining variant keys for Suicide and Atomic, and other variants that use the same board size and piece set as orthodox Chess.