From prechelt@ira.uka.de Mon Mar 14 17:46:17 EST 1994 Article: 21078 of comp.ai Xref: glinda.oz.cs.cmu.edu comp.ai:21078 comp.ai.edu:1660 comp.ai.philosophy:17239 comp.edu:9300 comp.groupware:3252 comp.lang.c:93571 comp.programming:8723 comp.protocols.misc:3419 comp.sources.wanted:29525 comp.theory.dynamic-sys:1832 comp.theory.self-org-sys:550 comp.unix.programmer:17580 Path: honeydew.srv.cs.cmu.edu!nntp.club.cc.cmu.edu!news.sei.cmu.edu!cis.ohio-state.edu!math.ohio-state.edu!howland.reston.ans.net!xlink.net!ira.uka.de!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,comp.unix.programmer Subject: Announcement: International KNOBELN contest Date: 12 Mar 1994 17:36:46 GMT Organization: University of Karlsruhe, Comp. Sc. Dept., FRG Lines: 498 Message-ID: <2lsujeINNl50@iraun1.ira.uka.de> NNTP-Posting-Host: i41s25.ira.uka.de =============================================== First Announcement of the 2nd International KNOBELN --- Game-Strategy Programming Contest =============================================== This is an announcement for the KNOBELN-contest, taking place on Saturday, May 14th, 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 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/12 registration deadline 94/05/14 THE CONTEST 94/05/21 Results posted to Usenet: rec.games.misc, misc.misc The time of day of the registration deadline and the contest start is noon Universal Time (UT, GMT). The compilation service ends two hours before the contest starts. Good luck and have fun ! Lutz -- Lutz Prechelt (email: prechelt@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.