This article is just me playing about with math, and showing how to extrapolate in ways that might not be immediately obvious, looking at how much AI can memorize chess

Summary

The Licess chess database has 5 billion chess games recorded. There is no evidence of us even scratching the surface of unique chess games. Games are really unique. Even if an AI memorized all 5 billion games, it would help for approximately 4 moves, and then the game would be unique

Background

In 2019, the lichess chess database had 500 million games recorded.

In those games, as of 2019, there were 21.5 billion unique positions, and 76% of all positions were unique. So a game had an average of 32 unique positions. A chess game has only 34-35 moves on average, so any given game is going to start being unique in only a few moves!

But as of writing in Nov 2023, the lichess chess database now has almost exactly ten times more games. Can we extrapolate how many unique positions it has now?

Power Law Approximation (Similar games are rare, but happen occasionally)

It’s not something we can answer without more data, but a reasonable starting point with the assumption that similar games are rare but happen occasionally, is a power law of approximately 0.5. Since we have 10 times more chess games, we can expect approximately sqrt(10) more unique positions, so ~68 million unique board positions in 2014 in 5 billion games.

Logarithmic Approximation (Similar games happen often)

As a conservative lower limit for this curve, we could instead fit logarithmic decay curve, instead of power law, to this using two data points:

1. 1 game corresponds to 35 unique positions.
2. 500 million games correspond to 21.5 billion unique positions.

So we want to solve:

35 = a log(b + 1)
21,500,000,000 = a log(b * 500000000 + 1)

But Wolfram Alpha timed out trying to solve it.

In python, solve and nsolve failed to solve it, but least_squares cracked it:

from scipy.optimize import least_squares
import numpy as np

# Define the function that calculates the difference between the observed and predicted values
def equations(p):
    a, b = p
    eq1 = a * np.log(b * 1 + 1) - 35  # Difference for the first data point
    eq2 = a * np.log(b * 500_000_000 + 1) - 21_500_000_000  # Difference for the second data point
    return (eq1, eq2)

bounds = ([1, 0], [np.inf, 1])


# Initial guesses for a and b
initial_guess = [10000, 1e-8]

# Perform the least squares optimization
result = least_squares(equations, initial_guess, bounds=bounds)

a_opt, b_opt = result.x
cost = result.cost

# Check the final residuals
residuals = equations(result.x)

print(f"Optimized a: {a_opt}")
print(f"Optimized b: {b_opt}")
print(f"Residuals: {residuals}")
print(f"Cost: {cost}")

Gives me: 1757372725 log(0.000411370x + 1)

Which gives ~25 billion unique board positions in 2023 for the conservative lower bound. (See summary for more)

New Data Point found! Lichess Opening Explorer

Lichess released an opening explorer – 12 million chess games, with 390 million unique positions. This gives us a new data point to test which model fits. This is what we have so far:

Let’s zoom in and see which model the lichess opening explorer fits:

The linear model! This means that the database of 5 billion games does not even scratch the surface of the 10^44 possible board positions in any way that we can detect…. although written like that it’s kinda obvious tbh.

Summary and interpretation

In the 2019 Lichess chess database, there were 500 million games, and 75% of game positions were unique,

In the 2023 Lichess chess database, there are 10 times as many games, and so extrapolating:

There are ~68 billion unique board positions using a power scaling law of 0.5. This is an empirical guess which models what we frequently see in nature. With 5000 million games and 35 moves per game, this means that only 0.4% of board positions are unique, and only 1.4% of games have a board position that hasn’t been played before.

There are ~25 billion unique board positions using a conservative lower bound estimate using logarithmic scaling). With 5000 million games and 35 moves per game, this means that only 0.14% of board positions are unique, and only 0.5% of games have a board position that hasn’t been played before.

If a board position can be stored in an average of 8 bytes (64 bits) then this could be stored in 1.4 GB. So easily fit in an over-fitted trained AI. But there are 10^44 possible board combinations. There is no evidence that we are even scratching the surface of being able to memorize

Conclusion: AI could memorize the entire 5 billion chess games, and it wouldn’t help. Probably.. see caveat

Caveat

This whole thing was kinda of a joke, and there’s one big serious flaw with the final conclusion. If the AI plays a move from the database, that’s no longer a random sampling of a game from the database, and the chance of a similar game being played goes way up. But in a way I can’t model. Oh well.

Edit: User Wisskey pointed out that, among other mistakes that I’ve made and fixed, that:

A move in chess corresponds to moves (actually called plies instead of moves) by both sides, so 1 move = 2 chess positions, not 1 chess position.

User: Wisskey

So, I’m probably off by a factor of 2 in places, not that it’s going to matter much to the final conclusion

I wanted to laser cut acrylic plastic, and then bend it into shapes.

So I mocked something up:

(The pink glow was my attempt to render a glow hot wire)

It’s extremely simple. It’s just a base and a channel along one edge with a nichrome wire (the wire used in e-cigarettes).

I actually built 5 of these, in different styles, methods and sizes.

And here’s a version built:

Here you can see how the wire is secured. It wraps around two bolts, and held in place with nuts. One end is connected to a spring because the wire shrinks as the wire gets hot.

I apply 12V across the wire, wait a minute for it to become hot, then place a piece of acrylic across the wire, wait a few seconds for it to become soft, then bend.

Folding version

Out of the five I built, three of them used a second piece with a hinge, like below, and also used an actual metal channel. My thinking is that I would heat up the plastic, hold it in place, then bend it smoothly with the second piece. However I found that I never used the hinge – it was far easier to just bend against the table or bend it around a piece of wood etc

Example

The main use was to bend the casing for my wire bender and mars rover, but these aren’t done yet.

So here’s a cat’s water bowl holder that I made, by bending acrylic around a 2×4 block. I laser cut a circle first to allow the water bowl to fit.

Fast development

The real key to fast development is outsourcing the hard work:

I found some acorns and bit of branch. Decided to paint them with a Totoro feel:

My daughter loved this ‘Flamingo’ song on youtube, so I laser cut out the ‘shrimp’ in wood, acrylic and pink paper, then mounted them together with an android tablet all inside of a frame. The result was pretty cool imho. (Unfortunately I can’t show the full thing for copyright reasons.)