Fixes for KPat Forty & Eight patience game

[Ian Wadham]

Hi Albert,

Thanks for replying.

> On 17 Jul 2020, at 6:38 am, Albert Astals Cid <aacid at kde.org> wrote:
> 
> El divendres, 10 de juliol de 2020, a les 7:38:40 CEST, Ian Wadham va escriure:
>> Hi guys,
>> 
>> Good news. In brief, I have found two or three causes of the 10 bugs listed in
>> https://bugs.kde.org/buglist.cgi?quicksearch=kpat%20forty%20eight.
>> 
>> However, I am going to need help from an expert with a knowledge of the KPat code to work out the most appropriate patches.
>> 
>> I will also need help to get patches committed, when they are ready, because I do not have access to or knowledge of the newer KDE Community repositories and procedures.
>> 
>> The bug list above relates to false positives and negatives from the 48 solver and touches on problems with the Autodrop feature. The false reports from the solver were easy enough to fix in patsolve/fortyeightsolver.cpp. However, when I tested my fixes, I found that the false positive had been fixed but the false negative was still there.
>> 
>> The false positive is due to the 48 solver generating an invalid move and using it to reach a win, then saying that the game is winnable when it is not. The human player cannot win because he/she is not able to make that move, except by using Demo to bypass it ;-). Actually the 48 solver generates invalid moves quite often (as shown by Hint), but they are not always used or needed in a winning solution.
>> 
>> Forty & Eight is a 2-pack game. False negatives can occur when there are two cards of the same suit and rank that can “go out” onto a foundation pile. The 48 solver always chooses the card on the left and ignores the other one. Sometimes playing the card on the right leads to a win, and the left hand card is a loser or not a good choice.
>> 
>> For example, stack 0 (on the left) may have a 2 of hearts on top and other suits beneath, whereas stack 4 may have the 2-3-4 of hearts in sequence and nothing else beneath, and then an ace of hearts comes out of the talon (or heap). The solver will consider only the 2 on the left to "go out" onto the ace, but the other 2 would almost always be the better option because three cards can go out, rather than one, and they will leave an empty stack 4 as well. Empty stacks are an advantage in later play.
>> 
>> When I had fixed the 48 solver to deliver both cards that can go out, Autodrop kicked in (specifically bool DealerScene::drop() in file dealer.cpp) and undid my good work. It uses DealerScene::getHints() to get a list of playable moves and selects out those that go out to foundation (or target) piles. Trouble is that if there are two cards of the same suit and rank in the list, Autodrop always plays the first (leftmost) one. It then returns, letting the animation of the move proceed, but when it is called back the second card is no longer playable (nor hinted) because the first card has taken its spot. In this kind of situation neither card should be autodropped. The human player should be left with a choice as to which card to play, unless it does not matter (e.g. if each card is the only one in its pile and either can go out first).
>> 
>> I have developed a patch to fix DealerScene::drop(). It takes effect only if the current game is Forty & Eight, because I am worried about adversely affecting other KPat games. I have looked at other multiple-pack games, but Mod3 and Gipsy do not seem to use Autodrop. I am not so sure about Spider, but perhaps it also is affected by Autodrop grabbing cards too soon.
>> 
>> Unfortunately my patch is rather kludgey. It is also a pity that it cannot get at some information known to the 48 solver and passed back to the main KPat solver, patsolve/patsolve.cpp, i.e. which possible moves are automatable. If there are two cards of the same suit and rank that can go out, the 48 solver flags neither one as automatable.
>> 
>> I really need help from a KPat expert to work out what is the best thing to do here.
> 
> Unfortunately I don't think we have many KPat experts around anymore, Shlomi and Fabian are the two that did changes to somewhat core parts lately.

I was hoping Parker Coates might be able to advise us. I did see a post on kde-games-devel from him not long ago.

> My suggestion would be for you to put the patch as a Merge Request in invent.kde.org

I have looked at that online, but I am really not up to it, Albert. The last review tool I had anything to do with was ReviewBoard and I have not committed or checked out anything for about five years. I have been keeping an eye on things using “anongit" and sometimes offering suggestions or a “diff -u” style patch (not a “git diff” style one). But as of now I cannot even figure out how to get a read-only git clone of KPat from invent.kde.org.

Furthermore, I am now working with one arm tied behind my back. Not only am I getting old and forgetful, but also the only source-code I am able to edit, compile and build on my Apple Mac is from KDE Release 4.14.3. The makeshift build system I used to have (based on kdesrc-build) no longer works, thanks to changes in Apple OSX, so I am subverting Macports to compile my patches into its KDE 4 version of KPat — cumbersome but workable.

All that is not as bad as it may sound from your (KF5) point of view. Before I started, I did a diff between KF5 KPat master and the KDE 4 version and it turns out that the kpat/patsolve/forteightsolver.h and .cpp files differ very little. The line counts are almost exactly the same and the line-by-line differences are all linguistic (e.g. using more recent dialects of C++, such as the keyword “override”), while leaving the actual 48-solver functionality unchanged (yes, the bugs I am looking at are that old — may even go back to KDE 3).

Long story short, I think I can supply patches that apply to current KPat master.

However they will be “diff -u” style patches, i.e. one file per patch, as opposed to “git diff” style patches that can apply to several files.

> and that way we all can have a look at it and maybe try to understand it together.

Indeed. I look forward to that.

I have found fixes for three bugs, two in the 48-solver and one in kpat/dealer.cpp. The first is where the solver uses an invalid move. The other two are where it fails to use both cards to search for a solution when two cards of the same suit and rank appear in the face-up stacks.

I am currently somewhat confused by the failures in Autodrop when cards that “went out” have been “Undone” and then will not autodrop when the opportunity to replay them returns. Apparently, several KPat games are affected by this one. I can see the code that causes the problem, but I cannot understand how the code works, nor the reason for its inclusion in KPat, nor when or why it was committed. So I am hesitant to change any of it.

I think the best I can do, over the next week or so, is first to tidy up the bug reports in:

https://bugs.kde.org/buglist.cgi?quicksearch=kpat%20forty%20eight,

flagging duplicate reports, collating test cases, etc. Then I can add my patches as attachments to whichever are the “main” reports (with appropriate comments). Then maybe links to that work in Bugzilla could help kick off any discussion on a merge request.

What do you think, Albert?

Cheers, 
Ian W.

> Cheers,
>  Albert
> 
>> 
>> Cheers,
>> Ian Wadham.