StarWar G00007


pdf   zip


Star War

Enric Rodríguez

1  Game rules

In this game each player commands a fleet of starships in the outer space. The goal is to get the highest possible score by collecting point bonuses and killing other players’ starships.

The game is played on a bidimensional cylindric universe. After unfolding, this universe can be seen as the result of setting side by side the same rectangle repeatedly along the vertical edge:


This repeated rectangle is an n × m grid of cells. Thus, any pair (i, j) such that 0 ≤ i < n determines the position of a cell of the universe. Note that two positions (i,j) and (i,j′) such that (jj′) mod  m = 0 actually refer to the same cell. In what follows we will refer to i and j as the row and the column of the position (i, j), respectively.

Each cell of this universe may be empty or may contain:

  • an asteroid, or
  • a starship (commanded by one of the players), or
  • a missile (previously shot by one of the starships), or
  • a points bonus, or
  • a missile bonus.

Players can look up the content of any cell of the universe during the match.

Each player commands a number of starships which is a parameter of the game. Each starship has a unique identifying number. The starships commanded by the same player have consecutive identifiers.

1.1  Moving and shooting

At each round a player can command any of its starships to move in a particular direction or to shoot a missile (but not the two at the same time).

In general, the movement of the elements on the universe follows the next rules:

  • Starships may move horizontally, vertically or in diagonal. More precisely, in one movement a starship may increment its row by −1, 0 or 1, and its column by 0, 1 or 2.
  • By default, at each round a starship moves horizontally one column, i.e., its row remains the same and its column increases by 1.
  • There is a window that the starships must remain within. This window is a rectangle of dimensions n × mW, where mWm, and is dynamic: it moves forward one column per round. Therefore, at round r, its leftmost upper corner is at position (0, r), and its rightmost lower corner is at position (n−1, r+mW−1). Moreover, a starship moving with the default direction remains always within the window.

    In the game viewer, the window is the part of the universe that will be shown. Since the window is taken as the system of reference for the visualization, it apparently does not move; similarly, starships moving by default apparently do not move either, etc.

  • Asteroids and bonuses do not move.
  • Missiles move horizontally two columns per round.
  • Asteroids, bonuses and missiles may be outside the window. Note that in this case, although they cannot be viewed, they still exist on the universe.

A starship may shoot a missile if it has at least one in its stock (which is then consumed). There is an initial number of missiles in the stock of each starship. This stock can be enlarged by means of missile bonuses. When a starship shoots, the new missile automatically moves forward two columns from the starship position, and then immediately after, the starship also moves with the default direction.

1.2  Collisions in a cell

When a starship and a bonus coincide in the same cell, the starship consumes the bonus (increasing the number of available missiles if it is a missile bonus, or getting more score if it is a point bonus). Once a bonus is consumed, if possible it reappears on a random position outside the window. This random position is guaranteed to be previously empty and such that its surrounding square 5 × 5 is free from missiles or starships.

In the other possible cases of collision, when two elements coincide in the same cell both are destroyed. In particular, if one of the colliding elements is a missile shot by a starship of player A and the other element is a starship of a different player B, then A increases its score.

When a starship is killed, it regenerates if possible after a number of rounds, on a random position of the window. This random position is guaranteed to be previously empty and such that its surrounding square 5 × 5 is free from missiles, starships or asteroids. The number of available missiles is the same as before it died.

As a final consideration regarding collisions, when in a round a starship (or a missile) moves from an initial cell to a final cell, in some cases it is considered that it also passes certain intermediate cells. More specifically:

  1. When a starship moves from cell (i, j) to cell (i+1, j+1), it also passes through cells (i+1,j) and (i, j+1). Similarly when it moves to cell (i−1, j+1).
  2. When a starship (or a missile) moves from cell (i, j) to cell (i, j+2), it also passes through cell (i, j+1).
  3. When a starship moves from cell (i, j) to cell (i+1, j+2), it also passes through cells (i,j+1), (i+1, j+1), (i+1, j) and (i, j+2). Similarly when it moves to (i−1, j+2).
  4. In the other cases it does not pass through intermediate cells.

The exact order in which intermediate cells are visited can be looked up in the map dir2all defined in

1.3  Order of execution of instructions

After the instructions of all players are collected, the following actions take place:

  1. First missiles are moved according to their rules.
  2. Next a random order is determined among the players, and the instructions for their starships are executed following this order. Invalid instructions (for example, moving outside the window limits) are ignored. If a starship receives more than one instruction, only the first one will be taken into account. Starships that have not received any instruction will move by default, in increasing order of identifier.
  3. If appropriate, dead starships and new bonuses (in this order) are regenerated.

1.4  Game parameters

A game is determined by following set of parameters:

number_players(): number of players in the game.

number_rounds(): number of rounds that will be played.

number_rows(): number of rows of the universe (and of the window).

number_universe_columns(): number of columns of the universe.

number_window_columns(): number of columns of the window.

number_starships_per_player(): number of starships for each player.

number_starships(): total number of starships.

number_rounds_to_regenerate(): number of rounds to wait before a starship can regenerate.

number_missile_bonuses(): number of missile bonuses in the game.

number_point_bonuses(): number of point bonuses in the game.

bonus_missiles(): number of extra missiles obtained when consuming a missile bonus.

bonus_points(): number of extra points obtained when consuming a point bonus.

kill_points(): number of points obtained when killing a starship of another player.

All these parameters can be accessed by the players during the game.

2  Programming

The first thing you should do is to download the source code. This source code includes a C++ program that runs the matches and also an HTML5/Javascript viewer to watch them in a nice animated format. Also, a ”Demo” player is provided to make it easier to start coding your own player.

2.1  Running your first match

Here we will explain how to run the game under Linux, but a similar procedure should work as well under Windows, Mac, FreeBSD, OpenSolaris... The only requirements on your system are g++, make and a modern browser like Mozilla Firefox or Chromium.

To run your first match, follow the next steps:

  1. Open a console and cd to the directory where you extracted the source code.
  2. Run make all to build the game and all the players. Note that the Makefile will identify as a player any file matching the expression ”AI*.cc”.
  3. The call to make should create an executable file called Game. This executable allows you to run a match as follows:

    ./Game Demo Demo Demo Demo < default.cnf > default.res

    Here, we are starting a match with 4 instances of the player ”Demo” (included with the source code), with the game configuration defined in ”default.cnf”. The output of this match will be stored in ”default.res”.

  4. To watch the match, open the viewer (viewer.html) with your browser and load the ”default.res” file.

A script for carrying out steps 2-4 automatically is also provided.

Use the --help option of Game to see a list of all options you can use. For instance, the option --list will show a list with all the available player names.

If needed, remember you can run make clean to delete the executable and all object files and start over the build.

2.2  Adding your player

To create a player, copy the file (an empty player that is provided as a template) to a new file with the same name format (

Then, edit the file you just created and change the playername line to your own player name, as follows:

#define PLAYER_NAME Whatever

The name you choose for your player must be unique, non-offensive and less than 12 letters long. It will be used to define a new class PLAYER_NAME, which will be referred to below as your player class. The name will be shown as well when viewing the matches and on the website.

Now you can start implementing the method play(). This method will be called every round and is where your player should decide what to do, and do it. Of course, you can define auxiliary methods and variables inside your player class, but the entry point of your code will always be this play() method.

From your player class you can also call functions to access the board state, as defined in the Board class in Board.hh, and to command your units, as defined in the Action class in Action.hh. These functions are made available to your code using multiple inheritance via the class Player in Player.hh . The documentation on the available functions can be found in the aforementioned header files of each class. You can also examine the code of the “Demo” player in as an example of how to use these functions. Finally, it may be worth as well to have a look at the file Utils.hh for useful data structures.

Note that you should not modify the factory() method from your player class, nor the last line that adds your player to the list of available players.

2.3  Playing against the Dummy player

To test your strategy against the Dummy player, we provide the AIDummy.o object file. This way you still will not have the source code of our Dummy, but you will be able to add it as a player and compete against it locally.

To add the Dummy player to the list of registered players, you will have to edit the Makefile file and set the variable DUMMY_OBJ to the appropriate value. Remember that object files contain binary instructions targeting a specific machine, so we cannot provide a single, generic file. If you miss an object file for your architecture, contact us and we will try to supply it.

Pro tip: You can ask your friends for the object files of their players and add them to the Makefile too!

2.4  Restrictions when submitting your player

Once you think your player is strong enough to enter the competition, you should submit it to the website ( Since it will run in a secure environment to prevent cheating, some restrictions apply to your code:

  • All your source code must be in a single file (
  • Your code cannot use global variables (use attributes in your class instead).
  • You are only allowed to use standard libraries like vector, map, cmath...
  • Your code cannot open files nor do any other system calls (threads, forks...).
  • Your CPU time and memory usage will be limited when executed on The time limit is 1 second for the execution of the entire game. If the time limit has been exceeded (or if the execution of your code aborts), your player will be frozen and will not admit further instructions any more.
  • Your program should not write to cout nor read from cin. You can write debug information to cerr (but remember that doing so on the code you upload can waste part of your limited CPU time).

3  Tips

  • Read only the headers of the classes in the provided source code. Do not worry about the private parts nor the implementation.
  • Start with simple strategies, easy to code and debug, since this is exactly what you will need at the beginning.
  • Define basic auxiliary methods, and make sure they work properly.
  • Try to keep your code clean. Then it will be easier to change it and to add new strategies.
  • As usual, compile and test your code often. It is much easier to trace a bug when you only have changed few lines of code.
  • Use cerrs to output debug information and add asserts to make sure the code is doing what it should do. Remember to remove (or comment out) the cerrs before uploading your code to, because they make the execution slower.
  • When debugging a player, remove the cerrs you may have in the other players’ code, to make sure you only see the messages you want.
  • By using commands like grep in Linux you can filter the output that Game produces.
  • Switch on the DEBUG option in the Makefile, which will allow you to get useful backtraces when your program crashes. There is also a PROFILE option you can use for code optimisation.
  • If using cerr is not enough to debug your code, learn how to use valgrind, gdb, ddd or any other debugging tool. They are quite useful!
  • You can analyse the files that the program Game produces as output, which describe how the board evolves after each round.
  • Keep a copy of the old versions of your player. When a new version is ready, make it fight against the previous ones to measure the improvement.
  • Before competing with your classmates, focus on qualifying and defeating the ”Dummy” player.
  • Make sure your program is fast enough: the CPU time you are allowed to use is rather short.
  • Try to figure out the strategies of your competitors by watching matches. This way you can try to defend against them or even improve them in your own player.
  • DO NOT GIVE YOUR CODE TO ANYBODY. Not even an old version. We are using plagiarism detectors to compare pairwise all submissions (including programs from previous competitions). However, you can share the compiled .o files.
  • Do not wait till the last minute to submit your player. When there are lots of submissions at the same time, it will take longer for the server to run the matches, and it might be too late!
  • Most of the game parameters (number of rounds, ...) will not change, but if your strategy can adjust to them, you will be extra-safe in case some changes are needed.
  • You can submit new versions of your program at any time.
  • If you create your own board for the game, send it to us before the competition starts and maybe we will include it!
  • And again: Keep your code simple, build often, test often. Or you will regret.
Enric Rodríguez
Official solutions
Unknown. This problem is being checked.
User solutions