ICFP Contest Underway

iseff writes "The ICFP Contest (reported first here) is now underway. There's probably still some time for us slackers to code up something for the first round. This year's problem is similar to the board game Cops and Robbers. What I find cool about this year is the split into two parts -- code the original spec, then wait, get a new spec, and modify. Plus, any language is accepted, even though it's a 'functional programming' contest."

Comments

Re:Better game? Something other than a game?

[Anonymous Coward]

I would probably enter if they said what ICFP meant.

I Have Found A Flaw In The Program Specification..

[Anonymous Coward]

but this textarea is insufficiently large to post the details of that flaw. I will provide a PDF later.

International Conference on Functional Program

[j1m 5n0w]

The programming contest is part of icfp (they usually announce the winner at the conference).

The name of the game is

[ciroknight]

Artifical Intellengence.

It's often best practices to make a contest be a game programming contest; people like games. People like to code interesting projects. Luckily this puts them together.

Before you pass it off as "too simplistic" or not "deeper", that game probably has well over 10^30 different possible configurations, easily defeating similar games like Chess, and on par with games like Go.

These are the kinds of things that really bring out the talented coders.. people who can design the algorithms, people who can figure out the internals of the game, and not just the coders who write code for a living. I can't wait to see the results; I'd work on it myself if I could.

Re:The name of the game is

[ZombieChiefExecutive]

Before you pass it off as "too simplistic" or not "deeper", that game probably has well over 10^30 different possible configurations, easily defeating similar games like Chess, and on par with games like Go.

I hear you. But there is so much more to life than games. I think... ;-)

Re:The name of the game is

[Ambush Commander]

and on par with games like Go.

Then we must worry about the game being too hard. Fortunantely, it'll be hard for everyone, but perhaps that's why we won't be seeing animated game transcripts (although that'd be really cool).

Re:The name of the game is

[ciroknight]

Actually, I would expect them to have an animated game transcript. Last time I programmed in a challenge like this (GNU Robots in PHP basically), I built an ASCII library for all of the graphics processing.. of course this was pre-AJAX, so it wasn't nearly as good as it could have been..

And yes, the game is actually too hard. That's the whole point; it's a fair game. Nobody's going to have any chance better than anyone else unless they design their algorithms correctly. That takes all of the guesswork out of the game, and ensures the playing field is fair. It also adds a lot of variability to the game, allowing for a huge amount of possible attacks at the game.

Re:The name of the game is

[Anonymous Coward]

It's often best practices to make a contest be a game programming contest;

Actually it's not. The problem with multiplayer game simulations is that the best strategy will depend on what other bots are doing. Even if you write a very complicated program that detects what strategies the other bots are following and has a large number of strategies coded as possible responses (which is far more effort than most entrants will make), there will still sometimes be no winning strategy against certain groups of bots, so all your extra effort goes to waste and someone with a trivial strategy wins.

If you absolutely must run a contest on a game, use these rules:

1) two players at a time only.

2) run many iterations.

3) consult a game theorist about your ideas.

Re:The name of the game is

[ciroknight]

The thing about a Game competition is, that it allows for so many different strategies, that anyone can come up with one, code it, bring it to life, and have a chance to win. Therefore, games make really good contests.

Of course any game competiton will run many different iterations due to the fact that so many things either have to be randomly generated, and the bots my behave differently in different environments.

The thing is, if this was a program to do database sorting, nobody would care (or anything else randomly that can pop off your head; let's face facts that most programming tasks suck. That's why we're writing the damned program in the first place, so that someone doesn't have to do it by hand!!!). So really, it is best practices to make a competition a gaming competition.

These particular rule sets, I'm not very happy with, but that's personal reasoning. And any game theorist will tell you that anyone's got a fair shot at this; the search space is so great that nobody will have any marvolous breakthroughs, and it's more of a game of chance. And everyone knows contests of chance are more fun (Texas Holdem anyone?) :-D

Re:The name of the game is

[Anonymous Coward]

The thing about a Game competition is, that it allows for so many different strategies, that anyone can come up with one, code it, bring it to life, and have a chance to win. Therefore, games make really good contests.

I'd prefer the person who successfully implemented the best strategy to win, not "anyone." That's the problem here, there's no guarantee that the best program or programmer will win.

The thing is, if this was a program to do database sorting, nobody would care (or anything else randomly that can pop off your head; let's face facts that most programming tasks suck. That's why we're writing the damned program in the first place, so that someone doesn't have to do it by hand!!!). So really, it is best practices to make a competition a gaming competition.

A programming competition can be fun without the problem being to implement a game. Plenty of previous ICFPs were not games and they were fun.

Seriously, it's cute and all to have a programming competition where you write code to play a game, but it's not the best way to do it.

Re:I Have Found A Flaw In The Program Specificatio

[Anonymous Coward]

Thats ok, when there's a day left, they'll post the fixed specification and everyone will have to hustle to recode it.

Re:Better game? Something other than a game?

[Anonymous Coward]

you are such a fucking liar. you wouldn't enter this contest ever, you just like to jerk off while reading slashdot. mental masturbation is not the same thing as being skilled

Sounds fun

[lvleat]

If I didn't suck balls and programming, and had a bigger attention span bigger than a goldfish, I'd give this a shot. But..I won't. The game actually sounds hella neat ^_^. G'Luck to everyone who's participating.

Any Language?

[Anonymous Coward]

Whoever enters a BrainFuck entry will be my personal hero.

[+++>>><<<---]

Re:Hackers are all robbers to management

[Anonymous Coward]

Why don't you shut the fuck up, you motherfucking moron? Huh?

More on the task

[spockvariant]

Participants need to write programs that control bots - cop bots and robber bots on a pre-defined map. The goal of the robber bots (of which there's only one in the first round) is to rob as many banks as possible (to rob a bank, a robber needs to simply arrive at its location), and that of the cop bots is to minimize the amount of money stolen - and if possible, catch the robber. The map can be seen as a directed graph with various edge attributes that decide how fast and in what direction a particular bot can move.

What is really interesting though, is the format in which the tournament is going to be played. Every game will consist of 5 cop bots going against 1 robber bot. The cop bots will be written by individual participants - and will have the capability to communicate with each other, suggesting 'plans', and voting on them to elect the best one. The whole team gets rewarded if the robber is caught, but you also get individual bonuses for individual achievements. This adds a byzantine-generals like dimension to the problem, since the strategy is always a mix between cooperative effort and individual greed.

The last and most important twist is the fact that the second round is worth 'significantly' more than the first, and involves adapting your bots to a modified version of the problem. What this modified version will be is a closely guarded secret... but it means that it's probably a good idea to spend as much time thinking about the design as thinking about the strategy.

Arimaa

[headkase]

Check out Arimaa. It's a game based on positional intelligence in stark contrast to brute force adaptive space searching that a chess engine uses. What is positional intelligence? Don't know, you gotta play it to learn it. But one thing that has been demonstrated so far is that a beginner human player has a good chance of beating the best computer player yet devised. And Arimaa has the same depth that is intrinsic within chess as well - your rating as a player ranges from novice to grandmaster. Positional intelligence has yet to pan out but one thing is proven by Arimaa, a new approach is needed to when dealing with the evaluation of the rules of it's game.

Re:Arimaa

[blogan]

Looking at the game it's only been out for less than three years. If the game was as popular as chess, than stating that there's no good computer program would hold a better argument that the game strategy is unique.

Re:Any Language?

[uchi]

Wow, that is some worthless brainfuck code you entered. It is all about befunge-98 anyways...

01&v-1: <
>2->::2`|
|:\0\_+v/
_$.@ ^\<<

Re:ANY language?

[j1m 5n0w]

If you can provide binaries that run on vanilla Windows XP or Knoppix and are capable of reading from stdin and writing to stdout, then as far as I can tell, that would be fine.

Oh, great

[Rick and Roll]

Now people have a place to meet to break all the contest rules.

I am working on this as a solo programmer. I'm more into math and algorithms than the average state university C. S. graduate, but still not very good at math. So I don't expect to have a very great entry, but will enter anyway. It would be really nice to make it into the playoffs (you compete against mediocre judge's robots in the regular season, and have to beat them to get into the playoffs). I think I'll be lucky if any AI I add doesn't break the protocol code (disqualifying my robot).

I'm going to work into the wee hours of the morning both tonight and tomorrow night (I am in Arizona, so the contest started at 7:00 AM Friday and ends at 7:00AM Monday). I'll see what I get. If nothing else it will be a good learning experience - in fact it already has been good.

I've been following the mailing list. The most interesting devlopment was that someone discovered that the five cops could camp the six banks, because two banks were only separated by one intersection. The organizers released a new map to fix this.

It's an exciting contest.

Re:Oh, great

[Anonymous Coward]

I believe BDK v3 removes the 5 cops camping the 6 banks ability.

I need more sleep.

[Mr. Bad Example]

I kept reading this as "Insane Clown FORTRAN Posse".

Hey, that's my old stomping grounds!

[billbaggins]

Well, ok, I lived in the Hyde Park area (the setting of the game) for a good solid 8 months. Odd, though... they've got the police station located at 55th & Woodlawn... Unless my memory is decieving me, that's actually a *fire* station...

(Hrmm. No, now that I think of it, that corner has a Starbucks [what corner doesn't?], a church, a school, and some nasty-looking apartments. The fire station is one block west. Ohwell, this is supposed to be the fictional future hyper-advanced year 2000 Chicago, maybe there'll be some changes by then...)

Re:Any Language?

[Anonymous Coward]

Nah, Boolfuck is where it's all at.

I like the "create this" part..

[dbcad7]

I like the "create this" part.. but the time pressure too much for my basic (literaly) skills.

I learned basic many moons ago (apple IIC if you want to calculate that), and other than a little python recently, I haven't done much coding. I find as an individual not doing it for a living, programming gets to the point where you say.. ok I can do this, but now what do I do ?

A few years back, I had a freind who wanted a program to mactch up roosters for fighting, It had the following requirements...

must randomly match

must match within 2 ozs

each participant had 2 entries, must not match into same "owner"

avoid matching 2 owners against each other twice if possible

Altough probably simple for most of you hard core coders, it was a challange for me, and I did it in qbasic.. my reason for bringing this up is that if I had other challenges like this, I probably would have kept at it more. I like the idea behind contests like these.. perhaps I will try to do this challenge just for my own fun and not part of the competition.

Re:I like the "create this" part..

[Fahrenheit 450]

Well, if you're willing to limit yourself to C, C++, Java, or Pascal, you may want to have a look at some of the problems available at The Online Jodge. You can code them up and submit them to have them tested for speed and correctness.

Evolved algorithms

[-Harlequin-]

This seems like a suitable challenge to grow your program using mutation & selection and/or crossbreeding methods to create an evolved solution instead of a designed one. Set it up now, and leave some simulations running on a dedicated box or six, 24/7 until the competition. Then take your killer software to the competition.

The coolest bit would be when anyone asks "So, how does your program work?", to which you would answer "I haven't the faintest idea. It just does." :-)

Re:Evolved algorithms

[rbarreira]

This reminds of that somewhat-well-known story which Skiena tells in one of his books.

The story's about neural networks, it tells about a military system which had a neural network program which was supposed to be able to distinguish between images of tanks and images of regular cars. They trained the network with their trainining input sets, and after some training, it was working for those.

When they started using the system in real life, it was a complete disaster... After some investigation, they concluded that the pictures they used to train the network were the guilty party - the car pictures were all taken on a rainy day, and the tank pictures were all taken on a sunny day. Conclusion - the network was distinguishing between cars and tanks based on the light present in the scene :)

Re:Evolved algorithms

[swiftstream]

My brother in law worked with a professor at Stanford Unviersity (Koza or something...) who worked with mutating computer programs and the like. At one point his computers designed a circuit which always returned the cube of the number inputted, but he couldnt figure out why.

So, not so far-fetched, after all.

knee deep in garbage

[epine]

In the original thread there were posts about the advantages of LISP and related languages citing garbage collection as one of the pillars of post-C language design.

Now, I find this amazing. Apparently, functional languages can solve every real world problem with ease except keeping track of what resources have been allocated and their necessary life scope. Why do such potent language frameworks punt this problem to a simplifying heuristic? Are problems that arise in the implementation domain of a fundamentally greater complexity than problems that arise anywhere else?

Re:knee deep in garbage

[Anonymous Coward]

Apparently, functional languages can solve every real world problem with ease

This is a straw man. Nobody claims this apart from the zealots, and they can be ignored like all other fanatics.

What serious FP users claim is that FP can solve many classes of real-world problem with greater ease than existing imperative languages.

There is some truth to this claim. Many OO design patterns have far simpler equivalents in FP languages. The visitor pattern, for example, is nothing more than an extremely complicated, tedious, and inefficient substitute for pattern matching on algebraic datatypes. FP languages are highly optimised for tree processing, making them ideal for any application that uses XML.

There are also problems which FP does not make any easier; for example, simple text processing applications are typically much more complicated to write in FP languages than in specialised scripting languages like Perl or Ruby, while event-driven GUIs are a problem ideally suited to an OO approach, which is another weak point of FP languages (though there are FP/OO hybrids like OCaml and Lisp's CLOS which go some way to dealing with this problem).

If you're interested in seeing what FP has to offer imperative/OO developers, just look at the Boost libraries for C++. Many of the ideas there, like closures and lazy lists, have been drawn from FP research. Sounds like someone thinks FP is interesting enough to be worth serious effort bending a non-FP language to support it.

...except keeping track of what resources have been allocated and their necessary life scope.

The garbage collector is a solution to that problem. In the presence of dynamic scoping, it is the only general solution that has been discovered so far. The only method of memory management that provides superior speed and efficiency is static allocation on the stack, and that is a great restriction that makes programming considerably more difficult.

What exactly is your problem with GC? It removes a major source of bugs and decreases the complexity of a program considerably, without introducing any major disadvantages. So why are you so hostile to it?

Re:knee deep in garbage

[Anonymous Coward]

[GC] removes a major source of bugs and decreases the complexity of a program considerably, without introducing any major disadvantages.

Not true. GC leads to excessive disk swapping when running a CPU-intentensive application even when memory requirements for the algorithm are not particularly high.

Re:knee deep in garbage

[Anonymous Coward]

That depends highly on the particular program and garbage collector, and probably isn't true in the general case. But in any event, there was a really good paper at this year's PLDI about how to make garbage collectors avoid paging that's well worth reading.

Re:knee deep in garbage

[Reverend528]

...the advantages of LISP and related languages citing garbage collection as one of the pillars of post-C language design

LISP really can't be categorized as a post-C language, as it was created roughly 15 years before C.

Mods...

[rbarreira]

Offtopic? Please...

Re:Hackers are all robbers to management

[DerekJ212]

How about your turn your brain on troll and see where the world is headed. Every day some article is posted about us losing our rights and becoming criminals for what was once something we were allowed to do. Go back in your hole.