Sample code: Moves and variations

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Sample code: Moves and variations

Post by sje » Fri Dec 02, 2011 7:13 pm

Sample code: Moves and variations

In BozoChess, a chess move is not packed into a single scalar type but instead is a structure of unpacked data. This works well as there is no packing/unpacking overhead and there is little need to actually move the move data from place to place.

A move can live inside a move node structure which is simply an element of a two-way linked list. Each node is initially allocated by a library call, but thereafter the node can be moved from list to list just by changing a few pointers. The dynamic storage is releases via library calls only when the list is destroyed.

A variation structure is composed of two move lists. The first is the used lust which contains the moves of interest. The second is the free node list which contains free nodes which are used for appending new moves to the used list as needed. When a move node is released form the used list, it is appended to the free list for later use. The big idea here is to not call an slow library memory management routine each time a variation needs adjustment.

Using the variation data structure greatly simplifies handling predicted variations at all ply. It's also good for handling the current variation (i.e., path from the root) for tracing and debugging.

Code: Select all

    { Chess move: a single move with a score value }

    movetype =
      record
        frsq:  sqtype;  { From square }
        tosq:  sqtype;  { To square }
        frman: mantype; { From man }
        toman: mantype; { To man }
        msc:   msctype; { Special case }
        mfs:   mfstype; { Move flag set }
        sv:    svtype   { Score value }
      end;

    { Move nodes }

    mnptrtype = ^mntype; { A pointer to a move node }

    mntype =
      record
        move: movetype;  { The move }
        prev: mnptrtype; { Link to previous move node }
        next: mnptrtype  { Link to next move node }
      end;

    { List of move nodes }

    mnlisttype =
      record
        ecount: ecounttype; { Element count }
        head:   mnptrtype;  { Head of move node list }
        tail:   mnptrtype   { Tail of move node list }
      end;

    { Variation }

    variationtype =
      record
        freelist: mnlisttype; { Free move nodes }
        usedlist: mnlisttype  { Move nodes in played order }
      end;

  { ***** Variation routines ***** }

  procedure VariationReset(var variation: variationtype);
  begin
    with variation do
      begin
        MnListReset(freelist);
        MnListReset(usedlist)
      end
  end; { VariationReset }

  procedure VariationRecycleTail(var variation: variationtype);
  begin
    with variation do
      MnListAppendTail(freelist, MnListDetachTail(usedlist))
  end; { VariationRecycleTail }

  procedure VariationRecycle(var variation: variationtype);
  begin
    with variation do
      while usedlist.tail <> nil do
        VariationRecycleTail&#40;variation&#41;
  end; &#123; VariationRecycle &#125;

  procedure VariationAppendMove&#40;var variation&#58; variationtype; var move&#58; movetype&#41;;
    var
      mnptr&#58; mnptrtype;
  begin
    with variation do
      begin
        if freelist.tail = nil then
          begin
            New&#40;mnptr&#41;;
            MnListAppendTail&#40;freelist, mnptr&#41;
          end;
        mnptr &#58;= MnListDetachTail&#40;freelist&#41;;
        mnptr^.move &#58;= move;
        MnListAppendTail&#40;usedlist, mnptr&#41;
      end
  end; &#123; VariationAppendMove &#125;

  procedure VariationAppend&#40;var variation, subvariation&#58; variationtype&#41;;
    var
      mnptr&#58; mnptrtype;
  begin
    with variation do
      begin
        mnptr &#58;= subvariation.usedlist.head;
        while mnptr <> nil do
          begin
            VariationAppendMove&#40;variation, mnptr^.move&#41;;
            mnptr &#58;= mnptr^.next
          end
      end
  end; &#123; VariationAppend &#125;

  procedure VariationAssign&#40;var variation, altvariation&#58; variationtype&#41;;
  begin
    VariationRecycle&#40;variation&#41;;
    VariationAppend&#40;variation, altvariation&#41;
  end; &#123; VariationAssign &#125;

  procedure VariationBuild&#40;
      var variation&#58; variationtype;
      var move&#58; movetype; var subvariation&#58; variationtype&#41;;
  begin
    VariationRecycle&#40;variation&#41;;
    VariationAppendMove&#40;variation, move&#41;;
    VariationAppend&#40;variation, subvariation&#41;
  end; &#123; VariationBuild &#125;

  procedure VariationNotate&#40;var variation&#58; variationtype; var pos&#58; postype&#41;;
    var
      mnptr&#58; mnptrtype;
      count&#58; ecounttype;
  begin
    with variation do
      begin
        count &#58;= 0;
        mnptr &#58;= usedlist.head;
        while mnptr <> nil do
          begin
            PosMoveNotate&#40;pos, mnptr^.move&#41;;
            PosExecute&#40;pos, mnptr^.move&#41;;
            Inc&#40;count&#41;;
            mnptr &#58;= mnptr^.next
          end;
        while count > 0 do
          begin
            PosRetract&#40;pos&#41;;
            Dec&#40;count&#41;
          end
      end
  end; &#123; VariationNotate &#125;

  function VariationPosEncode&#40;var variation&#58; variationtype; var pos&#58; postype&#41;&#58; String;
    var
      myresult&#58; String;
      mnptr&#58; mnptrtype;
      mc&#58; mctype;
  begin
    with variation do
      begin
        myresult &#58;= '';
        VariationNotate&#40;variation, pos&#41;;
        PosLoadToMc&#40;pos, mc&#41;;
        mnptr &#58;= usedlist.head;
        while mnptr <> nil do
          begin
            if &#40;mc.good = colorw&#41; or &#40;mnptr = usedlist.head&#41; then
              myresult &#58;= myresult + McEncode&#40;mc&#41; + ' ';
            myresult &#58;= myresult + MoveEncode&#40;mnptr^.move&#41;;
            McIncrement&#40;mc&#41;;
            mnptr &#58;= mnptr^.next;
            if mnptr <> nil then
              myresult &#58;= myresult + ' '
          end
      end;
    VariationPosEncode &#58;= myresult
  end; &#123; VariationPosEncode &#125;

  procedure VariationInit&#40;var variation&#58; variationtype&#41;;
  begin
    with variation do
      begin
        MnListInit&#40;freelist&#41;;
        MnListInit&#40;usedlist&#41;
      end
  end; &#123; VariationInit &#125;

  procedure VariationTerm&#40;var variation&#58; variationtype&#41;;
  begin
    with variation do
      begin
        MnListTerm&#40;freelist&#41;;
        MnListTerm&#40;usedlist&#41;
      end
  end; &#123; VariationTerm &#125;

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

Re: Sample code: Moves and variations

Post by hgm » Fri Dec 02, 2011 7:31 pm

I ever succeeded making somethig fast using linked lists on modern CPUs. The latency of memory fetches is so large (even if they are level-1 cache hits) that following the links becomes a major slowdown.

I usually pack the moves is a structure of 4 bytes, which can also be accessed as an int. Because most CPUs have byte addressing nowadays, this esentially makes the hardware do the packing / unpacking.

The only bytes that are really needed are for the from- and to-squares. These go into the hash table and uniquely identify the move. The other bytes of moves on the move stack are used for sort keys and such.

The most versatile and efficient system I found so far for the two-byte encoding of moves is to use off-board to-square for flagging 'special moves', i.e. moves that require execution of some code other than moving the piece between the from- and to-square. Such as castling, promotion, e.p., but also double-pushes. The standard MakeMove code has to fetch board[to] anyway, to get the victim. It then only requires a single compare and branch to test if the victim is a border guard delimiting the board, and if it is't, the move is a regular one. In the much rarer case it is special, the off-board to-square can be used to index tables to get the real to-square, capture square, move type, promotion piece etc.

User avatar
lucasart
Posts: 3041
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Sample code: Moves and variations

Post by lucasart » Fri Dec 02, 2011 7:42 pm

what's the "sizeof" of your move structure ? trust me you need to stuff it in 32-bit for hash tables later on.

Pascal is an unfortunate choice, but in C here's how I do it:

Code: Select all

typedef struct &#123;
	unsigned fsq&#58;6, tsq&#58;6;
	unsigned piece&#58;3, capture&#58;3, promotion&#58;3;
	unsigned ep&#58;1, check&#58;2;
&#125; move_t;
* fsq and tsq: from and to squares, being numbers 0..63 so 6 bits is just enough
* piece (the moving piece) capture (the piece on tsq, which is generally the capture or possibly an empty square for en passant) promotion (the piece to promote to): there are 6 pieces, so 3 bits is enough.
* ep is a boolean flag (1 bit) for en passant capture
* check: 0 (non check) 1 ("normal" check) 2 (discovered check)
total 6+6+3+3+3+1+2=27 bits, so 32 due to alignment (assuming x86 or x86_64 architecture)

Another beauty of the C language is that all the bitwise operations to extract and put info into such a structure are done by the compiler. In practice it's better to trust the compiler to optimize this than to write it yourself: it's just as fast (sometimes more), much less error prone and much easier to write and to read.

I also use this kind of thing for fitting my trans table entry into 16 bytes:

Code: Select all

// Pack key + depth into 64 bits &#40;by using 56 bits of the key&#41;
typedef struct &#123;
	int8_t depth&#58; 8;
	uint64_t key56&#58; 56;
&#125; key_depth_t;

// 16 bytes hash_t &#40;thanks to key_depth_t being packed into 8 bytes&#41;
typedef struct &#123;
	key_depth_t key_depth;
	int16_t eval, score;
	unsigned type&#58; 2;
	move_t move;
&#125; hash_t;
practically anytime you copy moves, it's as fast (and in assembly it's exactly the same) as using an int. there's no overhead for any kind of construction or destruction code, obviously.

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Sample code: Moves and variations

Post by Evert » Fri Dec 02, 2011 7:58 pm

lucasart wrote:what's the "sizeof" of your move structure ? trust me you need to stuff it in 32-bit for hash tables later on.
Jazz used to have 64-bit move structs, I didn't notice much of a gain by compating it to 32 bits (but I did it anyway).
Another beauty of the C language is that all the bitwise operations to extract and put info into such a structure are done by the compiler. In practice it's better to trust the compiler to optimize this than to write it yourself: it's just as fast (sometimes more), much less error prone and much easier to write and to read.
Here I found exactly the opposit: writing the bitshifts and extracting the data myself was faster than relying on the compiler to optimise bitfields.
I agree that the compiler should be doing as good a job, if not better, than you can do yourself, but in practice it doesn't seem to...

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Sample code: Moves and variations

Post by sje » Fri Dec 02, 2011 8:11 pm

The link transverse does take some time, but mostly everything lives in L1 cache so the link fetch time is no more and can be less than the code fetch time for pack/unpack.

Not included in the above code are the move node routines which are all small and all declared inline.

The move generation doesn't use move lists but rather a simple array. It could be coded with lists, but unlike a variation, all the generated moves from a single position are not played one after another. The list business is used almost exclusively for sequences of moves of arbitrary length and played in order. A predicted variation (like the current variation) can be of any length and without use of the triangular array scheme with its fixed limits. When building a predicted variation, a move is copied only once and then only its links are changed as needed. Library allocation and deallocation routines are called so rarely that they don't show up under profiling.

Having moves passed by reference allows for greater flexibility by not having to be concerned about packing/unpacking and the size of a move structure. I can increase the number of move flags in the flag set component an not be concerned with having to fit everything into a fixed length scalar. I use a 32 bit signed value for a score instead of trying to squeeze it into a 16 bit word.

The msc component of the move structure handled all special case information about the move. It's used for execute/retract and in a few other places:

Code: Select all

    &#123; Chess move&#58; move special case &#125;

    mscreg = 0; &#123; Regular move &#125;
    mscepc = 1; &#123; En passant capture &#125;
    msccqs = 2; &#123; Castles queenside &#125;
    msccks = 3; &#123; Castles kingside &#125;
    mscppn = 4; &#123; Pawn promotes to knight &#125;
    mscppb = 5; &#123; Pawn promotes to bishop &#125;
    mscppr = 6; &#123; Pawn promotes to rook &#125;
    mscppq = 7; &#123; Pawn promotes to queen &#125;

    &#123; Chess move&#58; move special case &#125;

    msctype = mscreg..mscppq;

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Move flags

Post by sje » Fri Dec 02, 2011 8:27 pm

The move flags are represented as a bit vector living inside an unsigned integer. This could be changed to a set and I may do this later; in Free Pascal, a set with 32 or fewer elements is handled reasonably efficiently. But this may not be the case with other Pascal implementations. There is (or was) a Pascal implementation that couldn't handle sets with more than eight (!) elements.

Code: Select all

    &#123; Chess move&#58; move flags &#125;

    mfandf =  0; &#123; Needs algebraic notation disambiguation file letter &#125;
    mfandr =  1; &#123; Needs algebraic notation disambiguation rank digit &#125;
    mfbook =  2; &#123; Book move &#125;
    mfcert =  3; &#123; Certain score &#125;
    mfchck =  4; &#123; Checking move &#125;
    mfchmt =  5; &#123; Checkmating move &#125;
    mfdraw =  6; &#123; Drawing move &#125;
    mfdrfm =  7; &#123; Drawing move &#40;fifty moves&#41; &#125;
    mfdrim =  8; &#123; Drawing move &#40;insufficient material&#41; &#125;
    mfdrrp =  9; &#123; Drawing move &#40;repetition&#41; &#125;
    mfdrsm = 10; &#123; Drawing move &#40;stalemate&#41; &#125;
    mfnote = 11; &#123; Notated move &#40;andf/andr/chck/chmt calculated&#41; &#125;
    mfnull = 12; &#123; Null move &#125;
    mfsrch = 13; &#123; Searched &#125;
    mfvoid = 14; &#123; Void move &#125;
I will be adding more flags later. One idea is to use a few more flags just to handle EDN (English Descriptive Notation) output, just for amusement.

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Transposition table move storage

Post by sje » Fri Dec 02, 2011 8:36 pm

Transposition table move storage:

The code is not written yet for transposition table move storage, but the design is ready.

Code: Select all

ttmovetype =
  packed record
    frsq&#58; sqtype; &#123; six bits )
    tosq&#58; sqtype; &#123; six bits )
    msc&#58;  msctype &#123; three bits &#125;
  end;
Since the program generates all moves and matches a transposition table move against the generated output, it is impossible to play an illegal move. This is true even in the extremely rare case of a false positive.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: Sample code: Moves and variations

Post by Don » Fri Dec 02, 2011 9:09 pm

I have always viewed pascal code as ugly, and verbose and this doesn't change my mind :-) C is perhaps even worse except that it's not as verbose. There has GOT to be a better way .....


sje wrote:Sample code: Moves and variations

In BozoChess, a chess move is not packed into a single scalar type but instead is a structure of unpacked data. This works well as there is no packing/unpacking overhead and there is little need to actually move the move data from place to place.

A move can live inside a move node structure which is simply an element of a two-way linked list. Each node is initially allocated by a library call, but thereafter the node can be moved from list to list just by changing a few pointers. The dynamic storage is releases via library calls only when the list is destroyed.

A variation structure is composed of two move lists. The first is the used lust which contains the moves of interest. The second is the free node list which contains free nodes which are used for appending new moves to the used list as needed. When a move node is released form the used list, it is appended to the free list for later use. The big idea here is to not call an slow library memory management routine each time a variation needs adjustment.

Using the variation data structure greatly simplifies handling predicted variations at all ply. It's also good for handling the current variation (i.e., path from the root) for tracing and debugging.

Code: Select all

    &#123; Chess move&#58; a single move with a score value &#125;

    movetype =
      record
        frsq&#58;  sqtype;  &#123; From square &#125;
        tosq&#58;  sqtype;  &#123; To square &#125;
        frman&#58; mantype; &#123; From man &#125;
        toman&#58; mantype; &#123; To man &#125;
        msc&#58;   msctype; &#123; Special case &#125;
        mfs&#58;   mfstype; &#123; Move flag set &#125;
        sv&#58;    svtype   &#123; Score value &#125;
      end;

    &#123; Move nodes &#125;

    mnptrtype = ^mntype; &#123; A pointer to a move node &#125;

    mntype =
      record
        move&#58; movetype;  &#123; The move &#125;
        prev&#58; mnptrtype; &#123; Link to previous move node &#125;
        next&#58; mnptrtype  &#123; Link to next move node &#125;
      end;

    &#123; List of move nodes &#125;

    mnlisttype =
      record
        ecount&#58; ecounttype; &#123; Element count &#125;
        head&#58;   mnptrtype;  &#123; Head of move node list &#125;
        tail&#58;   mnptrtype   &#123; Tail of move node list &#125;
      end;

    &#123; Variation &#125;

    variationtype =
      record
        freelist&#58; mnlisttype; &#123; Free move nodes &#125;
        usedlist&#58; mnlisttype  &#123; Move nodes in played order &#125;
      end;

  &#123; ***** Variation routines ***** &#125;

  procedure VariationReset&#40;var variation&#58; variationtype&#41;;
  begin
    with variation do
      begin
        MnListReset&#40;freelist&#41;;
        MnListReset&#40;usedlist&#41;
      end
  end; &#123; VariationReset &#125;

  procedure VariationRecycleTail&#40;var variation&#58; variationtype&#41;;
  begin
    with variation do
      MnListAppendTail&#40;freelist, MnListDetachTail&#40;usedlist&#41;)
  end; &#123; VariationRecycleTail &#125;

  procedure VariationRecycle&#40;var variation&#58; variationtype&#41;;
  begin
    with variation do
      while usedlist.tail <> nil do
        VariationRecycleTail&#40;variation&#41;
  end; &#123; VariationRecycle &#125;

  procedure VariationAppendMove&#40;var variation&#58; variationtype; var move&#58; movetype&#41;;
    var
      mnptr&#58; mnptrtype;
  begin
    with variation do
      begin
        if freelist.tail = nil then
          begin
            New&#40;mnptr&#41;;
            MnListAppendTail&#40;freelist, mnptr&#41;
          end;
        mnptr &#58;= MnListDetachTail&#40;freelist&#41;;
        mnptr^.move &#58;= move;
        MnListAppendTail&#40;usedlist, mnptr&#41;
      end
  end; &#123; VariationAppendMove &#125;

  procedure VariationAppend&#40;var variation, subvariation&#58; variationtype&#41;;
    var
      mnptr&#58; mnptrtype;
  begin
    with variation do
      begin
        mnptr &#58;= subvariation.usedlist.head;
        while mnptr <> nil do
          begin
            VariationAppendMove&#40;variation, mnptr^.move&#41;;
            mnptr &#58;= mnptr^.next
          end
      end
  end; &#123; VariationAppend &#125;

  procedure VariationAssign&#40;var variation, altvariation&#58; variationtype&#41;;
  begin
    VariationRecycle&#40;variation&#41;;
    VariationAppend&#40;variation, altvariation&#41;
  end; &#123; VariationAssign &#125;

  procedure VariationBuild&#40;
      var variation&#58; variationtype;
      var move&#58; movetype; var subvariation&#58; variationtype&#41;;
  begin
    VariationRecycle&#40;variation&#41;;
    VariationAppendMove&#40;variation, move&#41;;
    VariationAppend&#40;variation, subvariation&#41;
  end; &#123; VariationBuild &#125;

  procedure VariationNotate&#40;var variation&#58; variationtype; var pos&#58; postype&#41;;
    var
      mnptr&#58; mnptrtype;
      count&#58; ecounttype;
  begin
    with variation do
      begin
        count &#58;= 0;
        mnptr &#58;= usedlist.head;
        while mnptr <> nil do
          begin
            PosMoveNotate&#40;pos, mnptr^.move&#41;;
            PosExecute&#40;pos, mnptr^.move&#41;;
            Inc&#40;count&#41;;
            mnptr &#58;= mnptr^.next
          end;
        while count > 0 do
          begin
            PosRetract&#40;pos&#41;;
            Dec&#40;count&#41;
          end
      end
  end; &#123; VariationNotate &#125;

  function VariationPosEncode&#40;var variation&#58; variationtype; var pos&#58; postype&#41;&#58; String;
    var
      myresult&#58; String;
      mnptr&#58; mnptrtype;
      mc&#58; mctype;
  begin
    with variation do
      begin
        myresult &#58;= '';
        VariationNotate&#40;variation, pos&#41;;
        PosLoadToMc&#40;pos, mc&#41;;
        mnptr &#58;= usedlist.head;
        while mnptr <> nil do
          begin
            if &#40;mc.good = colorw&#41; or &#40;mnptr = usedlist.head&#41; then
              myresult &#58;= myresult + McEncode&#40;mc&#41; + ' ';
            myresult &#58;= myresult + MoveEncode&#40;mnptr^.move&#41;;
            McIncrement&#40;mc&#41;;
            mnptr &#58;= mnptr^.next;
            if mnptr <> nil then
              myresult &#58;= myresult + ' '
          end
      end;
    VariationPosEncode &#58;= myresult
  end; &#123; VariationPosEncode &#125;

  procedure VariationInit&#40;var variation&#58; variationtype&#41;;
  begin
    with variation do
      begin
        MnListInit&#40;freelist&#41;;
        MnListInit&#40;usedlist&#41;
      end
  end; &#123; VariationInit &#125;

  procedure VariationTerm&#40;var variation&#58; variationtype&#41;;
  begin
    with variation do
      begin
        MnListTerm&#40;freelist&#41;;
        MnListTerm&#40;usedlist&#41;
      end
  end; &#123; VariationTerm &#125;

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: Sample code: Moves and variations

Post by Zach Wegner » Sat Dec 03, 2011 2:37 am

Don wrote:I have always viewed pascal code as ugly, and verbose and this doesn't change my mind :-) C is perhaps even worse except that it's not as verbose. There has GOT to be a better way .....
Yes, Python!

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: Sample code: Moves and variations

Post by Don » Sat Dec 03, 2011 4:48 am

Zach Wegner wrote:
Don wrote:I have always viewed pascal code as ugly, and verbose and this doesn't change my mind :-) C is perhaps even worse except that it's not as verbose. There has GOT to be a better way .....
Yes, Python!
Python's way of intending code is quite interesting and has inspired a lot of discussion and "religious wars" even.

I like the Python way of indenting. However I prefer Ruby over Python as a language in general but they are both great.

Post Reply