Xref: relay1 comp.ai:1005 comp.ai.edu:61 comp.ai.philosophy:753 comp.edu:708 comp.lang.c:6717 comp.protocols.misc:166 comp.sources.wanted:1422 comp.theory.dynamic-sys:87 comp.theory.self-org-sys:10
Path: softp!relay1!csoft!kiae!relcom!fuug!mcsun!Germany.EU.net!ira.uka.de!uka!prechelt
From: prechelt@ira.uka.de (Lutz Prechelt)
Newsgroups: comp.ai,comp.ai.edu,comp.ai.philosophy,comp.edu,comp.groupware,comp.lang.c,comp.programming,comp.protocols.misc,comp.sources.wanted,comp.theory.dynamic-sys,comp.theory.self-org-sys
Subject: Announcement: International KNOBELN contest
Followup-To: comp.sources.wanted
Date: 24 Mar 1993 15:45:00 GMT
Organization: Universitaet Karlsruhe
Lines: 396
Message-ID: <1opvlsINNbsp@irau40.ira.uka.de>
NNTP-Posting-Host: i41s18.ira.uka.de

       ===============================================

         First announcement of the 1st international

        KNOBELN --- Game-Strategy Programming Contest

       ===============================================

This is an announcement for the KNOBELN-contest, taking place via
e-mail on Saturday, May 8th, 1993 and on Sunday, May 16th, 1993.

The contest is run at the University of Karlsruhe, Germany, by
Lutz Prechelt.

Arbitrary teams can participate in the contest.

PLEASE REDISTRIBUTE THIS ANNOUNCEMENT AS WIDELY AS YOU LIKE.



-----------------
Type of Contest:
-----------------

To participate, you must program in C a strategy for a simple game 
and send it to me by email. The game is quite interesting since there 
clearly is no canonical best strategy (the success of a strategy depends
on the behavior of all other participants).



--------------
Rules of Game:
--------------

1. Both players (at the same time) chose an integer number in the interval 
     a..b.
   This selection of two numbers is called a "throw".
   The players can watch each throw as it is made (i.e. they can know
   all numbers they and their opponent have thrown up to the 
   current throw)
   Assumption:  Player P choses p1 and player Q choses q1.

2. If p1 equals q1, nobody wins a point.

3. The player with the higher number wins, unless the number is more 
   than twice as high as that of his opponent.
   Let's assume that p1 > q1, then
     P wins if 2*q1 >= p1 and
     Q wins if 2*q1 <  p1.

4. A player who wins a throw with some number N gets
     floor(log2(N)) points
   in this throw.
   The other player gets 0 points in this throw.
   Example: if P wins, he/she gets floor(log2(p1)) points
            e.g. if p1 = 6800, player P gets 12 points.

5. A game consists of L throws.

6. Both players must throw series of non-decreasing throws.
   These series must (for each player individually) have a length
   of AT LEAST k throws.
   Example: If P1 throws (p1, p2, p3, .....) then
            p1 <= p2 <= p3 <= ... <= p(k) is required.
            After that, p(k) > p(k+1) is allowed.
            If p(k) > p(k+1) then
               p(k+1) <= p(k+2) <= ... <= p(k+k) is required.
            else 
               there exists some smallest number j, with j > k for which
               p(j) > p(j+1)
            and then 
               p(j+1) <= p(j+2) <= ... <= p(j+k) is required.
            and so on through the whole game.
      If for instance k = 3 then the sequence
        1, 2, 3, 1, 4, 5, 6, 8, 2    is allowed, while
        1, 2, 3, 4, 1, 2, 1          is not
                          ^ too early

In this turnament the parameters are:
  a = 1,  b = 12288,  k = 8,  L = 1000
   


--------------------
Rules of Tournament:
--------------------

The tournament is performed in successive rounds with randomly mixed 
groups of 7 to 12 participants. Within each group, every strategy
plays one game against every other strategy in that group.

Those half of the participants (rounded up), that have won most
points in their group (no matter how many their opponents got), proceed
to the next round, which is played with newly mixed groups.
The winners of the last round are the winners of the tournament;
the results of previous rounds are discarded.

Any strategy is allowed to fail once per round. Failing means doing
anything that is disallowed according to the rules of the game.
The game in question is immediately stopped, its intermediate results
are discarded and it is rescheduled after all the other games currently 
scheduled for that group.
If the strategy who failed had already failed before in the same round,
the game is not rescheduled but the strategy is disqualified from the 
contest. 
All its remaining games in that round will not be carried out and
all its previous games in that round will not be counted.

This tournament is performed twice to find the winners of the contest:
After the first tournament is performed, there is an eight day pause,
during which the contestants can revise and change their strategy based
on the game protocols of their games in the first contest (see below).
Then the second tournament with identical rules and the same (or a
reduced) set of participants is carried out.
Those teams with the highest total rank in both tournaments will
be announced as winners of the contest.

See section 'requirements for programs' for additional rules.



----------------------------
Characteristics of the Game:
----------------------------

The method of counting within a game and the method of selecting the
winners of a group have an interesting impact on the goal of a
strategy: It must actually try to arrange a cooperation with its
'opponent', because otherwise none of the two will usually be able to
win many points. 

It is NOT important to have more points than the opponent in any
single game. Instead it is important to have more points than the
other strategies on the average.

The problem of programming a strategy could thus be formulated as
  How do I (quickly) arrange a cooperation with a machine partner, if
  there is no predefined protocol to do so and the only communication
  channel is mutual exchange of integers, one at a time ?
  
It is clear, that there exists no optimal strategy: It is impossible
to guarantee that a strategy A is able to arrange a cooperation with a
strategy B, even if both are perfectly willing to cooperate in
principle. This is true because both strategies have to 'guess' what
might be suitable protocols to communicate. The two strategies of a game
should together form a self-organizing system that organizes for
cooperation.

I think this makes the contest very interesting.
By the way: This game is probably interesting to play with human
            players, too.



------------------------------
How to Announce Participation:
------------------------------

If you want to participate in the contest, send email of the
following form:

---
To: prechelt@ira.uka.de
Subject: registration for KNOBELN

email-address:   ourname@machine.domain.alfdkj
mail-preference: LAP,LGP,DGP,GRR
team-name:       the_heavy_lords_of_knobeln 
Organization:    University of Northeast Sacrodata
team-members:
  Joe Cool,  45, professional systems programmer,
     20-year-experienced programmer
  Jane More, 20, graduate student of computer science,
     hackeress fluent in 34 programming languages
  Mona Morn, 35, Professor of CS,
     hobby game strategy programmer
  Bill Neat, 24, undergraduate student of psychology,
     advanced beginner (will be my first C program!)
---

Please use this format exactly as shown.

- "email-address" gives the email address that uniquely 
  identifies the team, it should be an internet domain style address.
- "mail-preference" is a comma-separated list of some of the following
  declarators:
    LAP  send list of all participants (full registration format)
    LGP  send list of my groups' participants (team names only)
    DGP  send detailed game protocol for each of my games (every throw)
    GRP  send game result (points) for each of my games
    GRG  send group result (all games of all participants)
    GRR  send group result (ranking)

- "team-name" can be any string that is a valid C identifier of at
  most 50 characters and should be a funny name for the team.
- "Organization" should be the name of the institution the team is at
  or something else sensible, if no such thing exists.
- "team-members" should contain a two-line informal description of each 
  member of the team, giving his/her
     name, age in years, occupation,
        programming background, 
  in this order.
  Team size should be anywhere between 1 and 20.
  Personnel should not be shared among teams.

When I receive your registration, I will send an answer either
  (a) that your registration is not accepted, (e.g. because there are
      already too many participants registered), or
  (b) that your registration is accepted and your authentification 
      string is <somethingweird>. I may also tell you that I have 
      slightly modified your team name, if it conflicts with an already 
      registered one.
Notes:
- If you are unable to send email to me or if I am unable to send email 
  to you, you can not participate in the contest.
  Please use only Internet domain style email addresses.  
- Notification of acceptance or rejection will usually be sent within 
  72 hours.
  I reserve the right to limit participation of multiple teams from the 
  same organization.
- You must keep the authentification string carefully.
  It will be used to check, whether a strategy that swears to come
  from your team really does (see below "Sending Programs").



-----------------
Sending Programs:
-----------------

To send in the first version or a new version of your program,
send me email of the following form:

----
To: prechelt@ira.uka.de
Subject: please compile

/*
  <<FROM>> team_name  authentification_string
*/
/* your source code goes here */
----

<<FROM>> has to be given exactly as shown. The same is true for the 
"Subject:".
For <team_name> insert the name of your team as given in the registration.
For <authentification_string> insert the string that I sent you with the
registration acknowledge.

Your program will be compiled automatically a few minutes after your 
email arrives and you will be sent a report about the results of the 
compilation. A successfully compiled program is automatically stored 
to be used in the contest. The latest version is used always.



---------------------------
Requirements for programs:
---------------------------

1. Pure C (Ansi or KR), i.e., no library routines called, except
     int init_random ()
     int log2 (int number)
     int next_random (int low, int high)
     int make_throw (int my_throw)
     int count_points (int throw1, int throw2, int *points1, int *points2);
   (You will receive a detailed description of these functions
    upon registration)

2. Must be compilable with GNU C compiler (gcc).

3. Must be in a single file, no #includes

4. Must have at most 10000 lexical elements (after preprocessing)
   Lexical elements are: 
      identifier, keyword, number, 
      string denoter, char denoter, 
      special character
   NO lexical elements (i.e. not counted) are: 
      blank, Tab, newline, comment

5. The size of the process that runs the program must not grow 
   beyond 1024 kB on a SUN 4/25 running SUN OS 4.1.
   The value used to test this is the one shown by 'ps -u' in the column
   labeled 'SZ' (SIZE).

6. Must finish every game of 1000 throws in less than 60 seconds of cpu
   time on a SUN 4/25 (which has about 20 SPECmarks).



------------------------------
Recommendations for programs:
------------------------------

1. Should not use floating point operations. (Or you do it on your own risk)

2. Should be infinite loop (i.e. need not terminate after 1000 throws)



-----------------------
Technical Environment:
-----------------------

In order to write and hand-test a strategy, you need the definitions
of the library procedures mentioned above, called 'knobellib.c'.
The source code for these functions is only 130 lines and will be 
sent to you via email with the notification of acceptance of your
registration. Link your strategy with this module, but do not include
the source code of the module into your strategy or else it will
be rejected.

If you want to run complete games between two strategies in the same
kind of environment that will be used in the actual contest, you need
the source code of the 'knobeln' program. You will need an ANSI-C
compiler and a UNIX machine in order to compile and run it. 
There are two ways to get this source code (about 22 kB):

1. To get 'knobeln.c' by anonymous ftp (prefered method), fetch it from
   Sanfrancisco.ira.uka.de [129.13.13.110]:  /pub/knobeln.c

2. To get 'knobeln.c' by mailserver, send email of the following form:
   ---
   To: prechelt@ira.uka.de
   Subject: SEND knobeln.c
   ---



--------------------
The Actual Contest:
--------------------

The actual tournaments will be run at the dates given below.

At some time before, every team has to send its strategy as described
above. It will be compiled and linked automatically, and you will
receive a report about the success of this procedure or any problems
that occur.
This automatic compilation feature is disabled during the tournaments.

During the contest, all participants will receive information about
what happens, if they have announced a corresponding mail-preference 
upon registration: 

After every game, a detailed throw protocol or a short game result
file (giving only the points at the end) is sent to both participants
(if requested by their mail-preference, see in 'Registration' above);
after every round the group summary is sent to all members of that
group (if requested by their mail-preference).



-------------
Legal Issues:
-------------

By applying for registrations all members of a team assert that they
understand and agree with the following points:
1. All participants of the last round of one of the tournaments
   will send a verbal description of how their strategy 
   works (length 100 to 500 words) after the contest.
2. The team members allow the organizer of the contest to publish
   all or part of the information contained in the strategy program
   and in the strategy description. Such publication will mention 
   the contest context and will give credit to the team by
   mentioning the team name or the team's organization or the names 
   of one or several team members.


----------------
Important Dates:
----------------

93/03/28    beginning of registration
93/03/31    beginning of registration acknowledge
93/03/31    beginning of compilation service
93/05/07    registration deadline
93/05/08    first tournament of contest
93/05/16    second tournament of contest
93/05/20    Results posted to Usenet: rec.games.misc, misc.misc

Relevant time of day is noon, Universal Time (UT, GMT), for all dates.


Good luck and have fun !

  Lutz
  
-- 
Lutz Prechelt   (email: prechelt@ira.uka.de)            | Whenever you 
Institut fuer Programmstrukturen und Datenorganisation  | complicate things,
Universitaet Karlsruhe;  D-7500 Karlsruhe 1;  Germany   | they get
(Voice: ++49/721/608-4068, FAX: ++49/721/694092)        | less simple.

