To be, or not to be checkmated

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

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

To be, or not to be checkmated

Post by hgm » Fri Apr 18, 2014 7:43 am

Let me first tell you a true story that will teach us a moral lesson. (It was not really a Chess game, but I re-casted it in Chess terms to make it sound more familiar.)

My engine is playing a human. It is ahead by about +8. But suddenly, in its final iteration, it sees that in the current game position almost all moves get it mated in 5. Only a few moves 'help': first it throws a Bishop in the path of the opponent's Rook battery that is instrumental in delivering the mate (score +5). As it is unprotected, it is of course taken. Then it similarly throws a Rook in the path, which is also taken (score ~0). Now the only option left is a spite check by a QxP Queen sac on the opponent's King fortress (score -8). After that it plays one of the -M5 moves.
Now the opponent does not see the M5, the King can escape to a safer place, and the game lasts 20 more moves. But, starting from -8, this does of course not alter the outcome. Which is quite different from what it would have been when, after the opponent bungled the mate, the engine would still have been at +8.

Moral lesson: engines can be too clever for their own good.

Of course the sensible thing to do would have been to play one of the -M5 moves immediately, and cross your digits praying that he won't see the mate. Making the pointless sacs is about the worst thing you can do, as their obvious (1-ply) refutation is on the path to the mate, so it doesn't make it any more difficult to find the latter. In fact it alerts an opponent that knows engines to the fact that there apparently is a mate that he had not noticed yet! Largest DTM is not always 'best defense'. It can 'invite' the opponent to perform a checkmate he had not seen, performed as a side effect to the obvious opportunities we offer him for material gain, and in addition lose us the game even when he doesn't see it. Which pretty much qualifies as 'worst defense'! The problem is how to prevent this, however.

One of the things that makes it extra tricky is that we start from a +8 score here. In the position after the first two sacs, when the score is about even, it would be comparatively easy to make the decision to switch to 'swindle mode'. Based on the reasoning that in the previous iteration everything still looked OK (score ~0), and in the current iteration the score falls to -8, which is losing anyway, so better play the best move of the previous iteration.

But when the best move just makes your score drop from +8 to +5, it would still be a won game if it stayed at that. So why would you ever take the risk to be mated in 5? Of course the classical horizon effect plays a role here as well. But the bad thing is that even if we could somehow solve that, by extending the 3 pointless sacs by 2 ply each based on some heuristic, so that we would see it would get us mated too, this would still be a -M8 move, and thus preferred over the -M5 move. Material eval no longer plays a role when you are mated, so sacrificing Q+R+B to delay the mate by 3 moves would still seem a good deal to the engine.

Once it is seen that any move will get you mated, I guess the problem could be solved by weighting in the material in the mate score. E.g. at a rate of 1 Pawn per 2 ply. Then sacrificing a Rook to delay the mate would only be attractive when it delays the mate by more than 10 ply, but not when it delays it by merely 2 ply, like throwing into the path of the mating piece would.

But that still leaves the horizon problem, as this always happens when you for the first time see you will be mated with the normal moves, so that the mate can be pushed over the horizon through delaying sacs. Fortunately such sacs will become PV, and therefore the rest of the PV will be available for analysis. When, in a situation where the best score still is a to-be-mated score, you find a PV that captures in the second move the piece that was moved in the first move, and scores approximately the value of that piece lower than the current eval (or, perhaps better, than the score of the previous iteration or even from two iterations ago), there is every reason to become suspicious. It really looks then like the only thing achieved by the move was reducing the depth of the search of what follows to a value that we know from previous iterations to be inadequate. This suspicion might then be reason to award a 2-ply extension to the suspect move.

I guess this is actually a pretty general pattern, not just applicable to pending mates: the PV move from the previous iteration drops tremendously in score, and now you find at that same iteration some other moves that make the score drop less, namely by approximately the value of the piece that you lose in first two ply of this 'improved' PV. Better not believe it!

I wonder if it would not already be better to always stick to the move of the previous iteration, when this happens in what otherwise would have been the final iteration of the search. Even without making any effort to extend the suspect move. This could probably be generalized to cases where the score drop occurs in an earlier iteration (and the final iteration's PV then starts with a number of sacs to reduce the remaining depth to the value from before that iteration). But I am not sure this would be useful in practice, as one would expect impending doom to be always discovered in the last iteration, or otherwise you would already have been able to see it on the move before.

User avatar
SMIRF
Posts: 91
Joined: Wed Mar 26, 2014 3:29 pm
Location: Buettelborn/Hessen/Germany
Contact:

Re: To be, or not to be checkmated

Post by SMIRF » Fri Apr 18, 2014 9:14 am

It all depends on what you really want. You might wish to perform a real good move (in your quality system), or you want to gather swindled victories against a silly opponent. I rather would not chase behind such worthlessly swindled wins. The typical quality system is to postpone a mate as far as possible. Another one could be to save as much material and influence as possible in the moment of mate. The king then should consider and preserve his subordinates.

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

Re: To be, or not to be checkmated

Post by hgm » Fri Apr 18, 2014 9:35 am

SMIRF wrote:It all depends on what you really want. You might wish to perform a real good move (in your quality system), or you want to gather swindled victories against a silly opponent.
All wins are swindles, as the initial position of Chess is a draw, and by inference all opponents you win against must be silly... The best you can do is try to maximize the probability your opponent will make a fatal error. Forcing him to capture your Queen in a spite check usually does not leave much room for such an error!

But what is really silly is to think that to be mated in 6 is in any meaningful sense 'better' than to be mated in 5, if that extra ply is bought by a spite check that costs you a Queen.

User avatar
SMIRF
Posts: 91
Joined: Wed Mar 26, 2014 3:29 pm
Location: Buettelborn/Hessen/Germany
Contact:

Re: To be, or not to be checkmated

Post by SMIRF » Fri Apr 18, 2014 9:44 am

In principle you might me right. But Chess is not yet a game with its full information completely at hands. Thus the job still is to act best within an intelligently clipped part of the game tree.

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

Re: To be, or not to be checkmated

Post by hgm » Fri Apr 18, 2014 10:03 am

SMIRF wrote:Thus the job still is to act best within an intelligently clipped part of the game tree.
Sure. But 'best' is a relative notion, when you are in a lost position. Trying to last longer can greatly go at the expense of the probability your opponent will make a mistake that allows you to draw or win. And game-theoretically lasting longer is just as arbitrary a definition of 'best' as any other. The zero you get for being mated in 49 is just as fat as that for being mated in 1.

In general, sacrificial spite checks or throwing material in the path of an unavoidable mate never buys you anything even against the most stupid opponent (except perhaps a random mover). He just takes the offered material, and the situation has only changed to his advantage.

Engines are typically obsessed by delaying the made, and that is just no good.

User avatar
SMIRF
Posts: 91
Joined: Wed Mar 26, 2014 3:29 pm
Location: Buettelborn/Hessen/Germany
Contact:

Re: To be, or not to be checkmated

Post by SMIRF » Fri Apr 18, 2014 10:23 am

hgm wrote:Engines are typically obsessed by delaying the mate, and that is just no good.
SMIRF does not even know the distance to a mate found during its calculation. Having presumed a mate (still erroneous in finding an intended most "strong" way to it) SMIRF probes to estimate the distance to that mate analyzing the transposition table. There has been a lot of questions pointing to that "silly" behavior. It has been different in the vanished old SmirfMate engine, therein it always was searching for a shortest mate.

Stan Arts
Posts: 179
Joined: Fri Feb 14, 2014 9:53 pm
Location: the Netherlands

Re: To be, or not to be checkmated

Post by Stan Arts » Fri Apr 18, 2014 12:13 pm

Indeed especially in the context of having an electronic opponent to play against, something engines still don't do very well, an ability of swindling and bluffing (call it confidence..) would be really nice.
Though you are right especially in the case of -mate anything goes and even against an electronic opponent you are pretty much always better off trying to bluff your way out of it when you spot it at first. Small chance even your electronic opponent hasn't seen a mate that you have.
Probably comes down to asymmetrically ignoring certain threats in a minimax sense though. From a certain depth on and/or that fall outside a window or likely better, to acknoledge a threat and then doing a wacky research with strange bounds to find a bluffing counter instead of a "perfect" minimax one. Lots of ways to do it. When you encounter a fail low you could switch modes and research with a different evaluationfunction (empty the hash) that's purely aimed at complicating the position as much as possible opening up the position, getting pieces out in the open, to the opponents king at some cost and depending on the severity of the fail low will ignore some threats. It will be funny to try.

In january were you at the Tata steel round in the Rijksmuseum? In the corner of my eye I spotted a guy with a big beard and winterhat on (the clever disguise) walking out of the playing hall thinking nothing of it till I realised later that you live in Amsterdam and maybe it was you. It's remained a mystery to this day.

jdart
Posts: 3824
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: To be, or not to be checkmated

Post by jdart » Fri Apr 18, 2014 1:49 pm

I think HGM's example is an extreme one, but it seems human GMs pretty often select possibly sub-optimal moves that pose problems for the opponent (i.e. the correct response is hard to find).

Modern engines explore so much of the search space that they can usually win against humans without this strategy, but it is still an interesting one and might be worth trying to implement if the engine knows it is playing a weaker opponent.

--Jon

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

Re: To be, or not to be checkmated

Post by hgm » Fri Apr 18, 2014 2:15 pm

Stan Arts wrote:In january were you at the Tata steel round in the Rijksmuseum? In the corner of my eye I spotted a guy with a big beard and winterhat on (the clever disguise) walking out of the playing hall thinking nothing of it till I realised later that you live in Amsterdam and maybe it was you. It's remained a mystery to this day.
No, I wasn't there.

Alexander Zacharias
Posts: 5
Joined: Thu May 31, 2012 3:59 pm
Location: Germany

Re: To be, or not to be checkmated

Post by Alexander Zacharias » Fri Apr 18, 2014 2:59 pm

hgm wrote: I guess this is actually a pretty general pattern, not just applicable to pending mates: the PV move from the previous iteration drops tremendously in score, and now you find at that same iteration some other moves that make the score drop less, namely by approximately the value of the piece that you lose in first two ply of this 'improved' PV. Better not believe it!

I wonder if it would not already be better to always stick to the move of the previous iteration, when this happens in what otherwise would have been the final iteration of the search. Even without making any effort to extend the suspect move. This could probably be generalized to cases where the score drop occurs in an earlier iteration (and the final iteration's PV then starts with a number of sacs to reduce the remaining depth to the value from before that iteration). But I am not sure this would be useful in practice, as one would expect impending doom to be always discovered in the last iteration, or otherwise you would already have been able to see it on the move before.
Hans Berliner did something similar with HiTech, against other programs. As far as I remember it worked as follows: When the best move was constant for iteration N-3 .. N-1 and changed in the last (N), accompanied by a severe drop in evaluation from N-1 to N, the best move of iteration N-1 was played.

Some kind of poor mans opponent modelling.

Post Reply