search

SanchoGGP / ggp-base

The General Game Playing Base Package
8 stars 4 forks source link

Failure to solve Futoshiki 6x6 #372

Closed arr28 closed 8 years ago

arr28 commented 9 years ago

Hopefully will be fixed by #369 (Queens), but need to check.

arr28 commented 9 years ago

Need to re-enable the regression test (in PuzzleBase) when done.

arr28 commented 8 years ago

This wasn't fixed by the unguided Queens work - and it isn't clear why I ever thought it would be. Futoshiki is already legal-guided. There's nothing extra to be gained from latch analysis in this game.

What we really need is for the PartitionedChoiceAnalyser to run with this game. That should cause us to win nearly instantaneously.

arr28 commented 8 years ago

The problem, once again, is the "novel" way in which I phrased the GDL for my puzzles. In this case, it's the "quit" move, which is always valid and immediately terminates the game in a loss. If the player has messed up the puzzle somewhere along the way then, eventually, "quit" will be the only legal play and the player will be forced to concede.

PartitionedChoiceAnalyser.generatePartitionedChoiceFilter can't cope with that. The "quit" move doesn't affect any of the required base props, so the whole game is considered not to match the necessary pattern.

        if (!foundSet)
        {
          //  Input that is not in any partition - doesn't match the analysis pattern we are looking for
          return null;
        }

As a temporary gross hack, I modified that to...

        if (!foundSet && !inputProp.toString().contains("quit"))
        {
          //  Input that is not in any partition - doesn't match the analysis pattern we are looking for
          return null;
        }

...to see if the rest of the code could cope. Sadly, it can't.

When the PartitionedChoiceStateMachineFilter tries to call public ForwardDeadReckonLegalMoveSet(ForwardDeadReckonLegalMoveSet master) , it bombs out with an ArrayIndexOutOfBoundsException whilst trying to do something with the "quit" move. That code is currently proving completely impenetrable for me.

Steve - have you got any hints?

SteveDraper commented 8 years ago

I'll take a look when I have a little free time. Next weekend at the latest.

arr28 commented 8 years ago

Thanks. I'm not expecting you to change any code here - I'm just after some pointers to how the partition code works. Things like...

SteveDraper commented 8 years ago

Answers slightly out-of-order, but:

  1. Linkage inn the legal move sets is just a doubly linked list representation of which slots are active (which moves are available) in that move set. The (full set of at-any-time-possible) moves are represented by an array of the corresponding infos (masterList), and the linkage provides an enumeration of those currently available. We moved to this representation from the older bitmap-based one circa 6 months ago because it is more performant. Since (in many game) some move are always legal, we optimize the hanlding of those by keeping them always present in a leading sub-chain of the linkage, which lastImmutableActive acts as an index to the end of. The setup in the constructor you mentioned just initializes a legal move set to the always-legal-moves-only-active state given one in an arbitrary state (for the same game of course). This is entirely unrelated to partitioning.
  2. The results of the partitioning analysis are used to generate a state machine filter (PartitionedChoiceStateMachineFilter) which sits as a sort of proxy layer between the underlying propnet state machine and the API presented to the outside world. It modifies the view of legals to make only a single partition's legals active at once, so that externally it looks like there are a much smaller set of legals (which correspond to a single partition).
  3. If I hack the partitioned choice analyser to ignore the exit move then I could reproduce the crash. I have debugged this (it's a pure bug in the legal move set code that impacts the one-always-legal-move-game case), and fixed said bug (will push shortly). With both of those changes (note - I am NOT pushing the hack, so some work is needed to allow the quit move to not cause it to abandon attempts to use the partition analysis) we score 100 in meta-gaming time easily (i.e. - partitioning DOES work on this game.
arr28 commented 8 years ago

Steve - the good news is that your fix allows Futoshiki to be solved (with a bit more work). The bad news is that it breaks the Sudoku puzzles (e.g. base.sudokuGrade1). Partitioning still kicks in, but we subsequently die with...

[GamePlayer] java.lang.ArrayIndexOutOfBoundsException: -1
    at org.ggp.base.util.propnet.polymorphic.forwardDeadReckon.ForwardDeadReckonLegalMoveSet.clear(ForwardDeadReckonLegalMoveSet.java:420)
    at org.ggp.base.util.propnet.polymorphic.forwardDeadReckon.ForwardDeadReckonLegalMoveSet.copy(ForwardDeadReckonLegalMoveSet.java:441)
    at org.ggp.base.util.statemachine.implementation.propnet.forwardDeadReckon.PartitionedChoiceStateMachineFilter.determineActiveMoveSet(PartitionedChoiceStateMachineFilter.java:89)
    at org.ggp.base.util.statemachine.implementation.propnet.forwardDeadReckon.PartitionedChoiceStateMachineFilter.getFilteredMovesSize(PartitionedChoiceStateMachineFilter.java:147)
    at org.ggp.base.player.gamer.statemachine.sancho.TreeNode.expandInternal(TreeNode.java:3008)
    at org.ggp.base.player.gamer.statemachine.sancho.TreeNode.expand(TreeNode.java:2624)
    at org.ggp.base.player.gamer.statemachine.sancho.MCTSTree.setRootState(MCTSTree.java:891)
    at org.ggp.base.player.gamer.statemachine.sancho.GameSearcher.startSearch(GameSearcher.java:1048)
    at org.ggp.base.player.gamer.statemachine.sancho.Sancho.stateMachineMetaGame(Sancho.java:1176)
    at org.ggp.base.player.gamer.statemachine.StateMachineGamer.metaGame(StateMachineGamer.java:208)
    at org.ggp.base.player.request.grammar.StartRequest.process(StartRequest.java:70)
    at org.ggp.base.player.GamePlayer.run(GamePlayer.java:111)
arr28 commented 8 years ago

On the Futoshiki front, I've done something that's sufficiently unhacky to be reasonable for committing. The PartitionChoiceAnalyser now allows a very small number (2 or fewer) of inputs that don't match the pattern - i.e. they do something other than affect one of the "important" propositions. Any such inputs are added to all partitions.

With this enhancement, on my lowliest hardware, we solve 6x6 in 0.8s, 5x5 in 0.1s and 4x4 in 0.02s. I've checked a moderate range of other puzzles to ensure that partitioning doesn't accidentally misfire in other puzzles.

(This still doesn't fix Sudoku, so leaving this issue open for now.)

SteveDraper commented 8 years ago

Ok, I'll sort out Sudoku sometime in the next week ;-) Want to have our call this coming weekend?

Steve

On Tue, Jan 19, 2016 at 3:19 AM, Andrew Rose notifications@github.com wrote:

On the Futoshiki front, I've done something that's sufficiently unhacky to be reasonable for committing. The PartitionChoiceAnalyser now allows a very small number (2 or fewer) of inputs that don't match the pattern - i.e. they do something other than affect one of the "important" propositions. Any such inputs are added to all partitions.

With this enhancement, on my lowliest hardware, we solve 6x6 in 0.8s, 5x5 in 0.1s and 4x4 in 0.02s. I've checked a moderate range of other puzzles to ensure that partitioning doesn't accidentally misfire in other puzzles.

(This still doesn't fix Sudoku, so leaving this issue open for now.)

— Reply to this email directly or view it on GitHub https://github.com/SanchoGGP/ggp-base/issues/372#issuecomment-172786363.

arr28 commented 8 years ago

I've sorted out Sudoku. (Your fix to clear() didn't deal with the case where there were no always-legals.)

I've also re-enabled the regression test for Futoshiki 6x6 because we ought to be able to solve it, even on snap-ci.

Closing.