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:

oink/src/qpt.cpp

Lines 272 to 300 in 2d12471

	for (int to : out[v]) {
	if (disabled[to]) continue;
	au(tmp, pm_nodes + k*to, pr, k, max, maxo, pl);
	if (pm_val(tmp, k, pl) > goal) tmp[0] = max; // goal reached, lift to Top
	#ifndef NDEBUG
	if (trace >= 2) {
	logger << "to successor " << label_vertex(to) << ":";
	pm_stream(logger, tmp, k);
	logger << std::endl;
	}
	#endif
	if (first) {
	first = false;
	for (int i=0; i<k; i++) res[i] = tmp[i];
	strategy[v] = to;
	} else if (owner[v] == pl) {
	// we want the max
	if (pm_less(res, tmp, k, pl)) {
	for (int i=0; i<k; i++) res[i] = tmp[i];
	strategy[v] = to;
	}
	} else {
	// we want the min
	if (pm_less(tmp, res, k, pl)) {
	for (int i=0; i<k; i++) res[i] = tmp[i];
	strategy[v] = to;
	}
	}
	}

[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".