K. WW3 (3500 points)

Although air hockey is the common method for resolving problems among the gangs, Bertie prefers to have a plan B, just in case. The alternative to a friendly game is to purchase heavy weapons and tanks and start a large scale war. Before things escalate to this undesired level, Bertie wants to make sure he has the winning strategy. Especially that he does not have any secret weapons, he can only buy the same stuff anyone else can.

Your task is to develop an AI that can come up with the winning strategy in a war. You will need to test your AI against other teams' AIs in tournaments before it qualifies for use by Bertie.

   ww3

Rules

Terminology

The map is a grid of X*Y rectangular tiles. Each tile has one of the following types:
TYPE SYMBOL DEFENSE SLOW REMARK
grass g +2 1
forest f +4 2
town t +3 4 reinforcements, new units, income
water w n/a n/a impassable

Players have a budget, may own towns (a town can be owned by only one player at a time) and arbitrary amount of the following units:
TYPE SYMBOL BASE_HP MOVES ATTACK_RANGE REMARK
scout s 10 10 1
tank t 50 4 1
artillery a 20 6 4
infantry i 10 4 1 can take over towns

Turns

There is a constant number of 2 players participating in a battle. A battle is split into N turns (N % 2 == 0). Each player may move units, buy new units, buy reinforcements in his/her own turn and attack enemy units. The turn begins by increasing the budget by (W*TW) where W is the "town income constant" and TW is the number of towns owned by the player. After the player announced end of turn, the turn timed out (see constant T) or no more moves are possible, the next turn of the next player starts.

Moving units

Units can be moved only to adjacent tiles and can not move diagonally. Each unit has a move-counter that is reset to MOVES+M at the begining of each turn, where MOVES depends on the unit type (see the above table) and M is the "move bonus constant". By moving to an adjacent tile, move-counter is decreased by the SLOW factor of the target tile. The move-counter is evaluated before the move is executed: if move-counter would be decreased below zero as a result of the move, the move fails. If move-counter is zero, the unit can not move or attack or reinforce any more in that turn. If a unit attacks, or it is reinforced, move-counter is automatically decreased to zero. Units can not move on water.

Other units affect movements the following ways:

  1. a unit cannot move onto a tile occupied by another unit
  2. after moving from one of the neighboring 8 tiles of an enemy unit to another of those 8 tiles, the move-counter is set to 0 (the enemy unit exerted "a zone of control"). To put it another way: if the before and after position both has the same enemy unit in the neighboring 8 tiles, the move-counter is set to 0.

Attacks

An unit can fire any tile not further than ATTACK_RANGE tiles away, counted in moves on grass. Any unit staying on the tile under attack will lose truncate((A+B)/D)+1 of its HP, where B is the BASE_HP of the attacking unit, D is the DEFENSE of the attacked tile, A is the "attack bonus constant". If the HP of a unit decreases to or below zero, the unit is destroyed (removed from the game).

Fog of war

Town ownership and enemy units are reported only for areas visible to any of the units controlled by the player. Units see as far as they could move on grass. In the beginning of each turn the server reports all visible enemy unit positions and their HP. If an enemy unit previously seen is not reported again, the location of that unit is unknown.

Towns

If an infantry unit is moved into a town, the town becomes owned by the player who controls the infantry. If any other unit type moves into an enemy town, the enemy player loses the town and the new status of the town is "not owned". An unit with non-zero move-counter staying in a town owned by the same player can be reinforced; this means the HP of the unit will be increased by R, the budget of the user decreased by R. If the resulting HP is larger than the BASE_HP of the given unit type, it is truncated to BASE_HP. The user may buy a new unit at any empty town owned. Cost of a unit is truncate(ATTACK_RANGE*(BASE_HP+MOVES)/C), where C is the unit cost modifier constant. A new unit has 0 move-counter in the turn it was bought.

Goal of a battle and Scoreboard

After N turns of the battle, the battle ends. The current budget of the two contestants are compared. The player with the more money gets +1 points on the scoreboard, the player with the less money gets 0 points. In case of tie, both players get 0.

A series of battles are played in a tournament governed by a swiss system. At the end of each tournament teams get actual contest scores depending on their position in the scoreboard. When a tournament starts, points of all teams on the scoreboard are reset to zero, but initial pairing of teams (by the swiss system) will depend on their ranking in the previous tournament.

Game dependent constants

id meaning
A attack bonus (integer; A >= 0)
C unit cost modifier (integer; C >= 1)
M move bonuns constant (integer; M >= 0)
N number of turns for this battle (integer; N % 2 == 0; N > 30 )
P number of players participating in the battle (P = 2)
Q the actual map (string of X*Y characters)
R reinforcement value (integer; R >= 0)
T turn timeout in seconds (integer; T >= 2; tolerance: 0.02 + network delays)
W town income (integer; W >= 2)
X width of the map (integer; 256 > X >= 16)
Y height of the map (integer; 256 > Y >= 16)

Communication protocol

A command is a three characters long keyword, a space, a keyword-specific arguments and a \n. An argument may contain any character except \n and space. \n is the newline character (ASCII 10). The server may send commands any time, the client may send commands only when the server gives permission.

In command description bold means string literal, italic means name of an argument and _ means space (ASCII 32). Besides the explicitly indicated _ spaces, there are no other whitespace characters in the commands.

For each command sent by the client, either an ACK or an ERR is sent back. Optionally a series of other server commands may follow. The client is not required to wait for the ACK/ERR, and may insert multiple commands at once, however, in this case, the client is responsible for pairing requests with answers (order guaranteed).

Commands from the server

format meaning
BTL _ opponent A new battle starts against opponent, which is either a '?' when the opponent is unspecified or an integer between 0 and 29.
CNS _ name _ value Set value of a constant. value may be an integer or a string but may never contain \n. Note: name is always 1 character long. Map (constant called Q) is a string representing a row-major matrix of the terrain (tile types) with their SYMBOLs. First character is for coord x=0;y=0. A series of CNS commands are sent immediately after BTL, before the first TRN. It is guaranteed that all known constants are sent once (in random order, except for X and Y, which will always precede Q).
MOV _ whose _ fx _ fy _ tx _ ty _ type _ HP Unit moved. whose is f for friendly unit (owned by the player) and e for enemy (opponent contestant's units). fx and fy are the previous, tx and ty are the current coordinates of the unit. type is the SYMBOL of the unit type, HP is the current HP of the unit. HP is never 0. fx;fy may be the same as tx;ty to announce HP change.
NEW _ whose _ x _ y _ type _ HP Position of a new unit. x _ y are the same as fx/fy in MOV. This message is generated if an unseen unit is sighted or a new unit bought (in sight). HP is never 0.
DEL _ whose _ x _ y _ type _ HP Position of a unit which disappeared. x _ y are the same as fx/fy in MOV. This message is generated if a unit is going out of sight (coordinates are the last known ones) or when the unit is destroyed (HP == 0).
ATK _ ux _ uy _ tx _ ty Unit at coordinates ux and uy attacked tile at tx _ ty. ux;uy or tx;ty may be -1;-1, in case source or target tile is not visible. ATK is not sent if neither of those are visible. NOTE: a MOV/DEL command may follow.
TWN _ x _ y _ new owner Town at coordinates x y is owned by new owner, which has the same format as the "whose" field of MOV but also can be n which means the town is not owned.
TRN _ whose A new turn starts for whose. whose is the same as for MOV, plus it may be 'o' when the battle is over. In case of the player's own turn, a BDG and an RDY commands are also sent.
BDG _ budget Reports the player's budget (happens after TRN).
ACK Last command is valid and is being executed. Zero or more status updates and a closing RDY will be sent.
ERR _ code Last command was bogus and can not be executed at all. code is the error code explaining the problem with the request. If the player can send more commands in this turn, an RDY is sent.
RDY No more status updates to be sent, waiting for player's commands.

Commands from the client

format meaning
atk _ ux _ uy _ tx _ ty Unit at coordinates ux and uy should attack tile at tx _ ty. NOTE: a DEL command may follow.
mov _ ux _ uy _ seq Unit at coordinates ux and uy should move seq. seq is a string sequence of s (for south), n (for north) e (for east), w (for west). If any of the moves in the sequence would cause an error, the whole seqence is ignored and an error is reported. If ACK is sent, a series of NEW/DEL commands may follow.
rnf _ ux _ uy Reinforce unit at coordinates ux and uy. A MOV command will follow (for updating the HP). (For costs refer to section Towns.)
buy _ ux _ uy _ type Buy a new unit at coordinates ux and uy of type type One or more NEW command(s) or an ERR command will follow. (For costs check section Towns.)
end Ends turn.

Error codes

code meaning result of
01 unit not owned atk, mov
02 no unit at coordinates atk (ux/uy), mov, rnf
03 no town at coordinates rnf, buy
04 out of range atk
05 not enough money for operation rnf, buy
06 town is not empty buy
07 town is not owned buy, rnf
08 failed move or operation: move-counter is too low mov, atk, rnf
09 failed move: tile already occupied mov
10 syntax error: invalid keyword n/a
11 syntax error: invalid argument (any)
12 syntax error: coordinates out of range (any)
13 command sent out of own turn - no RDY follows (any)
14 number of arguments mismatch (any)
15 connection is closed because of a new connection from the same team (spontaneous)

Communication example

Please test the protocol on the practice server.

TCP ports

10001practice server control (raw CLI, use telnet client)
10002practice server game connection (see protocol)
10003practice server telnet view connection (use telnet client, press 'h' for help)
10012tournament server game connection (see protocol)
10013tournament server telnet view connection (use telnet client, press 'h' for help)