Mark

Posted on

# Switch Game or Not?

I'm a big fan of the podcast CAGCast which is all about video games. A few months back they invented a game called 'Switch Game or Not?' where one host would inject fake Nintendo Switch games into that week's list of new releases. Why is this fun? Because so many Switch game names are ridiculous. 'Almightree: The Last Dreamer', 'Hunter's Legacy: Purrfect Edition' and 'Oxyjet' are all examples of games that came out last week. It's so easy to slip in ridiculous game names not have it be obvious what's real and what's fake.

I've fiddled around with using Markov chains to generate new text (words, tweets, etc.) and found it to be pretty quick and easy. Markov chains are a way of moving between states stochastically (randomly). Now, they way they're normally setup, there's no memory. So, if you had a Markov chain for the weather you might have three states, Sunny, Cloudy and Rainy. Each state (say Cloudy) would have a probability of moving to a new state (Sunny or Rainy) or staying the same, the total probability would be 1 (because everything either changes or stays the same, guaranteed). In this case, it doesn't matter if the previous state was Rainy or Sunny, the fact that it is current Cloudy is all that's needed to determine the next state.

When using Markov chains on text, you could think of this as generating a sequence of tokens (letters, words, etc.) where the current token informs the probability of new tokens. If we built a Markov chain on the set of words ['hi','hello','help'] and tokenized on letters then when we're in the state of 'h' there would be a 33% chance of moving to 'i' and a 67% chance of moving to 'e' and a 0% chance of moving to any other letter (or staying the same). For the state of 'l' there would be a 33% chance of moving to 'o', 33% of moving to 'p' and a 33% chance of staying 'l'. For a more complex vocabulary this will become a lot more complex. The other thing to consider is adding a character which will generate the first letter and a terminating sequence to know when the word is done. So we might pad our words to look like ['hi`','*hello`','*help`'], this way we can start a new word from the state of '' and as soon as we generate a '`' we know we're done.

I mentioned that Markov chains don't have a memory, so working off of a single letter state, even in our simple vocabulary we could chain together a lot of 'l's which makes for things that don't look like words. So we can build in a memory by having a sliding window of characters. Instead of 'help`' having 6 states of '', 'h', 'e', 'l', 'p', and '`' we could use two characters to predict the next single letter '**', '*h','he', 'el', 'lp', 'p`', '' (I increased the padding to reflect the size of the window). This helps ensure that 'll' will always move to a letter other than 'l'.

Given a vocabulary then, we need a way to identify all sliding windows and the next token that is predicted. Traditionally this is stored in a matrix, but in our case we have so many possible current states and so many next states (many of which will be empty) that it may not be efficient to store it like that. In Python, I used a dictionary with current states as the keys and stored next tokens as lists.

In the code below hopefully you can follow my process. I take a list of Nintendo Switch game names (I built mine on the complete list of game names) and for each, pad it with my 'memory' window of '' at the beginning and '`' at the end (these characters are rarely used and the few '' that are used I stripped out). Then I walk through each title breaking it into windows and append the next window to a dictionary using that key. When this is done, I have a raw list of each next character which contains a lot of repeats. So, I calculate the cumulative probability of each next token (to support randomly picking the next character). In the end I have a nice JSON type structure of a dict of dicts, which I write out to a file.

``````from collections import Counter
from functools import reduce
import re
import json

def parse_name(name, n, nl):
name = "*"*n+name+"`"*n
l = name.__len__()-n
for i in range(l):
try:
nl[name[i:(i+n)]].append(name[i+n])
except KeyError:
nl[name[i:(i+n)]] = [name[i+n]]
return nl

def calc_percent(n):
ct = dict(Counter(n))
p = [v / sum(ct.values()) for v in ct.values()]
cp = reduce(lambda c, x: c+[c[-1] + x], p, [0])[1:]
ky = list(ct.keys())
output = {}
for ir in range(cp.__len__()):
output[ky[ir]] = cp[ir]
return output

def gen_markov(known, n):
next_letter = {}
for k in known:
k = re.sub("[\*\(\)]", "", k)
next_letter = parse_name(k, n, next_letter)

for i in next_letter.keys():
next_letter[i] = calc_percent(next_letter[i])

with open("markov_probabilities_{}.json".format(str(n)), 'w') as outfile:
json.dump(next_letter, outfile, indent=4, sort_keys=True)
return 0

known_games = ["SEGA AGES Phantasy Star","RollerCoaster Tycoon Adventures","ACA NEOGEO METAL SLUG 5","Hyperide: Vector Raid","Peace, Death! Complete Edition","InkyPen","Almightree: The Last Dreamer","TRYBIT LOGIC","Firewatch","Rain World","Nippon Marathon",Omensight: Definitive Edition","Atari Flashback Classics","Donut County","Venture Towns","Lazy Galaxy: Rebel Story","City Builder","Oxyjet","Knights of Pen and Paper Bundle","RAZED","MIND: Path to Thalamus","Race Arcade","Blue Rider","Clue: The Classic Mystery Game","Hunter's Legacy: Purrfect Edition","Party Arcade","Starman","Mahjong Solitaire Refresh","Sheltered","Knights of Pen & Paper 2 Deluxiest Edition","Big Bash Boom","GRIS","Arcade Archives ATHENA"]

_ = gen_markov(known_games, 4)
``````

Now that I have the data necessary to run a Markov process, I need a way of generating new names. Load in the json file we saved off earlier, generate our starting state ('****' here) and use a `while` loop to keep going until we hit the terminating state. The advantage of having a dict of dicts is we can quickly pull out all possible next states (we've removed all the 0's), generate a single random number and the pull out the key for the first value that's greater than the random number.

``````import json
import random

def choose_letter(s, p):
r = random.random()
p = probs[s]
i = min([i for i, x in enumerate([r < l for l in list(p.values())]) if x])
return list(p.keys())[i]

def gen_title(title, n, p):
keep_going = True
while keep_going:
if title[-n:] == "`"*n:
keep_going = False
else:
title = title + choose_letter(title[-n:], p)
return title[n:-n]

memory_length = 4

with open('markov_probabilities_{}.json'.format(str(memory_length))) as jsonfile: