Exploration and Exploitation: a direct tradeoff

You're playing Skyrim and you need to defeat all the computer enemies without dying. If you're playing "hard" mode, obviously, you can't just run at them and slash or shoot the enemies down like some superhero. You need to learn strategy that kills all the enemies in a calculated manner. Of course, when you first try the game, you might just die immediately, because your running path was terrible. You'll probably find some strategy to defeat the enemies easily each time eventually. Perhaps the mage charges right at you if you stand behind a pillar. You can then just cut him down when you're nearby. Using that strategy, you can kill the enemies each time you play, because the computer opponents never adapt.

What if you had a time limit or a death count on the game? You would need to learn the best strategy in the quickest time. However, the more you search and test that strategy the more you die. On the other hand, the more you search the better chance you find the best strategy which reaps the maximum reward with minimum risk. This is the basic premise of the Multi-armed bandit problem.

Slots (Source: Wikimedia Commons)

In the problem, a gambler is presented with an array of slot machines. Each slot machine yields a different reward at different chances. Not knowing which is which, the gambler much choose which slots to try and execute while maximizing profit.

Games today aren't so simple in presenting the exploration and exploitation tradeoff. Most games change scenarios often so you can't really exploit the same strategy over and over again, because the game changes levels. However, many games award the player for "exploring" more. A classic example is the super Mario brothers underground level. If the player explores the level and breaks the brick "ceiling", he can actually run on the ceiling through the level without meeting any hazards. To reward the player even more, the player is given the option to skip further levels if he runs across the ceiling.

The exploration and exploration tradeoffs can be tough decisions for game makers. If it is too easy to exploit the game, the player might get bored. There is also the question of how to reward the player for exploring and exploiting strategies. A big problem with many of the realistic games today like GTA, Call of duty, skyrim, Modern warfare, etc. is that their artificial intelligence systems always perform the same action and never adapt. It is too easy for the player to find a loophole and easily defeat the enemies.

How do you think a player should be awarded for exploring and exploiting strategies in games? How will the development of game artificial intelligence effect the tradeoff? Post your comments below.

I was inspired by this video to make this blog post. The maker discusses exploration and exploitation in the making of a skyrim ai mod.