Optimize a simple trading problem

Question

I am developing a simple resource trading game set in space for fun. The board is a two dimensional representation of a solar system (roughly similar to this image).

The game mechanics are as follows:

• Planets orbit a sun at different speeds (meaning the distance between them changes with time).
• There is a limited number of resources being traded in the universe.
• Planets either offer a resource for sale or have a demand for it.
• You can travel between planets.
• The price for travelling is linearly related to the euclidian distance between the planets the player is travelling between.
• Not travelling incurs a fee per time unit.
• Resources can be bought from planets if there is an offering or sold is there is demand.
• Resources sold are not fed back (i.e. resources are consumed over time).
• The player can choose to end the game at any time. The amount of currency held when ending the game constitutes the final score.

I am now searching for an approach to identify a program that maximises the final score. I have a vague idea of how to solve a relaxed problem, where there is no movement of planets, but I am stuck figuring out how to go about programatically determining the optimum score.

Maybe someone can point me in the direction of an algorithm or research in the area?

Answer 1

Based on comments above, I'm going to assume a turn-based game with every planet reachable from every other planet in a single turn. I'm also going to assume a fixed game length (number of turns), at the end of which you're looking to maximize the wealth/capital of the ship owner. The fixed game length can be finessed a bit by setting an upper limit on the number of turns and then, if the game ends before then (for instance, because the ship owner runs out of money), you basically just park the ship and wait for the remaining turns to expire. I'm also going to assume that you can only change planets once per turn.

Cargo purchases and sales may be divisible quantities (any value in some interval), but the decision in each turn where to go next is inherently discrete. There are several ways the game could be modeled.

• Dynamic programming (DP) (https://en.wikipedia.org/wiki/Dynamic_programming): You would model the state of the game as the turn number, the planet you're on at the end of that turn (before lifting off for your next destination), your cash wealth and your current cargo (immediately before liftoff). Throw in fuel if you want. This will only work if cargo volumes (and fuel, if included) are limited to discrete amounts. Picture a directed graph with a node for each possible state, and an arc from each node to each attainable node in the following turn. You're looking for a path from the start node to the best possible end node. The good news: You don't really need specialized software for this if you have reasonable programming chops. The bad news: The size of that graph tends to explode exponentially with the number of turns and number of possible cash/cargo/fuel levels.
• Constraint programming (CP) (https://en.wikipedia.org/wiki/Constraint_programming): You would write a model in a domain specific language. The model would contain variables representing location, cash, cargo and maybe fuel, indexed by turn number. You would also code assorted constraints (budget, trading limits, ...). Feed the model to a solver program or library and hope it doesn't take too long to solve. The good news: There are both open-source and commercial software options. The bad news: You'll need to learn a DSL and the UI/commands of some solver. There are some pretty good free online courses on CP if you're willing to commit the time to learn it.
• Integer programming (IP) (https://en.wikipedia.org/wiki/Integer_programming): You write a mathematical model in which there are variables similar to those described above, equations and inequalities constraining the values of those variables (where you go next, budgets, cargo sales/purchases/trades, ...) and an objective function (presumably wealth) to be maximized. Again, variables are indexed by turn. Hopefully everything is linear; otherwise the model becomes intractable quickly. The conversion from English-language description to mathematical model in IP may be a bit less obvious than in CP. For instance, if the planets are numbered $1,\dots,N$, in CP you can just say $x_i\in \{1,\dots,N\}$ is my location at the end of turn $i$, whereas in IP you would probably need something like a doubly-indexed binary variable $x_{ij}\in \{0,1\}$ indicating whether or not you are on planet $j$ at the end of turn $i$. Once again, you code in either a DSL or (if you're writing a program in some general purpose programming language) in your language of choice using the API for some solver library, feed the problem to the solver, and hope for the best. As with CP, there are plenty of good software options, both open-source and commercial (with the commercial software generally being faster/higher capacity than the open-source software), and there are MOOCs where you can learn the basics. So the good and bad news is largely the same as for CP. One other difference: whereas CP wants integer variables (including cargo quantities, cash reserves etc.), IP is happy with continuous variables.

Personally, I would go with IP if everything is linear and CP if there are any serious nonlinearities but all quantities are discrete.