A few things to debate for my chess engine

[Sven]

From what I've read - this is not what should happen. Captures are forcing things, that should be investigated ASAP. MVV/LVA Value is value of captured piece minus value to capturing piece.

Anyway, trying your idea has an extermely detrimental effect on my search. (I get depth 5 with 602K nodes, whereas your idea gets depth 5 with 853K nodes).

BTW: I do use LMR.

Matthew:out

What Álvaro meant was indeed the opposite of what he wrote, he definitely meant "make sure that values for captures are always higher than values for non-captures".

Your MVV/LVA is not as it should be, better would be something like: "X * (value of captured piece) - (value of capturing piece)" where X is chosen big enough to ensure that all moves capturing a higher-valued piece appear before all moves capturing a lower-valued piece, and only for ordering between two moves capturing a piece of the same value you need the value of the capturing piece.

The point of MVV/LVA is that QxQ should indeed be tried before PxR since removing the enemy queen from the board heavily reduces the tree size. QxQ may look like an "equal capture" while PxR looks like a "winning capture", but during tree search many "silly" positions are visited where e.g. the enemy queen is simply hanging.

A correct MVV/LVA ordering, for both full-width search and quiescence search, should already result in a significant improvement of your engine in its current state.

Sven

[Evert]

BTW: I do use LMR.

My advice: forget about LMR until you get to the point where you have a search and move-ordering that works correctly.
You're just making things harder for yourself if you don't.

[Evert]

It is worthwhile to write a specialized sort than to rely upon a general library sort for time-critical code.

I don't doubt it.
It is a useful way to get something that works quickly though, which was the main motivation. It also performs better than any of my half-hearted attempts to replace it with something else (typically some variation of insertion sort).

One reason here is that any general library sort will treat record length as a variable and so moving records will always take longer than with the fixed length case.

Oh, that's actually a good point: I actually sort a tag list rather than the moves themselves, because originally my moves were stored in a 64 bit integer (don't ask). Now, the move is actually the same size as an item from the tag list (32 bit, still larger than the barest minimum you'd need) so from a size point of view, I might as well sort the moves themselves...

From BozoChess, I have presented a move sort routine that moves records exactly twice; once into a temporary array and once back into the result array. All other motion is of only score values and a one byte record index.

I've been thinking whether it would be interesting to take a look at it, mainly to see how some things are implemented (I've never looked at a legal move generator, for instance).

[Evert]

The other reason why you may not want to use a library sort is that you often only need to explore the first few moves, so if you simply select the highest value in O(n) and swap the corresponding move to the beginning of the move list, you don't need to pay O(n*log(n)) if an early cut is found.

Absolutely.
I don't remember how much time I saved by just trying the first move without sorting the entire array, but it was a nice speedup when I did.

Perhaps one should sort differently depending on whether you expect the node to be a CUT node or not.

Almost certainly; if the node is expected to be an ALL node there's no point in sorting the moves at all, for instance. The problem is that getting it wrong will hurt you quite badly, maybe more than any savings you get from avoiding the search. But that's something that would show up in testing.

[ZirconiumX]

[
What Álvaro meant was indeed the opposite of what he wrote, he definitely meant "make sure that values for captures are always higher than values for non-captures".

Your MVV/LVA is not as it should be, better would be something like: "X * (value of captured piece) - (value of capturing piece)" where X is chosen big enough to ensure that all moves capturing a higher-valued piece appear before all moves capturing a lower-valued piece, and only for ordering between two moves capturing a piece of the same value you need the value of the capturing piece.

The point of MVV/LVA is that QxQ should indeed be tried before PxR since removing the enemy queen from the board heavily reduces the tree size. QxQ may look like an "equal capture" while PxR looks like a "winning capture", but during tree search many "silly" positions are visited where e.g. the enemy queen is simply hanging.

A correct MVV/LVA ordering, for both full-width search and quiescence search, should already result in a significant improvement of your engine in its current state.

Sven

This fails, causing a search explosion - even when using the king value as X.

Matthew:out

[AlvaroBegue]

Are you sure you are sorting in descending order of value?

[ZirconiumX]

This is my descending sort function:
http://www.cplusplus.com/forum/beginner/9420/

I'm currently playing with Pawn structure terms in my evaluation.

Matthew:out

[Sven]

This is my descending sort function:
http://www.cplusplus.com/forum/beginner/9420/

First of all I hope you are using the algorithm from the last post there, right at the bottom. The other one was just swapping i and j which might be a candidate for the third place in the "how to write ten lines no-op code" competition.

Now notice that the algorithm sorts in ascending order. To change it into descending order, change "if(arr[j] > arr[j+1])" into "if(arr[j] < arr[j+1])".

The algorithm is also less efficient than bubble sort but that's another issue. Once it is working correctly you can think about replacing it by a more efficient sorting algorithm.

Furthermore, I hope you are aware of this: if the values assigned to each move and used for move ordering are not part of the move data structure but live in a separate array then you need to sort both arrays (move array and value array) in parallel, i.e. use values for comparison but swap moves + values whenever swapping is necessary.

I'm currently playing with Pawn structure terms in my evaluation.

When programming, if I encounter a problem, like the move ordering problem mentioned above, I tend to try to solve it, not to ignore it and do something different

Sven

[ChrisFlorin]

Number 1:
Do I make my nullmove all-powerful and watch it play rubbishly in the endgame etc, or do I make my Futility Pruning all-powerful and starve nullmove of nodes?

Number 2:
Play well, and slowly, or play rubbishly, but go extremely fast.

Number 3:
Evaluation (ATM I only have PSTs, and mobility made it bring out it's queen on move 2..) or Search (Alpha-Beta, has no move ordering as I'm not sure how to implement it, Futility, Extended Futility, Limited Razoring, Nullmove, LMR, Some extensions, FHR and some other stuff)?

Number 4:
Blog (lucichess.blogspot.com ) or Tinker?

Matthew:out

When developing Blackmail, I tried all of these things out of order. Your first priority should be to write a working (read: bug-free) search/qsearch algorithm with a working (read: bug-free) material+pst evaluation.

Don't worry about improvements such as lmr, futility, etc. until your evaluation is fairly complicated. lmr always hurt Blackmail significantly until two or three months ago, and I haven't worked on it much since because of school and work this semester. You should wait to perform some of these improvements until you start seeing your engine sacrifice pawns for positional advantage and then converting that advantage to a win. Then and only then, worry about advanced reduction/pruning methods like lmr and futility. Blackmail still does not perform razoring because it hurts very badly and does not reduce as aggressively as other engines using lmr.

Once you have your search/evaluation bug-free, work on move ordering (which I see you're doing). This includes hashtables, iid, history, killers, null move, etc. Good move ordering will improve your engine a lot more than anything else; some improvements I made to Blackmail's move ordering proved to be 200+ elo after 1000 or more games. (more than once!)

Also, don't concentrate so much on how many nodes your engine searches to a given depth, or how (un)intelligent some moves seem. Blackmail used to move d1f3 all the time in its early stages of development, so whatever it is you're doing, you're probably doing it right so far in my opinion. Instead of trying to figure out why it's doing what it's doing, you should just keep making small improvements one at a time until it's so smart you couldn't possibly understand why it's doing what it's doing. I'm the best at chess in my few circles of friends, but Blackmail has far surpassed my level of chess ability that I couldn't possibly beat it especially at fast time controls. It made all the same mistakes your engine is probably making at this point and will make in the future.

The best advice I can give is to set up Arena tournaments (or whatever gui fancies you) and test your engine against itself. Don't bother testing against some of the engines that come with the gui, they'll likely beat you so bad the results won't be useful to you. For Blackmail, I set up games at 1s/move time controls; Blackmail only supports the st and sd commands. Using sd, you may be able to beat some of the stronger engines even at your stage, but the results won't be useful. You want to see your engine searching faster and deeper just because it knows how to play better.

The very first thing I would do is to take the current version of your engine, make one .exe with only material+PST and one with material+PST+mobilty, pit them against each other in Arena using 1s time controls, and wait a day or two while they play each other. You should get about 300 games in 24 hours if there are no hiccups.

As far as documentation, I wish that I did something similar to Mediocre chess so I could remember some things, but I didn't. I would recommend doing so. When you make a change, make a post, or page in a word document and post your results if for no other reason than to know what you've tried. Keep in mind that trying something now may produce bad results, but good results later on (lmr for me, for example).

You can use my sorting code from Blackmail if you're having problems with it still. Just place this in a header file (sort.h):

Code: Select all

template <typename T> void comb_sort&#40;T *a, int n&#41;
&#123;
	int gap = n;
	bool swapped = true;

	while ( &#40;gap > 1&#41; || swapped ) &#123;
		if ( gap > 1 ) &#123;
			gap = &#40;gap * 4&#41; / 5;
		&#125;
 
		swapped = false;
 
		for &#40;int i=0; i+gap<n; i++) &#123;
			if &#40;a&#91;i&#93; < a&#91;i + gap&#93;) &#123;
				T temp = a&#91;i&#93;;
				a&#91;i&#93; = a&#91;i+gap&#93;;
				a&#91;i+gap&#93; = temp;

				swapped = true;
			&#125;
		&#125;
	&#125;
&#125;

Then use it like this. There is no need to write different sort functions for different types of things, just input the pointer to the first element in an array, and the number of items in the array:

Code: Select all

		comb_sort(movestack, totalmoves);

If movestack is a struct or class, you must define a < operator for it:

Code: Select all

typedef unsigned int Move;

typedef struct MoveStack {
	Move move;
	int seescore;
	int extensions;
	int sortvalue;
} MoveStack;

//Used for sorting moves in a stack
inline bool operator< &#40;const MoveStack &a, const MoveStack &b&#41; &#123; return a.sortvalue < b.sortvalue; &#125;

[hgm]

Don't bother testing against some of the engines that come with the gui, they'll likely beat you so bad the results won't be useful to you.

Actually it would be a good idea to test against Fairy-Max, which comes with the WinBoard GUI, and is a virtually knowledgeless engine. So if you still lose against Fairy-Max, it will not be because Fairy-Max has better tuned piece-square tables (it has none), better King safety (it has none, except that it does not like to move the King), better passer detection (it has none), better move ordering (it has none, except that the hash move is search first)...

So it can really be considered a baseline case. When you still lose against Fairy-Max, you must have bugs.