Dr. Ben Goertzel's talk at Google, discussing his own work on the Novamente Cognition Engine, an AGI project based on combining a number of knowledge representations and reasoning and learning techniques into an integrative architecture motivated by complex systems theory, and initially oriented at the control of virtual agents in 3D simulation worlds such as Second Life.

The Apply AI Innovations 2007 conference drew together programmers from the games industry, students and professors from academia. The AI in games roundtable covered topics such as intelligent replanning, learning AI, debugging strategies, and opinions on current tools.

An Intel developer discussed model-based computing, and how this relates to multi-core architectures.

"Like the human brain itself, these intelligent applications lend themselves to parallel processing. 80-cores would change the game in a broader sense than just hardware - it will enable new application possibilities."

A computer program that learns to decode language sounds in a similar way to a baby could shed new light on how humans acquire the ability to talk. It casts doubt on the idea that babies are born with an innate understanding of all possible language sounds.

The debate in language acquisition is around how much specific information about language is hard-wired into the brain of the infant, and how much is something that can be explained by relatively general purpose learning systems.

There’s a new site on Game AI called AiGameDev.com (feed). It features daily articles in a blog-like format, including reviews, editorials, and tutorials, not forgetting regular community discussions on game AI.

Here are some interesting posts made recently.

Machine Learning in Games

Game developers are increasingly keen to try ML techniques, but it does take some know-how and experience.

• The Secret to Building Game AI that Learns Realistically
• Alternatives to Online Learning for Actor Behaviors
• Game AI: Beauty and the Beast

Hierarchical Planning & Behavior Trees

Planners have proven themselves very effective in recent games, and hierarchical planners are the next logical step.

• Understanding Behavior Trees
• A Technical Overview of Game::AI++
• The Motivation Behind Game::AI++

Conference Coverage

AiGameDev.com also has summaries of recent events, very useful for catching up with what went on…

• AIIDE ‘07 Conference Coverage
• Pushing the Limits of Game AI Technology
• Apply AI 2007 Roundtable Report

Be sure to check out the site/blog if you’re interested in game AI!

These days, the bots playing poker can't bluff convincingly. "Computers are programmed to perform the best strategy, but bluffing is based on unexpected, illogical actions," says Evan Hurwitz, a computer scientist at the University of the Witwatersrand in South Africa.

Now Hurwitz and Tshilidzi Marwala, also at Witwatersrand, have developed a virtual player that has taught itself to bluff at a card game called lerpa. Their artificial intelligence bot, named Aiden, is based on a neural network algorithm that usually forecasts stock market fluctuations.

Then the researchers decided to play Aiden against three other similarly trained bots to see what would happen. "They began to develop their own personalities - either aggressive or conservative - depending on their past successes,"

AIIDE ‘07 starts tomorrow (Artificial Intelligence and Interactive Digital Entertainment), featuring the most cutting edge research in game AI. The proceedings read like a "who's who" in the field, and there's lot to learn from! Here's a collection of highlights from the conference, and references that can be found online.

Last October, Netflix, the online movie rental service, announced that it would award $1 million to the first person or team who can devise a system that is 10 percent more accurate than the company's current system for recommending movies that customers would like.

The contest has also generated several academic papers, Mr. Bennett said. It has turned out to be more exciting than officials expected.

A computing visionary and leader of the movement to define and elucidate the "great principles of computing," Peter J. Denning is a professor at the Naval Postgraduate School in Monterey, California. He is a former president of the ACM.

""Artificial intelligence (AI) researchers claimed that the mind is a computational process. When they discovered the rules of the process, a computer that followed the same rules would be conscious and intelligent. This claim, often called "strong AI", is not falsifiable. In the past two decades, mainstream AI has focused on falsifiable claims, such as "a neural net can be trained to read handwritten addresses from postal envelopes." In the older terminology, this was called 'weak AI', but it has transformed AI into a strong scientific enterprise.""

A decision tree is a technique for predicting target values from observations.

Motivation

Assume your program has data samples and needs to draw certain conclusions about each of them. This is the case when mining for information in large databases, or trying to find an appropriate behaviour for a particular situation. You can apply decision trees to this problem as long as:

• The data samples each have attributes, either discrete or continuous values. For example, a symbol indicating if it was overcast or not, and the humidity level.
• The predictions must also be discrete or continuous values. For example, the estimated temperature or a prediction of whether it will rain or not.

Decision trees assume that it’s possible to check the attributes of the data samples multiple times, and use this information to refine the predicted value.

Description

A decision tree is based on a hierarchical data-structure, where each branch in the tree represents a condition. This condition typically evaluates to a boolean, with true/false each corresponding to a child node. However, it’s also possible to have more than two child nodes — for example if ranges are used as conditions. The leaves in the tree store the predictions for the target value(s).

A simple traversal algorithm is also necessary to traverse the tree, evaluating each decision and then selecting the appropriate sub-tree to enter. The algorithm is then applied recursively until a leaf node is reached. This process is rather efficient as very little memory is required to store a tree, and only simple conditional checks need to be evaluated while predicting.

Application

A decision tree can be used in almost any classification problem (to predict discrete symbols) or regression problem (to predict continuous values). They are particularly useful in data-mining because of their efficiency. However, such decision trees cannot solve all types of problems because of assumptions of the hierarchical model.

In practice, to apply the traversal algorithm successfully, a good decision tree is needed. This can be obtained in multiple ways:

1. The decision tree may be edited by an expert.
2. The decision tree can be induced from data samples.

Since expert solutions may take time to develop and tune, supervised learning is often used.

Resources

• See papers about the decision tree in the resources section on AI Depot.

Most of my time these days is spent updating the artificial intelligence knowledge part of the website. Two brand-new overviews of AI techniques have been published recently, complete with pseudo-code and graphics:

• Minimax Search
• Decision Tree

You can subscribe to articles like these by signing up for the combined artificial intelligence feed. Be sure to let me know (using the form below) if you have a particular topic at heart so we can bump it up the list of things to write about.

On a related note, I’m exploring ways to liven up this kind of content and drag it kicking and screaming into the world of Web 2.0. I would appreciate your feedback on the subject:

 Loading …

Any comments are also welcome on the subject.

New technology has been used to plan search and rescue operations for the American air force. The research can be seen as providing a way to combine route planning principles with principles for automatic fault finding. "My research has combined two different but complementary principles for handling complex planning problems, developed within the computer science disciplines of artificial intelligence and formal verification", explains Rune Moeller Jensen.

Several research groups have tried to combine the two principles. However, this has been shown to be difficult. Rune Moeller Jensen has, in co-operation with American colleagues from Carnegie Mellon University, developed a method called state-set-branching, in which the two principles can be combined. "We could show that these search algorithms were more efficient than previous algorithms", he says.

Let’s say your program is in a competitive situation against others, and must predict possible consequences of actions to select the one with the best outcome. This is the case in many logic games like Tic-Tac-Toe, Othello, Chess or Go. The minimax algorithm can be applied here as long as:

• The current state is (at least partly) available to the program. For example, the program knows the position of the pieces on the game board.
• It’s possible to search through successor states in the future. The program knows how the pieces end up when a move is made.
• There’s a way to evaluate the utility of certain states. For instance, knowing when about the winning/loosing conditions.

Since this is a competitive setting, you can assume that the others pick actions resulting in a worse outcome for your program. Then, minimax works by taking the predictions of future states, and working back to determine the utility of predecessor states. When your program has estimated the utility of the next states, it can easily select the best.

Description

Minimax is a policy to select optimal utility actions assuming the worst from other programs. Typically, minmax is combined with a depth-first search algorithm that traverses the game tree, predicting what the opponents are likely to do and what your program should do. As such, there are two different levels in the search tree: 1) for the opponents and 2) for team-members.

1. The level in the game tree dealing with opponents is known as MIN, since they will typically minimize the utility of the outcome state.
2. Conversely, the search tree’s level dealing with team-members is known as MAX, since they will typically maximize the utility of the outcome state.

The minimax search, in effect, minimizes the maximum possible loss, or looking at it the other way, maximizes the minimum gain.

Application

Minimax is applied to many games with great success, especially when the branching factor is small (i.e. there are few options each turn), when the situation is deterministic, and the state is fully observable.

However, in practice, there are significant challenges to applying Minimax to a logic game. Notably, the game tree is usually too large to search until the end, so good estimator functions are required for any state (and not just terminal states). This is not a trivial problem, and significantly affects the outcome of the algorithm. Most state estimation functions are hand written for each problem by experts.

The pseudo-code for a minimax search looks like this:

def minimax(node, depth)    if node.is_terminal() or depth == 0:         return node.calculate_heuristic()    if node.is_opponent():         a = +inf         for child in node.get_children():             a = min(a, minimax(child, depth-1))    else:        a = -inf        for child in node.get_children():             a = max(a, minimax(child, depth-1))    return a

On the bright side, alpha-beta pruning can be implemented easily to improve the efficiency of the search.

Theory

In classical statistical decision theory, an estimator is used to estimate a parameter . Also assume a risk function , usually specified as the integral of a loss function. Given this framework, is called “minimax” if it satisfies:

Resources

• See papers on minimax search in the resources section on AI Depot.

I prefer open source software - the license applied to an open source software project lets me know up front what my usage rights and obligations are.

The Numenta Platform for Intelligent Computing (NuPIC) is free for academic and non-commercial research use, but there is so far no definitive information on commercial licensing costs. As a result of this, even though I like the ideas behind NuPIC, I spend relatively little time playing with the examples. I very much enjoyed Jeff Hawkin's book On Intelligence (Amazon purchase link) and I will probably devote a lot more time to experimenting with NuPIC when all of the licensing issues are nailed down.

This requires a free sign up process. I just registered and I found a dozen articles on topics of interest to me that are now in my reading queue.

I installed OpenCyc 2.0 on one of my test servers last night. It is now Java based, so is (in principle) portable: I'll try modifying the start up scripts for OS X when I have time. There is also now a Semantic Web sub project for OpenCyc.

There are now references to other lined data sources - you will notice this as soon as you start experimenting with the browser based interface.

If you have not tried OpenCyc before, it is a free version of the Cyc product. OpenCyc provides an ontology of the "real world" and many facts and relations dealing with what might be called "common sense" knowledge.

Is there anything you want to know about artificial intelligence? If so, fill in our AI survey online; it’s only one question. You can be as brief or expressive as you like.

As artificial intelligence enthusiasts and developers, we’re interested in hearing what you have to say. There are lots of ideas and content in the pipeline for the AI Depot, but we’re particularly interested in what you want from us.

• http://ai-depot.com/site/survey

Those of you who fill in the questionnaire will get exclusive access to the new content before anyone else! You also get the satisfaction of knowing you helped out in shaping the future direction of this site.

We’re looking forward to hearing from you, but be sure to subscribe to our new artificial intelligence feed to hear from us daily!

I have a 22 year history of working with natural language processing, but for the most part this was a low level of effort (perhaps averaging 3 to 5 weeks a year). For learning (and perhaps for some production work if you extract the parts that you need) I can very much recommend NLTK.

NLTK developers (or aggregators since NLTK is an aggregate of smaller projects, with a lot of new work added) Steven Bird, Ewan Klein, and Edward Loper are writing a complete book on NLP using NLTK that looks good. I wish that I had a good resource like this 22 years ago!

Reuters has a great attitude about openly sharing data and technology. About 8 years ago, I obtained a free license for their 1.2 gigabytes of semantically tagged news corpus text - very useful for automated training of my KBtextmaster system as well as other work.

Reuters has done it again, releasing free access to OpenCalias semantic text processing web services. If you sign up for a free access key (good for 20,000 uses a day of their web services), then you can use my Ruby client library:

# Copyright Mark Watson 2008. All rights reserved.
# Can be used under either the Apache 2 or the LGPL licenses.

require 'simple_http'

require "rexml/document"
include REXML

require 'pp'

MY_KEY = ENV["OPEN_CALAIS_KEY"]
raise(StandardError,"Set Open Calais login key in ENV: 'OPEN_CALAIS_KEY'") if !MY_KEY

PARAMS = "&paramsXML=" + CGI.escape('<c:params xmlns:c="http://s.opencalais.com/1/pred/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"><c:processingDirectives c:contentType="text/txt" c:outputFormat="xml/rdf"></c:processingDirectives><c:userDirectives c:allowDistribution="true" c:allowSearch="true" c:externalID="17cabs901" c:submitter="ABC"></c:userDirectives><c:externalMetadata></c:externalMetadata></c:params>')

class OpenCalaisTaggedText
  def initialize text=""
    data = "licenseID=#{MY_KEY}&content=" + CGI.escape(text)
    http = SimpleHttp.new "http://api.opencalais.com/enlighten/calais.asmx/Enlighten"
    @response = CGI.unescapeHTML(http.post(data+PARAMS))
  end
  def get_tags
    h = {}
    index1 = @response.index('terms of service.-->')
    index1 = @response.index('<!--', index1)
    index2 = @response.index('-->', index1)
    txt = @response[index1+4..index2-1]
    lines = txt.split("\n")
    lines.each {|line|
      index = line.index(":")
      h[line[0...index]] = line[index+1..-1].split(',').collect {|x| x.strip} if index
    }
    h
  end 
  def get_semantic_XML
    @response
  end
  def pp_semantic_XML
    Document.new(@response).write($stdout, 0)
  end
end

Notice that this code expects an environment variable to be set with your OpenCalais access key - you can just hardwire your key in this code if you want. Here is some sample use:

tt = OpenCalaisTaggedText.new("President George Bush and Tony Blair spoke to Congress")

pp "tags:", tt.get_tags
pp "Semantic XML:", tt.get_semantic_XML
puts "Semantic XML pretty printed:"
tt.pp_semantic_XML

The tags print as:

"tags:"
{"Organization"=>["Congress"],
 "Person"=>["George Bush", "Tony Blair"],
 "Relations"=>["PersonPolitical"]}

OpenCalais looks like a great service. I am planning on using their service for a technology demo, merging in some of my own semantic text processing tools. I might also use their service for training other machine learning based systems. Reuters will also offer a commercial version with guaranteed service, etc.

I had a good talk with some of the Metaweb developers last year and started playing with their Python APIs for accessing structured data. I wanted to be able to use this structured data source in a planned Ruby project and was very pleased to see Christopher Eppstein's new project that provides an ActiveRecord style API on top of Freebase. Here is the web page for Christopher's Freebase API project. Assuming that you do a "gem install freebase", using this API is easy; some examples:

require 'rubygems'
require "freebase"
require 'pp'

an_asteroid = Freebase::Types::Astronomy::Asteroid.find(:first)
#pp "an_asteroid:", an_asteroid
puts "name of asteroid=#{an_asteroid.name}"
puts "spectral type=#{an_asteroid.spectral_type[0].name}"

#all_asteroids = Freebase::Types::Astronomy::Asteroid.find(:all)
#pp "all_asteroids:", all_asteroids

a_company = Freebase::Types::Business::Company.find(:first)
#pp "a_company:", a_company
puts "name=#{a_company.name}"
puts "parent company name=#{a_company.parent_company[0].name}"

You will want to use this API interactively: use the Freebase web site to find type hierarchies that you are interested in, fetch the first object matching a type hierarchy (e.g., Types -> Astronomy -> Asteroid) and pretty print the fetched object to see what data fields are available.