Reproducible error with Lode Runner A* path

[schrum2]

I think there is still some kind of problem with the A* calculation in Lode Runner. Here is a series of steps you can go through to find a problem level:

• Launch LodeRunnerGANLevelBreederTask
• Click SetGANModel
• Select LodeRunnerAllGround5LevelsEpoch10000_20_7.pth (the first model in the list)
• Click ShowSolutionPath

You'll notice that the level on the bottom-right (and others) do not have blue solution paths. However, these levels are beatable. Even if you increase the A* budget, it doesn't seem to help.

[schrum2]

I think you'll need to actually load us this exact json and extensively analyze what is happening with the A model. Also, this level is very similar to an actual level in the training set ... how well does A do on that level? What is the difference?

[schrum2]

I think the only solution at this point is to make a better heuristic.

[schrum2]

It occurred to me that the problem of finding all of the treasures is actually a Travelling Salesman Problem. Therefore, we should solve it that way instead of using A. However, we still have to use A to figure out how to get from one treasure to another. Here is a sketch of how we can fins the shortest solution path for a level:

1. Figure out the distance from each treasure to each other treasure in both directions. This can be done by reducing a level to consisting of only one treasure, and artificially placing the agent spawn point at the location of the other treasure, then running A. Although running A over and over will have a cost, each of these sub-problems should be cheap to solve. Note: we probably have to save all of the action sequences too.
2. Use the information from part 1 to build a directed graph. This graph will contain the ACTUAL costs from each treasure to every other treasure, and have directed (one-way) edges. Note that the agent spawn point also needs to be a node in the graph, but this is a node with ONLY outgoing edges (no need to return to the spawn point).
3. Now that we have the graph, we basically have an Asymmetric Travelling Salesman Problem (ATSP). I know that algorithms exist for solving this ... we will need to look for one on the internet and/or in the research literature. I'm hoping we can find some Java source code, but we can write the solution ourselves if needed.
4. The solution to the ATSP will tell us which treasures to visit in which order. We can use this information to stitch together all of the previously saved action sequences to get a solution to the problem.

I think this is the best way to go, but let's sit on it for a day or two before diving in ... something easier to write might occur to me.

[schrum2]

Search for GitHub repos and Maven libraries that can solve the ATSP problem in Java.

[kdsteckel]

Write a separate class that loads level 4 and then computes the a* distance between every gold to the other. See how long it takes, if it takes too long then we need to scap this.

[schrum2]

Eventually, we want to have a method that takes a level in List<List> form and returns a single action sequence for beating the level, the way that A* does. We also want the code to display that path on the rendered images (the blue X marks).

However, be careful when changing that code. Have a boolean command line parameter like "solveLodeRunnerAsTSP". If this parameter is true, then your new TSP approach will be used ... otherwise the original A* approach will be used. We might want to compare them, and what we have does still sort of work, so we don't want to completely destroy/disable it.

Eventually, we will have a parameter for "lodeRunnerTSPSolutionMethod", but this will be a class parameter. Being able to define this as such will require you to make each solution approach be its own Java class, but don't worry about that for now ... just try to get ANY approach working before worrying about having multiple approaches.

[kdsteckel]

If a level is not listed here then it was an optimal(at least from what I could tell) solution. The levels listed under not optimal are levels that I thought were less than optimal solution paths, but they still finished very quickly so I'm not sure if it matters that much. The levels that are not optimal: 2, 8, 15, 26, 28, 30, 32, 59, 82, 83, 87, 101, 103, 112, 122, 125, 128, 133, here are a few examples of not optimal path I found:

Not sure what happened with level 141:

Levels that get a Null Pointer Exception; I think it is because they do not have a valid start state: 6,7,9,11,14,17,21,22,23,25,29,31,33,37,38,41,42,43,46,47,49,50,52,55,57,58,60,61,64,65,67, 69,70,71,72,75,77,79,81,84,86,88,90,91,92,93,94,95,96,98,99,104,105,106,107,108,109,110, 113,117,119,120,121,123,124,126,127,130,135,136,137,138,140,142,143,144,146,147,148

[schrum2]

I've made a new permissive model, but I don't like it because it cheats and makes weird solution paths. Here is what you need to do.

First, verify that this new approach can beat all of the levels. If we still can't win, even after cheating this much, then more work is needed on the model.

However, if we can beat all of the levels, we still want to avoid cheating as much as possible, so do the following:

1. Change ALLOW_WEIRD_SIDE_WAYS_MOVE_THROUGH_DIGGABLE into a non-final variable that is set in the constructor of the LodeRunnerState. Whenever we create a new start state, we are designating whether we want to allow these cheating actions.
2. When you are building the TSP graph, try finding a path between points without cheating first. Only generate a cheating path if the first result is null, by restarting the search with a start state that allows the weird types of movements.

This should allow us to beat all levels, but with minimal cheating.

[kdsteckel]

Still getting null pointer after allowing to walk on the bottom of the level: 16,41,46,47,61,64,69,70,71,75,98,110,136,137,148

[schrum2]

In order to create getTSPGreedyWithBacktrackingSolution do the following:

getTSPGreedyWithBacktrackingSolution will be a kick-off for a recursive method greedyTSPStep that takes a Graph and a partial solution of List<Pair<Graph<Point>.Node, Double>> (starts empty). If every node has been visited, return the completed path. Else, sort the adjacencies by cost (might want to make a helper method that returns a sorted list of these), and take the first one ... add it to the solution. Then make a deep copy of the graph before removing the node that you just vacated. The copied graph with the node removed will be in the recursive call to greedyTSPStep that works toward finding the solution.

However, what if you hit a dead end? In this case, instead of returning the solution path, you return null. The place where you call greedyTSPStep needs to check for this result. This is why you sorted the list by cost instead of simply finding the min. At this point, you loop to the next edge in the list (second cheapest cost) and repeat the process with that edge ... but since you made a deep copy of the graph earlier, you get back the edges that were removed when leading up to the dead end path. If you loop through all adjacencies of a node and none of them work, then return null again, and the previous level of the recursion handles things in a similar way.

Note that for any level where the plain greedy approach worked, you should get the exact same solution with this approach ... in fact, make a unit test verifying this.

[schrum2]

The backtracking TSP solver seems to work now. At the very least, it solved level 41.

@kdsteckel Your next step is to test ALL of the levels and see if this finally solves them all.

[kdsteckel]

Still getting a Null Pointer: 47,61,64,69,70,75,98,136,137,148 This is the error we get for 47,61,64,69,70,75,98,137 This is the error we get for 136,148

[kdsteckel]

These levels are unsolvable for our model because it currently ignores the enemies, but these two levels require that the enemies bring the treasures to you.

[schrum2]

@kdsteckel I think it's fixed now! However, it doesn't beat all of the problem levels you found. Basically, the algorithm either works, or seems to freeze ... I think that the amount of computation is just outrageous. Still, I think that there are even more levels that have a problem of needing the enemy to bring the gold to the player.

So, the remaining steps that are necessary are:

• Test ALL levels again ... not just the problem levels, but even ones that worked before.
• Among the levels that worked, see if the paths are weird ... especially find levels where a "normal" path works, but a weird/cheating path is chosen
• Document all levels that don't work (and why) in this thread

[kdsteckel]

Levels that had weird paths: 37,53,72,77,84,103,107,125,126,142 These are the extreme examples, but most of the paths had unnecessary digging. Levels that still do not work at all: 7,86,136,148 136 and 148 we know are not solvable by our model, but 7 and 86 were working before and are now not working... strange. From watching play through for level 7, I saw that when falling the player fell through the blocks if there was only one diggable block. This makes them able to get the block that they are unable to get in this level using our model. From watching playthrough for level 86, it looks like they were able to fall through 2 diggable ground tiles to get to the gold that stopped our model from solving it. took too long to see results: 64,75,98,137 From watching game play of level 75, you have to stand on the enemy to get to the ladder on the bottom right (it does reach all the way to the ground) that allows you to get the treasures in the top right of the level. From what I could tell every one of these levels fails because you need to interact witht eh enemies to fully beat the level. Either in the way that level 75 does mentioned above, or needing them to bring you treasures.

Video of play through from version we are using: https://www.youtube.com/watch?v=sRhP8Nk0exw&t=124s

[schrum2]

I recently changed the A* model to be more restrictive about digging downward ... you can only dig down if there is a place to stand next to the diggable ground. This is why levels 7 and 86 now fail, even though they were beatable before. However, the video reveals that these levels aren't beatable after all, since we don't have a way of representing blocks the player can fall through. Therefore, being unable to beat them is actually the correct behavior.

This is true of the other levels too, since they depend on enemy mechanics we don't model. Therefore, all of these levels should indeed be unbeatable.

However, I find it alarming that the A* model is somehow allowing the player to climb to unreachable spots on some of these levels ... or perhaps the TSP process was checking what it would be like to start at certain unreachable gold pieces? How exactly were your left-side pictures made? Tell me how to recreate them

[schrum2]

In addition to explaining why X marks appear in unreachable places, go ahead and make a plain text file in the Lode Runner VGLC directory that contains notes on all of the levels that have weird issues, indicating whether or not they are beatable by our model and why. Basically, I want the notes from this issue thread to be in the repo.

[kdsteckel]

To get the result for having X's in unreachable places just run the TSPUtil class on the level you want to test it on with the debug code uncommented. @schrum2