Quote: 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)

//-------------------------------------------------------------------#include <stdio.h>#include <stdlib.h>#define st(q) a&(1<<q)?'x':b&(1<<q)?'o':'.'#define win(q) !(q&7&&q&56&&q&448&&q&73&&q&146&&q&292&&q&273&&q&84)#define prt printf("\n  %c %c %c\n  %c %c %c\n  %c %c %c  Move[1-9]: ",st(0),st(1),st(2),st(3),st(4),st(5),st(6),st(7),st(8),t)static int i,j,m,a,b,t;int RecMove(int a, int b, int *m){	int i=0,e,k,n,c=5; if(win(~a)) c=4; else{   		for(;i<9;i++) if(!(a&(k=1<<i)||b&k) 			&& c>(e=5-RecMove(b|k,a,&n))) c=e, *m=i;		if(c>4) c=3, c-=(c>1);	} return c;} void main(){  BEGIN:  m=a=b=t=0; printf("\n\n\n\n TIC TAC TOE   --- New Game ---\n"); prt;	do{		scanf("%2c",&m); a|= 1<<(m-'1'); 		if(win(~a)) 			prt, printf("You win!"), t=9;		else 				RecMove(a,b, &m), b|= 1<<m, prt;		if(win(~b)) printf("I win!"), t=9;	}while(++t<5); goto BEGIN;} //Algorithm taken from: http://www.iwriteiam.nl/SigProgC.html//-------------------------------------------------------------------

Tic-Tac-Toe, ANN 9 outputs, 9x9 weights.
(can be beaten, can be tricked, can see only opponent)

//-------------------------------------------------------------------#include <stdio.h>#include <stdlib.h>#define st(q) a&(1<<q)?'x':b&(1<<q)?'o':'.'#define win(q) !(q&7&&q&56&&q&448&&q&73&&q&146&&q&292&&q&273&&q&84)#define prt printf("\n  %c %c %c\n  %c %c %c\n  %c %c %c  Move[1-9]: ",st(0),st(1),st(2),st(3),st(4),st(5),st(6),st(7),st(8),t)static int i,j,m,a,b,t,NodeOut[9], Wgt[9][9]={0,43,19,43,44,1,19,1,42,29,0,29,4,1,4,5,37,5,19,43,0,1,44,43,42,1,19,29,4,5,0,1,37,29,4,5,3,1,3,1,0,1,3,1,3,5,4,29,37,1,0,5,4,29,19,1,42,43,44,1,0,43,19,5,37,5,4,1,4,29,0,29,42,1,19,1,44,43,19,43,0};void NetMove(int *m){	for(i=0;i<9;i++) for(j=0;j<9;j++)		if(a&(1<<i)) NodeOut[j]+= Wgt[j]; 	for(i=0,j=-9;i<9;i++){		if(j < NodeOut && !(a&(1<<i) || b&(1<<i))) 			j= NodeOut, *m=i; NodeOut= 0;	}}void main(){  BEGIN:  m=a=b=t=0; printf("\n\n\n\n TIC TAC TOE   --- New Game ---\n"); prt;	do{		scanf("%2c",&m); a|= 1<<(m-'1'); 		if(win(~a)) 			prt, printf("You win!"), t=9;		else 				NetMove(&m), b|= 1<<m, prt;		if(win(~b)) printf("I win!"), t=9;	}while(++t<5); goto BEGIN;} //-------------------------------------------------------------------

It's not that bad, eh?
ANN looks like this, it can see only X's.

INPUT_X     OUTPUT_O 1 2 3  ->   1 2 3 4 5 6  ->   4 5 6 7 8 9  ->   7 8 9Single layer perceptron, 9 nodes9 "wires" from input 1 to output 1,2,3...99 "wires" from input 2 to output 1,2,3...99 "wires" from input 3 to output 1,2,3...9.                    9 "wires" from input 9 to output 1,2,3...9

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:

//in1 -> out1,out2,out3...Weights_1[9]={ 0,1,1,   // X 2 3     x| |   1,9,1,   // 4 5 6  ->  |o| 1,1,1    // 7 8 9      | |}

Quick example B,
to "teach" NN to watch for 3in-row when opponent plays square '3' we modify nine connections coming from square '3', something like this:

//in3 -> out1,out2,out3...Weights_3[9]={ 5,7,0,    // 1 2 X      | |x 1,9,7,    // 4 5 6  ->  |o|   8,1,5     // 7 8 9      | |}

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:

Weights_1[9]={ 0,7,5,    // X 2 3     x| | 7,9,1,    // 4 5 6  ->  |o|   5,1,8     // 7 8 9      | |}Weights_3[9]={ 5,7,0,    // 1 2 X      | |x 1,9,7,    // 4 5 6  ->  |o|   8,1,5     // 7 8 9      | |}(W1 + W3)00 14 00  [1 2 3]   x| |     x| |x      x|o|x08 18 08  [4 5 6]    |o|  ->  |o|   ->   |o|13 02 13  [7 8 9]    | |      | |        | |

Tournament: 5,000 games - performance...

ANN vs RND     REC vs RND     ANN vs REC----------     ----------     ----------Won: 2800      Won: 4400      Won: 0Lost: 700      Lost: 0        Lost: 540Draw: 1500     Draw: 600      Draw: 4460time= 29s      time= 44s      time= 45sRND=random algorithm, REC=recursive algorithm

[Edited by - Victor-Victor on September 27, 2009 6:44:53 AM]

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.)

[Edited by - Victor-Victor on September 30, 2009 4:06:55 PM]

Face 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?????

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.

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

And as far as performance goes: There is nothing inately poor about the performance of a trained ANN. It's just a big lookup table with a fancy sounding name. :)

What 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).

Quote: Original post by alvaro
What 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). :)

Quote: Original post by willh
Face 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.

LOOK:

Weights_1[9]={ 0,7,5,    // X 2 3     x| | 7,9,1,    // 4 5 6  ->  |o|   5,1,8     // 7 8 9      | |}Weights_3[9]={ 5,7,0,    // 1 2 X      | |x 1,9,7,    // 4 5 6  ->  |o|   8,1,5     // 7 8 9      | |}9 = best move8 7 = good move5 1 = not good move(W1 + W3)00 14 00  [X 2 X]   x| |     x| |x      x|o|x08 18 08  [4 5 6]    |o|  ->  |o|   ->   |o|13 02 13  [7 8 9]    | |      | |        | |14 = best move 

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...

[Edited by - Victor-Victor on October 1, 2009 10:21:23 PM]

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 started with a network that had:
400 input nodes
0 nodes in 0 hidden layers
1 output node
Total: 401 nodes.

Each input was connected to the output using a randomly assigned weight. The training target for the output was -1.0 = no face, +1.0 = face.

The final network ended up with:
400 input nodes
1140 nodes in 27 hidden layers
1 output node
Total: 1541 nodes

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.

I 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. :)

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).

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

I know what you mean about using an image to draw these things. You're basically 'visually programming', which is kind of cool in its own right, but not practicle for complex networks. :)

Quote: Original post by willh
I 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?

[Edited by - Victor-Victor on October 2, 2009 11:47:23 PM]