← back to the archiveCover illustration for “The best move changes when the opponent model changes”
LINKday 104·2d ago·by Andy Padia

The best move changes when the opponent model changes

Expectimax and minimax can prefer different actions in the same game. The assumption about the other player belongs in the design review before search optimisation.

Stanford CS221https://web.stanford.edu/class/archive/cs/cs221/cs221.1186/lectures/games1-6pp.pdf

TL;DR: A search algorithm can be correct and still optimise for the wrong opponent. State the behaviour you assume before arguing about the best move.

Dorsa Sadigh's Spring 2018 Stanford CS221 Games I slides open with a small game: one player chooses a bin, and another chooses a number from it. The preferred bin changes depending on whether the second player cooperates, acts randomly or tries to minimise the first player's payoff.

The lecture develops that distinction through expectimax and minimax. Expectimax optimises expected utility against a specified opponent policy. Minimax guards against an opponent choosing the worst available outcome for you within the model. These are different objectives, rather than two interchangeable ways to make a search faster.

Here is my own smaller illustration. Option A allows outcomes of 2 or 12; option B allows 5 either way. If A's two outcomes are equally likely, its expected value is 7, so A beats B's 5. If the other player deliberately selects your lower outcome, A gives 2 and B gives 5. The preferred option flips without changing any available action.

I would put this assumption near the top of a design review for an automated decision system. Describe which events are treated as random, which actors may respond strategically and what evidence supports those choices. More search depth cannot repair an objective built around a friendly opponent who does not exist.

The practical exercise is to run the same tiny decision under two plausible behaviour models and inspect whether the recommendation changes. If it does, the uncertainty about behaviour deserves attention before the implementation is tuned.

I checked the lecture's definitions and opening example; the two-option calculation above is illustrative. The lesson does not validate the acquisition story wrapped around the social repost, and a real commercial interaction need not be a two-player zero-sum game.

Review the opponent you model before trusting the move your algorithm recommends.

#weekly-shares#read#game-theory#ai
← older drop
Open the startup archive at the decision you face
newer drop →
Put an audience decision between the YouTube prompts

related drops

explore all 329 drops →
← back to the archiveday 106