Problem Statement



Teams taking part in the competition are offered to develop and implement the behavior strategy of a player in the following game.

1. Rules of the Game

Two players take part in the game. The game is played in the rectangular field consisting of squares. The field size is 17 (number of lines) by 26 (number of columns). Squares are divided into 2 types: passable and impassable (walls). Each passable square belongs to some player, and has garrison in it, which is an army placed on this square. Quantity of garrison is represented by an integer non-negative number.

Players make their moves one after another starting with the first player. One who captures all the passable territory of the game field wins.

Each player is situated in his current position (square) and has available army (integer non-negative number). Making a move a player can stay at his position or move up, down, right, left to the adjacent square if it is passable (not a wall). A player cannot leave the boundaries of the field.

If after changing the position a player is on the opponent's square the battle between available army of the player and garrison placed on this square is started. If the opponent is located on this square himself then an available army of the opponent takes part in that battle too. The battle takes place in the following way. At first, garrison of the opponent and available army of the player enter the battle.

  • If opponent's garrison multiplied by 3 is greater than player's available army then the player loses all his army (it becomes equal to zero) as a result of the battle. At that, garrison and available army of the opponent do not change.

  • If opponent's garrison multiplied by 10 is not greater than player's available army then the army of the player does not change and the opponent's garrison is destroyed in the battle.

  • In all other cases the garrison is destroyed and the player's army decreases as much as the quantity of the garrison was.

If after that the opponent is in the square where the battle takes place then the available army of the opponent enters the battle. The player whose available army was smaller loses all his army as a result of the battle and the army of the other player decreases as much as the quantity of the opponent's army was. If the quantities of the available armies were equal then both lose all their armies.

If after the battle a player has non-negative army he captures the opponent's square and it becomes his own square. At that, the quantity of the garrison placed on that square becomes equal to zero. If a player is on his own square after changing his position (or keeping his position unchanged), particularly after he has captured the square in the battle, he can increase (respectively decrease) his available army at the expense of decreasing (respectively increasing) his garrison placed on this square by the same number. At that, the quantity of the garrison as well as the available army cannot become negative. Each 25 turns (i.e. after each 25th turn of the second player) quantity of the garrisons of all players on each square increases. The garrison with quantity

  • from 0 to 29 (inclusive) increases by one,

  • from 30 to 99 increases by two,

  • from 100 to 299 increases by three,

  • from 300 to 999 increases by four,

  • from 1000 and higher increases by five.

At the beginning of the game and before each turn a player has the following information. It is known for each square whether it is passable or not and whom it belongs to. If the square belongs to a player then the quantity of the garrison on that square is known. In addition the following extra information is given:

  • position of the player (position coordinates on the game field);

  • available army of the player;

  • territory of the player (total number of squares he possesses);

  • territory of the opponent;

  • total army (available army plus garrisons on all squares) of the player;

  • total army of the opponent.

2. Solution Requirements

Judges accept solutions written in the following three languages: C++, Pascal, Java. Participants programming in C++ or Pascal can use the following programming environments: Borland C++ 3.1, Visual C++ 6.0, Borland C++ Builder 5.0, Visual Age C++ 4.0, Borland Pascal 7.0, Borland Delphi 5.0. Judges will consider the proposals of participants to extend the list of programming environments.

Participants should implement two functions: function of initialization init and function that computes the move of the player get_move. Function init is started before the beginning of the game. Function get_move is started before each move of a player.

Pay your particular ATTENTION that a strategy you are to implement should be valid for both players (the first and the second).

Participants can use 32Mb RAM. It is not allowed to store information on the hard disk.

2.1 C++

Participants should give source code with the game strategy to Judges. There should be file named player.cpp with two functions: 

void init();
void get_move(int &new_ipos, int &new_jpos, long &collect_army);
All the available information about the current state of the game is stored in the following global variables:

  • int player is the number of the current player (0 or 1). At that, the number of the opponent is (1-player).

  • int ipos, jpos are position coordinates of the player (number of the line and the column respectively), 1 £ ipos £ 17, 1 £ jpos £ 26.

  • int field[19][28] is two-dimensional array 19×28, with information about squares whether they are passable or not and whom they belong to. If field[i][j] = 0, then the square is impassable (is a wall). If field[i][j] = 1, then the square is passable and belongs to the first player. If field[i][j] = 2, then the square is passable and belongs to the second player. Accordingly, if field[i][j] = (1+player), then the square belongs to the current player, if field[i][j] = (2-player), then the square belongs to the opponent. field[i][j] cannot have other values. Squares of the field have indexes i, j, where 1 £ i £ 17, 1 £ j £ 26. Other (boundary) elements of the array are guaranteed to be equal to 0. In other words, it is considered that the field is bounded by a solid wall.

  • long army[19][28] is two-dimensional array 19×28, with information about quantity of the garrisons on squares belonging to the player. If the square does not belong to the player (belongs to the opponent or impassable) then the respective element of array army is equal to 0.

  • int territory is the number of squares belonging to the player.

  • int opponent_territory is the number of squares belonging to the opponent.

  • long hand_army is the quantity of player's available army.

  • long total_army is the total army of the player (available army plus garrisons on all squares).

  • long opponent_total_army is the total army of the opponent (available army plus garrisons on all squares).

Function get_move accepts (as arguments) three references to variables in which it should write down information about the move, namely:

  • int new_ipos, int new_jpos are new position coordinates of the player. If the move on the new square is impossible the player stays on the same square.

  • long collect_army is the quantity of army which the player is going to take from the new square and add to his available army. If collect_army is negative, then -collect_army is the quantity of the part of available army which the player is going to add to garrison of the new square. If collect_army > army[new_ipos][new_jpos], then collect_army is set equal to army[new_ipos][new_jpos] before the move. If collect_army < -hand_army, then collect_army is set equal to -hand_army before the move. Note that if the move to the new square is impossible then there is no redistribution of army.

Participant can store his data in global variables.

2.2 Pascal

Participants should give source code with the game strategy to Judges. There should be module player.pas with two procedures: 

procedure init;
procedure get_move(var new_ipos, new_jpos : integer; var collect_army : longint);
All the available information about the current state of the game is stored in the following global variables:

  • player_num : integer is the number of the current player (0 or 1). At that, the number of the opponent is 1-player.

  • ipos, jpos : integer are position coordinates of the player (number of the line and the column respectively), 1 £ ipos £ 17, 1 £ jpos £ 26.

  • field : array [0..18,0..27] of integer is two-dimensional array 19×28, with information about squares whether they are passable or not and whom they belong to. If field[i,j] = 0, then the square is impassable (is a wall). If field[i,j] = 1, then the square is passable and belongs to the first player. If field[i,j] = 2, then the square is passable and belongs to the second player. Accordingly, if field[i,j] = (1+player), then the square belongs to the current player, if field[i,j] = (2-player), then the square belongs to the opponent. field[i,j] cannot have other values. Squares of the field have indexes i, j, where 1 £ i £ 17, 1 £ j £ 26. Other (boundary) elements of the array are guaranteed to be equal to 0. In other words, it is considered that the field is bounded by a solid wall.

  • army : array [0..18,0..27] of longint is two-dimensional array 19×28, with information about quantity of the garrisons on squares belonging to the player. If the square does not belong to the player (belongs to the opponent or impassable) then the respective element of array army is equal to 0.

  • territory : integer is the number of squares belonging to the player.

  • opponent_territory : integer is the number of squares belonging to the opponent.

  • hand_army : longint is the quantity of player's available army.

  • total_army : longint is the total army of the player (available army plus garrisons on all squares).

  • opponent_total_army : longint is the total army of the opponent (available army plus garrisons on all squares).

Function get_move accepts (as arguments) three references to variables in which it should write down information about the move, namely:

  • new_ipos, new_jpos : integer are new position coordinates of the player. If the move on the new square is impossible the player stays on the same square.

  • collect_army : longint is the quantity of army which the player is going to take from the new square and add to his available army. If collect_army is negative, then -collect_army is the quantity of the part of available army which the player is going to add to garrison of the new square. If collect_army > army[new_ipos][new_jpos], then collect_army is set equal to army[new_ipos][new_jpos] before the move. If collect_army < -hand_army, then collect_army is set equal to -hand_army before the move. Note that if the move to the new square is impossible then there is no redistribution of army.

Participant can store his data in global variables.

2.3 Java

Participants should give source code with the game strategy to Judges, more explicitly participants should give source code of the class ru.nsu.olympic.strategy.player.Player, implementing interface ru.nsu.olympic.strategy.Player. Further, all mentioned classes and interfaces are placed in package ru.nsu.olympic.strategy.

Interface Player defines two functions: 

public void init(GameInfo gameinfo);
public MoveInfo get_move(GameInfo gameInfo);
Each of them accepts (as an argument) an object of GameInfo class. It contains all the available information about the current state of the game, namely:

  • int player is the number of the current player (0 or 1). At that, the number of the opponent is (1-player).

  • int ipos, jpos are position coordinates of the player (number of the line and the column respectively), 1 £ ipos £ 17, 1 £ jpos £ 26.

  • int field[][] is two-dimensional array 19×28, with information about squares whether they are passable or not and whom they belong to. If field[i][j] = 0, then the square is impassable (is a wall). If field[i][j] = 1, then the square is passable and belongs to the first player. If field[i][j] = 2, then the square is passable and belongs to the second player. Accordingly, if field[i][j] = (1+player), then the square belongs to the current player, if field[i][j] = (2-player), then the square belongs to the opponent. field[i][j] cannot have other values. Squares of the field have indexes i, j, where 1 £ i £ 17, 1 £ j £ 26. Other (boundary) elements of the array are guaranteed to be equal to 0. In other words, it is considered that the field is bounded by a solid wall.

  • long army[][] is two-dimensional array 19×28, with information about quantity of the garrisons on squares belonging to the player. If the square does not belong to the player (belongs to the opponent or impassable) then the respective element of array army is equal to 0.

  • int territory is the number of squares belonging to the player.

  • int opponent_territory is the number of squares belonging to the opponent.

  • long hand_army is the quantity of player's available army.

  • long total_army is the total army of the player (available army plus garrisons on all squares).

  • long opponent_total_army is the total army of the opponent (available army plus garrisons on all squares).

Function get_move should return information about the next move of the player. Function returns an object of Moveinfo class. It contains the following variables:

  • int new_ipos, int new_jpos are new position coordinates of the player. If the move on the new square is impossible the player stays on the same square.

  • long collect_army is the quantity of army which the player is going to take from the new square and add to his available army. If collect_army is negative, then -collect_army is the quantity of the part of available army which the player is going to add to garrison of the new square. If collect_army > army[new_ipos][new_jpos], then collect_army is set equal to army[new_ipos][new_jpos] before the move. If collect_army < -hand_army, then collect_army is set equal to -hand_army before the move. Note that if the move to the new square is impossible then there is no redistribution of army.

Participant can store his data in variables of the class ru.nsu.olympic.strategy.player.Player.

3. Judging and Strategy Restrictions

To determine winners a tournament between strategies of the teams will be held. The tournament consists of several matches between strategies. A match consists of several games between the same strategies on different maps (i.e. initial game situations). Judges grant participants with some of these maps, which can be downloaded here. Winner of the match is determined by the number of victories in games. If the number of victories are the same then the winner is determined by the number of moves spent for that victories. Preference is given to the strategies winning after the less number of moves. Each game ends with the win of some player or with the draw. Player wins if he did not violate the strategy restrictions during the game and was able to capture the opponent's territory before number of moves exceeded the limitation. The player also wins if his opponent violated some of the strategy restrictions. If players did not violate the strategy restrictions and were not able to capture the opponent's territory before number of moves exceeded the limitation then the game ends with a draw.

Restrictions imposed on the strategy are the following.

  • Maximum CPU time allowed for procedure init: 30 seconds.

  • Maximum CPU time allowed for procedure get_move: 0.3 seconds.
Limitation on number of moves is 6000.

Testing will be held on Celeron 433 computers or better.

4. Tools Granted by Judges

Judges grant participants with source code of their programs for debugging the strategy implementations in three languages: for Borland C++ 3.1, Borland Pascal 7.0 and Java. Source code contains procedures of moves processing, basic tools for visualization, and implementation examples of 2 strategies. Description of these tools can be found within the public package (publicsource.rar archive) which can be downloaded here.