Minimalism in chess programming

[maksimKorzh]

Thank you, mr. Muller! This is the most inspiring thing I've ever heard - now I have absolutely no doubts whether to try to turn my engine into something close to micro-Max or not. I would definitely start rewriting the code from scratch just right now. Only a couple more technical questions. The first question - is the movelist necessary(how the move ordering is done if no movelist??). The second one - it seems there's no IsSquareAttacked() function in micro-Max, but checking whether the king is captured or not instead - that's pretty clear, but what about if say king is on e1 and f1 is attacked by black queen - after castling king is not going to be captured but such castling won't be legal, how to deal with this issue? And the last question - how to debug the program while writing it? Did you use some sort of debugging framework or perft test function just turned into minmax search after everything is bug free? The second approach seems to be more in minimalist spirit. Please explain a bit how would you personally debug a chess engine?

[hgm]

Move ordering is very important for the efficiency of an alpha-beta search. Conventional ordering is: (1) Hash move, (2) Null move, (3) captures (in MVV-LVA order), (4) killers (5) non-captures (possibly ordered through the history heuristic). If you don't keep a move list, (i.e. search moves as soon as you generate them) some of that order might be hard to achieve. E.g. to do all captures before all non-captures, you would have to run the move generator twice, first time ignoring all non-captures, second time ignoring the captures. And then each of these groups would still be searched in random order. Specialized move generators could ameliorate that (but usually require much more code), e.g. generating captures in MVV order. Putting the hash move (or killers) in front doesn't really require move generation, as the moves are already given. (For killers you would have to check if they are legal, however. Generating all moves and then running through the list to see if they are in it is a very inefficient way to do that, but has the advantage that you can then remove the duplicat. But the faster alternatives require dedicated code for the legality checking.) Having to generate the moves multiple times might seem inefficient, but with the nested loops it is actually not much more work than retrieving them from a list: you add the step to the previous to-square, and keep the from-square you already had. So the disadvantage is not so much speed, as well that you cannot optimize the ordering.

In micro-Max the only ordering is putting the hash move in front (which should always be legal, except in the very rare cases of a key collision), without making an attempt to suppress the duplicat. The duplicat should give a hash hit in the daughter, providing the result without search. Normally the hash move comes from the previous (root) iteration, with a depth one less than what we need now. If not, micro-Max starts iterating itself from the depth of the move that it did find in the hash table. If no hash move was available, it starts from d=0 (QS), but always preceeds that by an iteration without search, where the score is just the victim value minus the piece code, which picks out the capture that is (MVV-LVA-wise) best (as beta cutoff is suppressed in that iteration). The best move of an iteration then serves as 'hash move' for the next. The effect is that micro-Max first searches the MVV-LVA-wise best capture, followed by all other captures in 'random' order (when it generates all moves a second time), and then (if not in QS) all moves in random order (where the captures now should all give hash hits, as they were search already in the QS iteration). It doesn't use killers (which would require a lot of extra code). This is far from optimal, but it is bearable. The way the hash move is put in front leads to other moves with that same piece being generated first, which can be helpful in positions where you have to evade a threat, and cannot do it through a capture: if one way to withdraw the piece at some higher depth turns out no good, it tries other ways to withdraw it before any other non-capture.

Micro-Max treats castling as a double push: it sets the e.p. square (passed to the daughter node) on castling. The daughter node can see the difference between a real e.p. capture and a castling by testing if the 'e.p. square' is occupied (by the Rook) or not. If it is, it then checks if any 'raw' moves hit the e.p. square 'E' or the square left or right of it (i.e. whether the to-square 'y' of the considered move is in the range E-1 <= y <= E+1. If it is, the King must have castled either through check, into check, or out of check, which is all illegal. 'Raw' here means that I don't test whether the move fits the occupancy of the destination square for Pawns, so it imagines for this test that Pawns also capture straight ahead. Which is no problem: if the forward push would reach one of these 3 squares, it means a capture by that Pawn would always have made the castling illegal too.

As to debugging: I always do that through selective print statements embedded in the code. I use a global array path[MAXPLY] indexed by the ply level, and put path[ply++] = move before every call to Search() (and ply-- after it). The code can then be splattered with if(PATH) printf(...); for debug info, where I #define PATH as

ply==0 || path[0]==MOVE1 && (ply==1 || path[1]==MOVE2 && (ply==2 ....))

I always have such a conditional print after the return of Search(), which prints the ply level, the depth argument of Search(), the depth iteration it was working on, the move (encoding and in text form), the score just returned, and the best score so far. This is then printed in every node along the #defined PATH. Sometimes I also print the position at the top of Search(). (That is faster than reconstructing it from the moves, and allows you to spot board corruption.) When the engine blunders you can see from the scores in the last node along the PATH (initially only the root) whcih move is wrongly scored, and then you add that to the PATH, until you getto the point where the wrong score is generated (through eval, or by failing to generate a certain move, or by playing an illegal move, or by first corrupting the board). That usually allows me to find the problem pretty quickly. If the problem is crashing of the engine, I also put (i.e. uncomment) a debug print just before calling Search() (and make sure this is flushed), so that I can see during the search of which move the crashing took place, and step towards the crash point by adding that move to the PATH.

[maksimKorzh]

Mr. Muller, sorry for distracting, but could you please explain one little thing...

I'm rewriting my engine from scratch, this time basing on micro-Max design philosophy. I'm trying to print generated moves, only source and target squares for now, but if there's an enPassant move it's not shown due to the toSq (var y in micro-Max) never has a value of enPassant square, gained recursively as one of search(..., int side, int enPassant, ...) arguments. A square containing "en captured" pawn, int enCap (var H in micro-Max) is updated correctly, so the enPassant move is recognized. Is it possible to print all the moves, including castling and en passant in one place?

Code: Select all

	do
	{
		piece = board[sq];
		
		if(piece & side)
		{
			type = piece & 7;
			dir = vectors[type + 30];
			
			// Loop over directions
			while(ray = vectors[++dir])									
			{
				toSq = sq;
				tempFrom = noSq;
				
				// Loop over squares
				do
				{
					enCap = toSq;
					toSq += ray;
					
					if(toSq & 0x88)
						break;
					
					if(type < N & toSq == enPassant)
						enCap = toSq ^ 16;
							
					cap = board[toSq];
					
					if(cap & side)
						break;
						
					if((type < N) && !(ray & 7) != !cap)
						break;
						
					// print move
					PrintSquare(sq);
					PrintSquare(toSq);
					printf("\n");
					
					cap += type < B;
					
					if(type < N & 6 * side + (toSq & a1) == noSq)
					{
						tempFrom = toSq;
						cap--;
					} 
				}
				
				while(!cap);
			}
		}
	}
	
	while(sq = (sq + 9) & ~0x88);
}

Thanks in advance?

P.S. is it convenient to ask such questions here? is convenient to ask them in general? Is it convenient to ask them via personal messages? I'm really sorry to be annoying, but after rereading your micro-Max site for hundreds of times I'm still feeling a bit unclear about some points.

[hgm]

Note that micro-Max says enCap = toSqr += ray, which is not equivalent to

enCap = toSqr;
toSqr += ray;

but to

toSqr += ray;
enCap = toSqr;

En passant capture is only possible if the preceding move was a double-push. You have to tell that to the move generator by passing it the number of the e.p. square. If you do that it should print the e.p. move. If not, it assumes this is not a valid move, so it doesn't print it.

The place where you put the print statements would in principle print every move. The code you wrote does not generate castling moves, though. So they are not printed. Micro-Max generates castlings (and Pawn double-pushes) through the lines

Code: Select all

      if(p<3&6*k+(y&V)==S                      /* pawn on 3rd/6th, or      */
          ||(u&~24)==36&j==7&&                 /* virgin K moving sideways,*/
          G&M&&b[G=(x|7)-(r>>1&7)]&32          /* 1st, virgin R in corner G*/
          &&!(b[G^1]|b[G^2])                   /* 2 empty sqrs. next to R  */
      ){F=y;t--;}                              /* unfake capt., enable e.p.*/

just before the end of the range loop. To force termination of this loop after one iteration for leapers, micro-Max faked the move was a capture by incrementing t (= 'capt' in your terminology). If it was the first sideway step of a virgin King (and a host of other conditions are fulfilled) it eventually does t--; here to undo that, so that the range loop will not terminate if the move was not a real capture. Then the King (or Pawn) would make a second step. In addition 'e.p. rights' are created by setting F to the toSqr (which at this point is where the first step ended.

The other conditions are:

Code: Select all

(coloredPiece & ~24) == 36          This tests whether the piece is a virgin King; & ~24 obliterates the color, 36 = 4 (King code) + 32 (virgin)
j == 7                              Tests for sideway move (Note moves to left and right use same index j in step table)
G&M                              This is rookFromSqr & 0x88, and tests if rookToSqr is still invalid (i.e. whether this is not the 3rd step)
rookFromSqr = (fromSqr | 7) - (ray >> 1 & 7)      Calculates where the Rook is; note that ray>>1 is 0 or -1, after &7 this becomes 0 or 7
board[rookFromSqr]&32                 Tests if the corner piece is virgin (in which case it must be a Rook)
board[rookFromSqr^1]                  piece next to the Rook
board[rookFromSqr^2]                  piece two steps away from the Rook

It is fine to ask questions in public; I actually prefer that. You never know who else the answer might be useful to, now or later.

[maksimKorzh]

Note that micro-Max says enCap = toSqr += ray, which is not equivalent to

enCap = toSqr;
toSqr += ray;

but to

toSqr += ray;
enCap = toSqr;

En passant capture is only possible if the preceding move was a double-push. You have to tell that to the move generator by passing it the number of the e.p. square. If you do that it should print the e.p. move. If not, it assumes this is not a valid move, so it doesn't print it.

The place where you put the print statements would in principle print every move. The code you wrote does not generate castling moves, though. So they are not printed. Micro-Max generates castlings (and Pawn double-pushes) through the lines

Code: Select all

      if(p<3&6*k+(y&V)==S                      /* pawn on 3rd/6th, or      */
          ||(u&~24)==36&j==7&&                 /* virgin K moving sideways,*/
          G&M&&b[G=(x|7)-(r>>1&7)]&32          /* 1st, virgin R in corner G*/
          &&!(b[G^1]|b[G^2])                   /* 2 empty sqrs. next to R  */
      ){F=y;t--;}                              /* unfake capt., enable e.p.*/

just before the end of the range loop. To force termination of this loop after one iteration for leapers, micro-Max faked the move was a capture by incrementing t (= 'capt' in your terminology). If it was the first sideway step of a virgin King (and a host of other conditions are fulfilled) it eventually does t--; here to undo that, so that the range loop will not terminate if the move was not a real capture. Then the King (or Pawn) would make a second step. In addition 'e.p. rights' are created by setting F to the toSqr (which at this point is where the first step ended.

The other conditions are:

Code: Select all

(coloredPiece & ~24) == 36          This tests whether the piece is a virgin King; & ~24 obliterates the color, 36 = 4 (King code) + 32 (virgin)
j == 7                              Tests for sideway move (Note moves to left and right use same index j in step table)
G&M                              This is rookFromSqr & 0x88, and tests if rookToSqr is still invalid (i.e. whether this is not the 3rd step)
rookFromSqr = (fromSqr | 7) - (ray >> 1 & 7)      Calculates where the Rook is; note that ray>>1 is 0 or -1, after &7 this becomes 0 or 7
board[rookFromSqr]&32                 Tests if the corner piece is virgin (in which case it must be a Rook)
board[rookFromSqr^1]                  piece next to the Rook
board[rookFromSqr^2]                  piece two steps away from the Rook

It is fine to ask questions in public; I actually prefer that. You never know who else the answer might be useful to, now or later.

I've fixed my code and now enPassant captures are printed. It's also almost clear with castling code, i say "almost" because on the one hand I understand why it doesn't print castling moves correctly, but unfortunately have no idea how to fix it. After for about 3 hours of researching micro-Max code I've noticed one tiny little detail causing the disaster - in move generation tutorial appears this code:

Code: Select all

static int o[] = {
	-16,-15,17,0,			/* downstream pawn 	  */
	16,15,17,0,			/* upstream pawn 	  */
	1,-1,16,-16,0,			/* rook 		  */
	1,-1,16,-16,15,-15,17,-17,0,	/* king, queen and bishop */
	14,-14,18,-18,31,-31,33,-33,0,	/* knight 		  */
	-1,3,21,12,16,7,12		/* directory 		  */
      };  

please notice the directions are given as + and -

but in source code:

Code: Select all

o[]={-16,-15,-17,0,1,16,0,1,16,15,17,0,14,18,31,33,0, /* step-vector lists */
     7,-1,11,6,8,3,6, ....

the directory line changes from -1,3,21,12,16,7,12 to 7,-1,11,6,8,3,6, I assume this is the whole point,
I mean the condition (piece & ~24) == 36 & dir == 7 (dir is your var j) is never to happen. I might me wrong but feel that here is the problem. I don't want to obfuscate the code via using only one sided directions, but in this case the expression
(piece & ~24) == 36 & dir == 7 probably has to be rewritten... somehow, please help.
I tried blindly doing like so (piece & ~24) == 36 & dir == 14 - this caused castling only one side

Also another questions are arising:
1. I've written ParseFen(*fen) function to setup position via parsing FEN string. Setting up pieces and en passant square to pass it as argument to search() are just fine, but how can I pass castling rights??? May be via playing with virgin bits on rooks and queens?

2. Another issue is I doubt whether UCI protocol I got used to is applicable with such a all-in-one inlined design? May be switching to xboard/winboard is reasonable and solves that problem?

[maksimKorzh]

And I also wonder about pawn directions, is it a mistype?

Code: Select all

-16, -15,  17,   0,								// downstream pawns
16,  15,  17,   0,								// upstream pawns

It looks like it has to be

Code: Select all

-16, -15, -17,   0,								// downstream pawns
16,  15,  17,   0,								// upstream pawns

due to the downstream black pawn can't capture backwards. Please excuse me if I'm wrong.

[maksimKorzh]

I seems I've found the solution...

Code: Select all

if(type < N & 6 * side + (toSq & a1) == noSq ||
		    (((piece & ~24) == 36 & dir == 13) || ((piece & ~24) == 36 & dir == 14))/*7*/ &&
		    rookFromSq & 0x88 && board[rookFromSq = (sq | 7) - (ray >> 1 & 7)] & v &&
	           !(board[rookFromSq ^ 1] | board[rookFromSq ^ 2]))

where dir == 13 is +1 and dir == 14 is -1

is this correct? It seems to work fine...

[maksimKorzh]

Ahh!!!!! I've just noticed the version of micro-Max with meaningful names is available as well as variables description page! Ohh!!!!! What a dumb am I trying to deobfuscate it my own!

[hgm]

You are right: the ommission of the minus sign in the tutorial on -17 is a typo.

The change of the directory line is probably due to a mixup of versions. Initially the list of steps was including the steps in all directions. At some point I realized I could save a lot of characters by making the code automatically try bot the tabulated step, and the opposite direction as well: then I only had to tabulate the positive directions. (Which saved a lot of minus signs. Pawns obviously had to be exempted from that rule.) Of course the denser packing of the steps list now required another directory table to get to the first move of every type. (Note that this line actually points to one place before the first step, as the code to loop over the direction pre-increments the direction.)

With

Code: Select all

o[]={-16,-15,-17,0,1,16,0,1,16,15,17,0,14,18,31,33,0, /* step-vector lists */

We first have white Pawn (white moves in negative direction, to make it appear at the bottom when printing the board in the stand-alone version), then 1,16 for the Rook, 1,16,15,17 for King, Queen and black Pawn (which only uses the last 3), and finally 14,18,31,33 for the Knight. The 7th element of this is the 1 in the K/Q list, and 1 corresponds to a sideway step towards the h-file. The code tries this as both +1 and -1, and during both these tries j==7.

If opposite directions would have been listed separately (as they must be in Fairy-Max, as in chess variants pieces do not always move symmetrically), you would need to test for both those values. There is no need to test again if it is a King, you could just write

Code: Select all

	    ((piece & ~24) == 36 & (dir == 13 | dir == 14)) &&

(Note micro-Max sometimes uses | or & where you would normally use || or &&, just to save a character.) If you are lucky dual tests like that can sometimes be combined by first masking away a bit (or shifting it out). E.g. if you would have to test for 14 or 15 you could do dir >> 1 == 7 or (dir & ~1) == 14. So it is also a matter of finding a convenient ordering in the steps table. You could also test on the step vector itself: ray*ray == 1.

For castling rights you would indeed have to mark King and Rook as virgin, by setting the '32' bit in their encoding on the board. The simplest way would be to always set that bit on the King, when you place it, and at the end set it on the pieces in the corner when the castling-rights fields specify the corresponding right. (This assumes a valid FEN, which doesn't specify fake castling rights on Rooks that are not there.)

I don't think the protocol matters much. Not that I made no attempt in micro-Max to minimize the size of the protocol driver; the WB version is not the one where I count the characters, but just a way to enable testing of the strength of the AI against other engines. WB protocol supports everything that you need to do UCI. You can set up the start position, and you can enter a move to be played. It is just that UCI does this for every move the engine has to think about. But you could also do that in WB protocols, and there indeed have been interfaces that do this.

[maksimKorzh]

You are right: the ommission of the minus sign in the tutorial on -17 is a typo.

The change of the directory line is probably due to a mixup of versions. Initially the list of steps was including the steps in all directions. At some point I realized I could save a lot of characters by making the code automatically try bot the tabulated step, and the opposite direction as well: then I only had to tabulate the positive directions. (Which saved a lot of minus signs. Pawns obviously had to be exempted from that rule.) Of course the denser packing of the steps list now required another directory table to get to the first move of every type. (Note that this line actually points to one place before the first step, as the code to loop over the direction pre-increments the direction.)

With

Code: Select all

o[]={-16,-15,-17,0,1,16,0,1,16,15,17,0,14,18,31,33,0, /* step-vector lists */

We first have white Pawn (white moves in negative direction, to make it appear at the bottom when printing the board in the stand-alone version), then 1,16 for the Rook, 1,16,15,17 for King, Queen and black Pawn (which only uses the last 3), and finally 14,18,31,33 for the Knight. The 7th element of this is the 1 in the K/Q list, and 1 corresponds to a sideway step towards the h-file. The code tries this as both +1 and -1, and during both these tries j==7.

If opposite directions would have been listed separately (as they must be in Fairy-Max, as in chess variants pieces do not always move symmetrically), you would need to test for both those values. There is no need to test again if it is a King, you could just write

Code: Select all

	    ((piece & ~24) == 36 & (dir == 13 | dir == 14)) &&

(Note micro-Max sometimes uses | or & where you would normally use || or &&, just to save a character.) If you are lucky dual tests like that can sometimes be combined by first masking away a bit (or shifting it out). E.g. if you would have to test for 14 or 15 you could do dir >> 1 == 7 or (dir & ~1) == 14. So it is also a matter of finding a convenient ordering in the steps table. You could also test on the step vector itself: ray*ray == 1.

For castling rights you would indeed have to mark King and Rook as virgin, by setting the '32' bit in their encoding on the board. The simplest way would be to always set that bit on the King, when you place it, and at the end set it on the pieces in the corner when the castling-rights fields specify the corresponding right. (This assumes a valid FEN, which doesn't specify fake castling rights on Rooks that are not there.)

I don't think the protocol matters much. Not that I made no attempt in micro-Max to minimize the size of the protocol driver; the WB version is not the one where I count the characters, but just a way to enable testing of the strength of the AI against other engines. WB protocol supports everything that you need to do UCI. You can set up the start position, and you can enter a move to be played. It is just that UCI does this for every move the engine has to think about. But you could also do that in WB protocols, and there indeed have been interfaces that do this.

Thanks a lot for such a detailed answer! I'm pretty close to the perft testing at this moment, the only question left for now is under promotions... I used to test my move generators in this well known position
[d]r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1
So the under promotions are absolutely needed to pass the test to depth 3 and further.

I'm thinking how to implement them... here are my thoughts:

Code: Select all

					if(type < N)
					{
						if(toSq + ray + 1 & noSq)
						{
							for(int prom = Q; prom >= N; prom--)
							{
								if(prom == K) prom--;
								//printf("%c\n", promoted[i]);
								promPiece = board[toSq] |= prom;
								capVal += QVAL;
							}
						}
					}
					
					
					// print move
					PrintMove(fromSq, toSq, (board[toSq] == promPiece) ? promPiece & ~24 & Q : emSq);
					moveCount++;
					
					cap += type < B;
					
					// pawn double push and castling
					if(type < N & 6 * side + (toSq & a1) == noSq ||
					    ((piece & ~24) == 36 & (dir == 13 || dir == 14))/*7*/ &&
					    rookSq & 0x88 && board[rookSq = (fromSq | 7) - (ray >> 1 & 7)] & v &&
					    !(board[rookSq ^ 1] | board[rookSq ^ 2]))
					{
						skipSq = toSq;
						cap--;
					} 

1. I've added pieceProm variable to store the promoted piece
2. Loop over piece codes available for promotions, except king
3. "board[toSq] | prom" instead of "board[toSq] | Q"


Questions:

1. pieceProm is overwritten, should it be an array to store all the values
and later add extra moves where PrintMove(...) appears? I want to do it in micro-Max spirit though...
2. I wonder how to correctly update score for under promotions, pleace explain how to manipulate QVAL (your const C)
in more details.


Some other question, which is probably a bit early to ask, but nevertheless:

at the moment my engine looks like the ugly clone of micro-Max with different variable names
and non micro-Max spirit ParseFen() function, see it yourself if interested
https://github.com/maksimKorzh/Minilite ... Minilite.c
so I wonder what if guys from CCRL(or whatever) would claim my engine a clone and won't involve it to any tourney?
(I fell in love with micro-Max's design philosophy and ideas and don't want
to switch back to my previous tscp/vice like design, I definitely want the same piece encoding and all-in-one search(),
also I'm not going to claim I've written this myself - I would achieve completely nothing without your help. There are
two reasons why am I doing this: first - I want to embed this "wrapped" all-in-one philosophy into my daily life, second -
I want to make a youtube tutorial related to this design in future if I'd be ever able to complete this engine - I want to
make an alternative to bluefever's vice tutorial for if I had one back there when I started to learn chess programming
I would definitely choose the micro-Max like tutorial to follow instead of tscp/vice like )