N.E.G. 1.0 released

[hgm]

Interesting strategy improvement: I can reduce the number of stalemates in positions where it is several Queens ahead to almost zero by refusing to capture the last minor. Only in cases where the minor happens to get pinned this still produces the occasional stalemate.

[supersharp77]

There is no link to download this engine and your web site only shows NEG 0.3 for download........Thx AAR

[hgm]

I uploaded the new versions to my website now. It even includes an x64 Linux build.

This is for the version with stalemate avoidance (N.E.G. 1.2), which refuses to take the opponent's last minor when it is more than a Queen ahead.

[Roland Chastain]

It looks like I discovered a bug in NEG 1.2. Here is the PGN file.

[pgn][Event "?"]
[Site "?"]
[Date "2019.12.28"]
[Round "5"]
[White "Floyd 0.9"]
[Black "NEG 1.2"]
[Result "1-0"]
[ECO "A04"]
[Opening "Reti Opening"]
[PlyCount "45"]
[Termination "illegal move"]
[TimeControl "40/60"]

1. Nf3 {+0.20/9 0.54s} Nc6 {+0.06/2 0s} 2. d4 {+0.36/10 1.2s} Nf6 {-0.24/2 0s}
3. c4 {+0.29/10 0.58s} a5 {-0.24/2 0s} 4. d5 {+0.74/11 0.79s} Nb4 {-1.10/2 0s}
5. Nc3 {+0.79/11 0.95s} c5 {-2.09/2 0s} 6. a3 {+1.15/11 0.60s} Na6 {+0.26/2 0s}
7. Qa4 {+1.11/11 0.63s} e6 {-0.14/2 0s} 8. e4 {+1.38/10 0.82s} Bd6 {-0.14/2 0s}
9. e5 {+2.45/9 0.80s} Be7 {+2.11/2 0s} 10. d6 {+3.24/10 0.55s} Bf8 {+2.11/2 0s}
11. exf6 {+3.49/10 0.91s} gxf6 {-0.98/2 0s} 12. Nb5 {+3.46/11 0.58s}
h5 {-0.08/2 0s} 13. Be2 {+3.71/9 0.64s} Bg7 {-1.10/2 0s}
14. O-O {+3.90/10 0.71s} b6 {-1.00/2 0s} 15. Bf4 {+3.98/10 0.67s}
Bb7 {-1.00/2 0s} 16. Nc7+ {+4.53/9 0.60s} Nxc7 {+1.14/2 0s}
17. dxc7 {+3.26/11 0.79s} Qc8 {-1.00/2 0s} 18. Qb5 {+3.02/12 2.2s}
Be4 {-1.00/2 0s} 19. Qxb6 {+4.59/9 0.80s} d5 {-0.22/2 0s}
20. cxd5 {+6.87/8 0.66s} exd5 {+1.20/2 0s} 21. Qxc5 {+13.99/8 3.4s}
f5 {-0.13/2 0s} 22. Bb5+ {+M9/6 0.71s} Qd7 {-6.00/2 0s}
23. c8=R+ {+M7/4 0.004s, Black makes an illegal move: g7b2} 1-0[/pgn]

[hgm]

Indeed. I see that it only recognizes a move as a promotion when there is a 'q' suffix, and otherwise doesn't promote it at all. So the Pawn remains a Pawn, and there is no check to resolve.

BTW, the most obvious and annoying weakness of N.E.G. is that it does not consider capture of an attacker as solving the threat it makes. So after 1. e4 e5 2. Bb5+ Nc6 3. d3 d6 4. Bxc6+ it would play Ke7 to solve the check (which is of course the dominant threat, with a King at stake), rather than bxc6 (which in its eyes only gains a Bishop). Especially for threats exerted by only a single attacker it should be relatively easy to cure that.

[Roland Chastain]

Indeed. I see that it only recognizes a move as a promotion when there is a 'q' suffix, and otherwise doesn't promote it at all. So the Pawn remains a Pawn, and there is no check to resolve.

I see. I could have suspected that the problem came from the unusual promotion on rook.

BTW, the most obvious and annoying weakness of N.E.G. is that it does not consider capture of an attacker as solving the threat it makes. So after 1. e4 e5 2. Bb5+ Nc6 3. d3 d6 4. Bxc6+ it would play Ke7 to solve the check (which is of course the dominant threat, with a King at stake), rather than bxc6 (which in its eyes only gains a Bishop). Especially for threats exerted by only a single attacker it should be relatively easy to cure that.

Interesting. I like when I understand how an engine "thinks". I have just taken a look at the source code. It's a very beautiful program. If I had time, I would like to try a conversion to Pascal.

[Roland Chastain]

@H.G.Muller

By the way, may I ask if you still have the source code of older versions? I have a Windows binary of N.E.G. 0.3, that I often use. I would have liked (if possible) to see the source code.

Same question for Ram 2.0.

It isn't easy to search for these engines on the web, because the names are too short.

[hgm]

I uploaded a fixed version (1.3) to the same link (souce & Windows .exe). It now also tests for r, b or n suffix on the input move, and performs the indicated promotion if it finds one.

I guess it would need an extra run of the move generator to make it realize that capture can solve a solo threat: it would run for the opponent with a task function somewhat similar to Score(), which would ignore any move that does not capture or that goes to square with more than one attacker, and remember the score of the best such move at the from-square (initialized to 0 before the MoveGen). In the routine Score() this value for the to-square should then be added to the score.

I guess this would already give a big improvement. It would be more difficult to also apply this to threats with more than a single attacker. Because how much that matters would depend on what the other attacker is. Reducing a 2-attacker-1-protector threat (which would gain the entire victim) to 1 vs 1 might not make the entire threat go away, as the remaining attacker could be of lower value than the victim. But perhaps it could not hurt much to assume it does. As usually one of the attackers would be more valuable than the victim (or the threat could have been cashed before), and thus no threat when we take out its support. And when we take the more valuable attacker the opponent is under pressure to take that back first, rather than cash the the threat.

[hgm]

@H.G.Muller

By the way, may I ask if you still have the source code of older versions? I have a Windows binary of N.E.G. 0.3, that I often use. I would have liked (if possible) to see the source code.

Same question for Ram 2.0.

It isn't easy to search for these engines on the web, because the names are too short.

N.E.G. 0.3 was actually a slightly modified version of my regular alpha-beta engine Joker, which was closed source. I haven't worked on that since 2008, and I am not even sure I do have sources, as this is many computers ago.

The Ram 2.0 source is below. It should be linked with the MersenneTwister random generator.

Code: Select all

#include <stdio.h>

#ifdef WIN32 
#    include <windows.h>
#else
#    include <sys/time.h>
#    include <sys/times.h>
#    include <unistd.h>
     int GetTickCount()
     {	struct timeval t;
	gettimeofday(&t, NULL);
	return t.tv_sec*1000 + t.tv_usec/1000;
     }
#endif

#define WHITE 8
#define BLACK 16
#define COLOR (WHITE|BLACK)

double genrand64_real2(void);
int MTinit(int t);

unsigned int MyRandom(unsigned int n)
{
  unsigned int res = n*genrand64_real2();
  return res;
}

typedef void Func(int stm, int from, int to, void *closure);
typedef int Board[128];

int value[8] = { 0, 100, 100, 10000, 325, 350, 500, 950 };
int firstDir[] = { 0, 0, 27, 4, 18, 8, 13, 4 };
int steps[] = { -16, -15, -17, 0, 1, -1, 16, -16, 15, -15, 17, -17, 0, 1, -1, 16, -16, 0, 18, 31, 33, 14, -18, -31, -33, -14, 0, 16, 15, 17, 0 };
Board PST = {
 0, 2, 4, 6, 6, 4, 2, 0,   0,0,0,0,0,0,0,0,
 2, 8,10,12,12,10, 8, 2,   0,0,0,0,0,0,0,0,
 6,12,16,18,18,16,12, 6,   0,0,0,0,0,0,0,0,
 8,14,18,20,20,18,14, 8,   0,0,0,0,0,0,0,0,
 8,14,18,20,20,18,14, 8,   0,0,0,0,0,0,0,0,
 6,12,16,18,18,16,12, 6,   0,0,0,0,0,0,0,0,
 2, 8,10,12,12,10, 8, 2,   0,0,0,0,0,0,0,0,
 0, 2, 4, 6, 6, 4, 2, 0,   0,0,0,0,0,0,0,0
};


//              "abcdefghijklmnopqrstuvwxyz"
char pieces[] = ".5........3..4.176........";
int pVal[] = { 0, 1, 1, 10, 3, 3, 5, 9 };
Board board, checkRay;
int Zobrist[8*128], posKey, cnt50;
int bestScore, bestFrom, bestTo, lastMover, lastChecker, randomize, post, king, seq, minors, alwaysQueen, biased, silent;

unsigned int nMoves[2], moveList[2][4096], keyHash[2][1024];

#define C1 40
#define C2 40
#define P1 250
#define P2 250
#define N1 75
#define N2 75
#define M1 60
#define M2 60
#define K1 50
#define K2 50
#define Q1 30
#define Q2 30

int strategy[2][8][8] = {
  { {  0,  0,  0,  0,  0,  0,  0, 35 },
    {  1,400,400, P1, P1, P1, P1,400 },
    {  1,400,400, P1, P1, P1, P1,400 },
    {  1, K1, K1, K1, K1, K1, K1, K1 },
    {  1, N1, N1, N1,150, N1, N1, N1 },
    {  1, M1, M1, M1, M1,100, M1,100 },
    {  1, C1, C1, C1, C1, C1, 60,100 },
    {  1,  6,  6, Q1, 25, 80, 80,100 },
  },
  { {  0,  0,  0,  0,  0,  0,  0, 35 },
    {  1,400,400, P2, P2, P2, P2,400 },
    {  1,400,400, P2, P2, P2, P2,400 },
    {  1, K2, K2, K2, K2, K2, K2, K2 },
    {  1, N2, N2, N2,150, N2, N2, N2 },
    {  1, M2, M2, M2, M2,100, M2,100 },
    {  1, C2, C2, C2, C2, C2, 60,100 },
    {  1,  6,  6, Q2, 25, 80, 80,100 },
  },
};

int
MoveGen (int stm, int lastTo)
{
  int move, from, to, piece, victim, type, dir, step, stop, vert, side = stm >> 4, n = 0;
  king = -1; seq++;
  for(from=0; from<128; from = from + 9 & ~8) {
    piece = board[from];
    if(piece) minors += 2 - ((piece & 6) == 4);
    if(piece & stm) {
      type = piece & 7;
      dir = firstDir[type];
      while((step = steps[dir++])) {
        to = from;
        do {
          to += step;
          if(to & 0x88) break;
          stop = victim = board[to];
          if((victim ^ piece) < WHITE) break; // captures friend
          if(type < 3) { // Pawn
            int vert = !(to - from & 7);
            if(vert != !victim) break; // wrong mode
            move = 256*from + to;
            if(vert && (type == 1 ? to > 79 : to < 48)) stop--; // precompensate leaper on 3rd rank
            if(type == 1 ? to < 16 : to > 111) {    // promotion
              move += (6 - side) << 16;             // to Queen
              move += strategy[side][0][7]<<20;
              if(!alwaysQueen, 0)
              moveList[side][n++] = move - (1<<16), // to Rook
              moveList[side][n++] = move - (2<<16), // to Bishop
              moveList[side][n++] = move - (3<<16); // to Knight
            }
          } else move = 256*from + to;
          move += strategy[side][type][victim&7]<<20;
          if((victim & 7) == 3) { // king capture
            king = to;
	    if(lastTo != to)
            do {
              checkRay[to -= step] = seq; // mark check ray and attacker
            } while(to != from);
            return 1;
          }
          moveList[side][n++] = move;
          stop += type < 5;
        } while(!stop);
      }
    }
  }
  nMoves[side] = n;
  return 0;
}

int draw50, rep3, stalemate, insuf, checkmate[3];

void
GameEnd (int result, char *msg)
{
  if(result) checkmate[result+1]++; else
  if(*msg == '3') rep3++; else
  if(*msg == '5') draw50++; else
  if(*msg == 'i') insuf++; else
  if(*msg == 's') stalemate++;
  if(silent) return;
  printf("%s {%s}\n", result ? (result == 1 ? "1-0" : "0-1") : "1/2-1/2", msg);
  fflush(stdout);
}

int
Pick (int side)
{
  int n = nMoves[side];
  if(!biased) return MyRandom(n);
  int i, w;
  for(i=w=0; i<n; i++) w += moveList[side][i] >> 20;
  int x = MyRandom(w);
  for(i=w=0; i<n; i++) {
    w += moveList[side][i] >> 20;
    if(w > x) return i;
  }
  return 0; // dead code
}

int
DrawCheck(int stm, int from, int to, int piece, int victim)
{
  int side = stm >> 4;
  posKey += Zobrist[128*(piece&7) + to + stm - WHITE]
          - Zobrist[128*(piece&7) + from + stm - WHITE]
          - Zobrist[128*(victim&7) + to - stm + BLACK];
  int index = posKey & 1023;
  int key = keyHash[side][index];
  if((posKey ^ key) & ~1023) keyHash[side][index] = posKey & ~1023; // no match; save position key
  else { // posKey was already hashed: repetition
    if(keyHash[side][index]++ & 1) { GameEnd(0, "3-fold repetition"); return 1; }
  }
  if(cnt50 >= 100) { GameEnd(0, "50-move rule"); return 1; }
  cnt50++; if(victim || (piece & 7) < 3) cnt50 = 0;
  if(minors < 6) { GameEnd(0, "insufficient material"); return 1; }
  return 0;
}

int
Think (int stm)
{
  int from, to, piece, promo, pinSeq, pinned = -1, side = stm >> 4;

  while(nMoves[side]) {
    int n = Pick(side);
    int move = moveList[side][n];
    to = move & 0xFF; from = move >> 8 & 0xFF, promo = move >> 16 & 0xF; // decode
    if(from == pinned && checkRay[to] != pinSeq) { // this moves a piece known to be pinned from the pin ray
      moveList[side][n] = moveList[side][--nMoves[side]]; // delete the illegal move
      continue; // and try again
    }
    int piece = board[from];
    int victim = board[to]; board[to] = piece + promo; board[from] = 0; // make move
    minors = 0; // set up to detect mating potential
    if(!MoveGen(stm ^ COLOR, to)) {
      static char *name[] = { "", "", "k", "n", "b", "r", "q" };
      if(!silent) printf("move %c%d%c%d%s\n", (from&7)+'a', 8-(from>>4), (to&7)+'a', 8-(to>>4), name[promo+side]);
      if(DrawCheck(stm, from, to, piece, victim)) return 1;
      return 0;
    }
    board[from] = piece; board[to] = victim; // unmake move, as it was illegal
    if((piece & 7) == 3) { // King stumbled into check
      moveList[side][n] = moveList[side][--nMoves[side]]; // delete the illegal move and try again
    } else if(checkRay[from] == seq) { // we moved a pinned piece
      pinned = from; pinSeq = seq;     // remember the pinned piece
      moveList[side][n] = moveList[side][--nMoves[side]]; // delete the illegal move and try again
    } else { // we must have been in check all along
      int i, j, n = nMoves[side];
      for(i=j=0; i<n; i++) { // examine all moves, to delete those that cannot solve this check
        move = moveList[side][i];
        if((move >> 8 & 0xFF) == king        // King move
           || checkRay[move & 0xFF] == seq)  // interposition or capture of checker
          moveList[side][j++] = move; // keep it
      }
      nMoves[side] = j; // try again with the cleaned-up move list
    }
  }
  // none of the moves is legal!
  if(MoveGen(stm ^ COLOR, -1)) { // we are in check
    GameEnd(stm == WHITE ? -1 : 1, "checkmate");
  } else GameEnd(0, "stalemate");

  return 1; // flag game end
}

int
Setup (char *fen)
{
  char c;
  int i;
  for(i=0; i<128; i++) board[i] = 0;
  i = 0;
  while((c = *fen++)) {
    if(c == 'p') board[i++] = BLACK + 2; else
    if(c >= '0' && c <= '9') i += c - '0'; else
    if(c >= 'a' && c <= 'z') board[i++] = BLACK + pieces[c - 'a'] - '0'; else
    if(c >= 'A' && c <= 'Z') board[i++] = WHITE + pieces[c - 'A'] - '0'; else
    if(c == '/') i = (i | 15) + 1; else break;
  }
//  for(i=0; i<128; i = i + 9 & ~8) printf(i&7 ? " %2d" : "\n# %2d", board[i]); printf("\n");
  c = (*fen == 'w' ? WHITE : BLACK);
  MoveGen(c, -1);
  return c;
}

int
InitGame (char *fen)
{
  int i;
  if(!fen) fen = "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1";
  for(i=0; i<1024; i++) keyHash[0][i] = keyHash[1][i] = 0;
  posKey = -1; cnt50 = 0;
  return Setup(fen);
}

char *fens[] = {
  "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1",
  "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR b KQkq - 0 1",
  NULL,
  "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1",
};

void RunMatch()
{
  int i, f, t = GetTickCount();
  silent = 1; // suppress all CECP output
  for(i=f=0; i<1000000; i++) {
    int stm;
    if(!fens[f]) f = 0;
    stm = InitGame(fens[f++]);
    MoveGen(stm, -1);
    while(!Think(stm)) { // play a game
      stm ^= COLOR;
    }
    if(i%1000 == 999) printf("%7d: %8.2f sec, %5d %5d %5d %5d %5d %6d %8d\n", i+1, (GetTickCount() - t)/1000.,
     checkmate[2], checkmate[0], stalemate, rep3, draw50, insuf, seq), fflush(stdout);
  }
  exit(0);
}

int
main ()
{
  int i, stm = WHITE, engineSide = 0;
  char line[256], command[20];
  MTinit(GetTickCount()); for(i=0; i<50; i++) MyRandom(1);
  for(i=128; i<128*8; i++) Zobrist[i] = MyRandom(-1);
  while(1) {
    int i, c;
    if(stm == engineSide) {
      if(Think(stm)) engineSide = 0;
      stm ^= COLOR;
    }
    fflush(stdout); i = 0;
    while((line[i++] = c = getchar()) != '\n') if(c == EOF) printf("# EOF\n"), exit(1); line[i] = '\0';
    if(*line == '\n') continue;
    sscanf(line, "%s", command);
    printf("# command: %s\n", command);
    if(!strcmp(command, "usermove")) {
	int from, to; char c, d, promo, ep;
	sscanf(line, "usermove %c%d%c%d%c", &c, &from, &d, &to, &promo);
	from = (8 - from)*16 + c - 'a'; to = (8 - to)*16 + d - 'a';
        int piece = board[from], victim = board[to];
	if((piece & 7) == 3 && to - from == 2) board[from + 1] = board[to + 1], board[to + 1] = 0; // K-side castling
	if((piece & 7) == 3 && from - to == 2) board[from - 1] = board[to - 2], board[to - 2] = 0; // Q-side castling
	ep = ((piece & 7) < 3 && !victim); // recognize e.p. capture
	board[to] = piece; if(ep) board[from & 0x70 | to & 7] = 0, victim = piece ^COLOR; board[from] = 0;
	if(promo >= 'a') {
          board[to] = board[to] | 7; // promote to Q
          if(promo == 'n') board[to] -= 3; // correct for under-promotion
          if(promo == 'b') board[to] -= 2;
          if(promo == 'r') board[to] -= 1;
        }
	stm ^= COLOR;
        MoveGen(stm, to);
	if(DrawCheck(stm ^ COLOR, from, to, piece, victim)) engineSide = 0;
    }
    else if(!strcmp(command, "match"))    RunMatch(); // not used as XBoard engine!
    else if(!strcmp(command, "protover")) printf("feature option=\"always queen -check 0\n"),
              printf("feature option=\"biased to capture -check 0\n"),
              printf("feature myname=\"Ram 2.0\" setboard=1 usermove=1 analyze=0 colors=0 sigint=0 sigterm=0 done=1\n");
    else if(!strcmp(command, "option"))   sscanf(line+7, "always queen=%d\n", &alwaysQueen),
              sscanf(line+7, "biased to capture=%d\n", &biased);
    else if(!strcmp(command, "new"))      stm = InitGame(NULL), randomize = 0, engineSide = BLACK;
    else if(!strcmp(command, "go"))       engineSide = stm;
    else if(!strcmp(command, "result"))   engineSide = 0;
    else if(!strcmp(command, "force"))    engineSide = 0;
    else if(!strcmp(command, "setboard")) stm = Setup(line+9);
    else if(!strcmp(command, "random"))   randomize = !randomize;
    else if(!strcmp(command, "post"))     post = 1;
    else if(!strcmp(command, "nopost"))   post = 0;
    else if(!strcmp(command, "quit"))     break;
  }
  return 0;
}

[Adam Hair]

I uploaded a fixed version (1.3) to the same link (souce & Windows .exe). It now also tests for r, b or n suffix on the input move, and performs the indicated promotion if it finds one.

Hi H.G.
The executable found on the download page is misnamed NEG1_2 though a text editor shows that it refers to itself as 1.3. Also, the web site still uses the name "N.E.G. 1.2".