Railroads, an evolutionary approach to problem solving *

Static Badge Static Badge

Railroads is a 2D game in which the goal is to make a path for trains to arrive at their assigned destination. In it's simplest form, the world is made up of a grid of tiles, where very tile can be:

  1. A straight junction connecting two tiles horizontally or vertically.

  2. A 2-turn junction connecting two neighbouring tiles (4 tiles due to rotations).

  3. A 3-turn junction connecting 3 neighbouring tiles (4 with rotations).

  4. A crossroads connecting all 4 neighbouring tiles.

Players are able to change each tile into whichever tile they among the aforementioned options. The goal is to create a railroad network that will allow N trains, each with an origin and destination tile to finish their route. A solution is always guaranteed given that the worst case, we can fill the entire grid with crossroads thereby obtaining a fully connected graph. However, to avoid this, tiles are priced accordingly (number of tiles it connects), and the goal is not only to find a solution but to find one that requires a minimal number of tile swaps, and minimal penalty (tile types).

This assignment requires students to implement an evaluator that given a game world, scores the the proposed solution. To do this, a DFS algorithm can be used to search for a path between starting tile, and ending tile for each train. Trains that cannot reach the destination should impose a significant penalty to the final score.

To generate solutions, a genetic algorithm should be used to evolve an initial solution (assumed random assignment of tiles) towards a network in which all trains are able to reach their destination. The solution should continuously render the best solution currently found.

Implementation guidelines

  1. Running the program:

    • The program can be ran in different modes (sequential, parallel and distributed) by specifying a parameter.

    • User can specify the size of the 2d world of tiles, and number of trains (origin and destination are randomly(seeded) given).

    • The program measures run-time needed to compute a given number of iterations of the genetic algorithm.

  2. Implementation details

    • The fitness function (simulation) must be computed in parallel.

    • The implementation must adapt automatically to the hardware it is being ran on (Physical CPU's, Cores, Memory, etc..);

    • Wherever randomness is used a seed must be provided in order to compare solutions.

Testing

There are multiple tests worth performing. Analysis should include those that show interesting behaviours, and/or correlations. Given the problem is defined with the size of the world as well as the number of trains, both variables must be tested to estimate the impact on the complexity independently. At the same time, the genetic algorithm sorts solutions based on the fitness function, which is also worth looking at. What is the fitness progression over time for each of those combinations as well as different implementations. For more specific advice reach out the professor and/or assistant.