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

         Second Announcement of the 2nd International

        KNOBELN --- Game-Strategy Programming Contest

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

[Note some changes in the dates at end compared to first announcement !]

This is an announcement for the KNOBELN-contest, taking place
on Sunday, May 15th, 1994.
The contest is run at the University of Karlsruhe, Germany, by
Lutz Prechelt.

Arbitrary teams can participate in the contest via email.

     PLEASE REDISTRIBUTE THIS ANNOUNCEMENT
     AS WIDELY AS YOU CAN
     e.g. to local and regional newsgroups, bulletin boards,
     pin boards, friends, and colleagues.



-----------------
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). This means that you have
to make your strategy adaptive to an environment of opponents not known
in advance.



--------------
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. Otherwise, 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 P 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 contest the parameters for the game are:
  a = 1,  b = 12288,  k = 8,  L = 1000



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

The tournament is performed in successive rounds with randomly mixed 
groups of 20 to 41 participants. Within each group, each strategy
plays one game against every strategy in that group (including itself).

At least those half of the participants, 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 forbidden by the contest rules.
The game in question is immediately stopped, its intermediate results
are discarded and it is rescheduled.
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.

See section 'requirements for programs' for additional rules.



-----------------------
Disciplines of Contest:
-----------------------

In the contest, two disciplines are played.

Discipline 1: KNOBELN

The first (and main) discipline is the normal KNOBELN tournament as
described above.
The winners of its final round in order will be announced as "the winners
of the International KNOBELN contest".

Discipline 2: Knobeln Evolution

Participants of this discipline are those contest participants that 
reached the final round of the first discipline. The results of this
final round are used as the basis for the following evolutionary
computation:
1. A population of players is created that initially consists of, say,
   5 exemplars of each strategy. (A different number may be chosen in
   the actual contest)
2. This population is used as the group for a virtual round of a
   Knobeln tournament: Each exemplar plays once against every other.
   These games are not actually carried out; their result is just taken
   to be the same as in the real final round of the original Knobeln
   tournament.
3. After this round, each player has won a certain amount of points.
   This amount is also a certain fraction of the total number of points
   won overall (by all participating players). This fraction F is used as
   a measure of 'success' that determines the number of exemplars of
   this player in the next round: The total number N of exemplars in
   the population is held constant and the number of exemplars of
   each player p in the next round is computed as the rounded value
   of N*F(p).
4. The evolution ends when the fractions of the population the players
   hold have stabilized.
5. The rank of each player is determined by the fraction is holds
   at the end of the evolution; the higher the fraction, the higher the rank.
   Those players that have fraction 0 get no rank.

The ranked players of Knobeln Evolution, will be announced as "the winners
of Knobeln Evolution in the International KNOBELN contest".



----------------------------
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. 
Trying to 'exploit' the opponent will work only if the opponent is not
intelligent enough to strike back or has an attitude that is so extremely
cooperative that is tolerates being exploited.

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.

It should be noted that in the first contest (1993), aggressive
strategies that tried to exploit their opponents got quite a good
share of success despite the cooperation bias of the rules.

The evolution rules of discipline 2 have the following consequence:
A strategy that builds its success on strong exploitation of only a few
other strategies that are themselves not very successful will have a hard
time because these less successful strategies will vanish during the
evolution. Strategies that yield roughly the same results for almost
all opponents will score better.
Discipline 2 was not part of the contest last year.



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

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

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

mail-address:    ourname@machine.domain.alfdkj
mail-preference: LAP,DGP,GRG,RSM
team-name:       the_heavy_lords_of_knobeln 
Organization:    University of Northeast Sacrodata, Intellect City, Eggland
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, because the registration
will be processed automatically.
In particular, put all of the 'Organization' entry on a single line
(which may be longer than 80 characters if necessary) and don't put
spaces in front of the colons.
Don't put additional information into this mail; send separate
mail instead, if necessary.

- "mail-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 (in all uppercase):
    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)
    RSM  send summaries of rounds (includes all group rankings)
- "team-name" can be any string that is a valid C identifier of at
  most 30 characters and should be a funny name for the team.
  It must in particular not contain any spaces
- "Organization" should be the name of the institution the team is at
  or something else sensible, if no such thing exists. Please also
  give city and country/state.
- "team-members" should contain a two-line informal description of each 
  member of the team, giving his/her
     name, age in years, occupation,
        computer science and programming background, 
  in this order.
  Team size should be anywhere between 1 and 10.
  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 . I may also tell you that I have 
      slightly modified your team name, if it conflicts with an already 
      registered one.
I expect that case (a) will never occur.
Please allow some time (ca. 3 days) for the answer to arrive.
      
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: knobeln@ira.uka.de
Subject: please compile

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

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

Your program will be compiled automatically shortly 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, 
      character in string denoter, character in char denoter, 
      special character
   NO lexical elements (i.e. not counted) are: 
      blank, Tab, newline, comment
   Information about how many lexical elements your program has is
   sent to you as a report from automatic compilation as described above.

5. The size of the process that runs the program must not grow 
   beyond 1024 kB on a SUN SparcStation 2 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 30 seconds of cpu
   time on a SUN SparcStation 2 (which has about 20 SPECmarks).

7. Source code must contain a verbal description of the main program
   ideas of the strategy: Whether it tries to exploit and/or cooperate,
   and what techniques it uses to achieve that. The description should be
   at least about 15 lines long (but more detailed is fine).
   Please enclose the description in #if 0 ..... #endif.
   The description is not counted in the number of lexical elements.

I recommend (but this is not enforced) that programs do not use
floating point arithmetic and that programs are structured as infinite
loops, i.e., do not terminate automatically after 1000 throws.



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

1. 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. This is the only mandatory software you need; all
   other parts described below are just utilities for your strategy
   development and analysis.

2. 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 (or must write something similar
   yourself). You will need a UNIX machine in order to compile and run it
   (or otherwise must make some simplifications in the code).
   This program was originally written in C-Refine.
   You will receive both a C-Refine and a pure C version.

3. 'protocolfmt' is a Perl script that formats the compact game protocols
   sent to you during the contest (if you request them) to the full format.

There are two ways to get the source code of these programs
(about 60 kB altogether):

1. by anonymous ftp (prefered method):
   Sanfrancisco.ira.uka.de [129.13.13.110]:  /pub/knobeln94.tar.Z  (22 kB)
   (in the directory /pub/knobeln93 on the same server you can also
    find several large files with the software and results of last year's
    Knobeln contest. I will NOT send these by mail)

2. by mailserver. Send email of the following form:
     To: prechelt@ira.uka.de
     Subject: SEND knobelnsoftware



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

The actual contest 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 tournament.

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

- When the contest starts, the registration record of all participants
  is sent to all participants with mailpreference LAP.
- When a group starts, a list of its participants (team names only) is sent
  to the members of this group with mailpreference LGP.
- When a group is finished,
  - the game protocols of all games of participant X are sent to participant
    X if the participant has mailpreference DGP.
  - the game results of all games of participant X are sent to participant X
    if the participant has mailpreference GRP (superfluous if DGP is given).
  - the game results of all games of the whole group are sent to those
    participants that have mailpreference GRG.
  - the ranking of participants in the group is sent to those
    participants of the group that have mailpreference GRR.
- When a round is finished a handwritten summary of all groups of this
  round is sent to all participants of the contest that have
  mailpreference RSM. These summaries will at least include all
  group ranking, so that RSM makes GRR superfluous.



------------------
The 1993 Contest:
------------------

A similar contest was run last year; 41 teams from 9 countries participated.

The differences to this year's rules were:
1. Two tournaments were run, with a one-week pause in between during
   which the participants could change their strategy.
2. Strategies did not have to play against themselves.
3. The Knobeln evolution was not played.



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

By applying for registrations all members of a team assert that they
understand and agree with the following points:
   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
   (at least) the team name or the team's organization or the names 
   of one or several team members.
   In particular, the team members allow the organizer to distribute
   freely the source code of the strategy programs after the contest.



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

94/03/22    beginning of registration
94/03/23    beginning of compilation service
94/05/15    9:00 UT  registration deadline
94/05/15    11:00 UT end of compilation service
94/05/15    12:00 UT START OF CONTEST
94/05/21    Results posted to Usenet: rec.games.misc, misc.misc

UT is Universal Time (also known as Greenwich Mean Time GMT).
Note that registrations issued after 94/05/10 will be acknowledged only
immeadiately before the deadline and that programs can be sent only after
a registration is acknowledged.

Good luck and have fun !

  Lutz