Tag: exercise

The old Core War was a game where you write assembly code (Redcode) that runs in shared memory.  The goal is to write code that crashes your opponents.   Let’s try to update it to the new millennium and higher level languages.

At the Highest Level

At the highest level, Core War 2015 is a game where each player writes a function whose data resides in a shared memory space (the Arena).  Each function is given a magic number at the start of the game; at the end, the winner is determined by which magic number appears most often in the arena.

Like Core War, part of the game is over-writing your opponent’s data.  Unlike the original game, we assume that instructions are in a separate, protected region of memory.  Unlike the original Core War game, you can play this in a high-level language (e.g. Java, Python, C++).

The Rules

1. The user writes a function; the function is passed a pointer to the Arena.
2. The user’s code may not store any state outside the Arena.  I.e. no local variables, no allocations on the heap, et cetera.
   1. If you want to store state, you store it via the Arena pointer.
   2. All reads or writes to the Arena are atomic, aligned, 8-byte accesses.
3. Standard libraries may be used as long as:
   1. they have no nontrivial side effects, and
   2. they are strictly functions of their input.  (Specifically a function when called with the same argument must always return the same value.)
   3. Random number generators and timers are allowed, but see 3.1 and 2.
4. The Arena is circular, of finite size, and each program starts in a different place in the Arena.
   1. Each function sees itself as starting at address zero.
   2. The zero-point of each player is chosen uniformly randomly on 8-byte boundaries, with the constraint that the starting values of players don’t overlap.
   3. Each function can read or write anywhere on the Arena.
5. The Arena is initialized to zero everywhere, except for five values at each function’s origin (all are 8-byte integers):
   1. A special constant, to act as a marker, 0xbead1234
   2. The function’s magic number,
   3. The size of the Array (in bytes).
   4. The number of players in this round.
   5. An end marker: 0xbead5678.
6. Each player’s code runs until it makes either 1 write or M reads to the Arena.
   1.   Control is then passed to the next player.
7. After N accesses per player, the game ends.
   1. When the game ends, the player with the most copies of his/her magic number in the Arena wins.  (Only 8-byte aligned copies count.)
   2. If a player’s function runs for more than T seconds without making any access, that player loses and the game is restarted without that player.

Strategic Questions

• Your magic number could be overwritten.  If so, you may end up working for someone else.  Do you want to make several copies of your magic number for safety?
• Unlike Core War, you can do a large amount of computation per step.
• Any time you read from the Arena, you’re missing an opportunity to write your magic number.
• If you’re going to write a loop, the loop counter will be stored in the Arena, and could be overwritten.
• As M increases, you’d expect strategies that use more reading and thinking, rather than blindly writing.
• Does it pay to hide your markers?

What does the Arena look like?

In pseudocode:

Class Arena:
 int64 Get(int address);
 bytestring GetS(int address, int length);
 void Set(int address, int64 value);
 void SetS(int address, bytestring value);

In other words, integers are convenient, but if you want, and if you don’t mind waiting, you can allocate arbitrary data in the Arena.