1221620 AI RoboCom
Mick G.D. Remmerswaal
March 18, 2020
1 Introduction
The concept of environment is key to a living being. It tries to overcome hardship and adapt to
its environment to survive as long as possible. Analyzing the environment through eyes, ears, and
nose and acting on the environment through moving is how human beings grasp the concept of
environment. Translating this to computers is quite a task. One way is through the use of intelligent
agents, who try to grasp the concept of environments through the use of sensors and actuators.
For example, a robotic agent might use cameras and range finders to sense its environment while
using robotic arms and hands to act on it. A software agent might receive keystrokes and network
packets as sensory inputs and acts on the environment by displaying it on the screen.
This report is about analyzing the environment of RoboCom, a programming game, and to develop
a piece of software that acts according to basic concepts of the environment such as how observable
it is and how it changes over time.
2 RoboCom
RoboCom is a programming game created by Dennis C. Bemmann, it is inspired by the game Core
War [10]. The game is played on a field containing a 20 by 20 grid. The grid, however, is infinite as
the edges are connected, the top edge connects to the bottom one and vice versa, the same holds
for the left and right edge.
Figure 1: Field of a RoboCom simulation.
1
The idea of RoboCom is to write a program in an assembly type language, these programs are
represented as robots on the field [11].
Figure 2: A robot inside the field.
The robots are limited in their perception of the environment, this is due to the robots only being
able to observe the square which is located in front of them, called the reference field. Every
command not related to the robot is related to this reference field.
Commands are written in so called banks, all robots start in the first bank. When a bank has no
more commands in it, the robot goes back to the first bank. Every robot is limited to the amount
of variables it can use, there are only 20 variables, #1, #2, #3 ... #20. These variables can not be
renamed and can only hold integer values.
Every robots has a predefined instruction set, 0, 1 or 2. These instruction sets determine what
instructions a robot may use, with 0 being the most restricting and 2 with all of the commands
available.
The assembly type language consists of several commands for example:
Command Function
Move The robot moves to the field in front it,
provided that it is empty.
Turn The robot turns 90 degrees left or right.
Die The robot self-destructs.
Table 1: Three examples of instructions in the RoboCom language.
Every action done by a robot costs a certain time, called clock cycles. In general, a game of
RoboCom has a time limit of 80.000 clock cycles.
3 Assignment
The assignment, see [9], is to program a cooperative robot which, when put in the field with another
of the same kind, constructs a line of length 4 + 4 = 8 robots long. This line is build of four children
of one robot and four children of the other robots as seen in the figure below.
Figure 3: The line that has to be made, where X and Y represent different robots
This line can be constructed in multiple ways and is not bound to a horizontal orientation. The
programming language of RoboCom contains many commands, as seen in [7]. However, this
assignment has put a limit on the usable commands, the following table displays the commands
which may be used.
2
Command Clock Cycles Function
ADD #a, b 6 Adds b to #a.
BJUMP a, b 5 Causes program execution to con-
tinue in program bank a at the
bth instruction.
COMP a, b 4 Compares a to b. If a ¡¿ b, execu-
tion continues with the next in-
struction; otherwise, the next in-
struction is skipped. This arrange-
ment makes conditional branches
unnecessary.
CREATE a, 50 in each case + 20 per Causes the robot to built another
b, c bank * 2 if mobile + 40 for one on the reference field (if it is
instruction set 1 + 80 for free). The new robot has instruc-
instruction set 2 tion set a and b empty memory
banks. c indicates whether the
new robot is mobile (0 or 1). The
new robot is initially inactive.
DIE 1 Causes the robot to self-destruct
and disappear from the board at
the next clock cycle.
JUMP a 2 Performs an unconditional rela-
tive jump.
MOVE 18 Causes the robot to move to the
field before it (if it is free). The
robot must be mobile.
SCAN #a 6 Scans the reference field and re-
turn the result of the scan in #a.
#a = 0 if the field is empty. #a =
1 if an opponent’s robot is there.
#a = 2 if a friendly robot is there.
SET #a, b 5 Sets #a to b.
SUB #a, b 5 Subtracts b from #a.
TRANS a, b 5 + 3 per instruction in The robot transfers its a-th mem-
bank ory bank to the b-th memory
bank of the robot on the refer-
ence field.
TURN a 5 The robot turns 90 degrees left,
a = 0, or right, a 6= 0.
Table 2: Limited instruction set of the RoboCom language, found at [2].
4 Relevant work
RoboCom itself has not been thoroughly researched as its counterpart Core War. Due to similarities
in both language and approach of creating robots, solutions for Core War may also be solutions for
RoboCom. It seems that evolutionary programming yields very promising results when used to create
robots, as seen in [6], [5] and [3]. Evolutionary Programming is a Global Optimization algorithm
and is an instance of an Evolutionary Algorithm from the field of Evolutionary Computation [4].
Evaluating these robots can be done via data mining principles, as seen in [12].
3
5 Approach
In this chapter the approach to creating the robots is given. First, a PEAS analysis is given to
better understand the task environment in which the robots will operate. After this, a thorough
analysis of the properties of the task environment is created to give more clarification about the
approach to the problem [14] Chapter 2.
5.1 PEAS analysis
As mentioned before a PEAS analysis is done to better understand the task environment of the, to
be created, agent. A PEAS analysis is done with four specifications, the Performance Measure, the
Environment, Sensors and Actuators. The Performance Measure is what the agent must accomplish
to succeed in its task. The Environment is the scope in which the agent is acting. Sensors depict
with what the agent will perceive its environment and with the Actuators how it acts on this
environment.
• Performance Measure
- Create a line
- Perform line creation within the given time restrictions
• Environment
- RoboCom simulation
- A 20 by 20 playing field
• Actuators
- RoboCom Robots
- Certain commands such as ‘Move’ and ‘Create’
• Sensors
- The reference field of the robots
- Certain commands, such as ‘Scan’ and ‘Comp’
5.2 Properties of the environment
In this section, the properties of the environment are better analyzed. The environment will be
analyzed along six different axes. This is done to ensure a good understanding of the environment
and a good approach to designing an intelligent agent.
5.2.1 First Axis
The first axis is observability, this can be differentiated between fully or partially observable. Fully
observable means that the complete state of the environment is accessible by the sensors of the
agent. Anything otherwise is considered partially observable.
Robots in RoboCom are limited in there observations of the environment. The only way a robot
can perceive its environment is the reference field in front of the robots. Therefore RoboCom is
considered partiality observable.
5.2.2 Second Axis
The second axis represents the multiplicity of agents, there are two options regarding agent
multiplicity; single agent or multi agent. A single agent environment consist of a single agent acting
and perceiving in the task environment. Multi agent task environments host a multiple of the same
or different agents within.
Since this assignment calls for two robots cooperating in the same environment, the task environment
in this instance is considered multi agent.
4
5.2.3 Third Axis
The third axis is about uncertainty and probabilities, the options here consists of deterministic or
stochastic. In a deterministic task environment every next state of the environment is determined
by the current state of the environment and the action executed by the agent. If this is not the
case, such a task environment is stochastic.
Although the environment is not fully observable, it still is deterministic. This is because every
next state of the environment is determined by how a robot is in the current state and what action
it is going to take next.
5.2.4 Fourth Axis
The fourth axis explains how actions are taken, episodic or sequential. In episodic environments
next episodes do not rely on previous taken actions, if this is the case such an environment is called
sequential.
In this instance, there are some actions that depend on the current state of the environment and
that state of the environment depends on previous actions taken by the agent. Therefore this
assignment is considered sequential.
5.2.5 Fifth Axis
The fifth axis relates to change in the environment, whether it is static or dynamic. When an
environment is static it does not change at all, if it does, it becomes dynamic.
In this instance robots are able to move around the field, this alone makes the entirety of RoboCom
dynamic.
5.2.6 Sixth Axis
The sixth and last axis is about how the environment handles time in relation to the agent, discrete
or continuous. In a discrete environment a finite number of distinct states exist, when an infinite
amount of states exist such an environment is called continuous.
If the time limit of 80.000 clock cycles is removed the instance is discrete. This is because there
are limited amount of states a game of RoboCom can exist in. Although there are many, it is not
infinite.
6 Implementation
In this section, the implementation of the RoboCom program is discussed. First, the programming
language is discussed. Next, the search algorithm is touched upon. Lastly, the end state of the
robots and the creation of the line are discussed.
6.1 Programming language
For the implementation of the software, the editor of RoboCom itself is used. As mentioned
previously, RoboCom has its own distinct programming language. The language and commands
were provided by RoboCom and the assignment.
5
6.2 Search algorithm
This assignment called for two cooperating robots. Because these robots do not spawn at set
locations, they need a way to find each other. The solution was a simple search algorithm that has
the most resemblance with Depth First Search (DFS) [8].
Figure 4: An example how Depth First Search searches through a graph [13].
It resembles DFS in the way it searches exhaustively deep until it encounters a friendly robot, that
robot then turns and continues to exhaustively search deep again until it reaches an opponent.
Because another robot of its kind is its opponent and does the same thing, they are bound to find
each other.
6.3 End state
The end state is defined as the last state of the robots before line creation. This state is initialized
when one of the robots finds an opponent. Every other robot in the field is then commanded to
self destruct. The two remaining robots turn each other’s backs and the line creation state can
commence.
6.4 Line creation
After the end state, the line creation will begin. This is done via each robot creating three robots.
Each of these robots takes the appropriate amount of steps until the needed 4 + 4 = 8 long line is
created and displayed on the screen.
7 Experiments
This section contains the results of two experiments and some explanation about these results. Both
experiments contain 50 runs of the same program. The first is done with two robots, the second is
done with three robots.
The first 50 runs with two robots gave the results as seen in the table below.
Completed lines Amount of runs
0 3
1 39
2 8
Table 3: Number of completed lines, two robots.
6
As seen in Table 3, 8 out of 50 times two lines appear instead of one. This happens only when the
robots face an orientation opposite of each other. This results in a search line where four robots
meet each other at the same time. because of limited observability the robots do not know this
happens and simply go on with the creation of the line. The results are shown in Figure 5.
(a) Start situation, robots facing opposite directions. (b) Two lines created at the end.
Figure 5: Result of starting in opposite directions of each other.
7
The second 50 runs with three robots gave the following results:
Completed line segments Amount of runs
0 2
1 4
2 16
3 19
4 7
5 2
Table 4: Number of completed line segments, three robots
Instead of completed lines of length eight, line segments of length four were counted. This was done
because there were next to no completed lines of eight robots long in the first few runs. Also, most
of the runs with two line segments were due to one of the robots not reaching the others within the
time limit of 80.000 clock cycles. Would there be no time limit, most of these would score three line
segments instead of two.
Figure 6: The third robot does not have enough time to encounter the other two and is stuck in a
loop.
8 Conclusion and further work
The objective was to program a cooperative robot in the RoboCom programming game environment.
This robot, when put into the field with one of its kind as an opponent, must create a line consisting
of four of its own children and four of the opponents children such that an eight robot long line is
created.
After a thorough analysis of the RoboCom environment and a deeper look in the properties
of this environment a robot was implemented. This implementation was done in the RoboCom
programming language with a search algorithm that vaguely resembles Depth First Search.
This robot completes a line 39 out of the 50 times it was run, a 78% success rate, seen in Table 3.
Moreover it seems that adding more robots to the field does not increase the amount of correct
lines the robots are able to make, seen in Table 4.
To further improve this solution the robots could use a better search algorithm using heuristics, for
example A*. The squares of a field of RoboCom could be used to compute the heuristic. This can
be done via Manhattan Distance or Taxicab Geometry [1].The problem of two lines, as explained
in Section 7, could be removed with this improvement to the search algorithm.
8
References
[1] Rachit Belwariar. A* Search Algorithm - GeeksforGeeks. url: [Link]
org/a-search-algorithm/. (Last accessed: 18.03.2020).
[2] Dennis C. Bemmann. RoboCom summarized Documentation. url: [Link]
nl/~kosterswa/AI/[Link]. (Last accessed: 12.03.2020).
[3] Brian Blaha and Don Wunsch. “Evolutionary programming to optimize an assembly program”.
In: Proceedings of the 2002 Congress on Evolutionary Computation. CEC’02 (Cat. No.
02TH8600). Vol. 2. IEEE. 2002.
[4] Jason Brownlee. Evolutionary Programming – Clever Algorithms: Nature-Inspired Program-
ming Recipes. url: [Link] inspired/evolution/
evolutionary_programming.html. (Last accessed: 16.03.2020).
[5] F Corno, E Sanchez, and G Squillero. “Exploiting co-evolution and a modified island model to
climb the core war hill”. In: The 2003 Congress on Evolutionary Computation, 2003. CEC’03.
Vol. 3. IEEE. 2003.
[6] Fulvio Corno, Ernesto Sanchez, and Giovanni Squillero. “On the evolution of corewar warriors”.
In: Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No. 04TH8753).
Vol. 1. IEEE. 2004.
[7] Florian Fischer. RoboCom - The Programming Guide - R-files. url: [Link]
nl/robocom/[Link]. (last accessed: 16.03.2020).
[8] HackerEarth. Depth First Search Tutorial and Notes. url: https : / / www . hackerearth .
com / practice / algorithms / graphs / depth - first - search / tutorial/. (Last accessed:
18.03.2020).
[9] Walter Kosters. Kunstmatige intelligentie Programmeeropgave 2 van 2020 - Agenten &
Robotica. url: [Link] ~kosterswa/AI/[Link]. (Last
accessed: 12.03.2020).
[10] John Metcalf. Core War - The Ultimate Programming Game. url: [Link]
uk/[Link]. (Last accessed: 16.03.2020).
[11] Oracle. X86 Assembly Language Reference Manual. url: [Link]
E19253-01/817-5477/[Link]. (Last accessed: 12.03.2020).
[12] Doni Pracner et al. “Categorizing evolved CoreWar warriors using EM and attribute eval-
uation”. In: International Workshop on Machine Learning and Data Mining in Pattern
Recognition. Springer. 2007.
[13] ProgrammerInterview. DFS vs. BFS - Programmer and Software Interview Questions and
... url: [Link] (Last
accessed:18.03.2020).
[14] Stuart J Russell and Peter Norvig. Artificial intelligence: a modern approach. Pearson
Education Limited, 2016.
Appendix: Code
; RoboCom program
Published Name SnatsertjeV1.0 ; Name of this program
Published Author M.G.D. Remmerswaal ; Name of author
Bank 1_Scan_Create
@Start
Scan #1 ; Check next square
Comp #1, 0 ; Is it Empty?
Jump @Not_Empty
Jump @Empty_Square
@Not_Empty
Comp #1, 1 ; Is it a Foe?
9
Jump @Found_Friend ; No
Jump @Found_Foe ; Yes
@Empty_Square
Create 2,6,0 ; Empty, Create friend
Trans 1,1
Trans 2,2
Trans 3,3
Trans 4,4
Trans 5,5
Trans 6,6
Set %Active, 1
@IdleLoop ;Idleing
Set #3,0
Jump @IdleLoop
@Found_Friend
Turn 1
Jump @Start
@Found_Foe
Set %Active, 0
Trans 3,1
Set %Active, 1
Bjump 4,1
Bank 2_Turn_Die
Set #5, 0
@TransLoop
Turn 0
Set %Active, 0
Trans 2, 1
Set %Active, 1
Add #5, 1
Comp #5,4
Jump @TransLoop
Die
Bank 3_Jump_to_MeetingPoint
Bjump 4,1
Bank 4_MeetingPoint
@TransLoop2
Turn 0
Set %Active, 0
Trans 2, 1
Set %Active, 1
Add #5, 1
Comp #5,4
Jump @TransLoop2
@TurnLoop
Scan #1
Comp #1, 1
Turn 0 ;Turn until they face each other
Comp #1, 1
Jump @TurnLoop
10
Turn 0
Turn 0 ;Face Away from eachother
Set #11, 3 ;Total Robots
Set #12, 500
@CreateWaitLoop ;Wait for the field to clear
Sub #12 , 1
Comp #12, 0
Jump @CreateWaitLoop
@CreateLoop
Create 0,2,1
Trans 6,1
Trans 5,2
Set %Active, #11 ;Give the Robot a decreasing number,
Sub #11,1 ;This represents the amount of steps the bot needs to take
Comp #11,0
Jump @CreateLoop
@IdleLoop2
Set #3, 0
Jump @IdleLoop2
Bank 5_Move_Bot
Set #7, #Active
Set #8, #7 ;Waiting index needed else Bots move to quick
@WaitLoop ;and get caught in dying sequence of their elders
Comp #8, -25 ;Increase Waiting Index by 25 to make sure
Jump 2 ;The board is empty before starting to move
Jump @MoveLoop
Sub #8, 1
Jump @WaitLoop
@MoveLoop
Add #8, 10
Sub #7, 1
Comp #7, 0
Jump @MoveJump
Jump @IdleLoop3
@MoveJump
Move
Jump @MoveLoop
@IdleLoop3
Set #3, 0
Jump @IdleLoop3
Bank 6_Jump_To_Move_Bank
Bjump 2, 1
11