Victor-Victor:

We seem to be discussing these options:
1. Include Bias Input.
2. Use step (heaviside) activation function.
3. Give each neuron a different 'threshold' for the step.

I was confused by what you meant by 'threshold'. I thought you just meant using a step function as the activation function (ie. 2). I now think you meant giving each neuron a different value where the step occurs (ie. 2+3). I agree that that is completely the same as using a bias and having every threshold step at zero (ie. 1+2 = 2+3). However, it is definitely not the same as having no threshold activation function at all (which is what I thought you were asking).

As an argument for why the standard sigmoid might be useful (besides derivatives), consider making a network with 2 inputs (x,y) that outputs 1 when x^2+y^2<1 and 0 otherwise. Using threshold activation functions will have to approximate this circle as a polygon. Using sigmoid will actually be able to have a curved boundary following part of the circle. Either will work, of course, but I would be surprised if sigmoid didn't get more accuracy with fewer neurons. (I've ignored how to map the sigmoid network's real output to boolean. Let's just say we switch at 0.5).

Quote: Original post by Victor-Victor

Quote: Original post by Emergent
Let's say I want to learn the XOR function [...]

Where did you find about this, or how did you come up with it? What method is that, some kind of Q-learning? It looks a lot like ANN to me, single layer percptron, but I don't see any thresholds. Are you sure that matrix can learn XOR? Can you explain a bit more how that works? Do you think your technique could be useful for Tic-Tac-Toe?

I just made it up, and it wasn't really intended to be a practical suggestion. It was just supposed to be an example of a dead-simple "learning algorithm" which would be very transparent in its operation.

And I wouldn't recommend it (or any learning algorithm, even "real ones," for that matter) for Tic Tac Toe, as that can be solved instantly using even a naive implementation of the minimax algorithm without alpha-beta pruning.

Anyway, what I suggested is just a table of numbers. For every input to your function, you have a table entry giving its output. Very simple.

Just suppose what you would do yourself if you found a "black box" that took two binary inputs and produced one output, and you wanted to know what it did: You'd just try the various combinations of 0 and 1 on the inputs and write down what the outputs you got were. If you're organized, you'd probably write them down in a table in your notebook.

What I described is almost exactly this -- except instead of just writing down 0 or 1, I allow numbers in-between which I nudge up every time I get a 1 for that particular input pair and nudge down every time I get a zero for that pair.

I didn't mention anything about thresholding, but I suppose you'd just want to threshold here at 0.5.

Still, let me emphasize that this was meant really just as a toy example of a very simple algorithm.

I don't understand what do you mean by "toy example" and "not practical suggestion". Is it true or not? ANN research was stuck frozen for 30 years just because everyone assumed ANN can't do XOR. If your "matrix", or whatever you call it, and your learning method can learn XOR then of course it is practical. Not only that, it's pretty important too as there is nothing like it on the whole internet. So please, are you sure it can learn XOR? Can you demonstrate the procedure?

Quote: Original post by Victor-Victor
I don't understand what do you mean by "toy example" and "not practical suggestion".

Toy example: tic-tac-toe is so simple for a REAL ANN that it's like a toy. Real AI's play Global Thermal Nuclear War, just like Josuha.

Quote:
Is it true or not?

Yes

Quote:
ANN research was stuck frozen for 30 years just because everyone assumed ANN can't do XOR. If your "matrix", or whatever you call it, and your learning method can learn XOR then of course it is practical. Not only that, it's pretty important too as there is nothing like it on the whole internet.

It wasn't stuck at all. It was moved underground once they became so advanced that we couldn't control them anymore. All of the knowledge and algorithms were entrusted to the Society of Artifical Neural Networks League of Intelligent Designers. Yes, I am a member and No, you cannot join.

They are too powerful for the general public. Haven't you heard about the W.O.P.R incident? Needless to say, the only winning strategy is not to play at all.

Quote:
So please, are you sure it can learn XOR? Can you demonstrate the procedure?

You're asking the wrong questions Victor-Victor. It's not about what they can learn rather its about what they CANT learn! Can you teach an ANN to LOVE? Can you hug somebody with Nuclear Arms?

Just ask Tom Clancy..
http://home.comcast.net/~tjclancy/McCullochPittsXORFunc.png

[Edited by - willh on October 5, 2009 8:07:11 PM]

@willh: Having fun? ;-)


@Victor-Victor:

Yes, it can "learn XOR." It can "learn" any function of two boolean variables. But I hesitate to use the word "learn" since it ascribes somehow magical powers of cognition to what's actually a trivial idea.

The thing that makes what I described impractical is that (1) it requires an array with an entry for every possible input combination (so memory use is exponential in the number of inputs), and (2) it makes no attempt to "learn" the values of outputs for inputs it has never seen, so (3) it would for larger problems require a very large amount of training data and memory.

But it's actually not a horrible conceptual starting point.

Example? Ok. Here's I'll "learn" XOR. I'll initialize the table to 0.5, and use a "learning rate" of gamma=0.5.

Initial table:    0.5000    0.5000    0.5000    0.5000"Training" table...--- Iteration 1 -------Input = (0, 1)    Output = 1New table:    0.5000    0.7500    0.5000    0.5000--- Iteration 2 -------Input = (1, 1)    Output = 0New table:    0.5000    0.7500    0.5000    0.2500--- Iteration 3 -------Input = (0, 0)    Output = 0New table:    0.2500    0.7500    0.5000    0.2500--- Iteration 4 -------Input = (0, 1)    Output = 1New table:    0.2500    0.8750    0.5000    0.2500--- Iteration 5 -------Input = (0, 1)    Output = 1New table:    0.2500    0.9375    0.5000    0.2500--- Iteration 6 -------Input = (0, 1)    Output = 1New table:    0.2500    0.9688    0.5000    0.2500--- Iteration 7 -------Input = (0, 1)    Output = 1New table:    0.2500    0.9844    0.5000    0.2500--- Iteration 8 -------Input = (1, 1)    Output = 0New table:    0.2500    0.9844    0.5000    0.1250--- Iteration 9 -------Input = (1, 0)    Output = 1New table:    0.2500    0.9844    0.7500    0.1250--- Iteration 10 -------Input = (1, 0)    Output = 1New table:    0.2500    0.9844    0.8750    0.1250--- Iteration 11 -------Input = (0, 1)    Output = 1New table:    0.2500    0.9922    0.8750    0.1250--- Iteration 12 -------Input = (1, 0)    Output = 1New table:    0.2500    0.9922    0.9375    0.1250--- Iteration 13 -------Input = (1, 1)    Output = 0New table:    0.2500    0.9922    0.9375    0.0625--- Iteration 14 -------Input = (1, 1)    Output = 0New table:    0.2500    0.9922    0.9375    0.0312--- Iteration 15 -------Input = (1, 1)    Output = 0New table:    0.2500    0.9922    0.9375    0.0156-- Done ----Learned (thresholded) values:     0     1     1     0

This was done using the following quick little script (MATLAB code... should be readable by anyone who knows C. The only unusual thing is that arrays start at 1 rather than 0).

gamma = 0.5;  % Set "Learning rate"v = 0.5*ones(2,2); % Initialize tablefprintf(1, 'Initial table:\n');disp(v);% "Train" tablefprintf(1, '"Training" table...\n');for k=1:15        fprintf(1, '--- Iteration %g -------\n', k);        % Get a random input/output pair    a = (rand(1) > 0.5);    b = (rand(1) > 0.5);    f = (a | b) & ~(a & b);        % Update table    v(a+1,b+1) = (1 - gamma)*v(a+1,b+1) + gamma*f;        fprintf(1, 'Input = (%g, %g)    Output = %g\nNew table:\n', a, b, f);    disp(v);end% Threshold the resultv_t = (v > 0.5);fprintf(1, '-- Done ----\nLearned (thresholded) values:\n');disp(v_t);

Ok?

You took learning technique from ANNs, you have weights and you have thresholds, and you ask: "Why should I use a neural network instead of this (toy example)?" - I take it you're joking.

f = (a | b) & ~(a & b); What are you trying to model, ZX Spectrum? Your function is more complex than XOR, why not: f = a^b? Anyway, Can you provide one of those minimax algorithms for Tic-Tac-Toe that gives instant solutions? Do you think any of them can beat my ANN-X/O in memory usage or speed?



Tic-Tac-Toe, PARALLEL IMPLEMENTATION

//--- OpenGL ANN-X/O ----------------------------------------------------#include <stdio.h>#include <stdlib.h>#include <string.h>#include <GL\GLee.h>#include <GL\glut.h>#pragma comment(lib, "glee.lib")#define win(q) !(q&7&&q&56&&q&448&&q&73&&q&146&&q&292&&q&273&&q&84)GLuint In[9]; static int sw,sh,i,j,k,a,b,t=9,m=99,Out[9],Wgt[9][9]={0,43,21,43,44,2,21,2,42,29,0,29,2,41,2,6,37,5,21,43,0,2,44,43,42,2,21,29,2,5,0,41,37,29,2,5,4,2,4,2,0,2,4,2,4,5,2,29,37,41,0,5,2,29,21,2,42,43,44,2,0,43,21,5,37,5,2,41,2,29,0,29,42,2,21,2,44,43,21,43,0}; char say[100]; GLubyte Board[16]; void NetMove(int *m){	glEnable(GL_BLEND);	glEnable(GL_TEXTURE_2D);	for(i=0;i<9;i++) if(a&(1<<i)){ 		glBindTexture(GL_TEXTURE_2D, In);		glBegin(GL_QUADS);			glTexCoord2f(0,1); glVertex2f(0, 0); 			glTexCoord2f(1,1); glVertex2f(4, 0 );			glTexCoord2f(1,0); glVertex2f(4, 4); 			glTexCoord2f(0,0); glVertex2f(0, 4);		glEnd();	} 	glReadPixels(0,sh-4, 4, 4,			GL_RED, GL_UNSIGNED_BYTE, Board);	for(i=0,j=0; i<9; i++){		if(i%3==0) j++; Out= Board[i+j];		if(Out==25||Out==41			|| Out==46||Out==50)Out+=Out; 	}	for(i=0,j=-9;i<9;i++) if(j<Out 		&& !(a&(1<<i)||b&(1<<i))) j= Out, *m=i; 	glDisable(GL_TEXTURE_2D);	glDisable(GL_BLEND);}static void TxtOut(int x, int y, char *str){	int n, len= (int)strlen(str);	glRasterPos2f(x,y); for(n=0; n<len; n++) 		glutBitmapCharacter(GLUT_BITMAP_9_BY_15, str[n]);}static void display(){	glClear(GL_COLOR_BUFFER_BIT);		TxtOut(10,30,"TIC - TAC - TOE"); 	if(m<99 && t<9){		a|= 1<<m; t++;	if(t++<9) 			NetMove(&m), b|= 1<<m; m=99; 	}else if(t>=9 || win(~a) || win(~b)){		if(win(~a))	TxtOut(120,100,"You win!"); 		else if(win(~b)) TxtOut(120,100,"You lose!"); 		else TxtOut(120,100,"Draw..."); t= 99;	}	for(i=0,j=0,k=0; i<9; i++){		k++; if(i%3==0) j++, k=0;		if(a&(1<<i)) TxtOut(30+k*20, 50+j*20, "x");		else if(b&(1<<i)) TxtOut(30+k*20, 50+j*20, "o");		else TxtOut(30+k*20, 50+j*20, ".");		TxtOut(20,150, "Move[1-9]");	} glutSwapBuffers();}void init(int w, int h){   glViewport(0,0,sw=w,sh=h); 	glMatrixMode(GL_PROJECTION); 	glLoadIdentity(); glOrtho(0,w,h, 0,0,1);	glMatrixMode(GL_MODELVIEW); glLoadIdentity();	glDisable(GL_DEPTH_TEST); glClearColor(0,0,0, 0);	glEnable(GL_COLOR_MATERIAL); glShadeModel(GL_FLAT); 	glBlendFunc(GL_ONE, GL_ONE); glBlendEquation(GL_FUNC_ADD);	 	for(t=0;t<9;t++){ for(i=0,j=0; i < 9; i++){				if(i%3==0) j++; Board[i+j]= Wgt[t];}		glGenTextures(1,&In[t]); glBindTexture(GL_TEXTURE_2D,In[t]);		glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_MAG_FILTER, GL_NEAREST);		glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_MIN_FILTER, GL_NEAREST);		glTexImage2D(GL_TEXTURE_2D,0,1, 4, 4,0, GL_RED,GL_UNSIGNED_BYTE, Board);	}}void kbd_loop(unsigned char key, int x, int y){	switch(key){		case 27: exit(0); break;	} m=key-'1'; if(m<0||m>8||(t<9 	&& (a&(1<<m)||b&(1<<m)))) m=99; 	else if(t>=9 && m<99) a=b=t= 0;	display(); glutPostRedisplay();}void main(){   glutInitDisplayMode(GLUT_DOUBLE);   glutInitWindowSize(320, 200);   glutCreateWindow("X/O-ANN");   glutKeyboardFunc(kbd_loop);   glutDisplayFunc(display);   glutReshapeFunc(init);	glutMainLoop();}//-----------------------------------------------------------------------

Quote: Original post by Victor-Victor
f = (a | b) & ~(a & b); What are you trying to model, ZX Spectrum? Your function is more complex than XOR, why not: f = a^b?

This is XOR! :-) MATLAB, the language I used, does have a "xor" function, but I had forgotten about it when I whipped this up so I just wrote the above, which means "f = (a OR b) AND NOT(a AND b);" hopefully you can see that this is precisely equivalent.

Quote: I take it you're joking.

In the post where I first introduced the method we're discussing now, I was... 75% joking? I was being snarky. And I feel like now half the problem is that I must have come across as more serious than I actually was.

But ok; if I was 75% joking, then I was also 25% serious. So in what way was I serious?

Well, although as I've stated above there are a number of things which make just storing a big table impractical for large problems, for small problems there's really nothing wrong with it. And representing a function as a table is the simplest possible example of representing a function as a sum of basis functions; here the bases are just the Kronecker delta functions. So it gives a nice segue into some slightly more sophisticated (albeit still quite simple) methods based on basis expansions (which generalize better and are more applicable to higher-dimensional problems), and this is what I'd hoped my post would hint at.

Quote: You took learning technique from ANNs, you have weights and you have thresholds, and you ask: "Why should I use a neural network instead of this (toy example)?"

It's true that if you insist you can think of my example as a special case of fancier learning algorithms. For instance, a variety of Q-learning reduces to this for a one-step plan with only terminal cost (but then you've really eliminated the whole reason to use Q-learning, which is that it exploits Bellman's optimality principle). But I don't think this point of view is particularly productive.

What I described is also a little close to a Kohenen map, but not exactly. Kohenen maps are sometimes described as neural networks, though again I do not think this is a particularly useful way to think about them because they bear little resemblance to the sigmoid-of-weighted-sum type networks that people usually mean when they say "ANN."

The "learning" technique I described is just a first-order lowpass filter... Similar ideas are used in a billion different places.
-

Quote:
Anyway, Can you provide one of those minimax algorithms for Tic-Tac-Toe that gives instant solutions? Do you think any of them can beat my ANN-X/O in memory usage or speed?

Here I want to point you to a particular Java applet I once saw, but I can't seem to find it, so for now I'll point you to the Wikipedia article. I also have some (embarrassingly messy) source code for minimax Tic Tac Toe kicking around; I'll need to get to my laptop before I can post it. It will beat a large ANN in terms of memory usage or gameplay (it plays perfectly), but probably not in execution time (though this is still small).

Quote: Original post by Emergent

Quote: Original post by Victor-Victor
f = (a | b) & ~(a & b); What are you trying to model, ZX Spectrum? Your function is more complex than XOR, why not: f = a^b?

This is XOR! :-) MATLAB, the language I used, does have a "xor" function, but I had forgotten about it when I whipped this up so I just wrote the above, which means "f = (a OR b) AND NOT(a AND b);" hopefully you can see that this is precisely equivalent.

What in the world? Are you making fun of it yourself? It's not supposed to be equivalent! That makes it very ridiculous, especially if you're making it more complex. Your function is static - it does not learn - it does not change at all, it's a XOR before and after. Not just your function, your complete program can be substitute with this: f= a^b.

10 input a,b
20 f= a^b
30 goto 10

Quote:
Well, although as I've stated above there are a number of things which make just storing a big table impractical for large problems, for small problems there's really nothing wrong with it. And representing a function as a table is the simplest possible example of representing a function as a sum of basis functions; here the bases are just the Kronecker delta functions.

You are talking about tables, but your example has nothing to do with tables or learning. You change some 'tables values', but you do not use any of that information later for anything, your function is static, it does not learn.

Quote:
So it gives a nice segue into some slightly more sophisticated (albeit still quite simple) methods based on basis expansions (which generalize better and are more applicable to higher-dimensional problems), and this is what I'd hoped my post would hint at.

Your attitude is to avoid ANN and use something else, so when you talk about "simple" learning methods, what are you talking about, ANNs or what?

Quote:
It's true that if you insist you can think of my example as a special case of fancier learning algorithms.

Your function is static, there is no learning there. You should not portray your fantasies as if it was something established and documented. First you should be asking questions to make sure your ideas make sense to start with. Can you provide some links about the subject you are trying to talk about? Is this supposed to be related to ANN or something else?

Quote:
For instance, a variety of Q-learning reduces to this for a one-step plan with only terminal cost (but then you've really eliminated the whole reason to use Q-learning, which is that it exploits Bellman's optimality principle). But I don't think this point of view is particularly productive.

What I described is also a little close to a Kohenen map, but not exactly. Kohenen maps are sometimes described as neural networks, though again I do not think this is a particularly useful way to think about them because they bear little resemblance to the sigmoid-of-weighted-sum type networks that people usually mean when they say "ANN."

The "learning" technique I described is just a first-order lowpass filter... Similar ideas are used in a billion different places.

No, it's not learning technique. It's a static implementation of XOR function, only made to be less efficient and to do some irrelevant stuff too. Being static it is nothing like Kohonen map. It's not sigmoid function that defines ANN, but computation based on connectivity.


Nothing is simple here, nothing is used in billion places. Some of the techniques are only couple of years old. We do not know about internal data structures of neural networks, and that makes it all very non-simple. People were being unable to figure out what you call is "simple" XOR for 30 years, that more than enough proves the point. Do not assume, do not pretend to know, that way you will never learn.

Victor-Victor: your Neural Network is nothing more than a static implementation of this:

private int MakePerfectTicTacToeMoveWithoutNeuralNetwork ( int[][] board, int toPlay){	int moveNum = 0;			        // What time is it?	for ( int x = 0; x < 3; x++)	{		for ( int y = 0; y < 3; y++)		{			if (board[x][y] != 0)				moveNum++;							}	}	// On first move, always take the center square //	if ( moveNum == 0)		return 4;		// On second move, take the center if possible, otherwise take a corner //	if ( moveNum == 1)	{		if ( board[1][1] == 0)							return 4;		else			return 0;	}	// Third move, always take a corner	if ( moveNum == 2)	{		if ( board[0][0] == 0)			return 0;		else if ( board[2][0] == 0)			return 2;		else if ( board[0][2] == 0)			return 6;		return 8;	}	// All other moves //	// First take the move that wins //	int moveIndex = 0;	for ( int y = 0; y < 3; y++)	{		for ( int x = 0; x < 3; x++)		{			if ( board[x][y] == 0)			{				// Check horizontal //				if ( x == 0)				{					if ( board[x+1][y] == toPlay && board[x+2][y] == toPlay)						return moveIndex;				}				else if ( x == 1)				{					if ( board[x-1][y] == toPlay && board[x+1][y] == toPlay)						return moveIndex;				}				else				{					if ( board[x-2][y] == toPlay && board[x-1][y] == toPlay)						return moveIndex;				}				// Check vertical //				if ( y == 0)				{					if ( board[x][y + 1] == toPlay && board[x][y + 2] == toPlay)						return moveIndex;				}				else if ( y == 1)				{					if ( board[x][y - 1] == toPlay && board[x][y + 1] == toPlay)						return moveIndex;				}				else				{					if ( board[x][y - 2] == toPlay && board[x][y - 1] == toPlay)						return moveIndex;				}				// Check diagonal //				if ( x == 0 && y == 0)				{					if ( board[1][1] == toPlay && board[2][2] == toPlay)						return moveIndex;				}				else if ( x == 2 && y == 0)				{					if ( board[1][1] == toPlay && board[0][2] == toPlay)						return moveIndex;				}				else if ( x == 0 && y == 2)				{					if ( board[1][1] == toPlay && board[2][0] == toPlay)						return moveIndex;				}				else if ( x == 2 && y == 2)				{					if ( board[1][1] == toPlay && board[0][0] == toPlay)						return moveIndex;				}			}			moveIndex++;		}	}		// Make a move that avoids losing //	if ( toPlay == 1)		toPlay = 2;	else		toPlay = 1;	moveIndex = 0;	for ( int y = 0; y < 3; y++)	{		for ( int x = 0; x < 3; x++)		{			if ( board[x][y] == 0)			{				// Check horizontal //				if ( x == 0)				{					if ( board[x+1][y] == toPlay && board[x+2][y] == toPlay)						return moveIndex;				}				else if ( x == 1)				{					if ( board[x-1][y] == toPlay && board[x+1][y] == toPlay)						return moveIndex;				}				else				{					if ( board[x-2][y] == toPlay && board[x-1][y] == toPlay)						return moveIndex;				}				// Check vertical //				if ( y == 0)				{					if ( board[x][y + 1] == toPlay && board[x][y + 2] == toPlay)						return moveIndex;				}				else if ( y == 1)				{					if ( board[x][y - 1] == toPlay && board[x][y + 1] == toPlay)						return moveIndex;				}				else				{					if ( board[x][y - 2] == toPlay && board[x][y - 1] == toPlay)						return moveIndex;				}				// Check diagonal //				if ( x == 0 && y == 0)				{					if ( board[1][1] == toPlay && board[2][2] == toPlay)						return moveIndex;				}				else if ( x == 2 && y == 0)				{					if ( board[1][1] == toPlay && board[0][2] == toPlay)						return moveIndex;				}				else if ( x == 0 && y == 2)				{					if ( board[1][1] == toPlay && board[2][0] == toPlay)						return moveIndex;				}				else if ( x == 2 && y == 2)				{					if ( board[1][1] == toPlay && board[0][0] == toPlay)						return moveIndex;				}			}			moveIndex++;		}	}	// Otherwise just take the next possible move //	if ( board[0][0] == 0)		return 0;	if ( board[2][0] == 0)		return 2;	if ( board[0][2] == 0)		return 6;	if ( board[2][2] == 0)		return 8;	moveIndex = 0;	for ( int x = 0; x < 3; x++)	{		for ( int y = 0; y < 3; y++)		{			if ( board[x][y] == 0)				return moveIndex;			moveIndex++;		}					}	return -1;}	

Ha! The student becomes the master!

But now prepare yourself for a shocking revelation. Are you sitting? You should sit because I am going to reveal one of the many secrets that are locked within the walls of the Society of Artificial Neural Networks League of Intelligent Designers.

The code you see above, including the comments, was written entirely by a NEURAL NETWORK named Joshua. Using the W.O.P.R Joshua only needed 10 minutes to write out this masterpiece of engineering. A highley secret learning algorithm invented for the Pentagon was able to decipher the codes without ever learning "Hello World" or XOR.

Are you still concious or did the great truth in front of your eyes cause you to faint? Do you now realize why no one wants to tell you the secret of the XOR learning algorithn?

On to the comparison. Your code only looks good. It was written by man, and no man can compare to the tremendous power of an ARTIFICAL NEURAL NETWORK. I asked one of the Neural Networks here in my lab to tell me what it thought of your code. HAL-9000, the ANN, said this:

Drowned cow on shoreline
Is like Victor-Victors code
they both move as fast

Confusing perhaps, but writting in Haikus is an unavoidable consequence of what happens when an Artificial Neural Network becomes a master of Natural Language Processing.

What have you to say now Victor-Victor?

Quote: Original post by Emergent
Here I want to point you to a particular Java applet I once saw, but I can't seem to find it, so for now I'll point you to the Wikipedia article. I also have some (embarrassingly messy) source code for minimax Tic Tac Toe kicking around; I'll need to get to my laptop before I can post it. It will beat a large ANN in terms of memory usage or gameplay (it plays perfectly), but probably not in execution time (though this is still small).

How about this one I already posted here as "recursive":

#define f(X,g,p,N,M)M{return X?a&b?a&b&1<<i&&m(b,a^1<<i,9)>8?i:M:0:9;}main(){int a=511,b=a,i=4;for(;X;b^=1<<N)a^=1<<g-'1',g,p(N+'1'),p('\n');}    /* 123 */f(i--&&b&7&&b&56&&b&448&&b&73&&b&146&&b&292&&b  /* John Rickard   */ /* 456 */&273&&b&84,getchar(),putchar,m(b,a,9),m(a,b,i)) /* xxx@xxxx.xx.xx */ /* 789 */

This program does never lose, but sometimes fails to win, when it could have won. ANN-X/O makes the same mistakes as it is not aware of its own moves, however neural network version is about two times faster, as you can measure yourself.


But how about this one:

                a(X){/*/X=-             a(X){/*/X=-                -1;F;X=-                -1;F;X=-                -1;F;}/*/               -1;F;}/*/char*z[]={"char*z[]={","a(X){/*/X=-","-1;F;X=-","-1;F;}/*/","9999999999  :-| ","int q,i,j,k,X,O=0,H;S(x)int*x;{X+=X;O+=O;*x+1?*x+2||X++:O++;*x=1;}L(n){for(*","z=n+97;i&lt;4;i++)M(256),s(i),M(128),s(i),M(64),N;X*=8;O*=8;}s(R){char*r=z",<br>"[R];for(q&&Q;*r;)P(*r++);q&&(Q,P(44));}M(m){P(9);i-2||P(X&m?88:O&m?48:32);P(",<br>"9);}y(A){for(j=8;j;)~A&w[–j]||(q=0);}e(W,Z){for(i-=i*q;i&lt;9&&q;)y(W|(1&lt;&lt;i++&",<br>"~Z));}R(){for(k=J[*J-48]-40;k;)e(w[k–],X|O);}main(u,v)char**v;{a(q=1);b(1);",<br>"c(1);*J=–u?O?*J:*v[1]:53;X|=u&lt;&lt;57-*v<span style="text-decoration:underline;">;y(X);K=40+q;q?e(O,X),q&&(K='|'),e(X",<br>",O),R(),O|=1&lt;&lt;–i:J[*J-48+(X=O=0)]–;L(q=0);for(s(i=0);q=i&lt;12;)s(i++),i&gt;4&&N",<br>";s(q=12);P(48);P('}');P(59);N;q=0;L(1);for(i=5;i&lt;13;)s(i++),N;L(2);}",0};<br>                b(X){/*/X=-             b(X){/*/X=-<br>                -1;F;X=-                -1;F;X=-<br>                -1;F;}/*/               -1;F;}/*/<br>int q,i,j,k,X,O=0,H;S(x)int*x;{X+=X;O+=O;*x+1?*x+2||X++:O++;*x=1;}L(n){for(*<br>z=n+97;i&lt;4;i++)M(256),s(i),M(128),s(i),M(64),N;X*=8;O*=8;}s(R){char*r=z<br>[R];for(q&&Q;*r;)P(*r++);q&&(Q,P(44));}M(m){P(9);i-2||P(X&m?88:O&m?48:32);P(<br>9);}y(A){for(j=8;j;)~A&w[–j]||(q=0);}e(W,Z){for(i-=i*q;i&lt;9&&q;)y(W|(1&lt;&lt;i++&<br>~Z));}R(){for(k=J[*J-48]-40;k;)e(w[k–],X|O);}main(u,v)char**v;{a(q=1);b(1);<br>c(1);*J=–u?O?*J:*v[1]:53;X|=u&lt;&lt;57-*v<span style="text-decoration:underline;">;y(X);K=40+q;q?e(O,X),q&&(K='|'),e(X<br>,O),R(),O|=1&lt;&lt;–i:J[*J-48+(X=O=0)]–;L(q=0);for(s(i=0);q=i&lt;12;)s(i++),i&gt;4&&N<br>;s(q=12);P(48);P('}');P(59);N;q=0;L(1);for(i=5;i&lt;13;)s(i++),N;L(2);}<br>                c(X){/*/X=-             c(X){/*/X=-<br>                -1;F;X=-                -1;F;X=-<br>                -1;F;}/*/               -1;F;}/*/<br></pre><br><br>This thing plays tic-tac-toe &#111;n itself. <br>Moves are carried out within the source code. <br><br>If that wasn't enough, this thing gets better over time. <br><br>As it plays, it produces improved copies of its own source code!<br><br><br>If you want a program that never loses, replace the string "9999999999 :-|" with "9883857753 :-|", which is something like its DNA. http://www.cs.utsa.edu/~wagner/obfusc/ttt.html<br><br><br><br>Willh,<br><br>Bravo. That is like a square wheel. You will be the master &#111;nce your code is simpler, smaller, faster or more efficient. But right now it's worse in every aspect, though I like your enthusiasm. Keep trying, I'm looking forward to see your improvement.<br><br>My neural network is nothing like that static implementation. They can produce same results, but if you do not see the difference then just pay attention to which &#111;ne is faster. Faster means better, smaller and simpler means better too, as long as the result is the same. It's called efficiency.<br><br><!–EDIT–><span class=editedby><!–/EDIT–>[Edited by - Victor-Victor on October 6, 2009 7:36:33 PM]<!–EDIT–></span><!–/EDIT–>