When I was a college freshman, we had to take an introductory course to computer science. The course covered many different topics, such as sorting algorithms, internet of things, and artificial intelligence. For AI, we were given a prebuilt 2D "Mars Rover" simulation to write an AI for. Unfortunately since this was an introductory class, we weren't expected to know how to program with actual programming languages yet - instead we got use Scratch 2 for all of our assignments.

If you don't know already, Scratch is a drag-and-drop programming language, intended to be easy to learn and use. However, due to its idea of "simplicity", it doesn't provide many features that one might expect a modern programming language to have. For example, it doesn't have

• <=, >=, or !=
• multidimensional arrays
• local variables (all variables are global)
• functions that return values (set a global to return a value)
• performance matching a TI-83 Plus
• any kind of debugger (hope you like printf say)
• a way to actually write code instead of using an extremely clunky interface

Using Scratch to write complex, branching logic (because let's face it, most AI is a bunch of if statements) with deeply nested conditionals quickly turns into a pile of blocky, orange spaghetti code. Moreover, if I wanted to write a strong AI, I needed a way to iterate quickly and measure the effect of my changes. With that in mind, I decided the best course of action was to rewrite the entire simulation in C#.

Specifications

I first needed to specify the exact parameters of the simulation. While I don't have the original Scratch project anymore, I do have a copy with very broken AI.

Terrain

The surface of mars is represented by a 32x23 tile grid with 5 different terrain types:

• Impassable - the rover cannot move onto this tile.
• Smooth - easy to move on, and can be sampled
• Rough - difficult to move on, and can be sampled
• Smooth Sampled - easy to move on, but cannot be sampled.
• Rough Sampled - easy to move on, but cannot be sampled. (Functionally identical to Smooth Sampled)

The terrain is generated randomly. A border of impassible tiles is created first. Each inner tile has a 10% chance of being impassable, a 30% chance of being rough, and a 60% chance of being smooth. The center tile where the rover starts is always smooth.

Rover

The rover starts off with 500 power and 1000 moves. It can perform several different actions:

NoBacktrack counts the number of consecutive moves onto smooth terrain. This is reset whenever the rover collects light or moves onto a tile that is not smooth terrain. This number is cubed to determine the amount of power to add to the rover.

Miscellaneous

• Attempting to move the rover into an impassable tile has no effect and consumes no power and moves.
• The rover's hopper can only hold 10 samples at a time, after which they must be processed.
• Failing to collect a sample does consume power and moves.

AI

An AI is allowed to use any of the actions to control the rover, but nothing else (no cheating). The goal is to transmit the most amount of processed samples before the rover runs out of power or moves. I think getting an 'A' required transmitting at least 150 samples (or maybe it was 200).

A rover needs about 2.1 moves for each sample including processing every 3 samples (1 sample + 1 move + 1/3 process). A rover will need to collect power at least once and transmitt once, so that leaves 998 moves left. Therefore, in the perfect simulation, the rover will transmit 427 samples. Since on average there will be (32 - 2) / (23 - 2) * .9 = 567 tiles that can be sampled on each map, it's impossible for a rover to collect samples from every tile on the map.

Application

Using Windows Forms for the GUI and OpenTK for rendering the simulation, I created an clone of the original project, which I called RoverSim. It's capable of queuing several thousand simulations and running them in parallel to make sure that changes to the AI are statistically significant. Since in the end I had to turn something written in Scratch, I wanted any AI I wrote to be easily translatable from C# to Scratch. That meant that while most of the project is idiomatic C#, the AI are written in Scratch style - procedural style, global variables, no returns, etc.

While I tried to make it functionally identical to the original in most respects, I found I needed to modify the terrain generation slightly. Specifically, when simulating thousands of different rovers, the rover sometimes ends up completely surrounded by impassable tiles. This makes sense when you think about it - each tile has a 1/10 chance of being impassable, so since there's 4 directions a rover can move, on average one out of every 1/(10⁴) or 1/10000 simulations will trap the rover immediately. Therefore, I instead check the 4 tiles adjacent to the starting position. If each one is impassable, the terrain is regenerated. This means that to trap the rover (now within two tiles instead of one), 7 specific tiles must be impassable, lowering the odds to 1/10000000.

Since first writing RoverSim, I've cleaned the code up significantly. You can look at the source code on GitHub, as well as a build of version 0.1.0. I'm in the process of refactoring to isolate the Scratch AI compatibility and redo how the renderer gets updates from the rover. I've also started to build a new cross-platform GUI on Avalonia. Might even try a Blazor port as well. Once that's done, I plan on trying to improve the AI even more, without the burden of Scratch. This has come a long way for a simple homework assignment.

In total I wrote 3 different AI, plus the original demo AI. Even the simplest one easily beats the target of 150 samples, and the Mark II with pathfinding almost reaches 400 at times. I describe each of them in detail here, with animation.

Update 2019-04-25

I mistakenly thought that the rover could process 10 samples at a time. This is incorrect - the rover can hold 10 unprocessed samples, but it can actually only process up to 3 at a time. The specifications have been updated to reflect that as well as the optimal rover calculations.