## Archive for the ‘topics in artificial intelligence’ Category

## Backward induction

All games and all competitions can be represented by trees. Each node represents a place to make a decision, each edge represents a decision that can be made from that node. One of the simplest games we all know is tic-tac-toe. The game tree for tic-tac-toe has an root node with 9 edges. Each edge represents one of the 9 positions you can play if you are player one. The second level of nodes each have 8 edges. Each edge represents one of the remaining 8 positions open to player 2. The paths through the game tree for tic-tac-toe = 9! or 362,880 possible ways to play the game through to completion. So while tic-tac-toe is with in the realm of games the computer can fully solve while playing most games are not. One method used in artificially intelligent games to solve this problem is backward induction.

For example: You get a job transfer to Mars for 10 years. There are two possible jobs on Mars open to your spouse. One job pays $60/year, one job pays $100/year. You know that at the end of 10 years you will both be shipped back to Earth.

A lottery is held every year for the job openings, 1/2 are for the $60/year job, half are for the $100 a year job. Once you commit, that is your job until the trip home. At which point in time should your spouse stop holding out for the $100/year job and take the $60/job?

In year 10 the possibilities are $100/$60/$0 so the $60 job should be accepted.

In year 9 the possibilities are $200 for the $100/year job; $120 for the $60 year job. But if the spouse holds out there is a 50% chance of either. So 50%( $100 + $60 ) = $80. We have then $200/$120/$80. Take the bad job.

In year 8 we have possible earnings of $300/$180 or ( 50% * ($200 + $120 ) = $160 ). The bad job is a better choice than holding out.

In year 7 we have possible earnings of $400/$240 or ( 50% ( $300 + $180 ) = $320 ). Since the $320 is higher than the $240 we should hold out.

In year 6 and earlier it will be better to hold out and hope to do better in next years job lottery, in year 8 on it is better to take either job.

Now there are some big assumptions here. One is that everyone has all the information needed to make the decision. And two that your spouse won’t go stir crazy sitting on Mars with nothing to do. Another assumption which can lead to trouble is that backward induction assumes the players do not collude with each other.

In games you would use the final payoffs for each player to do your backward induction. In business backward induction is commonly used to guess what the competition will do in response to your moves in the market. While backward induction has been very successful in AI and in politics it won’t solve all game tree problems because we don’t always have all the information and there’s more to life than a paycheck.

Papers:

Is good algorithm for computer players also good for human players?

## Cellular Automata

In Wolfram’s book “A New Kind of Science” he studies cellular automata. What is also interesting is the approach he is taking. Rather than take something we know and try to figure out the rules, he tries different rules to see what they will create. While his book was badly received when it came out, other’s have found great success using this approach recently.

Wolfram was hardly the first to use cellular automata to mimick real life. Martin Gerhardt and Heike Schuster created ‘HodgePodge’ a cellular automata to mimic a chemical reaction. They explained it as using a discrete form of a differential equation. Since we have described most natural phenomena with differential equations that may explain why we have not done more with cellular automata. We just haven’t needed it. We may find use for it in things we can not yet easily describe with differential equations.

For example, cellular automata has found success in artificial intelligence in solving echohydraulics modeling problems. Cellular automata is also being used in pattern recognition, image processing, fluid mechanics and bioinformatics.

Cellular automata is simple rules repeated over and over. While one would expect simple patterns to emerge and repetitive patterns to emerge, non-repetitive and complex patterns also emerge in some cases. The two examples shown use only two colors and simple rules. Three colors leads to many more complex designs.

Nested: If either neighbor but not both neighbors in previous row are black-> color this cell black else color it white.

Irregular: If self and right neighbor in previous row are white then self is same color as left neighbor in previous row. If self and right neighbor are not both white then self is opposite color of left neighbor in previous row.

Source code:

Java automata examples

More information:

A New Kind of Science, Talk at US by Stephen Wolfram

CelLab, Cellular Automata Laboratory

A New Kind of Science ( book is available online and free)

Some of the recent controversy about Wolfram’s book

Fractal Geometry

Cellular Automata Links

An Introduction to Lindenman Systems ( related subject )

The Primordial Soup Kitchen

One dimensional cellular automata Java applet

A weakly universal cellular automaton in the hyperbolic 3D space with three states

## Biomorphs and artificial intelligence

I hadn’t heard of Biomorphs until I started wandering through The Magic Machine: A Handbook of Computer Sorcery. I’m brushing up on math and coding now so I can do some new projects this year and this book is a fun way to do it.

[ z = z^3 + c]

[ z = sin(z) + z^2 + c ]

Biomorphs were discovered by Clifford Pickover at the IBM Research Center. Biomorphs are like Mandelbrot functions in that you iterate a simple function over the complex plane. The algorithm is in the 2 example Java files below. Several more besides these two are known to reside between -20 and 20. { z^z + z^6 + c; z^z + z^6 + c; sin(z) + e^z +c; z^5 + c; z^z + z^5 + c; . . . } You should be able to figure out how to create them by altering the two examples in the download file.

Some people breed biomorphs and let them evolve as an artificial life form.

Source Code

biomorphs.tar.gz ( 2 Java source files for the biomorphs above )

More information:

Fractal Geometry

Dr. Clifford Pickover home page

Mad Teddy’s Fractals #2 Biomorphs

## Fractals and artificial intelligence

Fractals are a fascinating toy, one can easily spend an afternoon lost in Mandelbrot or Julia sets. Mathematicians were aware of fractals as early as the 1700s but it wasn’t until we had computers to do the calculations that we really discovered fractals.

Benoit B. Mandelbrot doing research at IBM was revisiting Gaston Julia’s work with fractals (1917) when he discovered the Mandelbrot set. Fractals are simple equations that are recursively computed. These simple equations create complex shapes.

The Mandelbrot function is z = z^2 + c. z and c are complex numbers, z is set to zero, c is the position on the x ( x, yi ) plane. You recursively compute this function to obtain the Mandelbrot fractal. Black is for the numbers that do not escape to infinity, the other colors represent how many loops it takes to escape.

Fractals have found some use in artificial intelligence. In the world of computer games, fractals create plant life, clouds, mountains and other scenery that would not be possible in such detail. Parkinson’s patients are diagnosed by their gait. In 2004 a sensor was developed that measures the patient’s gait, and analyzes the gait using fractals. 2002 fractals were put to use to help predict natural disasters and better model hurricanes. More recently fractal patterns have been found in solar wind. It is hoped this information will allow us to better predict solar storms.

Fractals have been found in Jackson Pollacks paintings and are being used to try to identify real paintings from fakes. They are also being used in image compression. A more fun way to play with fractals is to use them to predict the stock and commodity markets.

Fractals ( Mandelbrot and Julia in Java – source code )

More information:

Fractal Geometry

Fractals

Math on Display, Science News Online

Genius: Benoit Mandelbrot

3D Mandelbrot images

Papers:

The Fractal Geometry of Nature, Mandelbrot ( pdf/ps )

## Graphical models of knowledge representation

Reasoning using graphical models is rapidly gaining popularity. Not just used in reasoning they are also becoming useful in computer vision where they are used to classify objects.

Graphical models include: constraint networks, Markov random fields, belief networks, Bayes networks and influence diagrams.

Traditionally algorithms for these networks have been either inference-based or search based. While inference algorithms are not practical time wise for most problems outside the classroom some of the search algorithms perform quite well. Combinations of these algorithms are being used to solve knowledge representation problems not otherwise practical with just inference based algorithms. Often algorithms are tailored for each specific problem.

The advantages of this method is that all possible outcomes are known and declared in the graphical model. Also the models are easily understood by humans, and the techniques used are well understood.

Nodes on the graph represent facts or states and may be known or unknown, hidden or visible.

Connections between nodes may be hidden or not, they may be probabilities or equations and represent connections between the data.

The graphical representation allows us to decompose the big problem into smaller simpler to solve problems.

More information:

Graphical Model Algorithms at UC Irvine has a large list of software and example problems using graphical models in knowledge reasoning.

There are some Power Point and PDF tutorials you can download from Microsoft

Video lecture on Graphical models

A list of links to several software tools for doing graphical models

Graphical knowledge representation for human detection ( pdf )

Mean Field Theory for Graphical Models

Graphical Models for Discovering Knowledge (excellent beginner’s paper )

See also:

Bayesian logic

Knowledge representation and predicate calculus

Hidden Markov models