Rules-Unknown Artificial Intelligence Competition

OOglyDOOde writes: "This link points to a competition being hosted by a company that makes research on artificial intelligence. The task? Build a program that can play a number of games whose rules are totally unknown -- and earn the best score while competing against various opponents. Your program is told the possible choices available, when it should make a move, what did the opponent do; and what was your score for the last turn. There are no entry fees yet there is a cash prize. Submissions can be done in various languages, or in Linux or Windows binaries." This is certainly one of the odder ones I've ever seen, but has interesting prizes (trip to Israel) and rules (fairly broad entry categories).

My Statistics Professor Has Already Done This

I took a statistics course at BYU. My professor, Dr. Tolley, with the help of his "31337" kids, built an AI system that played Quake. Each possible move was designated as a random variable, and each random variable was weighted according to its success in keeping the player alive and killing the other player. The code would randomly try different actions with the game interface (walk forward, fire weapon, duck, etc.), and then register what worked and what didn't. At first, the computer-controlled player would just stand there. After getting blown apart a few times, it would start jumping to the left, and then ducking, etc. Eventually, it "learned" that it had its greatest chance for survival if it immediately ducked and went behind a box. It then learned to wait until someone walked around a corner, and then it would fire its weapon in the direction of the corner. Finally, it learned that coordinates of the game contained the "respawning" positions, and upon fragging the opponent, it would run to the next respawning point and wait until the player showed up there, blowing him away upon entry into the game.

This code could be similarly adapted to any game, inasmuch as the code can register a table with all the possible moves provided by the interface. It doesn't even have to know what those moves do; it only needs to know if, by doing certain moves according the "state" (or the attributes) of the game, it gains points (or stays alive or whatever) or loses points. The moves are then given a distribution weighting factor. Then, the algorithm just needs to approximate the game state with the registered table entries, determine which moves have the highest "survival rate" based on the current game attributes, and then perform those moves.

Depending on the game, it may take a long time before the random variable distribution table gets populated to the point where the algorithm can make "intelligent" decisions, but it works nonetheless.

Even if I could write this program i wouldn't...

...for all I know the crazy Israeli army/government will use the code to write programs to further their inhumane agenda. Think about it for a second. Where should we move our tanks, guns, planes and other US Tax payer supported weapons to target the Palestinians.

Going through UN archives or resolutions, even the United Nations condemns Israel for taking the land by force the way they did. And what's more ridiculous, is that now they say "You palestinian's shouldn't fight us, we're ready to make peace on our Israeli terms". Ridiculous! That's like me walking into Taco's home and kicking his butt out and then when he fights back, I cry to all of Slashdot saying he is psychotic. And when that's over, I tell him that he can live in the mulch pile in the back which I sleep in his room.

I know this message will get moderated down to -1, and is it doesn't people will sit here an attack me. Both sides have done wrong, I just think the people who started it (Israeli's) should take their stuff and walk away. Didn't the holocaust help them realize anything? What's ironic is that the holocaust of 21st century is being conducted by the Israeli's and our US taxpayer money supports them with weapons!

Ultimate lameness...!

some design specs for potential participants

After reading the guidelines to the contest, I figured I'd offer the following models/design specs for those interested in participating:

• Understanding how the Brain works [tbiguide.com]
• When will computer hardware match the human brain? [transhumanist.com]
• How your Brain Works [howstuffworks.com]
• How the Human Brain Developed and How the Human Mind Works [solbaram.org]
• Theory of Sequentially Timed Learning [accd.edu]
• If your toaster had a brain [lycos.com]
• neuroinformatics (please don't confuse with clam-baking) [nih.gov]
• Brain Implants Control Computers [slashdot.org]

Some black humor

If you win, you can win a trip under the bomb in israel. And if you die in this second game, they keep the source.

How will they do this?

From the detailed information on their web-site:
A round-robin tournament will be held to select the winner of the Learning Machine Challenge. All combinations of players will take part in all games, of which there will be between six and twelve.

As I see it, they plan to let every contestant play against every other, on 6-12 games, several thousand moves each.

Where will they find the time to do this if they get more than just a few dozens of entries?

Interesting

I don't claim to be an AI guru, but don't programs/computers live and die by rules? (Bad example: HAL in 2001. Rule: Complete Mission. Obstruction: Humans.) The AI could only adapt so much...

The simple solution

I'm going for the easy answer: If my score is an even number the answer is yes. Otherwise my answer is no.

Even more interesting...

...was the other information on the AI site about how they are working on the Child Machine HAL [a-i.com]. Can you teach them how to do Java? In that case I could "work" from home more often...

User-submitted binaries?

Will these programs be run in a sandbox? They're accepting user-submitted binaries, so I would hope so. To be completely fair, the submitted programs should be able to do nothing but read and write from stdin/stdout, otherwise they may do any number of things. Even if they are restricted like that, the judging program had better not having any buffer overflow vulnerabilities. ;-)

Somehow, I don't get the feeling that these people have planned this very thoroughly. There are other little things that don't quite seem right, too...

Easier than I feared

The first question that popped into my head was "How do we know what the opponents move means?"

I was under the misconception that at each turn in the game, the judge will inform the player of all possible moves (as in chess, checkers, or the like) but looking at the specification, it seems that the moves are detailed at the outset of the game, and then are available to each player at each stage in the game.

now the odd thing to me is the measure of 'state' in the game. Is the score that's returned after each move the current cumulative score, the score for that move alone, or what? Also, what is the goal of the game? It would be short-sighted to assume it's to amass the highest score. In effect, the score is just another input variable, along with the opponents move, which may or may not be useful for judging what is a good move or a bad move.

For example, if you were trying to make an algorithm to solve the A8 puzzle (the 'sliding tile puzzle' with 15 tiles and 16 spots), and the computer judged your score by totalling up manhattan distances to the goal state, that may or may not be a fair scale of how many moves away you are from winning in an ideal case.

The system is still underspecified. Without knowing what 'score' means, and whether it is an estimate or a deterministic function, then the project is pretty much a game of luck, and coding is not an effort of skill.

Offtopic: Trip to Israel

Sorry for posting off topic, but I'm not sure if a trip to Israel is that desirable as a prize at the moment, given the rather unstable situation there.

Of course, there may be some connection between the prize and the game ("win a conflict where you've got no clue of the rules", that pretty much sums up the problems of both parties in the Middle East).

The game is Slashdot, the score is Karma.

I wonder what will happen if you let one of these entries loose on slashdot? Would you get intelligent posts, or intelligent trolls? Imagine such a program accumulating more karma than Jon Katz. That would be a boost :)

But seriously. How can one consider this contest artificial intelligence? It's not like the entries have to be intelligent. They just have to be logical and well designed, and good at pattern recognition.

Look at chess as an example. This is like having a chess computer that has to learn the rules. Compared to playing chess (which is computable), learning the moves is relatively easy.

Paranoia

Don't you think this could be used for piloting weapons ? The site is dead at this time so I can't get more insight. yours, Britney

This should prove entertaining.

Heck, I'd like to see a competition where HUMANS play a game where they don't know the rules. That could be just as intereting.

Calvinball

Heck, I'd like to see a competition where HUMANS play a game where they don't know the rules. That could be just as intereting.

It's called Calvinball, and it's the sport of kings.

That recall me a couple of clever hack...

...where the problem was to make a program that played the old paper/rock/scissor game.

The entries had to be given in the form of a subroutine that played the next move (given the current score and the history). The judges were linking two of them together and run the resulting binary.

Of course, there have been an entry that looked in the stack and modified the scores.

But the greatest was one (IMHO) that fork()ed and returned one possible response in each of its child. At next turn, the one that did not make the point (ie: had top score), exit()ed.

Mind-blowing. Found the link [ualberta.ca]

That program was the "Fork Bot"

Cheers,

--fred

AI?

Give me a woman's brain anyday!
Sincerely, Mike Bouma

Why not pick a real problem?

There are enough real, interesting problems out there to choose from; why pick some company's idea of a contest? Work on Go, write a nice chess player, do something interesting with data mining, etc.

random fortune...

Probably irrelevant, but a fortune came to my mind when reading that submission:

In the days when Sussman was a novice Minsky once came to him as he sat hacking at the PDP-6.

"What are you doing?", asked Minsky.
"I am training a randomly wired neural net to play Tic-Tac-Toe."
"Why is the net wired randomly?", inquired Minsky.
"I do not want it to have any preconceptions of how to play".
At this Minsky shut his eyes, and Sussman asked his teacher "Why do you close your eyes?"
"So that the room will be empty."
At that momment, Sussman was enlightened.

Re:MOD UP!

I second that. This is a reference to a Koan found in 'Escher, Goedel, Bach, an Eternal Golden Braid' by innimitable Douglas Hoffsteder/

Otherwise known as the seminal work of AI philosophy.

This is truly on topic, moreso that the un-enlightened could ever know. ask yourelf: Are my mod points the mod points of the un-enlightened? if no, please mod up the parent's parent as +1, Insightful.

thankyou.

All Sample games only work by Collusion!

They give 3 samples, rock scissors paper , prisoners dilemma, and cooperation. The only way to gain advantage above random in Rock Scissor Paper is to collude with the other player for wins. The cooperation game gives points if the two players pick numbers sufficiently close to one another--again the only win vs random is to collude with the other player. Finally, the prisoners Dilemma has the odd property that the best score comes from colluding with the enemy. Can this be a coincidence? What are they aiming for here? See how many people are smart enough to write a bunch of programs that collude with themselves?

hmm

Sounds like it's time for a genetic algorithm plus a bit of matrix game theory.

Damn

Pity I can not program computers. This looks like a nice challenge.

How many actual AI researchers reading slashdot?

I mean how many real world CS people studying AI reads Slashdot?

Doing that and dumb enough to waste his time with this. Count me one.

tit-for-tat algorithm

If this is a 2+ player competition and they're the right sorts of games (like the rock-paper-scissors game that it mentioned), whoever wins it might have to figure out a way to consistently beat the tit-for-tat algorithm.

Tit-for-tat [umich.edu] is one of the dead simplest game playing algorithms, and collectively it's one of the most successful.

It's based on the rule of "always do what the other player did last move". Under most circumstances it's impossible for it to actually win a game because the other player is always one step ahead. But its strength is in winning tournaments.

While it always loses, it never loses by much. This is different from other algorithms which usually have about as many weaknesses as they have strengths and will usually flunk out in at least some trials.

If someone can beat it consistently in a tournament situation, they really will have accomplished something in AI. Of course, this whole thing depends on exactly how the rules are structured, the scoring system and the information available to the program.

A lot easier for AI when...

If only God open sourced the brain...

Two thoughts

1. If I win, do I get a trip to the US? (see email address)
2. I wonder whether the winner could visit me.

:-)

Exercise in neural networks

After reviewing the challenge rules, I see this challenge as a simple exercise in neural networks coding.

The challenge is so obscure that any entry submitted will have to deploy a very generic NN and a trainer. this basicly means that after enough training any entry would do sufficiently good at any simple game (such as scissors, rock, paper) but playing anything more complex than
that is shooting in the dark. The interface and the rules of the challenge themselves are too obscure.

If there is someone with a code that could win such uncertainty effectively and efficiently, he'd be stupid to submit it for $2000.

Then again I must give a person that can do something extraordinary as that some credit for not doing something that stupid.

I might know how to win or get an unfair advantage

Seems to me that since it is a round-robin for all contestants (the site was /.ed, but I saw another post claiming that this was the case), all you have to do is team up with a lot of friends and have them enter fake programs into the contest (i.e cheating). These programs will start by identifying themselves with an "ID-string", consisting of, say, the first 10 replies (this can obviously be done generically even with unkown rules, just pick the moves randomly with the same seed). When my program sees this ID it replies a similar code. When the fake programs sees this, they start cooperating with my program (by playing as badly as they can muster). If the fake programs does not get this reply, they start playing as well as they can and will (since there will probably be large element of luck in each game) steal a considerable amount of points from the pool. The "real" program never risks anything since it never sends its own ID before being statistically sure that the opponent indeed is a fake. This method was inspired by a similar trick in the famous Prisoner's dilemma game.

rand()

I took an AI class this year where we had a challenge to use PERL to design a Stratego-playing AI. One of the professors quickly wrote a script that moved a random piece a random direction (verifying the move was legal), and had a surprisingly high win %.

humans?

Hopefully they'll throw in some human opponents, just for comparison sake.

How they pay for the prizes...

They are playing the STOCK MARKET. They buy stocks according to the various submissions, gradually weed out the bad performers, and end up making a pile, with which they can pay the prize and still have a tidy profit.

Wish I'd thought of it!

95% of the solution is written already:

http://google.com/search?q=orwant+EGGG+game+engine [google.com]

The reason for such a generic interface...

Comaparing the main area of research for the company sponsering this competition, and the rules of the competition, I suspect they are going to try to use these bots to make some progress on the Turing test. They defined 'game' widely enough to consider conversation a game. The score is the reward/punishment - relevent and/or sensible responses are rewarded, etc. I suspect they want to give the machines thousands of possible moves, each representing a phrase, and then set them loose 'against' each other, seeing which one can score the highest on the conversation scale.