Tricks of the Windows Game Programming Gurus:Making Silicon Think with Artificial Intelligence

All ITKnowledge Source Code Search Tips Advanced Search |

| Tricks of the Windows Game Programming Gurus by Andre LaMothe Sams, Macmillan Computer Publishing ISBN: 0672313618 Pub Date: 09/27/99

Search this book:

Previous | Table of Contents | Next

To see how a basic neurode works, assume that you have two inputs, X1, and X2, that can take on the binary values 0 and 1. Then set your threshold at 2 and w1=1 and w2=1. The summation function looks like this:

    Y = X1*w1 + X2*w2

Compare the result to the threshold theta of 2. If Y is greater than or equal to 2, the neurode fires and outputs a 1.0. Otherwise, it outputs a 0. Table 12.3 is a truth table that shows what this single-neurode network does.

Table 12.3 Truth Table for Single Neurode Network

X1 | X2 | Sum Y | Final Output
--- | --- | --- | ---

0 | 0 | 0 | 0
0 | 1 | 1 | 0
1 | 0 | 1 | 0
1 | 1 | 2 | 1

If you stare at this for a moment, you’ll realize it’s an `AND` circuit. Cool, huh? So a simple little neurode can perform an `AND` operation. In fact, with neurodes you can build any logic circuit you want. For example, Figure 12.32 shows an `AND`, an `OR`, and an `XOR`.

Figure 12.32 Basic logic circuits.

Real neural networks are much more complex, of course. They can have multiple layers, complex activation functions, and hundreds or thousands of neurodes. But now at least you understand their fundamental building blocks. Neural networks are bringing a new level of competition and AI to games that you’ve never seen before. Soon games will be able to make decisions and learn!

This is an important area of interest, but I have to watch my page count so I don’t have time to cover it properly here. However, the `ARTICLES\AI\NETWARE\` directory on the CD contains an article on neural networks that will give you a more solid foundation on the topic. It covers all the various types of networks, shows you learning algorithms, and illustrates just what they can do. You’ll find all the source code, an executable, and both an MS-Word `.DOC` version and an Adobe Acrobat `.PDF` version of the text.

### Genetic Algorithms

Genetic algorithms are a method of computing that relies on biological models to evolve solutions (if you’re reading this, Dr. Koza, don’t have a heart attack based on my loose definitions). Nature is great at evolution, and genetic algorithms try to capture some of the essence of natural selection and genetic evolution in computer models to help solve problems that normally couldn’t be solved by standard means of computing.

Basically, genetic algorithms work like this: You take a number of informational indicators and string them all together into a bit vector, just like a strand of DNA, as shown in Figure 12.33.

Figure 12.33 Binary encoding of genetic information.

This bit vector represents the strategy or coding of an algorithm or solution. You need a few of these bit vectors to start with. Then you process the bit string and whatever it represents by some objective function that scores its fitness. The results are its score. The bit vector is really a concatenation of various control variables or settings for some algorithm, and you manually come up with a few experimental sets of values to start with based on intuition or prior knowledge (if available). Then you run each set and you get the score of each. You may find that out of the five you created manually, two of them did really well and the other three did really poorly. Here’s where the genetic algorithm comes in.

You could tweak the solution from there, knowing that you’re on the right track, or you could let genetic algorithms do it for you. Mix the two solutions or control vectors together to create two new offspring, as shown in Figure 12.34.

Figure 12.34 Digital sex.

To add a little bit of uncertainty, during the crossover process you flip a bit here and there to simulate mutation. Try your new solutions, along with the last generation’s best solutions, and see what happens with the scores. Pick the best results out of this generation and do it again. This is the process of genetic evolution. Amazingly, the best possible solution will slowly evolve, and the result might be something you never imagined.

The key things about genetic algorithms are that they try new ideas (patterns) and they can search a very large search space that normally couldn’t be searched if you went one by one. This is due to mutation, which represents completely random evolutionary events that may or may not lead to better adaptation.

So how do you use this in a game? There are millions of ways, but I’m going to give you just one to get you started. You can use the probability settings of your AI as the genetic source for digital DNA, and then take the creatures in your game that have survived the longest and merge and evolve their probabilities, thus giving the best traits to future generations. Of course, you would only do this when you needed to spawn a new creature, but you get the idea.

Previous | Table of Contents | Next

Copyright © Macmillan Computer Publishing, Inc.

Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.