Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 


Forgot your password?
Close
typodupeerror
×
Games Entertainment

Rules-Unknown Artificial Intelligence Competition 176

Posted by timothy from the sorry-not-as-much-as-for-solving-poe-codes dept.
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).
This discussion has been archived. No new comments can be posted.

Rules-Unknown Artificial Intelligence Competition More

Rules-Unknown Artificial Intelligence Competition

Comments Filter:

  • My Statistics Professor Has Already Done This (Score:5, Insightful)

    by omnirealm ( 244599 ) on Sunday August 05, 2001 @10:20AM (#2109608) Homepage
    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... (Score:1, Flamebait)

    by Anonymous Coward
    ...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...!
    • Oh, I don't know... It's more like Taco is renting from Joe, who told him that he would be selling him the apartment. Meanwhile Joe promises the apartment to his cousin Frank, evicts Taco and gives it to Frank. Now Taco keeps coming back and leaving piles of burning shit on Frank's doorstep, and trying to sleep in his kitchen. At which point Frank starts beating him with a baseball bat. Neither side can claim that they are being mature about this, but the problem is that Joe is an ass, and was never held responsible for tooling them both around...

  • some design specs for potential participants (Score:4, Informative)

    by beanerspace ( 443710 ) on Sunday August 05, 2001 @03:33AM (#2112086) Homepage


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

  • Some black humor (Score:1, Funny)

    by Anonymous Coward
    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.
  • 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?

    • It'll be done by a computer program - hence the standard console interface.
      • It'll be done by a computer program - hence the standard console interface.

        I realized that.

        But, let's say we get 1000 contestants.
        Also, they specify 6-12 different games for each, let's say 10 on average.

        This will mean 10*1000 * 999 / 2 matches (when A has played against B, B has played against A) of many thousand moves (let's say just 2000) each.

        A program is required to process at least 10 moves per second. Worst case, this will lead to roughly 1000 million seconds, or 30 years, of computer time.

        When you get more than 1000 contestants, the time required for the match will rise quadratically.

        I realize that the average program will be faster than 10 moves/second, and that you can use several computers to speed things up (from the height of the prize, I gather that their budget is not unlimited, so I think more than 10 computers will be out of the question), but still, if you get a significant number of contestants, letting every contestant play agains very other may be prohibitive.
        • There will probably be fewer than 100 contestants(a typical machine learning conferrence will draw only a few hundred participants including those presenting and I doubt this would atract more attention), and more likely around 20. At 100 contestants, using your other estimates, the time drops to about 114 computer days (at 20 contestants, it drops to about 4 computer days). With 10 computers, thats less than a week. Not unreasonable for something like this.
  • 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...
    • Not necessarily. There are rule based systems ("when I see X, I do Y"), and these can fall apart in unexpected situations. However, this is far from the only way to implement a system.

      One method is with classifier systems, where you evolve the rules that determine the output based either directly on the input, or a chain leading from some input. It starts with a pool of random bit strings which are evolved based on their success. The rule used is determined by a bidding scheme.

      Another method, which is about as general as you can get, is genetic programming (GP). GP involves creating a set of functions and terminals and randomly generating a set of parse trees using them. Each of these programs is evaluated, and based on that the standard genetic algorithm operations are performed for form a new generation. Essentially, genetic programming is automatic programming, if given the right function and terminal set. Unfortunately, it would probably be too slow a process for this competition.

      Both of the above methods have been proved over and over again. Classifier systems, for instance, have been used to run a simulated oil pipeline (with leaks, blockages, etc). Starting from a random population, it achieved human competitive results. Genetic programming has produced results that are not only human-competitive, but also infringe on pre-existing patents. [genetic-programming.com]

  • I'm going for the easy answer: If my score is an even number the answer is yes. Otherwise my answer is no.
  • ...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...
  • 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...
    • The rules state that the programs are not allowed to open network connections (so you can't get more processing power I assume). Because of this they are able to state on their site that all programs will be run on a machine isolated from the network.

  • Easier than I feared (Score:3, Interesting)

    by KFury ( 19522 ) on Sunday August 05, 2001 @03:36AM (#2117860) Homepage
    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.

    • Re:Easier than I feared (Score:1, Informative)

      by Anonymous Coward
      Try reading the specs.

      "Score" is the number of points scored that turn. It is a floating point number between -1 and 1.

      The goal *is* to get the highest score.
      • Try reading the post.

        Imagine in chess where you scrifice a pawn to gain position - in that case your "score" that turn would be negative yet you would be able to gain a higher overall score later as a result. With only knowledge of the "score" for that turn, how can you decide when a sacrificial move might leave you better off?

        • Your program can attempt to make theories about what moves give you what scores in what contexts, test those theories, and if they seem to work, continue with them; if not, try another theory. The program has to be a good scientist - working out the rules of the world in which it finds itself.

          • But with a game as complex as chess, for example, there is no mathematical way that the program could gather enough information over the course of a single game to make that kind of assessment.

            Lose a queen and you never know what it is to not have lost a queen, for example.
            • As they mention in the specs, you will play thousands of rounds for each game. I dont think that they mean that each game will consist of thousands of moves (even with random move selection for both players, chess usually terminates after 200-300 moves), I think they mean that you will play each game thousands of times against each opponent. If you only play a game once, very little learning will be done. This is because all learning requires either instruction or exploration. Since there is no instruction in this contest, all learning must come from exploration and one game would not be enough.
    • "How do we know what the opponents move means?"

      It really doesnt matter so long as the names for the all legal moves are given to you at the beginning. Just think of them as symbols, buttons to push at any given time. You shouldnt be trying to interpret meaning in the moves that are made, only value. It will be impossible to create some kind of high level of understanding about what a move means because the program does not know what the game is. It is possible to learn what values moves have though using some kind of reinforcement learning algorithm. Think of it this way: If your program believes it is in a certain state and its opponent executes a certain move, it should pick the move available to it that maximizes the expected reward

      Is the score that's returned after each move the current cumulative score, the score for that move alone, or what?

      Based on the example used in the specs, I would imagine that the score is for the most recent action if given after each action or cumulative if given only once at the very end. Either way, it will be relevant in the global context of the entire contest since the program with the highest overall score after playing all games against all opponents will be the winner.

      The system is still underspecified. Without knowing what 'score' means, and whether it is an estimate or a deterministic function

      I think its better to think of score like a reward or a penalty. The idea is to accumulate the most reward or the least penalty. As they say in the specs, the program with the highest score is the winner. If chess were to be one of the games(which I doubt it will due to its complexity), the score would probably be 1 for a win, 0.5 for a draw and 0 for a loss, just like at any chess tournament. There would be no intermediate score for taking a queen or getting into a strong position because those things are meaningless after the game is finished.

      coding is not an effort of skill.

      This contest is not about coding, its about learning. They dont care how good you are at writing programs, only at how good you are at designing a robust system that learns quickly. And as I hinted at before, this problem is just screaming for contestants to use a reinforcement learning algorithm.

  • Offtopic: Trip to Israel (Score:5, Funny)

    by absurd_spork ( 454513 ) on Sunday August 05, 2001 @04:26AM (#2120538) Homepage
    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).

    • Well the Palestinian have a clue about the whole thing. The Israelian can't win, as they are not facing an organised army but a population where every kid over 7 is a potential enemy. For Israel to win, they'd have to kill every Palestinian.

      The Palestinian have nothing to loose, most of them are rather happy to die in this war, and the Israelian have everything to loose.
      • Bla bla. Politics. Bla.

        Anyway, as an Israeli I can assure you that the
        "situation" has some really low chances of
        hurting any tourist. Fact: i'm taking the bus
        on a daily basis and yet i'm still alive. And
        I -live- here. So, really. The media just like
        to over bloat things.

        On the down side: Its freaking HOT. Dont get
        here unless you're heat tolerant. I'd take
        a trip to swiss instead at any time.
        • Well I'm sure some places in Israelien territories are very fine and rather safe - but for one many interesting places are in Palestinian territories (and no tourist wants to be taken in a crossfire), and for two I would really hate to provide, with the money I would spend, support to a country who is organizing etchnic cleansing and conquest thru colonization. The same as I would not visit North Korea or Birmania.
    • When you DO go to Israel, it's helpful to remember:

      You are more likely to be killed by a car accident than by a terrorist attack, with the odds being 5:1 against.

      Yes, there are terrorist attacks. Yes, they kill us, and we kill them. Yes, we live our daily lives, and so do they. Don't panic, folks.

    • Heh. That and the fact that I'd rather get a trip to Palestine. Spend my tourism dollars where they go to support a government not bent on genocide.

      Still, who wants to go to that part of the world right now? Is there something about landing in the middle of a shooting-blowing-people-up war that that just says `must-do vacation' to some folks?

      I do like your idea about it being to play out the Middle East peace process. Couldn't be any worse than any of the current players.

  • 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.
    • 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.

      Wrong. Let's suppose this program gets a list of available moves every turn. How is it to even know the board is a 8x8 board and the relations between each square? How is it supposed to know the significance and difference between a king, queen, rook, knight, bishop and pawn? In order to play intelligently, it will have to learn that sacrifices can be a good thing, but is generally bad if you aren't guaranteed an advantage later in the game. That making one little mistake in your tactic/strategy can quickly lose you the game against a strong player.

      Without assumptions you're really screwed. So it very much depends on the interface, how much and what information the program gets every turn. There'll always be some assumptions left too, as what you choose will always have some limitations.

      - Steeltoe
    • It's not like the entries have to be intelligent. They just have to be logical and well designed, and good at pattern recognition.

      All depends on the much debated definition of what is 'Intelligence'.

      Certainly, pattern recognition is a sign (symptom?) of intelligence.

      So, what are you actually saying? What do you mean when you say 'intelligence' ?

      • I mean the Turing definition: something is intelligent when another intelligent being (i.e. a human) cannot tell if it's a machine he's communicating with, or another human
        • something is intelligent when another intelligent being (i.e. a human) cannot tell if it's a machine he's communicating with, or another human

          So for example, you aren't intelligent because I'm confident that you're a human not a machine?
        • Let me see ... Turing NEVER defined intelligence.

          Turing said the following, in his famous paper "Computing Machinery and Intelligence":

          "I shall replace the question [can machines think] by another ..." and goes on to describe the 'Imitation Game', which is so often now mis-labeled 'The Turing Test'.

          He then goes on to say, after describing the imitation game;

          "We now ask the question, 'What will happen when a machine takes the part of A in this game?' Will the interrogator decide wrongly as often when the game is played like this as he does when the game is played between a man and a woman?"

          The problem these days is that when the Imitation Game is played, the interrogator has sometimes picked humans as machines. So, basically, the Imitation Game is worthless as an indicator of intelligence.

          If it can't tell humans from humans then it is useless to try and tell humans from machines.

  • Paranoia (Score:1, Interesting)

    by Anonymous Coward
    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. (Score:3, Interesting)

    by BiggestPOS ( 139071 ) on Sunday August 05, 2001 @03:43AM (#2126665) Homepage
    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.

  • That recall me a couple of clever hack... (Score:5, Interesting)

    by Anonymous Coward on Sunday August 05, 2001 @03:43AM (#2126666)
    ...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? (Score:1, Funny)

    by Anonymous Coward
    Give me a woman's brain anyday!
    Sincerely, Mike Bouma
  • 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.
    • I think the idea is to make an attemp at "meta-learning". In all of the games that you've mentioned, the programmer knows the rules in advance, and the challenge is to see how best to build a system that navigates through those rules. In this contest, the idea is to see how you can capture the "programmers' thinking".
    • As stated in the article, the submission of the winner will be used to improve natural language processing. I think this is **quite** a real world challenge.

      Daniel.

  • random fortune... (Score:5, Insightful)

    by Pelam ( 41604 ) on Sunday August 05, 2001 @03:33AM (#2128459)
    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:random fortune... (Score:1)

      by Anonymous Coward
      And this is one of the reasons Minsky set back research on neural nets for 20 years...
    • Mod that one up folks...

      • Re:MOD UP! (Score:4, Insightful)

        by MOMOCROME ( 207697 ) <momocrome@gmaEULERil.com minus math_god> on Sunday August 05, 2001 @07:09AM (#2131178)
        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.

    • Re:random fortune... (Score:2, Informative)

      by jesser ( 77961 )
      I don't get it. Is Minsky trying to say that using a random neural net doesn't mean that the net won't have any preconceptions?
      • Yes. It starts out with preconceptions, but you don't know what they are. The "right way" to do it is to have uniform weights, so you *know* that it has no preconceptions... but that means using a quite different learning algorithm. It's the difference between random and representative. If you flip a coin ten times, HHHHHHHHHH is just as common as HTHTHTHTHT, but only one is representative.
  • 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?
  • Sounds like it's time for a genetic algorithm plus a bit of matrix game theory.
    • GA won't win. If it's done beforehand, it will optimize itself for specific games. If it's done afterward, it will fall behind early and be unable to catch up.

    • Re:hmm (Score:1)

      by dlkf ( 261011 )
      Actually, this sounds more appropriate for some sort of multi-agent reinforcement learning algorithm. Anytime someone mentions actions, rewards and learning in the same sentance, the first thing that comes to my mind is reinforcement learning.

  • Damn (Score:1)

    by tsa ( 15680 )
    Pity I can not program computers. This looks like a nice challenge.

  • How many actual AI researchers reading slashdot? (Score:4, Funny)

    by exa ( 27197 ) on Sunday August 05, 2001 @04:35AM (#2135959) Homepage Journal
    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 (Score:4, Interesting)

    by jesterzog ( 189797 ) on Sunday August 05, 2001 @06:56AM (#2136471) Journal

    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.

    • Beating the tit-for-tat is easy when you are allowed to submit many entries. Submit a lot of fake progs that defect against everyone who does not reply to a specific ID string (transmitted by the early moves).

      The real prog answers an ID string with something similar and voíla the fake entries becomes nice cooperators. (see my also my earlier post)

    • What are you talking about? Tit-for-tat wins prisoner's dilemma tournaments, not games in general. The name is even based on prisoner's dilemma, it doesn't make sense to call repeating your opponents's last move tit-for-tat in general.

      Also, you could trivially beat it at rock-paper-scissors: just play rock, paper, scissors, rock, paper, scissors, and so on forever. You will win every round except maybe the first one. Finally, if you actually read the rules of this competition, you would find that there's no guarantee that there will always be one opponent move for every one of your moves, so you couldn't even implement tit-for-tat.

  • If only God open sourced the brain...

  • Two thoughts (Score:4, Insightful)

    by Cave Dweller ( 470644 ) on Sunday August 05, 2001 @03:42AM (#2137639)
    1. If I win, do I get a trip to the US? (see email address)
    2. I wonder whether the winner could visit me.

    :-)
    • > If I win, do I get a trip to the US? (see email address)

      Furriners who win a trip to the US shouldn't come unless they also get a get out of jail free card.
  • 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 (Score:4, Interesting)

    by CyberDruid ( 201684 ) on Sunday August 05, 2001 @05:42AM (#2139053) Homepage
    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.
    • Interesting idea, but I don't think it would be unfair, since according to the rules you can enter as many times as you want (don't even bother with friends, unless you want to). Also, I got the feeling from reading the site that programs are pitted against eachother one on one (I don't know for sure, perhaps this is another game rule that could change from game to game?). If this is the case, your "real" program might be subjected to other competitors' real programs and be unable to decline playing with them. Also, the judge program might not allow any identity information through until after your program makes a commitment. Still, assuming enough of the "fake" entries, it might still be possible to gain an advantage by dint of sheer numbers if you entered, say, a million times.

      I suspect, if they ever try this contest again, they'll want to ponder that rule a bit more...
      JMR

      • The point is not to decline playing against the other real programs, just for the fake progs to play to the best of their ability against everyone but you.

        Sending ID will most likely mean making a commitment, but for long and somewhat stochastic games (which I have a feeling that we will be dealing with here), this early commitment will (hopefully) not be enough of a handicap for the fake progs. They will still get points (provided that your algorithm is any good in the first place).

        The real program will only reply an ID string when it is statistically sure that its opponent is a "buddy", thus the real program gets the unfair advantage of getting a few/many easy wins that the programs made by the other contestants will not get, but sacrifices nothing. You will still need a good program to win. This is just how one could (if one were so inclined ;) give it that extra boost.

        //David Fendrich, Swedish AI-dude

    • You can't send arbitrary strings. Read the webpage. You can only look at moves, and make moves when your asked, out of the list of legal moves you're given.

      But you could adapt your idea to this situation. Simply have your "master" program know the internals of all your "slave" programs, so that it can identify a likely slave based on the first few moves. Since it knows the slave's internals, it can beat it 100% if it's actually a slave. If it deviates from the known slave behaviour, well then you need a real algorithm.

      In this scenario, your slaves don't even have to suck. They can use the best algo you can muster, but the master prog will still beat them because it knows what they're thinking. You can even use the same algo in the master when it identifies a real opponent.

      Dead simple to do this if you already have a half-decent algo. Someone want to try it? Easy 2K...

      • Oh, and I just remembered that the judge program can insert moves that are part of the game, but not initiated by your opponent. This means you don't know if the opponent made the move or if the judge did it. So you'll need some fuzzy matching on your identification algorithms... hmm. Maybe not so easy.

    • Of course, playing as "badly as they can" implies the same knowledge of the game as playing well, if you want to do better than random chance. To play badly is every much as difficult an AI problem as playing well...

  • rand() (Score:2, Interesting)

    by KurdtX ( 207196 )
    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 %.
    • Heh... Some years ago I was involved in some competitions in Denmark and Europe for high-school students ( programming ). Some challanges involed a bit AI knowledge - but each and everyone of the winning entries have used a random algorithm to solve the challanges, and still always had biggest success rate...

      World is weird....
      • That is because some amount of randomness is necessary to get intelligent search algorithms out of local minima. This is why genetic algorithms and simulated annealing, for example, have seen success.
  • Hopefully they'll throw in some human opponents, just for comparison sake.

    • Re:humans? (Score:1, Funny)

      by Anonymous Coward
      True! Or, even better - bacteria!

      I remember that some few years ago some guys used bacteria to predict the stock market. apparently they are more susceptible to the miniscule trends humans tend to overlook. They really know how to adapt to beneficial environments, and, accordingly beat many an analyst.

      However, with a doubling rate of over 20 minutes, they won't have a chance in Quake... Not even against Joe Schmoe with a 28.8k modem!

      However in a slow, perhaps turnbased system they could be killers.

      Sensmoral - that gaming competition has little to do with TrueIntelligence(tm). If one gets beaten by a gang of Streptococcus sp. it says very little indeed, but more perhaps on stock market analysts. ;)

  • How they pay for the prizes... (Score:5, Insightful)

    by A nonymous Coward ( 7548 ) on Sunday August 05, 2001 @09:54AM (#2150086)
    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!

Slashdot Top Deals

Our policy is, when in doubt, do the right thing. -- Roy L. Ash, ex-president, Litton Industries

Close