Lab Rat Race: an exercise in genetic algorithms

Question

This is Fortnightly Challenge #3. Theme: Genetic Algorithms

This challenge is a bit of an experiment. We wanted to see what we could do, challenge-wise, with genetic algorithms. Not everything may be optimal, but we tried our best to make it accessible. If this works out, who knows what we might see in the future. Maybe a genetic King of the Hill?

The spec is quite long! We've tried to separate the spec into The Basics - the bare minimum you need to know to start playing with the framework and submit an answer - and The Gory Details - the full spec, with all details about the controller, based on which you could write your own.
If you have any questions whatsoever, feel free to join us in chat!

You're a researcher in behavioural psychology. It's Friday evening and you and your colleagues decide to have some fun and use your lab rats for a little rat race. In fact, before we get too emotionally attached to them, let's call them specimens.

You have set up a little race track for the specimens, and to make it more interesting, you've put a few walls and traps and teleporters across the track. Now, your specimens are still rats... they have no idea what a trap or a teleporter is. All they see is some things in different colours. They also don't have any sort of memory - all they can do is make decisions based on their current surroundings. I guess natural selection will pick out the specimens that know how to avoid a trap from those that don't (this race is going to take a while...). Let the games begin!^†

^{† 84,465 specimens were harmed in the making of this challenge.}

The Basics

This is a single-player game (you and your colleagues didn't want to mix up the populations so each one built their own race track). The race track is a rectangular grid, 15 cells tall and 50 cells wide. You start with 15 specimens on random (not necessarily distinct) cells on the left edge (where x = 0). Your specimens should try to reach the goal which is any cell at x ≥ 49 and 0 ≤ y ≤ 14 (the specimens may overshoot the track to the right). Each time this happens, you get a point. You also start the game with 1 point. You should try to maximise your points after 10,000 turns.

Multiple specimens may occupy the same cell and will not interact.

At each turn, each specimen sees a 5x5 grid of their surroundings (with itself in the centre). Each cell of that grid will contain a colour -1 to 15. -1 represents cells that are out of bounds. Your specimen dies if it moves out of bounds. As for the other colours, they represent empty cells, traps, walls and teleporters. But your specimen doesn't know which colour represents what and neither do you. There are some constraints though:

• 8 colours will represent empty cells.
• 4 colours will represent a teleporter. A teleporter will send the specimen to a certain cell within its 9x9 neighbourhood. This offset will be the same for all teleporters of the same colour.
• 2 colours will represent walls. Moving into a wall is the same as standing still.
• 2 colours will represent a trap. A trap indicates that one of the 9 cells in its immediate neighbourhood is lethal (not necessarily the trap cell itself). This offset will be the same for all traps of the same colour.

Now, about that natural selection... each specimen has a genome, which is a number with 100 bits. New specimens will be created by cross-breeding two existing specimens, and then mutating the genome slightly. The more successful a specimen, the bigger its chance of reproducing.

So here is your task: You will write a single function, which receives as input the 5x5 grid of colours a specimen sees, as well as its genome. Your function will return a move (Δx, Δy) for the specimen, where Δx and Δy will each be one of {-1, 0, 1}. You must not persist any data between function calls. This includes using your own random number generators. Your function will be provided with a seeded RNG which you are free to use as you want.

Your submission's score will be the geometric mean of the number of points across 50 random tracks. We have found that this score is subject to a fair bit of variance. Therefore, these scores will be preliminary. Once this challenge dies down, a deadline will be announced. At the end of the deadline, 100 boards will be chosen at random, and all submissions will be rescored on these 100 boards. Feel free to put an estimated score in your answer, but we will score every submission ourselves to ensure no one cheats.

We have provided controller programs in a handful of languages. Currently, you can write your submission in Python (2 or 3), Ruby, C++, C# or Java. The controller generates the boards, runs the game and provides a framework for the genetic algorithm. All you have to do is provide the moving function.

Wait, so what exactly do I do with the genome?

The challenge is to figure that out!

Since the specimens have no memory, all you've got in a given turn is a 5x5 grid of colours that don't mean anything to you. So you'll have to use the genome to reach the goal. The general idea is that you use parts of the genome to store information about the colours or the grid layout, and your bot bases its decisions on the additional information stored in the genome.

Now, of course you can't actually store anything there manually. So the actual information stored there will initially be completely random. But the genetic algorithm will soon select those specimens whose genome contains the right information while killing off those which have the wrong information. Your goal is to find a mapping from the genome bits and your field of view to a move, which allows you to find a path to the goal quickly and which consistently evolves to a winning strategy.

This should be enough information to get you started. If you want, you can skip the next section, and select your controller of choice from the list of controllers at the bottom (which also contains information about how to use that particular controller).

Read on if you want all...

The Gory Details

^{This specification is complete. All controllers have to implement these rules.}

All randomness uses a uniform distribution, unless stated otherwise.

Track generation:

• The track is a rectangular grid, X = 53 cells wide and Y = 15 cells tall. Cells with x ≥ 49 are goal cells (where x is zero-based).
• Each cell has a single colour and may or may not be lethal - cells are not lethal unless specified by one of the cell types below.
• There are 16 different cell colours, labelled from 0 to 15, whose meaning will change from game to game. In addition, -1 represents cells that are out of bounds - these are lethal.
• Choose 8 random colours. These will be empty cells (which have no effect).
• Choose 4 more random colours. These are teleporters. For two of these colours, choose a non-zero offset in the 9x9 neighbourhood (from (-4,-4) to (4,4) except (0,0)). For the other two colours, invert those offsets. If a specimen steps on a teleporter it is immediately moved by that offset.
• Choose 2 more random colours. These are traps. For each of these colours, choose an offset in the 3x3 neighbourhood (from (-1,-1) to (1,1)). A trap indicates that the cell at that offset is lethal. Note: The trap cell itself is not necessarily lethal.
• The 2 remaining colours are walls, which impede movement. Attempting to move onto a wall cell will turn the move into staying still. Wall cells themselves are lethal.
• For each non-goal cell of the grid, choose a random colour. For each goal cell choose a random empty colour.
• For each cell at the left edge of the track, determine whether the goal can be reached within 100 turns (according to the turn order rules below). If so, this cell is an admissible starting cell. If there are less than 10 starting cells, discard the track and generate a new one.
• Create 15 specimens, each with a random genome and age 0. Place each specimen on a random starting cell.

Turn order:

1. The following steps will be performed, in order, for each specimen. Specimens do not interact or see each other, and may occupy the same cell.
   1. If the specimen's age is 100, it dies. Otherwise, increment its age by 1.
   2. The specimen is given its field of view - a 5x5 grid of colours, centred on the specimen - and returns a move in its 3x3 neighbourhood. Moves outside this range will cause the controller to terminate.
   3. If the target cell is a wall, then the move is changed to (0,0).
   4. If the target cell is a teleporter, the specimen is moved by the teleporter's offset. Note: This step is performed once, not iteratively.
   5. If the cell currently occupied by the specimen (potentially after using one teleporter) is lethal the specimen dies. This is the only time specimens die (apart from step 1.1. above). In particular, a new specimen which spawns on a lethal cell will not die immediately, but has a chance to move off the dangerous cell first.
   6. If the specimen occupies a goal cell, score a point, move the specimen to a random starting cell and reset its age to 0.
2. If there are less than two specimens left on the board, the game ends.
3. Create 10 new specimens with age 0. Each genome is determined (individually) by the breeding rules below. Place each specimen on a random starting cell.

Breeding:

• When a new specimen is created choose two distinct parents at random, with a bias towards specimens which have progressed further to the right. The probability of a specimen to be chosen is proportional to its current fitness score. A specimen’s fitness score is

  1 + x + 50 * number of times it reached the goal

  where x is the 0-based horizontal index. Specimens created in the same turn cannot be chosen as parents.

• Of the two parents, choose a random one to take the first genome bit from.

• Now as you walk along the genome, switch parents with a probability of 0.05, and keep taking bits from the resulting parent.
• Mutate the fully assembled genome: for each bit, flip it with probability 0.01.

Scoring:

• One game lasts 10,000 turns.
• Players start the game with 1 point (to allow use of the geometric mean).
• Every time a specimen reaches the goal, the player scores a point.
• For now, each player's submission will be run for 50 games, each with a different random track.
• The above approach results in more variance than is desirable. Once this challenge dies down, a deadline will be announced. At the end of the deadline, 100 boards will be chosen at random, and all submissions will be rescored on these 100 boards.
• A player's overall score is the geometric mean of the scores of these individual games.

The Controllers

You may choose any of the following controllers (as they are functionally equivalent). We have tested all of them, but if you spot a bug, want improve the code or performance, or add a feature like graphical output, please do send raise an issue or send a pull request on GitHub! You're also welcome to add a new controller in another language!

Click the language name for each controller to get to the right directory on GitHub, which contains a README.md with exact usage instructions.

If you're not familiar with git and/or GitHub, you can download the entire repository as a ZIP from the front page (see the button in the sidebar).

Python

• Most thoroughly tested. This is our reference implementation.
• Works with both Python 2.6+ and Python 3.2+!
• It's very slow. We recommend running it with PyPy for a substantial speedup.
• Supports graphical output using either pygame or tkinter.

Ruby

• Tested with Ruby 2.0.0. Should work with newer versions.
• It's also fairly slow, but Ruby may be convenient for prototyping an idea for a submission.

C++

• Requires C++11.
• Optionally supports multithreading.
• By far the fastest controller in the bunch.

C#

• Uses LINQ, so it requires .NET 3.5.
• Rather slow.

Java

• Not particularly slow. Not particularly fast.

Preliminary Leaderboard

All scores are preliminary. Nevertheless, if something is plain wrong or out of date, please let me know. Our example submission is listed for comparison, but not in contention.

  Score   | # Games | User               | Language   | Bot           
===================================================================================
2914.13   |   2000  | kuroi neko         | C++        | Hard Believers
1817.05097|   1000  | TheBestOne         | Java       | Running Star
1009.72   |   2000  | kuroi neko         | C++        | Blind faith
 782.18   |   2000  | MT0                | C++        | Cautious Specimens
 428.38   |         | user2487951        | Python     | NeighborsOfNeighbors
 145.35   |   2000  | Wouter ibens       | C++        | Triple Score
 133.2    |         | Anton              | C++        | StarPlayer
 122.92   |         | Dominik Müller     | Python     | SkyWalker
  89.90   |         | aschmack           | C++        | LookAheadPlayer
  74.7    |         | bitpwner           | C++        | ColorFarSeeker
  70.98   |   2000  | Ceribia            | C++        | WallGuesser
  50.35   |         | feersum            | C++        | Run-Bonus Player
  35.85   |         | Zgarb              | C++        | Pathfinder
 (34.45)  |   5000  | Martin Büttner     | <all>      | ColorScorePlayer
   9.77   |         | DenDenDo           | C++        | SlowAndSteady
   3.7    |         | flawr              | Java       | IAmARobotPlayer
   1.9    |         | trichoplax         | Python     | Bishop
   1.04   |   2000  | fluffy             | C++        | Gray-Color Lookahead

Credits

This challenge was a huge collaborative effort:

• Nathan Merril: Wrote Python and Java controllers. Turned the challenge concept from a King-of-the-Hill into a Rat Race.
• trichoplax: Playtesting. Worked on Python controller.
• feersum: Wrote C++ controller.
• VisualMelon: Wrote C# controller.
• Martin Büttner: Concept. Wrote Ruby controller. Playtesting. Worked on Python controller.
• T Abraham: Playtesting. Tested Python and reviewed C# and C++ controller.

All of the above users (and probably a couple more I forgot) have contributed to the overall design of the challenge.

C++ controller update

If you are using the C++ with Visual Studio and multithreading, you should get the latest update because of a bug with their random number generator seeding which allows duplicate boards to be produced.

Answer 1

Blind faith - C++ - seems to score above 800(!) over 2000 runs

Color coding genome with a mysterious track feedback and an effective wall-banging deterrent

#include "./gamelogic.cpp"

#define NUM_COLORS 16

// color meanings for our rats
typedef enum { good, bad, trap } colorType_t;
struct colorInfo_t {
    colorType_t type;
    coord_t offset; // trap relative location
    colorInfo_t() : type(good) {} // our rats are born optimists
};

// all 8 possible neighbours, carefully ordered
coord_t moves_up  [] = { { 1, 0 }, { 1,  1 }, { 1, -1 }, { 0,  1 }, { 0, -1 }, { -1, 0 }, { -1,  1 }, { -1, -1 } };  // toward the goal, going up   first
coord_t moves_down[] = { { 1, 0 }, { 1, -1 }, { 1,  1 }, { 0, -1 }, { 0,  1 }, { -1, 0 }, { -1, -1 }, { -1,  1 } };  // toward the goal, going down first

// map of the surroundings
struct map_t {
    static const size_t size = 5;
    static const int max = size / 2;
    static const int min = -max;
    colorType_t map[size*size];
    colorType_t & operator() (int x, int y) { return map[(x + max)*size + y + max]; }
    colorType_t & operator() (coord_t pos) { return operator()(pos.x, pos.y); }
    bool is_inside(int x, int y) { return abs(x) <= max && abs(y) <= max; }
    bool is_inside(coord_t pos) { return is_inside(pos.x,pos.y); }
};

// trap mapping info
struct trap_t {
    coord_t detector;
    colorInfo_t color;
    trap_t(int x, int y, colorInfo_t & color) : color(color) { detector.x = x; detector.y = y; }
    trap_t() {}
};

coord_t blindFaith(dna_t d, view_t v)
{
    colorInfo_t color[NUM_COLORS]; // color informations

    // decode colors
    for (size_t c = 0; c != 16; c++)
    {
        size_t base = c * 4;
        if (d[base])
        {
            color[c].type = d[base+1] ? good : bad;
        }
        else // decode trap location
        {
            color[c].type = trap;
            int offset = d[base+1] + 2 * d[base+2] + 4 * d[base+3];
            color[c].offset = moves_up[offset]; // the order is irrelevant as long as all 8 neighbours are listed
        }
    }

    // build a map of the surrounding cells
    map_t map;
    unsigned signature = 0;
    int i = 0;
    for (int x = map.min; x <= map.max; x++)
    for (int y = map.min; y <= map.max; y++)
    {
        int c = v(x, y);
        map(x, y) = (c == -1) ? bad : color[c].type;
        if (c != -1) signature ^= v(x, y) << ((i++) % 28);
    }

    // map traps
    for (int x = map.min; x <= map.max; x++)
    for (int y = map.min; y <= map.max; y++)
    {
        if (map(x, y) != trap) continue;
        const colorInfo_t & trap = color[v(x, y)];
        int bad_x = x + trap.offset.x;
        int bad_y = y + trap.offset.y;
        if (!map.is_inside(bad_x, bad_y)) continue;
        map(bad_x, bad_y) = bad;
        map(x, y) = good;
    }

    // pick a vertical direction according to surroundings signature
    int go_up = d[64 + signature % (DNA_BITS - 64)];

    // try to move to a good cell nearer the goal
    for (const coord_t &move : go_up ? moves_up : moves_down) if (map(move.x, move.y) == good) return move;

    // try not to increase fitness of this intellectually impaired specimen
    return{ -1, 0 };
}

int main() {
    time_t start = time(NULL);
    double score = runsimulation(blindFaith);
    slog << "Geometric mean score: " << score << " in " << time(NULL) - start << " seconds";
}

Sample results:

Scores: 15 4113306 190703 1 1 44629 118172 43594 63023 2 4 1 1 205027 1 455951 4194047 1 5 279 1 3863570 616483 17797 42584 1 37442 1 37 1 432545 5 94335 1 1 187036 1 4233379 1561445 1 1 1 1 35246 1 150154 1 1 1 1 90141 6 1 1 1 26849 1 161903 4 123972 1 55 988 7042063 694 4711342 90514 3726251 2 1 383389 1 593029 12088 1 149779 69144 21218 290963 17829 1072904 368771 84 872958 30456 133784 4843896 1 2 37 381780 14 540066 3046713 12 5 1 92181 5174 1 156292 13 1 1 29940 66678 125975 52714 1 5 3 1 101267 69003 1 1 10231 143110 282328 4 71750 324545 25 1 22 102414 1 3884626 4 28202 64057 1 1 1 1 70707 4078970 1623071 5047 1 1 549040 1 1 66 3520283 1 6035495 1 79773 1 1 1 218408 1 1 15 33 589875 310455 112274 1 1 4 1 3716220 14 180123 1 2 12785 113116 12 2 1 59286 822912 2244520 1840950 147151 1255115 1 49 2 182262 109717 2 9 1049697 59297 1 11 64568 1 57093 52588 63990 331081 54110 1 1 1537 3 38043 1514692 360087 1 260395 19557 3583536 1 4 152302 2636569 12 1 105991 374793 14 3934727 1 2 182614 1 1675472 121949 11 5 283271 207686 175468 1 1 173240 1 138778 1 1 59964 3290382 1 4 1757946 1 23520 1 2 94 1 124577 497071 1749760 39238 1 301144 3 1 2871836 1 1 10486 1 11 8 1 111421 11 1807900 1 587479 1 42725 116006 3 1 6 5441895 1 1 22 52465 952 1 18 1 1 46878 2 1 1 1994 4 593858 123513 4692516 820868 4247357 1 1 2 1 2 8770 2 1 95371 4897243 2 22741 1 1 1 1 325142 6 33650 4 51 102993 1 182664 1 4040608 18153 2045673 462339 1 1 617575 2 2551800 3 7760 1 108012 76167 143362 1148457 1 53460 1 71503 1 1 1 1 81482 3208 62286 69 139 1 3503941 1 253624 101903 3081954 80123 84701 9 16 1 1070688 71604 613064 2076 15009 9 1 1 1 199731 1 2 1 63132 1 1843855 27808 1 3569689 273144 1 460524 2703719 22443 10876 51242 1 6972678 4591939 1 140506 43981 45076 2 1 91301 5 1 1874615 1758284 608 13 1 96545 75161 1 618144 4 2056133 1 1 2 57401 1394307 6 188116 83545 1 41883 1 1 467189 371722 1 1122993 1 17912 159499 1 5 3355398 33 1 2 246304 1 2 168349 1 50292 12 141492 2723076 3 1 6 3060433 223360 171472 106409 1 2 1 102729 8814 1 285154 1 11 1 65 930 2 689644 3271116 1 5 4 60 77447 1 1 1477538 256023 100403 2480335 1 39888 1 1 70052 66090 1 250 1 2 8 115371 1523106 1424 168148 1 1 1 42938 17 1 364285 185080 1 1 36 4903764 13 51987 1106 276212 67460 1 251257 2 6867732 1 1 1890073 1 1 8 5 2118932 210 0 3792346 5209168 1 1 1 1 51 1 4621148 1 37 337073 3506096 1 1 1 1 458964 2 16 52930 1 15375 267685 1 1 1259646 14930 3248678 527105 1 103 24 1 3252685 6009 1 1 176340 3971529 121 1722808 1 31483 194232 2314706 95952 3625407 3 216755 56 1 8 1 1 1 1 885 229 9056 172027 31516 2526805 1 76076 1589061 1 1 8 90812 1 21 72036 1681271 2 212431 1581814 85993 79967 4 7 514708 1070070 1 71698 1 23478 15882 94453 1 27382 495493 277308 12127 91928 248593 1 1 1 26540 1709344 2119856 1 1 48867 107017 251374 64041 15924 15 87474 8 1 23 9 48 1 1 1 51793 2 61029 84803 15 689851 1 1 873503 10 140084 420034 87087 82223 1 163273 12 1 5 570463 19 26665 1 170311 1 39983 1 475306 1 2 36417 746105 11 141345 1 3 1 30 3 1 1 1 1 1312289 408117 1 42210 273871 561592 1 1 1 1 4448568 48448 7 378508 1 351858 278331 1 79515 1169309 3670107 14711 4686395 1156554 33 2528441 24537 76 335390 63545 122108 76675 21929 34 1 861361 83000 417781 1 90487 1 1 85116 7 2 1 60129 647991 79 1 2755780 726845 244217 50007 187212 1 3674051 286071 44068 3 307427 26973 1 26059 1957457 230783 58102 545318 1 4 172542 168365 1 89402 1 4 1 1 1 1 2 3 16 62935 5643183 117961 109942 85762 5 117376 118883 1 61 23893 122536 70185 1 64252 208409 179269 55381 1579240 3434491 1 4964284 3356245 3 21 2197119 346542 44340 59976 772220 5590844 199721 90858 63785 125989 57219 129737 81836 1 3671 16810 1 4151040 1 15 40108 1 443679 3224921 2 27498 2 3 146529 169409 19 1 1 1 1 41627 1 3 2722438 1 2013730 1 1649406 1 1 6943 125772 58652 1 1 1 2413522 1 2 48 36067 253807 2 146464 1 248 07 3359223 139896 395985 65241 43988 594638 69033 275085 1 17973 1 1 1 594835 1 1 4468341 3496274 222854 94769 55 161056 36185 8793 277592 3 1 6746 1 138151 66 37365 1 2729315 1 3 57091 22408 249875 246514 85058 1 20 5463152 1 3 1 45293 1 70488 2792458 461 441 951926 2236205 2 171980 1 1 48 3893009 1 458077 1 268203 1 70005 7 19299 1 278978 1 45286 26 2 1883506 274393 342679 1 1 913722 911600 12688 1 1 115020 1249307 1529878 53426 1 226862 3721440 23537 86033 397433 1 1 1 161423 96343 94496 1 1 1 2 1 111576 1 4039782 1 1 1 5742393 3569 46072 1 1 2 1 1 85335 219988 1 78871 115876 43405 1 300835 1 166684 53134 1 3 111487 6 3 3 77 1 115971 3 205782 10 1932578 356857 43258 47998 1 27648 127096 573939 32650 523906 45193 1 2 128992 1 10144 1 257941 1 19841 5077836 14670 5 3 6 1 1 21 14651 2906084 37942 45032 9 304192 3035905 6214026 2 177952 1 51338 1 65594 46426 553875 2676479 245774 95881 3 216364 3064811 1198509 223982 3 6 1 533254 1 590363 264940 68346 127284 1 7 1 1 4617874 5 45400 1 1 3097950 360274 1 3 1 8421 14 469681 418563 3 1 6 1 1 575766 405239 11 2631108 152667 1 1 1 467383 1 1 775499 1 157998 2 1 143351 92021 1 1 1173046 3636579 1 70635 162303 1 1534876 834682 2 1 1 11981 346908 245124 607794 17 1570641 126995 13 57050 1 2 33731 29739 1 1 35460 1 33716 168190 214704 1 443156 701674 2636870 108081 1604895 1 1 11 115901 23 571891 360680 1 1 35 1 2036975 1 1 2555536 4742615 5 360553 287044 1 1814255 7 59632 1 216 41546 1 540920 353424 2625301 223744 1 1 1 15717 3 429871 1 4 2329632 18 11 1 2 4 1 3905 5 1 1 1 2 5431442 1 859628 1 3 338378 15236 13764 1 3384362 1 15 65293 24 619599 152620 2 189921 35854 16647 7 2 404790 360096 1 2 189459 1097768 191610 1 1 470254 1 12 2 330299 364219 2365542 312023 2273374 2 10527 1 115453 1 2 3845592 52388 913449 1 14695 1 44 37352 90302 1 1 1 233577 51639 3474983 44010 1650727 31 2 2 1 8 7 1 3 5 25603 17799 45630 758457 1 4571839 37 4 3 2 1 1 1351271 196673 12 2880765 263886 2926173 1 2 1 241502 5 6 1 278576 9 7 290722 42749 143391 82753 21771 57887 1 1 60400 1766903 1 296392 1 5 2861787 125560 1 9 199218 1 1 308226 517598 2246753 12 1168981 3 98447 1 488613 9 842865 202108 10 1 238493 1 1523706 5383982 29435 1 1 207071 1 8 4 125742 70531 253135 72207 124291 23364 184376 2 40034 9569353 194109 102854 2 3247153 58313 85995 1 598 63 1 2676692 10 3573233 1 36651 118016 2486962 65456 46760 1 5813 723 178120 2 153305 1 1 2 1 2354413 3 1 17126 132953 437123 299778 3070490 1 6490 403704 2261 511439 1 39 33410 173045 1 1 120970 641346 132042 1 44906 1 33940 132124 467702 45472 9 44 1 1 1 107008 1 46635 1 121431 130760 1 7 3 1 56251 1299306 3 1 1 1 15 2147678 215169 1374943 1 332995 231089 269310 1 7816944 1 1 1 46 134426 1 1 1 2 76112 1 1 30438 299927 25 139373 76048 278757 71 3474997 1 294046 1 3126554 2518019 2 1 6 1 3054393 1 1 1 2 525 96 419528 1 1 154718 233 207879 26 1 6 57436 3 5944942 1 1 318198 147536 1 22 420557 1 1 120938 1 1 167412 4082969 73299 1 11 3557361 1 4 330028 269051 1 2569546 2 1 1 4 1 1 377412 1 1 1 213800 58131 1422177 54 109617 117751 12432 3830664 419046 3 6821 741 919 1 22335 1 1 15069 80694 488809 2389 2308679 145548 51411 115786 110984 107713 1 12 6 1 5 8365 1 2001874 210250 4674015 14 1 1204101 314354 89066 1 1 2438200 68350 1 1575329 5593838 2743787 151670 57 16 5948210 597158 128060 189160 23628 1 1 15 4171774 1 8206 4157492 1 2 315607 1618680 24736 18520 4787225 33842 134431 1 1 1 1 1 1115809 17759 1 33016 123117 1 77322 169633 219091 1 321593 57231 135536 175401 4 1 435702 1 253132 100707 114547 1 119324 6382967 1472898 3 72567 1707408 177958 26 208719 1 27083 74 12 576410 19375 177069 4 3 1 31 507048 2 1 1 2 1 2 1 40 7 99892 95202 60649 241396 232370 1 136579 70649 1 2877 280695 13603 102860 404583 29717 112769 1 54089 1 97579 40819 2 868629 64848 2 63432 5 1 1888426 99623 2 1 7911 53646 3047637 1 2 3 152910 1 3244662 105187 1 1 1 1 8966 200347 1 1 22 302654 6 17 1 10 328150 55259 1016 117291 2 1 224524 23846 74645 1 1 1 1 1 3117394 10847 33976 144613 4 201584 1 1 26959 3 4410588 27019 6 66749 55935 23 4126812 4089989 99959 1 1 1 1 55490 1 4275599 13652 33967 2 8126062 337093 320653 128015 4 1 7729132 1 10594 116651 20990 3046630 1 353731 132989 2066431 4 80 15575 147430 1 621461 3100943 2306122 5 33439 407945 25634 1 2911806 32511 2174235 298281 15159 54125 1 2 3063577 2205013 1 407984 1 319713 1 22171 1 2763843 1 2607606 1 100015 3096036 1 55905 1 1 635265 2890760 1 1 1 1 35854 1 352022 2652014 1 2 274366 1 4 1 602980 4 83828 602270 2816 2 59116 25340 1 11 1 5162051 34 8 218372 1186732 142966 1 1 170557 503302 1 84924 5 1 1350329 1 1 1 130273 78055 902762 1 8581 5 1 3635882 1 1 1 224255 44044 61250 2 438453 8 1 2729357 28 1 17658 82640 1 31809 10 1 33 1 1 45495 5798 5000217 40018 588787 67269 1 12 83512 2798339 1 609271 1 3 1 7 67912 189808 3388775 60961 81311 1167 24939 433791 405306 85934 1 1170651 2 1 66 552579 122985 515363 2188340 1 1 1 3807012 1502582 4 13 149593 1 1 2108196 3 34279 24613 1282047 27 1 2 1 1 584435 27487 1 1 5 33278 1 1 1202843 1 1 1 6 3649820 3100 2 266150 13 164117 10 53163 3295075 1 1 1 1 77890 1 286220 90823 18866 3139039 481826 1 3994676 23 116901 132290 6 3927 84948 1 1 1 1 256310 1 11 8 1 102002 8392 887732 98483 444991 1 1 49408 409967 1158979 1 1 1 81469 189764 3960930 296231 64258 1 1 176030 4 1 2 1 486856 1 1135146 31 2 13112 227077 31
Geometric mean score: 831.185 in 14820 seconds

Based on feersum's unvoluntarily long test, I reckon 2000 runs are enough to produce an acceptably stable result.
Since my modified controller displays the current geometric mean after each run, I confirmed visually that the variation over the last 50 runs was relatively small (+- 10 points).

What makes these critters tick

Instead of giving equal priorities to each color, I consider these possible values:

1. good -> the rat thinks it can go safely there
2. bad -> the rat won't go there
3. trap -> the rat will consider the position of the trap bad and the cell indicating the trap good.
   Though I'm too lazy to rename it, this rather a "danger detector" indicating the (supposed) location of an actual trap, a wall, a teleporter waiting to send the unsuspecting wanderer to an unpleasant place or even the entrance of a dead-end. In short, a place where a wise rat would rather not go.

good or bad genes only take 2 bits to store (for instance 11 and 10), but traps require 4 bits (0ttt where ttt represents one of the possible 8 "dangerous" locations).

To keep each gene consistent (i.e. retaining its meaning after been mixed into a completely different genome, which requires each color-coding gene to be at a fixed location), all values are coded on 4 bits (so good is coded as 11xx and bad as 10xx), for a total of 16*4 = 64 bits.

The remaining 36 bits are used as "anti wall-bangers" (more on that later). The 25 surrounding colors are hashed into an index of these 36 bits. Each bit indicates a preferred vertical direction (up or down), that is used when there is a possible choice between two cells.

The strategy is as follows:

• decode each color according to genome (or direct controller report for off-track "bad" cells)
• build a map of the immediate surroundings (3x3 cells, 8 possible neighbours)
• compute a signature of the surroundings (a hash of the 25 colors except off-track cells)
• pick a preferred vertical direction from the signature (among 36 hash buckets)
• try to move to a neighbour hinted as "good", starting with the ones nearest the goal and going in the preferred vertical direction first
• if no "good" neighbour can be found, try to move one cell back (thus possibly being victim of an unfortunate accident, and avoiding to increase fitness at any rate)

Ye rodents, behold the enemies of your kind

The worst thing that can happen to a population is to have produced no winner yet, but a lot of rats stuck either against a wall or inside an infinite teleporting loop close enough to the goal to have a dominant chance of being selected for breeding.
Contrary to rats being squashed in a trap or teleported into walls, these rodents will only be killed by old age.
They have no competitive advantage over their cousins stuck 3 cells from the start, but they will have ample time to breed generation after generation of cretins until their genome becomes dominant, thus harming genetic diversity badly for no good reason.

To mitigate this phenomenon, the idea is to make the offsprings of these bad, bad rats more likely to avoid following in the steps of their ancestry.
The vertical direction indication is only 1 bit long (basically saying "try going up or down first in these surroundings"), and quite a few bits are likely to have an effect on the path followed, so mutations and/or crossovers should have a significant impact.
A lot of the offsprings will have a different behaviour and won't end up banging their head on the same wall (among the corpses of their starved ancestors).
The subtelty here is that this indication is not the dominant factor in the rat's behaviour. Color interpretation will still prevail in most cases (the up/down choice will only matter if there are indeed two "good" cells to choose from and what the rat sees as a harmless color is not a teleporter waiting to cast it into a wall).

Why does it (seem to) work?

I still don't know precisely why.

The absolute stroke of luck that remains an unsolved mystery is the trap mapping logic. It is without a doubt the cornerstone of success, but it works in its own mysterious ways.

With the coding used, a random genome will produce 25% "good", 25% "bad" and 50% "trap" color identifiers.
the "trap" identifiers will in turn produce "good" and "bad" estimations in correlation with the 5x5 surroundings.
As a result, a rat at a given location will "see" the world as a mix of stable and contextual "go / no go" colors.

As the quite successful anti-banging mechanism seems to indicate, the worst kind of element on the track is the dreaded wall (and its cousin the teleporting loop, but I guess these are far less common).

The conclusion is, a successful program must above all manage to evolve rats able to detect positions that will lead to a slow starvation without reaching the goal.

Even without "guessing" the two colors representing walls, the "trap" colors seem to contribute to wall avoidance by allowing a rat to bypass a few obstacles not because it "saw" the walls, but because the "trap" estimation ruled out these particular wall cells in these particular surroundings.

Even though the rat tries to move toward the goal (which might lead to think the most "useful" trap indicators are the ones indicating a danger in front), I think all trap directions have roughly the same influence: a trap indicating "danger behind" located 2 cells in front of a rat has the same influence as one indicating "danger ahead" when the rat stands right on top of it.

Why this mix has the property to make the genome converge so successfully is way beyond my maths, unfortunately.

I feel more confortable with the wall-banging deterrent. This just worked as planned, though well above my expectations (the score was basically multiplied by four).

I hacked the controller heavily to display some data. Here are a couple of runs:

Turns:2499 best rat B  B  B  G  B  G  T3 G  T4 B  G  B  B  B  G  G  ^vv^^vv^v^v^^^vvv^v^^^v^^^v^vv^^v^^^ Max fitness: 790 Specimens: 1217 Score: 2800
Turns:4999 best rat B  B  B  G  B  G  T3 G  T4 B  G  B  B  B  G  G  ^vv^^vv^v^v^^^vvv^v^^^v^^^v^vv^^v^^^ Max fitness: 5217 Specimens: 15857 Score: 685986
Turns:7499 best rat B  B  B  G  B  G  T3 G  T4 B  G  B  B  B  G  G  ^vv^^vv^v^v^^^vvv^v^^^vvvvv^^v^v^^^^ Max fitness: 9785 Specimens: 31053 Score: 2695045
Turns:9999 best rat B  B  B  G  B  G  T3 G  T4 B  G  B  B  B  G  G  ^vv^^vv^v^v^^^vvv^v^^^vvvvv^^v^v^^^^ Max fitness: 14377 Specimens: 46384 Score: 6033904
Scored 6035495 in game 146 current mean 466.875

Here a breed of super-rat appeared early (the track probably allowed to run in a straight line and some lucky rat in the very first generations had the right DNA to take advantage of it). The number of specimens in the end is about the half of the theoretical max of some 100.000 rats, which means nearly half the critters acquired the ability to survive this particular track indefinitely (!).
Of course the resulting score is simply obscene - as is the computation time, by the way.

Turns:2499 best rat B  T0 G  B  T7 B  G  B  T6 T0 T3 B  G  G  G  T4 ^v^^^^^v^^v^v^^^^^^^^v^v^v^^vvv^v^^^ Max fitness: 18 Specimens: 772 Score: 1
Turns:4999 best rat T7 G  G  G  G  T7 G  B  T6 T0 T3 T5 G  G  B  T4 ^vvvvvvv^^^vvv^^v^v^^^^^^^^^^^^^v^^^ Max fitness: 26 Specimens: 856 Score: 1
Turns:7499 best rat G  T0 G  T3 G  T0 G  B  T6 T0 T2 B  T4 G  B  T4 ^^v^vvv^^^vv^^v^vvv^v^^vvvv^^^^^^^^^ Max fitness: 55 Specimens: 836 Score: 5
Turns:9999 best rat T6 T0 G  T5 B  T1 G  B  T6 T0 T3 B  T4 G  B  T4 ^^vv^^^^vv^^v^v^^v^^vvv^vv^vvv^^v^^v Max fitness: 590 Specimens: 1223 Score: 10478
Scored 10486 in game 258 current mean 628.564

Here we can see the genome refinement at work. The lineage between the last two genomes appears clearly. The good and bad evaluations are the most significant. The trap indications seem to oscillate until they either stabilize to a "useful" trap or mutate into good or bad.

It seems the color genes have a few useful characteristics :

• they have a self-contained meaning
  (a specific color has to be handled in a specific way)
  Each color coding can be thrown into a completely different genome without changing the behaviour dramatically - unless the color happens to be in fact a decisive one (typically a wall or a teleporter leading to an infinite loop).
  This is less the case with a basic priority coding, since the most prioritary color is the only information used to decide where to move. Here all "good" colors are equal, so a given color added to the "good" list will have less impact.
• they are relatively resilient to mutations
  the good/bad coding has only 2 significant bits out of 4, and the trap location might be changed most of the time without altering the rat behaviour significantly.
• they are small (4 bits) so the probability to be wrecked by a crossover is very low.
• mutations produce either harmless of meaningful changes
  A gene mutating to "good" will either have little effect (if for instance it corresponds to an empty cell, it might allow to find a new, shorter path, but that could also lead the rat straight into a trap), or a dramatic one (if the color represents a wall, the new rat is very likely to get stuck somewhere).
  A gene flipping to "trap" will either deprive the rat from an essential color or have no noticeable effect.
  A mutation of a trap location will only matter if there is indeed a trap (or anything harmful) ahead, which has a relatively small probability (I would say something like 1/3).

Lastly, I guess the last 36 bits contribute not only to avoid getting rats stuck, but also to spreading rats more evenly on the track, thus preserving genetic diversity until a winning genome emerges and becomes dominant through the color-coding part.

Further work

I must say I find these little critters fascinating.
Thanks again to all the contributors to this excellent challenge.

I am thinking of butchering the controller further to display more significant data, like the ancestry of a successful rat.

I would also very much like to see these rats in action, but this C++ b**ch of a language makes creating - let alone animating - images (among many other things) a messy chore.

In the end, I would like to produce at least an explanation of the trap system, and possibly improve it.

Controller hacking

If someone is interested, I can publish the modifications I made to the controller.
They are dirty and cheap, but they do the job.

I'm no GitHub savvy, so that would have to go through a mere post.

Answer 2

Hard believers - C++ - (improved teleporters): 10.000+ for 2000 runs

(this is an evolution of Blind faith, so you might want to climb another wall of text before this one)

#ifndef NDEBUG
#define NDEBUG
#include "./gamelogic.cpp"
#endif // NDEBUG
#include <cassert>

#define NUM_COLORS 16
#define BITS_OFFSET  3
#define BITS_TYPE    2
#define BITS_SUBTYPE 2
#define BITS_COLOR (BITS_TYPE+BITS_OFFSET)

// how our rats see the world
typedef unsigned char enumSupport_t;
typedef unsigned char trapOffset_t;
typedef enum : enumSupport_t {
    danger,   // code      trap detector
    beam,     // code      safe teleporter
    empty,    // code      empty
    block,    // code      wall, pit or teleporter
    trap,     // computed  detected trap
    pit,      // read      off-board cell
} colorType_t;

// color type encoding (4 first bits of a color gene)
// the order is critical. A single block/empty inversion can cost 2000 points or more
const colorType_t type_decoder[16] = {
    /*00xx-*/
    danger,
    empty,
    beam,
    block,
    /*01xx-*/
    beam,
    danger,
    empty,
    block,
    /*10xx-*/
    empty,
    beam,
    block,
    danger,
    /*11xx-*/
    block,
    empty,
    danger,
    beam,
};

// all 8 possible neighbours, carefully ordered
typedef coord_t neighborhood_t[8];
neighborhood_t moves_up =   { { 1, 0 }, { 1,  1 }, { 1, -1 }, { 0,  1 }, { 0, -1 }, { -1, 0 }, { -1,  1 }, { -1, -1 } };  // toward the goal, going up   first
neighborhood_t moves_down = { { 1, 0 }, { 1, -1 }, { 1,  1 }, { 0, -1 }, { 0,  1 }, { -1, 0 }, { -1, -1 }, { -1,  1 } };  // toward the goal, going down first

// using C++ as a macro-assembler to speedup DNA reading
/*
Would work like a charm *if* a well-paid scatterbrain at Microsoft had not defined
std::bitset::operator[] as

bool operator[](size_t _Pos) const
{   // subscript nonmutable sequence
return (test(_Pos));
}

Bounds checking on operator[] violates the spec and defeats the optimization.
Not only does it an unwanted check; it also prevents inlining and thus generates
two levels of function calls where none are necessary.
The fix is trivial, but how long will it take for Microsoft to implement it, if
the bug ever makes it through their thick layer of tech support bullshit artists?
Just one of the many reasons why STL appears not to live up to the dreams of
Mr Stroustrup & friends...
*/
template<size_t BITS> int DNA_read(dna_t dna, size_t base)
{
    const size_t offset = BITS - 1;
    return (dna[base + offset] << offset) | DNA_read<offset>(dna, base);
}
template<> int DNA_read<0>(dna_t, size_t) { return 0; }

// color gene
struct colorGene_t {
    colorType_t  type;
    trapOffset_t offset;  // trap relative location
    colorGene_t() : type(empty) {} // our rats are born optimists
};

// decoded DNA
class dnaInfo_t {
private:
    const dna_t & dna;
    static const size_t
        direction_start = NUM_COLORS*(BITS_TYPE + BITS_OFFSET),
        direction_size = DNA_BITS - direction_start;

public:
    colorGene_t color[NUM_COLORS];
    int         up_down; // anti-wall-banger

    // decode constant informations during construction
    dnaInfo_t(const dna_t & d) : dna(d)
    {
        for (size_t c = 0; c != NUM_COLORS; c++)
        {
            unsigned raw = DNA_read<BITS_COLOR>(d, c * BITS_COLOR);
            color[c].type = type_decoder[raw >> 1];
            if      (color[c].type == danger) color[c].offset = raw & 7;
            else if (color[c].type == beam  ) color[c].offset = raw & 3;
        }
    }

    // update with surroundings signatures
    void update(size_t signature)
    {
        // anti-blocker
        up_down = (direction_size > 0) ? dna[direction_start + signature % direction_size] : 0;
    }
};

// map of the surroundings
class map_t {
    struct cell_t {
        coord_t pos;
        int     color;
    };

    static const size_t size = 5;
    static const int max = size / 2;
    static const int min = -max;

    size_t local_signature[size*size]; // 8 neighbours signatures for teleporters
    cell_t track_cell[size*size]; // on-track cells
    size_t cell_num;
    colorType_t map[size*size];
    size_t raw_index(int x, int y) { size_t res = x * size + y + max + max * size; assert(res < size*size); return res; }
    size_t raw_index(coord_t pos) { return raw_index(pos.x, pos.y); }

    bool is_inside(int x, int y) { return abs(x) <= max && abs(y) <= max; }

public:
    size_t compute_signatures(view_t v, dnaInfo_t genome)
    {
        cell_num = 0;
        size_t signature = 0;
        memset (local_signature, 0, sizeof(local_signature));
        int i = 0;
        for (int x = min; x <= max; x++)
        for (int y = min; y <= max; y++)
        {
            int c = v(x, y);
            if (c == -1)
            {
                (*this)(x, y) = pit; continue;
            }
            track_cell[cell_num++] = { { x, y }, c };
            signature ^= c << (4 * (i++ & 1));

            if (genome.color[c].type == beam)
            {
                int in = 0;
                for (coord_t n : moves_up)
                {
                    coord_t pn = {x+n.x,y+n.y};
                    if (!is_inside(pn)) continue;
                    int cn = v(pn.x, pn.y);
//                    if (cn == -1) continue;
                    local_signature[raw_index(pn.x,pn.y)] ^= cn << (4 * (in++ & 1));
                }
            }
        }
        return signature;
    }

    void build(dnaInfo_t genome)
    {
        coord_t traps[size*size];
        size_t t_num = 0;

        // plot color meanings
        for (size_t c = 0; c != cell_num; c++)
        {
            const cell_t& cell = track_cell[c];
            const colorGene_t& color = genome.color[cell.color];
            (*this)(cell.pos) = (color.type == beam && (local_signature[raw_index(cell.pos.x,cell.pos.y)] % 4) == color.offset)
                    ? block
                    : color.type;

            // build a list of trap locations
            if (color.type == danger)
            {
                coord_t location = cell.pos + moves_up[color.offset];
                if (is_inside(location)) traps[t_num++] = location;
            }
        }

        // plot trap locations
        while (t_num) (*this)(traps[--t_num]) = trap;
    }

    // quick & dirty pathing
    struct candidate_t {
        coord_t pos;
        candidate_t * parent;
        candidate_t() {} // default constructor does not waste time in initializations
        candidate_t(int) : parent(nullptr) { pos.x = pos.y = 0; } // ...this is ugly...
        candidate_t(coord_t pos, candidate_t * parent) : pos(pos), parent(parent) {} // ...but so much fun...
    };

    coord_t path(const neighborhood_t & moves)
    {
        candidate_t pool[size*size]; // private allocation for express garbage collection...
        size_t alloc;

        candidate_t * border[size*size]; // fixed-size FIFO 
        size_t head, tail;

        std::bitset<size*size>closed;

        // breadth first search. A* would be a huge overkill for 25 cells, and BFS is already slow enough.
        alloc = head = tail = 0;
        closed = 0;
        closed[raw_index(candidate_t(0).pos)] = 1;
        border[tail++] = new (&pool[alloc++]) candidate_t(0);
        while (tail > head)
        {
            candidate_t & candidate = *(border[head++]); // FIFO pop
            for (const coord_t move : moves)
            {
                coord_t new_pos = candidate.pos + move;
                if (is_inside(new_pos))
                {
                    size_t signature = raw_index(new_pos);
                    if (closed[signature]) continue;
                    closed[signature] = 1;
                    if ((*this)(new_pos) > empty) continue;
                    if (new_pos.x == 2) goto found_exit; // a path to some location 2 cells forward
                    assert(alloc < size*size);
                    assert(tail < size*size);
                    border[tail++] = new(&pool[alloc++]) candidate_t(new_pos, &candidate); // allocation & FIFO push
                    continue;
                }
                // a path out of the 5x5 grid, though not 2 cells forward
            found_exit:
                if (candidate.parent == nullptr) return move;
                candidate_t * origin;
                for (origin = &candidate; origin->parent->parent != nullptr; origin = origin->parent) {}
                return origin->pos;
            }
        }

        // no escape
        return moves[1]; // one cell forward, either up or down
    }

    colorType_t & operator() (int x, int y) { return map[raw_index(x, y)]; }
    colorType_t & operator() (coord_t pos) { return operator()(pos.x, pos.y); }
    bool is_inside(coord_t pos) { return is_inside(pos.x, pos.y); }
};

std::string trace_DNA(const dna_t d, bool graphics = false)
{
    std::ostringstream res;
    dnaInfo_t genome(d);
    for (size_t c = 0; c != NUM_COLORS; c++)
    {
        if (graphics)
        {
            res << "tbew--"[genome.color[c].type];
            if (genome.color[c].type == danger) res << ' ' << moves_up[genome.color[c].offset].x << ' ' << moves_up[genome.color[c].offset].y;
            if (genome.color[c].type == beam) res << ' ' << genome.color[c].offset << " 0";
            if (c != NUM_COLORS - 1) res << ',';
        }
        else switch (genome.color[c].type)
        {
        case danger: res << "01234567"[genome.color[c].offset]; break;
        case beam  : res <<     "ABCD"[genome.color[c].offset]; break;
        default: res << "!*-#X@"[genome.color[c].type]; break;
        }
    }
    return res.str();
}

coord_t hardBelievers(dna_t d, view_t v)
{
    dnaInfo_t genome(d); // decoded DNA
    map_t     map;       // the surroundings seen by this particular rodent

    // update genome with local context
    genome.update(map.compute_signatures(v, genome));

    // build a map of the surrounding cells
    map.build(genome);

    // move as far to the right as possible, in the contextually preffered direction
    return map.path(genome.up_down ? moves_up : moves_down);
}

int main() {
    time_t start = time(NULL);
    double score = runsimulation(hardBelievers, trace_DNA);
    slog << "Geometric mean score: " << score << " in " << time(NULL) - start << " seconds";
}

Episode IV: getting our bearings on the grid

Results

Scores: 309371 997080 1488635 1 19 45832 9 94637 2893543 210750 742386 1677242 206614 111809 1 1738598 1 1 342984 2868939 190484 3354458 568267 280796 1 1 1 679704 2858998 1 409584 3823 200724 1 973317 849609 3141119 1 1987305 1 1 57105 245412 1223244 2 1603915 2784761 9 12 1 1839136 1 298951 2 14 138989 501726 1365264 308185 707440 22 772719 17342 63461 3142044 19899 3 409837 48074 3549774 138770 32833 1 1 1184121 67473 310905 1996452 4201 1701954 2799895 2041559 218816 174 433010 51036 1731159 1871641 1 23 2877765 1 127305 27875 626814 142177 2101427 167548 2328741 4 8433 2674119 2990146 466684 1 2 8 83193 388542 2350563 1 1140807 100543 1313548 31949 73117 73300 121364 1899620 1280524 1 10726 12852 7 2165 1 3 44728 2 122725 41 2 1902290 3 1 8581 70598 1148129 429767 1 112335 1931563 521942 3513722 1 2400069 1 3331469 141319 220942 205616 57033 63515 34 6 1419147 1983123 1057929 1 599948 2730727 2438494 5586 268312 1728955 1183258 95241 1537803 11 13 1157309 1750630 1 1 2690947 101211 3463501 1 258589 101615 212924 137664 19624 251591 509429 510302 1878788 1 4045925 1 21598 459159 118663 7 3606309 3 13016 17765 640403 1 72841 695439 1 135297 2380810 1 43 31516 14 1442940 1001957 95903 194951 1 238773 773431 1 1 975692 2 4990979 52016 3261784 2 413095 12 3 420624 7905 60087 760051 2702333 2572405 1 1717432 1 12 3040935 1 1 31787 60114 513777 1 3270813 9639 581868 127091 270 164228 274393 1275008 261419 597715 138913 28923 13059 1848733 2895136 7754 14 1 107592 1 3557771 2067538 147790 112677 119004 1 13791082842974 249727 838699 4067558 6 470799 695141 1 3 1 1276069 23691 831013 5 165142 1236901 1 187522 2599203 1 67179 81345 44111 2909946 94752 7 406018 991024 4 1 3 573689 6 748463 2166290 33865 670769 322844 5657 1131171 1990155 5 4536811 1785704 3226501 2030929 25987 3055355 192547 1761201 433330 27235 2 312244 13203 756723 81459 12 1 1 54142 307858 2 25657 30507 1920292 3945574 1 191775 3748702 3348794 4188197 366019 1540980 3638591 1 1840852 1 26151 2888481 112861 8 11 2 1 27231 1 74 106853 3 173389 2390495 25 1 83116 3238625 75443 1 1 2125260 1 49626 1 6 312084 159735 358268 54351 367201 2868856 5779 172554 119016 141728 3 1 6 9 1 1504011 1 168968 1868493 1 5 1 244563 2 2887999 3144375 1598674 1 1578910 45313 176469 30969 8 127652 1911075 9 1300092 224328 168752 8 1619669 292559 9090 2040459 705819 1852774 10 139217 16 1221670 355060 339599 3 2184244 2546028 1 1 11 70958 242187 1 80737 1 190246 3 1 1 577711 150064 1 1047154 3851461 92399 224270 612237 1 3 3330053 1 1 1192533 615756 267923 144724 2 1 150018 4621881 1 6 299247 115996 2 10 6 185495 76351 465554 178786 1802565 257101 56 2491615 1 24547 1 1203267 32 5741149 541203 11393 1 368082 540534 16167 113481 2004136 13045 17 1 12 333803 14 1955075 1 4 38034 1286203 2382725 26777 1 180312 1 87161 4773392 1244024 1146401 3 80598 2983715 1 63741 1 1 2561436 16 1 1 1807854 1239680 200398 2 46153 1400933 11 5058787 8787 1 98841 89162 1106459 112566 1 4138891 2858906 101835 81375 539485 6587808 1 5359988 1 1 869106 443452 120748 436156 2 2 3944932 1 1875599 2 3081185 733911 447824 1 1 23187 3082414 33 3 1 1 2053904 410824 104571 885952 1946162 2 294773 364169 1 101310 2166548 1177524 2192461 12 4 3457016 90975 2356374 573234 53746 187527 7837 1441335 458407 52139 3387239 2030900 38 1648216 215105 212589 8278 1201586 244282 1 1 1897515 3957343 46 1 134481 1 1 2041785 3 1 37593 163173 1565457 3 1026885 1 34530 4655639 2 18 1940645 1550444 593209 1 2270700 706918 1 1 610113 9 1287883 3 1472134 1998685 1916822 1 296017 2 1 1737607 4155665 1510560 553342 56130 14436 13240604 4025888 1 4253261 174177 2043316 504151 2370989 420666 155232 1 219327 3752236 130062 571247 24 1 29015 31392 1020196 3 1117502 460873 7 1 228 8 133656 1 147008 1 93471 1 1 1 513410 4834094 1 14 1875636 182714 1504903 95263 4418053 1 357853 1135536 3698641 3 239316 4237884 131730 3878724 2158931 55650 1906785 1 26372 32 99217 1645677 379838 1 450352 7329657 112909 1 897980 2114198 308917 126215 1 53839 539997 238036 2 2270000 5 2388928 1668820 519153 58227 347528 1 1 2339954 10 5 2031341 54 2341529 2189774 112731 1 21918 748662 2068921 2 2232504 2923457 97740 3858 16604 398940 388755 1875003 667810 53633 315866 839868 1 7 1 14238 185 4 14 1 2 178947 1965719 398323 120849 48 1397222 961772 34124 2 160652 1 252629 246554 14529 1 299866 135255 490837 2863773 8 10 2 1906405 57 9782 118940 870003 255097 6 4187677 50965 3354376 17611 1804789 183601 158748 1539773 116107 77684 34738 2862836 1 2081903 727739 50328 2740070 17 923524 18 3089706 3144082 1 20 205247 347420 2076952 3725220 39270 2 15 49329 422629 5 1693818 2570558 2146654 1 5 129085 653766 47438 102243 389910 59715 21769 1246783 361571 4 120502 255235 1314165 3 3 5 2902624 76351 3117137 174413 2546645 14534 166054 1013583 1 1 2 9 3027288 3173742 338261 94929 1071263 4659804 1 506576 42798 4 984508 1 4 4 1 18541 7 1 269761 188905 2 1 92011 147031 677955 27484 1291675 2420682 99970 57943 1 4081062 1 250953 704904 4 349180 4273479 30528 2092508 2352781 3700946 1 77799 328993 3684623 3930179 1250080 1975798 54981 1621677 91664 1355832 1084049 721612 56950 197563 246868 5031 1 924076 1328694 58562 1 457662 2445958 1345169 957845 1056809 2485300 1687907 199029 3 9474 86928 1 2419980 3585265 570673 1 1514184 437383 1596697 29709 199606 126031 2 1541777 1 3 2090249 2402438 15 19 1423959 28 37852 4 1652596 1 405512 52 3 1948029 1 2 376 1155902 3 631665 3741991 57673 284026 424787 1 11569 5 1200313 1 20 2360854 1 119994 3889143 673424 797763 1 1 144306 1007659 1231874 75607 1 15 66187 8763 21366 146277 2684501 4458542 162223 3 1 5 94232 3036009 401312 19775 510737 3305062 58905 125783 274094 3089988 118483 1 106213 1 1289180 127905 30 528859 2 1215596 1955900 30 2236528 218643 1 2396631 1598175 1148688 452064 1 1840394 198540 1 1307187 107463 341396 2684981 9602 536871 1 148107 4068 4918434 1 2430254 2066144 88915 3585780 6464 259394 3098337 49601 42 79205 925658 1 2513666 26817 2738302 1 28 345735 5086930 361294 505662 386194 1103890 2653001 412247 4074274 2217918 1 519433 1338570 4289317 140138 18 2519983 168656 4546204 8 1 76545 511580 979214 9318 210013 50508 40 152908 17969 922507 1 7 32 1 388579 1 49886 13319 1066048 4663 27883 38419 1418098 2538216 1 778734 3556791 490764 666880 22746 5666164 4 20 1806284 21142 1 527906 2 12417 182224 49536 105029 206917 2427623 294247 1405136 321480 354137 84225 50 128073 1391176 352835 26074 91159 34229 237942 1 1519676 1 2428669 272681 148689 528951 560736 1 3548197 3833513 1438699 286613 1 1290904 47145 3456135 249648 277045 1012397 271073 1 6 149276 94843 11 177134 32336 2772732 7 22 37065 1 105299 76735 44 2211334 511942 30639 522056 5162 1899842 74 1 1448039 1 88817 21 1027532 555416 1 364383 1335609 167332 283252 49564 220972 1006800 3108886 801258 265596 61651 1 2413276 252747 416606 960925 54 311956 267135 3871698 22581 8978 2 10 1966155 3123429 28 46409 1 18433963725323 1769396 114766 49071 1 1 4228762 3483932 1139490 602592 2700468 770273 3 1 1 212087 281247 27093 156094 286299 1204001 18374 1 330780 1 1 25384 906728 99334 1250819 2161201 34 1027892 1 33449 2 129787 52246 94872 1536841 23470 1 1700323 1 1 3785351 1 95315 1014155 56570 22586 66842 7 156840 48752 1 3143722 1 1168309 2 4 101423 385892 42868 2893851 7 1783109 217499 24 460497 2003214 180135 3503010 131137 2 5240 1621601 2754811 11198 1 1 1105643 1 1671021 3 139611 18268 107229 44582 2211034 1 2880152747163 231008 262504 1 257760 1 1 52992 804418 2 2 4811272 1772250 3 1796530 1918647 1 1934549 1 100550 3448657 1681262 3 604526 320865 1901079 556908 2794800 2472000 637735 123663 1 3213187 118199 2553610 1 1750628 2563806 1 1670872 1 999609 50200 654831 1 164612 2865759 1841739 9 3744159 1331395 3202501 1 7 1 1 239868 1 1 581984 112413 401 1 29656 359367 74532 27226 51752 2583 1 645443 1559731 1 114195 1 85473 229474 111353 1 1521653 1 2568733 444398 2593568 18546 1 158085 1211147 1020006 23407 42514941388799 158442 1 1660358 5 34874 1594789 1551270 386464 502417 32280 170606 1954278 72486 3406066 11 52896 345631 4010742 33307 1951926 1441325 1886066 1 3 402778 3089364 351 28028 4301364 1 431569 5 3054030 375986 404966 1 449317 1230292 1 7 763949 1 2 3197443 1537806 335317 2 1 161263 1 1959902 1664530 139136 447570 1 1 50 158825 222939 1842131 11252 1680094 1017889 71 144808 1 53679 1 41278 1226724 1 1 2 10 2 1 112451 42133 1406662 1 112593 2 2832116 1544488 3579017 3029492 2752014 6 255091 731329 540861 1 426725 440330 212602 202358 173553 4 1189793 11031 84073 2084554 3963 1473295 1 642570 1 1423688 34509 75056 163273 490193 3200250 451777 157797 4156542 2386299 2794795 2735308 1332758 1193296 1131014 1001570 414257 4415511 4 3 1 3499595 536583 16731 93839 92382 1 45890 1 17695 8 867246 18 1607123 3197052 5 40009 1 329895 3497309 2416600 2316390 11 118179 2166659 2 136426 76762 2 14 2 3632525 214889 6 3900942 270409 230143 120414 417489 16706 1563597 31418 2 73 468763 88585 428274 3537347 2 1 491461 2806485 1 7 2950804 115684 4 1 429002 85771 2480 285541 186486 1 1 2430862 6 9 4 1833423 17143 353689 2568741 408890 2929237 208679 2198380 1 2501053 1933666 180843 1 1 2569886 1 17035 3449472 71357 246257 217898 1 47601 589824 401679 362878 13178 34464 1076419 1 554417 1 21248 2136449 1068 23029 8 766649 4 302879 274751 19 1 390259 1899931 233910 1392272 184492 2 2752059 55813 1 6 64674 205205 595508 1714309 582492 4821971 63973 1708726 189200 4548446 479425 2866037 1 1 1 2139319 1 1 3 1572621 2086152 2341038 1 619612 1 78942 772466 18932 1404368 936790 2263929 230200 3009227 251065 835010 88225 642856 824193 5559048 1 36348 2338046 481447 108132 2728223 3539009 1 197164 181408 171634 2172263 2317332 1598340 1318829 1746303 7 59657 1 1415452 122924 915828 1063890 40339 430186 4 2165185 2250922 704568 85138 4417453 255 326360 33541 3 49759 72127 912537 599665 1 29169 168741 349838 996835 1548193 2 28449 803521 4 2 2 3359043 3243259 1 491574 1675000 186105 3203018 11 39127 959876 334480 873131 70262 137080 1076591 1 2155613 74804 893022 2473922 1 1 269835 5 2407308 3 55200 905207 1 1 1245609 65934 7 1372126 530582 1383562 1 1 2718341 1 3947638 4 76837 412551 11 1 1 1208080 3024670 277 46485 1 9 562183 46 2985858 3379885 67816 1896527 1 105478 2035453 3026415 1 189256 2992616 2098002 1099666 775250 5913 13 406948 166773 1 322250 41919 480047 64950 17435 2147428 2336270 3330243 352709 86029 1398723 106236 312951 1 408211 252689 847088 2 17 34088 13128 187366 2 1559482 2349010 1651122 2371088 401005 1715445 1 29483921 1464444 50228 2365851 1651636 768715 226704 23677 83501 1 252623 444628 34 3640316 3602127 45369 1 1 1978261 1 3019189 1 25411 2177552 192839 191146 293712 3840622 182598 4069200 175757 1 2250458 4 1 7 2740824 2753005 1 2836428 1 12 19 2 1788326 3302198122211 3386546 1176663 20847 28 1194294 794665 2630378 13624 722012 2273872 1549353 1 3 1735700 1668388 416 970581 258382 295427 1 121571 3193610 3764806 1 368985 20436 89411 3 16130 2 241879 1 2996216 136958 2382095 510146 1762872 1372194 4215387 346915 4423 1 904153 2004500 248495 836598 3529163 27 2547535 1424181 1885308 1 1056747 289743 176929 2299073 170473 1 1 839941 12382 51457 608526 1684239 4843522 34550 929855 2767014 2979286 1 340808 184830 131077 57298 63854 381689 201998 1715328 118687 69190 123466 1 2 69392 159797 382756 1513430 2506318 457 1
Geometric mean score: 10983.8 in 31214 seconds

I switched to g++/MinGW and 3 threads.
The code generated by GNU is more than twice as fast as Microsoft's.
No wonder, what with their appalling STL implementation.

Teleporters

Teleporter effect is highly position-dependent. Until now I was happy to consider a teleporter either as always good (seen as an empty space) or always bad (seen as a wall so that no rodent would ever take it).

This is too coarse a model.
A given teleporter can propell a rat forward until a few cells from the goal, but once there the same teleporter can cast the rat off the board.
Such a teleporter will very likely be recognized as passable (since it increases fitness faster than when "walking" to the same x location), become part of the dominant genome and kill nearly all rats that trust it as "always safe".
Since the rats have no means of knowing their X position, the only solution to detect these treacherous teleporters is to decide whether to step on them based on the only contextual data available, i.e. the 5x5 color grid.

To do so, I defined 4 types of color genes:

• danger trap detector
• empty passable anywhere on the track
• block forbidden anywhere on the track
• beam seen as empty or block depending on the surroundings

The idea is to try to distinguish a teleporter by looking at its immediate 8 neighbours. Since the probability of having 8 identical neighbours at a given location is very low, that should allow to identify a unique instance of each teleporter.

The 8 neighbouring colors can be combined to form a local signature, which is invariant respective to the position in the labyrinth. Unfortunately, the 8 neighbours are only visible for cells located within the 3x3 field of vision inner square, so signatures will be inaccurate on the rim of the field of vision.
Nevertheless, this will give us a constant contextual information in the immediate neighbourhood, which is enough to increase probability of navigating teleporters successfully.

beam genes have a 2 bits variable field.
For a given teleporter local signature, there is one chance in four that the beam cell will be considered impassable. Each value of the field selects one of these four possibilities.
As a result, a beam gene mutation on these 2 bits will cycle through 4 possible contextual significations of the color.

Besides, the most important colors to guess are still walls and traps. This means we should allow teleporter detection only after the rats learned where the walls and traps are.

This is done by updating the local signatures only sparringly. The current criterion for updating a local signature is to be in the vincinity of a color identified as a potential teleporter.

The coding uses 5 bits per color gene and groups types to free the 3 less significant bits to encode a 0..7 value :

• 4 danger
• 4 empty
• 4 block
• 4 beam

Each beam gene has 1/4 chance of being considered as a block and 3/4 chances to be considered empty, so 4 beams represent in average 1 block and 3 empty.

The average proportion represented by a random spread of 16 colors is thus:

• 4 danger
• 7 empty
• 5 block

This mix seems to give the best results so far, but I am not done tweaking it.

Gene mutability

One thing is for certain: the code values chosen to represent gene types are critical. Inverting two values can cost 2000 points or more.

Here again the reason why is beyond my maths.

My guess is that the probabilities of mutation from one type to another must be balanced, or else, like in a Markow matrix, the cumulative probabilities tend to restrict the values to the subset having the highest incoming transition probabilities.

Pathing to the rescue

Pathing will reduce the number of visited cells dramatically, allowing to test only the most likely to lead to the goal. Thus, not only are some frequent dead ends avoided, but wrong color codes are also much more likely to be discovered earlier on.
As a result, convergence time is strongly decreased.

However, this does not help solving the maps where the genome is unable to produce a proper representation of the track.

What to do with morons?

After looking visually at the track, I understood why a default strategy that tries to move forward even when there seem to be nothing but walls in front is indeed better than holding back.
"walls" can be in reality teleporters that produce so many unfortunate results that the genome maps them as obstacles never to be trod on, but on rare occasions a particular instance of this naughty teleporter can have a positive (or at least non lethal) effect, so taking it instead of moving back increases the chances of finding a path to victory.

Early convergence

It seems to me the mutation rate is a tad bit too low (for my rodents at least).

The current 0.01 setting gives a DNA 37% chances to survive the mutation process intact. Changing the parameter to 0.0227 lowers this probability to about 10%

The mysterious formula is P_{1 bit mutation} = 1-P_{whole genome intact}^1/100, 100 being the genome bit length.

For instance for 10% probability, P_{1 bit mutation} = 1 - 0.1^1/100 = 0.0277
For 5% probability, P = 1 - 0.05^1/100 = 0.0295
Inverting the formula, we find that 0.01 gives a 37% chances of being unchanged by mutation.

I re-ran the exact same test (using a fixed sequence of random seeds) with a 10% probability.
On a lot of maps, the previous failures turned into (limited) successes. On the other hand, enormous population explosions were fewer (which had the interesting side effect of speeding up computation a lot).
Even though the very high scores (one million+) were less common, the number of more successful runs was more than enough to compensate.
In the end, the mean rose from 1400+ to about 2000.

Setting P to 5%, on the contrary, produced a mean of about 600.
I assume the mutation rate was so high that the genome of winning rats devolved too often into less efficient variants.

How this one works

With the added teleporter detectors, the number of failed games (score < 10) dropped significantly.
On a 2000 runs trial, there was only 1/3 of failures.
The geometric mean only rose from 2900 to 3300, but this number fails to reflect the improvement.

Empty colors are frequently guessed as beams and dangers (usually 2 to 5). The genome "uses" these colors to block paths that would get rats into trouble.

The genome is pretty good at guessing traps (i.e. once rats become able to reach the goal, colors that represent actual trap detectors are guessed about 90% of the time).
It also makes use of the new beam codes for teleporters, though more rarely (probably because the "treacherous" teleporters are less common than traps, and other beam/danger colors evolve to block the path to the last instances of these traitors).

Judging by the number of games where a winning genome emerges after 5000 turns or more, I reckon this new breed would benefit greatly from an increased mutation rate.

Answer 3

ColorScorePlayer, preliminary score ≈ 22

This is the bot you see at work in the GIF in the challenge.

This was our test bot throughout the development phase. It uses the genome to store a quality score for each of the 16 colours. Then it makes the forward move that moves it onto the colour with the best score (and never moves onto -1). In case of a tie, a random move between the tying cells is picked.

We've ported this player into all controller languages, so it acts as example for how to use them:

Python

class ColorScorePlayer(Player):
    def __init__(self):
        Player.__init__(self)
        self.coords = [Coordinate( 1, 0),
                       Coordinate( 1,-1),
                       Coordinate( 1, 1)]
        self.n_moves = len(self.coords)

    def turn(self):
        max_score = max([self.bit_chunk(6*self.vision_at(c.x, c.y), 6) for c in self.coords if self.vision_at(c.x, c.y)>=0])
        restricted_coords = [c for c in self.coords if self.vision_at(c.x, c.y)>=0 and self.bit_chunk(6*self.vision_at(c.x,c.y), 6) == max_score]

        return random.choice(restricted_coords)

Ruby

class ColorScorePlayer < Player
    def initialize(rng)
        super(rng)
        @coords = [Vector2D.new( 1,-1),
                   Vector2D.new( 1, 0),
                   Vector2D.new( 1, 1)]
    end

    def vision_at(vec2d)
        @vision[vec2d.x+2][vec2d.y+2]
    end

    def turn
        max_score = @coords.map { |c|
            color = vision_at(c)
            color < 0 ? -1 : bit_chunk(6*color, 6)
        }.max

        restricted_coords = @coords.select { |c|
            color = vision_at(c)
            color >= 0 && bit_chunk(6*color, 6) == max_score
        }

        restricted_coords.sample(random: @rng)
    end
end

C++

coord_t colorScorePlayer(dna_t d, view_t v) {
    const int chunklen = DNA_BITS / N_COLORS;
    int ymax[3], nmax, smax = -1;
    for(int y = -1; y <= 1; y++) {
        if(v(1, y) == OUT_OF_BOUNDS) continue;
        int score = dnarange(d, v(1, y)*chunklen, chunklen);
        if(score > smax) {
            smax = score;
            nmax = 0;
        }
        if(score == smax) ymax[nmax++] = y;
    }
    return {1, ymax[v.rng.rint(nmax)]};
}

C#

public static void ColorScorePlayer(GameLogic.IView v, GameLogic.IGenome g, Random rnd, out int ox, out int oy)
{
    ox = 0;
    oy = 0;

    var max_score = cspcoords.Where(c => v[c.x, c.y] > -1).Select(c => g.cutOutInt(6 * v[c.x, c.y], 6)).Max();
    var restrictedCoords = cspcoords.Where(c => v[c.x, c.y] > -1 && g.cutOutInt(6 * v[c.x, c.y], 6) == max_score).ToArray();

    Coord res = restrictedCoords[rnd.Next(restrictedCoords.Length)];

    ox = res.x;
    oy = res.y; 
}

Java

package game.players;

import java.awt.*;
import java.util.Map;

public class ColorScorePlayer extends Player{
    private static final Point[] possibleMoves = {new Point(1, 0), new Point(1, -1), new Point(1, 1)};

    @Override
    public Point takeTurn(String genome, Map<Point, Integer> vision) {
        int chunkLength = genome.length()/16;
        int maxSum = -1;
        Point maxSumMove = possibleMoves[0];
        for (Point move: possibleMoves){
            if (vision.get(move) == -1){
                continue;
            }
            int initialPoint = chunkLength*vision.get(move);
            int sum = 0;
            for (int i = initialPoint; i < initialPoint + chunkLength; i++){
                sum = (sum<<1)+Integer.parseInt(genome.charAt(i)+"");
            }
            if (sum > maxSum){
                maxSum = sum;
                maxSumMove = move;
            }
        }
        return maxSumMove;
    }
}

The player scores fairly inconsistently. Here are 50 random runs:

Scores: 1 1 1132581 3 43542 1 15 67 57 1 11 8 623162 1 1 1 134347 93198 6 1 2 1 1 245 3 1 1 27 1 31495 65897 9 5 1 2 20 2 117715 1 1 1 20 64616 5 38 1 2 1 2 12

Answer 4

ColorFarSeeker, C++ ≈ 74.7

This challenge is really quite fun and simple if you try it.

Don't get put off by the long description.
Just visit the GitHub and check things out... everything will be much clearer! :)

The C++ simulator is highly recommended for its speed. Even after I've finished translating my python program to C++, the python simulation still hasn't stopped.

This is an improved variant of the ColorScorePlayer. To make good use of its 5x5 view, it considers moves 2 steps from it using a weighted function. Moves 1 steps ahead of it are given a higher weight, as they have more immediate effect on survival. Move 2 steps ahead are given lower weight.

Tries to move forward, but if no safe move seen... then tries sideways... and if all else fails, moves backwards randomly.

coord_t colorFarSeeker(dna_t d, view_t v) {
#define s(w,x,y) (v(x,y)>-1?((b+dnarange(d,l+m+n*v(x,y),n))*w):0)
#define max2(a,b) (((a)>(b))?(a):(b))
#define max3(a,b,c) (max2(a,max2(b,c)))
#define push(vec,maxScore,score,x,y) if(score==maxScore&&v(x,y)>-1)vec.push_back({x,y});
#define tryReturn() if(vec.size()){return vec[v.rng.rint((int)vec.size())];}vec.clear();

    // Some constants to tweak
    int k = 4;
    int l = 3;
    int m = dnarange(d, 0, l);
    int n = 4;
    int b = dnarange(d, l, k) + 10;

    std::vector<coord_t> vec;

    // Looks forward for good moves...
    int upRightScore = s(1,0,-2) + s(1,1,-2) + s(1,2,-2) + s(5,1,-1);
    int forwardScore = s(1,2,-1) + s(1,2,0) + s(1,2,1) + s(5,1,0);
    int downRightScore = s(1,0,2) + s(1,1,2) + s(1,2,2) + s(5,1,1);
    int maxForwardScore = max3(upRightScore,forwardScore,downRightScore);
    push(vec,maxForwardScore,upRightScore,1,-1);
    push(vec,maxForwardScore,forwardScore,1,0);
    push(vec,maxForwardScore,downRightScore,1,1);
    tryReturn();

    // Looks sideways for good moves...
    int upScore = s(1,-1,-2) + s(1,0,-2) + s(1,1,-2) + s(5,0,-1);
    int downScore = s(1,-1,2) + s(1,0,2) + s(1,1,2) + s(5,0,1);
    int maxSideScore = max2(upScore,downScore);
    push(vec,maxSideScore,upScore,0,-1);
    push(vec,maxSideScore,downScore,0,1);
    tryReturn();

    // If all else fails, move backwards randomly.
    // I have tried considering the scores of backmoves,
    // but it seems worse than just randomly moving backwards. 
    vec.push_back({-1,-1});
    vec.push_back({-1,0});
    vec.push_back({-1,1});
    return vec[v.rng.rint((int)vec.size())];

}

Score:

There are quite a bit of 1's... which can be a tad depressing when you see the console spewing 1 after each other. Like a planet with all the necessities for life, but no signs of advanced rat civilizations...
Then the occasional spike. :)

Hmm... apparently I was lucky for my 1st batch of runs, getting a geometric of 300+. The scores really do fluctuate quite a bit. But anyway, with more runs of the simulator, it's probably closer to ≈ 74. (Thx feersum for helping me simulate and his blazing fast program)

Scores from my runs: 6 6 53 1 5 101223 89684 17 2 303418 4 85730 24752 1 1 1 3482515 39752 1 59259 47530 13 554321 1 563794 1 1770329 1 57376 1 123870 4 1 1 79092 69931 594057 1 69664 59 1 6 37857 1733138 55616 2 1 51704 1 254006 4 24749 1 117987 49591 220151 26 4292194 23 57616 72 67 1 4 308039 1 1 103 89258 1 286032 1 5 3 1 5 114851 46 143712 5 15 9 80 7425 1 1 7 1 108379 70122 97238 1 1 5 2 23 104794 1 10476 59245 1 204 1 1 12 1 29641 1 314894 18785 13 1 3 1 1 1 2 526001 1 1 1 27559 29285 3 3 128708 70386 30 2 2 1 208531 331 1 2 1 61 114993 1 15 51997 1 2 1 146191 1 31 4 3 1 161422 207 1 64 1 1 1 68594 145434 87763 150187 169 185518 1 1 1 1 24208 2570 1 1 537 1 1 462284 1 2 55 1 1 1 214365 1 40147 2 213952 1 29 3 1 2144435 5 4502444 72111 1 1 1 1 1 774547

Answer 5

Bishop - Python, preliminary score 1.901

The Bishop always moves diagonally so half the board is inaccessible on a given trek across the board, but this does mean fewer potential moves to encode, so each individual bit of the genome can represent a move (the Bishop never retreats). Which bit to refer to is decided based on the 3x3 block of squares ahead (to the right) of the specimen. The best move for a given situation is only ever a single bit mutation away.

This bot learns quickly at first, but then often hits a ceiling before reaching the finish, presumably where one of the following two problems occurs:

• Two or more parts of the board map to the same bit but require different moves.
• Some boards are not passable using only diagonal moves.

Code

class BishopPlayer(Player):
    def __init__(self):
        Player.__init__(self)
        self.coords = [Coordinate(1,-1),
                       Coordinate(1, 1),
                       ]
        self.inputs = [(x,y) for x in (0,1,2) for y in (-1,0,1)]

    def turn(self):
        # Move away from out of bounds areas
        if self.vision_at(0,-1) == -1:
            return self.coords[1]
        if self.vision_at(0,1) == -1:
            return self.coords[0]

        # Move right, and either up or down based on one bit of the genome
        bit_to_use = sum(self.vision_at(self.inputs[i][0],
                                        self.inputs[i][1]
                                        ) * (16 ** i) for i in range(9)
                         ) % 100
        return self.coords[self.bit_at(bit_to_use)]

Despite these limitations, on rare occasions the Bishop does well, with individual specimens completing several laps of the board each. I had thought that on a given lap a specimen can only move on half of the board (equivalent to only the black squares or only the white squares on a chess board). However, as Martin Büttner pointed out, a teleporter can move a specimen from a black square to a white square or vice versa so on most boards they will not be restricted.

(There are two pairs of matched teleporter types and each has a probability of 0.5 of having an offset that moves a specimen into the other half of the black and white squares. So the probability of a board having only teleporters that restrict the specimen to one half of the board per lap is only 0.25.)

The scores show that the occasional triumphs are interspersed with long periods of falling short of the finish:

Scores: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 2 1 1 1 1 1 6 1 8 1 10 15 1 1 12544 1 2 1 1 1 1 3 7554 1 1 1 1 1

Answer 6

Run-bonus player: Geometric mean 50.35 (5000-game test)

This bot scores squares by their individual colors based on a 6-bit section of DNA like the color-score player, but with a different number system. This bot was motivated by the thought that it is rather arbitrary that one of the bits changes the value of the score by 32, while another does so by only 1. It assigns the value n(n+1)/2 to a run of n consecutive 1 bits. Additionally, it adds a randomization mechanism in an attempt to avoid getting stuck. It will make a random forward move with a 1 in 30 chance.

For comparison, the color-score player scored 30 to 35 in a couple of 1000-game tests. Interestingly, the color-score player's maximum game score was in the 3-5 million range, while run-bonus' maximum was only 200 thousand. Run-bonus benefits from the logarithmic average scoring system by getting a nonzero score more consistently.

Running 5000 games took about 20 minutes with 6 threads on the C++ controller.

coord_t runbonus(dna_t d, view_t v) {
    int ymax[3], nmax, smax = -1;
    if(!v.rng.rint(30)) {
        int y;
        while(!~v(1, y = v.rng.rint(-1, 1)));
        return {1, y};
    }
    for(int y = -1; y <= 1; y++) {
        if(v(1, y) == OUT_OF_BOUNDS) continue;
        int score = 0;
        int streak = 0;
        for(int i = 0; i < 6; i++) {
            if(d[6*v(1,y) + i])
                score += ++streak;
            else
                streak = 0;
        }
        if(score > smax) {
            smax = score;
            nmax = 0;
        }
        if(score == smax) ymax[nmax++] = y;
    }
    return {1, ymax[v.rng.rint(nmax)]};
}

Answer 7

StarPlayer | C++ | Score: 162 (based on 500 game run)

This player tries to use A* to find the best way forward. It assigns weights the same way as ColorScorePlayer and tries to pathfind it's way to the right edge of the view. The implementation isn't the prettiest I've ever done but it isn't too slow at least.

#include <utility>

#define IDX(a,b) a[VIEW_DIST + b.x][VIEW_DIST + b.y]

std::pair<coord_t,int> planAhead(int weights[N_COLORS], view_t &v, coord_t target) {
    bool open[VIEW_DIST*2+1][VIEW_DIST*2+1] = {false};
    bool closed[VIEW_DIST*2+1][VIEW_DIST*2+1] = {false};
    int f_score[VIEW_DIST*2+1][VIEW_DIST*2+1] = {0};
    int g_score[VIEW_DIST*2+1][VIEW_DIST*2+1] = {0};
    coord_t came_from[VIEW_DIST*2+1][VIEW_DIST*2+1] = {{0,0}};
    open[VIEW_DIST][VIEW_DIST] = true;
    g_score[VIEW_DIST][VIEW_DIST] = v.rng.rint(5);
    f_score[VIEW_DIST][VIEW_DIST] = (abs(target.x) + abs(target.y)) * 10;
    for (;;) {
        coord_t current{VIEW_DIST+1,0};
        for (int x = 0; x < (VIEW_DIST*2+1); x++)
            for (int y = 0; y < (VIEW_DIST*2+1); y++)
                if (open[x][y] && (current.x > VIEW_DIST || f_score[x][y] < IDX(f_score,current)))
                    current = {x - VIEW_DIST, y - VIEW_DIST};
        if (current.x > VIEW_DIST)
            return {{1,0}, 1000000};
        if (current.x == target.x && current.y == target.y)
            break;
        IDX(open,current) = false;
        IDX(closed,current) = true;
        for (int dx = -1; dx <= 1; dx++) for (int dy = -1; dy <= 1; dy++) {
            if (dx == 0 && dy == 0)
                continue;
            coord_t tentative{current.x + dx, current.y + dy};
            if (abs(tentative.x) > VIEW_DIST || abs(tentative.y) > VIEW_DIST)
                continue;
            if (IDX(closed,tentative))
                continue;
            auto color = v(tentative.x, tentative.y);
            if (color == OUT_OF_BOUNDS)
                continue;
            auto tentative_g = IDX(g_score,current) + weights[color];
            if (!IDX(open,tentative) || tentative_g < IDX(g_score,tentative)) {
                IDX(came_from,tentative) = current;
                auto distance = abs(tentative.x - target.x) + abs(tentative.y - target.y);
                IDX(f_score,tentative) = tentative_g + distance * 10;
                IDX(g_score,tentative) = tentative_g;
                IDX(open,tentative) = true;
            }
        }
    }
    auto prev = target, current = target;
    while (current.x != 0 || current.y != 0)
        prev = current, current = IDX(came_from,current);
    return {prev, IDX(g_score,target)};
}

coord_t starPlayer(dna_t d, view_t v) {
    const int chunklen = DNA_BITS / N_COLORS;
    int weights[N_COLORS];
    for (int i = 0; i < N_COLORS; i++)
        weights[i] = dnarange(d, i*chunklen, chunklen);
    std::pair<coord_t,int> choice{{1,0}, 1000000};
    for (int y = -VIEW_DIST; y <= VIEW_DIST; y++) {
        auto plan = planAhead(weights, v, {VIEW_DIST, y});
        if (plan.second < choice.second)
            choice = plan;
    }
    return choice.first;
}

Sample scores:

4 92078 1 10 1 1 3 2 2862314 5 24925 1 3 2 126502 1 24 1097182 39 1 1 1 47728 227625 137944 15 1 30061 1 1 1 3171790 19646 10 345866 1 1 1 829756 425 6699 22 8 1 1 6 6 104889 125608 1

Answer 8

The FITTEST - Geometric mean score: ~ 922 (2K runs)

My approach is to:

1. Find out what kills the species and define desired behaviour (functional)
2. Implement desired behaviour in code (technical)
3. Give it a priority. Is it more important or less important than other desired behaviour.
4. Optimize the Geometric mean score by tweaking parameters of the solutions.

I tested over 2000 sets of parameters with the same 50 seeds. The most promising sets were selected and were scored using 250 identical seeds and the ones with the highest rank were the input for the next round of test. So I managed to create a genetic algorithm to find the optimal genetic algorithm for this problem as suggested by user mbomb007.

The desired behaviour:

1. The species should learn which colours are safe and which are bad.
2. The species should mainly focus its decision where to move to based on the 3 cells right in front, but if no good moves are available, vertical or backward moves should be considered
3. The species should also look what is beyond the 8 cells around him and use that in information in decision making
4. The species should learn to identify traps.
5. Some species incorrectly assume that walls are good and try to move to them all the time and therefore get stuck in front of walls. If they are the species with the highest fittest score at that moment their DNA with the wrong assumption about the wall is duplicated many times into newborns. After some time all species are stuck in front of walls and none of them reaches the goal to score points. How to stop the morons?

Data storage methods:

We want the species to learn things, to adapt to its environment, to become the fittest. Inevitably this only works, if learning's can be stored somehow. The learning will be 'stored' in the 100 DNA bits. It is a strange way of storing, because we can not change the value of our DNA. So we assume that the DNA already stores information of bad and good moves. If for a certain species the correct information is stored in its DNA he will move fast forward and produce many new species with its DNA.

I found out the geometric mean score is sensitive to how the information is stored. Lets assume we read the first 4 bits of the 100 bits of DNA and want to store this in an integer variable. We can do this in several ways:

1. decimal data storage: by using the 'built-in' dnarange function, example: 4bits 1011 will become `1x2^3 + 0x2^2 + 1x2^1 + 1x2^0 = 15. Possible values (for 4 bits): [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
2. streaks data storage: by using the dnaStreakRange function (defined below), example: 4bits 1011 will become 1x1 + 0x1 + 1x1+ 1x2 = 4. Possible values (for 4 bits): [0, 1, 2, 3, 6, 10]

int dnaStreakRange(dna_t &d, int start, int chunklen) {
    int score = 0;
    int streak = 0;
    for(int i = 0; i < chunklen; i++) {
        if(d[start + i])
            score += ++streak;
        else
            streak = 0;
    };  
    return score;
}

3. bitsum data storage: by using the dnaCountRange function (defined below), example: 4bits 1011 will become 1x1 + 0x1 + 1x1 + 1x1 = 3. Possible values (for 4 bits): [0, 1, 2, 3, 4]

int dnaCountRange(dna_t &d, int start, int chunklen) {
    int score = 0;
    for(int i = 0; i < chunklen; i++) {
        if(d[start + i])
            score ++;
    };  
    return score;
}

Difference between storage methods are:

• The decimal storage method is vulnerable for a single bit change to the DNA. When the bitsum value changes from 1011 to 0011 its value changes from 3 to 2 which is a minor change.
• The decimal storage method is homogeneous. Each of the possible values has the same change to occur. The chance that you read the value of 15 from a 4 bit storage memory block is 1/16=6%. The streak storage method is not homogeneous. The chance that a streak 4 bit value is less or equal that 6 is (15-3)/16=81% (all 16 combinations except 0111,1110,111). Below a visual which shows the shape of the distribution. As you can see at the blue arrow the chance of a 4 bit streak to be less or equal to 6 is 81%:

Prioritize solutions.

When the ColorScorePlayer has identified two forward moves with identical scores an arbitrary choice is made. IMHO, you should never use the random function v.rng.rint() function. Instead you should use this opportunity of equal scores as a hook to evaluate solutions for second order effects.

First order effect get the highest priority. If equal scores are reaches, the solution with the priority 2 prevails and so on. By tweaking the parameters of a solution you can influence the chance that equal scores occur and in that way change weight of priority 1 and priority 2 solutions.

Implementation of desired behaviour

Learn which colours are safe:

• 33% of the 16 colors are bad and therefore when the score of a move is below 63/3 the move will not be allowed. Therefore threshold = 63/3=21, where 63 is the max score for 6 bits and 33%=1/3 (can be looked up in the graph above).

If no good moves are available, move vertical or backward:

• When no forward moves are allowed, vertical moves will be compared with each other in the same way. If also no vertical moves are allowed, the backward moves are ranked. This is achieved via the weightMove variable.

Look what is beyond:

• When 2 or 3 moves have identical scores, the 3x3 box around those moves will determine (via x2 and y2 loops) what is the best option (via the mainSubScore variable). The most right column in that 3x3 box is leading.

coord_t adjustedColorPlayer(dna_t d, view_t v) {
    const int chunklen = 6,threshold = 63/3;
    int xBestScore=0, yBestScore=0;
    long bestScore=-1, weightMove, weightMove2, mainScore;
    for(int x = -1; x <= 1; x++) {
        if (x < 0) weightMove = 1000; // moving backward
        if (x== 0) weightMove = 10000; //moving vertical
        if (x > 0) weightMove = 100000; //moving forward
        for(int y = -1; y <= 1; y++) {
            if(v(x, y) == OUT_OF_BOUNDS || (x==0&&y==0) ) continue;
            mainScore = dnarange(d,v(x,y)*chunklen,chunklen);
            if (mainScore<threshold+1) {
                mainScore =  0; //not a suitable move because too low score
            }else{
                mainScore*= weightMove;
                // when equal score, use sub score by examining 5x5 box to rank moves
                for(int x2 = x-1; x2 <= x+1; x2++){     
                    if (x2 < x) weightMove2 = 1; // moving backward
                    if (x2== x) weightMove2 = 10; //moving vertical
                    if (x2 > x) weightMove2 = 100; //moving forward
                    for(int y2 = x-1; y2 <= y+1; y2++){     
                        if(v(x2, y2) != OUT_OF_BOUNDS){
                            long mainSubScore = dnarange(d,v(x2,y2)*chunklen,chunklen);
                            if (mainSubScore>=threshold+1) mainScore+=mainSubScore*weightMove2;
                        }
                    }
                 }
            }
            if(mainScore > bestScore) {
                bestScore = mainScore;              
                xBestScore = x;
                yBestScore = y;
            }
        }
    }
    return{xBestScore,yBestScore};
}

Score: 123(2K runs)

First 50 Scores (18 games have scored only 1 point):

1 10 1 79947 3 1 11 125 7333287 23701 310869 53744 1 2 2 2 2 1 1 57556 2 688438 60 1 2 2636261 26306 1 125369 1 1 1 61895 27 1 36 1 91100 87636 1 2 47497 53 16 1 11 222384 1 1 1

Identify traps:

I examined the DNA of the species with the highest score when an arbitrary game ended using the a bitsum4 storage (so colour score has range [0,4]):

• scored 0: Teleport backward, both walls, 1x safe
• scored 1: Trap backward (so harmless), Teleport backward, 1x safe
• scored 2: Trap forward (so dangerous), 1x safe
• scored 3: Teleport forward, 5x safe
• scored 4: Teleport forward, 1x safe

From this it can be concluded that walls and teleports get a correct score. Traps are not identified since they are depending on direction and on color of origin, while scoring is done on color of destination. Therefore there is a need for also storing data on the color of origin, so v(0,0). In an ideal world we would like to store information for 16 colors x 8 directions x 3 bits = 384 bits.

Unfortunately, there is only 100 bits available and we can not use it all since we also need some memory for the solution explained above. Therefore we will make 4 colour bins:

• 0: colour 0 - colour 3,
• 1: colour 4 - colour 7,
• 2: colour 8 - colour 11,
• 3: colour 12 - colour 16

and 4 move direction bins

• 0: move vertical or backward,
• 1: move forward up,
• 2: move forward,
• 3: move forward down

When the decimal score is 4 or higher (100,101,110,111), it is assumed a trap is associated with this cell, as a result this move will not be picked when equal scores arise. So trap identification is a second order effect and the 'look what's beyond' will be a third priority solution.

int dnaLookup2(dna_t &d, int start, int chunklen, int storageMethod) {
    // Definition of storageMethod: 0=decimal, 1=streak, 2=bitsum
    int score = 0, streak = 0;
    for(int i = start; i < start+chunklen; i++) {
        int value = d[i];
        if (storageMethod==0) {
            score = (score << 1) |value;
        }else{
            if (storageMethod==1){
                if(value) score += ++streak; else streak = 0;
            }else{
                if(value) score ++;         
            }
        }
    };  
    return score;
}

coord_t theTrapFighter(dna_t d, view_t v) {
    // Definition of storageMethod: 0=decimal, 1=streak, 2=bitsum
    const int colorMemStorageMethod = 1, colorMemBlockSize = 3;
    const int trapMemStorageMethod = 0, trapMemBlockSize = 3;
    const int trapMemTopThreshold = 4, nDirBins = 4, nColorBins = 4;

    int xBestScore=0, yBestScore=0;
    long bestScore=-1, weightMove, weightMove2, mainScore;
  for(int x = -1; x <= 1; x++) {
        if (x < 0) weightMove = 1000; // moving backward
        if (x== 0) weightMove = 10000; //moving vertical
        if (x > 0) weightMove = 100000; //moving forward
        for(int y = -1; y <= 1; y++) {          
            int color = v(x, y);
            if(color == OUT_OF_BOUNDS || (x==0&&y==0) ) continue;
            mainScore = dnaLookup2(d,color*colorMemBlockSize,
             colorMemBlockSize,colorMemStorageMethod);
            if (mainScore==0) {
                //not a suitable move because too low score
            }else{
                mainScore*= weightMove;
                //lookup trap likelihood
                int directionBin = 0;
                if (nDirBins==3) directionBin = x>0?y+1:-1;
                if (nDirBins==4) directionBin = x>0?y+2:0;
                // put 16 colors in nColorBins bins
                int colorBin = v(0,0)*nColorBins/N_COLORS; 
                colorBin = colorBin>(nColorBins-1)?(nColorBins-1):colorBin;
                if (directionBin >= 0 &&
                 dnaLookup2(
                   d,
                   colorMemBlockSize*16
                    +trapMemBlockSize*(nColorBins*directionBin+colorBin),
                   trapMemBlockSize,
                   trapMemStorageMethod
                 ) >=trapMemTopThreshold){
                  //suspect a trap therefore no sub score is added                  
                 }else{
                    // when equal score, use sub score by examining 5x5 box to rank moves
                    for(int x2 = x-1; x2 <= x+1; x2++){     
                        if (x2 < x) weightMove2 = 1; // moving backward
                        if (x2== x) weightMove2 = 10; //moving vertical
                        if (x2 > x) weightMove2 = 100; //moving forward
                        for(int y2 = x-1; y2 <= y+1; y2++){     
                            int color2 = v(x2, y2);
                            if(color2 != OUT_OF_BOUNDS){
                                mainScore+=weightMove2 * dnaLookup2(d,color2*colorMemBlockSize,
                                 colorMemBlockSize,colorMemStorageMethod);
                            }
                        }
                    }               
                 }
            }
            if(mainScore > bestScore) {
                bestScore = mainScore;              
                xBestScore = x;
                yBestScore = y;
            }
        }
    }
    return{xBestScore,yBestScore};
}

Score: 580 (2K runs)

First 50 Scores (13 games have scored only 1 point):

28,044 14,189 1 2,265,670 2,275,942 3 122,769 109,183 401,366 61,643 205,949 47,563 138,680 1 107,199 85,666 31 2 29 1 89,519 22 100,908 14,794 1 3,198,300 21,601 14 3,405,278 1 1 1 2 74,167 1 71,242 97,331 201,080 1 1 102 94,444 2,734 82,948 1 4 19,906 1 1 255,159

Wrong assumption about the wall is duplicated many times into newborns by morons:

Some species incorrectly assume that walls are good and try to move to them all the time and therefore get stuck in front of walls. They can also get stuck in infinite loops of teleporters. The effect is the same in both cases.

The main problem is that after a few hundred iterations some genes get very dominant. If these are the 'right' genes, you can get very high scores (>1 million points). If these are wrong, you are stuck, since you need the diversity to find the 'right' genes.

Morons fighting: Solution 1: colour inversion

The first solution I tried was an effort to utilize a part of unused memory which is still very diverse. Lets assume you have allocated 84 bits to your colour memory and trap finding memory. The remaining 16 bits will be very diverse. We can fill 2 decimal8 variables which have values on the interval [0,255] and they are homogeneous, which means that each value has a chance of 1/256. The variables will be called inInverse and inReverse.

If inInverse equals 255 (a 1/256 chance), then we will inverse the interpretation of the colour scores. So the wall which the moron assume to be safe because of it is high score, will get a low score and therefore will become a bad move. The disadvantage is that this will also effect the 'rights' genes, so we will have less very high scores. Furthermore this inInverse species will have to reproduce itself and its children will also get parts of the dominant DNA. The most important part is that it brings back the diversity.

If inReverse equals 255 (a 1/256 chance), then we will reverse the order of the storage positions of the colour scores. So before colour 0 was stored in bits 0-3. Now colour 15 will be stored in that position. The difference with the inInverse approach is that the inReverse will undo the work done so far. We are back at square one. We have created a species which has similar genes as when the game started (except for the trap finding memory)

Via optimization it is tested if it is wise to use the inInverse and inReverse at the same time. After the optimization it was concluded the score did not increase. The problem is that we have more diverse gen population, but this also affects the 'right DNA'. We need another solution.

Morons fighting: Solution 2: hash code

The species has 15 possible starting position and currently there is a too large chance he will follow exactly the same path if he starts at the same starting position. If he is a moron who loves walls, he will get stuck on the same wall over and over again. If he by luck managed to reach a far ahead wall, he will start to dominate the DNA pool with his wrong assumptions. What we need is that his offspring will follow a slightly different path (since for him it is too late anyway), and will not get stuck on the far ahead wall, but on a more nearby wall. This can be achieved by introducing a hashcode.

A hashcode should have the purpose to uniquely identify and label the current position on the board. The purpose is not to find out what the (x,y) position is, but to answer the questions have my ancestors been before on this location?

Let's assume you would have the complete board in front of you and you would make a jpg of each 5 by 5 cell possible square. You would end up with (53-5)x(15-5)=380 images. Let's give those images numbers from 1 to 380. Our hashcode should be seen as such an ID, with that different that it does not run from 1 to 330, but has missing IDS, so e.g. 563, 3424, 9424, 21245, etc.

unsigned long hashCode=17;
for(int x = -2; x <= 2; x++) {
    for(int y = -2; y <= 2; y++) {
        int color = v(x, y)+2;
        hashCode = hashCode*31+color;
    }
}       

The prime numbers 17 and 31 are in there to prevent the information added in the beginning in the loop to disappear. Later more on how to integrate our hashcode into the rest of the program.

Lets replace the "look what's beyond" subscoring mechanism with another subscoring mechanism. When two or three cells have equal main scores there will be a 50% chance the top one will be picked, a 50% chance that the bottom cells is picked and a 0% chance that the middle one will be picked. The chance will not be determined by the random generator, but by bits from the memory, since in that way we make sure that in the same situation the same choice is made.

In an ideal world (where we have an infinite amount of memory), we would calculate a unique hashcode for our current situation, e.g. 25881, and go to memory location 25881 and read there if we should pick the top or bottom cell (when there is an equal score). In that way we would be in the exact same situation (when we e.g. travel the board for the second time and start at the same position) make the same decisions. Since we do not have infinite memory we will apply a modulo of the size of the available memory to the hashcode. The current hashcode is good in the sense that the distribution after the modulo operation is homogeneous.

When offspring travels the same board with slightly changed DNA he will in most cases (>99%) make exactly the same decision. But the further he comes the larger the chance becomes that his path fill be different from his ancestors. So the chance that he will get stuck on this far ahead wall is small. While getting stuck on the same nearby wall as his ancestor is relatively large, but this is not so bad, since he will not generate much offspring. Without the hashcode approach, the chance of getting stuck on the nearby and far away wall is almost the same

Optimization

After the optimization, it was concluded that the trap identification table is not needed and 2 bits per color is sufficient. The remainder of the memory 100-2x16=68 bits is used to store the hash code. It seems that the hash code mechanism is able to avoid traps.

I have optimized for 15 parameters. This code included the best set of tweaked parameters (so far):

int dnaLookup(dna_t &d, int start, int chunklen, int storageMethod,int inInverse) {
    // Definition of storageMethod: 0=decimal, 1=streak, 2=bitsum
    int score = 0;
    int streak = 0;
    for(int i = start; i < start+chunklen; i++) {
        int value = d[i];
        if (inInverse) value = (1-d[i]);            
        if (storageMethod==0) {
            score = (score << 1) |value;
        }else{
            if (storageMethod==1){
                if(value) score += ++streak; else streak = 0;
            }else{
                if(value) score ++;         
            }
        }
    };  
    return score;
}

coord_t theFittest(dna_t d, view_t v) {
    // Definition of storageMethod: 0=decimal, 1=streak, 2=bitsum
    const int colorMemStorageMethod = 2, colorMemBlockSize = 2, colorMemZeroThreshold = 0;
    const int useTrapMem = 0, trapMemStorageMethod = -1, trapMemBlockSize = -1;
    const int trapMemTopThreshold = -1, nDirBins = -1, nColorBins = -1;
    const int reorderMemStorageMethod = -1, reorderMemReverseThreshold = -1;
    const int reorderMemInverseThreshold = -1;
    // Definition of hashPrority: -1: no hash, 0:hash when 'look beyond' scores equal,
    // 1: hash replaces 'look beyond', 2: hash replaces 'trap finder' and 'look beyond'
    // 3: hash replaces everything ('color finder', 'trap finder' and 'look beyond')
    const int hashPrority = 2;
    int inReverse = reorderMemReverseThreshold != -1 && 
     (dnaLookup(d,92,8,reorderMemStorageMethod,0) >= reorderMemReverseThreshold);
    int inInverse = reorderMemInverseThreshold != -1 && 
     (dnaLookup(d,84,8,reorderMemStorageMethod,0) >= reorderMemInverseThreshold);
    int trapMemStart=N_COLORS*colorMemBlockSize;
    unsigned long hashCode=17;
    int moveUp=0;
    if (hashPrority>0){
        for(int x = -2; x <= 2; x++) {
            for(int y = -2; y <= 2; y++) {
                int color = v(x, y)+2;
                hashCode = hashCode*31+color;
            }
        }       
        unsigned long hashMemStart=N_COLORS*colorMemBlockSize;
        if (useTrapMem==1 && hashPrority<=1) hashMemStart+=nDirBins*nColorBins*trapMemBlockSize;
        if (hashPrority==3) hashMemStart=0;
        int hashMemPos = hashCode % (DNA_BITS-hashMemStart);
        moveUp = dnaLookup(d,hashMemStart+hashMemPos,1,0,inInverse);
    }

    int xBestScore=0, yBestScore=0;
    long bestScore=-1, weightMove, weightMove2, mainScore;
    for(int x = -1; x <= 1; x++) {
        if (x < 0) weightMove = 1000; // moving backward
        if (x== 0) weightMove = 10000; //moving vertical
        if (x > 0) weightMove = 100000; //moving forward
        for(int y = -1; y <= 1; y++) {          
            int color = v(x, y);
            if (inReverse) color = 15-v(x, y);
            if(color == OUT_OF_BOUNDS || (x==0&&y==0) ) continue;
            //when MoveUp=1 -> give move with highest y most points (hashScore=highest)
            //when MoveUp=0 -> give move with lowest y most points (hashScore=lowest)
            int hashScore = (y+2)*(2*moveUp-1)+4; 
            mainScore = dnaLookup(
              d,
              color*colorMemBlockSize,
              colorMemBlockSize,
              colorMemStorageMethod,
              inInverse
             );
            if (mainScore<colorMemZeroThreshold+1) {
                mainScore =  0; //not a suitable move because too low score
            }else{
                mainScore*= weightMove;
                //lookup trap likelihood
                int directionBin = 0;
                if (nDirBins==3) directionBin = x>0?y+1:-1;
                if (nDirBins==4) directionBin = x>0?y+2:0;
                // put 16 colors in nColorBins bins
                int colorBin = v(0,0)*nColorBins/N_COLORS; 
                if (inReverse) colorBin = (15-v(0,0))*nColorBins/N_COLORS; 
                colorBin = colorBin>(nColorBins-1)?(nColorBins-1):colorBin;
                if (useTrapMem && directionBin >= 0 &&
                 dnaLookup(
                   d,
                   trapMemStart+trapMemBlockSize*(nColorBins*directionBin+colorBin),
                   trapMemBlockSize,
                   trapMemStorageMethod,
                   0
                 )>=trapMemTopThreshold){
                  //suspect a trap therefore no sub score is added                  
                 }else{
                    if (hashPrority>=1){
                        mainScore+=hashScore;
                    } else{
                        // when equal score, use sub score by examining 5x5 box to rank moves
                        for(int x2 = x-1; x2 <= x+1; x2++){     
                            if (x2 < x) weightMove2 = 1; // moving backward
                            if (x2== x) weightMove2 = 10; //moving vertical
                            if (x2 > x) weightMove2 = 100; //moving forward
                            for(int y2 = x-1; y2 <= y+1; y2++){     
                                int color2 = v(x2, y2);
                                if (inReverse) color2 = 15-v(x2, y2);
                                if(color2 != OUT_OF_BOUNDS){
                                    long mainSubScore = dnaLookup(
                                      d,
                                      color2*colorMemBlockSize,
                                      colorMemBlockSize,
                                      colorMemStorageMethod,
                                      inInverse
                                    );
                                    if (mainSubScore>=colorMemZeroThreshold+1){
                                        mainScore+=mainSubScore*weightMove2;
                                    }
                                }
                            }
                        }
                    }               
                 }
            }
            if (hashPrority==2 || (useTrapMem<=0 && hashPrority>=1)) mainScore+=hashScore*10;
            if (hashPrority==3) mainScore=hashScore*weightMove;         

            if(mainScore > bestScore) {
                bestScore = mainScore;              
                xBestScore = x;
                yBestScore = y;
            }
        }
    }
    return{xBestScore,yBestScore};
}   

Score: 922 (2K runs)

First 50 Scores (9 games have scored only 1 point):

112,747 3 1 1,876,965 8 57 214,921 218,707 2,512,937 114,389 336,941 1 6,915 2 219,471 74,289 31 116 133,162 1 5 633,066 166,473 515,204 1 86,744 17,360 2 190,697 1 6 122 126,399 399,045 1 4,172,168 1 169,119 4,990 77,432 236,669 3 30,542 1 6 2,398,027 5 1 2 8

This is my very first C++ program. I have as most of you now background in gnome analysis. I want to thank the organizers, since I really enjoyed working on this.

If you have any feedback, please leave a comment below. Apologies for the long texts.

Answer 9

WallGuesser - Scored 113.266 in a 1000 game test

Encoding

I made a really simple 6 bit/color encoding. To decode color[n]

• Sum every n'th bit in the genome up to 96
• If the sum score is >=4 then say this square is blocked
• If the sum score is <=4 then its final score is 2 ^ of its sum score

By spreading the bits for a color throughout the genome I'm increasing the chance that bits from both parents will be used for each color.

Movement

I use a (I'm sure not very efficient) A* based search to look for the lowest cost path to any of the right edge squares. If a color maps to, "blocked", then it will never be entered by the search. If the search can't find a path it assumes that this rat is not fit to reproduce and tries to end it by moving one to the left.

Reducing the number of unfit rats

Since my genome is effectively guessing about which squares are wall or backward teleporters rats that have no guesses (no colors that map to blocked) are not very fit. To try and remove these rats if no color would be marked as blocked then EVERY color is marked as blocked and the rat will always move one to the left.

TODO

Currently there is no randomness in the behavior so it's easy for rats to get stuck.

#include "./gamelogic.cpp"

#include <algorithm>
#include <set>
#include <map>
#include <climits>

bool operator< (const coord_t &a, const coord_t &b){
    if(a.x != b.x){ return a.x < b.x; }
    else if (a.y != b.y){ return a.y < b.y; }
    else{ return false; }
}

bool operator== (const coord_t &a, const coord_t &b){
    return (a.x == b.x) && (a.y == b.y);
}

int coordDistance(const coord_t &a, const coord_t &b){
    int xDif = abs(a.x - b.x);
    int yDif = abs(a.y - b.y);
    return xDif > yDif ? xDif : yDif;
}

int coordMinSetDistance(const coord_t &a, const std::set<coord_t> &ends){
    int min = INT_MAX;
    for (auto i : ends){
        int cur = coordDistance(a, i);
        if (cur < min){
            min = cur;
        }
    }
    return min;
}


class ColorMap{
public:
    view_t *v;
    int colors[16] = {};
    const int Blocked = -1;

    ColorMap(dna_t &d, view_t *v){
        this->v = v;

        //Decode the genome
        for (int i = 0; i <= (16*6); i++){
            if (d.at(i) == true){
                colors[i % 16]++;
            }
        }

        //Encode the result
        bool guessedWalls = false;
        for (int i = 0; i < 16; i++){
            if (colors[i] >= 4){
                colors[i] = Blocked;
                guessedWalls = true;
            }
            else{
                colors[i] = pow(2, colors[i]);
            }
        }

        if (guessedWalls == false){
            for (auto i : colors){
                i = Blocked;
            }
        }
    }

    int operator() (coord_t pos){
        if (abs(pos.x) > VIEW_DIST || abs(pos.y) > VIEW_DIST){
            return Blocked;
        }

        int value = (*v)(pos.x, pos.y);
        if (value == OUT_OF_BOUNDS){
            return Blocked;
        }
        else{
            return colors[value];
        }
    }

    void print(){
        int lower = -1 * VIEW_DIST;
        int upper = VIEW_DIST;
        for (int y = lower; y <= upper; y++){
            for (int x = lower; x <= upper; x++){
                std::cout << std::setw(3) << this->operator()({ x, y });
            }
            std::cout << std::endl;
        }
    }
};

class node{
public:
    coord_t pos;
    coord_t cameFrom;
    int gScore;
    int minDistance;

    node(coord_t pos, coord_t cameFrom, int gScore, int minDistance){
        this->pos = pos;
        this->cameFrom = cameFrom;
        this->gScore = gScore;
        this->minDistance = minDistance;
    }

    int fScore() const{ return gScore + minDistance; };

    bool operator< (const node &rhs) const{ return fScore() < rhs.fScore(); }
};

class EditablePriorityQueue{
private:
    //This is reversed so smallest are on top
    struct lesser{
        bool operator()(node *a, node *b) const{
            return (*b) < (*a);
        }
    };

    std::vector<node*> queue; // Use heap functions to maintain the priority queue ourself
    std::map<coord_t, node*> members;

public:
    EditablePriorityQueue(){};

    ~EditablePriorityQueue(){
        for (auto &m : members){
            delete m.second;
        }
    }

    bool empty(){ return members.empty(); }

    node *top(){
        auto top = this->queue.front();
        std::pop_heap(queue.begin(), queue.end(), lesser());
        queue.pop_back();
        members.erase(top->pos);
        return top;
    }

    void set(coord_t target, coord_t cameFrom, int gScore, int minDistance){
        auto targetLocation = members.find(target);

        //If the target isn't a member add it
        if (targetLocation == members.end()){
            auto *newNode = new node(target, cameFrom, gScore, minDistance);
            queue.push_back(newNode);
            std::push_heap(queue.begin(), queue.end(), lesser());
            members[target] = newNode;
        }
        //The target must be updated
        else{
            auto currentNode = targetLocation->second;
            if (currentNode->gScore > gScore){
                currentNode->gScore = gScore;
                currentNode->cameFrom = cameFrom;
                std::make_heap(queue.begin(), queue.end()); //More efficient way to do this?
            }
        }
    }
};

std::pair<coord_t, int> pathCost(ColorMap &m, coord_t start, const std::set<coord_t> &ends){
    EditablePriorityQueue openSet;
    std::set<coord_t> closedSet;
    std::map<coord_t, coord_t> cameFrom;

    openSet.set(start, start, 0, coordMinSetDistance(start, ends));
    while (openSet.empty() == false){
        auto current = openSet.top();
        closedSet.insert(current->pos);
        cameFrom[current->pos] = current->cameFrom;

        //Check if we're done
        if (ends.count(current->pos) != 0){
            //Recover the path
            coord_t path = current->pos;
            int finalScore = current->gScore;
            delete current;
            while (!(cameFrom[path] == start)){
                path = cameFrom[path];
            }

            return{ path, finalScore };
        }               

        //Examine current's neighbours
        for (int x = -1; x <= 1; x++) for (int y = -1; y <= 1; y++){
            coord_t neighbour = { current->pos.x + x, current->pos.y + y };

            if (x == 0 && y == 0){ continue; }

            closedSet.count(neighbour);
            if (closedSet.count(neighbour) != 0){ continue; }

            int neighbourScore = m(neighbour);
            if (neighbourScore == m.Blocked){ continue; }

            int tentativeScore = current->gScore + neighbourScore;
            openSet.set(neighbour, current->pos, tentativeScore, coordMinSetDistance(neighbour, ends));

        }
        delete current;
    }

    return{ { -1, 0 }, INT_MAX }; //Try to end it
}

coord_t myPlayer(dna_t d, view_t v) {
    auto ourMap = ColorMap(d, &v);

    std::set<coord_t> edges;
    for (coord_t edge = { VIEW_DIST, -1 * VIEW_DIST }; edge.y <= VIEW_DIST; edge.y++){
        edges.insert(edge);
    }

    //Move to the neighbor closest to a square on the right
    auto result = pathCost(ourMap, { 0, 0 }, edges);
    auto minMove = result.first;

    return minMove;
}

int main() {
    slog << "Geometric mean score: " << runsimulation(myPlayer) << std::endl;
}

Answer 10

Pathfinder, C++, preliminary score 35.8504 (50 rounds)

A complete overhaul! I ported my algorithm to C++ and tweaked it a bit, but the score is still not very high, probably because the rats keep banging their heads into walls. I'm tired of trying to improve this, so I'll just let it be for now.

int dnarange(dna_t &d, int start, int len) {
    int res = 0;
    for(int i = start; i < start+len; i++) {
        res = (res << 1) | d[i];
    }
    return res;
}

int dnasum(dna_t &d, int start, int len) {
    int res = 0;
    for(int i = start; i < start+len; i++) {
        res += d[i];
    }
    return res;
}

int dnaweight(dna_t &d, int start) {
    return d[start] + d[start+1] + 2*d[start+2] + 2*d[start+3] + 3*d[start+4];
}

int trap_d [16] = {1,0,1,1,0,1,-1,1,-1,0,-1,-1,0,-1,1,-1}; //immutable
int nhood [10] = {1,0,1,1,1,-1,0,1,0,-1}; //immutable

coord_t pathfinder(dna_t d, view_t v) {
  int is_trap[16] = {0};
  int pos_or_weight[16] = {0};
  int u_weight = dnaweight(d, 80);
  for (int i = 0; i < 16; i++) {
    int status = dnarange(d, 5*i, 2);
    if (status == 1) {
      is_trap[i] = 1;
      pos_or_weight[i] = dnarange(d, 5*i + 2, 3);
    } else {
      pos_or_weight[i] = dnaweight(d, 5*i);
    }
  }
  int w_area[7][4] = {0};
  for (int j = 0; j < 7; j++) {
    w_area[j][3] = u_weight;
  }
  for (int i = 0; i < 3; i++) {
    w_area[0][i] = u_weight;
    w_area[6][i] = u_weight;
  }
  int d_coeff = dnaweight(d, 85);
  for (int i = 0; i < 3; i++) {
    for (int j = 1; j < 6; j++) {
      int p_or_w, color = v(i, j-3);
      if (color != OUT_OF_BOUNDS) {
    p_or_w = pos_or_weight[color];
      } else {
    p_or_w = 1000;
      }
      if (color != OUT_OF_BOUNDS && is_trap[color] && i+trap_d[2*p_or_w] >= 0) {
    w_area[j + trap_d[2*p_or_w + 1]][i + trap_d[2*p_or_w]] += d_coeff;
      } else {
    w_area[j][i] += p_or_w;
      }
    }
  }
  for (int i = 3; i >= 0; i--) {
    for (int j = 0; j < 7; j++) {
      int min_w = 1000;
      for (int k = std::max(0, j-1); k <= std::min(6, j+1); k++) {
    min_w = std::min(min_w, w_area[k][i + 1]);
      }
      w_area[j][i] += min_w;
    }
  }
  int speed = dnasum(d, 90, 5);
  w_area[2][0] += 2 + speed;
  w_area[4][0] += 2 + speed;
  int goal = dnaweight(d, 95);
  int min_w = 10000;
  int sec_w = 10000;
  int min_x, min_y, sec_x, sec_y, w;
  for (int i = 0; i < 5; i++) {
    w = w_area[nhood[2*i + 1] + 3][nhood[2*i]];
    if (w < min_w) {
      sec_w = min_w;
      sec_x = min_x;
      sec_y = min_y;
      min_w = w;
      min_x = nhood[2*i];
      min_y = nhood[2*i + 1];
    } else if (w < sec_w) {
      sec_w = w;
      sec_x = nhood[2*i];
      sec_y = nhood[2*i + 1];
    }
  }
  if (min_w > goal) {
    int r = v.rng.rint(5);
    return {nhood[2*r], nhood[2*r+1]};
  } else if (sec_w <= goal && v.rng.rint(100) < 2*speed) {
    return {sec_x, sec_y};
  }
  return {min_x, min_y};
}

Explanation

The general idea is to classify each color as either a trap or not, then assign directions to traps and weights to non-traps, and try to follow the minimum-weight path to the right border of the vision grid.

In the first 80 bits of the genome, each color is classified using 5 bits abcde. If ab = 01, the color is a trap, and cde encodes its direction (eight possibilities). If ab ≠ 01, the color is not a trap, and its weight is a + b + 2*(c + d + e).

Next, we initialize a 3x7 grid, which represents the rat's vision field to its right, padded with "unknown" colors. The bits 80-84 encode the weight of the unknown cells similarly to the non-trap colors, and the bits 85-89 encode a common weight for the traps. We fill the grid with the weights, compute the shortest paths, and add some extra weight (encoded in the bits 90-95) to the cells directly above and below the rat to discourage sidestepping. The bits 95-99 encode a goal weight. If the minimum weight of a path is below it, the rat is probably stuck somewhere, and proceeds to move randomly (but never backtracks). Otherwise, it follows the minimum weight path. With a small probability depending on the sidestep-preventing weight, the rat chooses the second-to-minimum weight path instead. This is to prevent getting stuck to walls (but it seems not to work very well right now).

Answer 11

SlowAndSteady C++ (score 9.7)

We cannot rely on interpreting chunks of the genome as numbers because a single bit-flip can have radically different effects dependent on its position. Thats why i simply use 16 6-bit segments and score them on the number of 1s. Initially 111111 was good and 000000 was bad, and while it doesnt matter in the long term (once the genome is fully evolved) in the initial configuration of the DNA most of the segments have 2-4 ones, so i switched to using 9 - (#1 - 3)^2 for scoring, this allows for much more freedom of movement in the first rounds and faster evolution.

Right now i only look at the 7 nearest neighbours, add a direction bias to the colour score and move in one of the highest directions at random.

Although the score itself isnt very high, my critters reach the finish line and score > 1 in 3/4 of cases.

coord_t SlowAndSteadyPlayer(dna_t d, view_t v) {
    const int chunklen = 6;
    int color_scores[16] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
    for(int i=0; i<16; i++){ //count ones
        for(int j=0; j<chunklen; j++){
            color_scores[i] += d[i*chunklen + j];
        }
    }

    int moves[7][2] = {
        {-1,1}, {0,1}, {1,1},
                       {1,0},
        {-1,-1},{1,-1},{-1,-1}
    };
    int movescores[7];
    int smax = -1;
    int nmax = 0;
    int best_moves[7];
    for(int m=0; m<7; m++){ //compute the score for each move
        int temp_color = v(moves[m][0], moves[m][1]);
        if(temp_color == OUT_OF_BOUNDS){
            movescores[m] = 0;
            continue;
        }
        int dir_bias[3] = {1,3,6};
        int temp_score = 9-(color_scores[temp_color]-3)*(color_scores[temp_color]-3) + dir_bias[moves[m][0]+1];
        movescores[m] = temp_score;

        if(temp_score > smax) {
            smax = temp_score;
            nmax = 0;
        }
        if(temp_score == smax) best_moves[nmax++] = m;
    }

    int best_chosen = v.rng.rint(nmax);
    return {moves[best_moves[best_chosen]][0], moves[best_moves[best_chosen]][1]};
}

And a sample scoring on 100 boards

Scores: 5 4 13028 1 1 101 2 24 1 21 1 4 2 44 1 1 24 8 2 5 1 13 10 71 2 19528 6 1 69 74587 1 1 3 138 8 4 1 1 17 23 1 2 2 50 7 7 710 6 231 1 4 3 263 4 1 6 7 20 24 11 1 25 1 63 14 1 2 2 1 27 9 7 1 7 31 20 2 17 8 176 3 1 10 13 3 142 1 9 768 64 6837 49 1 9 3 15 32 10 42 8

Geometric mean score: 9.76557

Answer 12

LookAheadPlayer C++ ≈ 89.904

My original thought was to look for 4 bits which match the color that I was looking for, and using the following few bits as a score. This turned out to be a terrible idea, likely because of mutations.

So I thought about ways of protecting against mutations and crossovers, and it reminded me on work that I have done on QR code decoding. In QR codes the data is split into blocks and striped to avoid errors from destroying too much of a given portion of data.

Therefore, like the ColorScorePlayer, I cut the DNA into 16 chunks and use those as the given score. However, the scores are striped so that the individual bits of each score are non-adjacent. I then sum the score of both the current possible moves and the next potential moves and choose the best move to make.

Note: this was coded/tested on MinGW. It would not compile with optimizations, or with multithreading. I don't have an actual Linux install or Visual Studio handy to use a compiler where these will work. I'm going to be testing it quickly tomorrow morning, but please let me know if you run into any issues.

// get striped color score, 6 bits per color. should be
// resistant to getting erased by a crossover
void mapColorsBitwise(dna_t &d, int* color_array) {
    for (int i=0; i<N_COLORS; i++) {
        int score = 0;
        for (int j=0; j<6; j++) {
            score = (score<<1) | d[ j*N_COLORS + i ];
        }
        color_array[i] = score;
    }
}

// label for the lookup tables
enum direction_lut {
    UP_RIGHT=0, RIGHT, DOWN_RIGHT
};

// movement coord_t's to correspond to a direction
static const coord_t direction_lut[3] = {
    { 1, -1 }, { 1, 0 }, { 1, 1 }
};

// indexes into the arrays to denote what should be summed
// for each direction.
static const int sum_lut[3][6] = {
    { 3, 4, 8, 8, 9, 14 }, { 9, 13, 13, 14, 14, 19 },
    { 14, 18, 18, 19, 23, 24 }
};

coord_t lookAheadPlayer(dna_t d, view_t v) {
    int scoreArray[25] = { 0 };
    int colorScores[N_COLORS] = { };

    // Get color mapping for this iteration
    mapColorsBitwise(d, colorScores);

    for (int y=-2; y<=2; y++) {
        for (int x=0; x<=2; x++) {
            // Get the scores for our whole field of view
            color_t color = v(x,y);
            if (color != OUT_OF_BOUNDS)
                scoreArray[ (x+2)+((y+2)*5) ] += colorScores[color];
        }
    }

    // get the best move by summing all of the array indices for a particular
    // direction
    int best = RIGHT;
    int bestScore = 0;
    for (int dir=UP_RIGHT; dir<=DOWN_RIGHT; dir++) {
        if (v(direction_lut[dir].x, direction_lut[dir].y) == OUT_OF_BOUNDS)
            continue;

        int score = 0;
        for (int i=0; i<6; i++) {
            score += scoreArray[ sum_lut[dir][i] ];
        }

        if (score > bestScore) {
            bestScore = score;
            best = dir;
        }
    }

    return direction_lut[best];
}

Answer 13

WeightChooser | C# | Scores: 220.8262 in 1520 Games

Calculates the weight for the possible next move(blue) based on the average weight of the possible followed moves(yellow)

using ppcggacscontroller;
using System.Linq;
using System;

public class WeightChooser
{
    public static ppcggacscontroller.Program.Coord[] cspcoords = new[] {
            new Program.Coord(1, -1),
            new Program.Coord(1, 0),
            new Program.Coord(1, 1),
        };

    const int dnaBits = 4;

    public static void move(GameLogic.IView v, GameLogic.IGenome g, Random rnd, out int ox, out int oy)
    {
        var gcrds = cspcoords.Where(c => viewVal(v, c) > -1)
            .OrderByDescending(p => getBitsSet(g, viewVal(v, p)))
            .ThenByDescending(gt => weight(v, g, gt));

        Program.Coord nextMove = gcrds.First();
        ox = nextMove.x;
        oy = nextMove.y;
    }

    private static uint getBitsSet(GameLogic.IGenome g, int vVal)
    {
        uint i = g.cutOutInt(dnaBits * vVal, dnaBits);
        i = i - ((i >> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
    }

    private static int viewVal(GameLogic.IView v, Program.Coord c)
    {
        return v[c.x, c.y];
    }

    private static double weight(GameLogic.IView v, GameLogic.IGenome g, Program.Coord toGo)
    {
        double w = 0;

        int y = (toGo.y + v.yd) - 1;
        int i = 0;
        for (; i <= 2; i++)
        {
            int field = v[toGo.x + 1, (y + i) - v.yd];
            if (field > -1)
                w += getBitsSet(g, field);
        }

        return w / i;
    }
}

---

Scores: 32, 56103, 1361, 3351446, 33027, 23618, 22481, 1172713, 1, 3, 1, 1, 1, 2 88584, 106357, 1, 1232, 1, 1651280, 16690, 1, 1, 23732, 207554, 53, 69424, 1, 1,  79361, 1, 1, 51813, 229624, 25099, 2, 1, 234239, 362531, 1, 1, 19, 7295, 1, 7, 2, 196672, 1654208, 73453, 1, 23082, 1, 8, 5, 1685018, 4, 20, 1, 1, 1, 1, 1, 144 671, 122309, 10, 94752, 100895, 1, 54787, 54315, 252911, 79277, 1159, 241927, 94 347, 1, 318372, 37793, 1, 1, 1345310, 18934, 169700, 1, 1, 3, 186740, 83018, 121 758, 1, 358, 1935741, 88, 1, 1, 1, 1, 7, 21, 51144, 2, 1, 267638, 1, 1, 3, 1, 1,  1, 1, 674080, 47211, 8879, 7, 222766, 67214, 2, 89, 21038, 178463, 92846, 3, 14 0836, 1, 1, 111927, 1, 92165, 1, 192394, 1, 1, 2563722, 1, 42648, 1, 16, 1, 1, 2 85665, 1, 212653, 1, 4, 20513, 3, 135118, 13161, 2, 57, 78355, 3, 3, 44674, 8, 1 , 226472, 1, 1, 31588, 19619, 1, 2931870, 60814, 1, 1, 33867, 60740, 20558, 1, 1 5, 3, 5, 1, 1, 1, 60737, 450636, 468362, 1, 1, 347193, 91248, 551642, 1, 427215,  1, 57859, 17, 15, 66577, 24192, 1, 63560, 6568, 40279, 68216, 23098, 180732, 1,  1, 3041253, 1, 253488, 60535, 1, 1, 150838, 7361, 72855, 290699, 104644, 1, 763 01, 378, 1, 89220, 1, 262257, 2, 2, 1, 117, 105478, 33, 1, 65210, 1, 117588, 1, 1, 24320, 12, 3714568, 81152, 1, 1, 10125, 2, 1, 22, 1, 45201, 1, 1, 10518, 1, 1 , 1, 1, 34, 210021, 1, 1, 1, 65641, 6, 72, 1, 7, 2, 161578, 1, 1, 38378, 1, 4113 741, 1, 34450, 244212, 127660, 1, 256885, 46, 2, 1, 1, 103532, 1, 503965, 114774 , 52450, 124165, 73476, 50250, 1, 3, 3755352, 24928, 1, 1, 51, 11, 1, 210580, 1,  62375, 1, 1, 92745, 341232, 167675, 86, 242, 293710, 454841, 1, 49840, 4456758,  121378, 145323, 74904, 5048, 25459, 1, 57, 116999, 1, 1, 76074, 111447, 95706, 1, 1, 52631, 166756, 2159474, 161216, 1, 2, 3, 11904, 1, 22050, 6, 1, 1, 1, 41, 48908, 6, 80878, 28125, 28, 160516, 1, 4, 1, 8, 1, 1, 7, 362724, 1, 397193, 1, 2 5, 1, 59926, 3, 74548, 2320284, 470189, 1, 108, 1, 1, 16, 1, 496013, 1, 1, 1, 1,  107758, 1, 284144, 146728, 1, 70769, 94215, 1, 1, 9961, 97300, 7, 1, 76263, 1, 27, 294046, 40, 8, 2, 1, 57796, 2, 79800, 1043488, 470547, 1, 1, 1, 6, 69666, 8,  1, 1, 344011, 205325, 3963186, 1141527, 61598, 446029, 1, 1, 1, 1, 625247, 1877 92, 136391, 1, 72519, 1, 141168, 412, 98491, 103995, 297052, 1, 1, 1, 1, 3, 17, 9, 62899, 5, 47810, 254, 26789, 2, 1, 1, 3, 10361, 19615, 40430, 17288, 3, 71831 , 41374, 1, 91317, 409526, 1, 184305, 1, 192552, 3, 3587674, 39, 13, 134500, 41,  42, 672, 559835, 9, 39004, 51452, 1, 1, 12293, 11544, 265766, 8590, 1, 8632, 1,  1, 61849, 35155, 1, 74798, 72773, 1, 89, 37, 4, 4405882, 1, 99, 44397, 5, 4, 6,  1, 1, 1, 515818, 78383, 20, 127829, 1824801, 157, 1, 1, 268561, 19, 2, 230922, 1, 103, 98146, 5029789, 304324, 1, 5, 60516, 1, 139, 28982, 7, 20755, 187083, 1,  1, 143811, 37697, 1, 1, 269819, 83, 1, 202860, 13793, 16438, 113432, 1, 1, 2, 5 134384, 29, 84135, 39035, 2, 125, 1, 30, 129771, 41982, 13548, 61, 1, 2, 1, 82, 102, 2, 105581, 210399, 291204, 3012324, 1, 84763, 1, 1, 442067, 2, 1, 1, 1, 116 , 1, 3, 3, 56, 208807, 1, 2, 1, 14, 29, 31286, 1, 1, 162358, 28856, 46898, 1, 16 2698, 1, 1, 1, 65, 1, 1, 234566, 6, 1, 1, 128, 124, 2167692, 181946, 29, 1, 1, 1 , 1, 17, 162550, 179588, 4, 226480, 28, 1, 158512, 35084, 1, 26160, 17566, 1, 81 826, 2, 33, 1, 1, 11, 1, 230113, 1, 1, 1, 24405, 17, 1, 2, 1, 162365, 2, 1, 1, 8 5225, 1, 15016, 51509, 1, 5, 1, 93, 13, 59, 24548, 1, 3, 2, 2, 1, 64424, 1, 1, 4 , 1, 1, 1, 2, 267115, 139478, 52653, 96225, 1, 1, 35768, 3, 1, 1, 3280017, 8, 80 014, 43095, 112102, 1, 1, 1, 79594, 5, 1, 1, 4, 455714, 19, 15, 1, 233760, 55850 5, 2, 2, 1, 63672, 1, 3732951, 1, 135858, 134256, 452456, 151573, 79057, 638215,  88820, 1, 1, 76517, 13, 314006, 5, 1, 17704, 1, 79589, 1, 18371, 530793, 59020,  1, 1, 1, 4, 1, 1, 1, 71735, 1, 1, 1, 1, 1, 37894, 1, 2, 24054, 1, 8, 26471, 34,  1, 48033, 5, 3, 1, 25, 101, 1, 1, 5, 1, 1, 1, 97521, 1, 682817, 286486, 5, 1472 4, 1, 7805226, 6, 1, 1, 1, 7, 2, 1, 1, 1, 25, 233330, 1, 20899, 3417337, 92793, 23, 80821, 1, 1, 115948, 264191, 3, 79809, 1, 2, 59531, 2, 1, 1, 28684, 97, 1, 2 69433, 98769, 1, 76608, 138124, 1, 1, 325554, 122567, 1, 1, 3, 689604, 4, 85823,  66911, 138091, 169416, 21430, 1, 2, 486654, 108446, 93072, 1, 67907, 4, 1, 1, 5 2260, 67867, 210496, 25157, 1, 1, 1, 5477, 2, 2, 11907, 106, 48404, 1, 1, 1, 787 11, 190304, 112025, 1, 9313, 143055, 40189, 315537, 157581, 70714, 6, 180600, 38 594, 103658, 59444, 7, 31575, 1, 1, 581388, 370430, 1, 114446, 1, 1, 2, 3968, 1,  1, 1, 1, 1, 4523411, 1, 1, 270442, 1, 59, 235631, 3, 110196, 9, 1, 93724, 1, 22 917, 1, 6, 1, 2350266, 1, 1, 20, 4686858, 31, 1, 240180, 10, 470592, 3, 61051, 1 45372, 2831, 64052, 10, 120652, 255971, 479239, 1, 387659, 1, 1, 1, 378379, 7, 3 3218, 55914, 1, 1, 1667456, 6, 2, 74428, 3, 2, 1, 121582, 121274, 19651, 59899, 1, 11, 406670, 137835, 100269, 2, 164361, 98762, 44311, 25817, 178053, 31576, 1,  8, 2539307, 121430, 1, 41001, 1, 4, 1, 116258, 91101, 1, 126857, 1, 8, 49503, 1 , 489979, 12, 500332, 1, 52, 4, 8786, 4, 4878652, 12354, 27480, 89115, 87560, 11 793, 5, 1, 4702325, 301188, 1, 1, 1, 1, 1, 416520, 49357, 230103, 24497, 1, 3, 2 , 57366, 183021, 1, 1, 1, 1, 1, 2, 2, 2546229, 1, 2, 38665, 1, 6903, 1, 89519, 9 5119, 64879, 1, 1, 160380, 474336, 3107, 1, 7, 29099, 28667, 3, 196933, 35979, 1 2924, 7, 1, 99885, 6, 1, 1, 1, 7, 1, 1, 1, 1, 65727, 1, 1, 1, 1, 2108110, 3, 107 811, 23818, 701905, 1, 156034, 32, 1, 29, 143548, 1, 67665, 4612762, 1, 3, 20, 1 , 1, 9, 28543, 1, 1, 1, 30978, 9, 1, 19504, 79412, 15375, 763265, 1, 352373, 193 045, 1, 4570217, 9, 1, 6, 29180, 90030, 1, 1, 1, 1, 1, 93, 1, 100889, 1, 1, 37, 15, 17, 1, 81184, 1, 2, 272831, 1, 137, 1, 9, 42874, 679183, 1, 350027, 12, 1, 2 , 1, 26408, 1, 11182, 1, 30, 139590, 7, 3, 1, 1, 34729, 1, 2, 1, 1, 50343, 66873 , 3891, 1, 148952, 1, 1, 22322, 104176, 1, 3, 20549, 140266, 37827, 30504, 17, 6 8588, 120195, 1, 123353, 2, 64301, 11, 1, 109867, 4, 1, 1, 1, 28671, 1, 50963, 5 4584, 1, 1, 1, 33, 1, 381918, 1, 265823, 4771840, 155179, 314, 134086, 1, 1, 30,  1, 2, 1102665, 18, 132243, 3861, 1, 1, 208906, 60112, 1, 1, 1, 31273, 551, 3490 0, 2, 43606, 1, 1, 1, 1, 5, 2, 88342, 2, 1, 19, 3, 1, 1, 1, 1, 28507, 1, 491467,  1, 1, 22, 1, 1, 1, 1, 9345, 9, 18, 84343, 1, 2, 1, 18, 36816, 1, 1, 513028, 287 88, 5037383, 721932, 170292, 108942, 539115, 1, 575676, 20, 1, 31698, 99797, 205 21, 380986, 1, 1, 14, 2, 1, 201100, 30, 1, 119484, 1, 1, 1, 1, 2214252, 3, 4, 18 179, 9, 4, 542150, 1, 6, 157, 3182099, 4, 1, 1, 6140, 3339847, 498283, 52523, 1,  1, 1, 1, 1, 202054, 263324, 1, 6, 2, 1, 2, 72357, 12, 5, 66, 4, 7368, 1, 30706,  61936, 3945270, 138991, 1, 68247, 1, 1, 30482, 35326, 1, 1, 9, 1, 148, 1, 46985 , 1, 4325093, 1, 1, 2880384, 65173, 1, 56581, 179178, 372369, 56187, 3, 12, 8, 4 00743, 3, 28658, 1, 1, 9, 1, 4, 2, 34357, 1, 42596, 68840, 2, 62638, 158027, 617 34, 71263, 1, 1, 9, 1, 6830309, 3, 1, 1, 157253, 129837, 9, 5008187, 48499, 5981 3, 1, 40320, 233893, 5, 1383, 7732178, 16, 1, 13, 5686145, 84554, 1, 79442, 1, 1 , 256812, 127818, 31, 226113, 1, 4, 1, 1, 4506163, 1, 4, 1, 40176, 19107, 205, 2 7, 1, 448999, 1, 1, 2750, 62723, 1, 12, 1, 1, 79881, 1, 48, 13, 4, 1, 28765, 1, 33, 291330, 30817, 2, 1, 1, 1, 4170949, 16, 1, 1, 118781, 10473, 520797, 1, 8, 1 , 80215, 1, 21759, 5143209, 79141, 40229, 1, 17403, 71680, 1115694, 1, 1, 1, 10,  1, 77149, 382712, 1, 11, 84891, 47633, 1, 2, 39037, 1, 213148, 1607280, 127674,  1, 333207, 1, 78901, 1, 16203, 87580, 1, 1565571, 537902, 53000, 15, 1, 2, 1, 2 13127, 1, 338634, 2469990, 469479, 9519, 51083, 1, 42082, 33179, 1, 1, 32444, 3,  1, 201642, 99724, 377, 1, 2, 1, 36919, 1, 322707, 2, 164765, 82516, 1, 5274643,  1, 36421, 1, 8, 1, 117856, 1, 1, 493342, 1, 36289, 7, 1, 62, 2, 1, 38533, 1, 68 , 45754, 9, 102015, 312941, 1, 99 
Final score is 220.826222910756

Answer 14

SkyWalker - Python - scores less than 231 in 50 games

So code first and then some explanations. I hope nothing broke while copying.

class SkyWalker(Player):
    def __init__(self):
        Player.__init__(self)
        self.coords = [#Coordinate(-1,-1),
                       #Coordinate( 0,-1),
                       Coordinate( 1, 0),
                       Coordinate( 1,-1),
                       #Coordinate(-1, 0),
                       #Coordinate( 0, 0),
                       #Coordinate(-1, 1),
                       #Coordinate( 0, 1),
                       Coordinate( 1, 1)]

        self.n_moves = len(self.coords)

    def visionToMove(self, x, y):
        x = x - 2
        y = y - 2

        return (x, y)

    def trapToMove(self, x, y, offx, offy):
        x = x - 2 + (offx % 3) - 1
        y = y - 2 + (offy % 3) - 1
        return (x, y)

    def isNeighbour(self, x1, y1, x2, y2):
        if (x1 == x2) or (x1+1 == x2) or (x2+1 == x1):
            if (y1 == y2) or (y1+1 == y2) or (y2+1 == y1):
                return True
        return False

    def calcMove(self, donots, never, up):
        forwards = {(1, 0): 0, (1, 1): 0, (1, -1): 0, (0, 1): 10, (0, -1): 10}

        for key in forwards:
            if key in never:
                forwards[key] = 100
            for x in donots:
                if (key[0] == x[0]) and (key[1] == x[1]):
                    forwards[key] = 20

        min_value = min(forwards.itervalues())
        min_keys = [k for k in forwards if forwards[k] == min_value]

        return random.choice(min_keys)

    def turn(self):
        trap1 = self.bit_chunk(0, 4)
        trap1_offsetx = self.bit_chunk(4, 2)
        trap1_offsety = self.bit_chunk(6, 2)
        trap2 = self.bit_chunk(8, 4)
        trap2_offsetx = self.bit_chunk(12, 2)
        trap2_offsety = self.bit_chunk(14, 2)
        wall1 = self.bit_chunk(16, 4)
        wall2 = self.bit_chunk(20, 4)
        tel1 = self.bit_chunk(24, 4)
        tel1_good = self.bit_chunk(28, 3)
        tel2 = self.bit_chunk(31, 4)
        tel2_good = self.bit_chunk(35, 3)
        tel3 = self.bit_chunk(38, 4)
        tel3_good = self.bit_chunk(42, 3)
        tel4 = self.bit_chunk(45, 4)
        tel4_good = self.bit_chunk(49, 3)
        up = self.bit_at(100)

        donots = []
        never = []

        for y in range(0, 5):
            for x in range(0, 5):
                c = self.vision[y][x]
                if (c == -1):
                    never += self.visionToMove(x, y),
                elif (c == trap1):
                    donots += self.trapToMove(x, y, trap1_offsetx, trap1_offsety),
                elif (c == trap2):
                    donots += self.trapToMove(x, y, trap2_offsetx, trap2_offsety),
                elif (c == wall1):
                    donots += self.visionToMove(x, y),
                elif (c == wall2):
                    donots += self.visionToMove(x, y),
                elif (c == tel1):
                    if (tel1_good > 3):
                        donots += self.visionToMove(x, y),
                elif (c == tel2):
                    if (tel2_good > 3):
                        donots += self.visionToMove(x, y),
                elif (c == tel3):
                    if (tel3_good > 3):
                        donots += self.visionToMove(x, y),
                elif (c == tel4):
                    if (tel4_good > 3):
                        donots += self.visionToMove(x, y),

        coord = self.calcMove(donots, never, up)

        return Coordinate(coord[0], coord[1])

Some Explanation

In my opinion the main difference is that I do not code every color. Instead, I try to save the number of the colours that are important. In my opinion those colours are the traps, walls and teleporters. The specimen does not need to know the color of a good cell. Therefore, my genome is structured in the following way.

• 2 x 8 bits for traps, the first 4 bits are the color number, the other 4 are the offset
• 2 x 4 bits for walls, just the color
• 4 x 7 bits for teleporters, again 4 bits for the color, 3 to decide good or bad

This makes for a total of 52 bits used. However, I use only the first bit of the 3 teleporter deciders (I check if the number is greater 3). Therefore, the other 2 could be deleted, leaving me at 44 bits used.

On each turn I check every field of my vision if it is one the bad colours (+ the out of board -1) and add it to a list of fields the specimen does not want to move to. In the case of a trap, I add the field that is on the saved offset for that trap color.

Based on the list of those bad fields the next move is calculated. The order of the preferred fields is:

1. forward
2. up or down
3. backwards up or down
4. backwards

If two fields of a category are applicable, one is chosen randomly.

Results

Individual scores: [192, 53116, 5, 1649, 49, 2737, 35, 5836, 3, 10173, 4604, 22456, 21331, 445, 419, 2, 1, 90, 25842, 2, 712, 4, 1, 14, 35159, 13, 5938, 670, 78, 455, 45, 18, 6, 20095, 1784, 2, 11, 307853, 58171, 348, 2, 4, 190, 7, 29392, 15, 1158, 24549, 7409, 1]
On average, your bot got 231.34522696 points

Thoughts

• I have no idea, if I got lucky with the 50 runs or if there is actually some wisdom in my strategy.

• My runs never seem to take off and get super high scores but they also tend to find at least a few times the goal

• Some small randomness is good to not get stuck in a trap some where close to the end of the race

• I think non-special colours are never bad. However, instances of them can be bad, when they are on the offset of a trap. Thus, labeling a color bad if its not trap, wall or bad teleporter makes no sense.

• Walls are the greatest enemies

Improvements

First, even though I will miss seeing the black squares moving closer and closer to the goal a C++ port is necessary to conduct more tests and get a more meaningful result.

One of the main problems is that if there are bad cells (or those the specimen thinks bad) in front of the rat it easily starts moving up and down in circles. This could be stopped or reduced by looking 2 moves ahead in those cases and prevent it from moving to a field where it would just move back again.

Often it takes quite some time until a rat with good genes gets to the goal and starts spreading it genes. Maybe I need some strategy to increase the diversity in those cases.

Since teleporters are hard to calculate maybe I should split the population in those who are risky and always take good teleporters and those who are more concerned and only take them if there is no other choice.

I should use the second half of my genome somehow.

Answer 15

RATS IN ACTION (not an answer, but a graphic tool for C++ bots)

Since the begining of this challenge, I had difficulties figuring out what the rats were really facing on the track.
In the end I hacked the controller and wrote a side tool to get some graphic representation of a track.
I eventually did some more hacking and added a visualization of the possible paths of a given rat's DNA.

The map is extremely cluttered and requires a bit of getting used to, but I found it quite helpful to understand how my bots worked.

Here is an example:

You'll probably need to zoom-in to see anything, so here is just the first half:

At first, let's look at the rat's paths. There is one path for each possible starting location (usually 15, sometimes a bit less). Usually they tend to merge, ideally leading to a single victory location.

The paths are represented by big straight arrows. The color describes the outcome:

• green: win
• yellow: infinite loop
• brown: wall banging
• red: unfortunate accident

In the example, we have 12 winning start positions, one leading to an infinite loop and two to a grueling death (being teleported into a trap, as it appears).

The path discontinuities are due to teleportations, which you can follow with the corresponding curved arrows.

Now for the colored symbols. They represent the meaning of the 16 colors (the grey ones represent what a rat sees).

• wall: square
• teleporter: 4 branched star
• trap detector: small octogon

empty colors are... well... empty.

Teleporters have outgoing arrows pointing to their destination.

Trap detectors also have arrows indicating the trap, which is figured as a red circle.
In one case out of 9, the trap is located in the same cell as its detector, in which case you will see the small octogon on top of the red circle.

It is the case for the pale yellow trap in this example.
You can also see the mauve trap detectors pointing down to their indicated trap.

Notice that sometimes a trap's red circle will be hidden under a wall. Both are lethal so the result is the same in case of teleportation.
Notice also that a trap might be located on a teleporter, in which case the teleporter takes precedence (i.e. the rat is teleported before falling into the trap, in effect neutralizing the trap).

Lastly, the grey symbols represent what my rats see (i.e. the meaning their genome attributes to the colors).

• wall: square
• trap detector: octogon
• trap: X

Basically, all cells sitting on a grey square are considered walls by the rat.
Big X's represent cells considered as traps, with the corresponding octogons indicating the detector that reported them.

In this example, both walls are identified as such, as is the pale yellow trap (indicating indeed a deadly cell, so representing it as a wall is correct).
The mauve trap detector has been identified as such (it sits on a grey octogon), but the trap location is incorrect (you can see that some red circles have no crosses under them).

Out of 4 teleporters, 2 are considered as walls (turquoise and tan), and 2 as empty cells (reddish and yellowish).

A few empty cells are considered as trap detectors or walls. Looking closely, you can see that these "faulty detectors" are indeed forbidding entry into cells that would get the rat into trouble, so even though they fail to match the real colors, they have a definite purpose.

The code

Well it's a mess, but it works rather well.

Seen from the player's code, I only added one interface: a trace function used to report the meaning of a given DNA. In my case I used 3 types (wall, trap detector and empty) but you can basically output anything color-related (or nothing at all if you want no genome-related graphics).

I hacked the controller to generate a huge character string collating the track and colors description with a "dry run" of the rat's DNA from all possible locations.

It means the results will be really meaningful only if the bot does not use random values. Otherwise, the paths displayed will only represent one possible outcome.

Lastly, all these traces are put into a big text file that is later read by a PHP utility that produces the graphic output.

In the current version, I take a snapshot each time a rat dies after having reached a new maximal fitness (that shows pretty well the progressive refinement of the genome without requiring too many snapshots), and a final snapshot at end of game (that shows the most successfull DNA).

If someone is interested I can publish the code.

Clearly this works only for C++ bots, and you will need to write a trace function and possibly modify the PHP code if you want to display some genome-specific data (the grey figures in my case).
Even without DNA-specific informations, you can see the paths followed by your DNA on a given map with very little effort.

Why an intermediate output?

First of all, C++ has no decent portable graphic library to speak of, especially when using MSVC. Even if Win32 builds are usually available, they often come as an afterthought, and the number of external libraries, packages and other unix-like niceties needed makes writing a quick and simple graphical application a terrible pain in a part of one's body that decency prevents me from naming.

I considered using Qt (about the only environment that makes portable GUI/graphical development in C++ a simple and even pleasant task, IMHO - probably because it adds a messaging system à la Objective C that C++ sorely lacks and does an incredible job of limiting memory management to the barest minimum), but this looked like an overkill for the task at hand (and anyone wanting to use the code would have to install the biggish SDK - hardly worth the effort, I guess).

Even assuming a portable library, there is no speed requirement to speak of (one second or so to produce a picture is largely sufficient), and with its proverbial rigidity and inherent messiness, C++ is certainly not the best tool for the job.

Furthermore, having an intermediate text output adds a lot of flexibility. Once the data are there, you can use them for other purposes (analyzing the performance of the bots, for instance).

Why PHP?

I find the language extremely simple and adaptable, very convenient for prototyping. I made it my pet language for code challenges that do not require extreme performances.
_{It is a terrible language for golfing, though, but golf was never my cup of tea anyway.}

I suppose python or Ruby would be just as pleasant to use for the same purpose, but I never had an occasion to do some serious work with them, and I was working on web sites lately, so PHP it is.

Even if you don't know the language, it should not be too difficult to modify the code to suit your needs. Just don't forget the $s before the variables, just like the good old Basic days :).

Answer 16

Python, NeighborsOfNeighbors, Score=259.84395 over 100 games

This is a variation on ColorScorePlayer. Every 6 bits stores a quality score for a square. When the bot is making a move, it scores each of the 3 forward squares -- diagonal up, forward, and diagonal down. The score is the quality of the square plus one half the average quality of the next 3 squares. This gives the bot some look ahead, without overwhelming the quality of the first square. The algorithm is similar to LookAheadPlayer, which I did not see before writing this solution.

class NeighborsOfNeighbors(Player):
  def __init__(self):
    Player.__init__(self)
    self.coords = [ Coordinate( 1, 0),
                    Coordinate( 1,-1),
                    Coordinate( 1, 1)
                    ]

  def turn(self):
    scores=[self.score(c.x,c.y)+0.5*self.adjacentScore(c.x,c.y) if self.vision_at(c.x,c.y)>-1 else None for c in self.coords ]
    max_score = max(scores)
    return random.choice( [c for s,c in zip(scores,self.coords) if s==max_score] )

  def adjacentScore(self,x,y):
    adjacent = [(x+1,y)]
    if self.vision_at(x,y+1)>-1:
      adjacent+=[(x+1,y+1)]
    if self.vision_at(x,y-1)>-1:
      adjacent+=[(x+1,y-1)]
    adjscores=[self.score(a,b) for a,b in adjacent]
    return sum(adjscores)/float(len(adjscores))

  def score(self,x,y):
    return -1 if self.vision_at(x,y) == -1 else self.bit_chunk(6*self.vision_at(x,y),6)

Answer 17

ROUS (Rodent of Unusual Size), Java, Score = 0

This hashes the surroundings to decide where to go. Due to the Java controller not working I do not have scores for this. This will only get very far if it finds a few teleporters to help it. This tends to go extinct and crash the controller once in a while. This is probably due to the fact that it's natural environment is the Fire Swamp.

import java.awt.*;
import java.util.Map;

public class ROUS extends Player{

    private static final int NUMBER_OF_GENES = 33;
    private static final int GENE_SIZE = 3;
    private static final Point[] coords = new Point[]{
        new Point(-1, -1),
        new Point(-1, 0),
        new Point(-1, 1),
        new Point(0, -1),
        new Point(0, 1),
        new Point(1, -1),
        new Point(1, 0),
        new Point(1, 1)
    };

    public Point takeTurn(String dna, Map<Point, Integer> vision){
        Point[] table = decode(dna);
        int hash = hash(vision);
        return table[hash];
    }

    private int hash(Map<Point, Integer> surroundings) {
        return Math.abs(surroundings.hashCode()) % NUMBER_OF_GENES;
    }

    private Point[] decode(String dna) {
        Point[] result = new Point[NUMBER_OF_GENES];

        for (int i = 0; i < NUMBER_OF_GENES; i++){
            int p = Integer.parseInt(dna.substring(i * GENE_SIZE, (i + 1) * GENE_SIZE), 2);
            int x;
            int y;

            result[i] = coords[p];
        }
        return result;
    }
}

Answer 18

Java, RunningStar, Score = 1817.050970291959 over 1000 games

This bot uses Run-Bonus's color coding with StarPlayer's technique.

Update: Fixed java controller.

Scores: 6, 81533, 1648026, 14, 5, 38841, 1, 76023, 115162, 3355130, 65759, 59, 4, 235023, 1, 1, 1, 3, 2, 1, 1, 14, 50, 1, 306429, 68, 3, 35140, 2, 1, 196719, 162703, 1, 1, 50, 78233, 5, 5, 5209, 1, 2, 60237, 1, 14, 19710, 1528620, 79680, 33441, 58, 1, 4, 45, 105227, 11, 4, 40797, 2, 22594, 9, 2192458, 1954, 294950, 2793185, 4, 1, 1, 112900, 30864, 23839, 19330, 134178, 107920, 5, 122894, 1, 1, 2721770, 8, 175694, 25235, 1, 3109568, 4, 11529, 1, 8766, 319753, 5949, 1, 1856027, 19752, 3, 99071, 67, 198153, 18, 332175, 8, 1524511, 1, 159124, 1, 1917181, 2, 1, 10, 276248, 1, 15, 1, 52, 1159005, 43251, 1, 536150, 75864, 509655, 1126347, 250730, 1548383, 17, 194687, 27301, 2, 1, 207930, 621863, 6065, 443547, 1, 6, 1, 1, 1, 1, 556555, 436634, 25394, 2, 61335, 98076, 1, 190958, 2, 18, 67981, 3, 8, 119447, 1, 1, 1, 19, 28803, 23, 33, 60281, 613151, 1, 65, 20341, 799766, 476273, 105018, 357868, 3, 92325, 2062793, 18, 72097, 30229, 1, 1, 3, 610392, 1, 202149, 887122, 56571, 1, 77788, 61580, 4, 72535, 381846, 148682, 26676, 1, 210, 3556343, 212550, 650316, 33491, 180366, 1, 295685, 46255, 43295, 1006367, 63606, 1, 1, 1, 1, 3094617, 21, 10, 3, 1, 1, 14730, 1585801, 102, 2, 410353, 1570, 1, 17423, 1, 1849366, 5, 1, 357670, 1, 1, 1, 1, 89936, 349048, 15, 7, 6, 2, 121654, 1852897, 19, 1, 103275, 1, 1, 771797, 23, 19, 6700, 1, 135844, 2966847, 3, 2356708, 101515, 1, 17, 1, 996641, 22, 16, 657783, 171744, 9604, 1, 1335166, 1739537, 2365309, 1, 3378711, 11332, 3980, 182951, 609339, 8, 10, 1746504, 61895, 386319, 24216, 331130, 12193, 1, 284, 1, 2, 50369, 38, 8, 1, 1238898, 177435, 124552, 22370, 1418184, 20132, 6, 2, 730842, 1, 1341094, 141638, 534983, 1551260, 31508, 96196, 434312, 3012, 715155, 1, 276172, 214255, 1, 208948, 4, 1631942, 512293, 37, 64474, 1342713, 1, 132634, 13, 2, 61876, 1081704, 160301, 2, 488156, 2414109, 1809831, 5, 74904, 6, 11, 5, 1, 79856, 96, 35421, 229858, 238507, 3838897, 18, 44, 1, 1659126, 9, 33708, 12, 1, 758381, 162742, 256046, 3, 15, 142673, 70953, 58559, 6, 2, 1, 984066, 290404, 1072226, 66415, 4465, 924279, 48133, 319765, 519401, 1, 1, 1201037, 418362, 17022, 68, 213072, 37, 1039025, 1, 2, 6, 4, 45769, 1, 5, 1061838, 54614, 21436, 7149, 1, 1, 1, 35950, 2199045, 1, 379742, 3, 2008330, 238692, 181, 7, 140483, 92278, 214409, 5179081, 1, 1, 334436, 2, 107481, 1142028, 1, 31146, 225284, 1, 14533, 4, 3963305, 173084, 102, 1, 4732, 14, 1, 25, 11032, 224336, 2, 131110, 175764, 81, 5630317, 1, 42, 1, 89532, 621825, 2291593, 210421, 8, 44281, 4, 303126, 2895661, 2672876, 3, 436915, 21025, 1, 4, 49227, 1, 39, 3, 1, 103531, 256423, 2, 1600922, 15, 1, 2, 58933, 1114987, 1, 4, 3, 1, 1544880, 285673, 240, 2, 128, 214387, 3, 1327822, 558121, 5, 2718, 4, 1258135, 7, 37418, 2729691, 1, 346813, 385282, 2, 35674, 513070, 13, 1930635, 117343, 1929415, 52822, 203219, 1, 52407, 1, 1, 1, 3, 2, 37121, 175148, 136893, 2510439, 2140016, 437281, 53089, 40647, 37663, 2579170, 83294, 1597164, 206059, 1, 9, 75843, 773677, 50188, 12, 1, 1067679, 105216, 2452993, 1813467, 3279553, 280025, 121774, 62, 5, 113, 182135, 1, 16, 71853, 4, 557139, 37803, 228249, 6, 32420, 8, 410034, 73889, 1, 2, 96706, 48515, 1, 3, 1314561, 137, 966719, 692314, 80040, 85147, 75291, 1, 1, 30, 38119, 182723, 42267, 3836110, 22, 986685, 2, 37, 1, 3, 26, 43389, 2679689, 1, 1, 57365, 1, 2662599, 2, 72055, 1, 141247, 1, 1, 1122312, 1, 1080672, 4, 266211, 1, 34163, 1490610, 256341, 1, 627753, 32110, 1, 42468, 1, 10746, 1, 9, 1, 46, 1714133, 5, 117, 1, 104340, 218338, 151958, 122407, 211637, 223307, 57018, 74768, 582232, 2, 621279, 4, 1, 11, 196094, 1839877, 167117, 8, 42991, 2199269, 124676, 1, 1, 1, 5, 1, 1, 698083, 1, 76361, 1564154, 67345, 1398411, 9, 11, 105726, 1197879, 1, 2, 62740, 39, 2, 397236, 17057, 267647, 13, 57509, 22954, 1, 12, 747361, 4325650, 21425, 2160603, 144738, 1, 204054, 3113425, 6, 3019210, 30, 3359, 1, 89117, 489245, 1, 218068, 1, 1, 14718, 222722, 1, 1, 216041, 72252, 279874, 183, 89224, 170218, 1549362, 2, 1, 953626, 32, 130355, 30460, 121028, 20, 159273, 5, 2, 30, 1, 76215, 1654742, 2326439, 1, 53836, 1, 6, 4, 72327, 9, 285883, 1, 908254, 698872, 47779, 3, 2293485, 265788, 3766, 1, 1, 83151, 36431, 307577, 256891, 29, 1, 1, 1093544, 145213, 5, 2, 581319, 2911699, 1, 213061, 1359700, 2, 1, 343110, 1, 157592, 1708730, 1, 22703, 32075, 1, 1, 87720, 159221, 2313143, 10, 2266815, 2106917, 1345560, 3146014, 4, 551632, 1066905, 550313, 4069794, 1, 1406178, 38981, 1, 3, 1, 3039372, 241545, 35, 63325, 85804, 1365794, 2, 2143204, 48, 1, 99, 3225633, 7, 4074564, 1023899, 3209940, 2054326, 70880, 2, 1, 284192, 1944519, 84682, 2, 867681, 90022, 378115, 1, 15, 602743, 1337444, 131, 1, 229, 161445, 3, 2, 5591616, 195977, 92415, 637936, 142928, 1, 2310569, 923, 1, 230288, 1300519, 398529, 2233, 100261, 4323269, 81362, 37300, 1, 233775, 32277, 434139, 323797, 19214, 782633, 2881473, 1, 1, 9, 337016, 1, 515612, 44637, 17, 1, 25, 67758, 1737819, 16454, 30613, 692963, 62216, 222062, 344596, 3, 33782, 19, 180441, 23552, 20462, 70740, 10298, 109691, 1, 1729427, 33714, 1770930, 1, 1, 1, 1, 290766, 136688, 688231, 3250223, 30703, 1985963, 527128, 3, 226340, 195576, 30, 1, 3, 1, 793085, 5527, 5, 1, 2188429, 1327399, 5, 6192537, 1445186, 2478313, 2, 16892, 3, 1, 1, 15, 12, 1361157, 4, 1241684, 1, 45008, 1, 505095, 4037314, 14, 8, 1, 16740, 69906, 45, 1, 240949, 3975533, 212705, 2617552, 278884, 1, 24966, 958059, 231886, 22929, 4052071, 51259, 67791, 78739, 1, 165787, 67, 518191, 86923, 437, 1271004, 135941, 244766, 1, 1, 1, 1152745, 1, 3, 406365, 3847357, 476636, 135097, 304368, 8, 1578276, 1, 1, 375, 1, 1, 1298206, 1860743, 2, 35311, 834516, 421428, 2, 66629, 1, 309845, 398756, 33, 907277, 384475, 2267460, 1, 269300, 124525, 34399, 93584, 362186, 811260, 426109, 1, 1009323, 109986, 122181, 1, 1, 3626487, 11452, 1092410, 57233, 6, 2009226, 1, 83333, 4, 1338631, 79114, 2140249, 51813, 1118986, 43514, 1529365, 1, 101, 1, 1,

package game.players;

import java.awt.Point;
import java.util.*;

public class RunningStar extends Player{

    @Override
    public Point takeTurn(String genome, Map<Point, Integer> vision) {
        Map<Integer, Integer> squareCosts = decode(genome);
        Path path = astar(vision, squareCosts);
        return path.get(1);
    }

    private Path astar(Map<Point, Integer> vision, Map<Integer, Integer> squareCosts) {
        Set<Path> closed = new HashSet<>();
        PriorityQueue<Path> open = new PriorityQueue<>();
        open.add(new Path(new Point(0, 0), 0));
        while (!open.isEmpty()){
            Path best = open.remove();
            if (best.head().x == 2 || (best.head().x > 0 && (best.head().y == 2 || best.head().y == -2))){
                return best;
            }
            for (Path path : pathsAround(best, vision, squareCosts)){
                if (!closed.contains(path) && !open.contains(path)){
                    open.add(path);
                }
            }
            closed.add(best);
        }

        Path p = new Path(new Point(0,0), 0);
        return p.add(new Point((int)(random.nextDouble() * 3 - 1), (int)(random.nextDouble() * 3 - 1)), 0);
    }

    private List<Path> pathsAround(Path path, Map<Point, Integer> vision, Map<Integer, Integer> costs) {
        Point head = path.head();
        List<Path> results = new ArrayList<>();
        for (int i = -1; i <= 1; i++){
            for (int j = -1; j <= 1; j++){
                if (i == 0 && j == 0){
                    continue;
                }
                Point p = new Point(head.x + i, head.y + j);
                if (!vision.containsKey(p) || vision.get(p) == -1){
                    continue;
                }
                results.add(path.add(p, costs.get(vision.get(p))));
            }
        }
        return results;
    }

    private Map<Integer, Integer> decode(String genome) {
        int chunkLength = genome.length()/16;
        Map<Integer, Integer> costs = new HashMap<>();
        for (int i = 0; i < 16; i++){
            int runSize = 0;
            int cost = 0;
            for (int j = i * chunkLength; j < (i + 1) * chunkLength; j++){
                switch (genome.charAt(j)){
                    case '0':
                        runSize = 0;
                        break;
                    case '1':
                        cost += ++runSize;
                }
            }
            costs.put(i, cost);
        }
        return costs;
    }

    private class Path implements Comparable<Path>{

        Point head;
        Path parent;
        int length;
        int totalCost;

        private Path(){}

        public Path(Point point, int cost) {
            length = 1;
            totalCost = cost;
            head = point;
            parent = null;
        }

        public Point get(int index) {
            if (index >= length || index < 0){
                throw new IllegalArgumentException(index + "");
            }
            if (index == length - 1){
                return head;
            }
            return parent.get(index);
        }

        public Point head() {
            return head;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Path path = (Path) o;

            if (!head.equals(path.head)) return false;

            return true;
        }

        @Override
        public int hashCode() {
            return head.hashCode();
        }

        @Override
        public int compareTo(Path o) {
            return totalCost - o.totalCost;

        }

        public Path add(Point point, int cost) {
            Path p = new Path();
            p.head = point;
            p.totalCost = totalCost + cost;
            p.length = length + 1;
            p.parent = this;
            return p;
        }
    }
}

Answer 19

Gray-Color Lookahead (C++, ~1.35)

This one isn't doing very well on average, but on rare occasion it performs brilliantly. Unfortunately, we're being scored on geometric average (1.35), and not on maximum score (20077).

This algorithm works by just using 4-bit gray codes to map each color's score somewhere from -2 to 2 (with a bias towards the range [-1..1]), and computes the score of each move's tile and its next moves. It also uses a 2-bit gray code to determine the multiplier for the tile itself as well as the biasing factor for moving to the right. (Gray codes are much less susceptible to big jumps due to mutations, although they don't really do any favors for mid-codepoint crossover...)

It also does absolutely nothing to try to handle traps specially, and I suspect that might be the downfall (although I haven't added any instrumentation to the controller to test this theory).

For each possible move it determines a score, and among all the moves with the highest score it chooses randomly.

coord_t colorTileRanker(dna_t d, view_t v) {
    const int COLOR_OFFSET = 0; // scores for each color (4 bits each)
    const int SELF_MUL_OFFSET = 96; // 2 bits for self-color multiplier
    const int MOVE_MUL_OFFSET = 98; // 2 bits for move-forward multiplier

    static const int gray2[4] = {0, 1, 3, 2};
    static const int gray3[8] = {0, 1, 3, 2, 7, 6, 4, 5};

    // bias factor table
    const int factorTable[4] = {0, 1, 2, 1};

    const int selfMul = factorTable[gray2[dnaRange(d, SELF_MUL_OFFSET, 2)]]*2 + 9;
    const int moveMul = factorTable[gray2[dnaRange(d, MOVE_MUL_OFFSET, 2)]] + 1;

    // scoring table for the color scores
    static const int scoreValue[8] = {0, 1, 2, 3, 4, 3, 2, 1};

    std::vector<coord_t> bestMoves;
    int bestScore = 0;

    for (int x = -1; x <= 1; x++) {
        for (int y = -1; y <= -1; y++) {
            const int color = v(x, y);
            if ((x || y) && (color >= 0)) {
                int score = 0;

                // score for the square itself
                score += selfMul*(scoreValue[gray3[dnaRange(d, COLOR_OFFSET + color*3, 3)]] - 2);

                // score for making forward progress;
                score += moveMul*(x + 1);

                // score for the resulting square's surrounding tiles
                for (int a = -1; a <= 1; a++) {
                    for (int b = -1; b <= 1; b++) {
                        const int color2 = v(x + a, y + b);
                        if (color2 >= 0) {
                            score += scoreValue[gray3[dnaRange(d, COLOR_OFFSET + color2*3, 3)]] - 2;
                        }
                    }
                }

                if (score > bestScore) {
                    bestMoves.clear();
                    bestScore = score;
                }
                if (score >= bestScore) {
                    bestMoves.push_back({x, y});
                }
            }
        }
    }

    if (bestMoves.empty()) {
        return {v.rng.rint(2), v.rng.rint(3) - 1};
    }
    return bestMoves[v.rng.rint(bestMoves.size())];
}

On my most recent run, I got scores: 1 1 1 1 1 1 1 46 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 20077 1 1 1 2 1 1 1 1 1

I wish I could get more of the 20077s and fewer of the 1s. :)

Answer 20

Ruby - ProbabilisticScorePlayer

class ProbabilisticScorePlayer < Player
    Here = Vector2D.new( 0, 0)
    Forward = Vector2D.new( 1, 0)
    Right = Vector2D.new( 0, 1)
    Left = Vector2D.new( 0,-1)

    def vision_at(vec2d)
        v = @vision[vec2d.x+2][vec2d.y+2]
        v==-1?nil:v
    end

    def turn
        coords = [Forward]
        [Here,Forward].each{|x|
            [Here,Right,Left].each{|y|
                c = x+y
                if x!=y && vision_at c > -1
                  coords.push c if bit_at(vision_at c)==1
                  coords.push c if bit_at(vision_at(c+Forward)+16)==1
                  coords.push c if bit_at(vision_at(c+Right)+32)==1
                  coords.push c if bit_at(vision_at(c+Left)+48)==1
                  coords.push c if bit_at(vision_at(c+Forward+Right)+64)==1
                  coords.push c if bit_at(vision_at(c+Forward+Left)+80)==1
                end
            }
        }
        coords.sample(random: @rng)
    end
end

This highly non-deterministic rat calculates the probability to go on a space by it's neighborhood. The first 16 slots in genome represent the 16 colors. 1 in a slot means the color is good to step on, 0 means bad. The next 16 hold the same for the space in front of your target, and so on.

The main advantage of the probabilistic approach is that it is nearly impossible to get stuck behind a wall for long. The disadvantage is that you will almost never get a near perfect rat.

Answer 21

C++, TripleScore, Score: 100~400

First of all, my score varies greatly over multiple runs (mainly because of the number of 1's).

The core calculates the score of 5 directions: up, down, forward-up, forward and forward-down. First the score of up and down are calculated, than the results are compared to the value of staying in place. If staying in place is better than moving up or down, these directions will not be chosen (so it must go forward). This is to prevent bouncing (up,down,up,down,...) between 2 spots.

Now the 3 other directions are scored: forward-up, straight forward and forward-down. From all investigated directions the ones with the highest score are kept and 1 of them is chosen at random.

Scoring a direction: TripleScore calculates the score of a movement using 3 subscores:

• The score of the color of the destination (depends on the dna, as in colorScorePlayer)
• The score of going forward (depends on the dna)
• The maximum score of taking a forward move from the destination (multiplied by a factor that is stored in the dna)

As with other answers, the score greatly depends on the number of 1-scores that are returned.

#define CHUNKSIZE 5 //We have 20 values so 5 bits/value
#define MAXVALUE 32 //2^CHUNKSIZE
#define AVGVALUE MAXVALUE/2

#define DNASEGMENT(dna, i) dnarange(dna, i*CHUNKSIZE, CHUNKSIZE)
#define DNA_COLOR 0
#define DNA_FORWARD 16
#define DNA_LOOKAHEAD 17

//Get the score for a specific move
int calcscore(dna_t dna, view_t view, int x, int y, bool final){
  if (view(x,y) == OUT_OF_BOUNDS){
    //We cant go there
    return -MAXVALUE;
  }
  //The score of the color
  int s = DNASEGMENT(dna, DNA_COLOR+view(x,y))-AVGVALUE;
  //The score of going forward
  s += x*DNASEGMENT(dna, DNA_FORWARD);

  //Get the children or not
  if (!final){
    int max=-MAXVALUE;
    int v;
    //Get the maximum score of the children
    for (int i=-1; i<2; ++i){
        v = calcscore(dna, view, x+1, y+i, true);
        if (v>max){
            max=v;
        }
    }
    //Apply dna factor to the childs score
    s += (max * DNASEGMENT(dna, DNA_LOOKAHEAD))/AVGVALUE;
  }
  return s;
}

coord_t TripleScore(dna_t dna, view_t view) {
  int maxscore = -100;
  int score;
  coord_t choices[5]; //Maximum 5 possible movements
  int maxchoices = 0;
  int zeroscore = calcscore(dna, view, 0, 0, false);

  //Go over all possible moves and keep a list of the highest scores
  for (int x=0; x<2; ++x){
    for (int y=-1; y<2; ++y){
        if (x | y){
            score = calcscore(dna, view, x, y, false);
            if (score > maxscore){
                maxscore = score;
                choices[0] = {x, y};
                maxchoices = 1;
            }else if (score == maxscore){
                choices[maxchoices++] = {x, y};
            }
        }
    }
    if (!x && maxscore <= zeroscore){
        //I will NOT bounce!
        maxscore = -100;
    }
  }

  return choices[view.rng.rint(maxchoices)];
}

Answer 22

LeapForward, Python 2

Not particularly ground-breaking but it is my only attempt that performed ok-ish.

class LeapForward(Player):
  def __init__(self):
    Player.__init__(self)
    self.coords = [Coordinate( 1, 0),
                   Coordinate( 1,-1),
                   Coordinate( 1, 1)]
    self.n_moves = len(self.coords)

  def turn(self):
    notOKColors = [self.bit_chunk(4*n,4) for n in range(4,8)]
    notOKMap = [Coordinate(x-2,y-2) for x in range(0,5) for y in range(0,5) if self.vision[y][x] not in notOKColors]
    goTo = [c for c in self.coords if c in notOKMap]
    if not goTo:
      goTo = [Coordinate(1,0)]
    return random.choice(goTo)

Basically, it codes four colors (each 4 bits) to avoid, in the genome. It then goes forward to a color that is not in that list. If all colors are bad, it still leaps forward to the unknown.

Answer 23

Java - IAmARobotPlayer - Score 3.7

I just created this robot rat for comparision with another (not very interesting so far) program I made. It does not score well overall but if it scores somewhere, it will get many rats throu. The idea is that it will only look at the three cells in front of it, each cell is good or bad. This gives a binary number. Then it is going to look up this number in its genome, take the three consecutive bits, also conver them to a number and take the action that is stored under this number. So it acts always the same when it encounters the same situation.

package game.players;
import java.awt.*;
import java.util.Map;
public class IAmARobotPlayer extends Player{
    private static final Point[] possibleMoves = {new Point(1,-1), new Point(1,0), new Point(1,1), new Point(0,-1), new Point(0,1), new Point(1,-1), new Point(1,0), new Point(1,1)};
    private int isGood(int pos,Map<Point,Integer> vision, char[] genomeChar){
        int value = vision.get(new Point(1,pos));
        if(value ==-1){
            return 0;
        } else {
            return genomeChar[84+value]-'0';
        }
    }

    @Override
    public Point takeTurn(String genome, Map<Point, Integer> vision) {

        char[] genomeChar = genome.toCharArray();
        int situation = 4*isGood(1,vision,genomeChar)+2*isGood(0,vision,genomeChar)+1*isGood(-1,vision,genomeChar);
        int reaction = 4*(genomeChar[3*situation+0]-'0')+2*(genomeChar[3*situation+1]-'0')+1*(genomeChar[3*situation+2]-'0');
        return possibleMoves[reaction];

    }
}

Result:

Individual scores: 1, 1, 332, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 47560, 15457, 1, 
Your final score is 3.7100115087136234

Answer 24

Cautious Specimens - C++ - scores about 2030 over 200 runs

This uses the colour part (16x4 bits) of the DNA encoding from Blind Faith but leaves the rest (36bits) of the DNA entirely unused.

The encoding for a colour is either:

• 10XX - for safe squares;
• 11XX - for lethal squares; and
• 0000 through 0111 - for the 8 types trap squares.

Where X indicates unused bits. Given that only 2-of-16 colours are traps that will use all 4 of their bits (and only if the trap is offset, which will be the case 8-of-9 times) then there are typically going to be 64 unused bits - the theory is that mutations which affect any of these unused bits are not going to wreck the genome and stability is better than any fancy solutions that can use those remaining bits.

The specimens then use this to plan a safe route within a 7x7 grid centred on themselves (the 5x5 their vision allows plus 1 square on each side to allow for offset traps) prioritising moving the greatest distance forward after 3 moves.

I did initially start building in some checks to ensure that the fact that the colour the specimen is currently standing on is not lethal corresponds with the genome and flagging any erroneous colours as squares of UNSURE safety (and their adjacent squares) - however it added significant complication for little-to-no gain compared to marking those squares as SAFE and killing a few additional specimens. I will return to this if I have time.

#include <initializer_list>
#include <vector>

enum class D { SAFE, LETHAL,TRAP_N, TRAP_NE, TRAP_E, TRAP_SE, TRAP_S, TRAP_SW, TRAP_W, TRAP_NW, UNSURE };
enum class X { SAFE, LETHAL, UNSURE };

inline void checkLocation( color_t color, D (&dna)[16], D check )
{
    if ( color != OUT_OF_BOUNDS && dna[color] == check )
        dna[color] = D::UNSURE;
}

inline void updateMapLocation( X (&map)[7][7], unsigned int x, unsigned int y, const X& safety ){
    if (        ( safety == X::LETHAL && map[x][y] != X::LETHAL )
            || ( safety == X::UNSURE && map[x][y] == X::SAFE ) )
        map[x][y] = safety;
}

inline unsigned int isSafePath( X (&map)[7][7], coord_t p )
{
    return map[p.x][p.y] == X::SAFE ? 1 : 0;
}
inline unsigned int isSafePath(X (&map)[7][7],coord_t p,coord_t q,coord_t r){
    if ( isSafePath( map,p ) )
        if ( isSafePath( map, q ) )
            return isSafePath( map, r );
    return 0;
}

inline unsigned int isSafeEast( X (&map)[7][7], coord_t p )
{
    if ( !isSafePath( map, p ) )
        return 0;
    if ( p.x == 6 )
        return 1;
    return isSafeEast(map,{p.x+1,p.y-1})
            +isSafeEast(map,{p.x+1,p.y+0})
            +isSafeEast(map,{p.x+1,p.y+1});
}

template<typename T> inline T max(T a,T b){return a>=b?a:b;}
template<typename T, typename... A> inline T max(T a,T b,A... c){return max(max(a,b),c...); }

coord_t cautiousSpecimins( dna_t d, view_t v ) {
    X map[7][7] = { { X::SAFE } };
    D dna[16] = { D::UNSURE };
    for ( color_t i = 0; i < 16; i++ )
    {
        if ( d[4*i] == 1 )
        {
            dna[i] = d[4*i + 1] == 1 ? D::LETHAL : D::SAFE;
        }
        else
        {
            switch ( dnarange( d, 4*i + 1, 3 ) )
            {
                case 0: dna[i] = D::TRAP_N; break;
                case 1: dna[i] = D::TRAP_NE; break;
                case 2: dna[i] = D::TRAP_E; break;
                case 3: dna[i] = D::TRAP_SE; break;
                case 4: dna[i] = D::TRAP_S; break;
                case 5: dna[i] = D::TRAP_SW; break;
                case 6: dna[i] = D::TRAP_W; break;
                case 7: dna[i] = D::TRAP_NW; break;
                default: dna[i] = D::UNSURE; break;
            }
        }
    }
    if ( v(-1, 0) != OUT_OF_BOUNDS )
        checkLocation( v( 0, 0), dna, D::LETHAL );

    if ( v(-1, 0) != OUT_OF_BOUNDS )
        for ( unsigned int y = 0; y < 7; ++ y )
            map[2][y] = X::LETHAL;

    if ( v(-2, 0) != OUT_OF_BOUNDS )
        for ( unsigned int x = 0; x < 2; ++x )
            for ( unsigned int y = 0; y < 7; ++ y )
                map[x][y] = X::LETHAL;

    if ( v( 0, 1) == OUT_OF_BOUNDS )
        for ( unsigned int x = 0; x < 7; ++x )
                map[x][4] = X::LETHAL;

    if ( v( 0, 2) == OUT_OF_BOUNDS )
        for ( unsigned int x = 0; x < 7; ++x )
            for ( unsigned int y = 5; y < 7; ++ y )
                map[x][y] = X::LETHAL;

    if ( v( 0,-1) == OUT_OF_BOUNDS )
        for ( unsigned int x = 0; x < 7; ++x )
                map[x][2] = X::LETHAL;

    if ( v( 0,-2) == OUT_OF_BOUNDS )
        for ( unsigned int x = 0; x < 7; ++x )
            for ( unsigned int y = 0; y < 2; ++ y )
                map[x][y] = X::LETHAL;

    checkLocation( v( 1, 1), dna, D::TRAP_SW );
    checkLocation( v( 1, 0), dna, D::TRAP_W  );
    checkLocation( v( 1,-1), dna, D::TRAP_NW );
    checkLocation( v( 0,-1), dna, D::TRAP_N  );
    checkLocation( v(-1,-1), dna, D::TRAP_NE );
    checkLocation( v(-1, 0), dna, D::TRAP_E  );
    checkLocation( v(-1, 1), dna, D::TRAP_SE );
    checkLocation( v( 0, 1), dna, D::TRAP_S  );

    for ( int x = 1; x <= 5; ++x )
    {
        for ( int y = 1; y <= 5; ++y )
        {
            switch( dna[v(x-3,y-3)] )
            {
                case D::LETHAL : updateMapLocation( map, x+0, y+0, X::LETHAL ); break;
                case D::TRAP_N : updateMapLocation( map, x+0, y+1, X::LETHAL ); break;
                case D::TRAP_NE: updateMapLocation( map, x+1, y+1, X::LETHAL ); break;
                case D::TRAP_E : updateMapLocation( map, x+1, y+0, X::LETHAL ); break;
                case D::TRAP_SE: updateMapLocation( map, x+1, y-1, X::LETHAL ); break;
                case D::TRAP_S : updateMapLocation( map, x+0, y-1, X::LETHAL ); break;
                case D::TRAP_SW: updateMapLocation( map, x-1, y-1, X::LETHAL ); break;
                case D::TRAP_W : updateMapLocation( map, x-1, y+0, X::LETHAL ); break;
                case D::TRAP_NW: updateMapLocation( map, x-1, y+1, X::LETHAL ); break;
//              case D::UNSURE : updateMapLocation( map, x+0, y+0, X::SAFE );
//                               updateMapLocation( map, x+0, y+1, X::UNSURE );
//                               updateMapLocation( map, x+1, y+1, X::UNSURE );
//                               updateMapLocation( map, x+1, y+0, X::UNSURE );
//                               updateMapLocation( map, x+1, y-1, X::UNSURE );
//                               updateMapLocation( map, x+0, y-1, X::UNSURE );
//                               updateMapLocation( map, x-1, y-1, X::UNSURE );
//                               updateMapLocation( map, x-1, y+0, X::UNSURE );
//                               updateMapLocation( map, x-1, y+1, X::UNSURE );
//                               break;
                default        : break;
            }           
        }
    }

    unsigned int north = isSafeEast(map,{4,4});
    unsigned int east  = isSafeEast(map,{4,3});
    unsigned int south = isSafeEast(map,{4,2});
    unsigned int mx    = max( north, east, south );
    unsigned int sz;
    std::vector<coord_t> dir;
    if ( mx > 0 )
    {
        if ( north == mx ) dir.push_back( {+1,+1} );
        if ( east  == mx ) dir.push_back( {+1,+0} );
        if ( south == mx ) dir.push_back( {+1,-1} );

        return dir[v.rng.rint(dir.size())];
    }


    north = isSafePath(map,{4,4},{5,5},{5,6})
            + isSafePath(map,{4,4},{4,5},{5,6});
    south = isSafePath(map,{4,2},{5,1},{5,0})
            + isSafePath(map,{4,2},{4,1},{5,0});
    mx = max( north, south );
    if ( mx > 0 )
    {
        if ( north == mx ) dir.push_back( {+1,+1} );
        if ( south == mx ) dir.push_back( {+1,-1} );

        return dir[v.rng.rint(dir.size())];
    }

    north = isSafePath(map,{3,4},{4,5},{5,6});
    south = isSafePath(map,{3,2},{4,1},{5,0});
    mx = max( north, south );
    if ( mx > 0 )
    {
        if ( north == mx ) dir.push_back( {+0,+1} );
        if ( south == mx ) dir.push_back( {+0,-1} );

        return dir[v.rng.rint(dir.size())];
    }

    north = 2*isSafePath(map,{4,4},{4,5},{4,6})
            + 1*isSafePath(map,{4,4},{3,5},{4,6});
    south = 2*isSafePath(map,{4,2},{4,1},{4,0})
            + 1*isSafePath(map,{4,2},{3,1},{4,0});
    mx = max( north, south );
    if ( mx > 0 )
    {
        if ( north == mx ) dir.push_back( {+1,+1} );
        if ( south == mx ) dir.push_back( {+1,-1} );

        return dir[v.rng.rint(dir.size())];
    }

    north = isSafePath(map,{3,4},{4,5},{4,6})
            + isSafePath(map,{3,4},{3,5},{4,6});
    south = isSafePath(map,{3,2},{4,1},{4,0})
            + isSafePath(map,{3,2},{3,1},{4,0});
    mx = max( north, south );
    if ( mx > 0 )
    {
        if ( north == mx ) dir.push_back( {+0,+1} );
        if ( south == mx ) dir.push_back( {+0,-1} );

        return dir[v.rng.rint(dir.size())];
    }

    north = isSafePath(map,{2,4},{3,5},{4,6});
    south = isSafePath(map,{2,2},{3,1},{4,0});
    mx = max( north, south );
    if ( mx > 0 )
    {
        if ( north == mx ) dir.push_back( {-1,+1} );
        if ( south == mx ) dir.push_back( {-1,-1} );

        return dir[v.rng.rint(dir.size())];
    }

    north = isSafePath(map,{3,4},{3,5},{3,6})
            + isSafePath(map,{3,4},{2,5},{3,6});
    south = isSafePath(map,{3,2},{3,1},{3,0})
            + isSafePath(map,{3,2},{2,1},{3,0});
    mx = max( north, south );
    if ( mx > 0 )
    {
        if ( north == mx ) dir.push_back( {+0,+1} );
        if ( south == mx ) dir.push_back( {+0,-1} );

        return dir[v.rng.rint(dir.size())];
    }

    north = isSafePath(map,{2,4},{3,5},{4,6});
    south = isSafePath(map,{2,2},{3,1},{4,0});
    mx = max( north, south );
    if ( mx > 0 )
    {
        if ( north == mx ) dir.push_back( {-1,+1} );
        if ( south == mx ) dir.push_back( {-1,-1} );

        return dir[v.rng.rint(dir.size())];
    }

    return {-1,-1};
}

Sample Scores:

Scores: 421155 2 129418 71891 90635 1 211 1111987 29745 7 2200750 41793 50500 45 2012072 2 485698 1 110061 1554720 210308 249336 2 1 262110 17 3 19 1719139 23859 45118 3182784 318 2 1 15572 14 2822954 18 11 2 3 15954 1331392 2296280 135015 1 360826 1 692367 4 244775 4814645 3749144 3 1 660000 1 11 3688002 3920202 3428464 123053 1 243520 86 9 6 289576 195966 549120 220918 9 1 43 71046 5213 118177 150678 54639 3 200839 1 3 6 1978584 1514393 119502 1 1 137695 184889 337956 1 1 441405 133902 991 1 4137428 1 1427115 3340977 1 2 1 55559 11 1 94886 30270 1 6 3 69394 264780 6877 47758 128568 1 116672 130539 163747 96253 1 2654354 1 141 58212 1613661 27 9504 1 2474022 843890 1 59 3110814 2353731 150296 313748 2590241 6 5970407 1434171 2 334715 141277 1 56810 2964306 51544 61973 715590 1 106 900384 50948 2 34652 108096 391006 1 2969764 47625 1 24 30481 44 8 1 18 2094036 106461 3080432 75 620651 16 71730 282145 275031 17 1 8 15 121731 18 2 1 1 495868 3252390 6 1 63712 7 3733149 13380 1 1
Geometric mean score: 2030.17

Max Score during testing: 8,150,817 Specimens Saved.