Nerd thought of the week - Scotland Yard
So my nerdy thoughts of the week have been focused on the board game Scotland Yard. Think fugitive the board game. Mr X has to survive 30 rounds without getting caught. Five collaborating detectives have to track him down. Each turn everybody can take a taxi, bus, or subway (if available at your location). Mr X almost always has to reveal what mode of transportation he used, but only actually shows himself on the board every 4ish turns. True to the bureaucratic spirit of a police force, the detectives have a limited numbers of taxi, bus, and subway fair tickets to get the job done.
At first glance it looked like a very strait forward graph problem. Then I realized there were lots of special considerations to the algorithms.
1. Mr X doesn't have a destination, he is simply taking evasive action.
2. The detectives have a moving target that they can only see every 4ish turns. They have to extrapolate where he might be the rest of the time.
3. Collisions - Only one detective may be in a specific location at a time.
4. Collaboration - you must coordinate all of the detectives together to effectively coral Mr X.
5. Resources - All links have a cost of one, but of three (actually 4) different kinds of resources. A taxi fair ticket does not work on the bus or subway and vice versa. You will run out of at least one kind and be significantly limited in your effectiveness. Mr X has unlimited fairs, except for the special black ticket that lets him use any type of transit (and swim across the river) without telling you what type he took.
(I can't decide if I want to actually implement the game / algorithms, or just discuss them. For a change of pace I'm actually doing a reasonable amount of coding at work, so this might have to wait.)
Thoughts?
At first glance it looked like a very strait forward graph problem. Then I realized there were lots of special considerations to the algorithms.
1. Mr X doesn't have a destination, he is simply taking evasive action.
2. The detectives have a moving target that they can only see every 4ish turns. They have to extrapolate where he might be the rest of the time.
3. Collisions - Only one detective may be in a specific location at a time.
4. Collaboration - you must coordinate all of the detectives together to effectively coral Mr X.
5. Resources - All links have a cost of one, but of three (actually 4) different kinds of resources. A taxi fair ticket does not work on the bus or subway and vice versa. You will run out of at least one kind and be significantly limited in your effectiveness. Mr X has unlimited fairs, except for the special black ticket that lets him use any type of transit (and swim across the river) without telling you what type he took.
(I can't decide if I want to actually implement the game / algorithms, or just discuss them. For a change of pace I'm actually doing a reasonable amount of coding at work, so this might have to wait.)
Thoughts?