Snowball Fight

Objective

Win Snowball Fight on the "Impossible" difficulty level.

Analysis

Snowball Fight is a variation on the classic game Battleship, but played with snow forts instead of naval ships. The board layout is generated by the computer based on a 32-bit seed value, such that any given layout can be repeated by using the same seed value.

The initial seed is randomly generated, but can be overridden by the user in the Easy level. The user can win repeatedly by playing with the same seed value over and over. The seed cannot be specified by the user in the Hard level, however the user can cheat by copying the displayed seed value into an Easy game to determine the snow fort positions, then use that information to win the Hard game.

On the Impossible level, the seed value cannot be overridden or found anywhere on the screen. If you look at the page source, however, you'll find 624 randomly generated numbers in the comments that were discarded by the computer before selecting one as the seed for that game.

The premise behind this terminal is that while pseudo-random number generators (PRNG) can produce a statistically sound series of random numbers, they are highly predictable under certain circumstances. In the case of MT19937, the most widely used PRNG, you can predict the numbers it will select if you know 624 of the most recently generated numbers.

Tip

Watch Tom Liston's talk about Mersenne Twisters for background on this topic.

Solution

#!/usr/bin/env python3

# Requires mt19937.py from https://github.com/tliston/mt19937
import mt19937
import random
import re

if __name__ == "__main__":
    # create an instance of mt19937 with seed 0
    myprng = mt19937.mt19937(0)
    # load the known random numbers as an array
    f = open("numbers.txt", "r")
    content = f.read()
    regex = r"(\d{6,10})"
    randnums = re.findall(regex, content)
    # Untemper the random numbers and store them in the MT array
    for i in range(len(randnums)):
        myprng.MT[i] = mt19937.untemper(int(randnums[i]))
    # Create some additional random numbers
    print("Now, predict the next random numbers...")
    for i in range(5):
        r2 = myprng.extract_number()
        print("%i: %10.10i" % (i, r2))

Step 1: Start the Snowball Fight game in Impossible mode and copy the page source code including all of the discarded random numbers into a file numbers.txt.

Step 2: Run the program and obtain the predicted next random number.

$ ./predict.py
Now, predict the next random numbers...
0: 3181216032
1: 3149432775
2: 2425293170
3: 0659190009
4: 1200190550
5: 2700544682

Step 3: Open another instance of Snowball Fight and play the game in Easy Mode using the predicted random number. Record all of the positions where you made a hit.

Step 4: Return to the Snowball Fight game that's in Impossible mode and play it using the positions you recorded from the Easy game.