GNOME Bugzilla – Bug 732225
Shuffling should not end up in unplayable state
Last modified: 2014-08-29 20:56:31 UTC
When we reach a point in the game where no more moves are possible, the game asks if the tiles shall be shuffled. I happens sometimes that this shuffling ends up in a state that also has no possible moves. Then (immediately) another "Do you want to shuffle" message appears. Expected behaviour: Shuffling should always end up in a playable state.
Thank you for your report. We've been discussing this issue in a bug that I can't find now. We believe, we have at least an NP-Complete problem on our hands here and we're thinking of a solution that is as correct as it is fast and user-friendly. We can't really properly decide (algorithmically), whether the general position of pieces can, in any permutation, be solvable. And that is essentially the problem. We can't, in polynomial time, check whether shuffling can ever be successful and we also don't want to put users in an infinite loop of reshufflings in case we are in that position. I do agree with the Expected behaviour if there is a permutation that allows for more playable moves. What do you think is the expected behaviour, when the board position is in no permutation solvable? We're open to suggestions :) How long would you be willing to wait on shuffling until the game tells you "well, this is it."? We remove the undo-stack after shuffling, so if this were the case, you can't go back to a former, solvable, state. Is this acceptable? I am happy for feedback :) Mario
Competitor research time! How does Microsoft Mahjong handle shuffling? They have a shuffle button in the bottom left (which can be used at any time, with a limit on reshuffles). [1] But evidently no reshuffle prompt at the end of the game. [2] (Judging from that Facebook group, it seems somebody at Microsoft takes Mahjong a bit more seriously than we do.) So one solution would be to just limit the number of possible reshuffles at the end of the game to one or two, and then declare the game to be over. (The message dialog would need to be adjusted such that it feels more natural if you hit it twice in a row.) [1] http://apps.microsoft.com/windows/en-us/app/microsoft-mahjong/8f3ca3ad-75bc-4492-8c08-a059360e9609 [2] https://www.facebook.com/microsoftmahjong/posts/278018382378585 P.S. I think it was Bug #723425
I have to admit, I did not think about the combinatoric complexity :) I would go for a more pragmatic approach: If "Shuffle" in the "No possible moves" dialog is clicked, try many times in a row to find a playable state. I think it would be even ok to search for several seconds -- as long as there is some animation/progressbar/... and the game stays responsive. I think it is ok if some very few games end with a "could not find a legal permutation" message. The main problem I see with the current (3.12) version of the game is, that the described behaviour is really annoying and happened to me already several times. It would be much less annoying if it only happened in e.g. 10% of the cases.
Update: I am now pretty sure that the problem, whether the position on a mahjong-board is, for any permutation, solvable, is generally NP-complete. I am pretty sure that I found an O(n) constructive method to map the mahjong-board to a graph and should that graph contain a hamilton path, the position has at least one solution. But during construction we get some special properties, that we might be able to use in a heuristic to get a "negative" answer in linear time. I suggest the following: We check the number of "open" (e.g. accessible) tiles and should that number be less than 2, it's obviously not solvable. For that we can check quite fast and we should do that. And I will in about two weeks time. During the summer: I will look into proving completeness of the transformation I already have on paper. If that works out, I implement a quick-check for solvability.
Created attachment 283678 [details] [review] Hide shuffle button when only one open title exists
Created attachment 283680 [details] [review] Hide shuffle button when only one open title exists Also, change the response types of this dialog so that the code is easier to read.
Created attachment 283681 [details] [review] Remove Shuffle from list of actions Shuffle is only valid from our "you have no moves left" dialog; you shouldn't be able to shuffle at any time via D-Bus, for example.
Created attachment 283682 [details] [review] Use reasonable response types for the no moves left dialog
Created attachment 283683 [details] [review] Destroy "no moves left" dialog before using the result
Created attachment 283684 [details] [review] Do not allow shuffling if it's guaranteed to fail
Review of attachment 283680 [details] [review]: This one is superseeded by the other patches.
Created attachment 283792 [details] [review] Reshuffle continuously
Review of attachment 283792 [details] [review]: ::: src/gnome-mahjongg.vala @@ +587,3 @@ { + while (!game_view.game.can_move && game_view.game.number_of_movable_tiles () > 1) + // this is no infinite loop since Since why? :) @@ +589,3 @@ + // this is no infinite loop since + { + game_view.game.shuffle_remaining(); space before ()!
Also doesn't work. I shared that here for friends to test. Still fiddling :(
Review of attachment 283681 [details] [review]: Works fine
Review of attachment 283792 [details] [review]: I think I change shuffle_remaining() around to get the desired behaviour
Review of attachment 283684 [details] [review]: Works fine
Review of attachment 283683 [details] [review]: Works fine
Review of attachment 283682 [details] [review]: Works fine
I fixed this. I am now reshuffling until a possible move is found. If it was impossible, it's only shuffled once.
*** Bug 735694 has been marked as a duplicate of this bug. ***