Robby the Robot

Robby is a robot who wanders around a grid looking for empty soda cans to pick up. Each cell is either already clean or has one piece of litter (a soda can). Robby has no memory. At any given time, all he knows is what’s in his current cell, and what’s in each of the adjacent cells to the north, south, east, and west.

Robby’s goal is to pick up as many of the soda cans—which are randomly distributed across the 10×10 grid—as possible, without bumping into the wall bordering the grid. His performance is evaluated by using rewards and punishments:

• +10 points for every soda can picked up
• -5 points for running into a wall
• -1 point for trying to pick up a can where there isn’t one

Robby’s strategy is a finite state machine which describes which action to take for each possible state he can find himself in. Each action is one of these:

• Move north
• Move west
• Move south
• Move east
• Move randomly
• Do nothing
• Try to pick up a soda can in current cell

With no knowledge of where he is in the room, and no memory of where he’s been, how can he act in a way that maximizes his score? There are three versions of Robby to compare:

1. “Darwin” Robby: Genetic algorithm (default)
2. “Smart” Robby: Genetic algorithm plus some extra hard-coded logic that allows him to avoid punishments
3. “Intelligent Design” Robby: A hand-crafted strategy that does not evolve

The genetic algorithms start with completely random genes (which are Robby’s strategy/FSM), and use selection of the fittest, mutation, and crossover to evolve this strategy over many generations.

Variable naming convention

This codebase uses an uncommon variable naming convention. It makes sense--with an explanation--I swear!

The convention is something like Applications Hungarian. (It’s not widely documented enough to know for sure.)

It’s similar to classic Windows APIs (Systems Hungarian), where each variable’s name has a prefix indicating its type, like w, dw, pb: word, dword, pointer to a byte, respectively.

Instead of those low-level prefixes that strictly represent data type, we use these, which signify what the variable represents:

• c: count
• i: index into an array
• r: real number (floating point)
• n: number (generic)
• min: lowest value or index
• max: highest value or index
• p: pointer
• rg: array (rg as in "range")
• sz: standard C string (z for zero/nul-terminated)

These prefixes can be combined with each other and with higher-level data types (structs), as well.

Prefixes for types specific to this program:

• act: ACTION value (an enum)
• stg: STRATEGY struct
• wld: WORLD struct
• Pop: POPULATION struct (capitalization to avoid leading-p confusion with pointers)

Examples:

• pstgMother is a pointer to a STRATEGY for a "mother" (one of the parents used when "mating" strategies)
• iact is an index into an array of actions ([i]ndex and [act]ion are clear enough, thus it doesn’t need to be irgact)
• cStrategies is a count of strategies. More traditional names for this variable would be num_strategies or strategy_count.