Engine programming

[Gejsi Marku]

My goal is pretty simple: learn enough programming to create a simple basic functional engine. Not caring about elo strength.. yet.

After that goal is achieved I would like to either 1) contribute to an open source, or 2) Develop further my own engine focusing on performance and few ideas of mine.

[Jonathan003]

Hi,

I was reading about your wish to learn to program to make a chess engine.
Why do you want to create a chess engine?
It seams to me that many programmers are focused on chess engine programming?
I think what the chess world needs is better software to make humans better chess players.
Like Chess Position Trainer. cpt 6 was promised to be released in 2019 but it's still not here.

I have a great chess passion. And I have all count of chess software you can think of, booth for windows as for android.
I try every software to see how it can make me a better player.
I'm focused mostly on best ways to make a repertoire based on my playing style.
For example I would like to be able to edit the playing style of an engine, so it fit's my own style and than let it create a repertoire in pgn. One for white and one for black. And some way to sort the repertoires in small chunks to be able to train them. I would like to create a wide repertoire to start with. Than some logic way to make a narrow repertoire from it. Than later whiden the repertoire in steps till I know the complete repertoire.
Making a good repertoire with existing chess software is very time consuming, and I find this frustrating.
Fritz 17 comes with standard repertoires you can train. But it's better to learn someone how to fish than just give him a fish.

[phhnguyen]

Hi,

I was reading about your wish to learn to program to make a chess engine.
Why do you want to create a chess engine?
It seams to me that many programmers are focused on chess engine programming?
I think what the chess world needs is better software to make humans better chess players.
Like Chess Position Trainer. cpt 6 was promised to be released in 2019 but it's still not here.

I have a great chess passion. And I have all count of chess software you can think of, booth for windows as for android.
I try every software to see how it can make me a better player.
I'm focused mostly on best ways to make a repertoire based on my playing style.
For example I would like to be able to edit the playing style of an engine, so it fit's my own style and than let it create a repertoire in pgn. One for white and one for black. And some way to sort the repertoires in small chunks to be able to train them. I would like to create a wide repertoire to start with. Than some logic way to make a narrow repertoire from it. Than later whiden the repertoire in steps till I know the complete repertoire.
Making a good repertoire with existing chess software is very time consuming, and I find this frustrating.
Fritz 17 comes with standard repertoires you can train. But it's better to learn someone how to fish than just give him a fish.

IMO, it is very hard to customize a given chess engine to fit a given user playing style. Basically, a typical chess engine has fixed-in-code the search and the evaluation functions thus it is almost fixed to a playing style. Some engines allow changing some parameters (or you can pick up an open-source and change parameters in its code) - but it is not enough to have multi-playing styles. It means it could fit someone but not other ones. Furthermore, The default parameters usually are optimized and the best thus users may easily make engines worse or broken when customizing those paras.

For Lc0 family - a new way to create a chess engine, those engines can learn. However, that is self-learning and engines only learn what they want. In other words, at least for recent states, they are almost fixed to their playing styles and we can't change either.

Thus I think to have games closed to a user playing style:
- Find an engine which is the fittest (instead of waiting for a new and magical engine)
- Create or customize an opening book that easily leads to that style. Or simpler, create a set of FENs to start games in that style. Many chess GUIs can help in that way

Good luck

[Ovyron]

IMO, it is very hard to customize a given chess engine to fit a given user playing style. Basically, a typical chess engine has fixed-in-code the search and the evaluation functions thus it is almost fixed to a playing style. Some engines allow changing some parameters (or you can pick up an open-source and change parameters in its code) - but it is not enough to have multi-playing styles.

I think the Rodent engine proved this is possible (i.e. the Karpov playing style would produce games that someone couldn't tell if it was played by the engine or by Karpov.)

The Rebel (later Pro Deo, even later Benjamin) engine also provided very different multi-playing styles that emulated famous GM moves, and even allowed swindling and changing radically playing style depending on the stage of the game or how the game is going (say, the engine plays in the style of Kasparov at the beginning, if it begins to win it morphs into Tal and if it is losing it morphs into Alekhine, etc.)

[hgm]

My goal is pretty simple: learn enough programming to create a simple basic functional engine. Not caring about elo strength.. yet.

After that goal is achieved I would like to either 1) contribute to an open source, or 2) Develop further my own engine focusing on performance and few ideas of mine.

Because of your future goal (1) it would then probably be best to learn C/C++, as most open-source engines are written in it. Also, you can start with plain C, or even a subset of C. It is perfectly possible to write a basic chess engine without using pointers or structures.

You should realize that the basic part of most programming languages is conceptually very similar. In terms of natuaral languages, you could say that they only differ in the spelling of the words. (Although there are certainly exceptions; e.g. Lisp comes to mind.) I once went through the exercise of converting a pretty complex BASIC program to C (because it was written for a BASIC that no longer could run on modern computers), and I could almost entirely do it through 'replace all' commands of a text editor.

Learning to program mostly boils down to learning how to break down complex tasks (e.g. "sort this table into alphabetical order") into smaller, manageable sub-tasks (e.g. "swap two given table elements" and "compare which of two given table elements comes first, alphabetically").

A chess engine is not the easiest program to write. OTOH, it doesn't have to be a ver complex program. E.g. the simplest version of micro-Max only consists of some 100 short lines of source code. A more advanced version, with somewhat enhanced readability for humans (by using more obvious names for the variables than single letters) is this:

Code: Select all

/***************************************************************************/
/*                               micro-Max,                                */
/* A chess program smaller than 2KB (of non-blank source), by H.G. Muller  */
/***************************************************************************/
/* version 3.2 (2000 characters) features:                                 */
/* - recursive negamax search                                              */
/* - quiescence search with recaptures                                     */
/* - recapture extensions                                                  */
/* - (internal) iterative deepening                                        */
/* - best-move-first 'sorting'                                             */
/* - a hash table storing score and best move                              */
/* - full FIDE rules (expt under-promotion) and move-legality checking     */

/* This version is for reference only, with all variable names changed to  */
/* be more indicative of their meaning, and better layout & more comments. */
/* There is no guarantee, though, that it still compiles or runs.          */

#include <stdio.h>
#include <math.h>

#define F(I,S,N) for(I=S;I<N;I++)
#define W(A) while(A)
#define K(A,B) *(int*)(Zobrist+A+(B&8)+S*(B&7))
#define J(A) K(ToSqr+A,Board[ToSqr])-K(FromSqr+A,Piece)-K(CaptSqr+A,Victim)

#define HASHSIZE 16777224
struct _ 
{ int  Key, Score;
  char From, To, Draft;
} HashTab[HASHSIZE];                                   /* hash table, 16M+8 entries*/

int V=112, M=136, S=128, INF=8e3, C=799,               /* V=0x70=rank mask, M=0x88 */
    Rootep, Nodes, i; 

char RootEval, InputFrom, InputTo,
PieceVal[] = {0,1,1,3,-1,3,5,9},                       /* relative piece values    */
StepVecs[] =                                           /* step-vector lists        */
         {-16,-15,-17,0,                               /* white Pawn               */
           1,16,0,                                     /* Rook                     */
           1,16,15,17,0,                               /* Q,K, also used for B, bP */
          14,18,31,33,0,                               /* Knight                   */
          7,-1,11,6,8,3,6,                             /* first direction per piece*/
          6,3,5,7,4,5,3,6},                            /* initial piece setup      */
Board[129],                                            /* board: half of 16x8+dummy*/
Zobrist[1035],                                         /* hash translation table   */
  
Sym[] = ".?+nkbrq?*?NKBRQ";                            /* piece symbols on printout*/

int Search(int Side, int Alpha, int Beta, int Eval, int HashKeyLo, int HashKeyHi,
                                                    int epSqr, int LastTo, int Depth)
{                       
  int j, StepVec, BestScore, Score, IterDepth, h, i=8, SkipSqr, RookSqr;
  char Victim, PieceType, Piece, FromSqr, ToSqr, BestFrom, BestTo, CaptSqr, StartSqr;
  struct _*Hash = HashTab;

  /* Hash probe. On miss (Internal) Iterative Deepening starts at IterDepth=0,     */
  /* without move hint. On a hit we start IID from the hashed values, except       */
  /* when the depth is already sufficient. In this case, if the bound type OK,     */
  /* we use the hashed score immediately, and otherwise we just do the last        */
  /* iteration starting with the hash move.                                        */
                                                       /* lookup pos. in hash table*/
  j = (Side*epSqr^HashKeyLo) & HASHSIZE-9;             /* try 8 consec. locations  */
  while((h=HashTab[++j].Key) && h-HashKeyHi && --i);   /* first empty or match     */
  Hash += i ? j : 0;                                   /* dummy A[0] if miss & full*/
  if(Hash->Key)                                        /* hit: pos. is in hash tab */
  { IterDepth = Hash->Draft; 
    Score     = Hash->Score;
    BestFrom  = Hash->From;                            /* examine stored data      */
    if(IterDepth >= Depth)                             /* if depth sufficient:     */
    { if(Score >=  Beta|BestFrom&S &&
         Score <= Alpha|BestFrom&8
        ) return Score;                                /* use if window compatible */
      IterDepth = Depth-1;                             /* or use as iter. start    */
    } 
    BestFrom &= ~0x88; 
    BestTo    = Hash->To;                              /*      with best-move hint */
    BestTo    = IterDepth ? BestTo : 0;                /* don't try best at d=0    */
  } else IterDepth = BestFrom = BestTo = 0;            /* start iter., no best yet */
  
  Nodes++;                                             /* node count (for timing)  */
  
  /* We have to search the current node; deepen the search in steps of one         */
  /* starting from the hashed data as if it were the previous iteration.           */
  /* In the root (LastTo==8) we deepen until node count or max. depth reached.     */

  while(IterDepth++ < Depth |                          /* iterative deepening loop */
       LastTo==8 & Nodes<1e7 & IterDepth<98)           /* at root until node limit */
  { /* Each iteration consist of a move-generation run, immediately searching      */
    /* all moves as they are generated. The best move from the previous iter-      */
    /* ation (still contained in BestFrom, BestTo) is slipped in front, though.    */
    /* To make this easier, move generation starts at StartSqr = BestFrom.         */
    /* The S-bit of BestTo indicates if there is a valid best move to try.         */
    FromSqr = StartSqr = BestFrom;                    /* start scan at prev. best  */
    ToSqr  |= 8 & ToSqr>>4;                            /* request try noncastl. 1st*/
    BestScore = IterDepth>1 ? -INF : Eval;             /* unconsidered:static eval */
    do      
    { Piece = Board[FromSqr];                          /* scan board looking for   */
      if(Piece & Side)                                 /*  own piece (inefficient!)*/
      { StepVec = PieceType = Piece&7;                 /* set StepVec > 0          */
        j = StepVecs[PieceType+16];                    /* first step vector Piece  */
        while(StepVec = PieceType>2&StepVec<0 ? -StepVec : -StepVecs[++j])                    
                                                       /* loop over directions o[] */
        {replay:                                       /* resume normal after best */
          /* For each direction we scan ToSqr along the ray startig at FromSqr.    */
          ToSqr   = FromSqr;
          SkipSqr = RookSqr = S;                       /* S = 0x80 = dummy square  */
          do
          { CaptSqr = ToSqr += StepVec;                /* ToSqr traverses ray      */

            /* FromSqr, ToSqr here scan through all tentative moves. If there      */
            /* is an old best move to try first, this is indicated in the 8-bit    */
            /* of BestTo (which was copied from the S-bit), and we overrule the    */
            /* generated ToSqr (which might ly at other distance or in direction)  */
            /* We then test if ToSqr is on the board, if we have an e.p. capture,  */
            /* are blocked by an own piece, and if Pawn moves are valid.           */
            if(BestTo & 8) 
              CaptSqr = ToSqr = BestTo&~0x88;          /* sneak-in prev. best move */
            if(ToSqr & 0x88) break;                    /* board edge hit (M=0x88)  */
            if(PieceType<3 & ToSqr==epSqr)
              CaptSqr = ToSqr^16;                      /* shift CaptSqr if e.p.    */
            Victim = Board[CaptSqr];
            if(Victim & Side |                         /* capture own              */
               PieceType<3 & !(StepVec&7) != !Victim   /*            bad pawn mode */
              ) break;      

            /* If we get here, we have a pseudo-legal move in (FromSqr, ToSqr).    */
            /* We check it for King capture (or Rook capture after castling).      */
            /* This can give a beta cutoff, as can the stand-pat score in QS.      */
            i = 99*PieceVal[Victim&7];                 /* value of victim piece    */
            if(i<0 ||                                  /* K capt. or               */
                      epSqr-S && Board[epSqr] &&       /* non-empty epSqr:castling */
                      ToSqr-epSqr<2 & epSqr-ToSqr<2    /*             bad castling */
              ) BestScore = INF;     
            if(BestScore >= Beta) goto cutoff;         /* abort on fail high       */
             
            /* We now have a move to search. If there is depth left, we different- */
            /* ially update the evaluation, Make the move, Search it recursively   */
            /* UnMake it, and update the best score & move. If not, we ignore it.  */
            if(h = IterDepth - (ToSqr!=LastTo))        /* remaining depth(-recapt.)*/
            { Score = PieceType<6 ? Board[FromSqr+8]-Board[ToSqr+8] : 0;
                                                       /* center positional pts.   */

              /* Make move & evaluate                                              */
              Board[RookSqr] = Board[CaptSqr] = Board[FromSqr] = 0;
              Board[ToSqr]   = Piece&31;               /* do move, strip virgin-bit*/
              if(!(RookSqr&0x88))
              { Board[SkipSqr] = Side+6;               /* castling: put Rook       */
                Score += 30;                           /*                 & score  */
              }                                     

              if(PieceType<3)                          /* pawns:                   */
              { Score -=                               /* structure, undefended    */
                9*(((FromSqr-2)&M||Board[FromSqr-2]!=Piece) + /* squares plus bias */
                   ((FromSqr+2)&M||Board[FromSqr+2]!=Piece) - 1); 
                if(ToSqr+StepVec+1&S)
                { Board[ToSqr] |= 7;                   /* promote Pawn to Queen,   */
                  i += C;                              /*                add score */
              } }
              
              Score = -Search(                         /* recursive eval. of reply */
                              24-Side,                 /* opponent color           */
                             -Beta-(Beta>Eval),        /* new Alpha (delayed gain!)*/
                              BestScore>Alpha ? -BestScore : -Alpha,  /* New Beta  */
                             -Eval-Score-i,            /* New Eval                 */
                              HashKeyLo+J(0),          /* New HashKeys             */
                              HashKeyHi+J(8)+SkipSqr-S,/* SkipSqr-S!=0 on castling */
                              SkipSqr, ToSqr, h);      /* New epSqr, LastTo, Depth */

              Score -= Score>Eval;                     /* delayed-gain penalty     */

              /* If the Search routine was called as move-legality checker, we     */
              /* now return before unmaking the move if it was the input move.     */
              if(LastTo==9)                            /* called as move-legality  */
                                                       /*   checker                */
              { if(Score!=-INF & FromSqr==InputFrom & ToSqr==InputTo)/* move found */
                { RootEval = -Eval-i;                  /* update eval, material    */
                  Rootep   = SkipSqr;
                  return Beta;                         /*   & not in check, signal */
                } 
                Score = BestScore;                     /* (prevent fail-lows on    */
              }                                        /*   K-capt. replies)       */

              /* UnMake move                                                       */
              Board[RookSqr] = Side+38;                /* undo move,RookSqr can be */
              Board[SkipSqr] = Board[ToSqr] = 0;       /*                    dummy */
              Board[FromSqr] = Piece;
              Board[CaptSqr] = Victim;

              /* Process score. If the move just searched was a previous best      */
              /* move that was tried first, we take its Score and redo the first   */
              /* ray of this piece. Otherwise update best score and move.          */
              if(BestTo&8)                            /* Move just done was in-    */
              { BestScore = Score;                    /*     serted previous best  */
                BestTo   &= ~8;                       
                goto replay;
              }                                       /* redo original first move  */

              if(Score>BestScore)
              { BestScore = Score;                    /* update max,               */
                BestFrom  = FromSqr;                  /* best move,                */
                BestTo    = ToSqr | S&RookSqr;        /* mark non-castling with S  */
            } }

            /* Determine if we have to continue scanning this ray. We must stop    */
            /* on a capture, or if the piece is a non-slider, with the exceptions  */
            /* of double moves for Pawns and King (castlings!). Such double moves  */
            /* cause setting of the SkipSqr, that otherwise is equal to the dummy S*/
            Victim += PieceType<5;                    /* fake capt. for nonsliding */
            if(PieceType<3&6*Side+(ToSqr&0x70)==S     /* pawn on 3rd/6th, or       */
                ||(Piece&~24)==36 &                   /* virgin K,                 */
                   j==7 &&                            /* moving sideways,          */
                   RookSqr&0x88 &&                    /* RookSqr not yet set       */
                   Board[RookSqr=(FromSqr|7)-(StepVec>>1&7)]&32 &&
                                                      /* virgin Rook in corner     */
                   !(Board[RookSqr^1]|Board[RookSqr^2]) /* 2 empty sqrs. next to R */
              ) { SkipSqr = ToSqr; Victim--; }        /* unfake capt., enable e.p. */

            /* continue ray scan if move was non-capture                           */
          } while(!Victim);                           /* if not capt. continue ray */ 

    } } } while((FromSqr=FromSqr+9&~0x88)-StartSqr);  /* next sqr. of board, wrap  */

    /* All moves have been searched; wrap up iteration by testing for check- or    */
    /* stalemate, which leave Score at -INF. Call Search with Depth=1 after null   */
    /* move to determine if we are in check. Finally store result in hash.         */
cutoff:     
    if(BestScore>INF/4 | BestScore<-INF/4)
      IterDepth=99;                                   /* mate is indep. of depth   */
    BestScore = BestScore+INF ? BestScore :           /* best loses K: (stale)mate */
               -Search(24-Side, -INF, INF, 0, HashKeyLo, HashKeyHi, S, LastTo, 1)/2;

    if(!Hash->Key | (Hash->From&M)!=M | Hash->Draft<=IterDepth) 
                                                      /* if new/better type/depth: */
    { Hash->Key    = HashKeyHi;                       /* store in hash,            */
      Hash->Score  = BestScore;
      Hash->Draft  = IterDepth;
      HashTab->Key = 0;                               /* dummy stays empty         */
      Hash->From   = BestFrom |                       /* From & bound type         */
                     8*(BestScore>Alpha) |            /*    encoded in X S,8 bits  */
                     S*(BestScore<Beta);              /* (8=lower, S=upper bound)  */
      Hash->To     = BestTo;                         
    }                                                 

    /* End of iteration. Start new one if more depth was requested                 */
    /*  if(LastTo==8)printf("%2d ply, %9d searched, %6d by (%2x,%2x)\n",
                                IterDepth-1,Nodes,BestScore,BestFrom,BestTo&0x77); */
  }

  /* return best score (and in root also best move) after all iterations are done. */
  if(LastTo&8)
  { InputFrom = BestFrom;
    InputTo   = BestTo & ~0x88;
  }
  return BestScore;
}

int main(void)
{
 int j, Side=8, *ptr, InBuf[9];                            /* 8=white, 16=black  */

 /* Initialize board and piece-square table (actually just a square table).      */
 for(i=0;i<8;i++)                                          /* initial board setup*/
 {Board[i] = (Board[i+0x70] = StepVecs[i+24]+40)+8;        /* Pieces             */
  Board[i+0x10] = 18; Board[i+0x60] = 9;                   /* black, white Pawns */
  for(j=0;j<8;j++) Board[16*j+i+8]=(i-4)*(i-4)+(j-3.5)*(j-3.5); 
                                                           /*common pce-sqr table*/
 }                                                         /*(in unused half b[])*/
 for(i=0x88; i<1035; i++) Zobrist[i]=rand()>>9;

 while(1)                                                  /* play loop          */
 {for(i=0;i<121;i++)
   printf(" %c", i&8&&(i+=7) ? '\n' : Sym[Board[i]&15]);   /* print board        */
  ptr = InBuf; while((*ptr++ = getchar()) > '\n');         /* read input line    */
  Nodes=0;
  if(*InBuf-'\n')
  {InputFrom=InBuf[0]-16*InBuf[1]+C;                       /* parse entered move */
   InputTo  =InBuf[2]-16*InBuf[3]+C;
  } else Search(Side,-INF,INF,RootEval,1,1,Rootep,8,0);    /* or think up one    */
  for(i=0;i<HASHSIZE;i++)HashTab[i].Key=0;                 /* clear hash table   */
  if(Search(Side,-INF,INF,RootEval,1,1,Rootep,9,2)==INF)
    Side^=24;                                              /* check legality & do*/
 }
 return 0;
}

[Ovyron]

I've always known about it but it's the first time that I see it, it's very impressive how a fully working chess program fits in a small post!

[Ovyron]

(except for lack of underpromotion and legality checking, but pretty close...)

[hgm]

It does full legality checking, in the last statement of the command-interpreter loop in main()! This is why there is a second call to Search(), and the side to move is only changed if that call 'succeeds'. (In version 4.8 I managed to collapse these two calls into one.) The trick is that the search tests, in the root, whether the move it just tried is equal to the input move, and if it is then aborts the search before UnMaking that move. But it only does that if its score from searching it deeper is not -INF (which would mean the reply could capture the King). So ordering a 2-ply search with a legal input move leaves that move done. An illegal or garbage input move would never match any searched move, and would make the search return without changing anything.

[Ovyron]

Would the size increase significantly if underpromotion was added? 2000 characters seem like an arbitrary count so I'd rather see a full implementation of the smallest program.

[hgm]

Would the size increase significantly if underpromotion was added? 2000 characters seem like an arbitrary count so I'd rather see a full implementation of the smallest program.

No, it would not. In fact my website does show a version (micro-Max 1.6) that allows the user to underpromote. It only measures 1433 characters, but it is a lot weaker than 3.2 or 4.8. (E.g. no hash table.) And the under-promotion is supported in a bit of a kludgy way: you have to type the move with promotion suffix 1, 2 or 3 for R, B or N, respectively.

The 2000 characters is indeed arbitrary, but the goal was never to be under a specific number of characters. The goal was to optimize the number of Elo points per character of source code. Adding the code to support underpromotion would decrease that ratio, as underpromotion adds virtually no Elo at all, even if you consider any case where its lack of support leads to an illegal move or false illegal-move claim as a loss. (If the opponent promotes to R or B, not much is lost by having the engine imagine that it is a Queen. Neither can any case where the promoted Pawn is immediately taken. So only a surviving Knight causes a problem.) This is why version 4.8 doesn't have it.

For micro-Max 1.6 the goal was just to be a very small alpha-beta engine that supported all rules. So there acceptance of under-promotion was part of the goal. That it cannot under-promote itself just means it sometimes does a grossly sub-optimal move, of which it would do plenty anyway.

BTW, as smallest program micro-Max has now been superceded by Toledo nanoChess. Which, I believe, fully supports under-promotion, even playing it himself.