William Angell — September 6th, 2019

Beating the Hot Dog Markets (with Gaussian Processes)

There's always money in the hot dog stand

One of the most formative experiences I had as a kid was playing Hot Dog Stand: The Works by Sunburst Communications.

The splash screen, accompanied by some excellent tunes

Hot Dog Stand is an economics simulator that allows you to run - surprise - a hot dog stand. You set the prices, order supplies, write checks, etc. I happened to stumble across my old copy recently and decided it should be solved using machine learning.

The Game

While beautiful in its simplicity, the game also has enough complexity that it's interesting - many of the problems within this game are faced by businesses across the world: suppliers can fail to deliver you the supplies you need, the weather report is wrong, your hot dogs go bad if you don't sell them, etc. These are all really hard problems to solve - especially at scale.

Fortunately for us - there are only 4 items we have to optimize the price of in this game: 1. hot dogs 2. turkey dogs 3. chips 4. cola

Difficulty

After picking a name, you have to select a difficult level. The difficulty levels influence how many random events occur. We'll stick to beginner for now.

Difficulty levels

Supplies

Ordering supplies

One of the complexities I mentioned before is that hot dogs / turkey dogs / buns expire after each event. This makes our problem more complex, as we now have to know how much of each to order so that none go to waste (adding to our costs).

Another thing to note: you need to have a sufficient number of buns for both turkey dogs + hot dogs, as well as "courtesy kits" - napkins.

Prices

Pricing your wares

This is the screen at which you set your prices - note, you don't set the prices for buns or courtesy kits.

Weather

The weather station

There are five different weather scenarios: sunny, fair, rainy, thunderstorms, and snow.

The weather prediction is not always correct - adding a bit of randomness to our results.

Attendance

Demand estimates

I ignored these values for this blog post - but each event has an estimated audience, which would help us in predicting absolute demand.

Running the stand

Running the stand

When you run the stand, some funky music plays and the silouhettes of people are animated.

Outcome

Your outcome from running the stand for an event

After the event, you're shown some important information: - Actual weather - Total amount of sales - Amount of each item sold - Amount of money left in bank account

Goal

The goal is to have $X amount of dollars by the end of 4 events. If you do it, you'll get to see this screen:

Congratulations!

Also, occasionally the phone will ring and someone will make a prank phone call:

Prank call

Automating the Process

We could automate the process in a few different ways the best, but most time consuming method, would be hooking into memory. Instead, I decided to opt for automating clicks/keypresses as it took me less than an hour to have the game automated.

PyAutoGUI

I ended up using PyAutoGUI as I was already using Python for the main code anyway.

It was a pretty straight forward process - I used the coordinates relative to the Wine window to automate the most basic tasks:

  • Setting prices
  • Ordering supplies
  • Running the stand

e.g. starting a new game:

pyautogui.moveTo(window_x + 15, window_y + 15)
pyautogui.click()
time.sleep(0.1)
pyautogui.moveRel(None, 10)
pyautogui.click()
pyautogui.keyDown('alt')
pyautogui.press(['n'])
pyautogui.keyUp('alt')
time.sleep(0.1)
pyautogui.press(['enter'])
pyautogui.moveTo(window_x + 500, window_y + 500)

pyautogui.click()
pyautogui.click()

Reading the weather

The next challenge was to read the weather screen. We need two parts of the weather: what the TV station predicted the weather would be, and the actual weather.

Fortunately, we don't have to crack open opencv - PyAutoGUI comes with some simple tooling for searching within images.

After running through a few different scenarios, I realized that the one unchanging detail of the weather screen (as it's animated) was the hair of the Hot Dog Weatherman. I took a few screenshots and used PyAutoGUI to search for these within some pixel threshold.

Examples of the unchanging elements: Fair{ width: 50px; } Sunny Snow

The code:

#                s  f  r  t  s
weather_array = [0, 0, 0, 0, 0]
weather_indicators = ["sunny", "fair", "rainy", "thunder", "snow"]
for x in range(len(weather_indicators)):
  weather_image = os.path.join("weather", weather_indicators[x] + ".png"
  if pyautogui.locateOnScreen(weather_image,
                              region = (3540, 520, 600, 400), 
                              confidence = c):
      weather_array[x] = 1

Reading the sales screen

After an event, you're presented with the sales screen.

This screen shows you how much of each product you sold, how many people showed up, what your current bank statement is, and what the actual weather was during the event.

For this screen, I opted to use Tesseract OCR - a popular off-the-shelf OCR solution that worked perfectly within minutes of setting it up. There's a small Python wrapper around the executable - pytesseract.

im1 = pyautogui.screenshot(region = (window_x + weather_offset_x, 
                                     window_y + weather_offset_y, 
                                     300, 200))

out = pytesseract.image_to_string(im1.resize((600, 500)))

Finally, I could run a complete run - each round occurs as follows:

  • Start a new game (this would erase any "state" that we have currently - as we are not approaching this as a typical reinforcement learning problem)
  • Read the weather screen
  • Given the predicted weather, use a model to return the amount of each item to purchase + the price of each item
  • Set the prices + order supplies
  • Run the hot dog stand, collect the output, and save as a training example

(At this point, I tried getting it to run headless under docker using Xvfb - but gave up after an hour - and just ran the experiments over the weekend)

An example run (with the objective grpahed on the right):

With the automation + data collection finished, I was ready to connect the model.

General Approach

I wanted to solve several different versions of the problem - not using classic econometrics models. Price optimization is a hard problem - and the classic approach involves picking a demand curve distribution for your items and predicting parameters of the curve using MLE/MAP. I wanted to solve this as a blackbox machine learning problem.

  1. Optimizing prices using only the profit at each round
  2. Optimizing prices using the profit at each round + weather
  3. Optimizing prices + inventory using profit + weather

I ran each approach 5 times for 1000 steps.

Gaussian Processes / Bayesian Optimization

I wanted to treat this as a Bayesian optimization problem - optimizing profit given that running the stand is an expensive operation (both in terms of time + money), and the input space is fairly small - so using Gaussian processes (GPs) seemed like a good approach.

GP: wiki

As GPs act as a distribution over functions, we get a mean + variance as the predicted output - allowing us to balance exploration/exploitation using Bayesian optimization.

There's been a lot of work on GPs in recent years - in getting them to scale (through sparse methods / variational inference) as well as combining them with deep learning (see: Andrew Gordon Wilson's lab). GPyTorch is a specific implementation of Gaussian processes in PyTorch that allows us to easily use some of the newer work in scaling them to bigger datasets, using SGD to solve - and on top of that, it presents a nice API. Another library in the same spirit, but for Tensorflow, is GPFlow.

Botorch is a library developed by Facebook that acts as a wrapper around gpytorch. Writing a short Bayesian optimization loop in gpytorch is already easy (set loss equal to output of aquisition function + turn on gradients for your inputs) - but botorch adds some niceties (for example, fixing particular values in your input space) that truly makes this plug 'n' play.

Example botorch code that gives us the next viable candidate:

gp = SingleTaskGP(train_X, train_Y)
mll = ExactMarginalLogLikelihood(gp.likelihood, gp)
fit_gpytorch_model(mll)
UCB = UpperConfidenceBound(gp, beta=0.1)

min_bounds = torch.zeros(9)
max_bounds = torch.Tensor([5.0] * 4 + [1.0] * 5)

bounds = torch.stack([min_bounds, max_bounds])

weather_state = w

fixed_features = dict(zip(range(4, 9), weather_state))

candidate = joint_optimize(UCB,
                           bounds = bounds,
                           q = 1, 
                           num_restarts = 5,
                           raw_samples = 20,
                           fixed_features = fixed_features)

Experiments

Prices 🡒 Profit

For this experiment, I used prices as our sole input and profit as the output.

So given a set of prices - and fixing inventory to a minimum set - what is the predicted profit? This obviously ignores a lot of important variables - weather, # of people in attendance, etc. But it was a good first experiment to see how well the model would perform.

Prices + weather 🡒 Profit

This experiment adds weather to our input vector - but only optimizes over the prices and keeps weather fixed (one of the niceties of botorch).

Prices + weather + inventory 🡒 Profit

Finally - this approach includes the amount of inventory to purchase. There are far better approaches to modeling this part of the problem (optimizing profits under inventory constraints) - but we thought it was sufficiently interesting to see how it would perform.

Results

Prices 🡒 Profit

Prices + weather 🡒 Profit

Prices + weather + inventory 🡒 Profit

Cola-only TAS

As a bonus, I decided to see if we could beat the game selling only cola.

This website uses cookies. By continuing to browse and use this website, you indicate your consent for us to use these cookies. You can change how your browser handles cookies in your browser settings.