Nomenclature suggestion: Bit target programs

[sje]

Nomenclature suggestion: Bit target programs

Based on the primary board representation mode, chess programs have been traditionally divided into three types: the mailbox type, the piece vector type, and the bitboard type. I propose a fourth: the bit target type, a hybridization of the piece vector type and the bitboard type. My programs Myopic and Oscar are bit target programs, the latter strongly so although it does mostly perft() and does not yet play chess.

In a bit target program, the primary representation of a set of chessmen in a 32 bit integer type with each bit corresponding to a given chessman. There is a secondary structure of a 32 element vector which gives the square coordinates of each target and an accompanying vector which describes the chessman kind for each target. The primary motivation for a bit target representation is to allow efficient chess calculation on 32 bit and 16 bit hardware. Testing has shown that, as expected, a bit target program can be faster than a bitboard program for perft() calculations on 32 bit hardware.

Maybe someone can suggest a better name than "bit target". It would be nice to have some kind of a consensus before this goes into the chess programming wiki.

[SMIRF]

Related to this typification discussion I ask for your opinions to my current approach: any position is represented by a twin set of boards (having features of a mailbox) but are colorlessly encoded by supplying mirrored views using an additional piece type "opponent". Simultaneously all non opponent pieces consist of binary encoded sets of combinations of valid gaits, additionally locally extended by an ordered double link list connecting all non opponent pieces.

This representation seems to perform very well. First experiments in check detection gained about 50% of increased performance compared to my old well functioning SMIRF approach. Still slowly working on the new legal, full information move generator (including e.g. information on check threats and captures) I am very optimistic in its growing efficiency.

P.S.: by this representation all routines are color independent, there is no need for b/w routine twins or template alternatives or any local color checking, everything is absolutely symmetric for color swapped test positions. Moreover 8x8 and 10x8 chess variations are supported.

[hgm]

Would 'pieceset program describe it?

[sje]

In my program Oscar, white chessmen are represented in the first (lower order) 16 bits of a 32 bit integer while the black chessmen get the second set of 16 bits. These are the king bits. Additionally, the white king always gets bit zero while the black king always gets bit 16. The remaining bits have no particular affinity to any chessman kind; these are called the peon bits.

An index variable which selects among the target bits is called a target index and is abbreviated as ti. By convention, the target index variable which scans the targets for the color on the move is called goodti while the target index scanning the targets for the other color is called evilti.

Some target indexed bit vector definition code from Oscar:

Code: Select all

// Chessmen population

#define ArmyLen     (FileLen * 2)           // Number of chessmen per color
#define ChessSetLen (ArmyLen * ColorRCLen)  // Total number of chessmen

// Ti: Target index (chessman fixed serial number)

typedef enum
{
  TiNil = -1,
  TiX00, TiX01, TiX02, TiX03, TiX04, TiX05, TiX06, TiX07,  // White man target indexes; 1st half
  TiX08, TiX09, TiX0a, TiX0b, TiX0c, TiX0d, TiX0e, TiX0f,  // White man target indexes; 2nd half
  TiX10, TiX11, TiX12, TiX13, TiX14, TiX15, TiX16, TiX17,  // Black man target indexes; 1st half
  TiX18, TiX19, TiX1a, TiX1b, TiX1c, TiX1d, TiX1e, TiX1f   // Black man target indexes; 2nd half
} Ti;

#define TiLen (TiX1f + 1)

#define IsTiNil&#40;ti&#41;    (&#40;ti&#41; <  0&#41;
#define IsTiNotNil&#40;ti&#41; (&#40;ti&#41; >= 0&#41;

#define MapColorToKingTi&#40;color&#41; (&#40;color&#41; * ArmyLen&#41;                        // King target index
#define MapColorToPeonTi&#40;color&#41; &#40;MapColorToKingTi&#40;color&#41; + 1&#41;              // First peon target index
#define MapColorToStopTi&#40;color&#41; &#40;MapColorToKingTi&#40;color&#41; + &#40;ArmyLen - 1&#41;)  // Last target index

// Target index bit vector &#40;set of target indexes&#41;

typedef ui32 TiBV;

// Target index bit vector&#58; Accessor macros

#define TiBVSet&#40;tibv, ti&#41;   &#40;tibv |=  BX&#40;ti&#41;)
#define TiBVReset&#40;tibv, ti&#41; &#40;tibv &= ~BX&#40;ti&#41;)
#define TiBVTest&#40;tibv, ti&#41;  &#40;tibv &   BX&#40;ti&#41;)

// Auxiliary position data; saved/restored on execute/retract

typedef struct
&#123;
  bool incheck;   // In check status
  bool dbcheck;   // Double check status
  TiBV checkers;  // Target indexed bit vector&#58; checking men
  TiBV pinned;    // Target indexed bit vector&#58; pinned targets
  TiBV frozen;    // Target indexed bit vector&#58; frozen targets
&#125; Apd;

// Target index bit vector set

typedef struct
&#123;
  TiBV occupied;  // Occupied
  TiBV sweepers;  // Sweepers
  TiBV pawns;     // Pawns
&#125; Tbvs;

// Target tracker capture stack element

typedef struct
&#123;
  Tbvs tbvs;     // Target bit vector set
  Sq   captsq;   // Capture square
  Ti   captti;   // Capture target index
&#125; Capt;

// Target tracker capture stack

typedef struct
&#123;
  Capt captvec&#91;ChessSetLen&#93;;  // Vector of saved capture data
  ui   captcount;             // Count of stacked captures; index of next free element
&#125; CaptStk;

// Target tracker

typedef struct
&#123;
  Tbvs    tbvs;          // Target index bit vector set
  Sq      sqvec&#91;TiLen&#93;;  // Map&#58; target index -> square
  Ti      tivec&#91;SqLen&#93;;  // Map&#58; square -> target index
  CaptStk captstk;       // Target tracker capture stack
&#125; Tracker;

[sje]

Would 'pieceset program describe it?

I was also thinking about targetset.

[Gerd Isenberg]

Would 'pieceset program describe it?

I was also thinking about targetset.

https://chessprogramming.wikispaces.com/Piece-Sets

[sje]

Would 'pieceset program describe it?

I was also thinking about targetset.

https://chessprogramming.wikispaces.com/Piece-Sets

I usually avoid the term piece because in much English language chess literature, piece does not apply to a king and usually doesn't apply to a pawn, either. Instead I use chessman/chessmen or man/men.

In Oscar, the typedef TiBV (Target indexed Bit Vector) is used. I may change this to TargetSet or TS.

[Gerd Isenberg]

Would 'pieceset program describe it?

I was also thinking about targetset.

https://chessprogramming.wikispaces.com/Piece-Sets

I usually avoid the term piece because in much English language chess literature, piece does not apply to a king and usually doesn't apply to a pawn, either. Instead I use chessman/chessmen or man/men.

In Oscar, the typedef TiBV (Target indexed Bit Vector) is used. I may change this to TargetSet or TS.

Yes, piece is a bit ambiguous in chess, but in chess programming piece-sets include pawns and kings similar to piece-lists, piece-arrays or piece-vectors. For me target-set implies a set of move targets per piece or direction, and men-set sounds strange. I am not an English native speaker, but for me piece-set sounds most natural - I used the term in the 1999 ICCA description of IsiChess. Andrew Tridgell used the term piece bitlist.

[sje]

Yes, piece is a bit ambiguous in chess, but in chess programming piece-sets include pawns and kings similar to piece-lists, piece-arrays or piece-vectors. For me target-set implies a set of move targets per piece or direction, and men-set sounds strange. I am not an English native speaker, but for me piece-set sounds most natural - I used the term in the 1999 ICCA description of IsiChess. Andrew Tridgell used the term piece bitlist.

I'd say that piece bitlist is not what I'd want because list usually means something with an arbitrary, perhaps unlimited, number of entries and which doesn't allow fast random access.

[AlvaroBegue]

I usually avoid the term piece because in much English language chess literature, piece does not apply to a king and usually doesn't apply to a pawn, either. Instead I use chessman/chessmen or man/men.

In the code for Ruy-López we use the word "piece" as including pawns and kings and the word "officer" to describe a piece that is not a pawn or a king. Well, it's actually in Spanish, but "pieza" and "oficial" are analogous.