Zannick
commented
1 year ago It doesn't seem to succeed at this extra greedy search all that often... which may be a result of how the greedy search intentionally chooses to prioritize even distant locations over nearby global actions. And we ditch the whole greedy search if it takes longer than the threshold, even though there's a legitimate obvious speedup.
Perhaps we should always allow the greedy search to finish and add the intermediate states, including the prior states, to the set of states we want to try to add back to the queue. This way we'd have the greedy search "smooth" over the section immediately prior to the initial state, even if greedy search stops being optimal after a few steps.
Due to the randomness of which thread gets which state (plus a lot of the states being less than ideal), the greedy thread can easily succeed with some unusual choices that wouldn't have an effect. On one hand, the purpose of this random element is to get tighter bounds on the max time, but on the other hand, these can stay as the best solution for a long time.
One option would be to run greedy searches from prior to the initial context, i.e. replay up to certain points like Warps, Actions, Locations. If we get a win better than the prompting greedy search, we insert those states similar to how we do for the greedy search now (except we may want to specially exclude states we've seen before at exactly the same time, as they'll likely be real dups).