Let's say I want to learn the XOR function -- a classic example from the early days of ANN research. One method might be to use a multi-layer neural network which "learns" XOR. Fine. Here's another (this is an intentionally-simple example): I'll store a 2d array and say that my estimate of "a XOR b" is simply given by the value in the array, "array[a][b]." Then, here's my learning algorithm:

No they don't. They cant model intuition, creativity and hunches. Which is the core of human biological thinking. They dont solve equations* nor can they prove theorems.

If as Sneftel suggests that ANNs in games are mostly used as classifiers (and the nonlinear nature of ANNs is not the key) then for most games Bayesian Networks would perform better, especially since game entities are trying to make decisions. With the added benefit that its reasoning is clear and you can go back and easily tune algo, game play etc based on results. kNNs too are probably sufficient (although SVM I feel is also overkill and probably poor since the training dataset probably would not be sufficient to produce best results).

Myself I am looking at ANNs for a problem where their function approximation and ability to capture interdependecies is useful, the blackbox nature of ANNs is ok since the data itself has no inherent meaning and is complex enough that any attempt using splines results in nonsense. I have used regression (as noted a simplest type of ANN) but it has not performed ideally. Of course there is a simper statistical technique I also plan to implement and test against to see which is better.

*An ANN is nothing but a directed graph connecting a bunch of functions with weighted nodes. They are an alchemical and blind way to approximate functions. I suspect I could build a 2 input 1 layer 3 output neural network with biological entities.

Using a mouse. I would have it classify colours using a series of tubes. I would show it a colour and use different sized cheeses and slight to mild shocks :( to correctly set the weights and implicitly, activation functions. Then initial choice of tube will set subsequent choice which chooses output :). It would also be able to classify new colour combos i did not train it weight.

No they don't. They cant model intuition, creativity and hunches. Which is the core of human biological thinking. They dont solve equations* nor can they prove theorems.

I was talking about mechanics of it, the flow of information and the type of computation can be modeled after what is known about biological/chemical information processing of neurons inside the living brain. Many different "computations" can be simulated with the results closely matching biological measurements.

Blue Brain Projecthttp://bluebrain.epfl.ch/

I do actually agree with you, but I would phrase it differently. I'd say, intuition, creativity and such are indeed the core of human mind, which can not be simulated as it is not really understood, it's not defined properly nor it can be objectively examined or measured.

But intelligence and logic can, which I refer to as "thinking", so I would separate intelligence (thinking) from everything else as it is the only thing we _can actually judge and measure as an external observer - it is because intelligence/logic is deterministic, while everything else is chaotic, if not completely random.

Though, in some hypothetical theory ANN could simulate intuition and creativity too... if it could only spontaneously arise and evolve by itself, just like in the real world. But really, you would need to build and train fully talking AI to be able to ask about it. You can't just put partial artificial or biological network and hope to measure some numerical or voltage output to be identified as "intuition". This can only be done with logic circuits aka intelligence and deterministic algorithms.

Imagine we train some ANN to the point you can have conversation with it, and it tells you it has emotions and intuition, it can dream and it likes music, would you believe it?

Anyway, amazingly I was right about Quake bots, many of them do use neural networks, but the best part is that it's all perfectly documented and all the source code is available. Google "neural network quake bot".

Original post by Emergent
Let's say I want to learn the XOR function -- a classic example from the early days of ANN research. One method might be to use a multi-layer neural network which "learns" XOR. Fine. Here's another (this is an intentionally-simple example): I'll store a 2d array and say that my estimate of "a XOR b" is simply given by the value in the array, "array[a][b]." Then, here's my learning algorithm:

So, you do know that most ANNs are essentially just a bunch of Sigmoid Functions trained on their derivatives with some random searches to optimize the arrow weights yuh? There is nothing magical about trig, hyperbolic or logistic functions. The more modern methods are more statistically influenced and ever further away from so called 'neurons'.

A decision Tree could result in behaviour just as robust as that bot's. Maybe better cause you could look at result make sense of it and go back and modify training, pruning, entropy etc functions. Indeed the simplest AI to train and code yet yielding nice behaviour could be written in terms of decision trees or even a hierarchy of such. It would also be able to react to situations it didn't train on.

A step further, harder but clearer than an ANN but still allowing for hardcore learning and allowing for random behaviour would be a bayes net. A pretty simple one would be Tree Augmented Naive Bayes.

So, you do know that most ANNs are essentially just a bunch of Sigmoid Functions trained on their derivatives with some random searches to optimize the arrow weights yuh? There is nothing magical about trig, hyperbolic or logistic functions. The more modern methods are more statistically influenced and ever further away from so called 'neurons'.

A decision Tree could result in behaviour just as robust as that bot's. Maybe better cause you could look at result make sense of it and go back and modify training, pruning, entropy etc functions. Indeed the simplest AI to train and code yet yielding nice behaviour could be written in terms of decision trees or even a hierarchy of such. It would also be able to react to situations it didn't train on.

A step further, harder but clearer than an ANN but still allowing for hardcore learning and allowing for random behaviour would be a bayes net. A pretty simple one would be Tree Augmented Naive Bayes.

Yes, except that ANN computation can be implemented via parallel processing, its natural design, which makes it suitable to handle high-volume input. ANN can learn dynamically (real-time evolution), which _will introduce chaos or even randomness (as you explained) that is necessary for human-smart AI. Unpredictable, inventive, creative and cunning one. For that you need dynamic flexibility, recursive self-adaptivity and, of course, some randomness or chaos, not to call it 'free will'.

However, if some variant of 'decision tree' can do all that, than indeed there is no difference between them at all, and I give my vote to whichever is faster.

I prefer philosophical aspect of it, so let me ask you - do you think there is a chance intuition and creativity might spontaneously arise within some ANN, perhaps as a byproduct of "adaptive-intelligence", if we could train its logic circuitry to the point of having a meaningful conversation? I find this interesting, because the first sentence of the type "I like" would suggest this AI has emotions and since it's built on "binary search" principle it's bound to have some preferences, likes and dislikes, maybe even a wild desire. Science fiction or theoretical reality?

You use words I am not used to seeing with ANN but all of the 7 or so ML algorithms mentioned in this thread can be parallelized. Especially so if coded in a functional language and making no use of mutable state.

As well for many of the simpler ones it is actually easier to code something to train them on the data gathered during play. And it would arguably 'learn' faster since the methods are still effective on little data unlike say ANN or SVM. The problem of course is that the AI would get too good or overfit to a particular play style so a good game would try to account for this.

As for strong AI, I am a sceptic. At least for the next 200 years. But if any such thing were coded and an ANN was part of it, it would only be a small part of it. Because you see, an ANN is much too simple to represent whatever intelligence is. In that scale of things saying f o g(x), g:X -> R^n;f:R^n -> R^m; n,m in R represents all intelligence is equivalent. And that is absurd no? To me the phrase train an artificial neural net till it can talk makes little sense. It sounds impossible, how to train a something that is beyond the scope of a technique to do something not understood using an undefinable method?

Original post by DaeraxYou use words I am not used to seeing with ANN but all of the 7 or so ML algorithms mentioned in this thread can be parallelized. Especially so if coded in a functional language and making no use of mutable state.

As well for many of the simpler ones it is actually easier to code something to train them on the data gathered during play. And it would arguably 'learn' faster since the methods are still effective on little data unlike say ANN or SVM. The problem of course is that the AI would get too good or overfit to a particular play style so a good game would try to account for this.

I agree most games can produce more enjoyable AI with much simpler algorithms, easier, faster to do develop and very much easier to debug and fix. This is enough to keep ANN from being popular, and it's pretty good reason. However, I also believe ANN can practically substitute any of those algorithms, no matter how simple or complex, with the same or better efficiency.

Quote:

As for strong AI, I am a sceptic. At least for the next 200 years. But if any such thing were coded and an ANN was part of it, it would only be a small part of it. Because you see, an ANN is much too simple to represent whatever intelligence is. In that scale of things saying f o g(x), g:X -> R^n;f:R^n -> R^m; n,m in R represents all intelligence is equivalent. And that is absurd no? To me the phrase train an artificial neural net till it can talk makes little sense. It sounds impossible, how to train a something that is beyond the scope of a technique to do something not understood using an undefinable method?

This is very much like Darwinian evolution and natural selection, driven by random mutations producing ever more efficient design under given external dynamics of nature itself. Trial and error - survival of the fittest. It is a slow process and not very pragmatic one, but it inexorably leads to nothing but improvement.

If you can believe humans could evolve from single cell organisms, then it should not be so hard to believe our ANN would eventually utter some meaningful words, after many random trial and errors of course, but word for word... And the more you know, it becomes easier to learn.

ANN can be trained from complete zero to do anything, as long is it keep trying. There is a project where ANN had an eye and it could move across chess board. The eye had no idea where it was or what it was doing, but it had built-in desire to keep moving chess pieces. It was "punished" for bad moves and it was "rewarded" when it made good moves. Eventually this eye learned to play chess without ever knowing what it was doing or where it was.

Genetic algorithms use ideas from the natural process of evolution to mould populations into a form which is well suited to their environment. This GA is called a steady-state genetic algorithm because of it's constant population size. Roughly every 1-6 minutes, The GA is run on the bots:

1. The fitness (or success) of each bot is evaluated.

2. Two parents are chosen from all the bots. The parents are chosen using one of three selection mechanisms. Generally the better the bot, the more chance it has of being chosen as a parent.

3. All the weights(connection strengths) of the two parent bot's NNs are then encoded into a chromosome, or string of 'DNA' for each parent.

4. These two pieces of DNA are sliced at certain random points and swapped around to create two new pieces of DNA from the parent DNA.

5. Two children bots are chosen - criteria: low fitness. The oven-fresh child DNA is then converted back into synapse weights with a reverse-encoding process and used to overwrite the children bots' NN weights. At this point mutation can occur.

Original post by LeChuckIsBackThere is a small but important practical use for ANN in games, that is speech recognition. Some of the latest games started to implement command input directly from human voice, quite funny to yell things in the mic if you ask me. There is a powerful SDK to easy implement it in a game but don't remember the name and it's not free.

AFAIK, most modern speech recognition is based on hidden Markov models.

Markov models have many similarities with neural networks. Both are statistical models which are represented as graphs. Where neural networks use connection strengths and functions, Markov models use probabilities for state transitions or observation probabilities. Where neural networks can be feed-forward or recurrent, so can Markov chains be left-to-right or recurrent. A key difference is that neural networks are fundamentally parallel, they excel at learning phoneme probability from highly parallel audio input. And, as in neural network where the challenge is to set the appropriate weights of connection, the Markov model challenge is finding the appropriate transition and observation probabilities.

The curious quality of recurrent neural networks is that they retain traces of the previous inputs, and in this sense incorporate context of time and memory. The previous states have an impact on the current states, even without additional learning algorithms. But what exactly is being represented, or how it is being represented, is largely unknown. It's like trying to figure out recursive equation by looking a a picture of its fractal.

Neural networks are metaphorical black boxes; we know what goes in, we know what comes out, but have no idea what is really going on inside, how knowledge and processes are actually represented. This is true for feed-forward networks and for biological brains. We can isolate locations and their functions, but inferring internal data structures has so far not been possible.

The main difference between biological networks and artificial networks is that the former engage constantly in reality testing. They are situated in a world of constant feedback. Studies of child development indicate that children are wired to interact heavily with their world, to understand physical properties with all of the senses, sensory overlap being an important notion in robotics for statistical constraint satisfaction, and learning how to achieve ends by producing various vocalizations is critical to learning language.

Although it may be a while before computers are given the same opportunities for real-world interaction as humans, this being dependent on the development of adequate sensory apparatus and successful coupling to neural or other computational machinery, we at least know that this is a correct path towards progress in developing intelligent systems.

Original post by frogtag
I've done some preliminary research into AI, specifically ANNs. But I don't really understand the practical uses of ANNs in game programming, in regards to its ability to potentially mimic human thinking. Okay, I get the concept that you can use it in character recognition, but that has utility potential, not say for instance how a NPC will react to a situation.

Can anyone give me some more practical usages in terms of NPC AI and/or direct me to some tutorials?

At the moment I don't see the point in an ANN unless your interest is purely ANN research!

In regards to its ability to mimic human thinking the most distinctive attribute of ANNs is their learning capacity. Where, how and why this can be useful is another story, but even though NN is somewhat of an 'alien-technology' to us it's not so terribly complicated.

--- "Hello World" ---

Tic-Tac-Toe, recursive algorithm
(plays almost perfect game, can not be beaten)

There are many ways to train ANN and that's all well documented, all 2% that we know about it, so I'll try to talk about something a little bit different, something more direct and hopefully more insightful.

Quick example A,
to "teach" NN to play square '5' when opponent in on square '1' we modify "thickness" or weights of these nine connections coming from square '1', like this:

Basically it means: "if opponent is on '3', the best move is square '5' then '7', good moves are '2' and '6', while not so good are squares '1' and '9'." Connections '4', '8' and '3', having a small value of 0-1, can be removed since they do not impact the computation, and that's how we optimize. This kind of network can even learn some chess based on these same principles, where you can program/teach ANN by directly setting its weights, pulling those neurons like some Despereaux. With some additional inputs it could learn specific chess moves for each figure, what to go for, what to run from, and who knows what else. You can use this in action games as well, say to make soldiers take cover at appropriate corner depending on where enemy is, and such.

Ok, I'll have to continue some other time, maybe I'll even manage to teach this X/O-ANN some new tricks, but considering its shallow brain and half-blindness this "creature" performs rather well, I think.

[EDIT]Quick example C,
"teach" NN to play couple of openings, this is how it all comes together:

Table driven state engines probably still provide the best bang for the buck. Most Neural Networks or just adaptive approximation trees. Neurons and the networks of axons and dendrites in a brain can only be simulated to a tiny fraction of the biological systems capacity to reason. In most cases a lot of processing time is eaten up attempting to calculate synapse threshold potentials. Factor in attempts to build the cerebral reflector clusters and you end up with huge amounts of code that eat up tones of processing time. I don't want to discourage development of neural algorithms because there is a lot to be learned about it. Here is one thought that will put the brain into perspective. "Tip of the tongue". I know it but I just can't quite remember it. Only in a brain can this anomaly occur. Reason is the highly associative nature of the cerebral cortex allows this to happen. A single though is not just a few synapses causing a few neurons to fire into axons triggering a response. I actually involves millions of neurons firing sequences of pulses in a collective manor that allows the thought to come into play. Micro processors just don't have the capability to make it work in todays instruction sets. For us in games it can evoke great ideas of how to mimic these actions and potentially start using multicore processors to our advantage.

Once trained ANN is indeed some form of look-up table, but its raw form is very liquid and multidimensional. I completely agree multicore processors and ANN is attractive combination. ANNs are also compatible with optical computing and holography in particular.

As for Tic-Tac-Toe, the good news is that it plays without losing when it goes first, even if the 1st move is randomly chosen. Nevertheless, I've come to conclusion I can not make it play any better. There are few positions I can not solve and I'm afraid I don't see how additional nodes might help. I tried it and since it's based on simple matrix addition we can actually see, as shown above, the boundaries and why "teaching" some new positions makes it "forget" some old ones.

But even if it is all very "visual", obvious and the whole interaction can be isolated step by step, I still can not see the solution. I don't see how could bias, threshold or anything else help either, so any ideas are welcome. The goal is to make minimal ANN play perfect tic-tac-toe.

Actually, hold on. Most graphics cards are highly parallel as of today, so 'ANN on GPU' sounds like technically interesting and very practical project, besides I don't think I've ever seen an actual *parallel* implementation of ANN, except in hardware. That would be really interesting, besides I was always wondering how do you solve multiple and simultaneous access to the same node in parallel computing?

Could we then use some OpenGL Shader language to make neuron logic? Does anyone know if GPU hardware pipelines are suitable for this? Could we implement this simple Tic-Tac-Toe game with GLSL? (I think I should start my own thread about this in graphics section, sorry.)

Original post by alvaroWhat kind of ANN are you guys talking about? The ones I know are not a lookup table at all. They are a composition of linear combinations and transfer functions (typically sigmoid).

The way mine is implemented is that each node of the network is just an element in a big 1 dimensional table. Each node maintains a list of connections to other nodes ahead of it in the table (feed-forward). Each connection has a weight. This is adequate to describe every FF ANN I've seen.

One reference + 1 multiply + 1 add for each connection. That's not terribly expensive, computationally. (There is an 'activation' but that happens once, and not for each connection)

The Sigmoid activation isn't a requirement of an ANN. Correct me if I'm wrong, but I thought the sigmoid just made ANNs play nicer with the back propagation learning algorithm.

I've used this method to train a network that is able to detect faces 99% of the time (which isn't as great as it sounds considering how many non-faces are in a 1024x768 image, but you get my point). :)

Original post by willhFace detection: 20x20 input nodes with a range in value of 0 - 255. Solved.Tic-tac-toe: 3x3 input nodes with a range in value of 0 - 2. Not solved?????

Your ANN solved face detection, not me and you. We know about it as much as we knew before. Yes, we could build some large network and it would eventually fit the mold, but *we* would again learn nothing from it.

Almost nothing is solved. People tried to model biological neurons and discovered some interesting computational properties, most of which came out unexpected. It turns out underlying principle is a completely another type of computation altogether. It's based on connectivity where the basic difference is that it's analog and probabilistic, while humans prefer their math to be digital and deterministic.

In any case, this divides the research to two roads. One leads scientists to try and mimic what they think biological neurons are doing, hoping to find other mysterious properties and harness some more of this computational power. It's kind of random search based mostly on hope, but I agree it's reasonable since that is exactly what brought us up to this point. The other road is about simplification and search for underlying principles. It's about understanding the essence and trying to make some mathematical sense out of it. I'm the second road extremist, I don't care to simulate biological networks, I think we can do better neurons than brain itself.

Quote:

An ANN should definately be able to solve Tic-Tac-Toe. No need for parallel processing. Not even any need for a sigmoid; It's optional, not required.

Yes, ANN should be able to play perfect Tic-Tac-Toe, and I'm asking you to tell us how to make it so. For start, can you tell what is the minimum number of layers and input/output neurons necessary for that?

Quote:

Could it be that your training data for the ANN is what's causing the problem?

I did not "train" it. I just wrote numbers there, by hand... in notepad.

Simple addition. I did the same thing for all the corners and I did the same thing for all the side moves, and it works! You can see each of 9 matrices in the source code. I just needed to increase some numbers so some new sums can fit in-between some old sums to store some new positions. I "trained" network in 5 minutes with pen and paper, like crosswords. If I ever make chess engine from this I will make moves and logic in Photoshop. It's like working with transparent image layers, 3D textures. Am I failing to explain, can you understand?

You will not find anything like this in books and articles. Besides, there are no freakin' examples on the whole internet at all. It's all the same, pictures of neurons and incomprehensible mathematics formulas, no "Hello World", no Tic-Tac-Toe. And with all those papers published, can you tell me what is the purpose of bias? Do you have bias or threshold implemented in your network? What difference does it make?

P.S.I think almost solved the Tic-Tac-Toe. 7 more neurons, 16 new weights...

Yes, you're right that 'I' did not solve face detection. I don't think 'I' could solve it though, which is why I trained a classifier.

I disagree with your assement that 'almost nothing is solved'. In my case the problem of detecting a face was solved.

I didn't engineer my NN by hand. I 'grew' it using what some might call a genetic algorithm. Ultimately it was a hill-climbing climbing algorithm that used some educated guessing about how to direct the climb. Mutation operators involved adding/removing/moving/modifying nodes and connections.

I did not keep a record of the number of connections. I 'regrew' the network later, with a scoring bias for simplicity, and was able to reduce the network size to approximately 800 nodes (that's only 1 extra node for each input!). I suspect it could go even smaller.

The architecture of the network, when graphed as something with layers, was very messy. Not every hidden-layer node is neccesarily connected to the layer in front of it. For example, a node in layer 3 might be connected directly to the output node and to a node in layer 15.

I employed a few strategies to help me understand what the network was doing and can tell you that there was some very obvious structure in the solution.

Original post by willhI just read the bottom of your post. I think you're being confused by the general amount of BS that accompanies most descriptions of anything AI related. :)

I said to have found a solution to make this very minimal ANN play a perfect game of Tic-Tac-Toe, how do you draw your conclusion without even hearing about it? I have no idea what are you talking about. Is there something you think can be done better, something I'm doing wrong? Please, what is it?

Quote:

An ANN is really just a decision tree. (or state table, whichever you prefer).Source code is really just a decision tree (or state table, whichever you prefer).

You can represent all boolean logic statements (AND, OR, XOR) using a NN. That fact alone means that, in theory, you should be able to approximate any function using an ANN.

Hand implementing OR, AND, and then XOR using an ANN is the best way to understand how they work. XOR is a great one since it uses all of the different tools (threshholds and biases).

Can you apply that knowledge to the problem at hand?

Quote:

Check out how XOR is implemented in an ANN and all of your questions will be answered.

I don't see how that answers, can you please say it out loud:

- What is the purpose of bias? Do you have bias or threshold implemented in your network? What difference does it make?