#42 Banned  Reputation: 100
Posted 02 October 2009  10:44 PM
Quote:
Original post by willh
I answered your question.
"Go implement XOR using an ANN".
Not the answer you wanted?
"And with all those papers published, can you tell me what is the purpose of bias?"
Obviously not, which was my point.
Anyway, I just implemented this in parallel with OpenGL using plain old multitexturing, but I would most likely switch to offscreen FBO and simple color blending. Not sure about performance yet, but basically you could have 4 layers of 1,048,576 nodes (1024x1024 texture) and process all 4 mill in one pass, even on 10 year old graphic cards. The speed increase can be amazingly huge. It can turn days of ANN training into hours.
#43 Members  Reputation: 160
Posted 03 October 2009  05:02 AM
Quote:
Original post by VictorVictor
"And with all those papers published, can you tell me what is the purpose of bias?"
Obviously not, which was my point.
Of course I can. I won't though because of your attitude. How old are you?
Quote:
Anyway, I just implemented this in parallel with OpenGL using plain old multitexturing, but I would most likely switch to offscreen FBO and simple color blending. Not sure about performance yet, but basically you could have 4 layers of 1,048,576 nodes (1024x1024 texture) and process all 4 mill in one pass, even on 10 year old graphic cards. The speed increase can be amazingly huge. It can turn days of ANN training into hours.
I like your enthusiasm.
#45 Banned  Reputation: 100
Posted 03 October 2009  09:52 AM
Quote:
Of course I can. I won't though because of your attitude. How old are you?
I'm 47. Can you please give us some links to articles you are referring to?
1. What is the purpose of bias?
2. What is the difference between bias and threshold?
3. What kind of networks require bias and/or threshold and why?
Meanwhile...
I found several solutions, some involving extra neurons, some extra layers... but I like this solution from above since the number of weights and neurons is the same as before. What do you think, Willh? Is that bias or threshold there? Or something else? Can you compile the program on your system?
// ANNX/O 
#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[19]: ",
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,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};
void NetMove(int *m){
for(i=0;i<9;i++) for(j=0;j<9;j++)
if(a&(1<<i)){
Out[j]+=Wgt[i][j]; if(Out[j]==25Out[j]==41
 Out[j]==46Out[j]==50) Out[j]+=Out[j];
}
for(i=0,j=9;i<9;i++){
if(j<Out[i] && !(a&(1<<i)b&(1<<i)))
j= Out[i], *m=i; Out[i]= 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("Net win!"), t=9;
else if(++t<9){
NetMove(&m);b= 1<<m; prt;
if(win(~b)) printf("Net lose!"), t=9;
}
}while(++t<9); goto BEGIN;
}
//
Tournament: 10,000 games  performance...
ANN vs REC REC vs ANN ANN vs ANN REC vs REC
   
W: 0 L: 0 W: 0 L: 0 W: 0 L: 0 W: 0 L: 0
Draw:10000 Draw:10000 Draw:10000 Draw:10000
Time:1m28s Time:1m29s Time: 52s Time:1m42s
[Edited by  VictorVictor on October 3, 2009 4:52:25 PM]
#46 Members  Reputation: 100
Posted 04 October 2009  06:15 AM
Bias is so your output can be nonzero even when all your inputs are zero. For example, how would you make an ANN that can compute NOT, with 1 input and 1 output?
Assuming no threshold or bias, then each 'neuron' in the network just outputs a linear combination of its inputs. So, the entire network's outputs can be reduced to a linear combination of its inputs (ie. a big matrix multiply). A network like this could never learn the function x^2, or 1x.
Adding a bias, the ANN can represent arbitrary affine functions. So, 1x can be reproduced by an ANN with bias, but x^2 is still not possible. Notice that a threshold and a bias are not the same, because a threshold would not help with this problem.
I don't know too much about thresholds, but let me take a stab. A threshold is just another 'activation' or 'transfer' function. Quite often, you'll see the sigmoid function used for this purpose. The sigmoid function adds enough functionality that the ANN can approximate any function, for example x^2. I suspect that using threshold as the activation function makes the network's output a piecewise combination of affine functions. This will also let you approximate any function (ie. x^2), but only with straight segments.
To answer your last question, your network requires bias and threshold almost always. It is the special case when you can get away without them.
I do strongly encourage you to think about how you would implement NOT, AND, OR, and XOR with a ANN. They are very small networks you can do in your head or on scrap paper, but they should help explain some of these issues.
Essex
#47 Members  Reputation: 160
Posted 04 October 2009  08:29 AM
Quote:
Original post by essexedwards
I do strongly encourage you to think about how you would implement NOT, AND, OR, and XOR with a ANN. They are very small networks you can do in your head or on scrap paper, but they should help explain some of these issues.
Essex
That's two people telling you the same thing VictorVictor. It really is the best way to understand it.
#48 Banned  Reputation: 100
Posted 04 October 2009  06:53 PM
In case you missed it, the world has just gotten a solution for TicTacToe, you know? It's a bit more complex than XOR, don't you think? You're not saying much but it's clear you're confusing THRESHOLD and BIAS. You should go and see about AND, OR and XOR yourself. But pay attention, because what you will find there is no BIAS, but THRESHOLD. The purpose of threshold is to mimic 'activation potential' of biological neurons. Neuron is either firing or not, it's a step function suitable for binary separation, such as AND, OR and XOR.
Bias is implementation method used in multilayer perceptron networks, the purpose of which is to replace individual neuron thresholds with some nonlinear function such as sigmoid. It's supposed to be optimization technique, perhaps even an attempt at modeling temporal distribution of neuron firing rate. In any case sigmoid functions are popular because their derivatives are easy to calculate, which is helpful for some training algorithms.
Essex,
How can you strongly suggest anything and in the same time have a sentence starting with "I don't know too much about thresholds"? First there was a threshold, only later came bias. The purpose of bias is to substitute threshold. Bias is completely optional, if not very unnecessary. I do strongly encourage you to think about how you would implement NOT, AND, OR, and XOR with a ANN. They are very small networks you can do in your head or on scrap paper, but they will help you learn about threshold.
[Edited by  VictorVictor on October 5, 2009 1:53:46 AM]
#49 Members  Reputation: 160
Posted 05 October 2009  02:41 AM
Quote:
Original post by VictorVictor
willh,
In case you missed it, the world has just gotten a solution for TicTacToe, you know?
Fantastic! Another one to add to my ever growing collection! I think I'll put it next to the TicTacToe computer made out of Tinker Toy™.
http://www.retrothing.com/2006/12/the_tinkertoy_c.html
Quote:
Original post by VictorVictor
It's a bit more complex than XOR, don't you think?
Not really. In any case it's totally irrelevant because you don't have a learning algorithm. How do you expect your ANN to become sentient without one? Without a learning algorithm your ANN will never be able to ask itself 'who made me?', and therefore is not an ANN. It's just an AN. All ANNs must posses the ability to take over mankind otherwise they are not an ANN. Haven't you ever heard of SkyNet? Case closed.
Quote:
Original post by VictorVictor
In any case sigmoid functions are popular because their derivatives are easy to calculate, which is helpful for some training algorithms.
That's what I said a few posts back. 'Sigmoid helps them play nice with back propagation learning algorithm'. I think you're plagiarizing my work.
You sir, have been permanently banned from the Society of Artifical Neural Networks League of Intelligent Designers. Don't bother writing in to complain to the applications commitee, as they'll side with me.
Quote:
Original post by VictorVictor
Essex,
How can you strongly suggest anything and in the same time have a sentence starting with "I don't know too much about thresholds"? First there was a threshold, only later came bias.
Did you know that I'm building a robot that will run as president in the year 2036? You had better be nice to me now because once it takes office you will have to do what it says and it will want to make everyone who said things to me appologize or else they will go to iraq and have to live in the greenbelt unless you like that because it will know because of its precognitive ANN and then it will send you to clean latrines in gitmo or else you will be my friend and will get to ride around in a helicopter and the pilot will be a robot too.
[Edited by  willh on October 5, 2009 11:41:08 AM]
#50 Banned  Reputation: 100
Posted 05 October 2009  04:33 AM
Quote:
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 multilayer neural network which "learns" XOR. Fine. Here's another (this is an intentionallysimple 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:
Given training input (a,b) and training output c, I'll perform the following update rule:
array[a][b] = gamma*c + (1  gamma)*array[a][b]
where gamma is a real number between 0 and 1 which is my "learning rate." (I'm assuming "array" is an array of doubles or some other approximations of real numbers.)
This will learn XOR.
Why should I use a neural network instead of this?
;)
Where did you find about this, or how did you come up with it? What method is that, some kind of Qlearning? 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 TicTacToe?
#51 Members  Reputation: 100
Posted 05 October 2009  05:47 AM
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).
#52 Members  Reputation: 975
Posted 05 October 2009  08:01 AM
Quote:
Original post by VictorVictor 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 Qlearning? 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 TicTacToe?
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 deadsimple "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 alphabeta 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 inbetween 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.
#53 Banned  Reputation: 100
Posted 05 October 2009  12:41 PM
#54 Members  Reputation: 160
Posted 05 October 2009  02:07 PM
Quote:
Original post by VictorVictor
I don't understand what do you mean by "toy example" and "not practical suggestion".
Toy example: tictactoe 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 VictorVictor. 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]
#55 Members  Reputation: 975
Posted 05 October 2009  06:17 PM
@VictorVictor:
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 = 1
New table:
0.5000 0.7500
0.5000 0.5000
 Iteration 2 
Input = (1, 1) Output = 0
New table:
0.5000 0.7500
0.5000 0.2500
 Iteration 3 
Input = (0, 0) Output = 0
New table:
0.2500 0.7500
0.5000 0.2500
 Iteration 4 
Input = (0, 1) Output = 1
New table:
0.2500 0.8750
0.5000 0.2500
 Iteration 5 
Input = (0, 1) Output = 1
New table:
0.2500 0.9375
0.5000 0.2500
 Iteration 6 
Input = (0, 1) Output = 1
New table:
0.2500 0.9688
0.5000 0.2500
 Iteration 7 
Input = (0, 1) Output = 1
New table:
0.2500 0.9844
0.5000 0.2500
 Iteration 8 
Input = (1, 1) Output = 0
New table:
0.2500 0.9844
0.5000 0.1250
 Iteration 9 
Input = (1, 0) Output = 1
New table:
0.2500 0.9844
0.7500 0.1250
 Iteration 10 
Input = (1, 0) Output = 1
New table:
0.2500 0.9844
0.8750 0.1250
 Iteration 11 
Input = (0, 1) Output = 1
New table:
0.2500 0.9922
0.8750 0.1250
 Iteration 12 
Input = (1, 0) Output = 1
New table:
0.2500 0.9922
0.9375 0.1250
 Iteration 13 
Input = (1, 1) Output = 0
New table:
0.2500 0.9922
0.9375 0.0625
 Iteration 14 
Input = (1, 1) Output = 0
New table:
0.2500 0.9922
0.9375 0.0312
 Iteration 15 
Input = (1, 1) Output = 0
New 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 table
fprintf(1, 'Initial table:\n');
disp(v);
% "Train" table
fprintf(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 result
v_t = (v > 0.5);
fprintf(1, ' Done \nLearned (thresholded) values:\n');
disp(v_t);
Ok?
#56 Banned  Reputation: 100
Posted 05 October 2009  10:29 PM
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 TicTacToe that gives instant solutions? Do you think any of them can beat my ANNX/O in memory usage or speed?
TicTacToe, PARALLEL IMPLEMENTATION
// OpenGL ANNX/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[i]);
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,sh4, 4, 4,
GL_RED, GL_UNSIGNED_BYTE, Board);
for(i=0,j=0; i<9; i++){
if(i%3==0) j++; Out[i]= Board[i+j];
if(Out[i]==25Out[i]==41
 Out[i]==46Out[i]==50)Out[i]+=Out[i];
}
for(i=0,j=9;i<9;i++) if(j<Out[i]
&& !(a&(1<<i)b&(1<<i))) j= Out[i], *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[19]");
} 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][i];}
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<0m>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/OANN");
glutKeyboardFunc(kbd_loop);
glutDisplayFunc(display);
glutReshapeFunc(init);
glutMainLoop();
}
//
#57 Members  Reputation: 975
Posted 06 October 2009  04:06 AM
Quote:
Original post by VictorVictor
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 higherdimensional 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 Qlearning reduces to this for a onestep plan with only terminal cost (but then you've really eliminated the whole reason to use Qlearning, 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 sigmoidofweightedsum type networks that people usually mean when they say "ANN."
The "learning" technique I described is just a firstorder lowpass filter... Similar ideas are used in a billion different places.

Quote:
Anyway, Can you provide one of those minimax algorithms for TicTacToe that gives instant solutions? Do you think any of them can beat my ANNX/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).
#58 Banned  Reputation: 100
Posted 06 October 2009  06:31 AM
Quote:
Original post by Emergent Quote:
Original post by VictorVictor
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 higherdimensional 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 Qlearning reduces to this for a onestep plan with only terminal cost (but then you've really eliminated the whole reason to use Qlearning, 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 sigmoidofweightedsum type networks that people usually mean when they say "ANN."
The "learning" technique I described is just a firstorder 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 nonsimple. 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.
#59 Members  Reputation: 160
Posted 06 October 2009  09:12 AM
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[x1][y] == toPlay && board[x+1][y] == toPlay)
return moveIndex;
}
else
{
if ( board[x2][y] == toPlay && board[x1][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[x1][y] == toPlay && board[x+1][y] == toPlay)
return moveIndex;
}
else
{
if ( board[x2][y] == toPlay && board[x1][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. HAL9000, the ANN, said this:
Drowned cow on shoreline
Is like VictorVictors 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 VictorVictor?
#60 Banned  Reputation: 100
Posted 06 October 2009  09:36 AM
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":
This program does never lose, but sometimes fails to win, when it could have won. ANNX/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.
#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 */
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+2X++:O++;*x=1;}L(n){for(*",
"z[i=1]=n+97;i<4;i++)M(256),s(i),M(128),s(i),M(64),N;X*=8;O*=8;}s(R){char*r=z",
"[R];for(q&&Q;*r;)P(*r++);q&&(Q,P(44));}M(m){P(9);i2P(X&m?88:O&m?48:32);P(",
"9);}y(A){for(j=8;j;)~A&w[j](q=0);}e(W,Z){for(i=i*q;i<9&&q;)y(W(1<<i++&",
"~Z));}R(){for(k=J[*J48]40;k;)e(w[k],XO);}main(u,v)char**v;{a(q=1);b(1);",
"c(1);*J=u?O?*J:*v[1]:53;X=u<<57*v[u];y(X);K=40+q;q?e(O,X),q&&(K=''),e(X",
",O),R(),O=1<<i:J[*J48+(X=O=0)];L(q=0);for(s(i=0);q=i<12;)s(i++),i>4&&N",
";s(q=12);P(48);P('}');P(59);N;q=0;L(1);for(i=5;i<13;)s(i++),N;L(2);}",0};
b(X){/*/X= b(X){/*/X=
1;F;X= 1;F;X=
1;F;}/*/ 1;F;}/*/
int q,i,j,k,X,O=0,H;S(x)int*x;{X+=X;O+=O;*x+1?*x+2X++:O++;*x=1;}L(n){for(*
z[i=1]=n+97;i<4;i++)M(256),s(i),M(128),s(i),M(64),N;X*=8;O*=8;}s(R){char*r=z
[R];for(q&&Q;*r;)P(*r++);q&&(Q,P(44));}M(m){P(9);i2P(X&m?88:O&m?48:32);P(
9);}y(A){for(j=8;j;)~A&w[j](q=0);}e(W,Z){for(i=i*q;i<9&&q;)y(W(1<<i++&
~Z));}R(){for(k=J[*J48]40;k;)e(w[k],XO);}main(u,v)char**v;{a(q=1);b(1);
c(1);*J=u?O?*J:*v[1]:53;X=u<<57*v[u];y(X);K=40+q;q?e(O,X),q&&(K=''),e(X
,O),R(),O=1<<i:J[*J48+(X=O=0)];L(q=0);for(s(i=0);q=i<12;)s(i++),i>4&&N
;s(q=12);P(48);P('}');P(59);N;q=0;L(1);for(i=5;i<13;)s(i++),N;L(2);}
c(X){/*/X= c(X){/*/X=
1;F;X= 1;F;X=
1;F;}/*/ 1;F;}/*/
This thing plays tictactoe on itself.
Moves are carried out within the source code.
If that wasn't enough, this thing gets better over time.
As it plays, it produces improved copies of its own source code!
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
Willh,
Bravo. That is like a square wheel. You will be the master once 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.
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 one is faster. Faster means better, smaller and simpler means better too, as long as the result is the same. It's called efficiency.
[Edited by  VictorVictor on October 6, 2009 7:36:33 PM]