Wednesday, April 19, 2017

Outside of games or even product development, there's a broad problem called global optimization in which you are trying to find the maximum of a function in some space. If we think about a “space” of all possible game designs, then we're trying to find good places in that space. Hill climbing is the simplest approach to function optimization — in each iteration you make a step to improve. The problem with hill climbing is that you run into “local maxima” — you are at the top of your little hill but there's somewhere far away in game design space that's even better. You can't see that far away so you never find those other game designs. Metaheuristics are different approaches to dealing with this for function optimization; some of these ideas also seem to apply to game development:

  • Simulated annealing says: start with big steps early on, make smaller steps later on. This already happens with many games, with early development making larger changes and post-launch being smaller changes.
  • Swarm optimization says: explore multiple places at once. Early on, you can prototype many different related games, and then see what works well and what works poorly. Later in development it's impractical to build many different games but you can explore small variants with A/B tests.
  • Genetic algorithms says: explore lots of places at once, randomly mutate them, and make copies of the best solutions. This seems like what the modding community provides. Let them explore many alternative sets of game rules, and then incorporate the best features into other mods or into the base game.
  • Variable neighborhood search says: alternate between making small changes for a while and then making a few big changes every once in a while. This could mean periodic patches and also bigger changes in the form of expansion packs.
  • Graduated optimization says: first optimize a simpler problem, then use the solution to simpler problems as a starting point for exploring a more complex problem. This happens in games that start small and grow more complex over time.

Are there other techniques you use to avoid your game design getting "stuck" in a local maximum?

Labels: