MatPlus.Net

 Website founded by
Milan Velimirović
in 2006

9:53 UTC
ISC 2024
 
  Forum*
 
 
 
 

Username:

Password:

Remember me

 
Forgot your
password?
Click here!
SIGN IN
to create your account if you don't already have one.
CHESS
SOLVING

Tournaments
Rating lists
1-Jan-2024

B P C F





 
 
MatPlus.Net Forum Helpmates h#49 legal position, non-unique (after Karl Fabel, Schachmatt 1948)
 
You can only view this page!
Page: [Previous] [Next] 1 2 3
(21) Posted by Joost de Heer [Friday, Mar 5, 2021 15:48]

 QUOTE 

8/1p3n1r/1p2k3/p2p4/3r1n2/q7/P4K2/8 (h#9)

h#6
1.Qa3-d3 a2-a4 2.b6-b5 a4*b5 3.Sf7-e5 b5-b6 4.Rh7-c7 b6*c7 5.Ke6-f5 c7-c8=S 6.Kf5-e4 Sc8-d6 #
1.Qa3-b3 a2*b3 2.Rd4-c4 b3*c4 3.Ke6-f6 c4*d5 4.Sf4-e6 d5*e6 5.Kf6-g7 e6*f7 6.Kg7-h8 f7-f8=Q #
 
   
(Read Only)pid=20783
(22) Posted by Viktoras Paliulionis [Friday, Mar 5, 2021 17:48]

This is my mistake, the stipulation was h#6, 2 solutions. The second problem also has 2 solutions.
 
 
(Read Only)pid=20784
(23) Posted by Hauke Reddmann [Friday, Mar 5, 2021 17:54]

Got a naming idea too. Since the program factually
checks whether you can weasel out a FIDE 6.9 fallen flag loss
by claiming unwinnable.

Flag Burner? Nooo, too misleading :-)
 
 
(Read Only)pid=20785
(24) Posted by Viktoras Paliulionis [Friday, Mar 5, 2021 21:29]

@Miguel Ambrona
It looks like your installation instructions doesn't fit for Windows and MSVC.
 
   
(Read Only)pid=20789
(25) Posted by Miguel Ambrona [Monday, Mar 8, 2021 13:36]

@Viktoras Paliulionis
The installation has been tested on Ubuntu >=18.04.
I don't use Windows and cannot help you with the installation there.

I wonder how much time it takes for other specialized tools to solve those two helpmates. (Note that my tool is simply doing brute-force when used for helpmates, since it is not designed for that purpose).

I believe that under the promise that the puzzle has 1 or 2 solutions, one can design a very efficient solving algorithm based on iterative deepening that completely prunes branches with a transposition at the same level (since transpositions will lead to non-unique solutions).
But even in those problems, how do you prove that the solution is unique without exploring (almost) the full tree up to a certain depth?
 
   
(Read Only)pid=20804
(26) Posted by Viktoras Paliulionis [Monday, Mar 8, 2021 23:47]

Solving test with the Popeye:

8/1p3n1r/1p2k3/p2p4/3r1n2/q7/P4K2/8 (h#6, 2 solutions)
Solving time: 1.7 seconds.

3n4/2k5/1p6/1b6/p2p2p1/Pp1p2p1/1P1P3p/R1B1K3 (h#5, 2 solutions)
Solving time: 8 seconds.

Popeye has two solving modes for helpmates: brute force and intelligent. In addition, Popeye uses hash tables to avoid analyzing the same position more than once. In the intelligent mode, the program first generates all possible mating positions and only then uses the brute force to reach these positions. The intelligent mode is especially effective for moremovers (h#4-13), and if there are only few white pieces. Popeye in both modes finds all solutions (if the user does not limit their number), which is very important for chess composers. The program starts solving with 1 move and then increases the number of moves (h#1, h#2, ... h#n). More information can be provided by the Popeye developers.

The solving time is highly dependent on the initial position of the problem, and although Popeye solves most of the helpmates quite quickly, there are positions that cannot be solved even within a few hours.
 
   
(Read Only)pid=20808
(27) Posted by Olaf Jenkner [Tuesday, Mar 9, 2021 00:05]

For comparison Gustav's solving time:
h#6 4.0 s
h#5 1.5 s
Gustav doesn't have an intelligent mode. A lot of helpmates
are solved faster by Popeye.
Some intelligent stuff was built in for the last 3 moves.
 
   
(Read Only)pid=20809
(28) Posted by Dmitri Turevski [Tuesday, Mar 9, 2021 08:06]

 QUOTE 
The program starts solving with 1 move and then increases the number of moves (h#1, h#2, ... h#n).


This applies to any stipulation, not only helpmates.
The approach may seem counter-intuitive - why waste time searching at smaller depths when we ultimately want to do the full search at the desired depth, but the idea is that these searches allow popeye to fill the transposition tables (aka hash-tables) with lots of info like "position X has no solution in K moves".
This kind of data is very valuable when it's analyzing the position in K+1 moves as it allows to prune the branches effectively and the extra time is paid off.

I'm not a real popeye dev, though, Thomas and Torsten should have more insight regarding this.
 
 
(Read Only)pid=20816
(29) Posted by Vitaly Medintsev [Tuesday, Mar 9, 2021 08:53]

@Viktoras
"Popeye in both modes finds all solutions (if the user does not limit their number), which is very important for chess composers."

Not quite correct. In the intelligent mode, Popeye finds only one line of play that leads to a certain mate position.
For example h#7 K7/1r6/8/8/8/5N2/8/1r5k has two solutions while just one displays after testing in the intelligent mode.
 
   
(Read Only)pid=20817
(30) Posted by Viktoras Paliulionis [Tuesday, Mar 9, 2021 09:44]

This seems to be a bug in Popeye. If you change the position a little (e.g K7/8/1r6/8/8/5N2/8/1r5k), all solutions will be displayed. By default Popeye searches all solutions in intelligent mode, but after the intelligent option, the maximum number of solutions per mating position can be given (see Popeye documentation).
 
   
(Read Only)pid=20818
(31) Posted by Vitaly Medintsev [Tuesday, Mar 9, 2021 10:12]

In such case, this bug exists a long time.
I saw it while testing several different positions.
 
   
(Read Only)pid=20821
(32) Posted by Miguel Ambrona [Tuesday, Mar 9, 2021 13:54]

@Dmitri Turevski
Right, iterative deepening and hash tables are a must.
Another way to see why iterative deepening is not so crazy is to realize that (assuming an average of 35 legal moves per position) the search at depth k+1 is 35 times bigger than the search at depth k. So doing the search at depth k one extra time makes it 36 instead of 35, which is nothing compared to the benefits that it can bring (move ordering, filling the table, etc).

@Viktoras Paliulionis
I find unbelievable that this puzzle can be proven to have only two solutions in a couple of seconds:
8/1p3n1r/1p2k3/p2p4/3r1n2/q7/P4K2/8 (h#6, 2 solutions)

Is Popeye really proving that there are no more? Or uniqueness would require a more expensive check?
 
   
(Read Only)pid=20826
(33) Posted by Viktoras Paliulionis [Tuesday, Mar 9, 2021 15:46]

No proving is needed, because Popeye looks through all possible moves and, when it finds a solution, displays it, and stops when all moves have already been checked. In intelligent mode, cutting-off a branch occurs earlier, therefore solving is so fast. In brute force mode, solving is much longer because clipping occurs when the max level is reached or when an unsolvable position is found in the hashtable.
 
   
(Read Only)pid=20827
(34) Posted by Olaf Jenkner [Thursday, Mar 11, 2021 00:14]

@Dmitri
Gustav doesn't save time when it starts solving with 1 move and then increases the number of moves.
There is no benefit from filled transposition tables. But it's also true that not much time is wasted,
in most cases below 10%. So it is recommended to set this option for testing. Shorter solutions will be found much faster.

@Vitaly
Gustav finds both solutions in 50 seconds. It has no intelligent mode, but some optimizations to stop searching if no mate is possible.
These optimizations are applied the last 3 moves. All moves before are discovered because it's a brute force search.

@Miguel
Your example h#6 is easy to compute. It takes Gustav 4 seconds. As decribed above, Gustav searches 3 moves brute force.
In 99.9% the position after the third move is a shuffled one with the white pawn far away the 8th rank.
Humans see immediately there is no chance for a h#3. A computer program has to prove that and sometimes this proof takes
more time than the whole brute force search for the last three moves. As a programmer I have to find the balance to get
a short solving time.
 
   
(Read Only)pid=20830
(35) Posted by Viktoras Paliulionis [Thursday, Mar 11, 2021 01:01]

@Olaf Jenkner
Gustav's result for this h#6 is very good because in brute force mode Popeye solves it in 8 minutes. How many CPU cores does Gustav use?

With single white pawn, a simple optimization is possible by calculating the distance from the pawn to the black king and stopping the search if the distance is too great. Does your optimization algorithm work if there are no pawns, for example, for the following problem: 2r4n/K7/b7/4r3/8/3qk3/8/7B h#8.5
 
   
(Read Only)pid=20831
(36) Posted by Olaf Jenkner [Thursday, Mar 11, 2021 02:44]

Gustav uses one core.
My optimization works, but your example is too hard. I estimate 3 weeks computing time for your database find.
Give me the first two moves of the solution (only one?) and I can tell you the solving time.
 
   
(Read Only)pid=20832
(37) Posted by Viktoras Paliulionis [Thursday, Mar 11, 2021 08:47]

One solution: 1...Be4 2.Bc4
 
   
(Read Only)pid=20833
(38) Posted by Joost de Heer [Thursday, Mar 11, 2021 09:30]

Popeye Windows-64Bit v4.86 (3034 MB)

0 potential positions in 1+0 (Time = 0.068 s)
0 potential positions in 2+1 (Time = 0.070 s)
0 potential positions in 3+2 (Time = 0.070 s)
0 potential positions in 4+3 (Time = 0.070 s)
0 potential positions in 5+4 (Time = 0.070 s)
0 potential positions in 6+5 (Time = 0.080 s)
0 potential positions in 7+6 (Time = 0.080 s)
3 potential positions in 8+7 (Time = 0.090 s)
1...Bh1-e4 2.Ba6-c4 Be4-h7 3.Sh8-g6 Ka7-b6 4.Re5-e6 + Kb6-a5 5.Ke3-e4 Ka5-b4 6.Qd3-d6 + Kb4-c3 7.Ke4-d5 Kc3-d2 8.Sg6-e5 Kd2-e3 9.Rc8-c5 Bh7-e4 #
17 potential positions in 9+8 (Time = 2.101 s)

solution finished. Time = 2.101 s

(4.86 is the development version, which can be found at http://joostdeheer.nl/popeye/)
 
   
(Read Only)pid=20834
(39) Posted by Olaf Jenkner [Thursday, Mar 11, 2021 11:16]

Gustav's solving time for the position after 1...Bh1-e4 2.Ba6-c4 Be4-h7 3.Sh8-g6 is 9 min.
An intelligent mode is needed.

Gustav's solving time for the position after 1...Bh1-e4 2.Ba6-c4 Be4-h7 3.Sh8-g6 Ka7-b6 4.Re5-e6 Kb6-a5 is 2 seconds.
With optimization switched off it takes Gustav 14 minutes!
My optimization algorithm works fine.
 
 
(Read Only)pid=20835
(40) Posted by Viktoras Paliulionis [Saturday, Mar 13, 2021 16:28]

Popeye v4.86 solves about 15% slower than v.4.85 on my PC.

The new version has the same bug. After I opened the issue on github due to Vitaly's example, Thomas Maeder commented:

"There is a strange interaction between intelligent mode and the hashtable.

If the hashtable is suppressed with the command line option -maxmem 0, Popeye finds both solutions.

If the hashtable is active, solving stops after 1.Rb7-f7 Sf3-h4 2.Rf7-f1 after the resulting position is found in the hashtable, probably from 1.Rb1-f1 Sf3-h4 2.Rb7-b1. But why exactly solving stops isn't clear yet."
 
   
(Read Only)pid=20841

Read more...
Page: [Previous] [Next] 1 2 3

MatPlus.Net Forum Helpmates h#49 legal position, non-unique (after Karl Fabel, Schachmatt 1948)