G-H. Dogfight

Problem G. and H. are coupled. To be succesful in H., G. needs to be solved early in the contest. For more details, please read the scoring section below for task H.

G. Dogfight - simulator (500 points)

Introduction

In this network game, 2 cars are playing dogfight. Rules are the following: The player who survives longer wins. If both players survive until a specific timeout, the game ends in a tie.

Simulation

Each player has a current position x, y and a current velocity vx, vy where vx^2 + vy^2 >= VMIN^2. Car position is controlled by player supplied acceleration ax, ay, where ax^2 + ay^2 <= AMAX^2.

Updating a car position is done by the following calculation:

check(ax, ay)
vx' = vx + ax
vy' = vy + ay
check(vx', vy')
x' = x + vx'
y' = y + vy'
check(x', y')

The next position is connected to the previous one with a trace vector:

line(x, y, x', y')

The checks verify the acceleration, velocity and trace crossing constraints. If any of the checks fail or the new vector intersects with a previous trace vector then the player loses. Otherwise the new vector is added to the global list of traces and should not be crossed.

Initial condition (x0, y0, vx0, vy0) is sent to the players as part of the protocol.

Protocol

Messages from the server
Server messages are all single line text messages, except for the snapshot message, which contains multiple lines. \n (decimal 10 ASCII) is used to terminate lines. In the following table bold means string literal, italic means parameter.
syntax sent to passive players? description
game len yes Game status: len battles are left before your next battle in this game. If len is 0, you need to play in this battle, if negative, you have already played in this game (or in other words in this hour), so you shouldn't expect to play more battles until the next game (next hour).
turn whose no Sent when a new turn started, before car states are updated. whose is you or enemy.
end winner no Sent when a battle ends. winner has the same syntax as whose in turn, or tie on tie.
envseg x1 y1 x2 y2 no A line segment of the environment
carpos whose x y no Current position of a car. whose is the same as in message turn. Position of enemy car is sent only before the first turn.
carvel whose vx vy no Initial velocity of a car. whose is the same as in message turn. Velocity of enemy car is sent only before the first turn.
snapshot start numlines no Sending a base64 encoded JPEG of the current standing. numlines lines are following, then a snapshot end message. Note: JPEG properties and image characteristics are expected to be different between the simulator and the actual device. Line width and color may change on the physical device during the contest.
snapshot end no End of snapshot.
Upon connection, commands are sent in the following order:
  1. game
  2. envseg
  3. carvel
  4. carpos
  5. (if car's just crashed: end)
  6. snapshot start (for active players only)
  7. (base64 JPEG data; for active players only)
  8. snapshot end (for active players only)
  9. (delay)
  10. turn (for active players only)
  11. (loop: go back to step "carpos")
During normal operation the same sequence is used, except for the game message that is sent again only when a new battle is started (or if the client reconnects). There is also a short delay between snapshot end and turn. When a player crosses (or touches) and existing line, the server sends end instead of turn and a new battle starts shortly. Vehicle position for the player is recalculated right after sending the turn command using the last ax;ay data sent by the player. If no data sent since last update, 0;0 is assumed.

Commands from the client

Command is a single line terminated by a newline (\n, decimal 10 ASCII). The server accepts commands any time, but will execute only the last one in the player's turn. If there is no command specified (because the player is not connected, not sending commands in time or at all), command ax=0, ay=0 is assumed.
syntax description
acc ax ay Set acceleration control for the next turn.

Task

The simulator is provided for the teams to have instant access to a sandbox where they can train their AIs any time, without waiting for the hardware. Furthermore teams are initially ordered and paired for task H (dogfight - plotter) according to their performance in the simulator during the first few hours of the contest.

Players can connect the simulator any time, and the server will allocate a new AI instance to the player and a battle starts immediately. Each team can have only one connection at a time, upon a new connection, any existing connection of the team is closed. The server logs the outcome of simulated battles; when task H starts, this information will be used.

Scoring

The first time a team defeats the AI in the simulator, the team gets 500 points.

H. Dogfight - plotter (2500 points)

Task

This round takes place on an actual old-style pen plotter, traces are digitized by an IP camera. The server is started two hours after the contest starts.

Players should be connected to the server all the time. There is one game per hour. Each game consists at most 15 battles. The server will pair up two players (of all 30 possible players) for a battle; those two players are marked active until the end of the battle. All other players are passive. Some messages are sent only to active players, other messages are sent to all players. Commands can be sent only by the two active players.

Scoring

Due to the limited availability of the hardware, the scoring scheme of these tasks is quite complex to allow the best team to score the most. All in all, there are only two things that really matter:

The 24 hours period is split into a soft and a hard fight period. In the soft period, the hardware is not running and teams are playing against an AI in the simulator, all teams in parallel. The simulator is available during the whole contest, but beating the AI in the sim matters more in the soft period. Whenever a team wins over the AI, we save a time stamp. At the beginning of the hard period we determine the initial order-of-strength of teams by those time stamps: teams won against the AI earlier are stronger; strongest team is the first on the list. Those teams who could not defeat the AI during the soft period are randomly placed at the end of the list.

The soft period takes 2 hours, the hard period takes 22 hours.

Once we have an order-of-strength list, hard round starts. In the hard round, before each game we pair up teams according to their place on the order-of-strength list and teams fight eachothers. There are 15 pairs in a game, thus each player plays 1 battle in a game. In that 15 battles, all 30 teams participate exactly once. A game takes slightly less than one hour. If team A beats team B, and team A was lower on the order-of-strength list, we swap the two teams before the next game. This does not affect pairing for the current game but for the next game. On a tie, teams are swapped and neither team gets any score.

At the end, it is not the order-of-strength list that directly matters. Instead, any time a team wins in the hard period, the team earns score proportional to the strength (at that time) of the team that lost the match. Beating the strongest team, 1st placed on the order-of-strength list, is worth 120 points while defeating the weakest team (last on the list) is worth only 4 points. The scale is linear. (So the best team can approximately earn 2500 points during the 22 battles).

Pairing for each game happens as follows, R being the serial number of the current game, first game is 0:

In other words: teams winning more will slowly climb up the list; sometimes a team need to win to keep its place. Being higher on the list lets the team play games for higher scores against more skilled team AIs.

Example

In the first two hours we will publish example images with appropriate lighting conditions. Please check the announcement channel.