8/8/89 Santa Fe Institute's D O U B L E A U C T I O N T O U R N A M E N T CHAPTER 3 -- THE SKELETON PROGRAMS ---------------------------------- This chapter describes the structure of the skeleton programs and the variables defined therein. The description here is largely language- independent; language-dependent details may be found in README files and/or as comments in the software provided for each available language. 3.1 Introduction ---------------- Skeleton player programs are presently available in C, Fortran, and Pascal. The skeleton programs take care of all the bookkeeping and communication details, allowing participants to concentrate on writing the central decision-making routines to implement their strategy. The skeleton programs provided are actually complete programs with a simple built-in strategy, and may be compiled and used as test players. To produce their own player programs, participants will modify the skeletons and re-compile. A complete player program based on one of the skeleton programs consists of the following parts: 1. The strategy routines, 'BID' and 'BUY' for a buyer, or 'OFFER' and 'SELL' for a seller. These routines return a value indicating the user's decision. In the skeleton programs as supplied these routines contain simple algorithms as examples. 2. Miscellaneous user routines that are called at different stages of the game to provide information to the user. These are all empty dummy routines in the skeleton programs as supplied. They do not need to be modified unless users desire to use them to gather information or initialize or update their own variables. 3. Control routines that take care of bookkeeping, communicating with the monitor, calling the strategy and miscellaneous routines, saving and restoring variables, displaying the game, providing random numbers, etc. Participants should not need to change these routines, or even to understand how they work. Note that routine names are written in upper-case (e.g. BID) in this document, but may need to be lower-case in actual programs. In more detail, the user routines are as follows: STRATEGY ROUTINES BID For a buyer, called at the start of each bid-offer step to decide on a bid value, or to pass. OFFER For a seller, called at the start of each bid-offer step to decide on an offer value, or to pass. BUY For a buyer, called at the start of each buy-sell step to decide whether to request to buy. SELL For a seller, called at the start of each buy-sell step to decide whether to request to sell. Note that a player program can play a buyer or a seller, or may be able to play either. If only one of the roles is chosen, then only two of the four strategy routines needs to be developed. However, in the tournament, players that can only play one role will be selected for fewer games, and thus have less opportunity for profit. More details about the return values of these routines is given in the last section of this document. MISCELLANEOUS ROUTINES GBEGIN Called once at the beginning of each game. GEND Called once at the end of each game. RBEGIN Called at the beginning of each round. REND Called at the end of each round. PBEGIN Called at the beginning of each period. PEND Called at the end of each period. BOEND Called at the end of each bid-offer step, after all players' bids and offers have been processed. BSEND Called at the end of each buy-sell step, after all players' buy and sell requests have been processed. 3.2 Variables in the user routines ---------------------------------- The variables and arrays described below are available in all the user routines (strategy routines and miscellaneous routines). They provide all the information available to the player, on which bid/offer/buy/sell decisions must be made. The variable names and meanings are almost the same in all languages, and are defined here in a language-independent way. See the comments in the appropriate skeleton programs for all language-dependent details. None of the variables described should be altered by the user routines themselves; doing so will not have any useful effect. All variables are integers. Prices are represented by integers in the range 1 - 8000. It is of no consequence whether these values are regarded as dollars, cents, or some other unit. Some variables are one-dimensional arrays of fixed length. The length is given in square brackets. Thus, for example, token[4] represents a 4-element array. How this is declared and referenced is language-dependent. In general array indices or subscripts run upwards from 1, not from 0. It is convenient to divide the variables into three classes, according to whether they are public (the same for all players) or private, and whether they are constant or varying: PUBLIC CONSTANTS These variables are unchanging throughout a game (the same in all periods and steps), and are known to all players: nplayers The total number of players in the game, including yourself. nbuyers The number of buyers in the game. This will never exceed 20. nsellers The number of sellers in the game. This will never exceed 20. Note that nbuyers+nsellers = nplayers. bnumber[20] A player-number for each buyer, in the range 1 - 9999. There is one entry for each buyer, 1 to nbuyers, and the remaining entries are zero. These numbers are intended to give a unique identification to each program and participant across all games, so that participants in the pre-tournament Santa Fe Token Exchange games can determine who they have and have not played against. A directory will be available. A value of 9999 is used to mean a human player. Some values may be reported as 0 to mean anonymous; all players will be anonymous in the actual tournament. Do not confuse player-numbers with the player id's (described below) that are used to identify the players in a particular game. snumber[20] A player-number for each seller. Like bnumber[20]. nrounds The maximum number of rounds in the game. This will never exceed 20. nperiods The maximum number of periods per round. This will never exceed 5. ntimes The number of time units in each period. This will never exceed 400. At each time there is first a bid-offer step and then a buy-sell step. A period will not be terminated before all 'ntimes' time units have been played if it is possible for any pair of players to trade with mutual profit. Early termination will not necessarily occur even when no more mutual profit is possible; see the description of the monitor's 'deadsteps' parameter. minprice The minimum price value allowed for any bid or offer. maxprice The maximum price value allowed for any bid or offer. Note that 1 <= minprice <= maxprice <= 8000. gameid An arbitrary unique integer in the range 1 - 9999 that identifies this particular game. The gameid is useful for referring to particular games and for creating unique filenames, etc. It will normally increase from game to game. gametype A 4 (decimal) digit number conveying the values for RAN1,..., RAN4. The RAN(i) values govern the random generation of tokens as described in rule 25 of chapter 7. The RAN(i) values are given by ran(i) = 3^k(i) - 1 i=1,...,4 where k(i) is the i'th digit of gametype, counting from the left, and where 3^k(i) denotes 3 to the power k(i). Thus, for example, gametype = 1236 means RAN1 = 3^1 - 1 = 2 RAN2 = 3^2 - 1 = 8 RAN3 = 3^3 - 1 = 28 RAN4 = 3^6 - 1 = 728 The values for the digits k(i) are restricted to (0,1,...,8). Values of gametype less than 1000 are taken as having leading zeroes. gametype = 0 implies that the token generation method is not revealed. The upper limits on nbuyers, nsellers, nrounds, nperiods, and ntimes specified above may be relevant if you want to construct your own arrays to record historical or strategic information about other players or the game so far. In fact the upper limits will rarely be approached, and you can set lower limits of your own if necessary; see the skeleton programs for details. If the parameters of a particular game exceed your own limits, your program will automatically refuse to play in it. Note also that no token value is allowed to exceed 8000 (due to technicalities of the software design). If the RAN(i) values are set sufficiently high, this limitation will cause an upward truncation in the token distribution at 8000. However rule 25 in chapter 7 guarantees that in the tournament RAN(i) values will be chosen so that such truncation will never occur. PUBLIC VARIABLES These variables change with the progress of the game and are known to all players. All are set to 0 before the start of the game and (except r and p) before the start of each new period (i.e. before the call to PBEGIN). The "unknown" values referred to below can only occur if a player makes a 'late' response (see 'late' below). r The number of the current round, r = 1, 2, ..., nrounds. p The number of the current period within the current round, p = 1, 2, ..., nperiods. t The current time within the current period, t = 1, 2, ..., ntimes. cbid The current bid value if any, or zero if none. In a SELL routine this is the value you accept in a sell request. In a BID routine this is the value to beat; a new bid must be above this value. In a bid-offer step the highest bid (if any) determines the new cbid value before the call to BOEND. The current bid is removed (cbid=0) whenever a trade occurs, before the call to BSEND. coffer The current offer value if any, or zero if none. In a BUY routine this is the value you accept in a buy request. In an OFFER routine this is the value to beat; a new offer must be below this value. In a bid-offer step the lowest offer (if any) determines the new coffer value before the call to BOEND. The current offer is removed (coffer=0) whenever a trade occurs, before the call to BSEND. bidder The id of the holder of the current bid, or zero if none. Between 1 and nbuyers when cbid>0, always 0 when cbid=0. offerer The id of the holder of the current offer, or zero if none. Between 1 and nsellers when coffer>0, always 0 when coffer=0. nbids The number of new bids made by buyers in the last bid-offer step, or 0 if none or unknown. Updated before each BOEND call. noffers The number of new offers made by sellers in the last bid-offer step, or 0 if none or unknown. Updated before each BOEND call. bids[20] The actual bids made by each buyer in the last bid-offer step, or zero if none or unknown. There is one entry for each buyer, 1 to nbuyers, and the remaining entries are zero. The whole array is reset to reflect the new bids before each BOEND call. offers[20] The actual offers made by each seller in the last bid-offer step, or zero if none or unknown. There is one entry for each seller, 1 to nsellers, and the remaining entries are zero. The whole array is reset to reflect the new bids before each BOEND call. bstype A code telling what happened in the last buy-sell step: 0 if no trade occurred, 1 if a buy request was accepted, 2 if a sell request was accepted, -1 if unknown because of a 'late' condition. This is set before each BSEND call. The next three variables provide more detail about the transaction if bstype>0. They are set at the same time as bstype. They are all set to zero if bstype<=0. price The price of the transaction. buyer The id of the buyer involved in the transaction. If bstype=1 this is a buyer whose 'buy' request was accepted. If bstype=2 this is the buyer whose current bid was accepted by 'seller'. seller The id of the seller involved in the transaction. If bstype=2 this is a seller whose 'sell' request was accepted. If bstype=1 this is the seller whose current offer was accepted by 'buyer'. btrades[20] A summary array giving the number of trades that each buyer has made so far in this period. There is one entry for each buyer, 1 to nbuyers, and the remaining entries are zero. A trade for a buyer is an accepted buy request or the acceptance by a seller of that buyer's current bid; in either case one token is consumed. Updated before each call to BSEND. strades[20] A summary array giving the number of trades that each seller has made so far in this period. There is one entry for each seller, 1 to nsellers, and the remaining entries are zero. A trade for a seller is an accepted sell request or the acceptance by a buyer of that seller's current offer; in either case one token is consumed. Updated before each call to BSEND. ntrades The total number of trades made by all players so far in this period. prices[80] The price of every trade that has occurred so far in this period. There is one entry for each trade, 1 to ntrades, and the remaining entries are zero. The value is negative (multiplied by -1) if the trade was made by you. lasttime The time (value of t) at which the most recent trade occurred in this period, or 0 if no trade has occurred yet in this period. PRIVATE VARIABLES Most of these variables change with the progress or the game and are in general different for each player. All are set to 0 before the start of the game. mytrades, mylasttime, pprofit, nobidoff, bo, nobuysell, bs, and late are reset to 0 at the start of every period and round. In addition at the start of each round, rprofit, tradelist[5], and profitlist[5] are reset to zero, and ntokens and tokens[4] are set to their new values. id Your own identification number, between 1 and nbuyers if you are a buyer, and between 1 and nsellers if you are a seller. When the id number of another player is given, it is always clear from context whether it is that of a buyer or that of a seller. role 1 if you are a buyer, 2 if you are a seller. timeout The number of seconds of elapsed (wall) time that you have per step. 9999 implies infinity; the monitor will wait for ever. 0 means a relatively short time, normally used for pipe-based players, that depends on the monitor's 'timefactors' parameters. ntokens The number of tokens that you have available to buy or sell. This is fixed for a given round, but may change from round to round. It will never exceed 4, and in the tournament it will be the same for all players. token[4] The redemption values of your tokens, in token[1], ..., token[ntokens]. The redemption values are given in decreasing order for a buyer and in increasing order for a seller, and are assumed to be used in that order, which maximizes any profits. Any unused array elements are set to 0. mytrades The number of trades (0 - ntokens) that you have made so far in this period. This is equal to the appropriate entry in btrades or strades. If mytrades