A9: Lambda Code Runner

Changelog

• 5/3/19: initial release!
• 5/4/19: removed reference to Wall tile in description of look

Overview

In this assignment, you will use the RML language you implemented in A8 to create artificial intelligence for a simple treasure finding game called Lambda Code Runner.

Because we are at the end of the semester, this assignment is much simpler than previous assignments. After reading this document and understanding the starter code, it should be possible to complete good or satisfactory scope in just a few hours, and excellent scope with just a bit more work. It is designed to be a lightweight and fun assignment, and we think you might have fun if you pair program your solution with your teammate(s). Having said that, if you are enjoying the game and want a challenge, there are numerous possibilities for exploring more sophisticated solutions.

In addition, we are providing you with reference solutions for A8, in the form of binaries for OS X and Linux (if you are on windows, we suggest using the CS 3110 VM.)

Table of Contents

• Step 1: Team Maintenance
• Step 2: Explore the Starter Code
• Step 3: Program Your Robot!
• Step 4: Test Your Robot
• Scope
• Submission

Step 1: Team Maintenance

Your A9 team will be the same as your A8 team. Briefly check in with your teammate(s) to see how things are going, and make a plan for how you will complete this assignment, and for how you will celebrate finishing the course on Slope Day.

Step 2: Explore the Starter Code

The starter code includes:

• Shell scripts for playing game, either using the staff-provided reference interpreters (run_staff.sh) or your own interpreter (run_student.sh). If you want to run your own A8 interpreter, you’ll copy the eval.ml file ino the top-level directory.

• Several RML libraries that contain helpful functions for lists (rml/list.rmx), maps (rml/map.rmx), and navigating (rml/navigate.rmx) on the game board.

• A template for writing robots rml/gold_digger.rml and an example of a trivial robot using this template that does absolutely nothing rml/trivial_gold_digger.rml.

• Some example game boards (maps/).

The template contains detailed comments to explain what each line does, but at a high level, it spawns all of your team’s robots and sets up handles for pair-wise communication between them, initializes global variables that contain details about the game board (width, height, vision_rad, etc.), and provides event handlers for processing messages from the server (listen_server) and other robots (listen_bot). You are free to change any of this code, but in principle you should only have to fill in the bodies of the event handlers.

Step 3: Program Your Robot!

The Game

In Lambda Code Runner (inspired by the classic Brøderbund game), two teams of robots compete to see who can collect the most gold on a rectangular grid. Robots can implement arbitrary RML computations includinng communicating with each other using the send and recv primitives. Theyq manipulate the game state (moving around, picking up gold, sensing, etc.) through the server, which processes actions as described below. The objective of the game is to collect and return as much gold as possible to the base. The game runs for a pre-determined number of steps—after the time limit has been reached, the game ends and the robot team that has returned the most gold to its base wins.

Here is how the game works in more detail.

Grid

The grid has width by height square tiles. Each tile is one of the following elements:

• Path: a regular tile that does not contain a base or any gold. A robot may move onto a path tile at any time, whether or not it is already occupied by another robot.

• Gold(n): a tile containing n units of gold. A robot may not move onto a gold tile, but it may take from it (see below) which decreases the amount of gold on the tile and increases the amount of gold the robot is carrying. When the value of a gold tile reaches zero, it reverts to a path tile.

• Base(n): the tile containing the base for team n. The player (i.e., you) is team 1 and the opponent is team 0. Each team has a single base tile. At the start of the game, all robots for a given team are spawned onto their base tile. When a robot moves onto the base tile for team n, any gold it is holding is immediately deposited on the base and added to the score for n. Note that a robot can transfer its gold to the opposing team!

Actions

Robots can perform one of several actions by sending one of the following message to the server.

• ("move", d): attempt to take a step in direction d, where a direction is either "N", "S", "E", "W", "NE", "NW", "SW", or "SE". If the tile located in that direction is of type Path or Base(n), the robot steps onto the tile. However, if the tile is of type Gold(n), the action has no effect and the robot remains in its current location.

• ("take", d): attempt to take gold off the tile in direction d. If successful, the robot takes m pieces of gold off the pile and adds it to the gold it is carrying. The number m is the maximum amount of gold the robot can carry up to the amount left on the gold tile. If the tile does not contain gold, the action has no effect.

• ("look", ()): look around at the surrounding tiles, up to some radius, obtaining an association list mapping positions to tiles. For example, if the robot was located at position (1,1) and the radius was 1, the list might be:

[((1,1), ("Path", [])),
 ((0,0), ("Gold", [2])),
 ((1,0), ("Path", [])),
 ((2,0), ("Path", [])),
 ((0,1), ("Base", [1])),
 ((0,2), ("Path", [])),
 ((1,2), ("Path", [])),
 ((2,1), ("Path", [])),
 ((2,2), ("Gold", [4]))]

Note that the first element of this list is always the current position, but the other elements may appear in any order.

• ("info", ()) request information about the game from the server, returning a tuple of the form: ((width,height), vision_rad, robot_cap, max_bots), where width and height are the dimensions of the grid, vision_rad is the vision radius, robot_cap is the capacity each robot has for carrying gold, and max_bots is the maximum number of bots allowed per team.

• ("inv", ()) request information about the robot’s inventory, or how much gold it is carrying.

To perform one of these actions, you will need to send a request to the server using a send expression. The syntax for doing so is as follows:

• send ("move", d) to SERVER to move in direction d, where d is one of “N”, “S”, “E”, “W”, “NW”, “NE, “SW, “SE”.

• send ("take", d) to SERVER to take gold in direction d.

• send ("info", ()) to SERVER to get the tuple of information about the grid.

• send ("look", ()) to SERVER to get the list of tiles within the vision radius.

• send ("inv", ()) to SERVER to get the robot’s innventory.

The server will wait for a small delay before processing to move and take commands, but it responds immediately to look, info, and inv commands.

Your task is to write a function that utilizes all of these actions and possibly other asynchronous expressions to gather and return to base as much gold as possible before the game ends.

Hints

Because your robots will be implemented as event handlers, when building more complicated robots, you you may find it helpful to think in terms of simple state machines. For example, your robot might start out in “Explore” state until it finds gold and then transition to the “Return” state. You might represent the state as strings stored in a global reference, and pattern match on the state at the start of the listen_server function to determine which code to execute. Then, to transition to a new state, you could simply assign a new string to the state reference.

Here are some common bugs in RML to watch out for:

• It is not possible to send promises or references (i.e., location values) between robots.

• RML does not support n-ary tuples. However, you should be able to encode them using nested pairs.

• If your RML code includes an infinite loop whose body is trivial, you may get a StackOverflow exception.

• RML’s match statements require the end keyword after the last case. Don’t forget it!

• Make sure that your .rmx files end with the in keyword.

• While OCaml match statements allow you to omit the | in the first case, RML does not support this syntax.

• In OCaml, if you put an expression before a sequencing command ; that does not evaluate to (), you get a warning. In RML, doing this will raise an error. You should use the built-in ignore function to discard the value.

• For await p = e1 in e2, remember that e2 must be a promise.

• Make sure to put semi-colons after your print statements.

• As in OCaml, your program cannot end with a semi-colon.

Step 4: Test Your Robots!

We have provided several sample maps (see maps/), as well as a GUI for visualizing and replaying matches between teams of robots. You should use these during development to make sure your robots are behaving as expected.

To run your robots, use the following commands:

• ./run-staff.sh <MAP> <BOT1> <BOT2> : Play a game between BOT1 and BOT2 on MAP using the staff-supplied interpreter.

• ./run-student.sh <MAP> <BOT1> <BOT2>: Build the .ml files (including your eval.ml) and play a game between BOT1 and BOT2 on MAP using your interpreter.

• make clean: clean all build files.

To visualize a game using the GUI, point your browser at https://bluefire2.github.io/lambda-code-runner/ and add the replay.json file that is generated when you play a game on the command line.

Scope

This assignment is designed to be fun. So our expectations for scope are fairly conservative. You should be able to complete a basic working solution that gets a good grade in just a few hours.

• Satisfactory: playing against a trivial adversary, your robot should be able to find all gold on the board and bring it back to the base (given a game the runs for sufficiently many steps). Note that you can achieve this by only writing code in the listen_server event handler, and without using any of the sensing functions, additional state, or communication between robots. For example, you could simply take a random walk around the board (see the helper function in navigate.rmx), and either perform a move or a take action at each step.

• Good: your robots should use the sensing primitives (e.g., look) to be more intelligent about which actions it performs. However, you do not need to use graph algorithms to nagivate the board, or communicate between robots.

• Excellent: your robots should implement some kind of non-trivial strategy to gather the gold on the board. This could include walking the board until the robot’s capacity is reached before returning to the base, building up a global view of the grid and using graph algorithms to navigate, or, most advanced, using RML’s communication primitives to coordinate behavior among multiple robots.

In order to develop these features incrementally, we recommend that you make a working satisfactory version first, then refine the searching methods of single robots working as individuals, and finally make the robots able to communicate with one another and share their respective knowledge about the grid with each other.

In addition, because it is the end of the semester, the time for this assignment is short, and the final exam is coming up quickly, we recommend stopping at “Satisfactory” or “Good” scope if you are feeling pressed for time. Nobody should have to miss out on Slope Day or compromise their plans for studying for finals because they were hacking on robots. We will take the short duration of this assignment into consideration when weighting assignments in the final grade calculation.

Submission

Name your file robot.rml and construct a ZIP file containing this file and any other .rmx files (including the staff-provided libraries) you are using. Note that the robot.rml file should be at the top-level directory of the ZIP file. Any ill-formed ZIP files will receive a penalty of 20 points. The size of the files is limited in CMS to 1 MB. Please stay within the size allotted, and make sure that any dependencies between RML files are included in the ZIP file (i.e., if you include any RML files in your submission code, they should also be in your ZIP file). If these dependencies are not closed under the ZIP file, we will not be able to run your submission.