breakds
Search through all possible charms
Currently to do any kind of search involving charms/talismans, we have to add the ones we want to check by hand. It'd be great if there was an option that assumed we have access to every charm in the game to see what charms would be needed to reach certain skills.
From reading the blog, I'm not sure how well that would scale considering the number of charms in the game, would probably have to tweak the existing algorithm.
Exactly. The algorithm won't work with it and, it is not designed to work with it. The reason is that, the algorithm is supposed to solve a constraint problem, and is destined to perform badly when there is no strong constraint. It is harder for the users to find what they want from a enormous result list full of charms they do not currently have either, which is what we can expect when all possible charms are allowed.
Instead, what I am thinking is porting this to Android/iOS, so that the camera can do us the favor: use the camera to scan the 3DS screen, and OCRs a list of amulet that are obtained :)
It is harder for the users to find what they want from a enormous result list full of charms they do not currently have either, which is what we can expect when all possible charms are allowed.
Right, but at the same time we often want to know if the desired skill combination is possible if we allow for any legitimately obtainable charm. There are techniques which allow charm sniping.
Well, it's not a huge problem as long as we can import charm lists.
Instead, what I am thinking is porting this to Android/iOS, so that the camera can do us the favor: use the camera to scan the 3DS screen, and OCRs a list of amulet that are obtained :)
I wonder how viable this is, sounds difficult: OCR is hard, OCR from a shitty phone camera even more :). Also I usually have 60-80 pages of charms, I can imagine it getting very tedious to scan all these. Either way I don't own Android/iOS so I'd hate to see this as a primary/only method.
I'd like to think there is hope here still: we could start by only searching optimal-in-category charms: if the user is looking for honed blade and attack up, only check a edgemaster +4 attack +14 OOO charm. We could stop there and just tell the user it's possible with such a charm but we probably want to do better. I try to describe the general idea a bit later.
I think in general it would look like: given n user skills, generate the optimal possible charms for each combination. n is usually small, up to 8 in obscene cases but often more like 4 or 5. That's not a large number of charms by any means (like n^2 if we properly disallow pairs of same skill and account for single skill charms). Perform search as usual using all these charms as charm list. We now have results with best possible charm associated to them. For each result, systematically find if the same type of talisman but with fewer slots and skill points works. Once found, this gear along with the worst charm that still works gets added to the final result set.
It seems that in reality we only need to add one thing: mapping a function over the result list that will downgrade the charm as much as possible. This downgrade is not even that expensive. There are two cases: we are either downgrading the points or the slots.
If we're downgrading points on the charm, the job is simple: simply look at the amount of points the set already gives with the current charm and subtract the excess. If the set has +12 edgemaster and we know that only 10 points are needed for the skill to activate, we simple take off 2 points from the edgemaster skill on the charm.
The case for reducing slots is similar: if the slot is empty then trivially remove it. If the slot is not empty but for whatever reason the set still works with the gem removed then trivially remove it (though such a gem would seem like a bug anyway). Another way to put this check is to just remove all gems from the charm, remove 1 slot and attempt to re-gem it in such a way that we recover the skills.
These two downgrade options raise a small question: is attack +2 preferable over attack +1 O--? It could be solved be either displaying all such combinations or simply by allowing the user to specify whether they prefer to reduce points or slots.
In conclusion, new steps are generating the optimal charm list and performing a search and then mapping the charm downgrader on each of the results which should not be too much further overhead.
What do you think? It does not alter the search algorithm. It actually runs with much fewer charms than a charm list user might provide (I think it's 10 charms per page and usually people have about 50-90 pages…) and then we simply apply the transformation on each result which seems quite cheap.
Of course I just came up with the above on the spot, it's not meant to serve as some design document or whatever. I haven't deeply considered it but just aim to demonstrate that it could be viable. Feel free to poke holes in it :)
Thanks for detailing the algorithm. I like your downgrading idea very much! I found myself doing the similar thing, try to poke around to see whether I can "still get some search result" by replacing the amulet with some more "accessible" ones. This kind of functionality should be useful.
So here is what I am thinking: Unless Capcom re-design the amulet/charm system, a charm will have
- contribution to up to two skills
- slots from 0 to 3
This makes the search space very limited and we can do something even better than downgrading the search results.
Let's say we want Skill A, B, C, D. Before starting search, let's restrict the charms:
- we have only one charm
- it has no slots
- it contributes to C and D, but we do not know the point.
So basically this is a "template charm", where we can put whatever points we want on it. A "blank check".
Then we start the search. We first construct the forest that satisfies A, then filter it to get forest that satisfies B. And we stop here!
Now we can evaluate for every tree, what are the points to put into the charm (for C and D) to achieve our criteria. We will get a lot of pairs of (c, d). Plot those 2-D points on a coordinate and the convex hull gives the set of all "worst charms that can still be used to support at least one such armor set".
And we can have other template amulet as well. In fact there are
4 slots * C(4, 2) = 24 different template charms.
Clearly this would be slower than normal search. But it might be worth waiting that time as well :)
It's just some preliminary thinking on this problem. I think it is roughly 24 x times slower than the normal search, but in reality it can be faster (or dramatically slower, which I don't want to believe ~).