Artificial Intelligence?
I bought my first computer at the age of ten. I asked the salesman if the computer could think and I was amazed when he said that it could. In those days it didn't take much to convince me he was right. As soon as I saw PAC-MAC being chased by ghosts I knew his adversaries could somehow see where he was and hunt him down. The "somehow" had me stumped for some time. Well I was only ten, and I soon lost interest in trying to replicate the behaviour of the ghosts in my own simple programs. It wasn't until years later that I found out how exactly PAC-MAN was hunted down so efficiently and I couldn't believe how simple it was. Is it intelligence though?
RoboHound
The RoboHound program emulates a dog trying to find a snack in a maze. The first task that the RoboHound applet (presented below) performs is to create a grid of cells and pick a random cell in that grid, which will become the target cell. The target cell has a distance from itself of zero. All adjacent cells will have a distance to the target cell of one and so on.
At this point all the cells in the maze are walls except for the target cell. So we start at the target cell and we place each adjacent cell into a list of cells. We then pick a random cell from this list and if it has not already been freed then we free it and set it's distance from the target cell as one. We then recursively repeat the previous steps for this cell, adding it's adjacent cells to a list and so on. This is a maze generation algorithm based on a depth-first search. You can read more about such algorithms here.
Once the maze has been created we find a random free cell in which to place the dog. The dog's task is very easy. He simply looks at the his adjacent free cells, picks the one with the lowest distance to the target cell and moves to it. He repeats this process until he has found an adjacent cell with a distance value of zero, in which case he's found his snack. The mazes that are generated are quite complex (deliberately so in fact) and can take some time for the dog (the blue dot) to find the snack (the red square).
Is this program intelligent? Well I certainly couldn't solve this maze, but yet the RoboHound program can. So is it intelligence? Well, in a very simplistic way, I believe it is. What's the difference between a real dog sniffing out a snack and RoboHound. The real dog has an infinitely more complex sense of smell, necessary in his more complex world. In RoboHound's limited world his simple sense of smell seems to serve him quite well. The source code for this project is available here. Feel free to contact me with any feedback. I'd especially like to know if you use the code in any of your own projects.
SmartSweepers
The SmartSweepers program simulates minesweepers picking up mines. The mines are represented by small green squares and the minesweepers are the tank like objects. SmartSweepers was written by Mat Buckland and is presented (with full source code) on his web site ai-junkie.com. SmartSweepers covers two very interesting topics in Artificial Intelligence. The First is neural networks and the second is genetic algorithms. I wanted to learn more about these subjects and found some of the literature daunting, to say the least. Then I stumbled across ai-junkie.com. I read two very good tutorials on the site and thought I understood them, but to be sure I decided to port SmartSweepers to Java from the original C++. To run the simulation below you will need to give the applet the focus by clicking on it and pressing the 'r' button. You can press the 'r' button again at any time to restart the simulation.
Matt Buckland's explanation of this program and the topics it demonstrates is excellent. Essentially we encode each neural net as a genome (a sequence of real numbers) which represent the weights applied to the inputs of each neuron and the bias applied to it's raw output. I say raw, because after the bias is subtracted from the summed products of the inputs and their corresponding weights a sigmoid function is applied to produce the output of the neuron. What I find amazing about this is that initially the genomes are created as sequences of random numbers. The neural networks that form the brains of the minesweepers are configured from these random numbers. Then the simulation allows the minesweepers to perform their tasks for a generation. At the end of a generation the fittest minesweepers have picked up the most mines. They are allowed to procreate, resulting in the next generation of minesweepers. Evolutionary principles, such as mutation and crossover are applied with each new generation. The fittest minesweepers are shown in red. To view the statistics for the generations press the 'f' button.
Another interesting point is regarding the neural nets themselves. The inputs to the neural nets are two vectors, or to put it another way four real numbers. These vectors represent the direction to the nearest mine and the direction in which the minesweeper in question is facing. Each neural network has only two outputs representing the force to be applied to each track. Although, each neural net is composed of several layers, each containing several neurons, the process is still surprisingly simple. And yet as simple as it is, even after only a couple of generations, the minesweepers exhibit behaviour that appears extremely intelligent. So I'm again forced to wonder if it isn't just the level of complexity that distinguishes our own intelligence from that of these simple programs?
The source code for this project is available here. Feel free to contact me with any feedback. I'd especially like to know if you use the code in any of your own projects.
