Performance improvement qpt.cpp

[Rupsbant]

Notation: au(b,pv) is the antagonistic update of a progress measure b with priority pv. pm(w) is the current progress measure of w and pr(v) is the priority of v.

If I understood the paper by Fearnley et al. then au(b, pv) is monotonic in b. It should follow that max{au(pm(w), pr(v)) | (v,w) in E} is equal to au(max{pm(w) | (v,w) in E}, pr(v)). The same for min. Applying this to the lift function in qpt.cpp should allow to reduce the number of expensive calls to au:

https://github.com/trolando/oink/blob/2d12471feca6b103346749f95af65fb7ff7c186c/src/qpt.cpp#L272-L300

[trolando]

Unfortunately this is not an easy issue to address. I will look at it eventually but it has low priority because I need to study the paper again to resolve this.

[trolando]

@superaxander any comments on this open issue? :)

[superaxander]

Yeah this could work (I did a quick test and it seemed to work on random games, not that that makes me super sure because we've seen 1 in a million bugs before) I would probably combine it with my modification of the update to make it actually monotonic but when testing it seems to work with and without. I still don't have a good idea as to why the if statement that checks if the new measure is actually lower makes the update behave "monotonic enough".