If both the players want to increase their score (by selecting the highest or best cost path), can this be done using the minimax algorithm, or are there other algorithms for this purpose?


I believe maximax is what you're looking for:

Maximax (economics, computer science, decision theory) A strategy or algorithm that seeks to maximize the maximum possible result (that is, that prefers the alternative with the chance of the best possible outcome, even if its expected outcome and its worst possible outcome are worse than other alternatives); often used attributively, as "maximax strategy", "maximax approach", and so on.
SOURCE: maximax (wiki)

You may also be interested in "minimax regret":

The minimax regret approach is to minimize the worst-case regret. The aim of this is to perform as closely as possible to the optimal course. Since the minimax criterion applied here is to the regret (difference or ratio of the payoffs) rather than to the payoff itself, it is not as pessimistic as the ordinary minimax approach.

One benefit of minimax (as opposed to expected regret) is that it is independent of the probabilities of the various outcomes: thus if regret can be accurately computed, one can reliably use minimax regret. However, probabilities of outcomes are hard to estimate.

This differs from the standard minimax approach in that it uses differences or ratios between outcomes, and thus requires interval or ratio measurements, as well as ordinal measurements (ranking), as in standard minimax.
SOURCE: Minimax regret (wiki)

Apologies for just grabbing the wikis on this, but they are accurate. Most of the references from economic sites are commercial. If interested, when I have some more time, I could probably link to some peer-reviewed papers. Hopefully, at the very least, this answer provides information for further research.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.