o1.robots.tribal

Each Frame object represents a data frame within a tribal bot’s call stack. A frame stores data relevant to a single RoboSpeak subprogram call. A stack frame is associated not with the code of a subprogram, but with a subprogram call that happens during a RoboSpeak program run.

Tribal bots’ subprogram calls — unlike methods in Scala — don’t have any parameters or local variables, and very little data needs to be stored in each CallStackFrame. In fact, only a single line number needs to be stored to indicate where the subprogram call was made (in order to determine where execution should resume once the bot returns from the subprogram).

The trait Instruction represents instructions within RoboSpeak programs. The program of each Tribe consists of instruction objects; a TribalBot is able to execute sequences of instructions.

A single Instruction object represents an instruction for a tribal robot to do something. By way of example, here are two RoboSpeak instructions in textual form, each of which can also be represented by an Instruction object:

turn
goto 1

See the documentation of class Tribe for more details and examples of RoboSpeak.

There are various kinds of instruction objects representing the various kinds of instructions that can appear in RoboSpeak programs. However, all instructions share the common interface described by this trait. Through this interface, instructions can be examined and executed. Each instruction object, irrespective of what is does, provides the following:

• Methods for determining basic information about the instruction: Does executing the instruction end a tribal robot’s turn? On which line in a RoboSpeak program does the instruction appear?

• A method for executing the instruction and determining which instruction to execute next.

An instruction object is immutable.

The class TribalBot represents the “brains” of robots that belong to a “robot tribe” and behave according to the rules of that tribe. Tribal robots consider other tribal robots of the same tribe their friends and all other robots their enemies.

A tribal robot is capable of attacking enemies and thereby converting them to their own tribe. As a consequence, tribes can be quite aggressive as they compete for survival in a robot world.

Robot Actions

Each tribal robot is capable of doing one (but only one) of the following things during its turn:

• Moving one square forward into an empty floor space.
• Spinning 90 degrees without moving.
• Spinning 180 degrees without moving.
• Attacking — “hacking” — an enemy robot immediately in front of it. (See below.)

Hacking is automatic whenever a tribal robot sees an enemy, but how a tribal robot moves about and spins depends on its tribe. Each tribe has its own program, written in the RoboSpeak language. All members of the tribe follow this program, which defines the sequences of actions that those robots take. See the documentation of class Tribe for details about RoboSpeak.

Hacking

A tribal robot starts its turn by looking at whether there is an enemy robot in front of it. An enemy robot is any robot that is not a member of the same tribe. If there is an enemy robot in the square right in front of the acting tribal bot, then the tribal bot attacks it by “hacking”. Hacking is a kind of brainwashing: it converts the enemy robot into a member of the acting robot’s tribe. The victim will begin executing its new tribe’s RoboSpeak program from a line determined by the hacking robot.

Memory

Each tribal bot has some limited memory resources available, which it draws on when it executes the tribe’s RoboSpeak program. A tribal bot remembers the following information:

• Where it is: a tribal bot knows which robot body it is controlling, just like any other RobotBrain does, and can therefore determine its location and facing.

• Where its allegiances lie: a tribal bot knows which tribe it belongs to.

• What it’s supposed to do next: a tribal bot knows which instruction in its tribe’s RoboSpeak program it is supposed to execute next once it gets its next turn. (This allows the tribal bot to save the program position it is at when it ends a turn. It can later resume program execution where it left off the previous turn.)

• Which way it’s turning: A tribal bot remembers if it’s supposed to be turning clockwise or counterclockwise when it next makes a turn.

• Which subprogram calls have been made: A tribal bot has a call stack where it stores frames representing calls to RoboSpeak subprograms. Each such frame is represented by a Frame object. This enables the tribal bot to execute subprograms and return to the correct line in the tribe’s RoboSpeak program whenever the end of a subprogram is reached.

• The contents of four memory slots (or “registers”) called mem, mem2, radar and hackline. The mem and mem2 slots can be used for any purpose. The intended use of radar is to store the readings produced by the robot’s radar. The hackline slot is meant for configuring hacked robots. See the text below and class Tribe for more details.

Sensors

A tribal bot is (only) capable of seeing the single square directly in front of it. It can determine what there is in that square, but no further.

A tribal bot also has a radar that it can use either short-range to determine how many enemies or friends are located within exactly two steps of the acting robot, or long-range to count the memberships of entire tribes in the robot world. Again, more details can be found in the documentation for class Tribe.

Initial state

When a tribal bot is created, it starts executing its tribal program from the beginning (unless otherwise specified by a hacking robot). Its call stack is initially empty, its memory slots all contain the value 1, and it is considered to be turning clockwise.

As a new tribal bot brain “plugs into” a robot body, it changes the robot’s name. Each new member of a tribe receives a new, rather impersonal name of the form "Tribe#number", e.g., "Tiger#123". The ID number that comes after the hash (#) is unique for every member of a tribe.

A “tribe” of robots is essentially a program which makes any robots who follow that program to behave in a certain way. Those robots are the “members” of the tribe.

NOTE TO STUDENTS: You are not required to understand this class’s implementation. However, you should read the text below so you know how to program in RoboSpeak.

RoboSpeak

As a Plan A, tribal robots spend their turn attacking nearby enemies (see class TribalBot). However, when there is no enemy directly in front, the tribal bot will instead follow its tribe’s program to maneuver itself.

Tribal programs are written in a programming language called RoboSpeak. You can think of RoboSpeak as “machine code for tribal robots”. It features a smallish number of simple instructions (commands) which can be combined to build programs that direct tribal robots' actions.

A description of RoboSpeak appears below.

Action Instructions

There are four “action instructions” that cause a tribal bot to spend its turn on something concrete:

• move: Attempt to move forward one step into an empty square.

• spin: Spin 90 degrees. Unless otherwise specified (see below), the robot spins clockwise.

• uturn: Spin 180 degrees.

• wait: Stand still. Don’t move, don’t spin.

Even if a robot fails to execute an action instruction (this happens if there is something blocking movement), the attempt ends the robot’s turn.

An Introductory Example

By themselves, action instructions are not enough to write interesting RoboSpeak programs. To control the use of action instructions, RoboSpeak provides a variety of “logic instructions” which allow a tribal bot to reason about its state and surroundings.

Here is a simple RoboSpeak program. It causes the members of a tribe to move forward as long as they can, turning clockwise whenever they run into a wall.

ifwall 4
move
goto 1
spin
goto 1

This program can be paraphrased as follows: "If you see a wall in front of you, go to line 4 (where you spin clockwise before returning to line 1). Otherwise, move one step forward and return to line 1." Either moving or spinning ends the robot’s turn. Next turn, it resumes where it left off. In this example, it so happens that the robot will always start its turns by returning to line 1 (because both the move and spin commands are followed by goto 1).

Only the action instructions listed above end a tribal bot’s turn: a robot can execute any number of non-action instructions during a turn.

Basic Logic

Some basic logic instructions are:

• goto N: Continue executing the program from line N.

• switch: Change the direction in which the robot spins when the spin instruction is executed. If the robot was previously spinning clockwise, it now spins counterclockwise. If it was spinning counterclockwise, it now spins clockwise. Note that switching only affects future spins; it does not actually spin the robot immediately.

• ifempty N: If there is nothing in the square in front of you, continue executing the program from line N, otherwise resume execution from the next line. The command ifnempty N does exactly the opposite, and jumps to line N if and only if the square is not empty.

• iffriend N: If there is a friend (a robot of the same tribe) in the square in front of you, resume executing the program from line N, otherwise continue execution from the next line. The command ifnfriend N does exactly the opposite, and jumps to line N if and only if there is no friend present.

• ifwall N: If there is a wall in the square in front of you, continue executing the program from line N, otherwise resume execution from the next line. The command ifnwall N does exactly the opposite, and jumps to line N if and only if there is no wall present.

• ifrandom N: “Flip a coin”: 50% chance of continuing from line N; 50% chance of continuing from the next line.

Labels

Since using line number literals is highly inconvenient when editing any program longer than a dozen lines or so, RoboSpeak allows the programmer to define labels. Labels are essentially names for program locations. They can be used instead of line numbers in RoboSpeak instructions.

A label is defined by line that contains a single word (the name of the label) followed by a colon. Here is the previous RoboSpeak program rewritten using labels:

start:
 ifwall wallfound
 move
 goto start
wallfound:
 spin
 goto start

A label definition itself does not instruct a tribal bot to do anything. It is simply a name for a location in code.

Anywhere a line number is required as a parameter to a RoboSpeak instruction, a label name may be used instead.

Comments and Whitespace

In RoboSpeak, the hash character (#) means that the rest of the line is a comment and does not have any effect on robot behavior. Empty lines are similarly ignored.

Using whitespace for indentation is encouraged for readability but has no effect on robot behavior.

Here is a slightly more complex tribe whose code has been explained using comments.

#########################################################
# A member of the Tiger Tribe moves straight forward,   #
# hacking anything it sees in front of it. When its     #
# route is blocked, it turns either left or right at    #
# random.                                               #
#########################################################

start:                        # Main loop: turn or move
  ifnempty turn               # turn if facing an obstacle
  move                        # move otherwise
  goto start                  # repeat the above

turn:                         # Turns left or right at random
  ifrandom noswitch
  switch
noswitch:
  spin
  goto start

Pacifist Tribes

If a RoboSpeak program contains a line that consists of the word pacifist, then members of the tribe will not try to hack anyone at the beginning of their turns (the bunny tribe is an example).

Memory Slots

Each tribal bot has four memory slots called mem, mem2, radar, and hackline. Each can store an integer value. Some commands directly manipulate these slots:

• set S N: Set the value of slot S to N. The parameter S must be a slot name. For instance, set mem 5 stores the value five in mem, replacing any previously stored value.

• add1 S: Increment the value of slot S by exactly one, replacing any previously stored value.

• plus S A B: Compute the sum of A and B, then store the result in slot S.

• minus S A B: Compute A minus B, then store the result in slot S.

You can use a slot name as a parameter. For instance, goto mem causes execution to jump to the line indicated by the current value of mem; set mem radar copies the value of radar into mem; and plus mem2 mem 10 sums the value of mem with the number ten and stores the result in mem2.

In addition to the logic instructions listed above, RoboSpeak features a few commands that compare numerical values or do arithmetic on them. These commands work best in combination with memory slots:

• ifeq A B N: If A equals B then continue executing the program from line N, otherwise continue execution from the next line. For instance, ifeq mem 100 22 jumps to line 22 if the memory slot mem contains the value 100. The command ifneq A B N does exactly the opposite, and jumps to N if and only if A and B are not equal.

• ifgt A B N: If A is greater than B then continue executing the program from line N, otherwise resume execution from the next line.

• iflt A B N: If A is less than B then continue executing the program from line N, otherwise resume execution from the next line.

The slots mem and mem2 may be used for anything. The slots radar and hackline have special purposes — see below.

Radar Commands

The radar memory slot is a special one that is automatically assigned a new value whenever the robot uses any of the available radar commands:

• enemiesnear: Use the radar to find out how many non-pacifist enemy bots are within two steps of the acting robot. (See diagram below.) Store this number in radar.

• friendsnear: Use the radar to find out how many friendly robots are within two steps of the acting robot. (See diagram below.) Store this number in radar. The robot does not count itself as a friend.

• foddernear: Use the radar to find out how many pacifist bots are within two steps of the acting robot. (See diagram below.) Store this number in radar. This count does not include the acting robot, even if it is a pacifist one. Non-tribal bots count as pacifists for this purpose.

• fodderleft: Use the radar to produce a count of how many “fodder bots” (see foddernear above) there still are in the entire robot world. Store this number in radar.

• score: Use the radar to produce a number that indicates who is leading the ongoing tribal fight and by how much. Store this number in radar. A positive number means that the acting robot’s tribe is more populous than any other tribe in the robot world, while a negative number means that another tribe is leading. The magnitude of the lead is also given: for instance, a score of 5 means that the acting robot’s tribe has five more members than the second-placed one, and -10 means that the acting robot’s tribe has ten fewer members than the leading tribe. Pacifist tribes are ignored when determining the score.

A “step” means a non-diagonal move to an adjacent square. For instance, in the diagram below, robots A, B, C, D, and E are within two steps of robot R, but robots F and G aren’t. (# represents a wall, and . represents an empty floor square.)

###########
#..A......#
#.D#RBC...#
#.....G...#
#.F.E.....#
###########

In addition to the radar-based commands listed above, two commands use a directed short-range radar: (see also TribalBot.directedRadar):

• enemiesdir D: Find out how many non-pacifist enemy bots are close by in the direction indicated by the parameter D. Store that number in radar. D must evaluate to a number between 0 and 3 (inclusive): 0 means the direction where the robot is facing; 1 means the direction 90 degrees clockwise from there (to the robot’s right); 2 means behind the robot; 3 means to the robot’s left. An enemy counts as being close if it is within one step of the nearest neighboring square in that direction (that square included). Since there are four possible locations for such enemies, this command puts a number between 0 and 4 (inclusive) in radar.

• friendsdir N: As enemiesdir above but counts friendly robots instead. The robot does not count itself as its own friend, so the result is between 0 and 4 (inclusive).

Hacking and Talking

As noted above, non-pacifist tribal bots always automatically spend their turn hacking a nearby enemy whenever possible. In its future turns, the hacked enemy robot will execute its new tribal program starting at whichever line number is stored in the hacking robot’s hackline memory slot. As the default value of all memory slots is 1, hacked robots start running their programs from the beginning, unless a set command has been used to modify the value of hackline.

Robots can affect how their existing tribemates behave. The instruction talk N transmits a command to a nearby friendly robot. Assuming that there is a friendly robot in front of the acting robot, the friend jumps to line N in its RoboSpeak program. The next time the friend gets a turn, it will resume executing its program from line N onwards. If there is no friendly robot right in front of the acting robot, this instruction achieves nothing. Talking does not end a robot’s turn.

There’s also an instruction for “talking louder”. The instruction shout N works like talk N except that it talks to all friendly robots nearby (where nearness is defined as for friendsnear; see above).

A robot that is hacked or talked to is rebooted. Its state (spinning direction, memory slots, etc.) are reset.

Subprograms

RoboSpeak provides a mechanism for making subprogram calls. Subprogram calls are similar to function calls in Scala in that they cause a specified sequence of instructions to be executed, after which execution resumes at the location where the call was made. However, they are much simpler than function calls in that RoboSpeak subprograms can not receive any parameters, don’t produce return values, and are never invoked on objects. (RoboSpeak is not an object-oriented language.)

Two RoboSpeak instructions are directly related to subprogram calls:

• callsub N: Calls a subprogram that starts at line N, causing program execution to jump to that line. Although this is similar to goto N, there is a crucial difference. Whereas the goto command simply moves program execution from one place to another, callsub causes the robot to remember that it is making a subprogram call. More specifically, the robot will remember that there is a location where the subprogram was called and where program execution is supposed to resume once the end of the subprogram has been reached.

• return: Marks the end of a subprogram’s code. When this instruction is executed the robot returns to where the subprogram was called and resumes program execution at the following RoboSpeak instruction.

Here is an example of a tribe that makes use of subprogram calls. Notice that just like Scala functions can call other functions, subprograms can also call other subprograms.

# A member of the Patrolman Tribe moves clockwise in rectangles,
# hacking every enemy it encounters. When it runs into obstacles,
# it takes a look around counterclockwise before proceeding.

start:
  callsub advance     # repeat three times: try to advance
  callsub advance
  callsub advance
  spin                # turn clockwise
  goto start

advance:              # move unless obstacle in front
  ifnempty cantmove
  move
  return
cantmove:             # spin around counterclockwise
  switch
  spin
  spin
  spin
  switch
  return

This is the companion object of class Tribe. NOTE TO STUDENTS: In this course, you don’t need to understand how this object works or can be used.

This exception type represents situations where a robot tribe file is either unreadable or does not contain a valid RoboSpeak program.