Wednesday, October 1, 2008

Artificial Neural Networks: Tic-Tac-Toe

  
ANN Tic-Tac-Toe solved (plays a perfect game) with only a single layer perceptron network, mapping 255,168 combinations into only 81 bytes of connectivity logic. I did the 'network training' by "hand", as I could understood the method through which this ANN would output results, but I could not see the way to provide conditions which would produce the necessary state via whatever recursive or self-learning algorithm.
  
So, I hard-coded the Tic-Tac-Toe "brain" by hand, using plain trial-and-error, which turned out to be surprisingly easy, but I again could not quite put into words what, why and how did I do it, so I could not express the procedure with any algorithm, yet again. Nevertheless, the "brain" was there, and it lives! This particular implementation below does all the computation in parallel, which is quite "natural", or better to say 'only' mode of operation for natural neural networks, here executed on a video card, using OpenGL multi-texturing capabilities, so both logic and graphics of the game are computed by the GPU.


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <GL\GLee.h>
#include <GL\glut.h>
#pragma comment(lib, "glee.lib")
//*** THE BRAIN 
 #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,sh-4, 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]==25||Out[i]==41
|| Out[i]==46||Out[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[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][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<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();
}

No comments:

Post a Comment