September 6th, 2010, by Tim Finin, posted in AI, Google
The University of Waterloo’s computer science club is holding another Google-sponsored AI Challenge this Fall. The task is to write a program to compete in a Planet Wars tournament. Your goal is to conquer all the planets in your corner of space or eliminate all of your opponents ships. Starter programs are available in Python, Java, C# and C++ and support for Common Lisp, Haskell, Ruby and Perl is under development. The contest starts on September 10th and ends on November 27th. Sounds like fun!
Planet Wars is inspired by Galcon iPhone and desktop strategy game. Here’s a Planet Wars game in action.
“Edd Hifeng barely merits a second glance in “Second Life.” A steel-gray robot with lanky limbs and linebacker shoulders, he looks like a typical avatar in the popular virtual world. But Edd is different.
His actions are animated not by a person at a keyboard but by a computer. Edd is a creation of artificial intelligence, or AI, by researchers at Rensselaer Polytechnic Institute, who endowed him with a limited ability to converse and reason. It turns out “Second Life” is more than a place where pixelated avatars chat, interact and fly about. It’s also a frontier in AI research because it’s a controllable environment where testing intelligent creations is easier.
There’s more information in an article on Virtual World News. Apparently the goal is not to build interesting Second Life Bots using a variety of hacks, but to demonstrate human-like behaviour using more principled techniques.
“RPI is looking, initially, at a “theory of mind” for children, specifically with a false-belief test. In the real world, a child (age 4) would be shown a person placing a teddy bear in a cabinet. When the first person leaves, a second person would move the bear to another spot, like a refrigerator. When asked where the first person will look for the bear, they usually answer with the refrigerator due to a lack of understanding of other people. In Second Life, an automated theorem prover and procedures for converting conversational English into formal logic make up the brain of “Eddie,” the four-year-old avatar. When posed the above problem, Eddie responded as the human child would.”
Tomas Rokicki has written up a proof that any Rubik’s Cube configuration can be solved in 25 or fewer moves. In his paper, Twenty-Five Moves Suffice for Rubik’s Cube, Rokicki proves that there are no configurations that can be solved in exactly 26 moves. Taken with earlier results, this means that 25 movies should suffice for any solution.
“How many moves does it take to solve Rubik’s Cube? Positions are known that require 20 moves, and it has already been shown that there are no positions that require 27 or more moves; this is a surprisingly large gap. This paper describes a program that is able to find solutions of length 20 or less at a rate of more than 16 million positions a second. We use this program, along with some new ideas and incremental improvements in other techniques, to show that there is no position that requires 26 moves.”
“Rokicki’s proof is a neat piece of computer science. Heâ€™s used the symmetry of the cube to study transformations of the cube in sets, rather than as individual moves. This allows him to separate the â€œcube spaceâ€ into 2 billion sets each containing 20 billion elements. He then shows that a large number of these sets are essentially equivalent to other sets and so can be ignored. Even then, to crunch through the remaining sets, he needed a workstation with 8GB of memory and around 1500 hours of time on a Q6600 CPU running at 1.6GHz.”
Rokicki is working to establish a bound of 24 moves and thinks that a bound of 20 can eventually be proved.