The power of Sauron, the Lord of the Rings, is spreading throughout Middle Earth. People flee in terror from his bloodthirsty ork soldiers. As a result, once prosperous cities are now abandoned, and vast areas of land have become as lifeless as a desert. Sauron’s troops would quickly conquer all Middle Earth... were it not for their own greed and ambition.
In this game, four players compete to conquer an island of Middle Earth for Sauron. The winner of a match is the one that gets the highest score at the end.
The map of the island is represented with a (randomly generated) square board. The cells on this board can be of different types: WATER, GRASS, FOREST, SAND, CITY or PATH. Being an island, the board is surrounded with WATER. Moreover, cells of type CITY are grouped into rectangles representing cities, hence the name. Similarly, cells of type PATH are grouped into sequences that form paths. Paths connect different cities and never cross each other.
In order to conquer the island, each player runs an army of ork soldiers. At each round of the match, players command their orks. Any player that tries to give more than 1000 instructions in the same round will be aborted. An ork can be instructed to remain still or move one cell towards the north, south, east or west direction. If an ork receives more than one instruction, all but the first one are ignored. Orks cannot move to cells with WATER (since otherwise they would lose the layer of dirt on their skin). On the other hand, they can move to all other cells. However, when an ork moves, its health (an integer value) decreases. Depending on the type of cell where an ork goes, this decrement in health may be different. When an ork reaches a negative health, it dies and regenerates under the control of the same player. Initially all orks have the same health, and when they regenerate they get this same amount of health again.
Each cell of the board can be occupied by a single ork at most. In the particular situation that an ork A attempts to move to a cell where there is already another ork B (who has moved there previously in the same round, or was there earlier), the following cases are considered:
When an ork dies, it regenerates at the next round on a random position on the shore of the island, that is, on a cell adjacent to the sea which is not WATER, CITY or PATH. Similarly, initially all players have their orks randomly distributed on the shore.
At the beginning of a match all cities and paths are empty, i.e., do not have any orks on their cells. However, once the game starts, orks can move to them. Points are then computed as follows. At the end of a round, for each city the number of orks of each player on its cells is counted. If there is a player who has strictly more orks on the city than any other player, then this player conquers the city; in case of a tie, the conqueror of the city (if any) does not change from the previous round. In any case, for each city currently conquered by a player (i.e., currently under their control), this player accumulates a number of points which is bonus_per_city_cell() × the size of the city (that is, the number of its cells); for paths the same applies as for cities, but the number of accumulated points is bonus_per_path_cell() × the size of the path. Finally, for each player, their graph of conquests is considered. In this graph, the vertices are the conquered cities, and the edges are the conquered paths that connect conquered cities. For each connected component of the graph with i vertices, additional factor_connected_component() × 2i points are obtained.
Let us illustrate with an example how the score is computed. Figure ?? shows a screenshot of the game. Blue represents WATER, light green represents GRASS, deep green represents FOREST, light yellow represents SAND, deep grey represents CITY and light grey represents PATH. The orks of a player are identified with small squares of the same color. Conquered cities and paths are filled with a crossed grid of the color of the player that conquered them.
Let us now count the score of the red player accumulated in the current round:
Thus, in total the red player has accumulated 213 points in this round.
In general, the execution of a round follows the next steps:
A game is defined by a board and the following set of parameters, whose default values are shown in parentheses:
nb_players(): number of players (4) rows(): number of rows of the board (70) columns(): number of columns of the board (70) nb_rounds(): number of rounds of the match (200) initial_health(): initial health of each ork (100) nb_orks(): number of orks each player controls initially (15) cost_grass(): cost in health of moving to a cell of type GRASS (1) cost_forest(): cost in health of moving to a cell of type FOREST (2) cost_sand(): cost in health of moving to a cell of type SAND (3) cost_city(): cost in health of moving to a cell of type CITY (0) cost_path(): cost in health of moving to a cell of type PATH (0) bonus_per_city_cell(): bonus in points for each cell in a conquered city (1) bonus_per_path_cell(): bonus in points for each cell in a conquered path (1) factor_connected_component(): factor multiplying the size of connected components (2)
Unless there is a force majeure event, these are the values of parameters that will be used in the game.
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 HTML viewer to watch them in a nice animated format. Also, a “Null” player and a “Demo” player are provided to make it easier to start coding your own player.
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 Google Chrome.
To run your first match, follow the next steps:
to build the game and all the players. Note that Makefile identifies any file matching AI*.cc as a player.
./Game Demo Demo Demo Demo -s 30 -i default.cnf -o default.out
In this case, this runs a match with random seed 30 where four instances of the player “Demo” play with the parameters defined in default.cnf (the default parameters). The output of this match is redirected to the file default.out.
to see the list of parameters that you can use. Particularly useful is
to show all the registered player names.
If needed, remember that you can run
to delete the executable and object files and start over the build.
To create a new player with, say, name Sauron, copy AINull.cc (an empty player that is provided as a template) to a new file AISauron.cc. Then, edit the new file and change the
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 State class in State.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. The documentation on the available functions can be found in the aforementioned header files. You can also examine the code of the “Demo” player in AIDemo.cc as an example of how to use these functions. Finally, it may be worth as well to have a look at the files Structs.hh for useful data structures, Random.hh for random generation utilities, Settings.hh for looking up the game settings and Player.hh for the me() method.
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 registered players.
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.
You can also ask your friends for the object files of their players and add them to the Makefile by setting the variable EXTRA_OBJ.
Once you think your player is strong enough to enter the competition, you should submit it to the Jutge.org website (https://www.jutge.org). Since it will run in a secure environment to prevent cheating, some restrictions apply to your code: