I've got a fairly basic implementation pretty much complete of a Brute Forcer.
As you can see from the times listed, the execution time grows drastically the longer you let the chain possibly be (or more powers). The optimizations Arcanaville mentioned earlier could greatly reduce the runtime for longer chains. For less bang, could also split it over multiple threads which'd be an improvement on dual/quad/etc core machines... but not enough to make longer chains suddenly reasonable.
Sample output:
Code:
The output is fairly confusing, though:Best tree is (in reverse, offset by 1): 122123
DPS 50.140404
Brute Force (6d) completed in 0 seconds
Best tree is (in reverse, offset by 1): 122123
DPS 50.140404
Brute Force (8d) completed in 0 seconds
Best tree is (in reverse, offset by 1): 3121321212
DPS 50.580837
Brute Force (10d) completed in 1 seconds
Best tree is (in reverse, offset by 1): 12123121232
DPS 51.00001
Brute Force (12d) completed in 4 seconds
Best tree is (in reverse, offset by 1): 12123121232
DPS 51.00001
Brute Force (14d) completed in 54 seconds
- The output starts counting powers at 1, instead of 0 like the array used to enter them.
- The output is also in reverse order, you'd execute them in right-to-left order
It's also currently limited to 9 powers (if you have a 10th, it'll screw with the in64 I use to store each path). None of these things would be too hard to fix, though. At this point I'd want to make it work before making it pretty.
Also, 14-deep trees take long enough that the golang website will kill it before it gets that far (it'll print out to 12, though).
Quote:
|
Originally Posted by ShadowNate
;_; ?!?! What the heck is wrong with you, my god, I have never been so confused in my life!
|
Quote:
The optimal attack chain problem can't be solved with linear equations, or any equations for that matter. It has to be discovered through search: given a set of powers P1, P2, P3... look at all possible sequences Pa-Pb-Pc... and find the one with the highest damage within a fixed amount of time. There are ways to reduce the scope of the search that eliminate options that are extremely likely to be bad ones, but it does ultimately come down to searching them all. Given a set of six attacks with an average cast time of 1.5 seconds, there will be 6^10 possible options to look at for a 15 second window, and 6^20 for a 30 second window. That is 3.7 quadrillion different combinations (3.7 x 10^15) for the 30 second case. A brute force search that checks a million combinations per second would take a hundred years to complete.|
Originally Posted by John_Printemps
I do think that we may be looking at the same issue on two different levels of complexity, though. I'm going back to a program code from my C++ courses' second week. Input four equations with different values for all eight integers, solve each, and output the data based on highest to lowest. Albeit this is questioning some additional steps (recharge markers and the like), but I don't see that ultimately taking a .5/s process and making it move up to more than 15-20 seconds, maybe 40 at best, 60 seconds at absolute worst (post timer end, for data compiling).
|
I will note that I believe the optimal attack chain problem to be NP-complete, because it appears to be a variation of the Knapsack Problem. That means as a practical matter there is no solution to the problem of finding the optimal attack chain whose running time doesn't rise more or less exponentially (mathematicians will correctly nit-pick this as only requiring super-polynomial time). If it is essentially a knapsack variation as I suspect (if I'm not writing another searcher, I'm not proving its NP-complete either) brute force search with some heuristic modifications is likely to be the best we can do.
Your algorithm essentially generates a chain based on a heuristic guess: it presumes that heuristic actually generates the optimal chain which it is not guaranteed to do. Heuristic guesses are usually in the ballpark, but are often suboptimal which is why some people have thought about doing it the hard way: actually searching the entire attack chain space for the best of all possible attack chains.
[Guide to Defense] [Scrapper Secondaries Comparison] [Archetype Popularity Analysis]
In one little corner of the universe, there's nothing more irritating than a misfile...
(Please support the best webcomic about a cosmic universal realignment by impaired angelic interference resulting in identity crisis angst. Or I release the pigmy water thieves.)
I did a brute force search of attack chains of 3. More than 3 took too long. Then took the first element and added it to my attack chain, increment time and recharge, repeat until 120 seconds of attack chain executes. There were interesting exceptions generated for more than one set. But in the end, picking the highest DPA attack worked at leas 9 out of 10 times. At which point I decided it wasn't worth coding anything else or even finishing the project.
Quote:
Is it 100% Accurate? No. Do I see it as the most likely answer to a problematic program? Yes. Just looking at Scrapper primaries, the only two sets I don't see this producing a data stream we already know the answer of, is Claws and Dual Blades. Claws may end up with Shock Wave somewhere in there that may devastate it's output, and Dual Blades has secondary effects that someone might want to chase. Knowing that the ultimate answer is unrealistic to expect from a program right now without some serious back sourcing and running power leaves the next best choice the most viable to expect. Every chain that what I'm suggesting may not be the most optimal, but it's often more than the average person can readily figure out on their own, and an even faster option for people looking to try out a new set and want a quick idea of what kind of chain they should be looking into it.|
Originally Posted by Arcanaville
Your algorithm essentially generates a chain based on a heuristic guess: it presumes that heuristic actually generates the optimal chain which it is not guaranteed to do. Heuristic guesses are usually in the ballpark, but are often suboptimal which is why some people have thought about doing it the hard way: actually searching the entire attack chain space for the best of all possible attack chains.
|
Honestly, something simple like this would be a boon to the community, I think, perfect or not. If it was something that could be pre-stored with all the attack sets for each AT so you could just select the set, input a recharge expectation, and see a result? That'd be pretty awesome, optimal or not.
Of course, after years of fiddling with builds and having access to Mid's, I personally can often flip through a set and see the chain in a few seconds, so obviously the easiest way to develop this program is to just hard-wire the interwebz into your brain Arcana, so we can dump these process trees somewhere awesome enough to handle the work load
Quote:
|
Originally Posted by Arcanaville
Warning: crazy space limit reached. Please delete some crazy and try again. |
Quote:
This is what I was thinking of as the third stage of the project. First, just get something that works for the basic case. Then, add in support for damage-enhancing powers (Build Up, Follow Up, Power Siphon, Placate, Fiery Embrace, etc). Third stage, create a database from scratch (unless someone could rip Mids' database into a non-crazily-obscured format) of the powers, with a nice and friendly GUI.|
Originally Posted by John_Printemps
If it was something that could be pre-stored with all the attack sets for each AT so you could just select the set, input a recharge expectation, and see a result? That'd be pretty awesome, optimal or not.
|
My current implementation has a lot of room for enhancements (split over multiple threads, optimize the recursive function/the path DPS calculator, use some sort of heuristics, stop it from executing the same path multiple times, etc), I'm hoping I can get it to support a reasonably large number of powers, with a reasonably long chain (say, 6 powers, at least 10 long) without taking all night.
Quote:
|
Originally Posted by ShadowNate
;_; ?!?! What the heck is wrong with you, my god, I have never been so confused in my life!
|
Very nice.
I did basically the same thing in Excel when I was analyzing my Kinetic Melee build, but this is much cleaner.