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
to15
, 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:
- 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.
- If the specimen's age is 100, it dies. Otherwise, increment its age by 1.
- 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.
- If the target cell is a wall, then the move is changed to (0,0).
- If the target cell is a teleporter, the specimen is moved by the teleporter's offset. Note: This step is performed once, not iteratively.
- 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.
- If the specimen occupies a goal cell, score a point, move the specimen to a random starting cell and reset its age to 0.
- If there are less than two specimens left on the board, the game ends.
- 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
ortkinter
.
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.
'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.'
\$\endgroup\$