Minimalism in chess programming

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
hgm
Posts: 22660
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Minimalism in chess programming

Post by hgm » Sun Sep 23, 2018 2:01 pm

To implement promotion choice you would need an additional level of nesting in the move generation, where the inner loop runs over all pieces. Micro-Max executes promotion 'on the board', as a sort of after-thought to the normal MakeMove code. It then adjusts the Pawn standing on the promotion square to a Queen.

You could add a do-while around the recursive call which decrements the piece on the promotion square for each iteration if the piece-type bits are unequal to the original type, and still larger than Knight. Like do { ... } while(p-b[y]--&7 && b[y]&4);

You would have to recalculate the new evaluation (v) as well though, and the new hash key. (Or at least spoil the old one, so that it won't get a hash it after under-promotion on the position where you promoted to Queen.)

maksimKorzh
Posts: 64
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Minimalism in chess programming

Post by maksimKorzh » Sun Sep 23, 2018 8:38 pm

hgm wrote:
Sun Sep 23, 2018 2:01 pm
To implement promotion choice you would need an additional level of nesting in the move generation, where the inner loop runs over all pieces. Micro-Max executes promotion 'on the board', as a sort of after-thought to the normal MakeMove code. It then adjusts the Pawn standing on the promotion square to a Queen.

You could add a do-while around the recursive call which decrements the piece on the promotion square for each iteration if the piece-type bits are unequal to the original type, and still larger than Knight. Like do { ... } while(p-b[y]--&7 && b[y]&4);

You would have to recalculate the new evaluation (v) as well though, and the new hash key. (Or at least spoil the old one, so that it won't get a hash it after under-promotion on the position where you promoted to Queen.)
It seems like everything is working fine, could you please say did I understand you correctly?

Code: Select all

					const char promoted[] = { [N] = 'n', [B] = 'b', [R] = 'r', [Q] = 'q', [K] = 'k' };
...
					// make move
					board[rookSq] = board[capSq] = board[fromSq] = 0;
					board[toSq] = piece & 31;

					if(type < N)
					{
						if(toSq + ray + 1 & noSq)
						{
							board[toSq] |= Q;
							capVal += QVAL;
						}
					}
					
					// Loop over promoted pieces
					do
					{	
						//decrements piece if promoted to king
						if(promoted[board[toSq] & ~24] == 'k') type - board[toSq]-- & Q;
						
						// print move
						PrintMove(fromSq, toSq, (toSq + ray + 1 & noSq) ? board[toSq] & ~24 : emSq);
						moveCount++;
					}
					
					while(type - board[toSq]-- & Q && board[toSq] & K);
					
					// take back
					// b[G]=k+38;b[F]=b[y]=0;b[x]=u;b[H]=t;
					board[rookSq] = side + 38;
					board[skipSq] = board[toSq] = 0;
					board[fromSq] = piece;
					board[capSq] = cap;
in position


the output is as follows:

g7g8q
g7g8r
g7g8b
g7g8n
g7h8q
g7h8r
g7h8b
g7h8n
g7f8q
g7f8r
g7f8b
g7f8n
f5f6
f5e6
b4b5
b4c5
d4d5
d4e5
d4c5
h3h4
...

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

Re: Minimalism in chess programming

Post by hgm » Sun Sep 23, 2018 8:59 pm

Well, if the piece encoding is the same as in micro-Max (order wP, bP, K, N, B, R, Q) there should be no need to worry about King inside the loop. You start at Q, and the condition in the while clause would decrement it as a side effect, to, R, B, N, and then terminate the loop when it reaches K. (Which has piece code 3, but on the board will also have the white or black color bit set, so that you cannot test by b[y]>3, but would need a a color-dependent test. So continuing when b[y]&4 (!= 0) is simpler, as N, B, R and Q all have the '4' bit set, but K has not. So you won't continue the loop if b[y] has reached King.

Of course you will have to adjust the value of capVal as well. What you added to it on promotion is actually not the value of a Queen, but the value of a Queen minus that of a (7th-rank) Pawn. For the under-promotions it would have to be lower.

maksimKorzh
Posts: 64
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Minimalism in chess programming

Post by maksimKorzh » Sun Sep 23, 2018 9:18 pm

Mr. Muller, I feel so excited finishing the move generator and greatly appreciate your help, many many thanks! Now it's time for me to take a hard decision of how to proceed. I really need your guidance now, could you please describe the pros and cons of keeping all-in-one search() compare to separate move generator from search. I'm tempted to choose the second approach just because that's pretty well-known territory, I mean I've done that before, but keeping the inlined style is for sure the way to learn something completely new. I really really doubt of how to proceed, what would you kindly suggest me?

maksimKorzh
Posts: 64
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Minimalism in chess programming

Post by maksimKorzh » Mon Sep 24, 2018 7:41 am

hgm wrote:
Sun Sep 23, 2018 8:59 pm
Well, if the piece encoding is the same as in micro-Max (order wP, bP, K, N, B, R, Q) there should be no need to worry about King inside the loop. You start at Q, and the condition in the while clause would decrement it as a side effect, to, R, B, N, and then terminate the loop when it reaches K. (Which has piece code 3, but on the board will also have the white or black color bit set, so that you cannot test by b[y]>3, but would need a a color-dependent test. So continuing when b[y]&4 (!= 0) is simpler, as N, B, R and Q all have the '4' bit set, but K has not. So you won't continue the loop if b[y] has reached King.

Of course you will have to adjust the value of capVal as well. What you added to it on promotion is actually not the value of a Queen, but the value of a Queen minus that of a (7th-rank) Pawn. For the under-promotions it would have to be lower.
I've adjusted piece order and now it seems to work fine, but I feel a bit confused about the perft testing

Perft results d1 20 d2 400 d3 8902 in initial position which is correct but fails on d4
also in this position

d1 48 - ok
d2 2049 - fails, must be 2039, but I'm not sure whether the bug is in my movegen or this happens due to the wrong
place for nodes++

here how I count nodes:

at the very beginning of search()

Code: Select all

	if(!depth)
	{
		nodes++;
		return 0;
	}
I increment nodes when reached depth 0, so we know this is the last node in a tree...
But I assume the problem might be because movegen somehow counts illegal moves after king has been captured
or something like that.

Questions:
Am I counting nodes correctly?
Is there a way to determine whether the trouble is in the node count or in movegen itself?

Thanks in advance!

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

Re: Minimalism in chess programming

Post by hgm » Mon Sep 24, 2018 8:26 am

maksimKorzh wrote:
Sun Sep 23, 2018 9:18 pm
Mr. Muller, I feel so excited finishing the move generator and greatly appreciate your help, many many thanks! Now it's time for me to take a hard decision of how to proceed. I really need your guidance now, could you please describe the pros and cons of keeping all-in-one search() compare to separate move generator from search. I'm tempted to choose the second approach just because that's pretty well-known territory, I mean I've done that before, but keeping the inlined style is for sure the way to learn something completely new. I really really doubt of how to proceed, what would you kindly suggest me?
It depends on what your goals are. 'All-in-one' search is not an all-or-nothing characteristic; there are several aspects to this. One is the omission of maintaining a move list to separate move generation from their search. That eliminates a lot of overhead, space as well as timewise. But it is likely to lead to a sub-optimal move ordering, and move ordering is the dominant factor in determining how deep your engine can search. So if the goal is to make a really strong engine, you should never compromise the move ordering. Poor move ordering is probably the major factor that limits micro-Max' strength.

Even advanced engines can use designs that have less separation of move generation and Search. With so-called 'staged' move generation there is no routine to generate all moves at once, but moves are instead generated in small batches, such as all captures, or even all captures on a set of pieces of equal value, killer moves, all non-captures. These are then produced 'on demand', whenever the Search() routine needs them. The advantage is that when a beta cutoff occurs, you will not have wasted too much time on generating moves you are never going to search. In a good engine more than 95% of all beta cutoffs are caused by the first two moves that are searched. The staged move generation in a sense has moved the 'master control loop' of the move generator back to the Search() routine again.

Another issue is how much redundancy you are willing to put in the board representation to speed things up. Micro-Max only uses a board array. This makes it easy to find the piece for a given square, but hard to find the square for a given piece. So to find its own pieces for move generation it has to scan the board, which is pretty inefficient. To figure out whether it is in check it must do a full move generation for the opponent, which is efficient code-wise (as it can use the Search() routine itself for it), but horrible speedwise. Tricks to do this faster only work if you kow where your King is, and having to scan the entire board just to find a single piece is prohibitively expensive.

So a less minimalistic design would, in addition to the board, keep a 'piece list', which keeps track of the location of each piece. This is in principle redundant information (and thus opens the possibility for bugs that cause the representation to become inconsistent, the piece list describing another position than the board). But it makes the piece -> square question a simple lookup. So you never have to search for pieces anymore. The board would have to encode pieces by a unique number to upate the piece-list, otherwise, when you move a Pawn, you would have to search the Pawn section of the piece list to find the Pawn in question and update its location, defeating the purpose. I sometimes still use a 'piece-type list', which keeps track of the location of the last-moved (or un-moved) piece of a given type. For pieces where only a single copy is on the board, such as the King, this would reliably track their location. But for others it would just give you the location of a sort-of randomly picke one of that type. It could still be useful in combination with a 'material key', (telling you wich material is on the board). E.g. when the material key tells you that there is only one Pawn on the board (i.e. you are in KPK), you can use the piece-type list to know where that Pawn stands in your special KPK evaluation. My semi-minimalistic engine ' KingSlayer' (the source of which can be found as the 'simple' project in my on-line repository at http://hgm.nubati.net ) uses this technique.

A completely independent issue is how to organize the code that sill do whatever you finally decide should be done. I have the tendency to violate the common (and no doubt very useful) practice of keeping routines simple by subdividing their tasks, and delegating those to other subroutines (such as MoveGen(), MakeMove(), UnMake()) which it then calls. The advantage of not having a separate MakeMove() is that you have immediate access to all variables in Search(), which you would otherwise have to pass as parameters (which is extra overhead). The disadvantage is that you would need a separate MakeMove() for the moves at game level, unless you use some quirky 'exit from the upper floor' trick like micro-Max. In my more recent engines I limit parameter passing by locating (nearly) all local variables of Search() in a struct declare locally. Subroutines then have access to all of those without the need to make any copies, by just passing them a pointer to that struct. This makes the barrier for splitting tasks into separate sub-routines much smaller. And you can also pass such a pointer in the recursive call to Search(), so that all variables of the parent node are also accessible.

E.g. in the engine I am currently working on (for the 'Gigatron', an 8-bit retro computer) I use a routine SearchMove(), which performs the task of MakeMove(), (recursive call of Search(), UnMake() and the score minimaxing (so baiscally the entire boy of the loop over moves, except for providing the next move), an returns whether there was a beta cutoff or not. This can then be called in several places in Search(), as

if(SearchMove(&f)) goto cutoff;

(where f is the pointer to the struct with variables). This makes the staged move generation much more straightforward as you can just sequentially write the code for generating the various classes of moves (hash move, promotions, loop over capture victims, killer moves, non-captures), and call SearchMove() from each of those sections. This way Search() again starts to look like the 'master control loop' of the move generator, and in most cases can immeiately search the next move that is generated (without using a move list as an intermediate). For non-captures some sorting (e.g. by history score) can be desirable, though, so they would all have to be generated before any can be searched. It is questionable whether this should be done in a convetional move list, though; to get fast sorting it woul be better to bin them by history score (keeping a linked list for each score bin), and then simply search them bin by bin.

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

Re: Minimalism in chess programming

Post by hgm » Mon Sep 24, 2018 9:00 am

maksimKorzh wrote:
Mon Sep 24, 2018 7:41 am
But I assume the problem might be because movegen somehow counts illegal moves after king has been captured
or something like that.
Indeed, perft only counts legal moves, and the move generator is a pseudo-legal move generator. So you would have to 'vet' each move for legality before you can count it. The remedy for this is to only count at d=1, and alter the code of the perft routine such that it retuns 0 if it detects a King capture and 1 otherwise, and add that return value to the node count at d=1. This makes perfting of course very slow, but if you do it only once for validating the move generator that shouldn't really matter.

The difference might not be entirably attributable to that: I see four white Knight moves that each make both one King move and a castling illegal (that is already 8 moves), and a Bishop move that pins a Pawn. That is only 9 moves. Perhaps I overlook the 10th.

Are you sure the e.p. capture after 1. a4 is counted?

maksimKorzh
Posts: 64
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Minimalism in chess programming

Post by maksimKorzh » Tue Sep 25, 2018 1:36 pm

hgm wrote:
Mon Sep 24, 2018 9:00 am
maksimKorzh wrote:
Mon Sep 24, 2018 7:41 am
But I assume the problem might be because movegen somehow counts illegal moves after king has been captured
or something like that.
Indeed, perft only counts legal moves, and the move generator is a pseudo-legal move generator. So you would have to 'vet' each move for legality before you can count it. The remedy for this is to only count at d=1, and alter the code of the perft routine such that it retuns 0 if it detects a King capture and 1 otherwise, and add that return value to the node count at d=1. This makes perfting of course very slow, but if you do it only once for validating the move generator that shouldn't really matter.

The difference might not be entirably attributable to that: I see four white Knight moves that each make both one King move and a castling illegal (that is already 8 moves), and a Bishop move that pins a Pawn. That is only 9 moves. Perhaps I overlook the 10th.

Are you sure the e.p. capture after 1. a4 is counted?
Capture after a4 is counted.

I get the idea conceptually, but feel a bit confused when you wrote:
alter the code of the perft routine
the perft "routine" (function?) actually doesn't seem to be separated... we can call search() as "perft" though... So I assume you were talking about that big all-in-one movegen-makemove-takeback -search function. correct me if I'm wrong please. So I wonder about the details of implementation:

1. count nodes at depth 1 instead of depth 0 - clear
2. return 1 on legal move and 0 on illegal, here'sthe question - micro-Max recognizes the king capture and bad castling by score:

Code: Select all

i=99*w[t&7];                             /* value of capt. piece t   */
      if(i<0||E-S&&b[E]&&y-E<2&E-y<2)m=I; 
I've been playing around with this and discovered that on king capture i == -99 (i < 0) because in relative piece values array -1 appears at king index: {0,1,1,3,/*here ->*/-1,3,5,9}, is this correct conclusion? If so is this the right place to return 0? Another question - do we return 1 at the beginning of search() as if(!depth) return 1; or somewhere else?
3. Add return value to node count: clear what to do, but unclear how.

I feel a bit stuck at this point. micro-Max is an expression of a particular way of thinking, which is probably much older than the engine itself, I'm trying to understand how you actually think while writing a chess engine, Mr. Muller, instead of blind copypasting. I can't get the entire flow of your thought though due to lack of experience. I don't want to annoy and distract you on every single little detail, so could you please suggest me how to start thinking in "micro-Max fashion" to become independent and solving the problems myself? Can I practice this way of thinking somehow?

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

Re: Minimalism in chess programming

Post by hgm » Tue Sep 25, 2018 5:44 pm

I said 'perft routine' because here you use it as such. You are right that it is just the modified all-in-one Search function. But it cannot do perft and search at the same time (as the search does beta cutoffs, which would interfere with the counting). So I assumed you just commented-out search-related parts such as beta cutoffs (or add those later), until you are satified with the perft counts.

In search micro-Max recognizes King capture by i<0 (indeed -99 in this case), but it never returns the i in that case, but instead sets m ('bestScore') to I ('INFINITY'). This is guaranteed to give a beta cutoff immediately after, as beta will never be larger than INFINITY. The test for beta cutoff is done already before the first move is searched, not just to detect the King captures, but also because you need to do that in QS (where m does not start at -I but at e (the current evaluation)). After beta cutoff micro-Max returns bestScore, so +INFINITY for King capture, which in the parent shows up as score = -INFINITY for illegal moves. If you keep that King capture and beta cutoff code at the stage where you do perft, you would count moves at d=1 only when the returned score in not -INFINITY. You would have to make sure that you would never get any other beta cutoffs, though. Which you could probably do best by always calling Search() with beta = INFINITY and alpha = -INFINITY. That would limit beta cutoffs to King captures.

I am not sure there is a special way of thinking in micro-Max. It basically does everything other chess engines do as well. It is just that I highly optimized the code for size afterwards, trying to see how things that were done twice could be moved around and combined so that they only had to be done once, etc.

maksimKorzh
Posts: 64
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Minimalism in chess programming

Post by maksimKorzh » Wed Sep 26, 2018 9:34 am

hgm wrote:
Tue Sep 25, 2018 5:44 pm
I said 'perft routine' because here you use it as such. You are right that it is just the modified all-in-one Search function. But it cannot do perft and search at the same time (as the search does beta cutoffs, which would interfere with the counting). So I assumed you just commented-out search-related parts such as beta cutoffs (or add those later), until you are satified with the perft counts.

In search micro-Max recognizes King capture by i<0 (indeed -99 in this case), but it never returns the i in that case, but instead sets m ('bestScore') to I ('INFINITY'). This is guaranteed to give a beta cutoff immediately after, as beta will never be larger than INFINITY. The test for beta cutoff is done already before the first move is searched, not just to detect the King captures, but also because you need to do that in QS (where m does not start at -I but at e (the current evaluation)). After beta cutoff micro-Max returns bestScore, so +INFINITY for King capture, which in the parent shows up as score = -INFINITY for illegal moves. If you keep that King capture and beta cutoff code at the stage where you do perft, you would count moves at d=1 only when the returned score in not -INFINITY. You would have to make sure that you would never get any other beta cutoffs, though. Which you could probably do best by always calling Search() with beta = INFINITY and alpha = -INFINITY. That would limit beta cutoffs to King captures.

I am not sure there is a special way of thinking in micro-Max. It basically does everything other chess engines do as well. It is just that I highly optimized the code for size afterwards, trying to see how things that were done twice could be moved around and combined so that they only had to be done once, etc.
Mr. Muller please excuse my foolishness but I still can't gather all this things in my mind. PLEASE have a look at my code and explain what's wrong with it - I'm going crazy trying to understand whether the problem is still in legal move count or in the movegen. I didn't invent anything better but to nodes++ on d=1 and nodes-- on beta cutoff. This gives correct counts on initial position depth 4 and the previous "tricky" position on depth 2. I got 2039 nodes instead 2049 with decrements nodes, but on depth 3: expected 97862 while got: 97884, 22 moves more than needed. I'm sorry but I CAN'T implement
you would count moves at d=1 only when the returned score in not -INFINITY.
for I don't understand where to put if(depth == 1) and what score are you talking about? score(your var 'v')? beta from previous iteration? bestScore? PLEASE look at my full code https://github.com/maksimKorzh/Minilite ... Minilite.c for I feel completely lost and need help :cry:

Post Reply