Computer Go and Windows HPC Server

Last year, at PDC 2008, the Windows HPC Server team presented a cluster of computers playing the game of Go. This video shows the gorgeous Surface interface:

(If the game of Go is new to you, visit:

http://www.gobase.org

There is lot of information, and the rules of the game. There is a section dedicated only to Computer Go:

http://gobase.org/information/computers/

)

David Fotland is the author of the program of the video. David is a reknowned computer go developer.  There is an email of David, explaining his program and his deal with Windows HPC Server:

http://computer-go.org/pipermail/computer-go/2008-November/017025.html

(That is THE mailing list to follow, if you want to know more the computer go problem). David programmed a MonteCarlo approach, using MPI and the Windows HPC Cluster.

ManyFacesOfGo awarded the computer world championship, last year, running on a Windows HPC Server cluster (competition results). Note: the second program was running using a cluster, too. There is more info about the (commercial) ManyFacesOfGo program at:

http://www.smart-games.com/

2008 was a year full of surprised in computer go arena. Actually, the programs can’t beat a professional or strong amateur human player, but the odds are changing. You can read:

Latest Advance in Artificial Intelligence: Computer Wins a Game Against a Go Master

and the Wikipedia page on Computer Go:

http://en.wikipedia.org/wiki/Computer_Go

After decades of poor results, the computer programs begin to beat strong human players, but there is a lot of improvement to do. The complexity of the game avoids the use of brute force methods: I guess the solution will be a mixture of brute force, clustering, MonteCarlo, and more classical planning methods.

I have my own program framework, AjGo to explore algorithms that can be used in this fascinating game, the “hard problem” in AI board games. This is an screenshot of the main form:

Spanish posts explaining the program:

AjGo- hacia un programa que juegue al go
Computer Go y el programa AjGo

I keep a collection of links about Computer Go at delicious and at my personal site:

http://delicious.com/ajlopez/computergo
Computer Go links

Angel “Java” Lopez
http://www.ajlopez.com/en
http://twitter.com/ajlopez

Artificial Intelligence links and resources

Past Wednesday, I had the pleasure of give an speech about Artificial Intelligence, here, in Buenos Aires, Argentina. The seminar was organized by Club de Programadores. I would like to present in this post the material I presented, examples, related links, resources and bibliography I used to prepare the speech.

Arficial Intelligence is a wide field, and after years of development, it has many different branches, that are based in differen principles and algorithms: symbolic processing, neural networks, genetic algorithms, strong AI, expert systems, fuzzy logic, planning, robotics, etc…

The presentation (in Spanish) can be downloaded from IntroIA2009012003b.ppt. An older but more complete presentation, more complete can be downloaded from: IntroIA200501.zip.

There is a group of peolple interested in Artificial Intelligence, here, in my country, Argentina, more details at:

Inteligencia Artificial en Argentina

During the speech, I mentioned that this year Buenos Aires will host a conference about Applied Computation Intelligence, more info:

Applied Computational Intelligence Conference

For a first view of the many branches and history of AI, the base are the Wikipedia articles:

Artificial Intelligence
History of Artificial Intelligence

A site to visit:

Peter Norvig

A paper, with the ideas of Marvin Minsky, about how could model a mind:

Future Models for Mind-Machines

I don’t agree with Kurzweil’s ideas, but you must visit his site:

KurzweilAI.net

At many points in the speech, I cited a paper that describes the history of Artificial Intelligence, and the chain of commercial failures:

If it works, It’s not AI

A recent and more optimistic article:

Future Watch: A.I. comes of ages

I like Douglas Lenat work at eighties. Currently, he is working on common sense, see:

http://www.cyc.com/

Sites to visit about AI:

http://www.aboutai.net About AI
http://www.pcai.com/ PC AI Free Magazine
http://www.jair.org/ Journal of Artificial Intelligence Research
http://www.aaai.org/ Association for the advance of Artificial Intelligence

Clear lessons, about many topics in AI, with source code examples, at

AI Junkie

Programming Languages

Two programming languanges related to AI are:

Lisp programs can be managed as data
Prolog that uses declarative programming

At the end of this posts, there are info about books on many AI topics, that use these languages in examples (example free books in the web).

I had a prepared example, using  P#, an open source Prolog implementation in C#.

I’m working on a Lisp interpreter, see AjLisp- a Lisp interpreter in .NET.

Also:

AI Programming (Lisp)
AI Programming (Prolog)

Fuzzy Logic

I used an example from:

Fuzzy Tech http://www.fuzzytech.com

Rule based systems

I didn’t show an example, but you can visit:

Jess Java rule based system (it uses the Rete algorithm).

Machine learning

Some links

UCI Machine Learning Group
Machine Learning in Games
Machine Learning (AI on the Web)

Planning

I mentioned the problems we faced with planning. Some links:

What is Partial-Order Planning?
Review of An introduction to Least Commitment Planning
Selected History of Partial Order Planning, Part 1 (Sacerdoti was my first reference in this topic)
Selected History of Partial Order Planning, Part 2

Neural Networks

I showed a demo of this commercial product:

NeuroSolutions

An example with ants controlled via neural networks that evolve using genetic algorithms, at:

Neural Networks in plain English

Other links:

http://www.inns.org/
http://www.nips.cc
http://www.makhfi.com/resources.htm
http://www.makhfi.com/realworld.htm
http://www.neoxi.com/NNR/index.html
http://www.ri.cmu.edu/pubs/pub_926.html
http://vasc.ri.cmu.edu/NNFaceDetector/
http://www.deepinsight.com/
http://satirist.org/learn-game/systems/neurochess.html
http://satirist.org/learn-game/systems/go-net.html
http://satirist.org/learn-game/systems/gammon/
http://www.20q.net/ Twenty Questions Neural-Net on the Web
http://gpdev.net/NeuroDriver_bpnet.html
http://www.codeproject.com/csharp/neural_dot_net.asp
http://www.codeproject.com/dotnet/simple_ocr.asp
http://www.codeproject.com/script/articles/list_articles.asp?userid=441940

Genetic Algorithms

An introduction to read

Genetic Algorithms in plain English

I showed my example:

AjGa- a genetic algorithm library

 

More links:

Galib genetic algorithms library http://lancet.mit.edu/ga/
http://delicious.com/ajlopez/geneticalgorithms

Genetic Algorithms and Genetic Programming (lot of links)
What is Genetic Algorithms?
Genetic Programming
Genetic Algorithms
Survival of the Fittest: Natural Selection with Windows Forms  (.NET)
An introduction to Genetic Algorithms In Java
AIAI Technology Genetic Algorithms
Genetic Algorithms and the Traveling Salesman Problem (C++ for Windows)

Evolutive Programming

I play with my example

Playing with evolvable programs

I run the example from AI_Life. It uses neural networks, genetic algorithms, pursuit behaviors. 

Games and Artificial Intelligence

First, board games.

The project Reversi is an implementation of MinMax algorithm using Alfa Beta pruning.

In Connect Four and Learning Draughts there are simple learning algorithms.

The current state of game and AI:

http://www.cs.ualberta.ca/~games/

Microsoft research group:

Applied Games

There is another branch: AI in video games:

Game IA

What is BattleCode-

Artificial Intelligence and Computer Games

AI- AAAI Library online

Game AI for Developers — AiGameDev.com

State machines are used in behavior simulation, you can read

State-Driven Game Agent Design

 

Computer Go

I showed my AjGo program:

AjGo- hacia un programa que juegue al go

Another link:

Computer Go in Microsoft

There is another research group at Beijing:

Craking Go with Feng-hsiung Hsu

My links about Computer Go http://delicious.com/ajlopez/computergo

All about Go http://www.gobase.org

Artificial Life

A fascinating topic. One project to study

http://life.ou.edu/tierra/

Images at:

http://life.ou.edu/pubs/images/

Other interesting project:

Darwin at home it uses Java-based Fluidiom 

Robótics

I showed the video:

Que lindo el guaguau- BigDog de Boston Dynamics

More links:

http://delicious.com/ajlopez/robotics

GRASP Laboratory of Robotics Research and Education @ Penn
Microsoft Invisible Computing
Concious Robots
Robotics Studio at Concious Robots (con algún foro en español)
An introduction to Programming Robots with Microsoft Robotics Studio
Wimo: The Windows Mobile Robot

Bibliography

Nils J. Nilsson wrote many books about AI. I recommend this book as a first look to the topic:

Artificial Intelligence: a new synthesis

An online Nilsson: How Are We To Know-

One book I commented in the seminar is the classic by Russell and Norvig (great historic notes at the end of each chapter):

AI- A Modern Approach

Other one by Norvig

Paradigms of AI Programming

 

If you are interested in declarative programming and AI, you must read the classic by Bratko:

Prolog Programming for Artificial Intelligence

Free books online:

Free Artificial Intelligence Books (there are books of other topics, computer science, mathematics, science, etc…)

More links

In my site, I keep links about AI

AI Links
Neural Networks links
Computer Go links

This century, I began to collect more links in my Delicious:

http://delicious.com/ajlopez/artificialintelligence

Angel “Java” Lopez
http://www.ajlopez.com/en
http://twitter.com/ajlopez

Applied Computational Intelligence Conference

There is an active Artificial Intelligence group in the University of Palermo, here in Buenos Aires, Argentine. They are organizing a congress on Applied Computational Intelligence. More info in the site:

Applied Computation Intelligence Conference

 

Applied Computational Intelligence Conference

The Conference will take place in Buenos Aires City on July, 23rd and 24th, 2009.
The purpose of the Conference is to analyze the discipline’s state of the art from a practical application point of view, in our country and abroad; to generate a debate between national and international peers about the central problematic of this subject and to promote the integration of professionals, researchers, enterprises and industries, within an innovative framework orientated towards the community benefit.
Contact:
Tel: +54-11-5199-4520
E-mail: cica@palermo.edu

The topics are:

• Genetic Algorithms Applications (GA)
• Web Intelligent Browsing (WIB)
• Modelization by concepts
• Industrial and financial applications of Computational Intelligence
The Conference will focus on those successful practices and strategies that may represent a significant advancement in any of the topics mentioned. It is suggested that authors should enclose a description of their work, as well as any findings in the field and details of future research. It would be advisable that all findings may come from centers where specialized resources are developed. It is expected that the papers presented deal with the above mentioned topics. However, papers that may not be directly concerned with those topics, but with the main theme of the Conference, will also be considered.

More about the topics:

http://www.palermo.edu/ingenieria/Congreso_inteligencia_computacional/topics.html

Gregory Chaitin and Noam Chomsky are part of the Honarary Committee

http://www.palermo.edu/ingenieria/Congreso_inteligencia_computacional/committees.html

Robert C. Berwick and Stan Franklin will be speakers. Berwick with “Cons forever: Language at the Core of Human Intelligence”, and Franklin topic is: “If you want smart software, copy it after a human”

It’s very interesting that this kind of congress is being organized in my country, Argentina. In this Internet times, the face to face relation still stands. I hope this event will be a success, and a key point to consolidate the AI research in Argentina.

Angel “Java” Lopez
http://www.ajlopez.com/en
http://twitter.com/ajlopez

AjGa: a genetic algorithm library

I was coding a genetic algorithm library, using C#. The code is in my AjCodeKatas Google Code project, at:

http://code.google.com/p/ajcodekatas/source/browse/#svn/trunk/AjGa

The main project is AjGa (with AjGa.Tests for testing):

The main interfaces are:

I use generics, with two generic types: G, as the gene implementation type, and V, as the value type (e.g. int, double), that it will be used to catalog the genomes.

IPopulation is a colletion of genomes.

IGenome  is a collection of genes, that is evaluated to value.

IEvaluator is in charge of evaluate a genome.

The implementation of IEvolution runs generations over a population, employing mutator, crossover operators, to change the population composition after each run.

There are operator interfaces, to generate one genome, mutate an existing one, or apply a crossover over two genomes.

To test the ideas, I implemented a project with gene, genome, and operators, to attack the classical Travelling Salesman Problem:

In this example, an evaluator has a list of positions of cities to visit:

 

    public class Evaluator : IEvaluator<int, int>
    {
        private List<Position> positions;

        public Evaluator(List<Position> positions)
        {
            this.positions = positions;
        }

The gene type is int, and tha value of each genome is expressed as a int. The genome keeps a list of integers, representing the ordinal number of the cities to visit:

 

    using AjGa;

    public class Genome : BaseGenome<int, int>
    {
        public Genome(int size)
        {
            for (int k = 0; k < size; k++)
            {
                AddGene(k);
            }
        }

That is, each gene is an int, and a genome with 2, 0, 1 represents: visit the third city, then the first one, and finish the trip in the second city.

You can run the WinForm project, to test the library:

The above run has a random distribution of cities. The cities can be distributed in a grid:

This way, you can test the efficient of the algorithm to reach the optimum solution.

If you want to implement a new GA project, you should:

- Define the gene type

- Define the value type

- Some operators (creators, mutators, crossovers)

Tests are green:

Code coverage in fine:

I spent 4 hours in the first version, 3 hours exploring TSP, and around 8 hours preparing and tuning the TSP WinForm application.

As usual, I enjoyed write this software!

Angel “Java” Lopez
http://www.ajlopez.com/en
http://twitter.com/ajlopez

Playing with evolvable programs

Yesterday, I wrote a codekata-like solution. I like the idea of evolvable programs (having agents with programs that evolves, in a simulated environment), so I created a solution dedicated to experiment with a proof of concept example. It’s written in C# using VS 2008 and its test support. I’ve commited to my ajcodekatas google code project at:

http://code.google.com/p/ajcodekatas/source/browse/#svn/trunk/EvolveExample

The solution is EvolveExample:

(If you don’t have the test features installed in your VS, you can remove the Evolve.Test project).

The core classes reside in Evolve class library project:

Animal represents the agent. It has a list of Instructions, that are randomly generated. An animal habitates a field with food. Its program has instruction to Eat, Move East, North, West, South, or Predate (get food from other animal in the same cell in grid). Each instruction has a cost: one point of energy. Eat is an instruction to get 10 points of energy or less, from the food in the current cell. Predate get 100 points of energy or less, from any other animal in the same cell.

To see the program in action, start the Evolve.GUI winform project, select Evolve -> Run menu option. You’ll see:

The field is a grid (in this example, 20×20). Each cell has a food level (green is full, blank is empty). At the left, a list shows the best animals and its program. The animals are ranked according to their energy levels at the end of a simulation run. The program continues to run more simulations, with new fields. In the next simulation, the population is ordered by descending energy, the top performers are included in the new simulation, they are are mutated, and some new animals are injected with new random programs.

During a simulation, the food level and the best animal information is displayed in the status at bottom.

With Food and Population menu options, you can set the food level to seed in the field at beginning of each simulation, and the number of agents to include. The settings are for the next Evolve -> Run. Evolve -> Stop option can be used to terminate a serie of simulations.

Next steps

This is a first example, a proof of concept solution. I have some ideas to explore in future versions:

- Having a more interesting instruction set, with conditionals, sensoring the environment. I like to add something like “If there is food at north, go north”.

- Settings (field size, food level, initial energy) via a form, and serialize the values in .XML files

- Serializes the results and populations to .XML files

- Evolution in a cluster. I could use AjMessages, AjAgents, or MPI over HPC cluster, to simulate evolution in a grid/cluster of machines.

As usual, I had fun writing the code!

Angel “Java” Lopez
http://www.ajlopez.com/en
http://twitter.com/ajlopez
http://delicious.com/ajlopez

Artificial Intelligence meeting in Buenos Aires

 Last Wednesday Nov 26th, I attended to the first meeting of Artificial intelligence in Buenos Aires. The motivation for the meeting was to contact other persons interested in AI, and begin to form a group of interest, coordinate activites, or simply, exchange opinions and knowledge about AI.The assistants:Hernán Moraldo, ten years ago he began programming games, now he is dedicated to the mathematical world, he worked with artificial vision, and now he works for Wolfram Research, the company that develops Mathematica.Marcos Leguizamón, programmer, interested in electronics, member of the list of Robot Developers, currently he’s developing games for Sabarasa.Javier Otaegui, who is one of the founders of Sabarasa, company dedicated to the creation of games, appeared under other “two hats”: founder of Think an App, a new enterprise that solves difficult problems, using artificial intelligence (they are using genetic algorithms, in an application for an oil one), and as a member of ADVA, Association of Developer of Videojuegos of Argentina; the next year they’ll accept papers for its annual congress, including the subject of artificial intelligence for games (already I had published something on ADVA in Exhibition of Videojuegos Argentina EVA 2008)Manuel Aráoz, student of ITBA, Technological Institute Buenos Aires, interested in artificial intelligence , but specially on the mathematics.Néstor Balich, that knew the meeting by the list Robots Developer, he’s interested in Artificial intelligence, professor and investigator in robotics, he presented his site dedicated to Robotics and Artificial intelligence http://www.robotia.com.ar/You can imagine the enthusiasm and interchange of ideas. We were spoken on the shortage of AI programmers in Argentina, the “gap” between academic and the practitioner, the different supports for entrepreneurs in my country, the programming languages that are used in AI, companies that need AI, AI in the world, AI and robotics, congress of Applied Computacional Intelligence , next year in Buenos Aires, AI in games (I mentioned Computer Go), the difference between producing “papers” and working in AI, etc. We were discussing algorithms in games, AI ones and others that no, like path finder, and state machines. The use of AI in the implementation commented of Popego, apparently, programmed by the people of Zauber. Software with AI in my country, Argentina, related to robotics, robotic soccer, developments using Prolog (in the University of the Comahue), AI activity in universities (like the work of Amandi in the University of the Center). Also new applications of AI like those of Evolution Robotics, one of whose vice-presidents is Argentine. We talked politic subjects, like the lack of relation between the industry, the government and the academic activity, and the next “technological pole ” of Buenos Aires, the Metropolitan Center of Technology, located in Parque Patricios.I showed something of Computer Go in HPC Cluster, some functionality of Microsoft Robotics, and a great of Big Dog of Boston Dynamics (I did not mention AjGo and AjLisp).As conclusion, we see that we have points in common, the desire to make things, so as “outcome” of this first meeting, we created a list in Google Groups, to coordinate the group and to exchange ideas on Artificial intelligence. The language of the list is Spanish, if you are interested in AI, you are welcome toIA GrupoMy personal outcome, is this post, a summary of the meeting, Spanish version atInteligencia Artifical en Buenos AiresAngel “Java” Lopez
http://www.ajlopez.com/ex
http://twitter.com/ajlopez