Herself’s Artificial Intelligence

I am finishing up my reading of ‘The Magic Machine: A Handbook of Computer Sorcery‘ and there were only two programs left to write. I thought I’d wipe the first one out in a day. Heh, it took three.

In a chapter of the book the author discusses early attempts at genetically evolving artificial life. He gives a rough algorithm and states he had all kinds of critters running around in just a few hundred generations. I loosely wrote a program based on his algorithm. 150,000+ cycles, and 36 hours on my computer later, no evolution. I don’t know how he did it? I couldn’t get the algorithm in the book to produce any interesting results.

I did today get a program that has bugs that learn to stay on and follow food lines drawn in the window. It takes about 1500 days ( cycles ) for them to achieve this universally. The source code is linked to below.

Here’s what I learned in my attempts at a very simple genetic program.

If you place food randomly there is nothing to learn. You just end up with a population of stupid bugs. Adjusting the food nutrient content worked better than adjusting the amount of food for controlling population levels and for evolution. Creating more food to meet the population just created lots of stupid bugs. ( I wonder if there is a real life lesson in that? )

If you adjust the bugs DNA when they find food, not just their energy levels they learn much faster.

I hope to do some more complex and interesting evolution programs soon.

Source Code:
Bugs.java

See also
Evolutionary AI for more information and several useful links and papers to get you started.
SantaFe Ants

All these recent studies using neural networks to predict human behavior have found a purpose. They are being trained and used on game users computers to get around network lag in games by predicting the gamers next move.

Lag time is the ping time between you and the game computer. If two players are shooting at each other, he with the shortest ping time ( lag time ) wins. This can be frustrating for people whose networks lag. The neural network will level the playing field.

Gamers know the problem well: in the middle of an awesome, fast-paced battle, the action onscreen becomes slow and jerky. Suddenly, your character turns up dead, and you didn’t see who did it. In massively multiplayer online games, the problem of lag arises when a player’s computer can’t keep up with changes in a shared online world–and it can turn euphoria into frustration. New software being designed at the National University of Ireland, Maynooth, could help reduce the problem and may also have applications in military simulations. . . [ read more Reducing lag time in online games]

Also interested , as always, is Darpa who hopes to use this technology to improve military battle simulations.

More information:
Neuro-Reckoning may reduce mmog time lag
Multistep ahead neural network predictors for network traffic reduction in distributed interactive applications

Designing AI Algorithms for Turn-Based Strategy Games

In action games the AI opponent always has the natural advantage: perfect accuracy and lightning fast reflexes, so the challenge in designing the AI for those games is making it act more human and to be beatable.

In turn-based strategy games the tables are turned. Speed and accuracy are no longer important factors and the cunning and intuition of the human player will easily out match any AI opponent. In fact, it’s nearly impossible to design a AI that can beat an experienced player, but that is not really the point anyway.

The challenge is to make the AI’s attack and defense strategy to appear intelligent and thought out, providing a challenge but letting the player win in the end. Once the player has familiarized himself/herself with the tactics of the AI the game rapidly gets boring, so a certain amount of unpredictability is desirable. . . .

I ran across this article while looking into predator prey chases and thought it might be of interest to some of you.

See also:
Simple predator prey chase algorithms
Predator prey chases using potential functions

Using potential functions for predator prey movement gives a more realistic chase than using line of sight or other line algorithms.

Potential functions are well known in physics and describe attraction and repulsion due to electricity, gravity etc.

Potential_Energy = – Attraction/distance^j + Repulsion/distance^k

A strong attraction will cause the predator to chase the prey, a strong repulsion will cause the prey to flee the predator. Either of these can be set to zero. Predators may only be attracted to prey, prey may only be repulsed by predators. Various prey and predators can be given slightly different numbers for attraction, repulsion, j, k allowing them to behave differently.

To chase or run a character using potential functions use this algorithm:

Move_Predator (){

double attraction = some_constant; // experiment with these, the size of your game
double repulsion = some_constant; // area will determine good choices
double j = some_constant; // try something between 1 to 3 for these numbers
double k = some_constant; // higher number mean smaller results
double x_predator;
double y_predator;
double x_prey;
double y_prey;

//distance between predator and prey
double distance_x = x_predator – x_prey;
double distance_y = y_predator – y_prey;

double distance = sqrt ( distance_x*distance_x + distance_y*distance_y);

//normalized distance vector
distance_x = distance_x / distance;
distance_y = distance_y / distance;

//see what our attraction or repulsion is
double potential = -attraction/distance^j + repulsion/distance^k;

//now use that attraction/repulsion to see how far we move
double move_x = potential * distance_x;
double move_y = potential * distance_y;

//new location for us
double new_x = predator_x + move_x;
double new_y = predator_y + move_y;

}

More information:
The use of potential functions on modelling animal movement
Advanced Movement Model of Crowd Robots ( pdf )

Books:
AI for Game Developers

The game of checkers has roughly 500 billion billion possible positions (5 x 1020). The task of solving the game, determining the final result in a game with no mistakes made by either player, is daunting. Since 1989, almost continuously, dozens of computers have been working on solving checkers, applying state-of-the-art artificial intelligence techniques to the proving process. This paper announces that checkers is now solved: perfect play by both sides leads to a draw. This is the most challenging popular game to be solved to date, roughly one million times more complex than Connect Four. Artificial intelligence technology has been used to generate strong heuristic-based game-playing programs, such as DEEP BLUE for chess. Solving a game takes this to the next level, by replacing the heuristics with perfection.

Test your skills at http://www.cs.ualberta.ca/~chinook/New. The user name is ‘checkers’, and the password is ‘solved2007′.

More information:
Chinook – World Man-Machine Checkers Champion
Paper at Science for a fee