Herself’s Artificial Intelligence

This might be of interest to some of my visitors.

Jeff Hawkins founder of Palm, Handspring and author of ‘On Intelligence’ has founded Numenta.

….To prove his theory, Jeff founded Numenta – a company dedicated to developing algorithms and software based on the ideas put forward in the book. This spring Numenta released its first product, an experimental software aimed at researchers and advanced developers which embodies the algorithms and techniques pioneered by Jeff and his crew….

Numenta

This AI process mimicks the physical process of annealing. Annealing is the process of heating and cooling a metal in a controlled manner. This gives us a stronger metal if the cooling part is done slowly. A higher temperature means more energy. So if I am trying to place a marble on a hilly landscape in the global minimum I may have to shake things up a great deal to bounce the marble out of a local minimum. So I start out with lots of energy hoping to locate the global minimum. Then reduce the energy hoping to zero in on the minimum better.

Start with a random solution or your best solution from a previous run. This is our current solution. The energy of our solution is then measured. For the eight queens problem the amount of energy is the amount of conflicts between our queens.

We then take a copy of the solution, bounce it around a bit and see if it has less energy than the previous solution. If so we use that as our working solution. If not we test it using P(dE) = exp( -dE/T). At higher temperatures we take worse solutions than we do when we get close to finding the correct solution.

Simulated Annealing is used in traveling salesman and scheduling problems and also it has been used to do some image clean up work.

Algorithm:
Set up initial board
Copy initial solution to current, working and best solutions

Loop:
Bounce the queens around a the board
See if this solution is better than last one ( uses less energy / has less conflicts )
if so use new solution
if not test again using P(dE) = exp( -dE/T )
if this gives a lower energy than a random number we pick, use this solution
Switch copy boards as needed
Adjust temperature
Bail from loop if problem solved ( energy < some number )

Java source code 8 queens, Simulated Annealing

Simulated Annealing was developed by S. Kirkpatrick, CD Gelatt and MP Vecchi in 1983 and by Cerny 1985. It is a Monte Carlo type of solution to a problem.

More information:
Simulated annealing for location area planning in cellular networks
Wiki – Simulated Annealing
Taygeta Scientific – Simulated Annealing Information

Game developers are right up there with the government on the progress and contributions they have made to AI. The game environment is an easier one to work in because the gamers can control the environment and deal with specific issues rather than dealing with the real world. Also, there is lots of money to buy cool equipment and get top notch people involved. Huge progress has been made in 2D and 3D graphics, search algorithms, data mining and bots in the game field.

Most of the game playing design in artificial intelligence is the search for quick, intelligent search routines. Game programs are concerned with reasoning about actions. Not only must the path of possible moves be sought but the program must consider the opponents moves which are unknown to the program until they are made.

Some History
The 1950s brought us a checkers playing program by Arthur Samuel. It got good enough to beat its creator at checkers.

The 1970s brought us a backgammon program from Carnegie Mellon. This program played well enough to beat Luigi Villa, who was the top backgammon player at the time.

More information:
Core Techniques and Alogrithms in Game Programming ( online textbook )
Beyond the bits: Artificial Intelligence Part #1
AI Programming in Games ( Introductory Material )

See also:
Game intelligence predicts your future moves
Use virtual simulations to predict human behavior
Predicting how humans behave
AI solves checkers
AI learns to play 20 questions
Testing the limits of AI in games
Poker AI vs human