Reduce Food Wastage using Machine Learning

A scenario the readers might be familiar with: food items hiding around in our refrigerator way past their expiry date. Once discovered, these are quickly transferred to the bin with promises to self that next time it will be different for sure OR worse yet we stuff the items in our freezer!

Estimates of waste range from 20% to 50% (in countries like USA). This is a big shame given the fact that hundreds of millions of people around the world don’t have any form of food security and face acute shortage of food.

What can we do about this? 

One solution is to help people be a bit more organised by reminding them of the expiry dates of various items. The registration of items has to be automated and smart. 

Automated:

If we insist on manual entry of items with their expiry date – people are likely to not want to do this especially right after a long shop! Instead, as the items are checked out at the shop, an option should be available to email the receipt which should also contain an electronic record of the expiry date of the purchased items. This should include all groceries as well as ‘ready to eat’ meals. Alternatively, one can also provide different integration options using open APIs with some sort of a mobile app.

Smarter:

Once we have the expiry dates we need to ensure we provide the correct support and advice to the users of the app. To make it more user-friendly we should suggest recipes from the purchased groceries and put those on the calendar to create a ‘burn-down’ chart for the groceries (taking inspiration from Agile) which optimises for things like freshness of groceries, minimising use of ‘packaged foods’ and maintaining the variety of recipes.

Setup:

Steps are as follows:

  1. When buying groceries the expiry and nutrition information are loaded into the system
  2. Using a matrix of expiry to items and items to recipes (for raw groceries) we get an optimised ordering of usage dates mapped to recipes
  3. With the item consumption-recipe schedule we can then interleave ready to eat items, take-away days and calendar entries related to dinner/lunch meetings (all of these are constraints)
  4. Add feedback loop allowing users to provide feedback as to what recipes they cooked, what they didn’t cook, what items were wasted and where ‘unscheduled’ ready to eat items were used or take-away called for
  5. This will help in encouraging users to buy the items they consume and warn against buying (or prioritise after?) items that users ‘ignore’ 

I provide a dummy implementation in Python using Pandas to sketch out some of the points and to bring out some tricky problems.

The output is a list of purchased items and a list of available recipes followed by a list of recommendations with a ‘score’ metric that maximises ingredient use and minimises delay in usage.

Item: 0:cabbage
Item: 1:courgette
Item: 2:potato
Item: 3:meat_mince
Item: 4:lemon
Item: 5:chicken
Item: 6:fish
Item: 7:onion
Item: 8:carrot
Item: 9:cream
Item: 10:tomato


Recipe: 0:butter_chicken
Recipe: 1:chicken_in_white_sauce
Recipe: 2:mince_pie
Recipe: 3:fish_n_chips
Recipe: 4:veg_pasta
Recipe: 5:chicken_noodles
Recipe: 6:veg_soup

Recommendations

butter_chicken:     Score:30            Percentage items consumed:36%

chicken_in_white_sauce:     Score:26            Percentage items consumed:27%

Not enough ingredients for mince_pie

fish_n_chips:       Score:20            Percentage items consumed:27%

veg_pasta:      Score:26            Percentage items consumed:27%

chicken_noodles:        Score:28            Percentage items consumed:36%

veg_soup:       Score:20            Percentage items consumed:27%

The recommendation is to start with ‘butter chicken’ as we use up some items that have a short shelf life. Here is a ‘real’ recipe – as a thank you for reading this post: 

http://maunikagowardhan.co.uk/cook-in-a-curry/butter-chicken-murgh-makhani-chicken-cooked-in-a-spiced-tomato-gravy/h

Tricky Problems:

There are some tricky bits that can be solved but will need some serious thinking:

  1. Updating recommendations as recipes are cooked
  2. Updating recommendations as unscheduled things happen (e.g. item going bad early or re-ordering of recipes being cooked)
  3. Keeping track of cooked items and other interleaved schedules (e.g. item being frozen to use later)
  4. Learning from usage without requiring the user to update all entries (e.g. using RFID? Deep Learning – from images taken of your fridge with the door open)
  5. Coming up with innovative metrics to encourage people to eat healthy and eat fresh – lots of information can be extracted (E.g. nutrition information) if we have a list of purchased items
  6. Scheduling recipes around other events in a calendar or routine items (e.g. avoiding a heavy meal before a scheduled gym appointment)

Network Traffic Monitoring using OpenFlow

These days you don’t have to shell out thousands of pounds for an OpenFlow switch. Especially if you don’t mind lesser number of ports and devices that are not blazingly fast. I purchased a Zodiac FX OpenFlow switch and have been trying out different projects with it. The switch has 4 ports at 100M each with Port 4 reserved for management.

Figure 1: Network Setup for Traffic Snooper

To make a Traffic Snooper we need to mirror ports that allow ingress into and egress from the internal network. Port mirroring means sending same traffic to the target port as well as a mirror port. We may also filter traffic that is mirrored (e.g. we may only want to mirror Layer 4: UDP traffic). 

For the Zodiac FX, I selected Port 2 to be the mirror port. Traffic exiting the internal network will arrive on Port 1 and be sent out from Port 2 and Port 3 (Apply Action List). Similarly traffic entering the internal network from the Internet will arrive on Port 3 and be sent out from Port 2 and Port 1.

Thus Port 2 will receive packets from both the directions. Port 2 is attached directly to a Raspberry Pi with Link Local addressing enabled. This means that the port on the Raspberry Pi has a link local IP address assigned to it. We don’t really care about this because we are already forcing the traffic to come this way using a static flow. 

On the Traffic Snooper Pi I run my Python based Traffic collector. This utilises raw sockets to listen for traffic. All data is converted into hex and dumped into the Analytics Store database (Mongo DB). This is a fairly simple utility perfect for a lightweight platform like the Pi. It does not do any processing of the network data. It simply stores it in a database. The source code is attached for both the Snooper and the static controller which uses Ryu.

Snooper.py: https://docs.google.com/document/d/e/2PACX-1vTVV-G17M-TrLfGd2gt0B-5aK_NshjZ1-F1tWvrQwbTHR4Z-FYoaAzfOYdMVtGxP3B1ODLoWWiQiWS3/pub

The Traffic Snooper needs the following to read from the raw socket that is getting data from port 2 of the switch (the mirrored port):

s = socket.socket(socket.AF_PACKET, socket.SOCK_RAW, socket.htons(3))

The line above can be interpreted as:

Open a socket that uses Address Family (AF) of Packets (you will need to run snooper with sudo to provide access) that will allow access to Layer 2 information. The socket is a raw type – therefore Layer 2 headers will not be stripped. Finally we provide the host to network byte order conversion (htons). 

This gives us a socket that pulls the packet with all the information (headers) intact and also ensures the byte ordering is correct.

The Traffic Snooper also stores the packet hash to ensure we do not store duplicate packets (this can be disabled if required).

Note: port 2 will not get any direct assignment of IP address (we don’t want any traffic to use this port for communication – only mirrored traffic should use this port) and should default to a ‘link-local’ IP address. In case of IPv4, link-local addresses are defined in the address block 169.254.0.0/16

Static_Controller.py: https://docs.google.com/document/d/e/2PACX-1vRU8ZAa5Vl03UwC5K61Rt9Me0y0tvKq_0s8lCm7aH9t7vN_Z6qnUMQgINPFdCrt9BM-kBkJh3uuJCyw/pub

The installed flows:

The OpenFlow Specification allows multiple Apply Actions. We use this to create duplicated traffic flows.
Flow 1: All traffic coming in from port 3 is forwarded to port 2 and 1. Here port 2 is the port connected to the analyser.

Flow 2: All traffic coming in from port 1 is forwarded to port 2 and 3.

Note: The controller is a static controller. In other words we use Ryu to install flows and then the controller is disconnected (thus flow timeout=0). To achieve this we use the ‘safe’ mode on the Zodiac FX which does not remove the flows that have been installed. As the Zodiac FX is a pure OpenFlow switch it does not support standalone mode.

Next Step: Next post will look at the traffic analyser that breaks down the incoming packet and pulls out various protocol related information.

Follow-up: I have used Zodiac FX for this post and not something like OpenVSwitch (which has several advanced features such as port mirroring and built in learning switch in ‘standalone’ mode) because I wanted to use a pure OpenFlow device that does nothing till you don’t provide the flows. 

OVS Implementation

It is fairly straight forward if you want to setup your Pi as a OVS switch. You will need USB-Ethernet plugs and a freshly formatted Pi. I used the lightweight no-desktop ‘Stretch’.

This is a good guide to follow: 
https://www.telematika.org/post/piovs-raspberry-pi-open-vswitch/

I only needed the ‘Install OVS’ and ‘Configure Interfaces’ step.

Below are the three interfaces I created, ‘eth2’ is the interface to the snooper and ‘eth3’ the ‘internet’ interface.

auto eth1
iface eth1 inet manual
hwaddress ether 00:0e:c6:de:54:15
auto eth2
iface eth2 inet manual
hwaddress ether 00:0e:c6:df:ae:ac
auto eth3
iface eth3 inet manual
hwaddress ether 00:0e:c6:df:ae:c2
auto ovsbr0
allow-ovs ovsbr0
iface ovsbr0 inet manual
ovs_type OVSBridge

There are few things to watch out for:

  1. The interface on the Raspberry Pi running the snooper application  should not be reachable from the network. This is because we do not want any traffic headed for that port. We only want to record traffic flowing between 1 and 3. Therefore, the Pi connected to port 2 of the switch should have two interfaces. One that has a valid local network address – to allow snooper to access the database server for example. The second which is connected to the switch interface 2 which receives the copied traffic. This second interface should have a link local IP address to ensure all the traffic received there either for port 1 or 3.
  2. Set the fail mode to ‘secure’ in OVS. If you do not set the fail mode in OVS to ‘secure’ then it will fall back to learning switch mode (standalone mode) and start faithfully switching traffic. This will mean (in short) your snooper Pi will have an IP address assigned to the port that is sniffing the mirrored traffic. Once you install the flows then the traffic will be mirrored but you can still get extra packets not part of the flow that we are monitoring.
  3. Use ‘sudo ovs-vsctl get-fail-mode <bridge_name>‘ to get the fail mode and then ‘sudo ovs-vsctl set-fail-mode <bridge_name> secure‘ to set to secure mode (replace bridge_name with the name of your OVS bridge). This will disable the learning switch and you will need to use the static-controller to setup the snooper flows.
  4. You can use ‘sudo ovs-appctl fdb/show <bridge_name>‘ to show the forwarding db (this stores the result of the mac learning) and ‘sudo ovs-appctl fdb/flush <bridge_name>‘ to clear the forwarding db.

Housing Market: Auto Correlation Analysis

In this post we take a look at the housing market data which consists of all the transactions registered with the UK Land Registry since 1996. So lets get the copyright out of the way:

Contains HM Land Registry data © Crown copyright and database right 2018. This data is licensed under the Open Government Licence v3.0.

The data-set from HM Land Registry has information about all registered property transactions in England and Wales. The data-set used for this post has all transactions till the end of October 2018. 

To make things slightly simple and to focus on the price paid and number of transaction metrics I have removed most of the columns from the data-set and aggregated (sum) by month and year of the transaction. This gives us roughly 280 observations with the following data:

{ month, year, total price paid, total number of transactions }

Since this is a simple time-series, it is relatively easy to process. Figure 1 shows this series in a graph. Note the periodic nature of the graph.

Figure 1: Total Price Paid aggregated (sum) over a month; time on X axis (month/year) and Total Price Paid on Y axis.

The first thing that one can try is auto-correlation analysis to answer the question: Given the data available (till end-October 2018) how similar have the last N months been to other periods in the series? Once we identify the periods of high similarity, we should get a good idea of current market state.

To predict future market state we can use time-series forecasting methods which I will keep for a different post.

Auto-correlation

Auto-correlation is correlation (Pearson correlation coefficient) of a given sample (A) from a time series against other available samples (B). Both samples are of the same size. 

Correlation value lies between 1 and -1. A value of 1 means perfect correlation between two samples where they are directly proportional (when A increases, B also increases). A value of 0 implies no correlation and a value of -1 implies the two samples are inversely proportional (when A increases, B decreases).

The simplest way to explain this is with an example. Assume:

  1. monthly data is available from Jan. 1996 to Oct. 2018
  2. we choose a sample size of 12 (months)
  3. the sample to be compared is the last 12 months (Oct. 2018 – Nov. 2017)
  4. value to be correlated is the Total Price Paid (summed by month).

As the sample size is fixed (12 months) we start generating samples from the series:

Sample to be compared: [Oct. 2018 – Nov. 2017]

Sample 1: [Oct. 2018 – Nov. 2017], this should give correlation value of 1 as both the samples are identical.

Sample 2: [Sep. 2018 – Oct. 2017], the correlation value should start to decrease as we skip back one month.

Sample N: [Dec. 1996 – Jan. 1996], this is the earliest period we can correlate against.

Now we present two graphs for different sample sizes:

  1. correlation coefficient visualised going back in time, grouped by Year (scatter and box plot per year) – to show yearly spread
  2. correlation coefficient visualised going back in time – to show periods of high correlation

Thing to note in all the graphs is that the starting value (right most) is always 1. That is when we compare the selected sample (last 12 months) with the first sample (last 12 months).

In the ‘back in time’ graph we can see the seasonal fluctuations in the correlation. These are between 1 and -1. This tells us that total price paid has a seasonal aspect to it. This makes sense as we see lots of houses for sale in the summer months than winter as most people prefer to move when the weather is nice!

Fig 2: Example of In and Out of Phase correlation.

So if we correlate a 12 month period (like this one) one year apart (e.g. Oct. 2018 – Nov. 2017 and Oct. 2017 – Nov. 2016) one should get positive correlation as the variation of Total Price Paid should have the same shape. This is ‘in phase’ correlation. This can be seen in Figure 2 as the ‘first’ correlation which is in phase (in fact it is perfectly in phase and the values are identical – thus the correlation value of 1). 

Similarly, if the comparison is made ‘out of phase’ (e.g. Oct. 2018 – Nov. 2017 and Jul 2018 – Aug. 2017) where variations are opposite then negative correlation will be seen. This is the ‘second’ correlation in Figure 2.

This is exactly what we can see in these figures. Sample sizes are 6 months, 12 months, 18 months and 24 months. There are two figures for each sample size. The first figure is the spread of the auto-correlation coefficient for a given year. The second figure is the time series plot of the auto-correlation coefficient, where we move back in time and correlate against the last N months. The correlation values fluctuating between 1 and -1 in a periodic manner. 


Fig. 3a: Correlation coefficient visualised going back in time, grouped by Year (scatter and box plot per year), Sample size: 6 months

Fig. 3b: Correlation coefficient visualised going back in time; Sample size: 6 months


Fig. 4a: Correlation coefficient visualised going back in time, grouped by Year (scatter and box plot per year); Sample size: 12 months

Fig. 4b: Correlation coefficient visualised going back in time; Sample size: 12 months


Fig. 5a: Correlation coefficient visualised going back in time, grouped by Year (scatter and box plot per year); Sample size: 18 months

Fig. 5b: Correlation coefficient visualised going back in time; Sample size: 18 months


Fig. 6a: Correlation coefficient visualised going back in time, grouped by Year (scatter and box plot per year); Sample size: 24 months

Fig. 6b: Correlation coefficient visualised going back in time; Sample size: 24 months

Conclusions

Firstly, if we compare the scatter + box plot figures, especially for 12 months (Figure 4a), we find the correlation coefficients are spread around ‘0’ for most of the years. One period where this is not so and the correlation spread is consistently above ‘0’ is the year 2008, the year that marked the start of the financial crisis. The spread is also ‘tight’ which means all the months of that year saw consistent correlation, for the Total Price Paid, against the last 12 months from October 2018.

Secondly conclusion we can draw from the positive correlation between last 12 months (Figure 2b) and the period of the financial crisis is that the variations in the Total Price Paid are similar (weakly correlated) with the time of the financial crisis. This obviously does not guarantee that a new crisis is upon us. But it does mean that the market is slowing down. This is a reasonable conclusion given the double whammy of impending Brexit and on set of winter/Holiday season (which traditionally marks a ‘slow’ time of the year for property transactions).

Code is once again in python and attached below:

from matplotlib import pyplot as plt
from pandas import DataFrame as df
from datetime import datetime as dt
from matplotlib.dates import YearLocator, MonthLocator, DateFormatter
import pandas as pd
import numpy as np
from sklearn.cluster import KMeans, MiniBatchKMeans, DBSCAN
from sklearn.mixture import GaussianMixture

months = MonthLocator(range(1, 13), bymonthday=1, interval=3)
year_loc = YearLocator()

window_size = 12

def is_crisis(year):
if year<2008:
return 0
elif year>2012:
return 2

return 1

def is_crisis_start(year):
if year<2008:
return False
elif year
>2008:
return False

return True

def
process_timeline(do_plot=False):
col = "Count"
y = []
x = []
x_d = []
box_d = []
year_d = []
year = 0
years_pos = []
crisis_corr = []
for i in range(0, size - window_size):

try:

if year != df_dates["Year"][size-1-i]:

if year > 0:
box_d.append(year_d)
years_pos.append(year)
year_d = []
year = df_dates["Year"][size-1-i]

corr = np.corrcoef(df_dates[col][size -i - window_size: size - i].values, current[col].values)
year_d.append(corr[0, 1])
y.append(corr[0, 1])
if is_crisis_start(year):
crisis_corr.append(corr[0, 1])
x.append(year)
month = df_dates["Month"][size - 1 - i]
x_d.append(dt(year, month, 15))

except Exception as e:
print(e)

box_d.append(year_d)
years_pos.append(year)

corr_np = np.array(crisis_corr)
corr_mean = corr_np.mean()
corr_std = corr_np.std()

print("Crisis year correlation: mean and std.: {} / {} ".format(corr_mean, corr_std))
if do_plot:

fig, sp = plt.subplots()

sp.scatter(x, y)
sp.boxplot(box_d, positions=years_pos)

plt.show()

fig, ax = plt.subplots()
ax.plot(x_d, y,'-o')
ax.grid(True)
ax.xaxis.set_major_locator(year_loc)
ax.xaxis.set_minor_locator(months)
plt.show()

return corr_mean, corr_std

csv = "c:\\ML Stats\\housing_oct_18_no_partial_mnth_cnt_sum.csv"
full_csv = "c:\\ML Stats\\housing_oct_18.csv_mnth_cnt_sum.csv"

df = pd.read_csv(full_csv)


mnth = {
1: "Jan",
2: "Feb",
3: "Mar",
4: "Apr",
5: "May",
6: "Jun",
7: "Jul",
8: "Aug",
9: "Sep",
10: "Oct",
11: "Nov",
12: "Dec"
}


dates = list(map(lambda r: dt(int(r[1]["Year"]), int(r[1]["Month"]), 15), df.iterrows()))

crisis = list(map(lambda r: is_crisis(int(r[1]["Year"])), df.iterrows()))

df_dates = pd.DataFrame({"Date": dates, "Count": df.Count, "Sum": df.Sum, "Year": df.Year, "Month": df.Month, "Crisis": crisis})

df_dates = df_dates.sort_values(["Date"])

df_dates = df_dates.set_index("Date")

plt.plot(df_dates["Sum"],'-o')
plt.ylim(ymin=0)
plt.show()

size = len(df_dates["Count"])

corr_mean_arr = []
corr_std_arr = []
corr_rat = []
idx = []
for i in range(0, size-window_size):
end = size - i
current = df_dates[end-window_size:end]
print("Length of current: {}, window size: {}".format(len(current), window_size))

ret = process_timeline(do_plot=True)
break #Exit early




House Market Analysis

The house prices in UK are at it again. A combination of Brexit, change in housing stock, easy loans and growing consumer debt is making things interesting again.

Figure 1: Number of Transactions per month from 1995 to August 2018

Figure 1 shows the number of transactions every month since 1995. The massive fall post 2007 because of the financial crisis. Then the surge in transactions since 2013. The lonely spot (top-right, March 2016) is just before the new Stamp Duty changes made buying a second house an expensive proposition. But this is relatively boring!

Visual Analytics: Relation between Quantity and Value of Transactions

Let us look at Transaction Count (quantity) and Total Value of those transactions, aggregated on a monthly basis. I used a Spark cluster to aggregate the full transaction set (4GB csv data file). The base data set has about 280 rows with the following structure:

{month, year, sum, count}

The month and year values are converted into dates and added to the row, then the data set is sorted by date:

{date, month, year, sum, count}

This leads us to three plots. Sum and Count against time and Sum against Count. These are shown below:

Figure 2: Total Transaction value by date, grouped by year (each dot represents a month in that year)

Figure 2 shows Total Transaction value by date (Y-axis). The plot is grouped by year where each dot represents a month in that year. The current year (2018) has complete months data till August therefore less number of dots.

Figure 3: Total Quantity of Transactions  by date, grouped by year (each dot represents a month in that year)

Figure 3 shows Total Quantity of Transactions (Y-axis), once again grouped by year. Similar to Figure 2 the data is complete till August 2018.

Figure 4: Total Transaction value (Y-axis) against Total Number of Transactions (X-axis)

Figure 4 show how the value of the transactions relates to number of transactions. Each dot represents a month in a year. As expected there is a slightly positive correlation between total value of transactions and the number of transactions. A point to note: the total value of transactions depends on the sale price (that depends on the property sold) as well as the number of transactions in a given month. For the same number of transactions the value could be high or low (year on year) depending on whether prices are inflationary or a higher number of good quality houses are part of that months transactions.

Figure 5: Total Transaction value (Y-axis) against Total number of transaction (X-axis), each point represents a particular month in a year

Figure 5 enhances Figure 4 by using colour gradient to show the year of the observation. Each year should have at least 12 points associated with it (except 2018). This concept is further extended by using different shape for the markers depending on whether that observation was made before the financial crisis (circle: year of observation before 2008), during the financial crisis (square: year of observation between 2008 and 2012) or after the crisis (plus: year of observation after 2012). These values for years have been picked using Figures 2 and 3. 

Figure 6: Showing the housing market contract during the Crisis and then expand

Figure 6 shows the effect of the financial crisis nicely. The circles represent pre-crisis transactions. The squares represent transactions during the crisis. The plus symbol represents post-crisis transactions. 

The rapid decrease in transactions can be seen as the market contracted in 2007-2008. As the number of transactions and the value of transactions starts falling, the relative fall in number of transactions is larger than in the total value of the transactions. This indicates the prices did fall but mostly not enough houses were being sold. Given the difficulty in getting a mortgage, this reduction in number of transactions could be caused by a lack of demand.

Discovering Data Clusters

Using a three class split (pre-crisis, crisis, post-crisis) provides some interesting results. These were described in the previous section. But what happens if a clustering algorithm is used on the data?

A Clustering algorithm attempts to assign each observation to a cluster. Depending on the algorithm, total number of clusters may be required as an input. Clustering is often helpful when trying to build initial models of the input data especially when no labels are available. In that case, the cluster id (represented by the cluster centre) becomes the label. The following clustering algorithms were evaluated:

  1. k-means clustering
  2. gaussian mixture model

The data-set for the clustering algorithm has three columns: Date, Monthly Transaction Sum and Monthly Transaction Count.

Given the claw mark distribution of the data it was highly unlikely k-means would give good results. That is exactly what we see in Figure 7 with cluster size of 3 (given we had three labels previously of before crisis, during crisis and after crisis). The clustering seems to cut across the claws. 

Figure 7: k-mean clustering with cluster size of 3 – total value of transactions (Y-axis) vs total number of transactions

If a gaussian mixture model (GMM) is used with component count of 3 and covariance type ‘full’ (using sklearn implementation – see code below) some nice clusters emerge as seen in Figure 8.

Figure 8: Gaussian Mixture model with three components.

Each of the components corresponds to a ‘band’ in the observations. The lowest band corresponds loosely with pre-crisis market, the middle (yellow) band somewhat expands the crisis market to include entries from before the crisis. Finally, the top-most band (green) corresponds nicely with the post-crisis market.

But what other number of components could we choose? Should we try other GMM covariance types (such as ‘spherical’, ‘full’, ‘diag’, ‘tied’)? To answer these questions we can run a ‘Bayesian Information Criteria’ test against different number of components and different covariance types. The method and component count that gives the lowest BIC is preferred.

The result is shown in Figure 9.

Figure 9: BIC analysis of the data – BIC score against number of components (X-axis)

From Figure 9 it seems the ‘full’ type consistently gives the lowest BIC on the data-set. Furthermore, going from 3 to 4 components improves the BIC score (lower the better). Another such jump is from 7 to 8. Therefore, number of components should be 4 (see Figure 10) or 8 (see Figure 11).

Figure 10: Transaction value (Y-axis) against  Total Number of Transactions – with 4 components.

Figure 11: Transaction value (Y-axis) against  Total Number of Transactions – with 8 components.

The 4 component results (Figure 10) when compared with Figure 5 indicates an expansion at the start of the data-set (year: 1995), this is the jump from yellow to green. Then during the crisis there is a contraction (green to purple). Post crisis there is another expansion (purple to blue). This is shown in Figure 12.

Figure 12: Expansion and contraction in the housing market

The 8 component results (Figure 11) when compared with Figure 5 shows the stratification of the data-set based on the Year value. Within the different colours one can see multiple phases of expansion and contraction.

The interesting thing is that for both 4 and 8 component models, the crisis era cluster is fairly well defined.

Code for this is given below:

from matplotlib import pyplot as plt
from pandas import DataFrame as df
from datetime import datetime as dt
from matplotlib.dates import YearLocator, MonthLocator, DateFormatter
import pandas as pd
import numpy as np
from sklearn.cluster import KMeans, MiniBatchKMeans, DBSCAN
from sklearn.mixture import GaussianMixture


csv = "c:\\ML Stats\\housing_sep_18_no_partial_mnth_cnt_sum.csv"


df = pd.read_csv(csv)


dates = list(map(lambda r: dt(int(r[1]["Year"]), int(r[1]["Month"]), 15), df.iterrows()))

df_pure = pd.DataFrame({"Date": dates, "Count": df.Count, "Sum": df.Sum, "Year": df.Year})


df_pure = df_pure.sort_values(["Date"])

df_pure = df_pure.set_index("Date")


bics = {}
for cmp in range(1,10):

clust_sph = GaussianMixture(n_components=cmp, covariance_type='spherical').fit(df_pure)
clust_tied = GaussianMixture(n_components=cmp, covariance_type='tied').fit(df_pure)
clust_diag = GaussianMixture(n_components=cmp, covariance_type='diag').fit(df_pure)
clust_full = GaussianMixture(n_components=cmp, covariance_type='full').fit(df_pure)

clusts = [clust_full, clust_diag, clust_sph, clust_tied]
bics[cmp] = []
for c in clusts:
bics[cmp].append(c.bic(df_pure))

plt.plot(bics.keys(), bics.values())
plt.legend(["full", "diag", "sph", "tied"])
plt.show()

num_components = 4

clust = GaussianMixture(n_components=num_components, covariance_type='full').fit(df_pure)

lbls = clust.predict(df_pure)

df_clus = pd.DataFrame({"Count": df_pure.Count, "Sum": df_pure.Sum, "Year": df_pure.Year, "Cluster": lbls})
color = df_clus["Cluster"]

fig, ax = plt.subplots()
ax.scatter(df_clus["Count"], df_clus["Sum"], c=color)

fig, ax2 = plt.subplots()
ax2.scatter(df_clus["Year"], df_clus["Count"], c=color)

fig, ax3 = plt.subplots()
ax3.scatter(df_clus["Year"], df_clus["Sum"], c=color)


plt.show()

Contains HM Land Registry data © Crown copyright and database right 2018. This data is licensed under the Open Government Licence v3.0.

Recurrent Neural Networks to Predict Pricing Trends in UK Housing Market

Recurrent Neural Networks (RNN):

RNNs are used when temporal relationships have to be learnt. Some common examples include time series data (e.g. stock prices), sequence of words (e.g. predictive text) and so on.

The basic concept of RNNs is that we train an additional set of weights (along with the standard input – output pair) that associate past state (time: t-1) with the current state (time: t). This can then be used to predict the future state (time: t+1) given the current state (time: t). In other words RNNs are NNs with state!

When used to standard time series prediction the input and output values are taken from the same time series (usually a scalar value). This is a degenerate case of single valued inputs and outputs. Thus we need to learn the relationship between x(t-1) and x(t) so that we can predict the value of x(t+1) given x(t). This is what I did for this post.

Time series can be made more complicated by making the input a vector of different parameters, the output may still remain a scalar value which is a component of x or be a vector. One reason this is done is to add all the factors that may impact the value to be predicted (e.g. x(t+1)). In our example of average house prices – we may want to add factors such as time of the year, interest rates, salary levels, inflation etc. to provide some more “independent” variables in the input.

Two final points:

  • Use-cases for RNNs: Speech to Text, Predictive Text, Music Tagging, Machine Translation
  • RNNs include the additional complexity of training in Time as well as Space therefore our standard Back-Propagation becomes Back-Propagation Through Time

RNN Structure for Predicting House Prices:

RNN simple time series

The basic time series problem is that we have a sequence of numbers – the average price of houses for a given month and year (e.g. given: X(1), X(2), … X(t-1), X(t) ) with a regular step size and our task is to predict the next number in the sequence (i.e. predict: X(t+1)). In our problem the avg price is calculated for every month since January 1995 (thus step size is 1 month). As a first step we need to define a fixed sequence size that we are going to use for training the RNN. For the input data we will select a sub-sequence of a given length equal to the number of inputs (in the diagram above there are three inputs). For training output we will select a sub-sequence of the same length as the input but the values will be shifted one step in the future.

Thus if input sub-sequence is: X(3), X(4) and X(5) then the output sub-sequence must be: X(4), X(5) and X(6). In general if input sub-sequence spans time step to where b > a and b-a = sub-sequence length, then the output sub-sequence must span a+1 to b+1.

Once the training has been completed if we provide the last sub-sequence as input we will get the next number in the series as the output. We can see how well the RNN is able to replicate the signal by starting with a sub-sequence in the middle and movie ahead in time steps and plotting actual vs predicted values for the next number in the sequence.

Remember to NORMALISE the data!

The parameters are as below:

n_steps = 36 # Number of time steps (thus a = 0 and b = 35, total of 36 months)

n_inputs = 1 # Number of inputs per step (the avg. price for the current month)

n_neurons = 1000 # Number of neurons in the middle layer

n_outputs = 1 # Number of outputs per step (the avg. price for the next month)

learning_rate = 0.0001 # Learning Rate

n_iter = 2000 # Number of iterations

batch_size = 50 # Batch size

I am using TensorFlow’s BasicRNNCell (complete code at the end of the post) but the basic setup is:

X = tf.placeholder(tf.float32, [None, n_steps, n_inputs])
y = tf.placeholder(tf.float32, [None, n_steps, n_outputs])

cell = tf.contrib.rnn.OutputProjectionWrapper(tf.contrib.rnn.BasicRNNCell(num_units = n_neurons, activation = tf.nn.relu), output_size=n_outputs)

outputs, states = tf.nn.dynamic_rnn(cell, X, dtype = tf.float32)

loss = tf.reduce_mean(tf.square(outputs-y))
opt = tf.train.AdamOptimizer(learning_rate=learning_rate)
training = opt.minimize(loss)

saver = tf.train.Saver()

init = tf.global_variables_initializer()

Results:

A sample of 3 runs, using Mean Squared Error threshold of 1e-4 we get the following values for Error:

  1. 8.6831e-05
  2. 9.05436e-05
  3. 9.86998e-05

Run 3 fitting and predictions are shown below:

Orange dots represent the prediction by the RNN and Blue dots represent the actual data

 

Run 3 prediction against existing data 3 years before October 2017

Then we start from October 2017 (Month 24 in figure below) and forecast ahead to October 2018. This predicts a rise in average prices which start to plateau 3rd quarter of 2018. Given that average house prices across a country like UK are determined by a large number of noisy factors, we should take this prediction with a pinch of salt.

Run 3 Forecasting from Month 24 (October 2017 for the year ahead till October 2018)

A sample of 3 runs, using Mean Squared Error threshold of 1e-3 we get the following values for Error:

  1. 3.4365e-04
  2. 4.1512e-04
  3. 2.1874e-04

With a higher Error Threshold we find when comparing against actual data (Runs 2 and 3 below) the predicted values have a lot less overlap with the actual values. This is expected as we have traded accuracy for reduction in training time.

predicted avg price vs actual avg price (Run 2)

predicted avg price vs actual avg price (Run 3)

Projections in this case are lot different. We see a linearly decreasing avg price in 2018.

predicted avg price vs actual avg price with forecast

Next Steps:

I would like to add more parameters to the input – but it is difficult to get correlated data for different things such as interest rates, inflation etc.

I would also like to try other types of networks (e.g. LSTM) but I am not sure if that would be the equivalent of using a canon to kill a mosquito.

Finally if anyone has any ideas on this I would be happy to collaborate with them on this!

 

Source code can be found here: housing_tf

Contains HM Land Registry data © Crown copyright and database right 2017. This data is licensed under the Open Government Licence v3.0.

UK Housing Data Analysis: Additional Price Paid Entry

I have been exploring the HM Land Registry Price Paid Data and have discovered few more things of interest.

The data contains a ‘Price Paid Data Category Type’ (this is the second last column at the time of writing this post. As per the description of the schema this field can have one of two values:

A = Standard Price Paid entry, includes single residential property sold for full market value.
B = Additional Price Paid entry including transfers under a power of sale/repossessions, buy-to-lets (where they can be identified by a Mortgage) and transfers to non-private individuals.

Therefore it seems there is a way of looking at how properties sold for full market value differ from buy-to-lets, repossessions and power of sale transactions. Proper Category B tracking only starts from October 2013.

Before we do this it is worthwhile to use the ‘Property Type’ field to filter out properties of type ‘Other’ which contribute to the overall noise because these are usually high value properties such as office buildings. The ‘Property Type’ field has the following values:

D = Detached,

S = Semi-Detached,

T = Terraced,

F = Flats/Maisonettes,

O = Other

Data Pipeline for all transactions:

Step 1: Filter out all transactions with Property Type of Other

Step 2: Group using Year and Month of Transaction

Step 3: Calculate Standard Deviations in Price, Average Price and Counts

 

Data Pipeline for Standard and Additional Price Paid Transactions (separate):

Step 1: Filter out all transactions with Property Type of Other

Step 2: Group using Price Paid Data Category Type, Year and Month of Transaction

Step 3: Calculate Standard Deviations in Price, Average Price and Counts

Tech stuff:

I used a combination of MongoDB (aggregation pipelines for standard heavy weight aggregations – such as simple grouping), Apache Spark (Java based for heavy weight custom aggregations) and Python (for creating graphs and summarising aggregated data)

Results:

In all graphs Orange points represent Category B related data, Blue represents Category A related data and Green represents a combination of both the Categories.

Transaction Counts

Price Paid Data Category A/B Transaction Count

Price Paid Data Category A/B Transaction Count

Category B transactions form a small percentage of the overall transactions (5-8% appprox.)

As the Category B data starts from October 2013 we see a rapid increase in Category B transactions which then settles to a steady rate till 2017 where we can see transactions falling as it becomes less lucrative to buy a second house to generate rental income. There is a massive variation in terms of overall and Category A transactions. But here as well we see a downward trend in 2017.

We can also see the sharp fall in transactions due to the financial crisis around 2008.

In all graphs Orange points represent Category B related data, Blue represents Category A related data and Green represents a combination of both the Categories.

Average Price

Price Paid Data Category A/B Average Price

Price Paid Data Category A/B Average Price

Here we find an interesting result. Category B prices are consistently lower than pure Category A. But given the relatively small number of Category B transactions the average price of combined transactions is fairly close to the average price of Category A transactions. This also seems to point to the fact that in case of buy to let, repossessions and power of sale conditions the price paid is below the average price for Category A. Several reasons could exist for such a result:

  1. People buy cheaper properties as buy-to-let and use more expensive properties as their main residence.
  2. Under stressful conditions (e.g. forced sale or repossession) there is urgency to sell and therefore full market rate may not be obtainable.

Standard Deviation of Prices

Price Paid Data Category A/B Price Standard Dev.

Price Paid Data Category A/B Price Standard Dev.

The variation in the price for Category B properties is quite high when compared with Category A (the standard price paid transaction). This can point to few things about the Category B market:

  1. A lot more speculative activity is carried out here therefore the impact of ‘expectation’ on price paid is very high – particularly:
    1. ‘expected rental returns’: The tendency here will be to buy cheap (i.e. lowest possible mortgage) and profit from the difference between monthly rental and mortgage payments over a long period of time.
    2. ‘expected profit from a future sale’: The tendency here will be to keep a shorter horizon and buy cheap then renovate and sell at a higher price – either through direct value add or because of natural increase in demand.
  2. For a Standard transaction (Category A) the incentive to speculate may not be present as it is a basic necessity.

Contains HM Land Registry data © Crown copyright and database right 2017. This data is licensed under the Open Government Licence v3.0.

UK House Sales Analysis

I have been looking at house sales data from the UK (actually England and Wales). This is derived from the Land Registry data set (approx. 4GB) which contains all house sales data from mid 1990s. Data contains full address information so one can use reverse geo-coding to get the location of the sales.

Sales Density Over the Years

If we compare the number of sales over the years an interesting picture emerges. Below is the geographical distribution of active regions (w.r.t. number of sales).

Years 2004-2007 there is strong activity in the housing market – this is especially true for London (the big patch of green), South coast and South West of England.

The activity penetrates deeper (look at Wales and South West) as the saturation starts to kick in.
The financial crisis hits and we can immediately see a weakening of sales across England and Wales. It becomes more difficult to get a mortgage. Market shows first signs of recovery especially around London.  Market recovery starts to gain momentum especially outside London.
The recovery is now fairly widespread thanks to various initiative by the Government, rock bottom interest rates and a generally positive feeling about the future. Brexit and other factors kick in – the main issue is around ‘buy-to-let’ properties which are made less lucrative thanks to three-pronged attack: increase in stamp duty on a second house, removal of tax breaks for landlords and tightening of lending for a second home (especially interest-only mortgages).

Finally 2017 once can see that the market is again cooling down. Latest data suggests house prices have started falling once again and with the recent rise in interest rates it will make landing a good deal on a mortgage all that more difficult.

Average House Prices

Above graph shows how the Average price of Sales has changed over the Years. We see there is a slump in prices starting from 2017. It will be interesting to see how the house prices behave as we start 2018. It will be a challenge for people to afford higher mortgages as inflation outstrips income growth. This is especially true for first-time buyers. Given the recent bonanza of zero percent stamp duty for first time buyers I am not sure how much of an impact (positive) this will have.

Returns on Properties

Above graph shows how the returns and risks associated with a house change after a given number of years. It is clear that it is easier to get a return when a house is held for at least 5 years. Below that there is a risk of loosing money on the property. Properties resold within two years are most likely to make a loss. This also ties in with a ‘distress’ sale scenario where the house is sold without waiting for the best possible offer or in times of slowdown where easy term mortgages are not available.

Number of Times Re-sold

Above graph shows the number of times a house is re-sold (vertical) against the number of years it is held for before being re-sold. Most houses are re-sold within 5 years. But why a massive spike where houses are re-sold within 2 years? One possible explanation is that these are houses that are bought by a developer, improved and then re-sold within a year or so.

House Transactions by Month of Year

Transaction by month

What is the best time of the year to sell your house? Counting number of transactions by month (figure above) we can see number of transactions increases as Spring starts and continues to grow till the end of Summer. In fact 60% more houses are sold in Jun – Aug period as compared to Jan – March.

Transactions tend to decrease slightly as Autumn starts and falls off towards end of the year. This is expected as people would not want to move right after Christmas or early in the new year (winter moves are difficult!)

Infrastructure

I have used Apache Spark (using Java) to summarise the data from approximately 4 GB to 1-1.5 GB CSV files and then Python to do next round of aggregations and to generate the plots.

 

Next step will be to incorporate some Machine Learning into the process.

House Price and Transactions with UK Elections

We are just getting over the not so shocking election result in UK (8th June 2017).

I wanted to look at house prices and how they are affected by election results.

The graphs below plot House Price/ Number of Transactions against date (blue dots). The data is averaged over a month and is normalised to 1.0.

The vertical lines represent UK general elections with blue representing clear results (clear majority) and black lines representing hung Parliament. There is a black line (2nd from right) that represents EU Referendum (‘Brexit’).

The orange dots represent GBP (Sterling) performing against INR (Indian Rupee) and CNY (Chinese Yuan). The data is daily average normalised to 1.0.

We can see house prices grow aggressively after clear results. The period from 2008 onward is the ‘financial’ crisis era which is further complicated by a hung Parliament in 2010. The actual recovery takes a few years and by 2014 the boom times are back! The growth is further enhanced by a Conservative majority in 2015.

It is too early to see the impact of Brexit on the housing market but as far as GBP goes there has been a fall against all major currencies.

This means investment into the UK housing market is made cheaper for ‘international’ buyers. The growth in house prices is compensated by the fall in the pound (we can see this by the relative falls in the two graphs).

Already the house price increase is cooling off (falling in many regions where they were over-inflated to begin with). With the messy general election of 2017 increasing the uncertainty, especially around Brexit, the house prices from internal demand should decrease or flatten out. We can already see this starting. People might rush in to lock their mortgage (thereby boosting short term demand) as Bank of England has indicated a rise in Interest Rates in the near future.

What happens if look at the number of transactions? The normalised graph  above shows that during the financial crisis era the transactions fell sharply. Then began to revive (correlates with the rise in house prices). The strong position of the Conservatives further supported the market.

But as soon as the Stamp Duty increase came into the picture the number of transactions started reducing and after ‘Brexit’ leading up to the 2017 General Election we can see a sharp fall in transactions.

All of these things indicate that people are not sure about what will happen in the future so are not willing to take positions of risk.

Stamp duty change

Stamp duty change (1st April 2016)

A final interesting titbit – Why is there a massive spike in transactions in a subdued period of house sales (the red arrow)? And no this is not an error! The month is March 2016 – and the spike is there because stamp duty changes were being introduced from 1st April 2016 which meant buying a second home (without selling the first one) would become a lot more expensive!

[This analysis uses the Land Registry data set which is processed using Apache Spark, Python was used to further process and plot the data]

Tic Tac Toe: Statistical Analysis with arbitrary Grid Size

The game of tic tac toe (naughts and crosses) is a very simple yet interesting game.

If you don’t know anything about the game visit this link first: https://en.wikipedia.org/wiki/Tic-tac-toe

Some terms I will be using in this post:

  • Grid – the x by x square grid used to play the game, most common size is 3 by 3
  • Grid Reference – the reference to each entry (or slot) in the Grid, for a x by x grid there will be x-squared grid references, therefore for 3 by 3 there are 9 references and for 4 by 4 there are 16
  • Grid Value – each grid reference (or slot) can be empty, ‘x’ or ‘o’
  • Move Sequence – a complete set of moves that define a game, for a Grid Reference length of 9 (3 by 3 grid) there are Factorial(9) set of Move Sequences, a valid example of a move sequence for 3 by 3 grid:
    [1, 3, 4, 6, 5, 7, 9, 8, 2] : alternate moves by player 1 and 2

    Each player takes a symbol and sticks with it (‘x’ or ‘o’)In my post Player 1 always uses ‘o’ and Player 2 ‘x’, this choice has no impact on the final result

  • Set of Move Sequences – a set of move sequences, these can be the full set (all possible moves) for grids of size 3 by 3 (2 by 2 is a trivial case as we shall see). As we move to larger grids the total set of possible moves increases at a Factorial rate therefore we can only sample from the full set of move sequences.
    Grid size, Number of Grid Slots, Total number of moves
    2x2, 4 slots, 24 move sequences
    3x3, 9 slots, 362880 move sequences
    4x4, 16 slots,  >20 trillion move sequences

The interesting thing about regular tic tac toe is that it is deceptively simple as a game with straight forward rules, but can throw some surprising results. The other interesting point is the one related to the rapidly exploding set of possible move sequences.

The Target

How do we analyze games, develop strategies and generally have some fun with this ‘friendly’ problem? Do the strategies remain the same as we scale up the grid?

Approach

I built a tic tac toe simulator to generate move sequences and process them to analyse the final result using Python.

I also used MatplotLib for plotting results and AnyTree for generating brute force move sequences. It is very easy to extend the code and incorporate optimum strategy results to build a tic tac toe bot.

The Python file is attached at the end of this post.

Data Collection

The process of collecting data is very simple.

A set of move sequences is generated (brute force for 3 by 3 grid will generate the complete set of move sequences) by sampling without replacement (size: 10000) from all possible move sequences.

Sampling

The sampling is carried out using a Markov Chain – starting with an initial move sequence (a list of grid references or slots – for 3 by 3 this will be [1, 2, 3, 4, 5, 6, 7, 8, 9]) we (with uniform probability) pick any two moves and switch them. Thus the next state depends only on the previous state.

As an example:

Pick the first and last move to switch.

Sequence at Step t: [1, 3, 4, 6, 5, 7, 9, 8, 2]
Sequence at Step t+1: [2, 3, 4, 6, 5, 7, 9, 8, 1]

The sample size for Grids more than 3 by 3 is 10000.

Using the sampling we can estimate the following given arbitrary grid size:

  • Is there any advantage in starting first?
  • How many games end in a draw or have second movers as winners?
  • Which are the ‘best’ starting squares?
  • How are these factors affected by grid size?

Results

I experimented with grids of size 3 by 3, 4 by 4, 5 by 5 and 6 by 6 (here we are going beyond the Age of the Universe w.r.t. number of move sequences!) and pulled out some interesting statistics!

3 by 3 Grid:

Here the first mover has a CLEAR advantage. It is not surprising because the first mover gets 5 moves as compared to the second user. But the advantage is QUITE SIGNIFICANT.

First Mover Advantage:

  1. The First mover wins 58.4 % of the games (using brute force: 58.492%)
  2. The Second mover wins 28.8% of the games (using brute force: 28.809%)
  3. There are 12.7% instances of a Draw (using brute force: 12.698%)

2 by 2 Grid (An Interlude)

If you are wondering about the 2 by 2 grid (and why we called it a trivial case) then try out a few simple games of 2 by 2 tic tac toe as a thought experiment. In case you are impatient the 2 by 2 grid becomes a trivial case because there is no possibility of a draw or the second mover winning. The first mover wins in all 24 move sequences! You could brute force it on a piece of paper.

3 by 3 Grid Plots

The graph below shows a 3 by 3 grid histogram of winning percentages for First Movers (Orange), Second Movers (Blue) and Draws (Green).

3×3 Grid: First movers in Orange, Second Movers in Blue, Draws in Green

The above histogram clearly shows the difference between the three.

Strategy for Tic Tac Toe!

For the first movers the best starting square by far is 5 (right in the middle and opens up 4 winning lines – most of any starting square, all other squares open up to 3!). Second best option then becomes the corners (1, 3, 7, 9).

For the second movers the best starting squares are 2, 4, 6, or 8 (a diamond pattern).

4 by 4 Grid:

When we increase the size to a 4 by 4 grid we get 16 slots with > 20 trillion move sequences. It is difficult to analyse this (and probably pointless) using the brute force approach. To do this quickly we can use the sampling approach where we randomly sample move sequences (as described before) and measure how many of these lead to draws, first mover wins and second mover wins. This will obviously be an approximate measure.

The result is presented in the histogram below. Once again First movers in Orange, Second Movers in Blue and Draws in Green.

This time we see that there is high chance of a draw (~ 42%), first movers still win more than second movers but the difference is less dramatic (~ 31% for first movers and ~ 26% for second movers). We also see that the first and second mover distributions are starting to overlap at the edges.

4×4 Grid: First movers in Orange, Second Movers in Blue, Draws in Green

5 by 5 Grid:

For a larger 5 by 5 Grid it is impossible to do a brute force calculation as the full number of move sequences reach a stunning Factorial 25!

Using the same sampling approach we can again plot the percentages as a histogram.

As expected the chance to draw has now increased to ~60%! First movers win only about ~25% of the time where as second movers win only about ~13% of the time.

5×5 Grid: First movers in Orange, Second Movers in Blue, Draws in Green

6 by 6 Grid:

Finally doing the same for a 6 by 6 Grid we find that there is a ~75% chance of a draw! There is also almost no difference between first movers and second movers (or very little difference) and both are in the 12 – 15% range. Thus as we increase the grid size it becomes more difficult to win and there is no real advantage in moving first.

6×6 Grid: First movers in Orange, Second Movers in Blue, Draws in Green

Next Steps:

Obviously the experiments given in this post are not the final word. They can be further improved by implementing parallel processing so that we can increase the sample size (especially for larger grids).

To answer the questions we started with:

  • Is there any advantage in starting first? – Yes, definitely! Right up till grid size of 5 by 5.
  • How many games end in a draw or have second movers as winners? – More games end in a draw as the grid size increases. It is almost always bad to be the second mover!
  • Which are the ‘best’ starting squares? – For the 3 by 3 Grid we have:
    • For the first movers the best starting square by far is 5 (right in the middle and opens up 4 winning lines – most of any starting square, all other squares open up to 3!). Second best option then becomes the corners (1, 3, 7, 9)
    • For the second movers the best starting squares are 2, 4, 6, or 8 (a diamond pattern).
  • How are these factors affected by grid size? – As the grid size increases a draw becomes more likely.

Larger Sample Sizes:

What if we increase the sample size from 10000 to 100000 (a factor of 10)?

Let us see what happens to the spread of the first movers, second movers and draws in case of 5 by 5 Grid and 4 by 4 Grid:

Grid Width 5×5: Large Sample, First movers in Orange, Second Movers in Blue, Draws in Green

Grid Width 4×4: Large Sample, First movers in Orange, Second Movers in Blue, Draws in Green

The spread is now far less as compared to the 10000 sample graph. This means we get the percentage values with higher degree of accuracy. The spread looks more like Burj Khalifa than the Shard!

 

Tic Tac Toe python code file can be found HERE!