Game Theory & Video Games

[Asterisk Propernoun]

I've been looking up math in games lately, and it seems that most mathematicians revolve around board games such as checkers and tic-tac-toe. What about single player video games?

 

Now, I know what you're thinking. "Video games? The game tree would be so big that all of the computers on earth couldn't hold the information!" I'll admit it, you're probably right; but you don't really need every possible scenario to solve a game. For instance, most people know that the quickest route from one point to another is a straight line, so you can easily rule out all of the unnecessary zigzagging, loop-de-loops, and other strange things that might show up in a full game tree.

 

But wait, there's more to it. For instance, how would you even define a 'solved single player game'? Is the perfect play an algorithm that has the greatest probability of being successful (since there's random chance and AI to worry about)? Is it the fastest algorithm? To further confuse the goal, how would you define 'completing' a game? Where the main story ends, sure; but what about things such as side quests, achievements, and making the character you control as powerful as can legally be? There's probably a whole lot of mathematical complications that my young, naive eyes are unable to see, but I think I can provide some examples of what I mean:

 

 

Now this is a game that is probably easier to solve than tic-tac-toe. Although there's no end to it, one can easily make it to where the score would be you: tending towards infinity, and the AI: 0. Though, games such as these are fun in a sense that it takes more skill through practice than strategy and mathematical theory, which makes solving it mathematically pretty pointless. the original Super Mario Bros for the NES and Pac-Man are games that I believe would fall under this category. Although they're probably harder to solve, there's little to no probability, and the goals are clear cut. Let's look at something that would likely be on the level of 'Difficult, yet possible; and therefore interesting.'

 

 

All laughter aside, I believe that solving this game is possible. The primary goal that this game is challenged by is to be comedic. The game play is the game's secondary goal; and is therefore quite linear, but still interesting. As far as the game play goes, it's basically just "Go to this location.", "Here are the enemies that you have to fight. They have this move set, you have this move set, now take turns hitting each other.", "Make a choice that will not effect the story the slightest.", etc. However, there are still problems concerning unclear goals that I have listed above. Do you just want to finish the main story, or all of the side quests as well? Are you going for the bare minimum, or do you want you're character to be as powerful as possible? Do you plan on getting all of the trophies and achievements as well? Speed or certainty? If a mathematician wanted to challenge himself/herself with solving a video game, I would recommend this game to them. Though, I am just a high school math enthusiast... Ah well, it's your choice regardless of what I say.

 

Now let's move on to one of those games that will most likely make a mathematician slam his pen on to the ground and yell "NOPE!"

 

 

This game is called Minecraft. It's basically advanced building blocks. The list on what I think makes this game so difficult to solve goes on and on:

 

Randomly generated terrain. No two maps are alike unless they were to share an identical seed. However, the seeds change after every update, and the maps would only be similar, not identical. Small details such as tree placement and village spawning will still be hard to predict.

 

Updates will make the game evolve faster than any mathematician can work.

 

The maps have no clear end-point. After, say, 30,000,000 meters, the map will start to bug and glitch out, but will continue to generate until eventually crashing the game.

 

Mob (NPC) spawning is next to completely random. There's no telling if there's a hostile mob around a dark corner or not.

 

In the game, you can mine underground to gather ores and other various resources which are also randomly generated. Even more so, to be exact.

 

In this game, your goal is just about as foggy as can be. Are you trying to defeat the Ender Dragon? Discover a really rare biome called a 'mushroom island'? Create a 32-bit computer (yes, this can be done)? Create a house that's identical to the one presented above? There's really no end to what can be done, and its this dynamic game play that makes people so interested in the game. However, I can easily tell that this is a nightmare from a mathematician's perspective.

 

I understand that this is less of an experiment and more of an idea, so please feel free to move this topic if you feel the need to do so. Other than that, I would like to know about your thoughts on this.

[Endy0816]

I've been trying to figure out how to respond. Interesting topic and it does involve one of my favorite games. Minecraft can definitely provide a decent challenge, especially the more interesting Superflat customizations. When the Mobs have been your only source of resources, you look at normal maps in a whole new light.

 

There are pathfinding algorithms. What most of the AI's actions are based on. A route between their current state and their assigned goal. Not sure this exactly counts as part of game theory. The raw power needed to completely solve some of these games would be huge, but can find ideal paths through the problem space.

Edited April 15, 2014 by Endy0816