Random numbers aren't random

In a previous post, I mentioned that you can add the appearance of intelligence to a game playing script by throwing in a random component. While the computer can always win tic-tac-toe by playing the same sequence of moves, it looks much less boring if the computer picks different winning moves in each game.

Following up on this, I got a special request to explain how random number generators work. I happen to know that the person who asked for this information is sort of a logical determinist, so she'll be delighted to hear that random numbers are not random at all, but generated by a very specific script.

When we think about random numbers, what we generally want is an unpredictable number in a range, with 0 or 1 at the low end, and some number "m" at the high end. How big m is depends on the application. For instance, to simulate a die roll, we want a random number from 1 to 6. To simulate drawing a card, we need a number from 1 to 52. For a roulette wheel, 1 to 38. For a game with two dice, like monopoly, we need to generate two random numbers and add them together. The rules for a role-playing game such as Dungeons & Dragons will often instruct you to roll 1d20 (roll a 20 sided die, i.e., generate a random from 1-20) or 3d4 (roll three four sided dice) to determine a monster's health, or whether they hit you on a particular round. Games like World of Warcraft have borrowed heavily from tabletop gaming rules in order to come up with event odds in the range that make sense for the game balance.

It's hard to generate a truly random number, since computer programs are fundamentally deterministic in the way they follow algorithms. So they do something slightly easier. Once we have one random number (or pseudo-random), we generate a sequence of randoms after that, where each one is based on the number before it.

There are many functions which can generate this sequence; one common example is this:

• X_n+1 = (a*X_n+b) mod m
  

In this case, a and b are constants that you can pick, often large prime numbers. "m" is a maximum value for the resulting number.

Let's try a few examples. I'll pick arbitrary values a=107, b = 23, and m=101.

• 1 (This comes before the first number. It's called the "seed," as it helps to determine which numbers will come up in the pattern.)
  
• 107*1+23 = 130; 130 % 101 = 29
• 107*29+23 = 3126; 3126 % 101 = 96
• 107*96+23 = 10295; 10295 % 101 = 94
• 107*94+23 = 10081; 10081 % 101 = 82
• 107*82+23 = 8797; 8797 % 101 = 10
• 107*10+23 = 1093; 1093 % 101 = 83

As you can see, this function produces a string of seemingly unconnected numbers from 0 to 100. However, they aren't unpredictable. If you know the formula, and the current number is 29, then you know the next number is always going to be 96.

Because of this, you wouldn't want to use 101 as your "m" value, if you were actually looking for a random number in the range of 0 to 100. You could always predict the next number in the sequence. If you're a company that writes video poker machines, and your random number generator is easy to reverse engineer in this way, you'd be in very big trouble.

So instead, you'd make all your constants, m, a, and b, much larger. Then you'd take the resulting random numbers and mod them by a smaller number to get program data, but you'd still retain the larger number to generate the sequence. That way, if people see the number "3", they have no way of knowing that the real number in your random sequence was generated by 5,495,110 mod 6 plus one, and therefore they can't deduce what the next number is going to be, even if they know the algorithm.

So the random sequence is masked from the program's end user by not telling them what the formula is. Nevertheless, a random number generator is still predictable based on the seed. If you start with a fixed seed number of 1, and you get the sequence of die rolls 4, 2, 6, 1, 3, then you will always get the same sequence after you shut down the program and restart it.

If an enterprising gambler were to discover that his video poker machine was programmed so foolishly, he could take advantage of it in the following way: First, unplug the machine and plug it back in to reset it. Then, bet small amounts of money while writing down the card sequences that you get. Then, reset the machine again, and bet large amounts of money against the cards that you know will turn up.

So predictability is the bane of random number generators. Clearly, it's important not only to have a disguised algorithm, but an unpredictable seed set at the beginning of your program.

How can you set the seed? It doesn't really matter, as long as it's not based on a known quantity. It needs to be a truly random number, but again, there is no such thing as a truly random number to a computer.

One approach is to use the internal clock, including milliseconds. A human can't really control the precise millisecond at which the program starts, so there's no way to predict what the seed will be.

There are wackier ways to handle it. For instance, an algorithm called "lavarand" operated by pointing a camera at a lava lamp, taking a digitized picture, and creating a hash from the bits. This is chaotic enough to provide something that appears to be truly random.

So to recap, in order to generate random numbers, you need

1. An algorithm that is deterministic but unpredictable
2. A random seed that is preferably discovered through some (also unpredictable) aspect of the external world.

There are, of course, also advantages to using predictable seeds. If you always use the same seed, then you can test the same set of data repeatedly, which you sometimes must do if you don't want to tear your hair out trying to nail down a problem with the algorithm that actually does something with the numbers. But in a real world environment, you need some kind of outside information in order to randomize the results and stymie the users.

Artificial intelligence in games, part 2

In the previous post, we discussed the fact that tic-tac-toe is finite game, and you can even calculate all the possible states of the board: it's 19,683, with 362,880 different ways to get to the legal states.  Now we can talk about how to take advantage of this calculation to always win the game.

Let's imagine that we pit two perfect computer opponents against each other.  The first opponent, playing as "X", will want to evaluate each of the nine possible moves on a blank board.  How does it know which is best?

Well, starting in the corner, the question is: "Do I have a sure win on this path?  If so, then I will definitely make this move.  If not, then does my opponent have a sure win?  If so, then I will definitely not make this move."

But how do you know if you or the opponent has a sure win?  Simple: Imagine that you already made this move, and then try to make the best move for the opponent.

You can easily see that this is a recursive process.  It has a recursive step ("Let me try this move") and it definitely has a terminating condition.  After all, if you come to a step where (a) the board is full, (b) X has won, or (c) O has won, you don't need to look ahead to any other moves.

Here's an example of how the computer would evaluate the first possible path.

|  X |   |       X | O |       X | O | X
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
|
|  X | O | X     X | O | X     X | O | X
| ---+---+---   ---+---+---   ---+---+---
|  O |   |       O | X |       O | X | O
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
|
|  X | O | X
| ---+---+---
|  O | X | O
| ---+---+---
|  X |   |

This game ends in a win for the X player.  So if you are the X player, you like this game.  If you  are the O player, you do not like this game.  So the computer then backs up by two moves ("waking up," in the dream analogy) and assumes that O would not go there, but would instead do this:

|  X | O | X
| ---+---+---
|  O | X |
| ---+---+---
|  O |   |

Of course, this game will also result in a win for X if you follow it to the conclusion, which is this:

|  X | O | X
| ---+---+---
|  O | X | X
| ---+---+---
|  O | O | X

You get the idea.  The computer will play every game to its ending, at which point it will know exactly which games guarantee a win for one player or the other.

Now the pruning begins.  The X-playing intelligence will try to reach one of the game states that guarantees a win for X.  If it cannot, it will at least avoid reaching any game state that guarantees a win for O.

Writing an unbeatable tic-tac-toe opponent in this way is actually pretty straightforward.  You can write it to pick the first "good" move, where "good" means "First try to pick a move that guarantees a win; then try to pick a move that doesn't guarantee a loss."  If you do this, you'll find that your tic-tac-toe game will always play in the same way.  For instance, in the first move, the upper left corner is as good a move as any (the O play can never force a win).  So your program may well always start in the upper left.  This program will not appear to be intelligent.  But it will never lose.

If you want your program to be more interesting, throw in a randomizer.  If there are multiple moves that guarantee a win, then pick one at random.  Otherwise, if there are multiple moves that don't guarantee a loss, pick one of those.  Then you'll have a program that never loses, and also it will make moves that appear unpredictable.

Even though tic-tac-toe is an unwinnable game with two perfect players, some moves are better than others.  Against novice opponents, there are tricks you can use to moderately increase the likelihood that your opponent will make a mistake and lose.  This program doesn't know that.  It doesn't evaluate different positions as tactically stronger.  It just knows whether or not one player is guaranteed to win.

By the way, needless to say, this tic-tac-toe program does not have sufficient reasoning capacity to prevent it from launching a global thermonuclear war.  ;)  The computer doesn't have abstract thoughts; it's just following instructions.  Completely deterministic instructions for winning if it can.

Next time: Chess as a deterministic game.

Separating form from content

In a previous post I highlighted a video showcasing some experimental wearable Technology. One of the features in this video was that a person picked up a product from the shelf, scanned it, and received some information (green, yellow, or right lights) indicating whether the product was environmentally friendly.

A friend asked:

The thing that interests me the most about this is the impact it will claim to have on shoppers' ability to make more eco-friendly purchasing decisions. Where will the database be kept? Does it already exist? Also wondering how companies would be held to objective standards about the environmentally friendly nature of their products. Are there standards already in place? Will the database include packaging environmental impacts?

The important thing to recognize about the gizmo in the video is that it is not an information creator. It is simply a display device. In the current web 2.0 world, it's important to recognize the separation of form and content.

Essentially, the device consists of a wireless receiver, a camera, and a projected screen. All computers and computer-like devices require three basic components: input, output, and data. They've gotten more complicated over time, but they can still be best understood as variations on those basic components.

As a kid in 1982, I had an IBM PC 8086. For output, it had a screen that would display only four colors (red, green, blue, and of course black), and it had a speaker that could generate various pitches of annoying beeps. For input, it had a keyboard that made loud solid clicky noises; no mouse. It also had no hard drive. All data was stored to 5-1/4" floppy disks, which would turn on a red light when writing and produce an audible "kachunk kachunk" noise.

Many of my friends had Atari 2600s. Ataris didn't come with their own screen or speakers of course; instead, they had a dongle thingy that would plug into a standard TV and provide output. Input was limited to a joystick that had one button and four directions, which are not sensitive to the level of force you apply. Data was in the form of interchangeable cartridges. You could not save the state of your games; your progress only existed in memory while the console was on.

Now the components for a high end gaming system are getting more and more elaborate, especially with high end games: output includes complex 3D graphics and digitized sound, while input may include mouse, keyboard, camera, gamepad, and a microphone. Game files (data) take up several gigabytes, sometimes read from your hard disk and sometimes directly from a CD. Saved games may take several megabytes.

But something else is happening too.

The most important aspect of this is the internet. Thanks to the internet, the data component has shifted away from individual computers and onto servers that can be accessed from anywhere in the world. I don't have to be actually at my home computer anymore to look up some important information that's saved in an email. I don't have to be holding a physical copy of "Consumer Reports" in my hand to check out a product rating.

At the same time, wireless devices -- basically a fancy method of receiving additional input -- are infiltrating everything. We've got wi-fi hubs popping up all over the place, in coffee shops and restaurants and airports and malls. If you're not near a hub and you're willing to pay extra (I'm not yet), your cell phone will pull down an internet connection from satellite. And they're coming up with new methods to connect people, like Mobile Ad Hoc Networks, which can turn a room full of people with wireless devices into a grid of amplified signals.

So, how does the device in the video generate the information about environmental products? It doesn't. It doesn't take up space in the device's memory. It comes from the internet, from sites that are maintained by someone else.

As I envision the guts of this device, you probably install a minimal amount of middleware -- software which "knows" where to get raw data from and what is the best way to display it. The database that keeps track of individual products would probably be very large, but that needn't concern you, any more than the inner workings of your favorite web pages concerns you. You ask for a specific piece of information -- what is THIS product? -- and that gets interpreted into a web request, and the server sends it back as a stream of formatted information, to which the middleware then adds some graphical bells and whistles, for the display.

So then the question is, where does the environmental information come from? Does it already exist now, or is it just a fantasy from the video?

Well, yes it does, I think. I'm not real up on this stuff, but I googled around and came up with this and this. The data may not yet be formatted in a way that is useful to a mobile device, but the information exists in some format. If nothing else, somebody could easily write a program to scan the web page and throw out most of the HTML, pulling out only relevant information and turning it into a graphical display.

So the remaining question is: what is the standard for this information? Are these sites reliable? Well, that's up to you to decide. The main thing that has been accomplished by web 2.0 is that many competing organizations can generate this sort of content in a standardized format. Whether you trust the information depends on whether you trust the organization that generated it.

I can understand the suspicion if it is, for instance, a government agency that is known to have been strongly influenced by a political agenda. Likewise, if it's a corporate site, and the corporation is influenced by advertising dollars. But there are also consumer advocacy groups with a reputation to uphold. And while I am not a pure capitalist by any means, this really is a case where if there's a strong enough demand, the market provides what you want. "The market" in this case may be profit driven, or it may just be a bunch of activists who want to make this data available to further their agenda. Whatever the case, it's likely that you can find the data you're looking for.

The bottom line is that technology is a tool for getting at the information that already exists, or can be created. It gives you quick access to the same data from anywhere in the world.

I don't think the device shown in the video is perfect. After having some discussions about it, I think that waving your arms around is a clunky and tiring way to interact. I bet the screen is hard to read in a brightly lit area. That's not the point, though. The point is that it's becoming easier to apply technological solutions to pull in information about the world around you, and get back useful background information that's not immediately obvious to your senses.