Respec Calculator

[teuneboon]

This one might be kind of hard, but I would love the option to select 2 trees and have a "most optimal respec path" calculated for it. It would give you a quick idea of how many regrets you have to get and it might catch some stuff you didn't think of for respeccing. If you add it I'll make part 2 of this: https://www.youtube.com/watch?v=WEDGBkvbKYI include it ^^

[EmmittJ]

You can kind of get something like this using the Skill tree comparison tool (located at the bottom of the builds list).

[brather1ng]

I think what he means is more on the lines of calculating the optimal way to respec. It's not always possible to just regret the old nodes and after that skill the new ones. It might need more regret orbs than just the node difference you get from the comparision tool. The feature would output (and maybe visualise) the minimum regrets required for respeccing.

This is something I'm interested in doing, but I do have a decently sized backlog of skill tree generator related stuff I'd want to do first and also don't have much time atm. So I'll definetely not start working on it in the near future.

[EmmittJ]

Alright, that makes more sense actually. Well, no rush really. I have a lot
of things to do that is ahead of this as well

[teuneboon]

Just to confirm: the most optimal path thing is what I meant yes.

[rikai]

I would very much like to see this, i'm pretty terrible at figuring out optimal pathing myself, any update on where this stands on the list? :)

[brather1ng]

A lot of new, more important stuff on my list, so this is still far away, sorry.

[MLanghof]

So it's been a while but I started looking into this today. I'll keep using this issue since it's already open. If possible, I'd appreciate if someone could follow through my thoughts in this post to verify my basic assumptions (I found a counterexample to one of my earlier "proofs" and despite many revisions Lemma 6 failed to be what I wanted it to be - things are a lot less trivial than they may seem initially). This should serve partially as documentation and partially as peer review.

---

The problem formally consists of trying to find a transformation from one node set (say, A) to another (B) through a serious of point allocations (including a node adjacent to the set) and deallocations or "unspecs" (removing a node without disconnecting any nodes from the set) over the graph G (the skill "tree") such that the number of deallocations is minimal and the number of nodes in the node set never exceeds a certain limit (N). We will also require A and B to contain at least 1 common node (class start node) that cannot be unspecced (or allocated).

I will include the option to have a certain amount of unallocated points u := N - |A|; these can be treated as nodes in A that are unspecced immediately and "for free". I will assume |A| = N from here on. (This also follows from combining the proofs in Lemma 1 and Lemma 3.)

---

Lemma 1: We can assume both node sets to have the same number of nodes N.
Proof: If B has more nodes than N, the problem is unsolvable. If it has k nodes less, then solving the problem for B̂ consisting of B and k added "leaf" nodes yields an optimal solution by omitting the allocation of those leaf nodes. There cannot be a better solution for B than this because otherwise the best solution for B̂ would consist of the solution for B plus the allocation of the k leaf nodes.

Lemma 2: We can represent the transformation as a series of "steps", whereby each step consists of one unspec followed by one allocation.
Proof: With every point that we unspec, we reduce the amount of options for where to allocate a point (ignoring the one we just unspecced, which is clearly suboptimal to allocate again right away). It is thus impossible to require more than one unspec in a row: The first allocation after a series of k unspecs could just as well happen after the first of those k unspecs. Since |A| = |B| (Lemma 1) we must allocate exactly as many nodes as we unspec. Together, this means we can represent the transformation as an alternating series of unspecs and allocations (starting with an unspec and ending with an allocation) which can be divided into steps as suggested, making the number of steps equivalent to the number of unspecs (and the optimal solution the one with a minimal amount of steps).

Lemma 3: The problem is symmetric in that solving the problem for A -> B immediately solves B -> A.
Proof: Executing the inverse steps for the optimal solution of A -> B in reverse order does not violate any constraints. If the resulting solution for B -> A was not optimal, then A -> B could not have been optimal since the inverse transformation takes the same amount of steps.

Lemma 4: The amount of necessary steps is bounded by N-1.
Proof: Unspeccing the entire tree minus the starting node and then speccing into the new tree takes N-1 unspecs (and according to Lemma 2 equally as many steps).

Lemma 5: The amount of necessary steps is not bounded in any form by the amount of nodes that differ between A and B (it is O(∞) with respect to |A ⊕ B|)
Proof: Consider the following example:
Black nodes represent A ∩ B (nodes that are in both sets), red nodes are A - B (all nodes in A but not B) and green nodes are B - A (all nodes in B but not A). In other words, we start with the graph consisting of red+black nodes and want to get to the graph of green+black nodes. The bottom node is the starting point that cannot be unspecced.
If no extra points are available, it is easy to see that we must always respec k+1 nodes, which can grow arbitrarily large compared to the one pair of nodes that A and B differ by.

---

Ok, that was the easy stuff. Now, as the first precursor to the next proof, here's a slightly more complex version of the previous proof's example: http://i.imgur.com/m5Soi0v.png
Variables next to the lines denote the amount of nodes those lines represent. Like the previous example, this problem can only be solved by completely unspeccing the entire red+black tree and then respeccing into green+black: There are not enough available nodes above the "a" level to connect both the red and green "a" line to the remaining graph at the same time, hence the green "a" line can only be completed if the red "a" line is at least partially unspecced, which requires everything above to also be unspecced. The same applies on the "b" level and the "c" level (with the last being a generalization of the previous example) - which is of course redundant because we have to unspec everything anyway, but it's an important observation with regards to what's to come.

However, we may also be able to use graph nodes that are in neither A nor B to get a better solution. Consider the following example from the real skill tree (viability aside):
Clearly, the optimal respec steps involve allocating two nodes from the Lord of the Dead cluster (above the cursor) after unspeccing the necessary two points from somewhere, then unspeccing the attribute nodes, respeccing them on the other side and then unspeccing the two Lord of the Dead points again to reallocate them where we unspecced them.

I will represent the available graph nodes that belong to neither A nor B as blue lines in my drawings, for example like this:
This is essentially the same example as the one in Lemma 5, however we only need 7 respecs instead of k+3: Unspec the 2 nodes on the right end of the black line, spec into the blue line, unspec the red line, allocate the green line, unspec 2 nodes from the left of the black line (assuming k≥2), connect the right end of the black line, unspec the 2 blue nodes and complete the black line again - conceptually the same as the skill tree example above.

---

Now for the thing that took me a while to figure out (and which I'm still not quiet satisfied with):

Lemma 6: An optimal solution may involve unspeccing the same node more than once (in the sense that a solution that unspecs a node more than once is not necessarily suboptimal).
Proof: Here is an example: http://i.imgur.com/07XYJgz.png
Bear with me as I walk you through it (Note: If you can come up with an easier example than this, please let me know. More importantly, if you are convinced I made a mistake, LET ME KNOW!).
This is conceptually the same as the "ladder" I showed previously. I have labelled the sections A-D and given names to some lines in orange (a, b, c, v, w). Numbers indicate the node counts, with those in parenthesis being irrelevant (but included for the sake of completeness).
Without making use of the blue lines, the best (and only) solution is respeccing the entire thing. And even if you managed to "flip" from red to green lines in the "A" section, everything in "B" above would still need to be respecced just the same (etc.). Hence, using the blue lines at each level is necessary for the optimal solution (and I will show that it is possible to do so, and further show that the optimal way can involve unspeccing some points in line v twice).

Overview:
We must start by "flipping" section A: B cannot be flipped without respeccing everything above (b is only available after flipping A), C's blue line requires 205 points but only 200 are available without disconnecting it from w. Flipping D before anything else is useless because we need those 200 points.
After this, we still cannot flip C, but flipping B gives us 10 extra points to work with that allow flipping C. Those 10 extra point are finally consumed by rebuilding D (flipped). To flip B, we have to unspec v and a that were used for flipping A, but we need v again in combination with c for flipping C in the optimal solution.

Let's start: To flip section A, we unspec the 200 points in section D, as well as 5 points from w (this leaves c ending in nowhere). We build v and a, then unspec the 10000 points on A's red line and allocate them into A's green line. We won't need section a anymore, so we can unspec the 5 points in line a right now.
Quick recap: Section A is flipped, v is allocated (all other blue lines are not), we have 5 spare points, section D is entirely unspecced and w is missing 5 points on the right. We can now look into flipping B using blue line b that became accessible, but we still cannot flip C. Respec points used = 10210

Now we have two choices for acquiring the points needed for b: Unspec 200 more points from w or unspec v.

• If we unspec v (10410 respecs used), we build b and flip section B which gains us 10 extra points (13420). We unspec b (13625) and can now (re)build v+c while putting the 5 points we took away from w back into it. This allows flipping C (14625). We have 5 free points and everything except section D is complete, so we unspec v+c (14830), build D with the 210 points and are done.
• If we instead take 200 points from w's right end (10410), we once again build b, flip section B for a 10 point gain (13420) and unspec b again (13625). w was missing 205 points so we put those back, complete v+c with 5 of the 10 extra points and flip C (14625). Unspec v+c (14830) for 5+205 free points that go into completing D.

Longest proof by example I ever gave, I think. I'm also fairly certain this example is way too complicated (I was originally going for showing that the only optimal solution may require a node to be respecced more than once, but I noticed errors in that while writing it down. Again, let me know if you can come up with an easier or more "powerful" example).

---

Lemma 6 is important because it directly impacts how (optimal) solutions can/must be represented. I would very much like to prove that there are cases where every optimal solution involves respeccing at least one node twice but I couldn't get there yet. It feels like it should just be a small step from what I have...

In particular, this would mean that we cannot represent the step sequence as some (repetition-less) permutation of nodes or assign each node a number/order for when it is respecced. I don't know if any such examples can even come up in the skill tree in practice, but it seems theoretically possible.

[brather1ng]

The first 5 Lemmas look good, I actually put some thoughts into it myself and came up with similar results (though less results, much less in-depth and all in my head). Can't say much about Lemma 6 as I don't have the time at the moment, but I promise to look into it!

One thought on 6: because of the symmetry it would also be sufficient to find an optimal solution for an example that allocates (rather than unspecs) one node twice. Maybe it's easier to come up with examples when thinking that way.

My few thoughts were more focused on the implementation side, so I'll just leave them here: My idea was to basically solve it as a shortest path problem. Take skill tree configurations as the nodes, the initial tree as start node and the goal tree as end node and try to find the shortest path from start to goal using some kind of heuristic. Edges could be steps (unspec and spec, cost 1 for each step) or both unspec and spec (no idea how the cost would be distributed).

Because of the symmetry search tree depth could maybe be halved by starting simultaneously from start and goal and trying to meet in the middle. It might actually not even need a good heuristic to solve medium-sized problems on the skill tree with that.

[MLanghof]

Thanks for sharing your thoughts!

it would also be sufficient to find an optimal solution for an example that allocates (rather than unspecs) one node twice

True, I've so far focused my efforts on having a blue line be unspecced and then allocated again (which is two allocations and two respecs), but finding an example where a green line would be unspecced (or a red line allocated) at any point would also suffice. I'll think about those some more.

My idea was to basically solve it as a shortest path problem.

That's a great representation of the search space, leaving us with 2^K nodes (with K being the number of considered nodes) and at least as many edges (although generally many more - at each step we can unspec any leaf node and respec any adjacent one) if we allow any sequence of unspecs and allocations, or K over N (binomial) nodes if we only allow steps.

There can be a lot of redundancy in the representations (i.e. the order/interleaving of allocations and unspecs is often meaningless, but not always) so eliminating that could significantly cut down on the search space size. It also seems that the really iffy cases (i.e. what I'm trying to come up with in Lemma 6) tend to be highly artificial (consisting solely of long lines and no spare nodes to unspec) which likely won't be applicable in practice.

Another way to think of the problem is "squeezing" a constant volume node "goo" through the graph into a new position (while never disconnecting a part of the goo). I have yet to come up with search terms for literature on this problem though (of which we have a special case because we have at least one fixed node, without which Lemma 4 would not hold).

I'm still trying to get a better understanding of the problem before deciding on the method of choice. I mean, establishing NP-completeness of the problem would be a step I suppose :D

[EmmittJ]

Ok, so I had a look, and I will need sometime on Lemma 6. Lemma 1 through 5 look good.

---

Another point, trees with different starting classes cannot be done.

[MLanghof]

So after some googling (starting from this team puzzle I felt reminded of) I found something related:

https://en.wikipedia.org/wiki/Pebble_motion_problems

The complexity section is interesting, because our pebbles are technically unlabelled and we only seek to minimize the number of moves (up to this point we're in polynomial time) but we have the additional constraint of not losing pebble connectivity (with our moves consequently looking slightly different). I'll keep on digging.

[brather1ng]

Hm, that problem moves pebbles edge by edge, so I think it is pretty different from our problem. But yeah, they seem somewhat related. Maybe "graph relocation" is a term both pebble motion and our problem fit under.

[MLanghof]

Yes, in the pebble motion problem, pebbles only move to adjacent vertices without being concerned about keeping the subgraph connected. I still haven't found anything that matches our problem very well. It doesn't help that graph pebbling is actually a different problem.

A problem field that seems extremely similar to (labelled) pebble motions is the graph relabeling problem, whose general definition fits what we do but the only relevant papers essentially do the above pebble motion (in my understanding).

There are graph grammars but I haven't dived deep enough into that to see if they have had their theory specialized in the direction we are concerned with (I got as far as this). There's also graph edit distances but those seem too far off.

Maybe I should ask on on stackexchange's math site if anybody can figure out keywords to look for (or knows some papers on this)? I mean, I essentially couldn't find the pebble movement problem by googling (only by exploring Wikipedia's graph theory pages) before I knew how it was called...

[brather1ng]

Found some time to look into Lemma 6!

On Lemma 4 and 5:

|A ⊕ B| is a lower bound of the optimal solution, which could be as useful as upper bounds.

The upper bound from Lemma 4 can be improved a bit: Instead of only subtracting the root node (N-1), all nodes that are connected to the root node in the graph with nodes A∩B can be subtracted (deallocate all nodes that are only in A and all nodes that become disconnected by that, allocate all nodes that are only in B and the common nodes previously deallocated).

On Lemma 6:

I think I improved your solution without the need for unspecing a node twice. Your image does not match your numbers (image has 2 for a, c and 202 for b, text has 5 and 205; image has the 1 black node above D) but my solution works for both variants. I did verify my solution twice, but it might still have errors.

(first table is image variant, second is text variant; negative number behind action means deallocation, positive allocation)

action	points availabe	total deallocations
D black -1	1	1
D red -200	201	201
w -1	202	202
v +200	2	202
a +2	0	202
A red -10000	10000	10202
c +2	9998	10202
w +1	9997	10202
C red -1000	10997	11202
A green +5000	5997	11202
b +202	5795	11202
B red -3010	8805	14212
C green +1000	7805	14212
B green +3000	4805	14212
c -2	4807	14214
b -202	5009	14416
A green +5000	9	14416
a -2	11	14418
v -200	211	14618
D green +210	1	14618
D black +1	0	14618

action	points availabe	total deallocations
D red -200	200	200
w -5	205	205
v +200	5	205
a +5	0	205
A red -10000	10000	10205
c +5	9995	10205
w +5	9990	10205
C red -1000	10990	11205
A green +5000	5990	11205
b +205	5785	11205
B red -3010	8795	14215
C green +1000	7795	14215
B green +3000	4795	14215
c -5	4800	14220
b -205	5005	14425
A green +5000	5	14425
a -5	10	14430
v -200	210	14630
D green +210	0	14630

My intuition is that at least the stronger variant of the Lemma (all optimal solutions may involve deallocating twice) doesn't hold, but didn't have the time to even try proving that (by converting a solution with deallocating a node twice to a solution of at least the same value that doesn't deallocate a node twice). Also, skill "trees" are planar except for one violating edge for Ascendants, which might make it easier.

[MLanghof]

Argh, yeah, I messed around with the graphic after realizing a problem while writing but then failed to update it to match the new text. I see though that you made a step that works in both cases that I didn't think of (put points from red A into completing c+w and then flip C early, I mentally treated e.g. red A -> green A as an atomic operation too much), which certainly ruins my example.

[wackygoose]

I was searching for a Respec Calculator and stumbled upon this thread and I'm amazed by how much effort you guys have put into this. Have you given up or made more progress? I didn't understand all but I felt my brain get bigger reading all your elaborations. Cheers

[brather1ng]

As far as I'm aware, there hasn't been any progress. At least I haven't spent time on it.