Verification of pruning techniques

[Ferdy]

There is delta pruning here, not sure if you tried this.
https://chessprogramming.wikispaces.com/delta+pruning

I tried this in CDrill with slight modification on calculation of delta. Something like this.

Code: Select all

int qsearch(int alpha, int beta, int depth, bool incheck){
	bool pv_node = beta - alpha > 1;
	// ...

	// Prune based on static eval
	if (!incheck){
		best_value = eval();
		if (best_value >= beta)
			return best_value;
		if (best_value > alpha){
			alpha = best_value;
		}
		else{
			// Delta pruning: Assume we can capture the highest piece (not king) of opp
			if (!pv_node && get_opp_piecevalue() > QUEEN_VALUE + KNIGHT_VALUE && alpha < 5 * QUEEN_VALUE){
				if (best_value + get_opp_highest_piecevalue() <= alpha)
					return best_value;
			}
		}
	}

	// Gen and search moves
	generate_move();

	// ...
}

It gets a good result vs the version without delta pruning.

I believe I did try the chessprogrammingwiki version a long time ago (in whatever engine I was working on back then). But I probably did it almost exactly like it's shown on the wiki. I don't remember how I tested it or how it effected results. But the fact that I didn't adopt it probably means I didn't like the results.

I will definitely be giving your variation a try. Just one question to make sure I adapt it to my engine properly:

Is get_opp_piecevalue() the sum of all opponent pieces (minus king)? And if so does it exclude or include pawns?

Thanks

It is for opp pieces only, no king and no pawns (simplified version). The intention is, even if the queen of opp is captured, the remaining pieces of opp is still capable to win, like for example, q+b+n, assume we can capture the q, the n and b is capable to mate us. You can vary the material condition of course to include opp pawns.

[hgm]

Now back to our regularly scheduled program... You're obviously deliberately misinterpreting me. Nowhere do I say or imply that "evasion" == "check".

Actually that is exactly what you did. To quote you again:

Correction, you've repeatedly stated that checks ARE candidates for futility pruning. See the cases above in which I call this out. See many of your previous posts.

Like this one for example:

When in check, futile moves deserve to be pruned just as much as when not in check.

Here you very explicity say that the statement you quote from me "states that checks ARE candidates for futility pruning". While actually is says nothing at all about checks, it only makes a claim about evasions.

So you clearly confuse evasions with checks here. And the fact that you use the word repeatedly shows that you made this same mistake in many other places as well. So by your own admission there are many things I said that you completely misunderstood, by understanding 'check' where it actually described 'evasion'.

I think it is important to first clear up these misunderstandings. So if you agree now that this quoted statement does NOT say checks can be pruned, please point out where else I "repeatedly" stated that checks could be pruned, so that we can clear up those misinterpretations too.

But if you want to play the deliberate misinterpretation game, it's not very difficult to turn that around on you. Take this sentence typed by your very own fingers for example:

In fact evasions very rarely are checks (although it can occasionally happen).

That pretty clearly shows that you think checks ARE evasions on occasion. See how easy it is is to deliberately twist someone's words around to seem like they means something other than what was intended?

I don't see any twisting here. Evasions very rarely are checks, so checks ARE evasions occasionally. Isn't that totally synonymous? It just illustrates that "check" and "evasion" are independent or orthogonal classifications of moves. As stated, their intersection is thinly populated ("rare" which I consider synonymous for "on occasion"), but it is non-empty. Most checks are not evasions, and most evasions are not checks. But it can happen that a move is both:
[d]6r1/6k1/8/8/8/6N1/8/6K1 w
1. Nh5+ is a check. After that 1... Kh7 is both a check and an evasion. So what?

Checks are checks. Evasions are moves that get you out of check. And sometimes a move that gets you out of check also happens to "give" check.

Still seem to you like I don't know the difference between checks and evasions? Now if you actually misinterpreted what I said. Perhaps you should read it again with the knowledge that I know the difference between check and evasion.

Well, that you can declamate the definition, (which I admit is flawless here) unfortunately does not mean that you always applied it flawlessly. As the quote that I started this posting with shows: you clearly claim there that I say something about checks, while quoting a statement about evasions. So alas, as long as you do not explicitly acknowledge that you now understand you were in error there, the fact that you can merely give the definitions doesn't inspire much confidence in that you actually understand them to the point where you can reliably determine whether something I say addresses a check or an evasion...

The point is that there is nothing for ME to read back. The only thing I encounter when reading back is vague (false) claims that I "repeatedly claimed that checks should be pruned", without giving a (valid) example. And on any such occasion I already immediately pointed out they were wrong. None of the claims I made of prunability were ever about checks. That was so when I made them, and it remains true when I read them back. If you disagree with that, I think the burden is upon you to point out the cases where you think I claimed checks can be pruned, so that we can debunk that misunderstanding similarly to the way we debunked your first attempt to find such a quote earlier in this posting.

I don't think it would be good to just shrug this off with a "then I must have misunderstood you, no need to look at it again, I believe you on your word for it". Because understanding that these claims were not about checks is not the same thing as understanding exactly what I claimed about evasions.

Anyway, I think the only real disagreement we're having on this point is that you say it's okay to prune when "in" check. I've been saying it's just as bad to do pruning when "in" check as it is to prune away moves that "give" check.

This definitely is a remaining disagreement. And I already explained very clearly why this is the case. What exactly in that explanation did you not understand, that you still think searching evasions that are not checks and do not approach alpha is anything else but a waste of time, at d<=1?

It seems pretty clear to me that you've also said it's okay to prune moves that "give" check. But now you seem to be implying you agree with me that pruning moves that "give" check is bad.

Well, as long as you cannot give any example of this, or can only give 'examples' where you obviously confused checks for evasions, like the one above, I guess we should consider this merely a superstition on your part.

[hgm]

It is for opp pieces only, no king and no pawns (simplified version). The intention is, even if the queen of opp is captured, the remaining pieces of opp is still capable to win, like for example, q+b+n, assume we can capture the q, the n and b is capable to mate us. You can vary the material condition of course to include opp pawns.

Well, N+P could still mate (after promoting), but N+N can not. So although perhaps better than nothing, it is a pretty inaccurate condition. Also because it for instance fails to capture the case R+R, which is smaller than Q+N, but would still leave mating potential even if one Rook is captured.

But the idea of doing bulk pruning even before you generated moves and extracted the capture of the MVV (to conclude it was futile) is a sound idea. The best implementation would probably be to tabulate this 'highest piece value' in the material table. If you hash material info, this is practically free, even if you need to be a bit subtle to determine it.

The point is that you want to have the maximum score swing here that a single capture could possibly give you, based on what the opponent has left on the board. (Plus some positional margin.) Usually this would just be the value of is highest piece. But when you get into the drawishness zone, this begs correction. With KNP capture of the Pawn would reduce you to KN = 0, so highest_piece_value should be 400 here, the 'virtual' value of the last Pawn.

[Ferdy]

It is for opp pieces only, no king and no pawns (simplified version). The intention is, even if the queen of opp is captured, the remaining pieces of opp is still capable to win, like for example, q+b+n, assume we can capture the q, the n and b is capable to mate us. You can vary the material condition of course to include opp pawns.

Well, N+P could still mate (after promoting),

Yes I know it, I was only showing a simplified version.

but N+N can not.

There are KNN vs kp pos where KNN would win.

[zd3nik]

Ferdy,

I've run your version of delta pruning through my usual battery of tests and it's not looking any more promising than the other delta pruning techniques I've tried. It's also doing about the same as other delta pruning techniques in the bullet round robin.

I'd like to run the tests you're running but looking at the files in your 4opening_sets.rar archive I don't see how you measure success/failure.

Normally epd files have a bm (best moves) and/or am (avoid moves) designation. The epd file in your archive doesn't, it only has ce values (which I guess are centipawn evaluation). Are you judging your engine based on how close it comes to that evaluation?

I don't have any guess as to how you're using the pgn files for testing.

[Ferdy]

We know there are pruning methods that would work in one engine but will not work with other engines. There are a lot of factors.

I only use two engines in the test. One the base engine and the other engine is from the base engine plus the delta. Take silver.pgn and run a match between the two engines at TC 40 moves/60s a total of 100 games since each engine will take both starting side of the position.

For epd suite also use it as starting position, I am not running it as test position but play a game starting from those positions.
I use the integrated tournament manager inside the winboard gui to run the individual suite in a match.

If the engine using the delta has won over without the delta in silver suite for example then the delta is successful for that particular suite. I knew the games are low but I am only interested how the delta would perform in this particular suite.

[hgm]

There are KNN vs kp pos where KNN would win.

Sure, but assuming they cannot win is on average probably better than assuming they can.

The point is that you can do this quite accurately by storing the 10 'marginal piece values' (i.e. the difference in value between the listed material and that same material with that single piece missing) in the material table. The material table would keep track of opponent material as well, so you would be able to see the difference between KNNPKB (where BxN might be futile while BxP is not) and KNNPKPP (where PxP is futile).

Of course storing the marginal piece value in the material table is rather expensive memory-wise. An alternative would just to probe the total material value after the capture. (Or, depending on how you imlemented material, take the difference of the material correction before and after the capture, to add it to the base value of the captured piece.) That would be a little bit more expensive time-wise. But in both cases it would eliminate the inaccuracy due to drawishness.

[jdart]

Or you could just turn off this pruning mechanism for low-material situations.

--Jon

[zd3nik]

We know there are pruning methods that would work in one engine but will not work with other engines. There are a lot of factors.

I only use two engines in the test. One the base engine and the other engine is from the base engine plus the delta. Take silver.pgn and run a match between the two engines at TC 40 moves/60s a total of 100 games since each engine will take both starting side of the position.

For epd suite also use it as starting position, I am not running it as test position but play a game starting from those positions.
I use the integrated tournament manager inside the winboard gui to run the individual suite in a match.

If the engine using the delta has won over without the delta in silver suite for example then the delta is successful for that particular suite. I knew the games are low but I am only interested how the delta would perform in this particular suite.

Thanks for the info. I'll give it a try.