This is the archived CodeCup 2010 website.
Click here to go to the new CodeCup website.
CodeCup 2010 - An online programming competition  

CodeCup 2010 - An online programming competition
Introduction
Rules
Competitions
FAQ
Links

Rules of the game Amazes

Introduction

Amazes is a two player game that is played inside a square maze on rectangular grid of dimensions 25 x 25. The player that starts the game is the 'Red' player. The other player is the 'Blue' player.
Both players are located in the maze and initially do not know the layout of the maze. They are provided with information about what they can see from their location, and how far away from their opponent they are. A player cannot see the other player. Each turn consists of the player taking steps through the maze. The players earn points by discovering previously undiscovered squares in the maze, but lose points by taking steps.
The Red player starts by getting information about what is visible from his position. He must then indicate which steps he wishes to take in the maze. Once he is done moving about, the Blue player gets information and also takes steps. After this it is Red's turn again. The maximum number of turns for each player is 150.
The final score of each player is determined by the number of points collected during the game.

Goal

The goal of the game is to score as many points as possible by discovering previously undiscovered squares in the maze. A player does not necessarily have to visit a square in order to discover it.
A player will score more points by the following:
  • Efficient discovery of a square (i.e. fewer moves is better).
  • Earlier discovery of a square (i.e. visiting a square before your opponent visits it).
  • Moving into the opponent's position at the end of a turn.
  • Discovery of all squares and then moving into the position of the opponent at the end of a turn (sudden death).

The Maze

The players do not receive a map of the maze beforehand. The exact layout of the maze is therefore unknown, but some properties of the 625 squares of the maze are known beforehand:
  • The maze consists of 25 x 25 squares.
  • It is impossible to step out of the maze (the outer edges are walls).
  • A player can reach the entire maze (all squares are somehow connected).
  • Each corner of a square is connected to at least one wall.
  • There may be multiple possible paths to get from one square to another square.
The following is an example of a valid maze.
Sample of a valid maze
You can find more examples of mazes here.
During the competition, a different maze will be used for each round.

Starting positions

The players start in a randomly determined square somewhere in the maze. These positions are chosen such that the Euclidian distance at the beginning of the game is at least √288 ≈ 17. The Euclidian distance between the two players is calculated using the following formula:
√(Δy^2 + Δx^2)
Δy is the vertical distance in squares between the two players. Δx is the horizontal distance in squares between the two players.
The Euclidian distance is equivalent to using Pythagoras' theorem to calculate the distance.
The starting position of a player is chosen so that there is no wall directly behind the player (i.e. it is always possible to take a step backwards).

Making a move

The players take turns moving around the maze. A changes the position of the player (i.e., in which square are you located) and may change the orientation of the player (i.e., which direction are you facing).
Before making a move, a player is given information about the situation of the maze. This information consists of information about the maze directly around you, as well as information about the Euclidian distance to your opponent.
A single turn consists of several steps and turns you wish to make.

Getting information

A player can read information about the current situation from stdin. The information is given in the form of five lines. The first four lines describe what you see in the corridors respectively ahead of you, to your right, behind you and to your left. The last line is the squared Euclidian distance to your opponent. This number is always an integer.
A line that describes a corridor consists of several characters that describe the consecutive visible squares of the corridor. The final character is always a 'W'. The following characters may be used:
  • B Opening in both directions of the square.
  • L Opening to the left.
  • R Opening to the right.
  • N No opening on either side.
  • W A wall (you cannot see further).
The following example demonstrates the information that you are given before making a move. The information that the red player is given is:
This sample is not fully complete. During the game you will also receive the fifth line with the squared Euclidian distance to your opponent, as is specified earlier on this page. 
W
W
LLBNW
W
The two vertical walls are discovered because you know that each corner in the maze is the endpoint of at least one wall.

Making your move

The players take turns writing instructions to stdout.
In order to avoid serious delays, you must flush stdout immediately after you've written to stdout. Note that you need to do this before starting to read from stdin, otherwise the jury software may never receive your output.
A turn consists of a single line of instructions of moves. A line must have between 1 and 256 (inclusive) characters. A move is basically an instruction to step into another square and to change your orientation so that you are facing away from the square that you came from.
  • F Step into the square that you are facing
  • T Turn around and step into the square that you are now facing
  • L Turn left and step into the square that you are now facing
  • R Turn right and step into the square that you are now facing
There are some restrictions to your movement:
  • If you attempt to make more than 256 steps in one turn you will be disqualified and you will get a score of 0. The jury will not perform any of your moves and takes over by performing a 'T' for you player the rest of the game.
  • If you attempt to step through a wall, you will stop and no further steps will be performed (your player will not move, nor change orientation).
  • If you end your turn in the same square that you started your turn on, regardless of why this happens, an extra 'T' step will be performed by the judging software. Note that this extra step may cause your player to actually take 257 steps.
  • If your program crashes, runs out of time, outputs too many characters or outputs other characters than 'F', 'T', 'L', or 'R', the jury software will take over and will perform a single 'T' move each time you are expected to move.
If in the previous example the player outputs 'TFRFF' the player runs into a wall and ends up in the following situation:
Note that the 'R'-move would run you into a wall. Therefore the entire move is not performed, nor are any of the following moves performed.

Special information

The player that starts the game gets an extra first line of input that says 'Start'. Based on the presence of this text during your first move, you can determine whether you are the first or second player.
If on the first line of input the text 'Quit' is written, the players program must exit normally.

End of the game

The game can end in two ways:
  • Normal ending; both players have taken 150 turns.
    After 150 turns your program is expected to terminate itself. You mustn't wait for a 'Quit'.
  • Sudden death; one player has discovered all 625 squares of the maze and has ended the turn on the square of the opponent.
Note that the game does not end if one of the two players crashes, makes an illegal move or runs out of time. In this case the judge will take over for this player and will have the player move back and forth on the same two squares as if the given instruction were a consistent 'T'. The other player will still get a chance to finish 150 turns and collect as many points as possible.

Points & score

During the game, the players may earn points. The number of points is used to determine the final scores of the players.

Points

You start with 0 points. While playing you may earn or lose points according to the following rules:
  • For each step you wish to take, you lose 1 point.
    This means that if you wish to take x steps and you run into a wall after y steps, you will still lose x points. Basically you will lose points based on the number of characters in the string you write to stdout. If you write more than 256 characters your program behaves illegally and you score 0 points.
  • For each square you discover, you earn 1 point.
  • For each square you discover before your opponent has discovered it, you earn 1 extra point.
  • If at the end of your turn you are in the same square as your opponent, and you have not yet discovered all squares, you earn 100 extra points.
If the game ends because of sudden death, the number of points of the player that made the last move is doubled. The number of points of the losing player is set to 0.
For the purpose of the extra points that you may earn by being first to discover a square, the time of discovery is important. At the beginning of your turn, you stand still and look around you. This is the time that you discover many new squares.
This implies that you cannot discover new squares after your last turn.
During your turn you may walk across squares that you have not yet discovered. They are discovered immediately.

Score

Your final score is determined according to the following rules:
  • If your program has crashed, your score is 0.
  • If your program has run out of time, your score is 0.
  • If your program has output illegal characters, your score is 0.
  • If your program has output too many characters, your score is 0.
  • If your program earns less than 0 points, your score is 0.
  • If your program earns more than 1000 points, your score is 1000.
  • Otherwise your score is the number of points earned.

Discovery

You score points based on the new discovery of squares in the maze.
The discovery of squares, walls, and openings between squares is determined by the jury software according to the following rules:

General rules

  • A square can be 'discovered' once by each player during a game.
  • A square can be 'discovered first' only once during a game.
  • A wall can be discovered once by each player during a game.
  • An opening can be discovered once by each player during a game.
  • Players do not have direct knowledge about squares discovered by the other player.
  • A square is 'discovered first' by a player if the player discovers the square when the opponent has not (yet) discovered the square.
  • The discovery rules do not take discoveries by the opponent into account.

Discovery of squares

  • A square has been discovered if, at the beginning of your turn, you can potentially see it in any orientation from your current position. Any squares that are directly behind openings to the left and right of the directions in which you are looking have also been discovered.
  • A square has also been discovered if you have visited the square during a move.
  • A square that you have not yet discovered, but for which you have discovered three of its walls, is also discovered. This square is called a 'dead-end'-square. The opening from this square to the next square is also discovered.
  • A square that you have not yet discovered that has one discovered opening to a 'dead-end'-square and two discovered walls is also discovered. This square is also called a 'dead-end'-square. Now both openings are discovered.
  • A square that you have not yet discovered that has two discovered openings to 'dead-end'-squares and has one discovered wall is also discovered. This square is also called a 'dead-end'-square. The three openings from this square are also discovered.
  • A square that you have not yet discovered that has three discovered openings to 'dead-end'-squares is also discovered. This square is also called a 'dead-end'-square. All four openings for this square are discovered.

Discovery of walls

At the beginning of the game you do not know where you are located in the maze, or in which direction you are facing. Initially you will not know whether a wall is an interior wall or part of the outer edge of the maze.
  • A wall is discovered if, at the beginning of a turn, you can see it: the wall is along the sides or end of the corridor that extend from your position.
  • If for a corner in the maze you have discovered that three edges are openings, the fourth edge has to be a wall and is discovered.
  • If you have discovered, or know of open connections to, at least one square in all 25 columns of the maze, the vertical walls on the outside (the outer edges of the maze) are discovered.
  • If you have discovered, or know of open connections to, at least one square in all 25 rows of the maze, the horizontal walls on the outside (the outer edges of the maze) are discovered.
  • If the 25 walls of one outer edge of the maze have been discovered, the 25 walls on the opposing side are also determined as discovered.

Example game

You can watch an example game!

Discovery example

Play this applet to see an extreme example of the square and wall detection rules:
Right after the information stage of turn 2, the red player knows some of the walls of the dead end corridor at the right corner, of course, the red player doesn't know this yet, because he doesn't know where he is inside the maze.
Note that in turn 2 this player is going into an area which is entirely unknown. As described this is still a valid move, the red player is just lucky that there is no wall on it's path.
Or maybe we put this all up to keep the example short, who knows!
Right after the information stage of turn 4, the red player also knows some of the walls of the dead end corridor at the left. The number of known squares horizontally is now 23 so the red player still doesn't know any of the walls of the left or right outer edges.
This image has been modified for clarity
This is what the situation looks like after the 4th turn. The player has discovered the long corridor and took a last step to the left. This square was already discovered, but two of the edges (the bottom one and the right one) were not yet discovered. The player is about to discover more!
This image shows what is going on during the information stage of turn 5. The red player detects that the square at the right (marked by the number 0) exists (it is discovered). So the player has found squares in each of the 25 rows (note that we've used the verb found instead of discovered).
Move one to the next image to see the result of the more complicated detection rules.
This is the advanced part of the information stage of turn 5. The jury software iterates through the list of rules until there is no new information available:
  • The first thing the red player finds in the advanced stage is that it knows about the 25 rows. According to the rules this reveils the location of the outer edges at the top and at the bottom.
  • Let's have a look at the fields marked with the number 1. These fields were not yet discovered, and we know that this field has three walls (we already knew two of them and just discovered the third). The red player discovers these fields and marks them so it knows that these fields belong to a dead end.
  • Because we know the fields marked with 1 have three walls, we also know that the fourth edge has no wall, so there has to be something at the left square marked 3 and the right square marked 2. The red player just marks these fields as 'exists' (which is different than 'discovered' and 'dead end').
  • Now we take a look at square 2. It has two walls and one connection to a field which is marked as a dead end. This gives us the knowledge that there has to be a connection to the right, so we discover the field and mark it as 'dead end' and after that we mark the right square 3 as 'exists'
  • The red player now knows of at least one square in each column that it exists (not necessarily discovered), so the outer edges to the left and the right are discovered.
  • The rule applied to square 2 can now be applied to both squares 3.
  • The same goes for the squares 4.
The squares below the squares 4 are not discovered, because they still have two edges the red player knows nothing about.