﻿﻿ MatPlus.Net

Website founded by
Milan Velimirović
in 2006

1:22 UTC
 ISC 2020

Remember me

 CHESS SOLVINGTournamentsRating lists1-Apr-2020
 B P C F

MatPlus.Net Forum Retro/Math Moves that determine all the previous moves

Page: [Previous] [Next] 1 2 3 4 5
(21) Posted by Kevin Begley [Friday, Mar 2, 2012 15:22]; edited by Kevin Begley [12-03-02]

@Per,

I really enjoy this kind of problem, but, already it seems a simple algorithm can outperform top human composers.
And, I doubt stipulating a pair of moves will grant you a lasting immunity from computers.
It may seem the extension of moves is beyond the computers reach, but before you wager too much, consider:

A program needn't search all positions which result from every game of 12 (or n) full moves...
It can break any multiple-move-stipulated word-problem into milestones.

First, search to the first milestone (the first move stipulated).
You need only build a list of all distinct extended-fens (def - which includes castling & en passant rights), each of which contains only two pieces of information:
1) a single set of moves (the first path found), and
2) a boolean indicator of uniqueness (initialized to 1, but changes to 0 when a secondary path is found leading to this def).

Much of this search can be carried out in parallel; and, though some serial processing is required -- particularly constructing/accessing the def list -- there are simple ways to avoid an access bottleneck.

If there is no unique path to any of the def's (satisfying the first milestone), obviously, the problem can not have a unique solution (it's cooked).
But, let's assume there are many millions (or even more than many billions) of distinct fens, and at least one has a unique path.
That brings us to...

Second step: for each def, calculate all possible games (if any) which achieve the second milestone.
Again, you need only retain the same data.

The point being: you needn't look at all possible positions which can be reached in 12-moves...
Instead, you have a pair of searches, each of which is manageable.

Granted, the secondary searches may require many billions of starting positions.
But, this is manageable (particularly if designed for a parallel architecture), and you need only find a single counter-example, to realize a cook, and terminate the search.

And, I also grant this is only enough to validate a problem with multiple stipulations -- more is required to "auto-compose" such a problem.
But, it's really not so difficult for the computer to postulate word-problems with multiple milestones, given both a validation method, and a (relatively small) list of all def's which determine a unique path (from a single milestone).

The computer resources required are considerable -- the heat generated may even melt a few glaciers (I recommend computing in space).
And, in all honesty, I would not expect a great return -- in terms of a problem product, I doubt a secondary stipulation will provide opportunities for thematic content.
You are likely to find some puzzles, but fewer problems.

I don't believe there is sufficient criteria to enable you an intelligent bet (with some timetable) against my intuition; but, in any case, I am not likely to make such a wager.
There is already substantial profit for anyone who creates a counter-example (such a problem would be its own reward)...
I sincerely hope humans will continue to produce quality word-problems, and I don't wish to hedge against my hopes (which would be, by definition, a hopeless act).
I prefer to wish people success in this genre -- I would cheer it as a human triumph if this genre's potential is revealed to exceed my expectations.

ps: I think chess960 (aka FischerRandom) would be a very interesting variant to computer search for word problems... it also puts the programmer on track to solving word-problems w/ multiple milestones (each of the 960 starting positions can be considered a def w/ a unique path -- the leftovers from a preliminary search to the first milestone).

@Alex: Congrats on your first chess problem!
Will try to solve it this evening (i just can't think in front of a computer!).

Another possibility to have GrassHoppers is so to consider that Q is replaced by GH in the startup position, and you can even put RH and BH instead of R and B... I could try to include this on my program, but i won't go more than ply 7 this way i think (and it will already melt some ice! ;), and my prog only looks for games ending in mate. Having promotion requires to force white pawn moves (Francois did it). If someone can test a program i think it's Mario Richter, he has the stronger program.

As for chess+draughts, Thierry Le Gleuher made at least one (maybe more?) retro in draughts. Below are the two only draughts retros i know of:
The stipulations are approximately:
Henri Chiland: how did the 23 man (e7) get there?
Thierry Le Gleuher: White has just moved. Black can not force White to take back his last move and play another move (thus if last move was a capture it was the biggest possible capture). What was the last move?

@Per:
>we know that the Rösler achievement can not be surpassed
Why so? Francois Labelle says: "Is there anything else at ply 12 or beyond that would beat the current record gxf8=N#? In 2007 I verified that no such checkmate problem exists at ply 12. This leaves the slim possibility of a non-checkmate problem at ply 12, or of a problem at ply 13 or beyond."

Siep Korteling once made a draughts retro: http://www.dorinde.nl/steenslag/curiosa/waar.htm

The first diagram is missing a black king. Where is it?

@Kevin: After reading your post, we better understand why I said 'my uneducated guess'. Computers and computer science is not my strong area. But I enjoy competing with the computers, to compose problems that can not easily be checked with a computer.

@Alain: Well, yes there might be some 7th or 8th move of a game that fully determines all previous moves. If that is the case, I predict that the game will not be as beautiful as the one of Rösler and that the move needs a long description (starting square of capturing piece, piece to be captured on which square, promotion, possible check or mate sign +#). I am surprised that I have not yet found it...!

@Per (post 19) You ask can draughts problems be as entertaining as chess problems. I think the answer is yes. Somebody may ask can chess problem with 5 man only be as entertaining as chess problem with 25 man. Or can endgame with kings and pawns only be as interesting as "normal" endgame. I think this is just the same situation. Usualy good chess problems are more deep and complex than good draughts problems. But draugts can be as beautyful as chess.

@Jost (post 20)
I know several example of chess+draughts composers. I think that greatest is Aleksandr Shoshin (1878-1906). He is one of the best draughts composers (on 8x8 board) of all time. He was very strong otb player. Here is one of his awarded chess composition:
http://www.yacpdb.org/?id=181563

In post 11 in the latter link http://abrobecker.free.fr/chess/synthetics.htm is as last among the orthodox ones mentioned: 'Find the unique game containing 5... e1=N and in which black mates on his 7th move (Mark Kirtley, Probleemblad 2004/07-08)'. In addition to solution given, does this fulfill the stipulation: 1.e3 d5 2.Ke2 d4 3.Kf3 dxe3 4. Kg3 e2 5.a3 e1S 6.a4 Dd7 7.Dg4 Dxg4# ?. Is the stipulation cited correctly? Have I seen somewhere '...mates in his 7th move by a pawn move'?

Stipulation as printed:
"5...e1=N ... 7... Black has no move but to checkmate. Game?"

Updated http://abrobecker.free.fr/chess/synthetics.htm :
Removed and added problems of Per.
Modified stipulation of Kirtley's.

I modified stipulations, tell me if something still is incorrect...
The "Fairy Promotions" is quite empty for the moment, feel free to propose some problems. :)

PS: I have Chess960/Baseline problems up to ply 7 lying in my HD, but have not yet made a compilation.

Implemented Hoppers in my program and computed up to ply 7 (~45 min computing for each set of start pieces).

Synthetic problems found:
* Find the unique game ending in 4.PxN# (Q changed to G) Moreover
* Find the unique game ending in 4.Gg5xRg8# (Q changed to G)
* Find the unique game ending in 4.Rg6xNg8# (R changed to RH)
* Find the unique game ending in 4.Pe6xNd7# (Q/R/B changed to G/RH/BH)
All C+ unless my program is buggy

Will probably go up to ply 8 in a week or so.

Just another type of puzzle: white promotes on move 6th. If I give you white and black 6th move (in short notation) than you can determine all the moves. How did the game go?

My solution:
=============
1.f4 h5
2.f5 h4
3.f6 h3
4.fe7 hg2
5.h4 gh1=Q
6.ed8=N Qxh4#

=============
Can anybody find a cook?

Own try coocked; deleted. New tries.

So I hope that my solution is unique.

It starts to look good for you! Trying to find another solution I see the many finesses in your problem. I have also tried a different approach with 1.a4 5.Txa7 and 1.d4 5.Dxd7 and a double check in the 6th promoting move by white; no unique solution found. Also having the discovered check by wDd8 fails due to the existence of the e.p.-capture rule: 1.d4 c5 2.dxc5 d6/d5 3. exd6/exd6 e.p. f5 4.dxe7 Kf7 5.Dxd8 Kf6 6.e8L+ Ke5. This does not spoil your problem as the move sequence is not unique due to 2. - d6/d5.

Yes, if it turns out to be that, with the condition that white promotes in his 6th move, the moves 6.exd8S Dxh4# is the only pair of 6th moves that totally determines the previous moves, then this is absolutely a good problem. But there is not full certainty by my tries only, let's see what others say.

Thank you very much, Per! When I composed this puzzle I don't think about double checks.
I am not sure should we mark dbl check in standard algebraic notation. May be no by the FIDE rules -- http://www.fide.com/fide/handbook.html?id=125&view=article (see chapter C).
By the way, some times short notation can give us much more information than full notation. If we see moves like 6.Bfa6 than we can conclude that where is white promoted bishop on c8. Using this trick I composed another puzzle:

If I give you white 6th and black 7th moves (in standart algebraic notation) than you can determine all the moves. How did the game go if white and black promotes on move 5?
My solution:
===========================================
White: 6.Bcf4, so promoted bishop on b8
Black: 7...Rxb1#
1.d4 a5
2.d5 a4
3.d6 a3
4.dc7 ab2
5.cb8=B ba1=R
6.Bcf4 Qa5+
7.Qd2 Rxb1#
together with previous puzzle it shows AUW

===========================================
Can anybody cook it? If no,what happend if we knows only that white promotes on move 5?
Or if we knows only that white and black promotes?

Alex, your latter example reveals too much information. It is possible to cook it using a mirrored setting: 1.g4 f5 2.g5 f4 3.g6 f3 4.gxh7 fxe2 5.hxg8=B exd1=B 6.Bfc4 Bf3 7.Kf1 Bg2+

Your first problem (6...Qxh4#) is very solid; I was not able to cook it, either. Well done!

Thank you, Kostas! But I find cook in your cook. 6th white and 7th black moves must determine all the moves. But
1.g4 f6 2.g5 d6 3.g6 Bg4 4.gxh7 Bxe2 5.hxg8=B Bxd1 6.Bfc4 Bf3 7.Kf1 Bg2+. So moves 6.Bfc4 and 7...Bg2+ not determine previous moves.

Cook attempt to first problem: 6. exf8=N Qhxh4#

In addition to the second solution by Joost also 6.exf8B Qhxh4# seems to function. In the original problem by Alex this is not possible as 6.exd8B prevents the mating move on h4.

@Alex: Your cook to my cook is cooked, because it doesn't promote for black. Both sides were required to promote on the 5th move.