2nd International KNOBELN Contest (part1/2)
Lutz Prechelt
KNOBELN Programmierwettbewerb.
Zu Programmieren ist eine Strategie fuer das Zweipersonenspiel KNOBELN.
Der Wettbewerb findet am 14. Mai statt. Bis zu diesem Datum muss eine
Strategie per email eingeschickt werden.
Lasst Euch in Scharen registrieren!
Lutz
Lutz Prechelt (email: prec...@ira.uka.de) | Whenever you
Institut fuer Programmstrukturen und Datenorganisation | complicate things,
Universitaet Karlsruhe; 76128 Karlsruhe; Germany | they get
(Voice: ++49/721/608-4068, FAX: ++49/721/694092) | less simple.
#! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of shell archive."
# Contents: Announce FAQ example.c
# Wrapped by prechelt@Sofia on Thu Mar 24 19:45:31 1994
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'Announce' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'Announce'\"
else
echo shar: Extracting \"'Announce'\" \(19407 characters\)
sed "s/^X//" >'Announce' <<'END_OF_FILE'
XSubject: Announcement: International KNOBELN contest
X
X ===============================================
X
X First Announcement of the 2nd International
X
X KNOBELN --- Game-Strategy Programming Contest
X
X ===============================================
X
XThis is an announcement for the KNOBELN-contest, taking place
Xon Saturday, May 14th, 1994.
XThe contest is run at the University of Karlsruhe, Germany, by
XLutz Prechelt.
X
XArbitrary teams can participate in the contest via email.
X
X PLEASE REDISTRIBUTE THIS ANNOUNCEMENT
X AS WIDELY AS YOU CAN
X e.g. to bulletin boards, pin boards,
X friends, and colleagues.
X
X
X
X-----------------
XType of Contest:
X-----------------
X
XTo participate, you must program in C a strategy for a simple game
Xand send it to me by email. The game is quite interesting since there
Xclearly is no canonical best strategy (the success of a strategy depends
Xon the behavior of all other participants). This means that you have
Xto make your strategy adaptive to an environment of opponents not known
Xin advance.
X
X
X
X--------------
XRules of Game:
X--------------
X
X1. Both players (at the same time) chose an integer number in the interval
X a..b.
X This selection of two numbers is called a "throw".
X The players can watch each throw as it is made (i.e. they can know
X all numbers they and their opponent have thrown up to the
X current throw)
X Assumption: Player P choses p1 and player Q choses q1.
X
X2. If p1 equals q1, nobody wins a point.
X
X3. Otherwise, the player with the higher number wins, unless the number
X is more than twice as high as that of his opponent.
X Let's assume that p1 > q1, then
X P wins if 2*q1 >= p1 and
X Q wins if 2*q1 < p1.
X
X4. A player who wins a throw with some number N gets
X floor(log2(N)) points
X in this throw.
X The other player gets 0 points in this throw.
X Example: if P wins, he/she gets floor(log2(p1)) points
X e.g. if p1 = 6800, player P gets 12 points.
X
X5. A game consists of L throws.
X
X6. Both players must throw series of non-decreasing throws.
X These series must (for each player individually) have a length
X of AT LEAST k throws.
X Example: If P throws (p1, p2, p3, .....) then
X p1 <= p2 <= p3 <= ... <= p(k) is required.
X After that, p(k) > p(k+1) is allowed.
X If p(k) > p(k+1) then
X p(k+1) <= p(k+2) <= ... <= p(k+k) is required.
X else
X there exists some smallest number j, with j > k for which
X p(j) > p(j+1)
X and then
X p(j+1) <= p(j+2) <= ... <= p(j+k) is required.
X and so on through the whole game.
X If for instance k = 3 then the sequence
X 1, 2, 3, 1, 4, 5, 6, 8, 2 is allowed, while
X 1, 2, 3, 4, 1, 2, 1 is not
X ^ too early
X
XIn this contest the parameters for the game are:
X a = 1, b = 12288, k = 8, L = 1000
X
X
X
X--------------------
XRules of Tournament:
X--------------------
X
XThe tournament is performed in successive rounds with randomly mixed
Xgroups of 20 to 41 participants. Within each group, each strategy
Xplays one game against every strategy in that group (including itself).
X
XAt least those half of the participants, that have won most points
Xin their group (no matter how many their opponents got), proceed
Xto the next round, which is played with newly mixed groups.
XThe winners of the last round are the winners of the tournament;
Xthe results of previous rounds are discarded.
X
XAny strategy is allowed to fail once per round. Failing means doing
Xanything that is forbidden by the contest rules.
XThe game in question is immediately stopped, its intermediate results
Xare discarded and it is rescheduled.
XIf the strategy who failed had already failed before in the same round,
Xthe game is not rescheduled but the strategy is disqualified from the
Xcontest.
XAll its remaining games in that round will not be carried out and
Xall its previous games in that round will not be counted.
X
XSee section 'requirements for programs' for additional rules.
X
X
X
X-----------------------
XDisciplines of Contest:
X-----------------------
X
XIn the contest, two disciplines are played.
X
XDiscipline 1: KNOBELN
X
XThe first (and main) discipline is the normal KNOBELN tournament as
Xdescribed above.
XThe winners of its final round in order will be announced as "the winners
Xof the International KNOBELN contest".
X
XDiscipline 2: Knobeln Evolution
X
XParticipants of this discipline are those contest participants that
Xreached the final round of the first discipline. The results of this
Xfinal round are used as the basis for the following evolutionary
Xcomputation:
X1. A population of players is created that initially consists of, say,
X 5 exemplars of each strategy. (A different number may be chosen in
X the actual contest)
X2. This population is used as the group for a virtual round of a
X Knobeln tournament: Each exemplar plays once against every other.
X These games are not actually carried out; their result is just taken
X to be the same as in the real final round of the original Knobeln
X tournament.
X3. After this round, each player has won a certain amount of points.
X This amount is also a certain fraction of the total number of points
X won overall (by all participating players). This fraction F is used as
X a measure of 'success' that determines the number of exemplars of
X this player in the next round: The total number N of exemplars in
X the population is held constant and the number of exemplars of
X each player p in the next round is computed as the rounded value
X of N*F(p).
X4. The evolution ends when the fractions of the population the players
X hold have stabilized.
X5. The rank of each player is determined by the fraction is holds
X at the end of the evolution; the higher the fraction, the higher the rank.
X Those players that have fraction 0 get no rank.
X
XThe ranked players of Knobeln Evolution, will be announced as "the winners
Xof Knobeln Evolution in the International KNOBELN contest".
X
X
X
X----------------------------
XCharacteristics of the Game:
X----------------------------
X
XThe method of counting within a game and the method of selecting the
Xwinners of a group have an interesting impact on the goal of a
Xstrategy: It must actually try to arrange a cooperation with its
X'opponent', because otherwise none of the two will usually be able to
Xwin many points.
XTrying to 'exploit' the opponent will work only if the opponent is not
Xintelligent enough to strike back or has an attitude that is so extremely
Xcooperative that is tolerates being exploited.
X
XIt is NOT important to have more points than the opponent in any
Xsingle game. Instead it is important to have more points than the
Xother strategies on the average.
X
XThe problem of programming a strategy could thus be formulated as
X "How do I (quickly) arrange a cooperation with a machine partner, if
X there is no predefined protocol to do so and the only communication
X channel is mutual exchange of integers, one at a time ?"
X
XIt is clear, that there exists no optimal strategy: It is impossible
Xto guarantee that a strategy A is able to arrange a cooperation with a
Xstrategy B, even if both are perfectly willing to cooperate in
Xprinciple. This is true because both strategies have to 'guess' what
Xmight be suitable protocols to communicate. The two strategies of a game
Xshould together form a self-organizing system that organizes for
Xcooperation.
X
XIt should be noted that in the first contest (1993), aggressive
Xstrategies that tried to exploit their opponents got quite a good
Xshare of success despite the cooperation bias of the rules.
X
XThe evolution rules of discipline 2 have the following consequence:
XA strategy that builds its success on strong exploitation of only a few
Xother strategies that are themselves not very successful will have a hard
Xtime because these less successful strategies will vanish during the
Xevolution. Strategies that yield roughly the same results for almost
Xall opponents will score better.
XDiscipline 2 was not part of the contest last year.
X
X
X
X------------------------------
XHow to Announce Participation:
X------------------------------
X
XIf you want to participate in the contest, send email of the
Xfollowing form:
X
X---
XTo: kno...@ira.uka.de
XSubject: registration for KNOBELN
X
Xmail-address: our...@machine.domain.alfdkj
Xmail-preference: LAP,DGP,GRG,RSM
Xteam-name: the_heavy_lords_of_knobeln
XOrganization: University of Northeast Sacrodata, Intellect City, Eggland
Xteam-members:
X Joe Cool, 45, professional systems programmer,
X 20-year-experienced programmer
X Jane More, 20, graduate student of computer science,
X hackeress fluent in 34 programming languages
X Mona Morn, 35, Professor of CS,
X hobby game strategy programmer
X Bill Neat, 24, undergraduate student of psychology,
X advanced beginner (will be my first C program!)
X---
X
XPlease use this format EXACTLY as shown, because the registration
Xwill be processed automatically.
XIn particular, put all of the 'Organization' entry on a single line
X(which may be longer than 80 characters if necessary) and don't put
Xspaces in front of the colons.
XDon't put additional information into this mail; send separate
Xmail instead, if necessary.
X
X- "mail-address" gives the email address that uniquely
X identifies the team, it should be an internet domain style address.
X- "mail-preference" is a comma-separated list of some of the following
X declarators (in all uppercase):
X LAP send list of all participants (full registration format)
X LGP send list of my groups' participants (team names only)
X DGP send detailed game protocol for each of my games (every throw)
X GRP send game result (points) for each of my games
X GRG send group result (all games of all participants)
X GRR send group result (ranking)
X RSM send summaries of rounds (includes all group rankings)
X- "team-name" can be any string that is a valid C identifier of at
X most 30 characters and should be a funny name for the team.
X It must in particular not contain any spaces
X- "Organization" should be the name of the institution the team is at
X or something else sensible, if no such thing exists. Please also
X give city and country/state.
X- "team-members" should contain a two-line informal description of each
X member of the team, giving his/her
X name, age in years, occupation,
X computer science and programming background,
X in this order.
X Team size should be anywhere between 1 and 10.
X Personnel should not be shared among teams.
X
XWhen I receive your registration, I will send an answer either
X (a) that your registration is not accepted, (e.g. because there are
X already too many participants registered), or
X (b) that your registration is accepted and your authentification
X string is <somethingweird>. I may also tell you that I have
X slightly modified your team name, if it conflicts with an already
X registered one.
XI expect that case (a) will never occur.
XPlease allow some time (ca. 3 days) for the answer to arrive.
X
XNotes:
X- If you are unable to send email to me or if I am unable to send email
X to you, you can not participate in the contest.
X Please use only Internet domain style email addresses.
X- Notification of acceptance or rejection will usually be sent within
X 72 hours.
X I reserve the right to limit participation of multiple teams from the
X same organization.
X- You must keep the authentification string carefully.
X It will be used to check, whether a strategy that swears to come
X from your team really does (see below "Sending Programs").
X
X
X
X-----------------
XSending Programs:
X-----------------
X
XTo send in the first version or a new version of your program,
Xsend me email of the following form:
X
X----
XTo: kno...@ira.uka.de
XSubject: please compile
X
X/*
X <<FROM>> team_name authentification_string
X*/
X/* your source code goes here */
X----
X
X<<FROM>> has to be given exactly as shown. The same is true for the
X"Subject:".
XFor <team_name> insert the name of your team as given in the registration.
XFor <authentification_string> insert the string that I sent you with the
Xregistration acknowledge.
X
XYour program will be compiled automatically shortly after your
Xemail arrives and you will be sent a report about the results of the
Xcompilation. A successfully compiled program is automatically stored
Xto be used in the contest. The latest version is used always.
X
X
X
X---------------------------
XRequirements for programs:
X---------------------------
X
X1. Pure C (ANSI or KR), i.e., no library routines called, except
X int init_random ()
X int log2 (int number)
X int next_random (int low, int high)
X int make_throw (int my_throw)
X int count_points (int throw1, int throw2, int *points1, int *points2);
X (You will receive a detailed description of these functions
X upon registration)
X
X2. Must be compilable with GNU C compiler (gcc).
X
X3. Must be in a single file, no #includes
X
X4. Must have at most 10000 lexical elements (after preprocessing)
X Lexical elements are:
X identifier, keyword, number,
X character in string denoter, character in char denoter,
X special character
X NO lexical elements (i.e. not counted) are:
X blank, Tab, newline, comment
X Information about how many lexical elements your program has is
X sent to you as a report from automatic compilation as described above.
X
X5. The size of the process that runs the program must not grow
X beyond 1024 kB on a SUN SparcStation 2 running SUN OS 4.1.
X The value used to test this is the one shown by 'ps -u' in the column
X labeled 'SZ' (SIZE).
X
X6. Must finish every game of 1000 throws in less than 30 seconds of cpu
X time on a SUN SparcStation 2 (which has about 20 SPECmarks).
X
X7. Source code must contain a verbal description of the main program
X ideas of the strategy: Whether it tries to exploit and/or cooperate,
X and what techniques it uses to achieve that. The description should be
X at least about 15 lines long (but more detailed is fine).
X Please enclose the description in #if 0 ..... #endif.
X The description is not counted in the number of lexical elements.
X
XI recommend (but this is not enforced) that programs do not use
Xfloating point arithmetic and that programs are structured as infinite
Xloops, i.e., do not terminate automatically after 1000 throws.
X
X
X
X-----------------------
XTechnical Environment:
X-----------------------
X
X1. In order to write and hand-test a strategy, you need the definitions
X of the library procedures mentioned above, called 'knobellib.c'.
X The source code for these functions is only 130 lines and will be
X sent to you via email with the notification of acceptance of your
X registration. Link your strategy with this module, but do not include
X the source code of the module into your strategy or else it will
X be rejected. This is the only mandatory software you need; all
X other parts described below are just utilities for your strategy
X development and analysis.
X
X2. If you want to run complete games between two strategies in the same
X kind of environment that will be used in the actual contest, you need
X the source code of the 'knobeln' program (or must write something similar
X yourself). You will need a UNIX machine in order to compile and run it
X (or otherwise must make some simplifications in the code).
X This program was originally written in C-Refine.
X You will receive both a C-Refine and a pure C version.
X
X3. 'protocolfmt' is a Perl script that formats the compact game protocols
X sent to you during the contest (if you request them) to the full format.
X
XThere are two ways to get the source code of these programs
X(about 60 kB altogether):
X
X1. by anonymous ftp (prefered method):
X Sanfrancisco.ira.uka.de [129.13.13.110]: /pub/knobeln94.tar.Z (22 kB)
X (in the directory /pub/knobeln93 on the same server you can also
X find several large files with the software and results of last year's
X Knobeln contest. I will NOT send these by mail)
X
X2. by mailserver. Send email of the following form:
X To: prec...@ira.uka.de
X Subject: SEND knobelnsoftware
X
X
X
X--------------------
XThe Actual Contest:
X--------------------
X
XThe actual contest will be run at the dates given below.
X
XAt some time before, every team has to send its strategy as described
Xabove. It will be compiled and linked automatically, and you will
Xreceive a report about the success of this procedure or any problems
Xthat occur.
XThis automatic compilation feature is disabled during the tournament.
X
XDuring the contest, all participants will receive information about
Xwhat happens, if they have announced a corresponding mail-preference
Xupon registration:
X
X- When the contest starts, the registration record of all participants
X is sent to all participants with mailpreference LAP.
X- When a group starts, a list of its participants (team names only) is sent
X to the members of this group with mailpreference LGP.
X- When a group is finished,
X - the game protocols of all games of participant X are sent to participant
X X if the participant has mailpreference DGP.
X - the game results of all games of participant X are sent to participant X
X if the participant has mailpreference GRP (superfluous if DGP is given).
X - the game results of all games of the whole group are sent to those
X participants that have mailpreference GRG.
X - the ranking of participants in the group is sent to those
X participants of the group that have mailpreference GRR.
X- When a round is finished a handwritten summary of all groups of this
X round is sent to all participants of the contest that have
X mailpreference RSM. These summaries will at least include all
X group ranking, so that RSM makes GRR superfluous.
X
X
X
X------------------
XThe 1993 Contest:
X------------------
X
XA similar contest was run last year; 41 teams from 9 countries participated.
X
XThe differences to this year's rules were:
X1. Two tournaments were run, with a one-week pause in between during
X which the participants could change their strategy.
X2. Strategies did not have to play against themselves.
X3. The Knobeln evolution was not played.
X
X
X
X-------------
XLegal Issues:
X-------------
X
XBy applying for registrations all members of a team assert that they
Xunderstand and agree with the following points:
X The team members allow the organizer of the contest to publish
X all or part of the information contained in the strategy program
X and in the strategy description. Such publication will mention
X the contest context and will give credit to the team by mentioning
X (at least) the team name or the team's organization or the names
X of one or several team members.
X In particular, the team members allow the organizer to distribute
X freely the source code of the strategy programs after the contest.
X
X
X
X----------------
XImportant Dates:
X----------------
X
X94/03/22 beginning of registration
X94/03/23 beginning of compilation service
X94/05/12 registration deadline
X94/05/14 THE CONTEST
X94/05/21 Results posted to Usenet: rec.games.misc, misc.misc
X
XThe time of day of the registration deadline and the contest start
Xis noon Universal Time (UT, GMT). The compilation service ends
Xtwo hours before the contest starts.
X
X
XGood luck and have fun !
X
X Lutz
X
END_OF_FILE
if test 19407 -ne `wc -c <'Announce'`; then
echo shar: \"'Announce'\" unpacked with wrong size!
fi
# end of 'Announce'
fi
if test -f 'FAQ' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'FAQ'\"
else
echo shar: Extracting \"'FAQ'\" \(2322 characters\)
sed "s/^X//" >'FAQ' <<'END_OF_FILE'
XSubject: The KNOBELN FAQ (Frequently asked questions)
X
X
XQuestions:
XQ1. How is KNOBELN pronounced correctly ?
XQ2. What does the word KNOBELN mean ?
XQ3. When and by whom was KNOBELN invented ?
XQ4. What is the history of the KNOBELN contest ?
XQ5. Is it difficult to write a strategy for KNOBELN ?
XQ6. Is it difficult to write a *good* strategy for KNOBELN ?
X
X------------------------------------------------------------------------
XAnswers:
X
XA1. How is KNOBELN pronounced correctly ?
X
XTake the syllables 'ack' (as in acknowledge), 'no' (opposite of yes),
X'bell' (that chimes), and a 'n'.
XThen leave out the first sound, the 'a' of 'ack' and say
X 'ck-no-bell-n'
Xas a single word, with the stress on the first syllable.
XThis is close the the real pronounciation.
X
X
XA2. What does the word KNOBELN mean ?
X
XKnobeln is the german name for the game you would call
X'rock-paper-scissors' in english.
XThe name was chosen since the game played in the KNOBELN contest
Xbears some similarity to 'rock-paper-scissors' in the rules that
Xdescribe who wins a single throw.
X
X
XA3. When and by whom was KNOBELN invented ?
X
XThe rules of the KNOBELN game were invented in 1991 by Lutz Prechelt.
XThe game was inspired by the tournament Robert Axelrod organized
Xfor programs playing the iterated prisoners dilemma as described
Xin his book "The evolution of cooperation" and the article of
XDouglas Hofstadter in Scientific American.
XThe goal was to make the interaction in the game more complex so that
Xit would not be as simple to invent a good strategy as it is for the
Xiterated prisoners dilemma.
X
X
XA4. What is the history of the KNOBELN contest ?
X
XAfter the invention of the game, two small contests were played with
Xstudents of University of Karlsruhe (1991 and 1992). However, there were
Xonly five participants both times, which was a bit unsatisfying.
XThe idea was born to make an international contest and let the participants
Xsend their strategies in source code by email.
XSoftware was written to execute games and rounds in the contest
Xand 1993 the first international KNOBELN contest took place.
X
X
XA5. Is it difficult to write a strategy for KNOBELN ?
X
XNo, if you know how to write C programs.
X
X
XA6. Is it difficult to write a *good* strategy for KNOBELN ?
X
XYes.
X
X------------------------------------------------------------------------
END_OF_FILE
if test 2322 -ne `wc -c <'FAQ'`; then
echo shar: \"'FAQ'\" unpacked with wrong size!
fi
# end of 'FAQ'
fi
if test -f 'example.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'example.c'\"
else
echo shar: Extracting \"'example.c'\" \(1131 characters\)
sed "s/^X//" >'example.c' <<'END_OF_FILE'
X/*
XVery simple strategy - select a random length of the next sequence
Xbetween MINLEN (=8) and MINLEN+EXTLEN (=16).
XAfter that, pick random throws from max(my_last_throw,opponents_last_throw)
Xto MAXNUM (=12288) as long as the sequence goes.
X*/
X
X
X/*
X * my.c Simple strategy for the Knobeln contest
X *
X */
X
X#define MINLEN 8 /* Min. length of non-decreasing */
X#define EXTLEN 8 /* Potential extension to MINLEN */
X#define GAMELEN 1000 /* Length of a whole game */
X#define MAXNUM 12288 /* Biggest number available */
X
Xmain()
X{
X int len = 0;
X int mythrow = 0, yourthrow = 0;
X int myscore = 0, yourscore = 0;
X int whowins = 0;
X int gamecount = 0;
X (void) init_random();
X while (gamecount++ < GAMELEN) {
X if (len-- < 1) { /* Start next series */
X len = next_random(MINLEN,MINLEN+EXTLEN);
X mythrow = next_random(0,MAXNUM);
X } else { /* Continue series */
X mythrow = next_random((mythrow>yourthrow)?mythrow:yourthrow,
X MAXNUM);
X }
X yourthrow = make_throw(mythrow); /* Make/read throw */
X whowins = count_points(mythrow, yourthrow,
X &myscore, &yourscore);
X }
X}
X
END_OF_FILE
if test 1131 -ne `wc -c <'example.c'`; then
echo shar: \"'example.c'\" unpacked with wrong size!
fi
# end of 'example.c'
fi
echo shar: End of shell archive.
exit 0