The 2nd Annual Ellington Bid-Tac-Toe Challenge

Latest Changes

(11/5/07: For the winners: the reception date will be moved from November 8th to another date. We apologize for the inconvenience.)

(11/5/07: The actual scoring is now finished and being reviewed. All who have submitted should get an email in the next couple of days. For privacy, sanity, and other issues, we will not release information about your fellow contestants, more detailed scoring reports, or revised/debugged submissions now that the contest is finalized. Thanks for all the submissions!)

(10/23/07: Clarifications: the students must be enrolled at an accredited university from the United States; the due date is 12 AM, Eastern Time; users of C# should make sure that the code works under Mono so we can run under Unix)

(10/16/07: Clarification: I have replaced two instances of “round” with “game” in the “Challenge Formulation” section.)

(10/15/07: Just a reminder that the contest will be over in two weeks. Please note that the contest director will not be readily available over the weekends, including the last weekend of the contest. Thus, contestants are advised to start earlier and to send their questions in advance as opposed to last-minute.)

(10/11/07: the repetition rule in the “Challenge Formulation” is bolded since some of you missed it. Also, we will be using Python 2.4 for those using Python.)

(10/10/07: “next round” in output should be “nextround” without the space. Also, outputs are expected to be followed by an endline character)

Introduction

Ellington Management Group is a hedge fund with world-class talent from campuses across the nation. To help us identify top programming talent, we are proposing a self-contained challenge requiring only ingenuity and programming skills to solve.

Team Formation / Reward Rules

  1. Each team may have up to two (2) participants. Both participants must be enrolled in undergraduate or graduate studies at an accredited university in the United States. At least one participant must be enrolled at Caltech, MIT, or Carnegie Mellon.
  2. For each campus, the top three performing solutions will receive prizes of $1,500, $1,000, and $500 respectively. The $1,500 winners will be brought to Ellington’s headquarters for a reception.
  3. In addition, One Grand Prize winner will be chosen from among the top winners and will receive an additional $1,000. 

Challenge Formulation

We present a variant of the popular game Tic-Tac-Toe in which players bid for squares (Bid-Tac-Toe). In particular:

  1. There are two players, A and B, each with an initial bankroll of $100.
  2. Players A and B bid in secrecy on the empty squares of a 3x3 grid. Initially all nine squares are empty. Bids must be in (non-negative) whole dollars and must add up to at most the players' respective bankrolls.
  3. Bids are compared square by square: the player who bids more for a square wins it. If the two bids for a given square are equal, it is won by neither player. The players see their opponent's bids at this point. If there is a winner, then the winner removes an amount equal to his/her winning bid from his/her bankroll. A square that is won is won permanently for that game, and no player may bid into that square for the remainder of the game.
  4. Steps (2) and (3) are repeated until all squares are won by some player or three (3) consecutive rounds of bidding have occurred without any change in the state of the board.
  5. The winner is the player who has more three-in-a-row formations. Valid three-in-a-row structures are the same as for Tic-Tac-Toe: vertical, horizontal, or diagonal. If both players have an equal number of three-in-a-row structures, the game is deemed a tie.

The challenge is to find a winning strategy for this game and write code according to the protocol specified below. The strategies submitted will be played against one another in a tournament.

Structure of the Game

You must deliver a program that plays your strategy by following a simple protocol we outline below. You must provide us with the complete source code of your program, written in any programming language you wish that has a free and publicly available implementation. If the language is arcane, please also provide a link to the implementation.

The Program

Your program should communicate solely via standard input/output (i.e. no graphical user interfaces). The program should repeatedly read a single line from standard input, process the command described by the line, and write an appropriate response to standard output. The program should terminate upon reading EOF (end of input) from the standard input.

Each command consists of a sequence of words delimited by whitespace. In the descriptions below, non-italicized words are to be taken literally and each italicized word is a placeholder for a corresponding word in the input. The commands are:

newgame opponentID

This indicates the start of a new game against the given opponent. The opponent ID will correspond uniquely to some other program in the tournament. Your program should output a single line containing 9 nonnegative integers in the format “a1 a2 a3 a4 a5 a6 a7 a8 a9” corresponding to your bids on each of the 9 squares, followed by an endline character. Board squares are enumerated from left to right and top to bottom:

1

2

3

4

5

6

7

8

9

nextround b1 b2 b3 b4 b5 b6 b7 b8 b9

Another round of play is required for this game. The bs are your opponent's bids for the previous round. You can deduce the state of the game from these bids and the bids you provided earlier. Respond with the format “a1 a2 a3 a4 a5 a6 a7 a8 a9” for your next set of bids (followed by an endline character). You must specify “0” for an already-occupied square.

gameover b1 b2 b3 b4 b5 b6 b7 b8 b9

The game is over; the bs again are your opponent’s bids, and you can deduce the winner or whether the game tied. Do not provide any response.

If at any time you give an illegal set of responses (not giving non-negative integers, not supplying “0” for an already-occupied square, bidding a set of values with sum exceeding your bankroll, etc.), you forfeit that round. Your input will be treated as “0 0 0 0 0 0 0 0 0” for that round, and you will receive a “gameover” command in the format above.

Your program will see the following repeatedly: a newgame command, followed by zero or more “nextround” commands, followed by a “gameover” command. A single execution of your program can expect to play many games against each of the other contestants’ programs. Your program can maintain whatever state it wants to in memory, but it cannot preserve state across executions and/or write to a file. Programs that violate this rule will be disqualified. It may, however, read from files in the current working directory.

Your program should make reasonable demands on computer resources. As a rough guideline, do not use more than a hundred megs of memory or take more than five seconds to respond to a command. We may disqualify any program that exceeds these bounds.

Determining the Winner

We will judge entries solely on how they perform in a tournament. We do not specify the details of the tournament, except to say that each submitted strategy will have an opportunity to play every other at least 100 times.

Example Game

Mark faces off against his nemesis Rebecca, with their strategy having identifiers MarkMcLovin and rebecca111 respectively.

Mark receives newgame rebecca111 and outputs 2 4 2 4 10 4 2 4 2. Rebecca receives newgame MarkMcLovin and outputs 2 7 2 14 2 1 6 4 2:

 

R

 

R

M

M

R

 

 

Note that the two strategies bid the same amounts for squares 1, 3, 8, and 9, so those squares are not owned by anyone. Mark deducts $10 + $4 = $14 from his bankroll, ending with $86. Rebecca deducts $7 + $14 + $6 = $27, ending with $73.

Mark then receives nextround 2 7 2 14 2 1 6 4 2 and Rebecca receives nextround 2 4 2 4 10 4 2 4 2. From this, they were both able to deduce the state of the board as above.

Mark outputs 25 0 25 0 0 0 0 0 30 and Rebecca outputs 25 0 17 0 0 0 0 13 31. The board now looks like:

 

R

M

R

M

M

R

R

R

Mark deducts $25, ending with $61. Rebecca deducts $13 + $31, ending with $29.

Mark then receives nextround 25 0 17 0 0 0 0 13 31 and Rebecca receives nextround 25 0 25 0 0 0 0 0 30.

Mark outputs 61 0 0 0 0 0 0 0 0 and Rebecca outputs 29 0 0 0 0 0 0 0 0. Mark wins the last square:

M

R

M

R

M

M

R

R

R

Unfortunately, Rebecca had already won. Mark will receive gameover 29 0 0 0 0 0 0 0 0 and Rebecca will receive gameover 61 0 0 0 0 0 0 0 0. From this, they both deduce that Rebecca had won, and they will both receive new newgame commands, maybe with each other, maybe with another strategy.

Response Submission & Details

All responses should be sent to challenge AT-SIGN ellington.com.

 

The Challenge ends on Monday, October 29th at 12 am, Eastern Time.

 

Any questions about the challenge should be directed to the same email address. The response should contain all of the following:

 

  1. Team Name and school represented (Caltech, MIT, or Carnegie Mellon).
  2. Team Members (up to 2) with academic affiliations.
  3. The source code for the strategy, in the form specified by the previous section.
  4. A brief description (2 paragraphs) of the strategy in English, explaining the idea behind it and the principles it uses.
  5. A brief description (1-2 paragraphs) of how the workload was split between the team members (if applicable).
  6. Optional: Additional (text only!) files that your strategy may read from, but not write to.

Reception

On a TBA date, Ellington will be hosting a reception for the $1,500 winners from each school at Ellington’s headquarters in Old Greenwich, CT.

You will meet with various business leaders and get to know Ellington during the afternoon.

Note:  Ellington will be responsible for making your travel arrangements.

 

Company Overview

Ellington Management Group, L.L.C. is an investment management firm founded in December 1994. With over 150 professionals, Ellington manages over $24 billion in collateralized debt obligations ("CDOs") and over $5 billion of hedge fund capital, net assets under management.

 

Ellington pursues a relative value investment strategy with the objective of capturing a stable income stream while minimizing return volatility over time. This strategy relies on Ellington’s ability to identify and purchase undervalued securities, and its intensive analytical approach to risk management. Ellington’s risk management process emphasizes the proper hedging of portfolio risks. Given the complexity of instruments such as MBS derivatives, this is only possible with sophisticated and precise quantitative tools and methodologies that are the foundation of Ellington’s investment technique. Analyzing prepayment risk, in particular, necessitates the development and continuous refinement of sophisticated statistics-based computer models.

 

At Ellington, top programming talent builds the backbone of our multi-billion dollar MBS trading platform. We develop trading systems, perform statistical analyses on historical data, and build advanced models that support highly profitable trading decisions. 

 

FAQ

Q: I am going to write my program in Perl/Python; how should I write the first line?

A: Just send us code that works on your computer. We will change the first line so it works on ours.

Q: Can we have two team members from two of the three listed schools?

A: Yes. But only one team affiliation can be selected.

Q: Can we use C#?

A: Yes, but make sure that it works under Mono so we can run under Unix.

Last updated: 10/15/2007