July 20, 2015
"Settlers of Catan" Route Optimization
game-related, optimization problem, Monte Carlo simulation, simulated annealing
Performs endless Monte Carlo simulated single-player runs of a specified or randomly generated Settlers of Catan map, sans Development Cards, to determine the most optimal route with simulated annealing. Makes use of all harbors. Every possible state is available to the simulation. For efficiency, resources are gained in proportion to their respective dice probabilities.
Routes are scored by minimal turns to reach the win condition of 20 victory points.
Unfortunately there is no well-defined means to create a "neighbor" for a completed route since every decision is dependent on an earlier one. Since it's not possible to make a small change to the middle of an existing route and retain something valid, I instead choose a random point in the history of a completed route (with a bias toward earlier points) and play out a random game from that point. This becomes a "neighbor" for evaluation via simulated annealing.
The game simulation itself is excellent and comprises the majority of the code, but my optimization technique is not particularly effective. In the future I might loop through all starting locations and obtain an average score for each routing decision as it develops by playing out random games beyond each decision. A combination of Monte Carlo and Hill Climbing. I will then convert it to use Simulated Annealing (i.e. the "best" decision won't always be chosen until it "cools").