Maximizing my take from this MMORPG monster (probability problem)

There’s an MMORPG I play that has a little mini-game inside it that gives variable amounts of game currency to the players who happen to find it while it’s active. I’m trying to maximize my take from the game’s “purse” over many plays of this mini-game.

A competent player of this game can pretty much choose the game’s outcome and decide how much she’s going to take from the purse during a given session. And if there’s anything left in the purse, go right back again and keep playing until the game says “OK, you’ve taken enough, I’m shutting down now.”

For competent players, the game effectively works like this:

Game: “I had X number of coins to give away when I last spawned. Out of which I have Y left now. I’ll tell you X, but I won’t tell you Y. Other players might have been here before you and taken some of it. Now, how many would you like to take?”

During a single play of the game a competent player can choose to take any number of coins up to that X number. Not Y. The game will happily give out the player’s choice (really it’s a function of how well they played it and what score they got but competent players can spin any score they want) up to X, and then at the end of the session it will subtract what the player won from its current hidden Y value. If there’s anything left, it will stay active and let the player play again. If that last play drew it out to zero or below, the game shuts off until it respawns some random time later with another full purse.

Most competent players will sit there and draw as much as they can until the game shuts down. But not all. Players who aren’t so competent might draw some, and leave some left in the purse for another player to try when they come by later.

If I found the game right after it respawned, I know Y = X and the winningest strategy is obvious: On the first play, take x-1 coins. On the second play, Take the full X. I just won 2x-1 coins.

But… sometimes I don’t find it right after it respawned. Y has been depleted by some unknown amount. Maybe I was the first to find it, maybe not. What’s the best choice for my first play, knowing that if I take too much, I won’t get that second play this time?

The answer to this question depends on the population of other players, in a way that can’t be determined from what we know. You could, by experiment, just try different values and see what works best, but that would probably take a long time. Alternately, if this is like most MMORPGs, someone else out there has probably already collected the data, and you can find it by just searching for the name of the game and the monster.

Something like a binary search might work well. You take 1 coin, then 2, then 4, etc. If the pot is a power of two, then you get the optimal result. Suppose the pot is 1024: you get 1023 coins from the first 10 plays, and then 1024 coins on the last play. If the pot is just under a power of two, you get get only the amount in the pot. In-between values give varying optimality.

There are better strategies if you know the expected distribution of values, but this is a fairly good general purpose one. I would say that if you know the maximum pot, then tweak some of the steps to take that into account. For instance, if the pot is 1000 coins, then the 10th play should take 489 coins, not 512.