Alexander Zacharias wrote: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.
What I had in mind was not even as drastic, as I wanted to make it subject to the additional condition that the drop in score would be explainable by the first two ply of the PV. I would not mind it so much if it replaced something complex that only is punished at high depth by something else that is punished somewhat less at equally high depth. What annoys me is that it just prefixes the troublesome line with a pointless sacrifice.
I guess the proper way would be to start iterating the best move of iteration N from scratch, to check when the score drop becomes visible, and only stick to the old move if that is too soon. But the fact that everything is already hashed for depth N makes that difficult. I guess one could spoil the hash key in the root before restarting a new iterative search of the new move, and then restore it later.
If you like "non-blunder blunders" here is a good one.
In 1984 we had been invited to enter Cray Blitz in the US Open speed chess championship held in Pasadena California (spelling looks wrong but macbook insists). There were so many they set up multiple sections and then were going to have the section winners play in a final round-robin.
We went through human IM/GM players like a knife through hot butter. In the last game of our section, which had us 3 games ahead of the nearest competitor (we had a perfect 11-0 score at this point) we played a 2000-rated (USCF expert) player, and midway through the game we inexplicably tossed our queen. Korchnoi was there along with his second (I think the WCC event he was going to play in was delayed, or something) and both were watching our play (they were not in the speed event). We lost and Gutman (His second, not sure about spelling) casually observed in a broken Russian/English dialect "machine make terrible blunder." I backed the game up to the point where we tossed our queen and asked "what would you play here?" He replied "rook takes rook and you win easily". I made the move, let Cray Blitz search for the opponent and it instantly announced "mate in 14". Turns out THAT was why we sacrificed the queen. Gutman's jaw almost hit the floor. Even Korchnoi looked at it for a minute before finally saying "of course, that bishop hidden over on the other side..."
The problem was our 2000 rated player saw NONE of this, but the program assumes the opponent sees what it sees and it took the necessary step to avoid getting mated, even if it did mean losing the queen and the game. As a human, had I seen the mate, I would have ignored it, taking a chance my opponent didn't see it, rather than making a move that easily loses the game...
Berliner suggested a fix for this which we (next year) used, although only in blitz games against humans.
"If you complete an iteration with score = N, and change your mind next iteration because the best move (score=N this iteration) fails low, and you switch to another move but still see score way less than N, then simply play the score=N move and hope your opponent didn't see the deep threat (and we know it was a deep threat because it was not seen at iteration N-1, but only at iteration N.)" It worked well enough against humans, but seems quite risky against a computer opponent.
The question already rose in 1977 in the game : Duchess vs Kaissa .
Kaissa give a rook to avoid a mate 34...Re8?! but the best try would probably be to not give the rook and hope the opponnent wouldn't see the mate ... http://www.chessgames.com/perl/chessgame?gid=1162183
this is an extremely interesting issue that you’re raising here; in fact, is has deep philosophical implications that go well beyond mundane computer chess.
In the realm of computer chess, this topic is subsumed under the notions of speculative play and opponent model search. Basically, we’re aiming at endowing chess programs with a swindling capability, i. e. to play (according to its own standards) suboptimally while speculating that the opponent doesn’t grasp the opportunity for a technically faster, but hidden win. As Vincent Lejeune already mentioned in another response to your posting, the earliest and possibly most famous example occurred in the game between Duchess and Kaissa at the Second World Computer Chess Championship in Toronto, 1977
Q5k1/4rp1p/1p1q1bp1/1B1n4/3Pp1P1/4B2P/PP3P2/2R3K1 b - - 1 34
where Kaissa played that seemingly nonsensical rook „sacrifice“ 34. … Te8, bringing their programmers a sleepless night; eventually, however, it turned out that this very move is formally optimal in the sense that it is the only remedy against a mate-in-five hidden in the position.
Peter Jansen has done some very important research in the field of speculative play – see, e. g., his excellent contribution „Problematic Positions and Speculative Play“ to the great book by Tony Marsland & Jonathan Schaeffer „Computers, Chess, and Cognition“ (Springer, 1990). In fact, he is elaborating upon the very questions raised in your posting, providing a precise structural account (distinguishing between „swindles“ and „traps“; including some nice graphics and examples) of how strong chess engines might perform swindling in the case of a deep search with a suddenly dropping (or raising) evaluation value.
However, as far as I have understood your original posting, you have re-cast a „true story“ of everyday life in chess terms in order to discuss it from the point of view of a „moral lesson“; so let’s move towards a more philosophical discussion. A telling headline in this regard might be: „Too clever is dumb!“ – not only in computer chess, but also in everyday’s human life? Perhaps this is strongly related to the point that highly intelligent people are sometimes considered to behave „clumsy“ / non-easygoing / too sophisticated / pessimistic … by more down-to-earth men?
The novelist and Literature Nobel Prize Laureate Elias Canetti not only brought to us the famous chess playing dwarf Fischerle in his novel „Die Blendung“ (Engl.: „Auto da Fé“), but wrote as well the highly intriguing essay „Die Befristeten“ (Engl.: „Their Days are Numbered“), in which he describes a fictitious word in which each person knows, from the day of his / her birth on, the exact date at which he / she will die. Transferred back to the realm of computer chess: how would a fictitious 32-piece endgame database change the way how (human or machine) chess players (should) behave when they commence their chess play? According to common perception: what would be the most „intelligent“ way of playing chess after we have eaten from the tree of knowledge?
Of course, rather than just shaking hands and signing empty move list sheets, we should temporarily forget about our perfect knowledge and try to make our best out of it, just as in everyday life! Investigations on how to enhance chess engines’ abilities to „swindle“ ultimately brings us back to highly relevant classical AI issues in the field of human-machine interaction. My gut feeling is that the type of opponent modeling required should have applications in a plethora of other challenging, typically less well-structured domains as well!
Maybe we should discuss these issues at a „1st International Workshop on Machine Lying“, bringing together AI specialists, chess experts, philosophers, and social scientists?
Well, it does touch upon the subject of opponent modelling. But I think there also is another issue here, namely the 'according to its own standards' you mention. It seems to me the standard, distance to mate, just sucks. Game-theoretically there is nothing optimal about it, there is no award in Chess for speedy mate. It is just a fiction spread by engine authors that delaying the mate as long as possible constitutes 'optimal play'. Human players frown upon it. ("why is it making these silly sacrifices if it can see they do not help?") Finding a more realistic definition of 'optimal play' in the face of mate is not really very dependent on opponent modelling. At least, not beyond the observation that the opponent might be fallible, so that the engine should keep striving for doing heuristically good (albeit game-theoretically still losing) moves when it is badly behind.
The actual game on which the story was based was a Chu-Shogi game played by my engine HaChu on the 81Dojo server. In stead of a Queen ahead it was actually a Lion ahead, and in stead of throwing a Bishop and a Rook on the path of a Rook battery, it actually threw a White Horse and a Dragon Horse in the path of a battery formed by a Dragon King and a Soaring Eagle, and in stead of QxP for a spite check it captured a Blind Tiger of the King shield with its Lion. So it was not my intension to be philosophically beyond the realm of chess-variant engines. Just to make it more understandable what happened to the average reader. Chu Shogi is a pretty hard game on a 12x12 board, with enormously powerful pieces and thus a huge branching ration, making it quite hard to reach a very high depth (7-8 ply is already pretty good, in a 1-hour sudden-death game).
Of course I understand why it is very useful for a winning engine to strive for fastest mate: it is a sure way to prevent it from putting off the mate indefinitely. But it is just the simplest kludge to achieve that goal, and not really a fundamental principle. Other metrics are conceivable that achieve the same goal. (E.g. in simple end-games there are DTZ tablebases that do the job.) A possible metric that would be more consistent with the evaluation of non-mate positions could be to award a mate as LARGE - DTM + material. This would still guarantee you will eventually reach the mate, as the material gain you are hunting at the same time is bounded. You will either keep lowering the DTM, or gain some extra material, and if there is nothing more to gain, you will play by DTM to finish the job. This might delay the mate for making a detour to pick up an extra Queen in the process, but who cares?
In fact this remind me of another story, form the ancient times when I was still active as a human Chess player: I was in a totally won position (a Knight ahead, with the opponent reduced to Pawns), but the opponent still had a passer. I had one too, and I would win the race to promotion if I kept supporting it with my King. But in stead I stepped into the 'square' of his passer with my King, so I would be able to pick it off (and he could in the mean time position his King in the path of my protected passer). This immediately evoked heavy criticism from my team mates: "Why are you wasting time on stopping his passer? You would have promoted first, and you could have mated him before he got the chance to use his Queen! Now it will take very long before you can drive his King out of the path of your passer, as you are forced to go to the other side of the board to pick off that Pawn first! You might even have to adjourn, now.". Of course what happened in reality was that I walked back to the board just to shake the hand the opponent stuck out to me in surrender. The shortest path to mate was not the quickest path to a win at all. Showing the opponent I did not intend to even allow him the illusionI would give him any chance whatsoever. Taking away his last hope, vested on that passer, left only an absolutely certain, albeit length loss for him. That was a much bigger incentive for him to resign than seeing that the mate was much nearer but in a complex situation where I could still trip. People don't think in terms of DTM. Win/loss probability is a much more sensible measure. You have to show them not that they are close to a loss, but that the loss will be certain. Stripping his material can be more effective in accomplishing that than going for the shortest mate. Especially when the shortest mate might not be the fastest mate, because you have to think about how to do it, Converting to KRK can be much more effective in getting a resign than staying in a more complex KRNKP that in theory would allow you a faster mate.
bob wrote:
Berliner suggested a fix for this which we (next year) used, although only in blitz games against humans.
"If you complete an iteration with score = N, and change your mind next iteration because the best move (score=N this iteration) fails low, and you switch to another move but still see score way less than N, then simply play the score=N move and hope your opponent didn't see the deep threat (and we know it was a deep threat because it was not seen at iteration N-1, but only at iteration N.)" It worked well enough against humans, but seems quite risky against a computer opponent.
Sounds like a very reasonable 'fix'. It should work well against humans, while also providing more natural and realistic play.
The only thing I don't understand is why NOBODY is interested in implementing this sort of 'feature' these days. Can it be that hard? It doesn't even have to be a default setting; a check-box parameter could be switched on for games vs human players.
I'm glad HGM brought this up. Maybe someone will now take the next step and include such a swindle mode into a modern engine.
bob wrote:
Berliner suggested a fix for this which we (next year) used, although only in blitz games against humans.
"If you complete an iteration with score = N, and change your mind next iteration because the best move (score=N this iteration) fails low, and you switch to another move but still see score way less than N, then simply play the score=N move and hope your opponent didn't see the deep threat (and we know it was a deep threat because it was not seen at iteration N-1, but only at iteration N.)" It worked well enough against humans, but seems quite risky against a computer opponent.
Sounds like a very reasonable 'fix'. It should work well against humans, while also providing more natural and realistic play.
The only thing I don't understand is why NOBODY is interested in implementing this sort of 'feature' these days. Can it be that hard? It doesn't even have to be a default setting; a check-box parameter could be switched on for games vs human players.
I'm glad HGM brought this up. Maybe someone will now take the next step and include such a swindle mode into a modern engine.
Regards,
CL
From the program point of view, there is 2 questions to ask :
1) Will the opponent have a good chance to see what (the fail down) I see ? (Yes, No or around 50%)
2) If I play the best move I see (where I give material), am I strong enough to draw (or win) against my opponent anyway ?
2 clear cases :
1) giving a rook to avoid a mate in 15 against a human opponent 100 Elo points weaker : don't do it !
2) giving a pawn to avoid to lose a rook in 5 moves against a human opponent 400 Elo points weaker : do it !
For cases between the 2, some kind of fuzzy logic have to be applied (the complexity of position and the remaining time of the 2 players have to be evaluate too).
bob wrote:
Berliner suggested a fix for this which we (next year) used, although only in blitz games against humans.
"If you complete an iteration with score = N, and change your mind next iteration because the best move (score=N this iteration) fails low, and you switch to another move but still see score way less than N, then simply play the score=N move and hope your opponent didn't see the deep threat (and we know it was a deep threat because it was not seen at iteration N-1, but only at iteration N.)" It worked well enough against humans, but seems quite risky against a computer opponent.
Sounds like a very reasonable 'fix'. It should work well against humans, while also providing more natural and realistic play.
The only thing I don't understand is why NOBODY is interested in implementing this sort of 'feature' these days. Can it be that hard? It doesn't even have to be a default setting; a check-box parameter could be switched on for games vs human players.
I'm glad HGM brought this up. Maybe someone will now take the next step and include such a swindle mode into a modern engine.
Regards,
CL
From the program point of view, there is 2 questions to ask :
1) Will the opponent have a good chance to see what (the fail down) I see ? (Yes, No or around 50%)
2) If I play the best move I see (where I give material), am I strong enough to draw (or win) against my opponent anyway ?
2 clear cases :
1) giving a rook to avoid a mate in 15 against a human opponent 100 Elo points weaker : don't do it !
2) giving a pawn to avoid to lose a rook in 5 moves against a human opponent 400 Elo points weaker : do it !
For cases between the 2, some kind of fuzzy logic have to be applied (the complexity of position and the remaining time of the 2 players have to be evaluate too).
Case 1 should be a no-brainer, as the best/worst case is still mate (assuming giving up a Rook only delays the mate), so trying something else loses nothing, but potentially can be a big gainer vs a weaker engine or a human player.
This is not to say that it is trivial to implement, but it's been done before, by Berliner. I like the idea of reverting to the last "good" iteration if an unavoidable mate is detected.
Case 2 could be a bit more debatable perhaps, but if you can truly avoid losing a Rook by giving up a pawn, then that should be a good move. However, if it only delays the inevitable loss of the Rook, maybe something similar to Case 1 should be applied.
carldaman wrote:Case 2 could be a bit more debatable perhaps, but if you can truly avoid losing a Rook by giving up a pawn, then that should be a good move. However, if it only delays the inevitable loss of the Rook, maybe something similar to Case 1 should be applied.
Indeed, this is what makes this problem so nasty: it often combines with horizon effect. If only the final iteration can see the problem that looms near the horizon on the move that looked good on the previous iteration (and thus must be a reasonable move), any delaying tactic will push it over the horizon. So it is in fact very likely that after a bold Pawn sac you will lose the Rook anyway.
So either you should extend the search of moves that obviously look like mere delaying tactics, or have a clever heuristic to recognize such moves. Extending could be very costly. In the example that triggered this discussion, there were three pointless sacrifices that could delay the mate, so 6 ply of extension would be needed to prove beyond doubt that they were pointless. (Even if you would take some smarter measure of move quality, that would consider it pointless to merely delay a mate by burning material, as DTM of course would not consider pointless at all.) So perhaps it is more feasible to only have the heuristic to classify a move as pointless. But this is of course risky, as you might now and then also reject moves that would truly help.
And the problem is further compounded when you already have a hefty lead. That you should not sac a Rook to avoid a mate in 15 is not so clear to me if you are a Queen ahead anyway. Even after the sac you should easily win. So why take the risk the opponent will see it?
hgm wrote:And the problem is further compounded when you already have a hefty lead. That you should not sac a Rook to avoid a mate in 15 is not so clear to me if you are a Queen ahead anyway. Even after the sac you should easily win. So why take the risk the opponent will see it?
Yes, I talked about a normal games where the material/eval is about equal. Gives a rook means : get the material to -5. You should better give a rook if you score still positive.
