[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-bugs-dist
Subject:    [Bug 279229] Solver could be made a lot more efficient with 'undo' ...
From:       Bryan <BryanFRitt () HotMail ! com>
Date:       2011-08-03 15:38:31
Message-ID: E1QodWh-0008K2-9Z () bugs ! kde ! org
[Download RAW message or body]

https://bugs.kde.org/show_bug.cgi?id=279229


Bryan <BryanFRitt@HotMail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |UNCONFIRMED
                 CC|                            |BryanFRitt@HotMail.com
         Resolution|WONTFIX                     |




--- Comment #2 from Bryan <BryanFRitt HotMail com>  2011-08-03 15:38:31 ---
(let's just call moves that can be undone without the undo button, 'manually
undo-able', to distinguish it from just hitting the undo button. And 'manually
undo-able arrangements' as card arrangements that have manually a undo-able
move that can go from one arrangement to the other arrangement and back. Feel
free to help come up with a better names)

"you're right, that we keep on solving even after having had a lost because we
found a tons of bugs this way in the solver." This should be saved for a
debugging mode. For regular use mode use mode you can do it like stated here...

"storing all positions and checking all the time if you had this before", How
about just comparing it to the LAST move? That should cover the most obvious
cases. Win-ability is transitive for manually undo-able arrangements. If the
first move is manually undo-able  , and the second move also manually
undo-able, etc... it'll be possible to manually go all the way back to anywhere
between these manually undo-able arrangements. A 'winnable' or 'can not be won'
on any of them means that these arrangements are all 'winnable' or 'can not be
won', respectively. No need to reprocess on another manually undo-able move, or
an 'undo button' move with a move that is manually undo-able.

I'm sure checking to see if a move is manually undo-able back to the last
position, and the looking at the previous arrangement's solve-ability state,
takes a lot less time would take a lot less time than trying to re find out if
it's solvable. For debugging you could have a separate mode that rechecks
solve-ability after every move.

Since the solver can't realize the win-ability is the same in undo-able
arrangements and sometimes comes up with different answers for rather or not
it's solvable or unknown, (switching from 'unknown' to 'winnable', or 'cannot
be won' or vise-versa for these), the win-ability can be made 'sticky'. When a
'winnable' or 'cannot be won' arrangement appears, any manually undo-able
arrangement is also 'winnable' or 'cannot be won'. Just find out if it is
manually undo-able.

For the 'history' aka 'undo', etc... It can be marked so that from a 'cannot be
won' point all future moves/redos will cause the game to still be 'cannot be
won' games, no extra win-ability testing needed, and once a 'winnable' shows up
all points earlier in the history/undos in a game are 'winnable', no extra
win-ability testing needed. This would save a lot of processing time when using
the 'undo'/'redo' buttons.

Above in chart form...
When ___ is found ___ history items (including it's manually undo-able
arrangements in history) are all ___ since ___
'winnable', 'past', 'winnable', "it's possible to go from the previous
positions to the current positions for this game and then go on to win."
'can not be won', 'future', 'can not be won', "if it were possible to win from
a 'can not be won' position, it wouldn't be a 'can not be won' position."

I suppose rather or not a move is manually undo-able to the last position as
well as win-ability could be stored in the history, instead of recalculated
when needed.

Maybe we could call this feature 'stickiness of win-ability' to last position.
It'll save processing time with manual undo-able moves, 'undo' when the current
arrangement is 'winnable', 'redo' when in 'can not be won' arrangements. It'll
also increase accuracy of win-ability in these cases. With only a slight
increase in processing time, if no manually undo-able moves are made, and
'undo'/'redo' buttons are not used.

two extra points for the undo history:
'winnable' point: point at which all items at and *before* in the history are
'winnable'., <= W
'can not be won' point: point at which all items at and *after* in the history
are 'can not be won'., >= L
'unknown' goes in-between these two points., !<= W & !>= L

-

Idea list overview

Using last state for moves that are manually undo-able.
Processing 'undo button'/'manual undo' when in 'winnable' state. / Processing
'future moves'/'redo button' when in 'can not be won' state.
Adding a debugging option for when you don't want to do the above.

-- 
Configure bugmail: https://bugs.kde.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are watching all bug changes.
[prev in list] [next in list] [prev in thread] [next in thread]