Back to the Math and Logic page

 

Games and Levels of Complexity

UNDER CONSTRUCTION

Consider the following list of single-player games:

These games have three things in common. First of all, they're all equivalent. If you find an extremely efficient method of tackling one of them you have a method which can solve all of them. Secondly, they're all known to be extremely hard. There is no known way to solve any one of these problems which is any better than brute force, or simply considering every possibility. And thirdly, if you can come up with an efficient way to perfectly play any of these games, or even prove there is no efficient method, you'll be a millionaire overnight.

Actually, all of the above games have another thing in common, but lists of three things just sound better for some reason. Each of these games has the property that if you do come up with a solution, you can check it extremely easily. In a Sudoku game, which is a specialized type of crossword puzzle with numbers, you're looking for a solution which fills in all the squares without breaking any of the rules. You can look at a sample solution and know if it's right really easily enough, you just can't find that solution without trying a lot of combinations. The same holds true for freecell or any of the other games-if someone shows you the right answer you can easily tell it's correct, but finding that answer may take a lot of work.

Now, there's a couple things I should clarify before everyone is leaping down my throat to claim a million dollar prize. These problems are only considered to be sufficiently hard when they're stated in a very general form. You may be able to solve every game of minesweeper in a five by five board, but the problem is to create an efficient technique of solving the game that will work in every case, even if you're working on a board that has a million squares on both sides and close to that many mines. The second constraint is that for some of these problems, only certain parts are considered to be "hard." Sliding tile puzzles can be solved fairly quickly under normal circumstances, but finding how to solve it in the shortest number of steps is an extremely hard problem. Similarly, the tricky part to Mastermind isn't just getting lucky and "guessing" the solution but being able to figure out a valid guess from a list of guesses made so far.

These problems all also have a name. NP-complete. The "NP" part means that there is an easy way to check a solution for them (or in "Nondeterministic Polynomial time if you speak math), and the "complete" part means that they're the hardest problems known in this particular class. While I'm at it, I'll throw a few more equivalent problems at you in case you want to keep trying your luck.

  • The Traveling Salesman Problem-Finding the most efficient way to travel between every city on a map while spending the least overall travelling time.
  • Various Scheduling Problems- such as assigning a list of students to a given set of rooms, given that there are certain pairs of students who refuse to work together. Or, scheduling a series of events between people with various gaps in their schedule that might conflict. Both of these problems are easy to check when you find a solution, but very hard to find a solution for in general.

The reason there's a million dollar prize for being able to solve any of these problems is because people have known about them for over thirty years and no one's been able to come up with an easy way to solve them, or even demonstrate that there is no simple solution. Solving any one of these problems efficiently would radically change telecommunications, circuit design, and a huge number of practical problems which people in industry have to work around. The entire field of computer security, for example, is based on the premise that these problems have no simple solution. If they do have an efficient solution, that means that all the encryption algorithms in widespread use can be broken with very little effort. The general assumption is that all these problems must be hard to solve, since we haven't found a more effective technique than a brute force search over all possibilities. We'd just like to know for sure.

As we saw in the language example, trying all possibilities increases in size very quickly--to the point where we may never have enough time or resources to solve some of these problems in a very complex case. This is the guiding assumption behind computer security--the fact that you can protect your data in such a way that it can't be unlocked without a huge amount of effort--but it also is the reason why all of the above games are fun for people to play. If any of these games had a simple solution, or some formula or technique you could apply to solve them in every case, they wouldn't be nearly as much fun for people to play.

Tic-Tac-Toe becomes kind of a boring game once your age reaches double digits, just because the strategy becomes so elementary--there are only a few rules you need to know to avoid losing, and there's no point to playing a game which both players can figure out perfectly. Games like Sudoku are popular just because they have no simple solution, and they force you to explore more combinations than you can possibly consider at once, trying to find a clever strategy to cut down on all that complexity. The games that remain popular are the ones that no one has managed to figure out--after all, if you have a game completely figured out, you should know what the outcome will be before you even begin.

Two Player Games with limited moves

As you might have noticed, all of the above games considered are single player. They basically consist of a puzzle you have to solve on your own, and if you find a way to solve it you'll know you have the solution. You're essentially looking for some set of values, whether that's moves on a board or assignments of some variables, which will "solve" the puzzle.

There's another class of problems which is known to be at least as difficult as the previous group; it can basically be described as two player games with no randomness and with a limited number of moves. For a two player game, you're just not looking for a solution to a puzzle-you're looking for a winning move, no matter what your opponent does. You have to make the best possible move at each point such that no matter what your opponent does you still have a way to win. Once again, there's no known way to solve this problem except by brute force, so you have to consider all the moves you could make, all the moves your opponent could make in response, all the moves you could make after that, and so on.

There are basically three possibilities for a two player game that doesn't involve random chance--either the first player can always win, the second player can always win, or it'll end up being a draw if both players play perfectly.

Some examples of the hardest problems in this class:

Well, all right, maybe there aren't that many examples. The problem with coming up for problems in this class is that the game has to be hard enough so that there's no winning strategy that's easy to find, but there also has to be a limited number of moves you can make--and most popular board games don't fall under that last rule. Some do, like Connect Four, which has a limited number of moves before the game ends, but Connect Four can actually be solved without too much effort. If you play with perfect strategy on a normal board the first player can always win, and the problem has been solved for different board sizes as well.

Now, since this class of problems is at least as hard as the single player games we looked at earlier, if you can come up with an easy solution for anything in this class you'll have solved all the other ones as well. And if you can prove that there is no easy solution you won't be made a millionaire, but the math geeks of the world will love you for it and you'll have your name in every textbook from now until the collapse of human civilization, next to Euclid, Pythagoras, and more people you don't care about.

Two Player Games with no limit on the number of moves

For a problem in the previous class, the amount of time it takes to compute an answer is incredibly huge, but you can finish eventually because there are only so many positions to consider. For a problem in this class, not only would you need to run forever but you'd need more computational resources than you could ever have.

In order to complete solve a game like Chess or Go, you have to have a computer consider every possible position and whether or not it leads to winning or losing the game depending upon what moves you make. Now, Chess has roughly 10^50 possible positions. The game of Go has 10^170 possible positions. Once again, that latter number is more than the number of atoms in the universe, so it's hard to imagine you could ever come up with a computer that could ever even store the information neccessary, if you consider that every bit in the circuit has to be at least one atom in size. Essentially, for a computer to solve problems of this complexity they would have to represent information more efficiently than the universe itself.

Computers do well at Chess because they can calculate millions upon millions of moves a second. Good enough to beat most of us, but geniuses like Gary Kasparov can pull off a draw or even a win now and then. Chess has more possibilities than a computer could ever find, but it can search through enough possible moves to have a good chance.

As for Go on the other hand, if you can come up with a program capable of beating a decent tournament player, you'll win a cool 1.6 million. Despite the fact that the number of possibilities in the game are far too many to consider, humans have a far better grasp of intuitive strategy and finding patterns than computers do.

 

 

email me

#top