Herself’s Artificial Intelligence

Poindexter made prediction markets common knowledge when he created his market to predict terror attacks. Prediction markets work like stock exchanges. Lots of people buy stock in what is expected to do well, and sell off what is expected to do poorly. They have been used to predict political and sports event results among other things.But as those of you know who watch the stock market, mob intelligence is often more like lemming behavior than pooled intelligence. That said, many well known, successful companies have been successfully using predictive markets to decide what new products to bring forth; HP, Corning, Intel, MS, Google, WSJ and more.These markets do best when there is actual money or some other incentive to gain or lose.Online examples include:Iowa Electronic MarketsUS News Futures

See also:
Mob Intelligence

More information:
The Prediction Company
The Fizz-dom of Crowds
Google’s Lunchtime Betting Game
Putting crowd wisdom to work, Google
Here’s an Idea: Let Everyone Have Ideas, NYT
Oddhead Blog: Prediction Markets, Gambling, Electronic Commerce, Artificial Intelligence
Predictify

Papers:
Prediction Markets, Journal of Economic Research ( pdf )
Google Prediction Market Paper ( pdf)

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

Natural language processing allows people to interact with computers and robots in a more natural way. There are five major areas in NLP: Speech recognition, Language processing, Language understanding, Language generation, Speed synthesis.

Speech recognition consists of breaking down speech into words. Most modern systems require a pause between words so the computer knows where one word ends and another begins.

Language processing is breaking down of words it is then parsed using grammar rules and a lexicon. A lexicon is a list of words to be understood by the computer and attributes for those words( noun/verb/etc ). The grammar is a formal description of the language. It might have rules explaining how sentences may be formed example Subject->NounPhrase->Verb or NounPhrase->VerbPhrase etc. Sometimes you have parsers that break a sentence down into parts and a parse tree. Other times you have a recognizer which parses the sentence and determines if it is valid with the grammar and lexicon supplied.

Understanding is mapping the processed language onto a representation that the computer can handle.

Language generation is the formation of an answer by the machine. Usually these are predefined phrases.

Speech synthesis is the verbal expression of the language generated and is also usually predefined phrases.

Language is difficult to parse structure can be as simple as two word sentences or complex lengthy sentences. By using a limited grammar and lexicon this can be simplified.

Language can also be ambiguous words can some times be nouns or verbs ( a run – to run ; a program – to program ). This can create multiple possible parse trees from a single statement.

Metaphors are not well translated by machines.

Parsers can be top down, bottom up, or finite state machines. Top down parsers start with sentences and work down to words. When every word has been classified it is complete. Bottom up parsing starts with words applying rules to parse them into verb and noun phrases until a sentence can be fit into a sentence rule. Finite state machines work from the bottom up. Finite state machines identify words and work through a graph like structure to form the sentence.

NLP is used in speech interfaces, text processing, language translation and information retrieval. It is an important tool in the war against spam.

More information:
Stanford School of Engineering, Natural Language Processing Online Course
Simon: Open source speech to text software
Natural Language Processing Blog
Getting Started with OpenNLP ( Natural Language Processing )
Has voice recognition finally come of age?

See also:
Darpa builds speech translator
Neural net learing vowels

Whether you are writing a game with artificial intelligence or a life form to evolve you have to decide how and when predators catch their prey. Should the predator try to catch the prey? If so what’s the best way? And the predator must watch out for obstacles during the chase, we don’t want any Wiley Coyote type accidents with our predators.

About the simplest method the predator can use to meet up with the prey is to see if the prey’s x & y positions are above or below the predator’s.
Prey ( 3, 6 )
Predator ( 5, 1 )

if ( prey_x > predator_x ) { x++; } else { x–; }
if ( prey_y > predator_y ) { y++; } else { y–; }

So the first pass through the predator moves from ( 5, 1 ) to ( 4, 2 ).

A bit more natural appearing predator chase would be to use line of sight as the path to move towards the prey. Bresenham’s Line Algorithm is usually used for this. While this is not more effective than the previous method it is more natural appearing. It is also more steps to compute.

prey current position ( xp, yp )
predator current position ( xP, yP )

x = x position to move to
y = y position to move to
dx = xp – xP
dy = yp – yP
Adx = AbsoluteValue ( dx )
Ady = AbsoluteValue (dy )

if ( xp > xP ) stepX = 1 else stepX = -1
if ( yp > yP ) stepY = 1 else stepY = -1

if ( Ady > Adx ){ //the y distance from prey is larger than the x distance

fraction = 2*dx – dy;

if (( yP != yp ) && ( fraction > 0 )){
x += stepX
}

y += stepY

}else{

fraction = 2*dy – dx;

if (( xP != xp ) && ( fraction > 0 )){
y += stepY
}

x += stepX
}

Sometimes instead of having the predator chase the prey it is more effective to have the predator intercept the path of the prey. To do this the velocity as well as the position of the prey must be taken into account.

//figure out when we can reach the prey
dvx = vxp – vxP //difference in x direction velocity
dvy = vyp – vxP //difference in y direction velocity

dx = xp – xP //difference in x positions
dy = yp – yP //difference in y positions

dtx = dx/dvx //time away from x intercept position
dty = dy/dvy //time away from y intercept position

//calculate where prey will be at that time
x = xp + vxp*dxt
y = yp + vyp*dxy

//use above Bresenham’s line algorithm to aim for that location ( x, y )

More information:
Line Drawing explained
Bresenham’s line algorithm

Genetic Algorithms create agents who compete to find the best solution to a problem using evolution.

Agents are initially created either using the best chromosomes from a previous run or a random mixture of chromosomes. After each round we evaluate each agent to see how well he has done. We then mix up the genes by switching among our best agents and or adding in some mutations. We repeat this for a set number of rounds or until some goal is reached.

If only gene switching is done and no mutations are entered into the population the agents will often only find local maximums not global maximums. If the number of agents is too small a solution may not be found.

Simple Genetic Program – you have predators, prey and food for the prey. When either a predator or prey reaches reproduction energy 2 of 3 genes are passed directly to the child, one is random.
GeneticLife.java

See Also:
Bioinformatics Blog: Genetic Algorithms: A Quick Tutorial
Racing with Evolutionary Algorithms