Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

Exploring Botworld

20 Post author: So8res 30 April 2014 10:29PM

Many people have been asking me this question:

But what am I supposed to do with Botworld?

This indicates a failure of communication on my part. In this post, I'll try to resolve that question. As part of this attempt, I've made some updates to the Botworld code (which is now v1.1) which make Botworld a bit more approachable. A changelog and some documentation are included below.

Playing with Botworld

To clarify, Botworld was devised as a tool for reasoning about different AI formalisms. We're not trying to build a hotbed for programming competitions or anything of the sort. Rather, we need a concrete system with concrete games where we can study how a given agent deals with a given situation. As such, most of our work which references Botworld will describe complex agents playing simple games. A few such posts are in the pipeline.

Benja and I designed Botworld as a universe where we can distill many 'edge case' scenarios that an AI may face, such as having it's source code read or distributing itself across multiple machines. Such scenarios are often handled clumsily by existing AI formalisms, and it is quite useful to have simple, concrete scenarios where we can envision such events.

That's how we use Botworld: we throw different formalisms at different edge cases, figure out where their problems might lie, and visualize solutions. If we encounter problems, we use Botworld as a way to find a minimal example. You'll see one such example in an upcoming post.

So how are you supposed to use Botworld? Well, if you're studying AI formalisms, then you're encouraged to use Botworld to visualize and distill weird scenarios where different agents may run into trouble. Otherwise, we don't really expect you to get direct use out of it.

Don't get me wrong, you're more than welcome to play around, write amusing games, and design programs that do neat things. It's a flexible and fun little system. If you are just looking to entertain yourself, you're invited to:

  • Write some simple robots that cooperate in a Stag Hunt (now included in the games/ directory)
  • Design your own game
  • Write a program that wins in the Precommitment game (spoiler alert: a solution can be found in the Ideal.ct file)
This can definitely help you get a feel for Botworld, and will help you understand the upcoming posts more readily. That said, we don't have plans to make Botworld into more than an explanatory tool.

For anyone following our research, it's sufficient to know only the high-level description Botworld (or even just that it exists) so that you may follow along when we talk about different agents playing different Botworld games in the future.

If you do want to use Botworld, either to understand our games better, or because you're considering writing your own Botworld games for your own purposes, or just out of curiosity, this new code update makes Botworld much more approachable.

Changelog

  • The step function has been split into the Environment phase and the Computation phase. Everything still works in exactly the same way, but this change allows you to pause halfway through a step and see what's happening. The new runEnvironment and runRobots functions allow you to partially step a grid through only one of the phases.
  • An Event datatype has been added, which describes the state of a square between phases. This drastically simplifies the register machine input type from (Int, [Robot], [Action], ([Item], [Item], [([Item], [Item])]), Constree) to (Int, Event, Constree), but does introduce a minor incompatibility in the way that register machine input is encoded. If you have written a Constree program that navigates the input data structure, it will have to be updated accordingly.
  • The display code has been extracted into a library and fleshed out. See the Displaying Botworlds section below.
  • Many tools have been added to make it easier to write Constree programs. See the Writing Constree section below.
  • Four new games have been added. See the New Games section below.

Displaying Botworlds

The display code now lives in the Botworld.Display module. New functionality has been added which allows you to gain much more insight into what happens between steps. The Botworld displays are now much prettier (using ASCII box drawing characters) and much less cluttered.

The new Botworld grid display is quite minimal, displaying only the positions of each robot by color. (Use the displayBotworld function to display a Botworld grid.) Much more data can be had by half-stepping a grid (using the runEnvironment function) and then displaying the resulting EventGrid (see the displayEventGrid function). The Event Grid display works as follows:

Each cell has two rows. The first shows the position of (up to 5) robots in the square by color. The second has information about what is happening in the cell, using the following flags:

  • ↓ at least one item was dropped in this cell
  • ↑ at least one item was lifted in this cell
  • ↕ items were both dropped and lifted in this cell
  • × at least one robot was destroyed in this cell
  • + at least one robot was created in this cell
  • ? at least one robot was inspected in this cell
  • ! at least one robot in this cell executed an invalid action

Robot movement is shown by arrows breaching the borders between cells. (Diagonal movements are somewhat awkward to display. To see which robots moved in/out of a cell's northwest/northeast neighbors, look at the cell's top border. To see which robots moved in/out of a cell's southwest/southeast neigbors, look at the top border of the cell's southwest/southeast neighbor. It's less confusing than it sounds; the arrows make things fairly clear.)

To get additional information about what happened in a single cell, you may use the displayChangesAt function. This prints a full description of a cell's event. This includes a full robot list (color, action, speed, register count, inventory) and a full breakdown of items (untouched, dropped, and fallen, with fallen items separated by robot and by fallen part vs fallen inventory).

 

Writing Constree

A minimal language 'ct' has been added, which makes writing robot programs slightly less painful. The syntax is as follows:

A register is declared by either a name followed by a colon, or a name followed by a number followed by a colon. The number, if given, is the memory limit of the register. If omitted, the register size will be made to fit the register contents precisely (this is useful when a register holds a subroutine.) Examples:

  • REG:
  • REG 1024:

A register definition must be followed by content. Content may be any of:

  • Raw constree, such as "Nil" or "Cons Nil Nil"
  • A command, such as "Inspect 1"
  • An instruction, such as "CopyIfNil 0 0 0"
  • A list or tuple of the above
  • A series of machine instructions

Machine instructions compile directly into the normal Constree instructions (Nilify, Construct, Destruct, or CopyIfNil), but they allow you to specify registers by name instead of by number, and allow some simple shortcuts. Accepted instructions include:

  • NILIFY target
  • CONS left right target
  • DEST target left right
  • COPY source dest
  • CONDCOPY test source target
  • EXEC source
  • CONDEXEC test source
  • PUSH source stack
  • POP stack target
  • WRITE source
  • CONDWRITE test source
NILIFY, CONS, DEST, and CONDCOPY compile to Nilify, Construct, Destruct, and CopyIfNil.

COPY, EXEC, and WRITE may only be used if you have a register named NIL, and they only work if the register NIL actually contains NIL. They are aliases for COND* NIL * *.

PUSH source stack is the same as CONS source stack stack.
POP stack source is the same as DEST stack source stack.
EXEC source is the same as COPY source 0 (0 is the program register).
WRITE source is the same as COPY source 2 (2 is the output register).

For an example, see this file. ct files may be compiled to haskell using the ct2hs binary, which is now bundled with Botworld. This compiler is quite rudimentary, and may get better in the future. For now, it takes two arguments: the name of the ct file (without the .ct extension) and the name of the Haskell module to output (optional, defaults to the file name). It then outputs (to stdout) a Haskell module which defines a machine object containing the compiled machine. Example usage:

> ct2hs Omega > Omega.hs
> ghci Omega.hs
λ :t machine
Memory

Some simple Constree debugging facilities have been added in the Botworld.Debug module, which is now bundled with Botworld.

New Games

Four games have been added to the new games directory.

  1. A Prisoner's Dilemma: there are two robots, the left robot and the right robot. There are two cells, the left cell and the right cell. The left robot starts in the left cell, which is the left player's home square. The right robot starts in the right cell, which is the right player's home square. Each robot holds an item that their player values at $1, but which the other player values at $2. The game lasts for one timestep. Each robot must decide whether or not to move into the opponent's home square.
  2. A Stag Hunt: there are two player robots, two hare robots, and one stag robot. Each player robot has just barely enough time to attack exactly one non-player robot, take it's item, and get to it's home square before the game ends. The Hare robot has no shields and holds a low-value item. The Stag robot holds two high-value items, but has one shield, which means that it must be attacked twice in order to drop its items. (The time constraints are such that the attack must be simultaneous, and such that no one player can score both of the stag's items.)
  3. A Precommitment game, to be explained in an upcoming post.
  4. A Self-destruction game, to be explained in an upcoming post.
In order to play these games, you'll have to provide machines for the player robots. This can be written using the ct language and the ct2hs binary as described above. For example:

> ct2hs LeftBot > LeftBot.hs
> ct2hs RightBot > RightBot.hs
> ghci PrisonersDilemma
λ :m +LeftBot
λ :m +RightBot
λ run LeftBot.machine RightBot.machine
...

Comments (2)

Comment author: Vulture 03 May 2014 03:37:03PM 0 points [-]

Okay, so this may be a really stupid question, but would it be possible to use botworld to test decision theories experimentally? Like pitting a bot running TDT against one running CDT in a bunch of partially-randomized scenarios, and seeing who scores higher?

Comment author: philh 03 May 2014 08:58:55PM 2 points [-]

For a given situation, you might be able to work out "what would a TDT agent do", and you might be able to program your bot do that. (These are different challenges, because a TDT agent might analyse its opponent's source code, which is a difficult programming problem.) You might be able to do the same for CDT, and pit the two bots against each other. I guess you wouldn't learn very much from the results, because if you can program the TDT and CDT actions for this situation, it's probably simple enough to just analyze it and work out what happens.

Implementing either of these algorithms in general is beyond our current abilities.