N.E.G. 1.0 released

[maksimKorzh]

The move generator code reminds me microMax:
1. 0x88 board representation (but PST are separate instead of being on the right part of unused board squares)
2. Three nested loops in movegen
3. Faking captures for non-sliding pieces

Nearly all my engines have a move generator like that. Sometimes the outer loop does not scan the board, but a piece list. Sometimes the table of start indexes in the array of board steps is not only indexed by piece type but also by from-square (making it a pise-square table for moves, rather than scores, to have location-dependent moving, as in Xiangqi).

But what I can't figure out is whether it supports castling, in microMax there was a rocket science level line that was handling
double pawn push and castling (for you've explained that the nature of these two actions is same in essence). Here in NEG I can see line:

Code: Select all

if(!(to - from & 7) && type < 3 && (type == 1 ? to > 79 : to < 48)) victim--;

It seems to my code monkey's eyes to be responsible for double pawn push and castling but castling part is much simpler compared to microMax.
I assume that happens because here king capture is not allowed (hence InCheck function)

Indeed, that is the double-push code, which undoes the kludge of faking a victim for leapers if the Pawn is still on 3rd rank. This is in the move generator. Castling and e.p. capture are only implemented for input moves; they are not in the move generator, and N.E.G. would never play them byitself. In the code for handling the "usermove" command the castling is done through:

Code: Select all

        if((board[from] & 7) == 3 && to - from == 2) board[from + 1] = board[to + 1], board[to + 1] = 0; // K-side castling
        if((board[from] & 7) == 3 && from - to == 2) board[from - 1] = board[to - 2], board[to - 2] = 0; // Q-side castling

This just recognizes sideway double steps by the King, and then moves the corresponding Rook in addition to the normal move performance.

So the question is - is it full FIDE rules (apart from promotions and probably 50 rule/3 fold repetitions)?

The move generator isn't; it doesn't generate castling or e.p. capture. To generate castlings according to the rules you would have to keep track of piece virginity. Micro-Max does this through an extra bit in the piece encodings on the board, but you could also keep track of a castling rights word (containing 1 bit per type of castling), and a board-size array that for each square tabulates which castling rights are destroyed when that square is used as from- or to-square. (Actually you only have to keep track of whether it is used as to-square, but then you would have to test whether it is non-empty to test if the corresponding castling is allowed.)

Also I would like to ask for your permission:
Can I make a tutorial series on NEG's movegen? (MicroMax is too complicated because of movegen is embedded into a search, beta cutoffs on king capture and other unusual stuff like remembering best from square to order first in the next iteration of IID)

Of course you can; N.E.G. can be considered public domain. There are also some unusual things in the N.E.G. move generator, though: it also generates 'pseudo-captures', i.e. capture of friendly pieces. So the 'consumer' of the moves (the callback) has to test whether it actually gets a pseudo-legal move, or just a 'protection', depending on what it wants to do (select a move for playing, or just count attackers and protectors).

Perhaps the move generator of KingSlayer / simple (line 841-932 in the latest commit) would be more suitable for your purpose. It also uses the three nested loops, similar to micro-Max, but is decoupled from search, and just puts the generated moves in a list. It also contains a few quirks (such as marking pieces protected by 'pseudo-captures' on a separate board, and a way to abort move generation when an 'off-scale' capture (such as that of a King) is found, and remember piece mobility, but you could easily delete the corresponding code sections from it without compromising the overall structure.

I'm also now playing with MCTS algorithm and looking for some light weight movegen for this purpose (my bitboard based BBC is huge and I just don't want to use it for that purpose), so can I please use your NEG's movegen in my project?

THANKS IN ADVANCE!

P.S. You can't ever imagine how happy I am with obtaining this source code! It's a GOLD for me! Thank you HGM!

Thank you for the answer and permission!
I'm just curious did you invent these nested loops in movegen and piece encoding with 8th bit to encode color and 32th bit for virginity?
and another question - aren't you interested to try alpha zero type of engine?
Is it possible to avoid deep learning and use only a couple of hidden layers to output policies and value like in leela's net?
It would be nice to have such a minimalist net written in pure C

[hgm]

I invented this independently when I wrote my first Chess program 'Usurpator' in the early eighties (in 6800 machine code), at which time I had no knowledge whatsoever on what others had done. But it is hard to imagine it would not have been used before. It seems very elementary; each player has a number of pieces, each piece can move in a number of directions, for each direction the piece can take a number of steps. I did not invent the 0x88 idea; Usurpator used contiguous square numbering, so it was a bit cumbersome to test whether a move hit the edge. It did use a bit in the piece encoding for indicate virginity, and one to indicate color.

I am interested in trying an alpha-zero type engine, especially for games where people have no idea how they should be played (such as Paco Shako / Peace Chess). I don't have a powerful GPU though.

I am not sure that a Leela-type engine would work with only a few hidden layers. The problem is that to sensibly guide the search through the policy heads, it has to be able to recognize tactics (e.g. at the level of N.E.G.). The NN used in LC0 has a very unsuitable topology for doing that: each layer examines only adjacent squares. So to see that a Bishop on a1 attacks a Queen on h8 requires many layers already before there is any cell that has both a1 and h8 in view. Of course this could be repaired by having cells that get their inputs from ranks, files and diagonals (8x1 areas) instead of only using 3x3 areas.

Of course one can also offer a NN not just the raw board position, but augment the latter with info on concepts that are known to be useful in chess. Like number of attackers and protectors of each square, lowest attacker of each square, which pieces block slider attacks etc. Essential the type of information that N.E.G. uses to decide about its move.

So one of the experiments I would like to do is make a slighty improved N.E.G., which generates all moves, and then uses them in two passes: by counting attackers and protectors like it does now it can also identify 'essential' attackers and protectors, whose absence would alter the verdict about the square, and by how much. It can then recalculate the gain that would result from capturing at each square taking into account the effect the removal of the target would have on other squares. E.g. by sacrifycing a Rook for a Bishop that was an essential protector of a Rook attacked by a Queen, you would actually gain that Bishop. It would also have to identify X-ray attacks.

This information could then be used to guard a MCTS, as a "poor man's policy head".

[maksimKorzh]

I invented this independently when I wrote my first Chess program 'Usurpator' in the early eighties (in 6800 machine code), at which time I had no knowledge whatsoever on what others had done. But it is hard to imagine it would not have been used before. It seems very elementary; each player has a number of pieces, each piece can move in a number of directions, for each direction the piece can take a number of steps. I did not invent the 0x88 idea; Usurpator used contiguous square numbering, so it was a bit cumbersome to test whether a move hit the edge. It did use a bit in the piece encoding for indicate virginity, and one to indicate color.

I am interested in trying an alpha-zero type engine, especially for games where people have no idea how they should be played (such as Paco Shako / Peace Chess). I don't have a powerful GPU though.

I am not sure that a Leela-type engine would work with only a few hidden layers. The problem is that to sensibly guide the search through the policy heads, it has to be able to recognize tactics (e.g. at the level of N.E.G.). The NN used in LC0 has a very unsuitable topology for doing that: each layer examines only adjacent squares. So to see that a Bishop on a1 attacks a Queen on h8 requires many layers already before there is any cell that has both a1 and h8 in view. Of course this could be repaired by having cells that get their inputs from ranks, files and diagonals (8x1 areas) instead of only using 3x3 areas.

Of course one can also offer a NN not just the raw board position, but augment the latter with info on concepts that are known to be useful in chess. Like number of attackers and protectors of each square, lowest attacker of each square, which pieces block slider attacks etc. Essential the type of information that N.E.G. uses to decide about its move.

So one of the experiments I would like to do is make a slighty improved N.E.G., which generates all moves, and then uses them in two passes: by counting attackers and protectors like it does now it can also identify 'essential' attackers and protectors, whose absence would alter the verdict about the square, and by how much. It can then recalculate the gain that would result from capturing at each square taking into account the effect the removal of the target would have on other squares. E.g. by sacrifycing a Rook for a Bishop that was an essential protector of a Rook attacked by a Queen, you would actually gain that Bishop. It would also have to identify X-ray attacks.

This information could then be used to guard a MCTS, as a "poor man's policy head".

This is incredibly fantastic idea - "poor man's policy head" - I'm so excited - that's the exact direction that was in my dreams. Unfortunately I'm not smart enough to come up with that on my own) but thankfully to your idea of using static exchange evaluation factors as an additional input to the network seems to be a fantastic idea!

Just to give you an example to explain why these weird ideas are coming into my head: the reason is simple - my brain is too poor to pick up complicated concepts that are today's trends) The only thing I more less "understand" now is a single layer perceptron, or at very most a NN with input/1 hidden layer/output, by saying "understand" I mean how to multiply inputs by weights, sum and normalize via activation function (and even backpropagate results to adjust weights) I "can" do it in python using numpy and more less understand how to multiply matrices using bare for loops (great achievement for me!) to make it in C one day.

My current ultimate goal is to implement alpha-zero's NN training (actually it has been implemented ad a generalized algorithm already) but instead using tensorflow and deep learning (which I understand like "MANY hidden layers NN" which is the same to me as black box, so I want to avoid what I don't understand) I'd like to craft my own primitive NN like input/1 hidden layer/output for value and policies. Assuming primitive and minimalist design I assume it would take LESS computation power and CPU is enough (I don't ever want to deal with GPUs)

Now imagine that we simplify this idea even more - getting rid of hidden layer completely! I understand that in this case NN would be capable of only learning linearly separable data dependencies and it makes it similar to a handcrafted evaluation BUT in this case we can input material/PST values as inputs (I guess no need to input board position as far as we don't want to learn non-linear dependencies) on the one hand and static exchange evaluation (or even rudimentary quiescence search output - it won't take long for we don't do alpha beta search) on the other to output policies.

And that's it, so eventually we'll come up with something like "Texel's tuning on reinforcements learning steroids")
What do you think of this idea? Is it technically possible?

[hgm]

I will still have to contemplate all that.

Anyway, I made a new version of N.E.G., which should not play illegal moves anymore. It still cannot castle or capture e.p., but when these are the only legal moves (so that it finds no move), it now resigns:

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)


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........";
Board board, attacks[2], lva[2];
int bestScore, bestFrom, bestTo, lastMover, lastChecker, randomize, post, iron[2], minors[2], material[2];

void
MoveGen (Board board, int stm, Func proc, void *cl)
{
  int from, to, piece, victim, type, dir, step;
  for(from=0; from<128; from = from + 9 & ~8) {
    piece = board[from];
    if(piece & stm) {
      type = piece & 7;
      if(type == 4 || type == 5) minors[!(piece & WHITE)]++, iron[!(piece & WHITE)] = from; // count minors and remember location of one
      material[!(piece & WHITE)] += value[type];
      dir = firstDir[type];
      while((step = steps[dir++])) {
        to = from;
        do {
          to += step;
          if(to & 0x88) break;
          victim = board[to];
          (*proc)(piece & COLOR, from, to, cl);
          victim += type < 5;
          if(!(to - from & 7) && type < 3 && (type == 1 ? to > 79 : to < 48)) victim--;
        } while(!victim);
      }
    }
  }
}

int InCheck (int stm)
{
  int k, xstm = COLOR - stm;
  for(k=0; k<128; k++) if( board[k] == stm + 3 ) {
    int dir=4, step;
    int f = (stm == WHITE ? -16 : 16); // forward
    int p = (stm == WHITE ? 2 : 1);
    if(!(k + f + 1 & 0x88) && board[k + f + 1] == xstm + p) return k + f + 2;
    if(!(k + f - 1 & 0x88) && board[k + f - 1] == xstm + p) return k + f;
    while((step = steps[dir])) {
	int from = k + steps[dir + 14];
	if(!(from & 0x88) && board[from] == xstm + 4) return from + 1;
	from = k + step;
	if(!(from & 0x88) && board[from] == xstm + 3) return from + 1;
	from = k;
	while(!((from += step) & 0x88)) if(board[from]) { // occupied
	    if(dir < 8 && (board[from] & COLOR + 6) == xstm + 6) return from + 1; // R or Q and orthogonal
	    if(dir > 7 && (board[from] & COLOR + 5) == xstm + 5) return from + 1; // B or Q and diagonal
	    break;
	}
	dir++;
    }
    break;
  }
  return 0;
}

void
Count (int stm, int from, int to, void *cl)
{
  int s = (stm == BLACK);
  if(!(to - from & 7) && (board[from] & 7) < 3) return; // ignore Pawn non-captures
  attacks[s][to]++;
  if(lva[s][to] > value[board[from] & 7]) lva[s][to] = value[board[from] & 7];
}

void
Mark (int stm, int from, int to, void *cl)
{
  int s = (stm == BLACK);
  if(from != iron[s]) return; // only consider moves of iron piece
  attacks[s][to] += 5;        // and count its attacks as many
}

void
Score (int stm, int from, int to, void *cl)
{
  int score = PST[to] - PST[from];
  int piece = board[from];
  int victim = board[to];
  int myVal = value[piece & 7];
  int hisVal = value[victim & 7];
  int push = (piece & 7) < 3 && to - from & 7;// Pawn non-capture
  int s = (stm == BLACK);
  int check;
  if((piece & 7) < 3 && !(to - from & 7) != !victim) return; // weed out illegal pawn modes
  if((piece & 7) == 3) score -= score;        // keep King out of center
  else if(myVal > 400) score = 0;             // no centralization for R, Q
  if((piece & ~7) == (victim & ~7)) return;   // self capture
  board[from] = 0; board[to] = piece;
  if(from != lastChecker && InCheck(COLOR - stm)) score += 50; // bonus for checking with new piece
  check = InCheck(stm);                       // in check after move?
  board[to] = victim; board[from] = piece;
  if(check) return;                           // illegal
  score += ((rand()>>8 & 31) - 16)*randomize; // randomize
  if(from == lastMover) score -= 10;          // discourage moving same piece twice
  if(hisVal && hisVal < 400) score += PST[to];// centralization bonus of victim
  score += hisVal;                            // captured piece
  if(iron[!s] == to) score -= 500;            // discourage capturing last minor, to reduce stalemate probability
  if(attacks[!s][to]) {                       // to-square was attacked
    if(attacks[s][to] - 1 + push < attacks[!s][to] ) score -= myVal; else // not sufficiently protected
    if(myVal > lva[!s][to]) score += lva[!s][to] - myVal; // or protected, but more valuable
  }
  if((piece & 7) != 3 && attacks[!s][from]) { // from-square was attacked (and not King)
    if(attacks[s][from] < attacks[!s][from] ) score += myVal; else // not sufficiently protected
    if(myVal > lva[!s][from]) score -= lva[!s][from] - myVal; // or protected, but more valuable
  }
  if((piece & 7) == 1 && to < 48) score += 50;
  if((piece & 7) == 2 && to > 79) score += 50;

  if(score > bestScore) bestScore = score, bestFrom = from, bestTo = to; // remember best move
  if(post) printf("2 %d 0 1 %c%d%c%d\n", score, (from&7) + 'a', 8 - (from >> 4), (to&7) + 'a', 8 - (to >> 4));
}

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");
  return (*fen == 'w' ? WHITE : BLACK);
}

int
main ()
{
  int stm = WHITE, engineSide = 0;
  char line[256], command[20];
  srand(GetTickCount());
  while(1) {
    int i, c;
    if(stm == engineSide) {
	char *promo = "";
	for(i=0; i<128; i++) lva[0][i] = lva[1][i] = 30000, attacks[0][i] = attacks[1][i] = 0;
	minors[0] = minors[1] = material[0] = material[1] = 0;
	MoveGen(board, COLOR, &Count, NULL);
	bestScore = -30000;
	if(material[stm == BLACK] - material[stm == WHITE] < 1000 || minors[stm == WHITE] != 1) iron[stm == WHITE] = -1;
	else MoveGen(board, COLOR-stm, &Mark, NULL);
	MoveGen(board, stm, &Score, NULL);
        if(bestScore == -30000) printf("resign\n"), engineSide = 0; else {
	    board[bestTo] = board[bestFrom]; board[bestFrom] = 0; stm ^= COLOR;
	    if((board[bestTo] & 7) < 3 && (stm == BLACK ? bestTo < 16 : bestTo > 111)) board[bestTo] |= 7, promo = "q"; // always promote to Q
	    lastMover = bestTo;
	    lastChecker = InCheck(stm) ? bestTo : -1 ;
	    printf("move %c%d%c%d%s\n", (bestFrom&7) + 'a', 8 - (bestFrom >> 4), (bestTo&7) + 'a', 8 - (bestTo >> 4), promo);
        }
    }
    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';
	if((board[from] & 7) == 3 && to - from == 2) board[from + 1] = board[to + 1], board[to + 1] = 0; // K-side castling
	if((board[from] & 7) == 3 && from - to == 2) board[from - 1] = board[to - 2], board[to - 2] = 0; // Q-side castling
	ep = ((board[from] & 7) < 3 && !board[to]); // recognize e.p. capture
	board[to] = board[from]; if(ep) board[from & 0x70 | to & 7] = 0; board[from] = 0;
	if(promo == 'q') board[to] =  board[to] | 7;      // promote to Q
	if(promo == 'r') board[to] = (board[to] | 7) - 1; // under-promote
	if(promo == 'b') board[to] = (board[to] | 7) - 2; // under-promote
	if(promo == 'n') board[to] = (board[to] | 7) - 3; // under-promote
	stm ^= COLOR;	
    }
    else if(!strcmp(command, "protover")) printf("feature myname=\"N.E.G. 1.3b\" setboard=1 usermove=1 analyze=0 colors=0 sigint=0 sigterm=0 done=1\n");
    else if(!strcmp(command, "new"))      stm = Setup("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"), 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;
}

It relies on the GUI to declare real checkmates and stalemates.

[unserializable]

Anyway, I made a new version of N.E.G., which should not play illegal moves anymore. It still cannot castle or capture e.p., but when these are the only legal moves (so that it finds no move), it now resigns:

Thanks, great stuff, it now should be flawless engine , brief testing gameplay testing from couple positions with e.p. being only legal move resulted in resignment indeed. Situation where castling is only legal move would never happen (rook moves and king moves would also be available). Hope you update N.E.G. at https://home.hccnet.nl/h.g.muller/dwnldpage.html too, that is most certainly the place where most of the people make acquintance with formidably fast N.E.G.

[Roland Chastain]

@H.G.Muller

Thank you for the new version of NEG. (May we call it NEG 1.4?)

I take the occasion to share a logo that I made for NEG. (I don't remember to have seen a logo for this engine.)

logo.zip

[Guenther]

@H.G.Muller

Thank you for the new version of NEG. (May we call it NEG 1.4?)

I take the occasion to share a logo that I made for NEG. (I don't remember to have seen a logo for this engine.)

logo.zip

It's already different to 1.3, this is sufficient for me. I will make a windows compile.

Code: Select all

else if(!strcmp(command, "protover")) printf("feature myname=\"N.E.G. 1.3b\"

Edit:
Does this look correct?

Code: Select all

xboard
# command: xboard
protover 2
# command: protover
feature myname="N.E.G. 1.3b" setboard=1 usermove=1 analyze=0 colors=0 sigint=0 sigterm=0 done=1
new
# command: new

# 22 20 21 23 19 21 20 22
# 18 18 18 18 18 18 18 18
#  0  0  0  0  0  0  0  0
#  0  0  0  0  0  0  0  0
#  0  0  0  0  0  0  0  0
#  0  0  0  0  0  0  0  0
#  9  9  9  9  9  9  9  9
# 14 12 13 15 11 13 12 14
post
# command: post
go
# command: go
2 4 0 1 a2a3
2 6 0 1 a2a4
2 4 0 1 b2b3
2 6 0 1 b2b4
2 6 0 1 c2c3
2 8 0 1 c2c4
2 6 0 1 d2d3
2 8 0 1 d2d4
2 6 0 1 e2e3
2 8 0 1 e2e4
2 6 0 1 f2f3
2 8 0 1 f2f4
2 4 0 1 g2g3
2 6 0 1 g2g4
2 4 0 1 h2h3
2 6 0 1 h2h4
2 14 0 1 b1c3
2 4 0 1 b1a3
2 4 0 1 g1h3
2 14 0 1 g1f3
move b1c3
go
# command: go
2 4 0 1 b8a6
2 14 0 1 b8c6
2 14 0 1 g8f6
2 4 0 1 g8h6
2 4 0 1 a7a6
2 6 0 1 a7a5
2 4 0 1 b7b6
2 -94 0 1 b7b5
2 6 0 1 c7c6
2 8 0 1 c7c5
2 6 0 1 d7d6
2 -92 0 1 d7d5
2 6 0 1 e7e6
2 8 0 1 e7e5
2 6 0 1 f7f6
2 8 0 1 f7f5
2 4 0 1 g7g6
2 6 0 1 g7g5
2 4 0 1 h7h6
2 6 0 1 h7h5
move b8c6

[hgm]

That looks correct. Because N.E.G. doesn't search ahead there is no iterative deepening, and it uses Thinking Output in a sort of multi-PV way for printing the entire list of root moves and the score it assigned to those.

I called it 1.3b because it basically plays exactly the same as 1.3, except that it resigns where it would otherwise forfeit. That is purely a cosmetic thing.