In this blog post I will introduce a way of thinking about learning, including machine and human learning. I want to propose this framework as a mental model specifically useful to programmers as a perspective on data science and machine learning. I came to adopt this mental model while working on practical problems in ML and AI, including text classification and LLM efficiency and interpetability. Chess is used only to illustrate the model with a concrete example.
I call this model the “heuristic stack” model of an agent. An agent (chess player, LLM, ML or AI model, computer program, human) is something that makes choices (produces outputs) in response to some state of affairs. The heuristic stack lets us model any agent as a combination of smaller parts that all have the same shape. It is an answer to the question: if we have some agent that performs some task, but that agent is complex beyond our understanding, how can we break the agent down into smaller parts that are more easily understood individually, while still explaining the full behavior when taken together.
Here are a few examples of questions that the heuristic stack framework lets us address:
An AI model is interpretable when it can be broken down into terms that we can understand, and when we can show that the behavior of the model is simply the result of the combination of all of those terms.
As a novice chess player myself, I find chess interesting for it’s own sake, but as a programmer it is even more interesting as a way to explore AI and the limits of human knowledge and learning. Chess is deeply connected to the AI field; every major AI technique or advance has been applied to chess. It is also well-placed between mathematical certainty and partial knowledge.
Chess follows well-defined rules and in a Platonic sense, questions like whether the game of chess is a draw have defined, mathematical answers. In fact, every position is objectively either a draw, or a win for white or black.
In contrast, the actual play of the game is all about uncertainty. We do not know the objective evaluations of our moves (or chess wouldn’t be interesting as a game) but there is also second-order uncertainty. We also cannot know which lines our opponent has reviewed the day before, which lines are more likely to lead one player or the other to blunder, and so on. Because of this, the play of the game involves luck, psychology, surprise, and all kinds of human factors.
Chess is further interesting to machine learning and data science because of the ready availability of data:
Most people working in AI or data science would dream of having the access to even a small fraction of the things that are freely available for chess.
We can measure the performance of a heuristic stack model, or any model, by measuring the reduction in information of a given dataset.
We define a dataset as a sequence of events , each drawn from some event space , having possible events. The total information of the event sequence is then . Here is the number of events in , and is the number of possible events in the set from which the events are drawn. Each single event has total information. There are various names for total information across fields, including maximum entropy and channel capacity. An equivalent description would consider as an alphabet, and as a sequence of tokens drawn from that alphabet, where we then have giving the maximum information that can be transmitted by a string of length . What is great about this as a framework is that, with any dataset, we can start with the total information and then add heuristics and see how they chip away at the total information, which goes to zero when we have perfect prediction.
For a chess dataset we can take the events to be moves, and we can add other kinds of events to cover timing information and other metadata. Then we would regard a chess dataset (e.g. the lichess database of 7 billion games) as some sequence of events drawn from this set of some few hundred possible events. The total information of that dataset is then just the log of that number of events, times the number of events in the dataset. There are many ways to break a chess dataset down into a sequence of events, just like there are many ways to tokenize text, and these have significant downstream effects, just as tokenization does on LLM efficiency.
The event space determines the richness of the model and what kinds of behaviors it can represent. It is necessary to add events to to represent internal states of the agent in order to represent most interesting models, including human chess players. If we simply have a fixed set of heuristics, and we run those over a game position and combine the results using some simple math, then we will get a result in constant time for any position. Clearly this is not how human thinking works, so to represent human thinking fully, we would have to add to our model some representation of the human’s mental state while thinking about the game.
Similarly, a heuristic stack model representing an ML model requires representation of the internal state of the model as part of the event space.
Our model is all about representing some ability as a combination of smaller abilities. These are the “heuristics” in the heuristic stack.
A heuristic, informally, is a rule of thumb. Heuristics include all the chess knowledge that we can directly express in language, as an instruction to tell someone else how to play the game. For example, any idea you have ever read in a chess book, if it affects your play, can be expressed in the form “In situations like X, do Y” where X is some kind of situation in the game, and Y is some kind of move, or a strategy that will lead to particular moves, and so on.
Formalizing X and Y leads us to an appropriate mathematical or programmatic representation of a heuristic.
As a program, a heuristic is a function that takes as input some state (e.g. a chess board position) and as output produces some influence on what the next action of the agent will be (e.g. a move). To turn a heuristic into a program, we need to make X and Y concrete; we can represent X as just a function that takes the state and determines whether the heuristic applies at all.
Heuristics generally are not hard-and-fast rules, so we need probability theory to represent what they do. Given some situation, a heuristic gives us a hint as to what to do, but it doesn’t force us to do that thing. So our heuristics must have an output that somehow influences, but does not fully determine, what happens next.
Both “play checkmate if you see it” and “centralize your Queen” are heuristics familiar to most chess players. We could represent the first as a function that identifies positions where there is a checkmate move and gives that move’s probability a big boost. The second could give the probability of any Queen move a boost if that move is to one of the center squares.
Mathematically we can represent a heuristic as a partial function from the state of the agent (or the world) to some adjustment to the probabilities of what the agent does next.
Now that we’ve formalized our idea of a heuristic, can we combine them into a coherent model? Assume we have a bag of heuristics, represented as partial functions like our play-checkmate and centralize-the-Queen functions. Then in any chess position, we can get back a bunch of adjustments: “play Queen to f7 (because it is checkmate)” might get a big boost, while “play Queen to e5” (one of the central squares) would presumably get a much smaller boost.
It is nice that the heuristic stack model is built on something so straightforward. This means that any model or complex behavior can always be represented as a set of heuristics in the ordinary sense.
To evaluate our model against a dataset we must combine the individual heuristics to give a single output. Let’s take the programmer’s perspective.
Given a set of heuristics, we combine into a model that takes an event sequence and gives a probability distribution for the next event over the event space . Our heuristic stack model, as a program, has the same shape as the individual heuristic. It is a function from some state to some probability distribution over the next event. Regardless of what kind of events we have in our dataset, we can write this program with only:
For a chess dataset, we can have heuristic functions which take as input a board position (or some richer representation of game state) and which output, for zero or more moves in the position, some positive integer that represents a boost to the chances of playing that move. We can represent these boosts as small positive integers, e.g. as a single unsigned byte taking values from 0 to 255. For example, we can easily write our play-checkmate heuristic as a function that puts +3 on any move that delivers checkmate. On positions where there is no checkmate, of course, this heuristic doesn’t have any effect. Our internal state function takes the sequence of moves, and represents the current board position or any other game state information (such as clocks). Then to combine these changes into a single probability distribution, we can do something very simple:
So our heuristic stack model as a program is easy to write if we already have the heuristics. We just accumulate all the heuristics and run softmax over the result. Is such a simple model really powerful enough to be useful?
It turns out to be more powerful than we might expect, and in fact we can show equivalencies from this model to many other things:
This is our heuristic stack model. It is a set of simple rules that just give us some kind of push in some direction in particular situations, and combined with some straightforward math that can be done efficiently, combines those pushes to give us an agent that can play chess or simulate any other human behavior or data.
Once we have a dataset and a model, we can measure the fit of the model to the dataset. If the model is an understandable combination of understandable parts, then we can say we have explained the phenomena in an understandable way.
We measure how well our understanding explains the data of some dataset by measuring the remaining information after applying our model. If we write for the probability assigned to the event by the model given the prior sequence of events up to that point, then the information of the dataset under that heuristic stack is equal to where is the sequence of events prior to in the dataset. This is called Kullback information or Kullback-Leibler divergence. K-L divergence is measured in information units, and it is the difference between the information of a dataset under one model and another.
To a programmer, the most intuitive understanding of K-L information is by thinking of a compression program. If we have a dataset and a model and we compress that dataset using that model, the K-L information is literally just the number of bits that we have to store in our compressed data file to be able to recreate the original data. So K-L information, very intuitively, divides the total information of our dataset into the part that our model explains and the part that it can’t explain. The part that it explains we can throw away, and the bits we have to store measure exactly how much isn’t explained. If we can compress a dataset into a file that is 80% smaller with an explainable model, then we understand 80% of the phenomena.
It is possible for a model to overfit to a particular dataset, and fail to generalize to new data. The availability of so much chess data helps solve this problem.
Now we have presented the heuristic stack model, I would like to make a few arguments as to why this model is interesting.
Let us say that we want to teach people how to play chess better. All we can do is give them advice of the form “in situations like this, do that”, which is the form of our heuristics.
If we build a model that is built only on understandable heuristics, like the ones that chess players commonly repeat or that are written in chess books, then we may find that the model cannot reach a great strength. However, we know from the generality of our model that this is not a limitation of the model, and it must be due to the set of heuristics we have picked.
Another way to describe a chess player’s skill in chess is like this:
As we mentioned above, this fits within our heuristic stack model, by adding events to that represent changes in our internal state of mind.
This means that there are some heuristic stacks that are actually accurate models, not only of the results of a human’s thought process, but also of the intermediate internal states.
This implies that there exists some stack of heuristics that actually accurately models your own chess playing “program” that plays out in your head over the board, and determines the things like which moves you consider and which tactics you see, i.e. your state of mind, which then finally determines your move. We can even argue that your whole mind is just some internal state (including senses and your actions) and some stack of heuristics that adjust that state.
We’ve seen that heuristic stacks can explain any behavior, but what is still remaining is to ask how complex those stacks must be (whether by containing complex heuristics or by large numbers of simple ones) and how we can compare different heuristic stacks against each other.
A few interesting results follow directly from our definitions. First, if any two stacks A and B each explain most of a given phenomena, then necessarily they are equivalent, specifically in the overlapping part of the phenomena which they both explain.
Let us assume a dataset with bits of total information, and two stacks, and , which partly explain the dataset, with and remaining information, respectively. Then we can see that, even in the worst case, at least of the same information is eliminated or explained by both models. The explanations given by both stacks within this area of overlap are necessarily equivalent, even though on the surface they may be expressed in completely different ways, may be different in number, and may select different subsets of the data that they act on.
In programmer terms, if we have two compression programs that take 1 GB of data into 100 MB and 80 MB respectively, then they must explain at least of the same information, which means they must explain at least 82% of the phenomena in exactly an equivalent way, even if they seem on the surface to be completely different.
For the chess player, this tells us that, while there are a nearly infinite number of ways to explain or achieve play at any level, to the extent that any explanation is correct, it must be deeply equivalent to all the other correct explanations.
I call this principle “explanatory sufficiency”. It means that if any explanation of some complex phenomena works, then it must be equivalent to some other explanation that also works, even if they seem unrelated.
For example, if a chess heuristic like “centralize your Queen” has value, then it must be explainable in terms of engine lines. We must be able to show a positive correlation between top engine lines and centralizing Queen moves, a relationship that we can then explore in many ways.
Many chess players have dreamed of an algorithm for solving chess. This would be something that can simply be memorized and applied, avoiding the need to spend years developing intuition and pattern-matching abilities. The same elegant mathematical underpinning of chess that we alluded to earlier means that such algorithms must exist, in principle. Just as we can prove, in a Platonic sense, that every position in chess has a mathematically-certain evaluation as a win for one player or the other or a draw under perfect play, we can also prove that there exists some shortest possible algorithm that can give, in any position, one of the correct moves in that position.
We don’t know the complexity of this algorithm, only that it exists. Assuming it is more complex than what a human could learn and manually apply, there also exists, among the simpler algorithms that a human player is capable of learning and using, one that most closely approximates the true algorithm.
This means there is some set of heuristics, some ideal collection of chess advice, that is the best possible way for humans to learn chess. It’s unlikely that our current ways of teaching chess are anywhere near this global maximum.
Our heuristic stack model doesn’t breathe new hope into these dreams of solving chess with a simple algorithm that anyone can understand and memorize. However, it does let us quantify exactly how far such rules can get us, and measure them. If we can break down actual human play into the actual human heuristic stack that different players learn and use to play, then we can explore these questions directly and scientifically, and at least measure and compare the heuristic stacks that we have, to measure our progress against that ideal one that we know must exist.
When I’ve presented these ideas before, some people take the term “heuristic” to mean only a program that is written by a human. We think of expert systems from the AI boom of the 80s, which involved thousands of hand-written rules. Our model does not share the limitations of these systems, but we have to consider both human-written and automatically generated heuristics.
We have interesting ways to generate heuristics that can then be combined into stacks and compared, including:
In our model, we presented a heuristic as giving a positive boost to some moves over others, as a fixed small integer. These correspond to weights in an ML context, and they can be learned in the same way. A practical way to build a heuristic stack from scratch is then:
The training step follows well-known AI techniques and is a solved problem. This means the interesting part of constructing heuristic stacks is really just picking an interesting set of heuristics.
Here I will describe some experiments that could be done along these lines and speculate about what such experiments might show us. Today we have chess engines written for maximum strength, which use tree search. These engines are strong, but they rely on machine capabilities that are not at all a good match for human thinking. Because of this, there is also interest in models that play in a more human way. These are generally traditional machine learning approaches of training a model to predict human play, but the model itself remains a black box.
The heuristic stack model gives us a framework to imagine a different approach. A heuristic stack that accurately models human play would also be explainable in human terms, because it would break down into individual parts that actually correspond to real human skills.
An accurate human model should:
There are many ways to build an engine that can reach super-human skill. This problem was solved definitively in 1997. If I was to build a chess engine today, rather than simply trying to solve the problem of achieving super-human play, which is already solved, I would work on the much more rich and interesting unsolved problem of modeling human chess play and chess learning.
We conclude with a few sample experiments that could be performed within this framework, followed by a brief sketch of the approach to programming them.
The most basic ML experiment of all is to build a model and measure accuracy on some dataset. For a given heuristic stack model we can answer questions like:
To run this experiment, we just need the data and a heuristic-stack model. A little wrapper can run the model and measure the information gain. As mentioned above, we can run this experiment by starting with just heuristics as predicate functions, and then find the weights for them by fitting the model to the data. The interesting question is how we pick the heuristics, and how granular they are.
The most appropriate place for human-written heuristics is as the direct expression of human advice. For example “centralize your Queen” can be trivially turned into a predicate that matches moves that meet the human understanding of that advice. A heuristic stack model that includes a set of all the standard chess advice, or all that advice collected from some set of books, lets us answer questions like:
This could lead to giving better or more nuanced advice to players at each level.
When a player blunders, it is because that move looked good for some reasons. Heuristics can explain both why a move looked good, and why it actually isn’t, giving us a way to directly explain mistakes in a way that the player can immediately benefit from.
In an opening we may play the same move we always play, so our move in that position is something of a policy. We can derive heuristics like this one directly from a dataset, by looking at players who play the same opening moves more than once.
What heuristics to include depends on what we are trying to learn from our model. A heuristic like this isn’t useful if we are trying to explain to a beginner why a move is good. Then, “because it’s the move that’s played here” is a rather unsatisfying answer. But if we are trying to model human play correctly and accurately over a dataset, including a heuristic that takes care of people’s memorized lines means that the rest of the stack will do a better job modeling their moves in novel positions.
An interesting experiment if you have an existing heuristic stack that does well on the whole Lichess dataset is to take that heuristic set and re-train it separately on each individual player.
It might be that every time my opponent has a knight fork, I miss it, and so I always play into knight forks and lose material. Then it would turn out that if there is a “seeing knight forks” heuristic in the stack, it would be lower weighted for me.
There are many powerful ways to parameterize over individual players by extending the event space , but reweighting per player is easy to implement.
An interesting heuristic stack to design is one that matches some existing model of how we play chess. Several of these have been written about extensively.
The usual account is that we have some kind of loop, like:
A model that’s this simplified is clearly not the real human decision procedure. For example, we don’t evaluate candidate moves only once. The value of this experiment is to try very simple models, see where they fall short, and which simple models are the best.
We would begin by extending our event space to support a rich internal mental state. This might include things like candidate moves and the memories that we have of those moves already considered (and of lines evaluated before).
It includes all the fuzzy things that we do that aren’t strict tree search. A trace of our model might include events like considering a new candidate move, rejecting it, considering another move, and so on.
Unlike the previous experiment, here we would want to derive these internal events (the set of them) themselves through an automatic and iterative process of discovery, as part of a training step, rather than by hand.
Such a model would be a powerful tool for chess training. It could tell us things like “relative to other players, you often spend too much time analyzing the first move you consider, rather than switching earlier to another candidate move and analyzing that”. This would be found because:
A model that does not model the decision process is limited to giving advice that is based on the aspects of the position itself. The more accurate we capture the true human thinking process, the more useful advice we can give to players.
Some experiments might be more suitable to beginners, or to grandmasters.
One interesting perspective is to take a heuristic stack that starts with the stockfish evaluation, and then adds further heuristics on top. When we train this stack to match human players, we essentially are training the heuristic stack to predict only the mistakes. The correct moves have already been explained by the engine evaluation.
For grandmasters, something that starts with Stockfish and then adds mistakes would be a useful model. When grandmasters play the correct moves, it’s not interesting, because that is what usually happens. What is interesting in grandmaster games are the mistakes, and if we had a player-specific characterization of the kinds of mistakes that they make, that could be very useful to either the player or to an opponent preparing for a match against them.
On the other hand, for absolute beginners, a model that starts with nothing and adds heuristics is more interesting. Surely the simplest context to explore chess learning would be to model players who have just learned the moves. One way to build a general model of the human player is to start with beginners and derive heuristics automatically from beginner play, then from a slightly stronger cohort, and so on, so that we can see how simple heuristics (like “if there is an undefended piece, capture it”) define early play, and then become refined or removed as more powerful heuristics are acquired.
If we built up a set of such heuristics from players across multiple levels, it would give a kind of ladder that players climb as they develop, and this would let us identify some of the ways players get stuck. Bad habits are also heuristics.
Our existing chess skill is also the reason why we do not improve further. We have habits which helped us reach our current level, but prevent us from going beyond it. We may know consciously that getting better sometimes means first getting worse, but we don’t know specifically which heuristics we need to drop or dial down. A heuristic stack model would help us uncover these stumbling stones and break through the walls that chess players hit at certain levels.
The bitter lesson is the observation that putting what we know into the model has historically had worse results that simply constructing a generic learning capability with an appropriate loss function and throwing data and hardware at the problem. While true for the goal of simply solving the problem of accuracy, we should not forget that the original goals of AI research went far beyond simply beating humans at chess, or correctly predicting text tokens. The dream of AI has always been that by modeling human cognitive abilities, not only do we gain the ability to replicate those abilities, but also we should gain insights into how humans perform them, with obvious applications to understanding human performance and improving human learning.
I have presented these ideas here using chess, but the same considerations apply to text or any other data modality to which ML has been applied. In chess, the easy problem of super-human performance was solved in 1997 by embarrassingly brute-force means, and the problem of predicting text tokens has recently been solved in an even more brute-force manner. What remains, in both cases, is the much more interesting problem to solve these problems again in ways that are compatible with the human approach.
The bitter lesson is useful guidance when you are simply applying ML to solve a problem. However, if we are interested in continuing to move the field forwards towards AGI, there must be a “tick-tock” of the pendulum, where the raw abilities that we gain through brute-force means are then systematically broken down into things that we can understand and reinterpret in human terms. I think the timing is right for interpretable chess models; the corresponding “tock” in LLMs will undoubtedly be more difficult, because the gap between the most powerful models and the most explainable ones is greater there.
The conclusion of this document is to sketch a toolkit for exploring these ideas further. Most parts are readily available.
Requirements of the toolkit:
For working with chess databases, working with engines, and measuring information gain of a model, there are already excellent tools available. Python has libraries that make all of these tasks easy, and I have also had good results using Stockfish directly as a subprocess. The PGN format makes parsing Lichess or other chess databases relatively easy even if you do it from scratch.
The requirements that are more specific to this model are around working with heuristics, and combining a set of heuristics into a model, and fitting the model to a dataset to find the optimal weights (the adjustments made by each heuristic). Representing heuristics as ordinary functions means that no special tooling is required there, but combining and training a model still requires some work and a bit of specialist knowledge. A useful direction for future work could be to release a Python library to make this model easy for anyone to use.