Bug 281383

Summary:	Spider: Winnable state becomes unwinnable via a reversible move
Product:	[Applications] kpat	Reporter:	davidblunkett <dav1dblunk3tt>
Component:	solver	Assignee:	Stephan Kulow <coolo>
Status:	RESOLVED FIXED
Severity:	normal	CC:	kde-games-bugs-null
Priority:	NOR
Version First Reported In:	3.5
Target Milestone:	---
Platform:	openSUSE
OS:	Linux
Latest Commit:		Version Fixed/Implemented In:
Sentry Crash Report:
Attachments:	kpat "unwinnable" position (which is winnable) kpat spider position winnable unwinnable position one reversible move from the winnable position the orignal winnable position for go with the orignal unwinnable example unwinnable position winnable position one reversible move from unwinnable2 another unwinnable game convertible to winnable. savegame 897321213 with problem demonstration

Description davidblunkett 2011-09-05 12:29:31 UTC

Version:           3.5 (using KDE 4.6.0) 
OS:                Linux

In the attached game spider_solver_broken is winnable but spider_solver_broken_unwinnable according to the solver.  There is a legal move to move between these two positions.

Reproducible: Always

Steps to Reproduce:
Load these games - the solver predicts one is solvable and one isn't but there is a legal move between them (and the game is indeed solvable from either position).

Actual Results:  
Solver gets it wrong

Expected Results:  
Solver should get it right

OS: Linux (x86_64) release 2.6.37.6-0.7-desktop
Compiler: gcc

Comment 1 davidblunkett 2011-09-05 12:31:09 UTC

Created attachment 63395 [details]
kpat "unwinnable" position (which is winnable)

Comment 2 davidblunkett 2011-09-19 08:42:46 UTC

Created attachment 63764 [details]
kpat spider position winnable

Comment 3 davidblunkett 2011-09-19 08:44:06 UTC

Created attachment 63765 [details]
unwinnable position one reversible move from the winnable position

Comment 4 davidblunkett 2011-09-19 08:46:44 UTC

Created attachment 63766 [details]
the orignal winnable position for go with the orignal unwinnable example

Comment 5 davidblunkett 2011-09-20 11:09:50 UTC

Created attachment 63793 [details]
unwinnable position

Comment 6 davidblunkett 2011-09-20 11:10:27 UTC

Created attachment 63794 [details]
winnable position one reversible move from unwinnable2

Comment 7 Parker Coates 2011-11-05 22:53:47 UTC

Thanks for all the example save games. I can reproduce with the latest version of KPat, with the exception of the second save game which is labelled unwinnable here.

Comment 8 Dan Keshet 2011-12-26 21:38:26 UTC

Created attachment 67141 [details]
another unwinnable game convertible to winnable.

A game labeled "unwinnable"; moving the 4spades to 5clubs makes it marked winnable.

Comment 9 a.kasparas 2013-09-22 10:56:59 UTC

Created attachment 82456 [details]
savegame 897321213 with problem demonstration

This game marked as winnable. If 2 lowest cards from 2nd from right column moved to 4th from right colum, it changes to no longer winable. But this move is reversible. Therefore some of them is wrong. I don't know which one.

Comment 10 Stephan Kulow 2023-01-19 11:57:17 UTC

Spider is a very painful game to solve - way too many possible moves at any given time. So the solver cuts out some of these possibilities - and sometimes it's wrong.

Comment 11 Stephan Kulow 2023-01-19 12:33:44 UTC

Don't take my word for it :) https://arxiv.org/ftp/arxiv/papers/1110/1110.1052.pdf

Comment 12 Stephan Kulow 2023-01-20 16:57:43 UTC

https://invent.kde.org/games/kpat/-/merge_requests/43 - I replaced the spider solver now, but I need better spider experts than I am to try it. Because a lot of the save games attached in here aren't solvable and I don't know if I'm just too stupid to find the solution or if the solver is real (it's very possible that the savegame of 2013 is interpreted differently now).

Any volunteers?

Comment 13 Stephan Kulow 2023-02-03 09:10:56 UTC

I'm sure there now other situations where the solver will pick something wrong, but I need new data to work on this. So this bug is fixed