The formal phrase is “finite state automaton“, which is imposing and mathy and often too painful to contemplate, until you realize what kinds of things are actually state machines [1].
Tic-Tac-Toe is a state machine. The diagram above, from Wikimedia, shows the partial solution tree to the game.
Tic-tac-toe is a state machine. You have 9 positions on a board, a state of empty, X, or O, marks that can be placed on the board by a defined set of rules, and you have a defined outcome from those sets of rules.
Checkers is also a state machine.
Checkers (draughts) is a state machine. You have 64 positions on a board, pieces that move through the positions via a set of defined rules, with a defined outcome from those rules.
Chess is a state machine.
Chess is a state machine. You have 64 positions on a board, pieces that move through the positions via a set of defined rules, with a defined outcome from those rules.
If you can comprehend checkers, or even tic-tac-toe, then you can understand state machines.
To treat football as a state machine, start with the idea that football is a function of field position. There are 100 yards on the field, so 100 positions to begin with. Those positions have states (1st and 10, 2nd and 3, etc), there are plays that lead to a transition from position to position and state to state, there is a method of scoring, and there is a defined outcome that results from position, states, plays, scoring and the rules of the game of football.
A lot of the analytical progress that has been made over the past several years comes from taking play by play data, breaking it down into things like games, drives, scoring, and so forth, compiling that info into a state (i.e. down and distance) database, and then asking questions of that database of interest to the analyst.
You can analyze data in a time dependent or a time independent manner. Time dependence is important if you want to analyze for things like win probability. If you’re just interested in expected points models (i.e. the odds of scoring from any particular point on the field), a time independent approach is probably good enough (that’s sometimes referred to as the “perpetual first quarter assumption”).
Net expected point models, all downs included. The purple curve does not account for response opposition drives, the yellow one does. The yellow curve was used to derive turnover values.
Take, for example, Keith Goldner’s Markov chain model. As explained here, a Markov chain is a kind of state machine. The same kinds of ideas that are embedded in simple state machines (such as tic-tac-toe) also power more sophisticated approaches such as this one.
Once a set of states is defined, a game becomes a path through all the states that occur during the course of the game, meaning an analyst can also bring graph theory (see here for an interesting tutorial) into the picture. Again, it’s another tool, one that brings its own set of insights into the analysis.
[1] More accurately, we’re going to be looking at the subset of finite state automata (related to cellular automata) that can be represented as 1 or 2 dimensional grids. In this context, football can be mapped into a 1 dimensional geometry where the dimension of interest is position on the football field.
Notes: The checkers board is a screen capture of a game played here. The chess game above is Nigel Short-Jan Timman Tilburg 1991, and the game diagram (along with some nice game analysis) comes from the blog Chess Tales.
October 11, 2011 at 10:26 am
[...] states. For now, by way of example, we’ll use these raw NEP data I calculated for my “states” post. We’ll plot an opposition set of data upside down and show what a state [...]
October 15, 2011 at 12:35 pm
Doesn’t this analysis end with the same stable matrix the Markov Chain model did?
October 18, 2011 at 3:45 pm
Good question. If by default everyone should end up with the same matrix Keith Goldner does, then why do the expected points curves of different analysts look different?
I suspect it’s because there are different ways of calculating the score to be assigned to a play.
I’m going to try to analyze that later, in a qualitative way.
David.
October 15, 2011 at 3:46 pm
Really? 64 positions in checkers??!? I thought it was only 32. Nice mathing.
October 18, 2011 at 3:42 pm
An 8 by 8 board has 64 positions. Didn’t say all of them could be occupied. A tic-tac-toe board has offhand 3**9 possible combinations of positions and states, but some of them will never be reached by playing the game.
David.
October 18, 2011 at 5:19 pm
The checkers or “draughts” game is played using a MAXIMUM of 32 positions on a CHESS board.
October 21, 2011 at 12:18 pm
[...] reintroduce data we described briefly before, but this time we’ll fit the data to curves. Linear fit is to formula Scoring Potential = [...]
August 21, 2012 at 1:02 pm
[...] models are a class of related models which can be quite different in value (discussed here, here, here). If you need independent verification, please note that Keith Goldner now has published 4 separate [...]