MiniZinc plays Dragster | … nearly 42 …

What happens if a modern constraint satisfaction and optimization program decides to play a Video Game Classic?

I’m a fan of old Video Games (80s games) and recently I found an interesting debate about the world record of the Atari’s videogame Dragster by Activision.

T.R. [I’m polite :-)] claimed to achieve a time of 5.51 in Dragster on 1982 and after 35 years nobody was able to replicate such time: the best time achieved by a human player is 5.61, and with a Tool-Assisted Speedrun (TAS) is 5.57.

Omnigamer disassbled the original cartridge of the game and anlyzed the code. He came to the following conclusion: 5.51 is not achievable with a normal gameplay (assuming that the hardware behavior is consistent with the technical specifications). Even 5.54, claimed to be the best possible time by the Activision’s game developers, seems impossible. Twin Galaxies decided to ban T.R. and cancel his world record.

Omnigamer made a publicly available interactive spreadsheet with the rules of the game; if you change the values of “Gas” and “Shift” in the spreadsheet, you get the exact behaviour of the game frame by frame. For more details about the game model see the first page of the spreadsheet or look this detailed video explanation.

I decided to write a MiniZinc program (MiniZinc is a powerful and open-source constraint modeling language) to simulate the gameplay and see what happens. Note that MiniZinc implicitly tries ALL POSSIBLE combinations of Gas, Shift, starting Tach and Starting Frame.

In short, the “computer-verified” results are:

MiniZinc correctly played the game achieving 5.57;
The maximum total distance achievable is 97.3828125 (=24930 in-game distance);
A time < 5.57 is not possible;
If one could start from 2nd gear, then 5.51 would be achievable.

These are the definitive (and already known) results about Dragster unless the game model is wrong (I myself spent some time on the disassembly of the game and it seems correct).

Here you can download and play with the MiniZinc Dragster source code (remember to choose the built-in Chuffled solver in order to get a solution in a reasonable time):

Download dragster.mzn source code

This is the sequence of Shift/Gas moves generated by MiniZinc that achieve a “regular” 5.57 (and max distance 97.38)

STARTFRAME = 12;
STARTTACH = 24;
Shift=array1d(0..167,[
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,
0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,
0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,
0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]);
Gas=array1d(0..167,[
0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,
0,0,1,1,1,1,0,1,1,1,0,0,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,
1,1,0,0,1,0,1,0,0,1,0,0,0,1,1,1,1,1,1,1,1,0,1,1,0,0,1,0,1,1,
1,0,0,0,1,1,1,1,1,0,1,1,0,0,0,1,1,1,1,1,1,0,0,1,1,1,0,0,0,1,
0,1,0,0,1,0,0,1,0,1,1,1,1,1,0,1,1,1,0,0,1,1,0,1,0,1,0,1,0,1,
0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0]);

It took MiniZinc about 7 minutes to calculate the optimal run.

If we allow MiniZinc to start from 2nd gear, then this is a sequence of moves that achive a “cheated” 5.51 time and max dist ~97.25 (internal dist. 24898):

% Change 
% constraint GEAR[0] = 2;
% in the source code!!!
STARTFRAME = 0;
STARTTACH = 30;
Shift=array1d(0..165,[
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,
0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,
0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0]);
Gas=array1d(0..165,[
1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,
1,0,1,1,1,1,1,1,1,1,1,0,0,1,1,1,0,0,1,1,1,0,1,1,1,1,1,0,1,0,
1,0,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,0,
0,1,1,1,0,1,0,1,1,0,0,1,0,1,1,1,0,0,1,1,0,1,0,1,0,1,0,1,0,1,
0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1]);

… if we fill the spreadsheet with these values after setting Initial gear = 2, we indeed get a “cheated” 5.51:

The full outputs of the MiniZinc runs is here: results.txt.

Leave a Reply Cancel reply