Martin Gardner
Sim, Chomp and Race Track (Mathematical Games, January 1973):
Race Track, virtually unknown in this country, is a truly remarkable simulation of automobile racing. I do not know who invented it. It was called to my attention by Jurg* Nievergelt, a computer scientist at the University of Illinois, who picked it up on a recent trip to Switzerland.
The game is played on graph paper. A racetrack wide enough to accommodate a car for each player is drawn on the sheet. The track may be of any length or shape, but to make the game interesting it should be strongly curved [see illustration]. Each contestant should have a pencil or pen of a different color. To line up the cars, each player draws a tiny box just below a grid point on the starting line. In the example illustrated the track will take three cars, but to simplify things a race of two cars is shown. Lots can be drawn to decide the order of moving. In the sample game, provided by Nievergelt, Black moves first.
You might suppose that a randomizing device now comes into play to determine how the cars move, but such is not the case. At each turn a player simply moves his car ahead along the track to a new grid point, subject to the following three rules:
1. The new grid point and the straight line segment joining it to the preceding grid point must lie entirely within the track.
2. No two cars may simultaneously occupy the same grid point. In other words, no collisions are allowed. For instance, consider move 22. Green, the second player, would probably have preferred to go to the spot taken by Black on his 22nd move, but the no-collision rule prevented it.
3. Acceleration and deceleration are simulated in the following ingenious way. Assume that your previous move was k units vertically and m units horizontally and that your present move is k' vertically and m' horizontally. The absolute difference between k and k' must be either 0 or 1, and the absolute difference between m and m' must be either 0 or 1. In effect, a car can maintain its speed in either direction or it can change its speed by only one unit distance per move. The first move, following this rule, is one unit horizontally or vertically, or both.
The first car to cross the finish line wins. A car that collides with another car or leaves the track is out of the race. In the sample game Green slows too late to make the first turn efficiently. He narrowly avoids a crash, and the bad turn forces him to fall behind in the middle of the race. He takes the last curve superbly, however, and he wins by crossing the finish line one move ahead of Black.
Nievergelt programmed Race Track for the University of Illinois's Plato IV computer-assisted instruction system, which uses a new type of graphic display called a plasma panel. Two or three people can play against one another or one person can play alone. The game became so popular that the authorities made it inaccessible for a week to prevent students from wasting too much time on it.
Addendum I (Mathematical Games, May 1973):
Many readers felt that Race Track rules should not allow one car to win if another car on the same move could also cross the finish line. They suggested giving the win to the car farthest from the finish line at the end of the move. Joe Crowther was the first of many readers who proposed drawing one or two patches on the roadway to represent oil slicks. Cars are required to move at a constant speed and direction when passing wholly or partly through each patch. J.P. Schell, in addition to oil slicks, proposed adding upgrades and downgrades to force cars to speed up or slow down, as well as stationing pretty girls along the track to distract drivers. Others suggested adding pit stops here and there and requiring a driver to lose one move by coming to zero velocity within any one pit of his choice. Some readers thought it would simplify the game if the finish line were always drawn along one of the grid lines.
David Popoff** suggested a fast-acceleration move. Any time that a car slows to a full stop it can on the next move go any desired distance in either or both of the two directions. Tom Gordon, who welcomed the game as a teaching device for his high school physics students, added a power-braking option that allows a car to reduce both coordinates by two units, provided the move continues the preceding move in a straight line.
C.R.S. Singleton described two novel variants of the game: (1) Instead of a track, numbered gates are marked on the graph. Cars must pass through the gates in numerical order. (2) A series of numbered checkpoints are substituted for the track. Cars must visit each checkpoint by ending a move on that point.
Michael D. Greenberg and his friends at the Westinghouse Aerospace Division in Baltimore adopted two rules to offset the advantage of a first move: (1) Slant the starting line (as in actual racing) and allow the second player to choose between the two starting points. (2) Allow cars to occupy the same point at the same time. They also preferred to draw the track along grid lines to avoid arguments over whether a point was on the track or inside it. Two British readers, Giles Vaughan-Williams and John Kinory, devised rules allowing cars to brake and skid when rounding a sharp curve at high speed.
Addendum II (Knotted Doughnuts, October 1986):
I have been unable to determine the origin of Race Track. A car-race game very similar to it appeared under the name of Le Zip in a French book by Pierre Berloquin, Le Livre des Jeux, published about 1971***. It is reprinted in Berloquin's book 100 Jeux de Table (Paris, 1976). A version of Race Track appeared as game 13 in the Hewlett-Packard Games Pac 1 book (1976) for use with the company's HP-67 and HP-97 calculators.
_______________________________________________________________________________________________
* actually Jürg, who told me (July 2011): "Some acquaintance showed me the game, I don't recall who. It had no name."
** the name was changed (presumably corrected) to David Pope in Knotted Doughnuts
*** September 1970
Some links:
Jakob Schmid: VectorRace (2005)
Steve Baker: Graph Racers (2007)
Dan Eastwood: Graph Paper Race (2009)
Jeff Erickson: How hard is optimal racing? (2009)
Markus Holzer & Pierre McKenzie: The Computational Complexity of RaceTrack (minus two pages, Fun with Algorithms 2010)
David Low: Teaching Inductively (UniServe Science 2010)
