Subject: Adversarial Nanomunchers Architecture
From: <Saved by Windows Internet Explorer 7>
Date: Wed, 22 Oct 2008 08:01:28 -0400

Adversarial Nanomunchers Architecture

Class:

Heuristic Problem Solving

Instructor:

Prof. Dennis Shasha

Architect:

Mike Eltsufin

Competition Date:

October 28, 2008

Revisions

October 19, 2008:

initial draft created

October 20, 2008:

added an explanation of the game and the game loop

October 21, 2008:

eliminated the ability to drop new nanomunchers to kill the old
ones
changed the ADD example to show that repeating codes are allowed
in nanomuncher programs

Introduction

A description of Adversarial
Nanomunchers can be found on the course home page.

In this version of adversarial nanomunchers, players will be given an
opportunity to add new nanomunchers to the graph before each time step.
Consequently, there is no need to allow delayed deployment, and all nanomunchers
will have an immediate start time.

After 2 players have joined, the game begins with an uninhabited graph.

The game server informs each player of the structure of the graph and the
total number of nanomunchers they can deploy. Each player responds with an
attempt to place zero or more nanomunchers on the graph. Nanomunchers can only
be placed at uneaten and uninhabited nodes because otherwise they would die
immediately.

After deploying new nanomunchers, there could be more than one new
nanomuncher at a node. If a new nanomuncher is placed on top of an old one, the
new one dies immediately. But if two or more new nanomunchers are placed at a
node, the game server randomly picks the one to keep. In this process some
nanomunchers may die, leaving at most one alive nanomuncher at each uneaten
node.

The living nanomunchers then eat the nodes at which they are located.

Following the eating, nanomunchers attempt to synchronously move according to
their programs. Immediately, some may die if they have nowhere to move.

Others that do make it to a new uneaten node, may find themselves colliding
with another nanomuncher which has also just moved to that node. Here, the
conflicts are resolved according to the living priority rules: up > left >
down > right. The move just made before the collision is used for the living
priority.

At this point, the time step is completed, and all living nanomunchers are
sitting on uneaten nodes. If no eating happened during the time step, the game
ends, even if one of the players has more nanomunchers to deploy. Otherwise, the
game server proceeds to the next time step by asking the players to deploy new
nanomunchers.

In pseudocode, the game proceeds roughly as follows:

t = 0
do
{
ask players to deploy new nanomunchers

resolve nanomuncher collisions where old kills new, and random among new

nanomunchers eat the nodes at which they are located

synchronous move

resolve nanomuncher collisions according to living priority rules

t++
} while (nodes eaten this round is greater than 0)

Communication Protocol

The game server and the players communicate with each other through TCP/IP
sockets. The game server listens for connections on the specified port. After
the player connects, the game server expects a JOIN message from the player. The
game server responds with an ACK message, if the join request was successful.
After both players have joined, the game server starts the game by beginning to
send PLAY messages to each player before each time step. The PLAY message
contains information about the current state of the game. Each player must
respond with an ADD message providing 0 or more new nanomunchers to deploy. The
game server will respond with an ACK or a NACK, depending on whether the request
was successful.

Messages Summary

Message

Source

Destination

Short Description

JOIN

Player

Game server

player joins the game

PLAY

Game server

Player

prompts player to add new nanomunchers before each time step

ADD

Player

Game server

player adds new nanomunchers

ACK

Game server

Player

positive acknowledgement of a message from player

NACK

Game server

Player

negative acknowledgement of a message from player

GAMEOVER

Game server

Player

game over

JOIN Message

Source:

Player

Destination:

Game server

Syntax:

JOIN:<name>

Example:

JOIN:Mike

A successful join attempt will result in an ACK message sent back to the
player with the player index: ACK:0 or ACK:1. A failed attempt to
join will result in a NACK message: NACK:<reason for failure>.

PLAY Message

Source:

Game server

Destination:

Player

Syntax:

PLAY:<uneaten graph nodes>:<graph edges between uneaten
nodes>:<red (0) player score>:<red (0) player
seconds remaining>:<red (0) player nanomunchers left
count>:<red (0) player alive nanomunchers>:<blue (1) player score>:<blue(1) player seconds
remaining>:<blue (1) player nanomunchers left count>:<blue (1)
player alive nanomunchers>

uneaten graph nodes:

a semicolon-separated list of <node
id>,<x>,<y>

graph edges between uneaten nodes:

a semicolon-separated list of <node id 1>,<node id
2>

score

integer between 0 and the original # of nodes

seconds remaining

integer between 0 and 120

nanomunchers left count:

integer between 0 and max # of nanomunchers

alive nanomunchers:

a comma-separated list of node id's at which the nanomunchers
are located

Example:

PLAY:0,3,7;1,4,7;2,4,8:0,1;1,2:3:114:6:1,3:1:118:7:2

There graph has 3 uneaten nodes: node 0 at (3, 7), node 1 at (4, 7),
and node 2 at (4, 8).
There are two edges between these nodes: between
node 0 and node 1, and between node 1 and node 2.
The
red player's current score is 3.
The red player has 114 seconds left
and 6 more nanomunchers to deploy.
The red player has two alive
nanomunchers on the graph: one at node 1 and another at node
3.
The blue player's current score is 1.
The
blue player has 118 seconds left and 7 more nanomunchers to deploy.
The
blue player has 1 alive nanomuncher on the graph at node 2.

The game server sends a PLAY message to the player before each time step. It
notifies the player about the current state of the game, and requests the player
to deploy any new nanomunchers. The player must respond to the PLAY message with
an ADD message even if the player does not desire to add any new nanomunchers at
this time step.

ADD Message

Source:

Player

Destination:

Game server

Syntax:

ADD:<semicolon-separated list of new nanomunchers to
deploy>
Each nanomuncher is represented by:
<position node
id>,<4-char program>
The program is represented using codes: U
= up, L = left, D = down, R = right. The codes may be repeated in the
program.

Example:

ADD:0,UDRL;2,DDRU
The player requests to add two
nanomunchers: one at node 0 and another at node 2. The nanomuncher at node
0 has a loop sequence of up-down-right-left. The nanomuncher at node 2 has
a loop sequence of down-down-right-up.

The player sends an ADD message to the game server in response to a PLAY
message. The ADD message contains a (possibly empty) list of nanomunchers the
player desires to deploy at this time. Each nanomuncher is represented by an
uneaten node id at which it will be placed and its loop program. If the ADD
request is successful, the game server will immediately respond with an ACK
message.

ACK Message

Source:

Game server

Destination:

Player

Syntax:

ACK:<integer parameter>

Example:

ACK:0
If this was in response to a JOIN request, it
confirms that the player joined as the red player.
If this was in
response to an ADD request, it confirms that no nanomunchers have been
added.

The game server sends ACK messages in response to successful JOIN and ADD
requests. For responses to JOIN, the parameter is the assigned player index
<0|1>; and for responses to ADD, the parameter is the number of
nanomunchers added.

NACK Message

Source:

Game server

Destination:

Player

Syntax:

NACK:<error message>

Example:

NACK:Two players have already joined.

The game server sends NACK messages in response to failed JOIN and invalid
ADD requests.

GAMEOVER Message

Source:

Game server

Destination:

Player

Syntax:

GAMEOVER:<WIN|LOSE|TIE>:<reason text>

Example:

GAMEOVER:WIN:The red player ate 12 nodes, while the blue player ate
8 nodes.

When the game is over, the game server sends a GAMEOVER message, informing
the player of the result of the game.