Return to “Technical”

Post

Opportunity Cost

#1
I just read the latest dev logs about the value of time. I wonder if you're familiar with the economics concept of opportunity cost?

It allows you to calculate the cost of something relative to your other choices rather than in absolute terms.

The opportunity cost of singing to you for a whole day is missing my day at work where I'm worth $100/hr (undervalued if you ask me ;)). The opportunity cost of singing to you for a minute instead of sitting on the couch is the value of the rest I'd receive by sitting on the couch (difficult to value, but AIs don't need rest). I think this is basically the realization you had on your trip w/o using the term "opportunity cost".

If I'm an AI sitting next to an asteroid in space the opportunity cost of mining the asteroid is stuff like "I can't start putting over to that asteroid over there to mine it" which is less valuable than mining the one right in front of me (unless that asteroid over there has a more important asset, or is more dense or something). It seems to me that it should be possible to assign a value/tick to the available choices in front of the AI and choose the most valuable one. The key is making sure the value is distributed among subtasks properly. Say you can sell a cargo hold full of minerals for 100 credits. If you're docked at the station w/ a cargo hold full of minerals the value/tick of selling them is 100/tick (assuming it's instant of course). If you're sitting at the station with an empty hold and there are a bunch of asteroids outside and it would take 100 ticks to fill your hold and return the value/tick of leaving the station and embarking for one of the asteroids is 1/tick. If you're sitting next to an asteroid w/ a half-full cargo hold and it would take 20 ticks to get back to the station, or 10 ticks to fill your hold and you have two choices, return now and sell or continue mining. The value/tick of continuing to mine until full and returning is 100/(10+20)=3.33. The value/tick of returning immediately is 50/20=2.5. So the AI decides to fill up first essentially figuring as long as I'm out here I might as well top it off. This would scale pretty well for the long term too. Say there's a more expensive ship available at the station for 10000 credits that travels at the same speed but can haul 500 credits worth of minerals the value/tick as you work up to that ship is actually more than the credits you're receiving from the minerals. Every mining trip becomes a subtask of earning that bigger ship. This technique lets you reconsider your choices every tick and still be pulled towards the one you've mostly completed unless something even better comes along.

This can clearly be taken to many levels of reasoning that would make it rather intractable (what if somebody buys the ship before I get to it, maybe I should go scout for more valuable opportunities), but if you just pick a level of reasoning I think it would work.

http://en.wikipedia.org/wiki/Opportunity_cost
Post

Re: Opportunity Cost

#2
negascout wrote: If you're sitting next to an asteroid w/ a half-full cargo hold and it would take 20 ticks to get back to the station, or 10 ticks to fill your hold and you have two choices, return now and sell or continue mining. The value/tick of continuing to mine until full and returning is 100/(10+20)=3.33. The value/tick of returning immediately is 50/20=2.5. So the AI decides to fill up first essentially figuring as long as I'm out here I might as well top it off. This would scale pretty well for the long term too.
I'm not sure, this part seems illogical. What if instead of 10 ticks, it took 40 ticks to fill up the remainder of the hold? Then the value/tick factor of continuing to mine until full and returning would be 100/(40+20) = 1.67. The value of returning with a half-full load would remain at 2.5, and using your system, the AI would prefer to return with a half-full load than fill its load before returning. It would be better for a miner to consistently fill up on as much ore as possible before returning to sell it.

Let's explore the general case. Assume it took X ticks to travel from the asteroid to the station, it took Y ticks to fill the hold from empty, and the total value of a full hold of the ore was Z. According to your system, the AI would employ a greedy algorithm of choosing at each tick whichever action maximised the value/tick ratio.

Assume Z is a real value > 0; X, Y are integers >= 1; and time starts from when it's by the asteroid and about to begin mining.

At t=0:
V(mine + return) = Z/(X + Y)
V(return) = 0

Z / (X + Y) > 0
=> V(mine + return) > V(return)
=> mining will commence.

However, after this point, for the AI to continue mining:
V(mine + return) > V(return)
=> Z / (X + Y - t) > t*(Z/Y) / X
=> Z*X / (X + Y - t) > t*Z/Y
=> X / (X + Y - t) > t/Y
=> X*Y / (X + Y - t) > t

where 0 <= t <= Y

I.e. the AI will only continue to mine for values of X, Y, Z and t that satisfy this inequality. Notice also that the value of the ore is completely irrelevant in this calculation.

(It's fun playing around with this inequality. Setting t=0, it becomes X*Y / (X + Y) > 0. This inequality is satisfied by any positive real values of X and Y, so the miner will always choose to mine when he's by the asteroid initially. Setting t=Y, it becomes Y > Y => 1 > 1, which is never satisfied due to the irreflexiveness of ">". So the miner will always choose to return when its cargo is full).

Let's test it. In your example, X = 20, Y=20 (because it takes 10 ticks to fill your hold when it's half-full), Z=100, t=10:

X*Y / (X + Y - t) = 20*20 / (20 + 20 - 10) = 400 / 30 = 13.3, 13.3 > 10 so the inequality is satisfied and the AI mines.

With my example: X = 20, Y = 80, Z = 100, t = 40:

X*Y / (X + Y - t) = 20*80 / (20 + 80 - 40) = 1600 / 60 = 26.7, 26.7 < 40 so the inequality is unsatisfied and the AI returns.

Ideally, the AI shouldn't be flipping its mind halfway through mining I believe. You'd want it to mine all the way before returning.

Bonus: I wrote a Python script to evaluate this behaviour. http://pastebin.com/vzX7UhL3
Last edited by ThymineC on Fri Nov 22, 2013 9:44 pm, edited 1 time in total.
Post

Re: Opportunity Cost

#3
That's true if the AI only looks at the current task and one transaction ahead, but there would need to be a hierarchy of tasks to calculate the true value/ticks over a longer term. The example I gave was a simplification of that. Figuring out where to draw the line and actually assign a value is a bit tricky, but the trick might be to start with high level goals and break those into sub goals as I think Josh's AI already does. A single mining trip would be far down the hierarchy and the value/tick calculations would be taking in to account future transactions leading up to a bigger goal.

Awesome analysis though :)

Online Now

Users browsing this forum: No registered users and 9 guests

cron