This Programme Can Read Your Mind

I was looking at a website which allows you to play Rock-Paper-Scissors against an AI that learns to beat you by attempting to find patterns in the moves that you choose. The link to the website can be found here.

I wanted to make my own, so after a small bit of searching I found a blog post detailing a method of predicting game moves. The blog post referencess and makes use of “n-grams”. It took me a while to understand the concept, but in the end I got it and as a result was able to do the following:

• Make my own game
• Create a programme that can win against any AI that uses this technique

After performing more searching, I came to a webpage by Adam Pearce that presents a game where you have to press either the left or right keys and the computer tries to predict which key you’ll press. The link to that webpage can be found here. Pearce’s website lists another website, written by Nick Merill, as inspiration for its creation. The website has a game that’s quite similar to Pearce’s one, it can be found here.

What Pearce’s webpage does is implement an “Aaronson oracle”, it looks at my previous moves and finds all “5-grams” from them, that is to say that it finds all sequences of five moves that I’ve ever performed. Once it has done that, it looks at my last four moves and find the probability of the next key in the current sequnce being the left key and the probability of it being the right key. The AI then picks the picks the key with the highest probability of being chosen. Effectively, the AI has created a model of how I pick which key to press and is reported to average somewhere around 70% accuracy. (You can try it out for yourself)

If I can recreate that model, then I know what key the AI thinks I’m going to press and can just press the other key! The code is open source but I didn’t look at the source beforehand because I wanted to create the algorithm from scratch.

Essentially, my code for predicting scores went as follows

def generate_ngrams(sequence, n): # This function generates ngrams
    assert len(sequence) >= n
    ngrams = []
    for i in range(len(sequence) - n + 1):
        ngrams.append(sequence[i:i+n])   
    return ngrams

def predict(sequence, n, actions, dominant=None):
    ngrams = generate_ngrams(sequence, n) # Generate list of possible move sequences
    last_moves = sequence[-(n-1):] # Looks at the last `n` moves
    assert len(last_moves) == n-1
    prediction = None
    probability = -1
    for action in actions: # Finds the probability of each possible move and predicts the one with the highest probability. If two moves have the same probability of occuring, the 'dominant' move will be chosen
        new_prediction = last_moves + [action]
        new_probability = ngrams.count(new_prediction)
        if new_probability > probability:
            prediction = new_prediction
            probability = new_probability
        if dominant and new_prediction == dominant and new_probability == probability:
                prediction = new_prediction
                probability = new_probability
    return prediction, (probability*100)//len(ngrams) # Returns the prediction and its estimated probability of being correct

To apply this to the site, I wrote a function that generates moves that will always beat the AI, here’s the code

def deoracle_pearce(upto=100): # `upto` is the number of moves the function will generate
    moves = []
    actions = list("LR") # The moves are either left or right

    for i in range(upto):
        if i < 5: # For the first five moves, the AI picks left, so this function picks right
            new_move = "R"
            predicted_probability = 100
        else: # Predict which move the AI will choose then pick the opposite
            predicted_move, predicted_probability = predict(moves, 5, actions)
            if predicted_move == "L":
                new_move = "R"
            else:
                new_move = "L"
        moves.append(new_move)
        print(f"{i}) {new_move}, {predicted_probability}%")

I’ve tested it and I can beat the webpage with 100% accuracy.

Now, I’ve learned a new skill and to apply it once more I can make my own game.