Dec. 19, 2014
"Forbidden Island" Strategy Optimization
game-related, optimization problem, Monte Carlo simulation
Simulation of the board game Forbidden Island for optimizing strategy. Uses the A* pathfinding algorithm. Represents strategies as priority chains, here is one example: prioritize claiming treasure, then saving critical tiles, then the maximum number of tiles, then important tiles, then inner tiles, then tiles closest to the next claimed treasure temples, then closest to the other player. Card management strategies are similarly represented. Special player abilities are omitted for simplification. Plays hundreds of thousands of random games to evaluate strategy effectiveness Monte Carlo style. Strategy chains could also be expanded to change depending on game condition (water level, tiles sunk, treasures captured). In the future strategies could be evolved with genetic algorithms with the simulation win percentage as the cost function.