ICFP 2005 contest - Drunk Sed once again

a cop arresting a clown

News

September, 28th, 2005

Here are the results of the final round. 2100 games were done, I collected the results (from here, with the help of bash, wget, C, sed, tr, wc, bc, grep, less, cut, vi, sort, uniq and xcalc) (yes, I know that noone cares), summing up everything, calculating the average.

rank  team (2) means second submission  total nb games average langage(s) used
 1st: KiebererAndXiaoTou		839910 161 = 5216.8323	(Haskell)
 2nd: Dylan Hackers			840728 194 = 4333.6495	(Dylan)
 3rd: Combat-Tanteidan			732689 173 = 4235.1965	(Haskell)
 4th: Combat-Tanteidan (2)		686068 176 = 3898.1136	(Haskell)
 5th: Contest Crackers			667983 175 = 3817.0457	(C)
 6th: Team Smartass			649146 177 = 3667.4915	(Java)
 7th: Dun(kosmi)loolump			628457 188 = 3342.8564	(Haskell)
 8th: Contest Crackers (2)		322895  97 = 3328.8144	(C)
 9th: The Caml Riders			307103 100 = 3071.03	(Objective Caml)
10th: Disco Turtle			432045 160 = 2700.2812	(Python, C++)
11th: Drunk Sed Team (2)		371378 155 = 2395.9871	(C)
12th: Some graduate, others mature (2)	393708 165 = 2386.1091	(OCaml)
13th: uguu.org (2)			324178 179 = 1811.0503	(C++)

So I finish 11th. There were 161 teams registered for the first round, 86 (I think, but I am not sure) for the second round. So, not that bad.

My contribution

What is it? Well, check the contest page to get the point.

First round's code
Second round's code

See this?

    if (!strcmp(line, "from/"));
      return;

Shame on me... If another cop is named game-over, my program will quit, because of this bug... (This bug is in the first round's submission.)

In the second round's submission I do some malloc with no free, I am really a bad bad hacker.

Here comes the README from the second round's submission. It's the essay too. (We were supposed to submit an essay describing our solution.)

Drunk Sed Team
==============

This document describes my entry for the second round of the
contest.

Bots have exactly the same behavior as for the first round
of the contest. I don't take into account the new stuff, just
modified the parser to accomodate them (I hope I did it correctly).
(I have no time to change more than that.)

It took me three hours and a half to adapt my solution to the
new rules (which is a lot).

There was a bug in my previous entry for the first round.
I did (see main.c of cops):
     if (!strcmp(line, "from/"));
       return;
You see this silly ';' at the end of the if?
Shame on me...
But it should not cause too much troubles. There just might be
some buffering issues, because I will send a message to the
server before having read everything it sent to me. (The code
will return, and then it will read the rest of the message which
won't match anything and silently be discarded.)

WHY NO CHANGE WITH PREVIOUS BOTS?
=================================

short answer 1: my bots are perfect.
short answer 2: no time.

long answer:
OK, so the changes are:
1 - a cop may become a nasty cop, thus getting more money to the end
    (if he is not caught)
2 - honnests cops can accuse other cops
3 - robber can push cops
4 - the bribing stuff

3 could be nice but complicates all my calculation, and the robber
loses money when it does it. And if I want 3, I must take into
account bribing, which complicates everything a lot.

4 is too complicated. My robber is a robber, not a computer scientist!

1 and 2, are they good? For my cop, no. Here is the psychology of my cop:
He is a white sub-urban 50 year old cop. He is not clever. He is cop
just to have a work. He is a bit fat. He does not trust that much other
cops. But when he was a kid he didn't like people to accuse each other,
so he just decided to let them live on their own, not caring too much
about them, not creating deep and tricky mental representations of
people, and not accusing anyone, unless he is sure of someting.
He respects the laws, because it costs less to do so. But
he does not like to accuse other cops. They are co-workers, he trusts
them by default. And since he does not care that much about them,
he does not see when they become nasty.

So, my cop's psychology is not compatible with this nasty behavior.
So, he won't behave in a nasty way. And he won't accuse others,
because he mainly does not care about what they do. He just tries
to catch robbers (and he knows he's bad at it). He is just a cop
to get money for his wife and two kids, that's all.

CONTACT
=======

email: Cedric.Roux@eurecom.fr
web: http://sed.free.fr/icfp2005 (after the contest)

Give me 24 hours to reply in the week. I don't my emails in the week-end.

BUILD
=====

Just run the script 'build' in this directory.
It should produce four programs: cop, cop2, robber, and robber2.

gcc is needed. Version 3 or higher would be nice.

IMPORTANT
=========

I close stderr at start of program, is it OK?
If you give one or more parameters to the programs, they
will use stderr and write some debug stuff. Contact me
if there are problems.

TOOLS USED
==========

language: C
editor: vi
environment: X Window with fvwm and several xterm.
compiler: gcc 3 something.

INTERNALS
=========

Bots find their way with some kind of Dijkstra algorithm.

Cops are not very clever (I mean *my* cops, not cops in general).
Robbers are a bit more, even if they are simpler.

The two cops behave exactly the same, but since I wanted to
submit two robbers, I had to include a second cop.

The robbers differ in that robber2 takes more risks than robber.
It will go to a bank if cops are closer than what robber does.
Apart from that, they are the same.

They decide what banks are OK to attack, based on the nearest
cop present. Then, they take the nearest one. They take care
on the path not to get too near from a cop (by giving a higher
weight to nodes close to cops for the Dijkstra algorithm).

The cop, on the other side, goes to the place the robber was seen
last. If on his way, he finds some information (returned by the
server, it ignores other cops), he keeps it and will maybe come
back here later, if he has nothing else to do (we have a list
of tasks, and when he finishes one task, he does the next one).
When he reveices a message telling him with 100% insurance that
the robber is at position X, he goes directly to position X,
ignoring his current tasks.

For the run with McGruff cops, he orders them to go each one
on a bank, so that four banks are safe. But if the robber
goes into another bank, he asks McGruff cops to all go to this
bank, so maybe they can catch the robber in the way.

The cop could use McGruff's informations, but since in the next
part of the tournament, he will have to 'compete' with other
cops, these cops could generate false information, to let
my cop out of the game. So, no information used at all, generated
by other cops. This is probably a bad thing.

Apart from that, since the goal is to win, the cop generates
at each turn 1000 fake messages about the position of the
robber (inform messages), to fool slow players. Bad, I know,
but, well, that's the way it is.

The plan he makes is tuned for McGruff cops. It probably won't
be very useful when not with McGruff cops. And even with McGruff
cops, they rarely catch robbers. So anyway, it's a bad plan.

For the vote, I vote for myself first, then random choice
for the next. Democracy it is, no? :)

The important sources are the files main.c and strategy.c.
The others come from other projects. I mainly needed
hash tables for the various names involved in the game.

main.c contains startup code and parser. strategy.c contains
all the calculation.

My programs are fast. They are not very good I think. We'll see.

REMARKS
=======

I could not work on my pentium 200, 64Mb of ram, linux 2.2,
so I had to use a linux/windows setup with ethernet between.
I did my bots under linux and on windows a little wrapper to
talk to your simulator. Your simulator was running under
windows. It sometimes behaved badly (suddenly stopping,
because of a socket problem, not of my own), and didn't
terminate properly (I had to kill processes by hand, with
this horrible mousepad sh*t, and this horrible task manager
sh*t). For next contents, tell the future organizers to choose
a task which does not require a simulator like this.

The simulator is in scheme, no?
I guess that your scheme stuff needs some improvements... :)

Anyway, thanks for this funny week-end of free code. It was
nice.

Sed.

Take care of yourself.


Contact : sed@free.fr

Creation time: Tue, 12 Jul 2005 13:01:49 +0200
Last update: Wed, 28 Sep 2005 14:17:02 +0200

Powered by a human brain, best viewed with your eyes (or your fingers if you are blind).