Where Is the Algorithm? Two tic-tac-toe players and what they mean for teaching algorithms

I built two tic-tac-toe players. One solves the game by dynamic programming. The other learns it by playing 200,000 games and never sees a model of the game at all. Both finish as a table of numbers I did not type, and neither contains a rule anyone wrote about where to open. That is the puzzle people raise about language models and learned agents, sitting inside an exercise from an undergraduate algorithms unit.

I wrote this as the High Distinction position paper for SIT320 Advanced Algorithms at Deakin in T2 2026. I shaped it as a computing education research paper, then decided to publish it here myself rather than send it to a conference. This post is the paper, shortened. The full PDF is linked at the end.

My answer is that "the algorithm" is relative to a level of description. Relative to the generic executor, the table a player reads is input. Relative to the deployed player, that table is part of the procedure that runs. The boundary I draw runs between a generic executor and the persistent state it reads, and whether a person or a training run wrote that state makes no difference to it. That boundary is already inside dynamic programming.

The questions

The overall question is where the word "algorithm" points in a learned system, and what an algorithms unit should do about it. I split it into three research questions.

• RQ1. At which levels of description can "the algorithm" name a part of a learned system, and what does it name at each level?
• RQ2. Which run-time state belongs to a deployed algorithm, and does it matter whether a person wrote that state?
• RQ3. What should an undergraduate algorithms unit change because of the answers, and how could the change be tested?

The method is conceptual analysis. I state candidate answers and test each one against a fixed set of cases, against five conditions I set out before the analysis, and against what the two players actually printed. None of the conditions fixes which verdict an answer has to reach. They ask, for example, that an answer give a verdict on two bit-identical tables run by the same executor, one fitted and one typed, and that it say where it stops.

What has already been argued

Some of what I might have claimed as news was argued twenty years ago. Blass and Gurevich (2003) survey the attempts at an absolute definition and say "the notion of algorithm is richer these days than it was in Turing's days". Gurevich (2012) puts it harder: "the notion of algorithm cannot be rigorously defined in full generality, at least for the time being". Moschovakis (2001) argues that algorithms are recursive definitions, while machines model implementations. So the claim that the classical definition is incomplete belongs to them, and none of their reasons is machine learning. My part is narrower. I ask where the word points inside a running learned system, and what a curriculum should do about it.

Wegner (1997) argued that interaction is more powerful than algorithms. Cockshott and Michaelson (2007) replied to a later version of that argument that the input stream of an interactive run can be recorded and fed to an ordinary tape machine. I try to stay out of that fight by making a claim about description and not about computational power. Nothing here says a learned system computes a function no Turing machine can.

In computing education, Perrenet, Groote and Kaasenbrood (2005) describe four levels at which students think about the concept of algorithm, from one run on a concrete machine up to a black box chosen for a problem. None of the four has a place for state that is neither the program nor an input and that every run reads. Lonati and colleagues (2022) leave out, on purpose, programs whose logic is "machine produced" and, following Janlert, call them "dark". This paper takes up the case they scoped out. The level split itself goes back to Turing (1950), who wrote that the rules which change in a learning machine "are of a rather less pretentious kind, claiming only an ephemeral validity".

Two players for the same game

Tic-tac-toe has 5478 reachable board positions. Of those, 2423 are unfinished with X to move, and those are the states my players have to decide in. O has its own 2097. Every number below comes from my notebook's saved output, and every win rate is exact, scored over the whole game graph rather than counted from sample games.

The solved player treats the game as a Markov decision process, with the opponent folded into the transition probabilities. Value iteration converges in 9 sweeps, and the last sweep changes nothing. The empty board comes out at 0.994791666667, and a backward induction over the same graph in exact fractions gives exactly 191/192. Policy iteration, run separately, picks the same move as value iteration in all 2423 decision states. Against a uniformly random opponent this player wins 0.994792 of games and loses none. Against a perfect opponent every game is a draw.

The learned player is the tabular Q-learning of Watkins and Dayan (1992). It gets the legal moves, the board it lands on after each move and the result of each finished game, and it never sees a model of the game. I used a constant step size of 0.3, no discount, and an epsilon that starts at 1.0 and is multiplied by 0.99995 after every episode, ending at 0.00005. A win scores +1, a loss −1 and a draw 0. Both players break ties on the lowest cell index. After 200,000 episodes against a random opponent, its table covers 2420 of the 2423 decision states. It wins 0.989583 of games against that opponent, loses none, and draws every game against a perfect one. The whole run, including exact scoring of 100 checkpoints, took 0.9 seconds.

Watkins and Dayan prove convergence for step sizes that shrink. Mine stayed at 0.3, so their theorem does not cover this run, and the evidence that the learner plays well is the exact scoring.

They differ on the opening. The solved player opens on a corner, and all four corners are worth 191/192 against a random opponent. The learner's final table opens on the centre, which is worth 95/96. That choice never settled. The greedy policy opened on a corner at 21 of the 100 checkpoints I saved during training, 16 of them in the second half, and the centre is where the last checkpoint happened to land.

Then the part I did not expect. The learner's greedy move matches an optimal move in 0.9059 of all 2423 decision states. Of the 109 decision states that come up when it plays a random opponent, 108 are optimal, and the one it gets wrong is the empty board, which is the centre opening again. Its values are much further out than its moves are. Over the 8622 legal state-action pairs in the states it stored, the gap between its Q values and the true ones has a mean of 0.3423 and a maximum of 1.157. Picking the largest of the legal entries survives a lot of error spread across them.

The notebook also trained the learner on five more seeds, in a shorter setup of 100,000 episodes, and saved only summaries for those runs. Their win rate against the random opponent printed as 0.9885 ± 0.0013, and between them they opened on cells 1, 4 and 6, which are an edge, the centre and a corner. So the same learning procedure gave deployed players that open in three different places.

Three levels

Most of the disagreement here is people meaning different things by the same word, so I fix my terms first. An executor is the execution procedure a program runs on, such as an interpreter, a virtual machine or the forward pass of a network. Persistent control state is state the executor reads to decide what to do. It outlives any one input and is read again on the next. A comparator passed into a sort is persistent control state. So are a parser table, a script fed to an interpreter, the policy a dynamic programming solver reads off its value table, and a weight vector.

Whenever I write "the algorithm" I say which of three levels I mean.

• Executor level. The algorithm is the generic machinery, and everything it reads is input.
• Deployed level. The algorithm is the particular procedure running on this task, executor and control state together.
• System level. The algorithm would be the whole arrangement, including the people and the feedback.

The first two carry their weight as answers to where the algorithm is. The third gives no answer until it says where it stops.

Five places it could be

The learning procedure. Gradient descent, value iteration and Q-learning are classical algorithms in the full sense. Each stops on a rule you set, and you can state its complexity. But the same Q-learning update gave me a centre opener on the main run and an edge, a centre and a corner across the five shorter ones. So the learning procedure is an algorithm, and it is not the algorithm that plays.

The inference procedure. My move selector is a few lines in each player. It takes the largest entry among the legal cells and breaks ties on the lowest index. Handed a different table, either player plays differently, so the selector is not the whole answer. Strength is not always concentrated in the parameters either. AlphaGo Zero's raw network, picking its most probable move with no search, rated 3055 Elo against 5185 for the full system with Monte Carlo tree search (Silver et al., 2017). The competence there is split between a learned artefact and a procedure.

The parameters. At the executor level they are input, and at the deployed level they are part of the procedure. They are never the algorithm alone. A table with nothing to read it is an inert array.

The interaction between model and user. This can be written down as a loop, so it deserves a real answer. A chat with a model whose weights and prompt stay fixed is one run of a deployed algorithm, and the conversation so far is that run's input. A recommender that refits on your clicks is different. Every refit changes the control state, so a new deployed algorithm starts at each one, and the loop is the learning procedure running online with the user supplying its data.

All of it together. This sounds the most reasonable and I think it is the weakest. If the algorithm includes the model and the user, does it include the people who wrote the training data, the engineers who set the reward, or the electricity? Each of those changes the output if you change it, so a test built on causal influence has no way to exclude any of them.

The strongest objection

A universal machine has a fixed transition procedure and reads a program off a tape. Change the tape and it computes a different function, but the tape is not part of the universal machine's algorithm. Inference code plus weights has exactly that shape. So, the objection goes, the weights are input to the inference algorithm, and classical theory already has every word it needs.

I think that is right at the executor level, and it kills a tempting move. The move says that swapping the weights changes the output, so the weights are part of the algorithm. That proves too much. Swap the comparator in a sort, the tape in a universal machine or the table in a table-driven parser, and each computes something different. If determining the output made a thing part of the procedure, the input would be part of the algorithm too.

The compilation analogy, that weights are like machine code, runs the wrong way as well, because machine code is not part of the CPU. It does show that being found by optimisation rather than typed does not stop a thing being program-like, which is the point Karpathy (2017) was reaching for.

The objection leaves the deployed level alone, though. When I ask which sorting algorithm a process is running, I do not answer "the CPU". I name what the code encodes. Partial evaluation gives that level a classical form. Specialise an interpreter to one fixed program and the result "behaves exactly the same" as that program, which is the first Futamura projection as Williams and Perugini (2016) present it. Cook and Lämmel (2011) work a case close to mine, an interpreter for table-driven state machines, where in the result they aim for "The accept states and the transition table are no longer present as data structures". My solved player does a version of this by hand. It runs the move selector over its value table once for every position before any game, and at move time only the policy is left to read.

So the objection forces a distinction between levels, but it does not pick one.

The test for what belongs

My answer to RQ2 is that computational knowledge can be part of an algorithm, at the deployed level. Run-time state counts as part of a deployed algorithm when three things hold.

1. It is persistent.
2. The executor reads it to decide what to do.
3. The deployment holds it fixed across the inputs the procedure ranges over, instead of taking it as one of them.

That admits weights, a Q table, the policy my solved player reads, a comparator, a parser table and a script fed to an interpreter. For my solved player the value table itself is out, because nothing reads it at move time. A memo table that fills while a program runs is persistent and gets read, but the deployment does not hold it fixed, so it is out too. A system prompt held fixed across a deployment is in, and the words a user types in one conversation are not. The user, the training data and the hardware are not run-time state at all, which is what stops the composite answer spreading out to the power grid.

The price is that the test does not care where the state came from. Two systems running bit-identical tables under the same executor have the same status, whether the table was fitted, evolved, copied off a disk or typed by hand. So the category is not one machine learning invented. It is large and old, and neural networks are a recent and extreme member of it. Breiman (2001) made the same move in statistics, calling the fitted predictor "an algorithm that operates on x to predict the responses y".

The same test says when two deployed algorithms are one: same executor, same tie rule and same state. I checked this with a second solver that plans against a worst-case opponent. With ties going to the lowest index, the policy read off its table wins 0.994792 against a random opponent. With ties going to the worst of the tied best moves, worst as scored against the random opponent, it wins 0.848958. Not one value in the table changed. A different tie rule over the same table gives a different deployed algorithm.

Where the behaviour nobody wrote comes from

Nothing in my learner was told to open on the centre, and nothing in the solved player was told to open on a corner. In both, I wrote a general update rule, a way of scoring an outcome and a way of picking among scores, and then a lot of arithmetic ran. Turing (1950) took on this worry as Lady Lovelace's objection, that the Analytical Engine "can do whatever we know how to order it to perform". To the variant that a machine can never surprise us, he replied "Machines take me by surprise with great frequency", and he argued that thinking otherwise assumes every consequence of a fact arrives in the mind together with the fact. I could not have predicted the corner opening by reading the Bellman equation, or the centre opening by reading the Q-learning update. Specifying a process is not the same as listing its results, and algorithms have worked that way since long before anyone fitted one to data.

What this means for teaching

If the split between a procedure and the state it reads is old, the fix belongs inside the algorithms unit that already exists. Denning (2003) wrote that the great principles of computing have been "interred beneath layers of technology in our understanding and our teaching", and he turned down the picture of a pantheon with one pillar per principle. An extra pillar for learned computation would be that picture. I would make three changes.

Teach the table as the artefact

The way I was taught it, dynamic programming is a recurrence and the assessment is the recurrence. The table is scaffolding, printed once for a small example and then thrown away. But the play comes from the table. A student who has filled a memo table and is then asked what that table is after the run, whether it is data or program, and whether it would still work if the opponent changed, has met the whole question on ground where they can check the answer.

Teach the level question directly

Ask where the algorithm is for a short list of cases and require the level to be named in the answer. The trained digit classifier is the case worth the time. The same convolution code with a different weight file could sort small photos of clothes, so at the executor level the code is the whole algorithm and the weights are its argument. Anyone who uses it still calls it a digit recogniser. Students should be able to give both answers without finding either evasive, and to spot the slide between them in a paper or an argument.

Teach correctness of the state as well as of the steps

This is the one I would fight for. A loop invariant proves the steps. It does not tell you whether the table those steps produced is right in the places nobody looked. My learner's policy is optimal in 0.9059 of the 2423 positions overall, and in 108 of the 109 positions it meets against a random opponent. The update rule says where errors are likely, in rarely met states and near-ties, but it cannot say which moves are wrong. For that I had to score the learner against a solved reference. The one wrong state it meets in play is the empty board, where the corner beats the centre by 1/192 against a random opponent. That gap is small next to the 0.3423 mean error in its values.

So alongside the classical tools, students need generalisation treated as a correctness notion, PAC-style guarantees and what they assume (Valiant, 1984), and the habit of holding out a reference and measuring where the two disagree. This is my version of the point Tedre, Denning and Toivonen (2021) make about correctness.

A two-hour lab

The three changes fit in one lab, written for students who have met dynamic programming but not reinforcement learning. The teacher hands out the notebook code for both players and the worst-case solver, with its tie rules and seeds, so the good answers are what that code prints. Students work in pairs. By the end of the lab a student should be able to do three things.

• LO1. Name the level (executor, deployed or system) whenever they say where the algorithm is in a system, and say what the word picks out at that level.
• LO2. Apply the three-part test to a piece of run-time state and justify whether it belongs to the deployed algorithm.
• LO3. Check a learned table against a solved reference, and explain what reasoning about the update rule alone can and cannot tell you about where the two disagree.

1. Before, 0 to 10 minutes. Each student writes a definition of "algorithm" in their own words and hands it in.
2. Solve, 10 to 30 minutes. After a short briefing on Markov decision processes and the Q update, students run value iteration and read the policy off the table. A good answer has 9 sweeps, an empty-board value of 191/192 and a corner opening, and notes that all four corners are worth the same.
3. Learn, 30 to 55 minutes. Train the learner on several seeds at 100,000 episodes each and pool the opening cells. A good answer notices that the openings can differ while the update rule never changed. If a class gets the same opening every time, the main run's checkpoints still show it moving, with a corner opening at 21 of the 100.
4. Swap the tie rule, 55 to 70 minutes. Read two policies off the worst-case solver's table and score both. A good answer has 0.994792 and 0.848958, and says that no value in the table moved.
5. Score, 70 to 90 minutes. Compare the main run's greedy moves with the solved player's optimal ones in every decision state, then only in the states met against the random opponent. A good answer finds the second rate much higher than the first (mine were 0.9059 and 108 of 109) and says the update rule can point at rarely met states and near-ties but cannot say which moves are wrong.
6. Six cases, 90 to 105 minutes. In groups, fill in the answer key below from its first column only, then find the level slide in a short paragraph the teacher hands out.
7. After, 105 to 120 minutes. Each student writes the definition again, without seeing the first one.

The paragraph for step 6 can be short. This is the one I wrote to slide on purpose.

The network reads its weights on every input and they stay fixed once the model ships, so the weights are part of the algorithm. But the weights are only numbers the inference code reads, so every model trained this way runs the same algorithm.

The first sentence works at the deployed level and the second at the executor level, and nothing in the text marks the change. A good answer finds the word changing level between the two sentences and says both can be true once the level is named.

LO1 goes after a gap in a workshop study by Bellettini and colleagues (2024). Over nine workshops they coded definitions of "algorithm" written by 27 groups of students and teachers. Most asked for unambiguous steps, but only three of the 27 mentioned an interpreter or executor, and the authors say getting the interpreter named was often the turning point. Mirolo, Izu, Lonati and Scapin (2021) report the advice that students "should be made aware of any change of abstraction level", and LO1 is one way to do that.

How the lab could be evaluated

I have not run this lab and I have not studied any learners. What follows is a plan, and running it would need ethics approval and consent from each student first.

• Primary measure. After the lab each student works alone on four new items: a route planner's map, a chat deployment where they sort the system prompt from the user's messages, a new paragraph that slides between levels, and a handful of learned values set next to the solved ones. The same items come back a week later to separate learning from recall.
• Secondary measure. Code the before and after definitions with the scheme Bellettini and colleagues used, count how many name an executor, and place each one on Perrenet's levels. Perrenet and colleagues report a Cohen's kappa of .64 for their level coding, after dropping four items, so I expect that coding to be the hard part.
• Analysis. Within a class, compare the before and after definitions with McNemar's test. Between classes, compare the lab class with a class that does a dynamic programming lab that never asks the level question.

The plan says in advance what would count against the lab. If the lab class does no better than the comparison class on the new items, or loses the gain a week later, the lab did not do its main job. If students name a level on the six cases and then miss the slide in the paragraph, they have learned the level words as labels and are not using them.

Limits

• My evidence is one game with 5478 states, two solvers and one learner, all tabular. A Q table is a much friendlier object than a weight vector. I can diff it against an exact answer, which is the only reason I can quote 0.9059 at all. The analogy to large models is about shape, an executor plus persistent control state, and I am not claiming a network is as legible as a Q table.
• Provenance changes how you audit a table even when it changes nothing about how the table runs. My value table can be checked against the recurrence that produced it. Nothing that produced my Q table gives me a check like that, so I scored it against a solved reference instead.
• For a network the executor is less generic than an interpreter, because the forward pass fixes an architecture. My line is cleanest for tables and blurrier for networks. The next case to build is a digit classifier with one executor and two weight files.
• I wrote the definitions, the test and the cases myself, so the cases may fit the test partly because I chose them.
• The numbers come from one main run with one pair of seeds. The five other seeds ran a shorter setup with only summaries saved, so I cannot say how much the 200,000-episode player varies from seed to seed.
• This is a paper about teaching with no data about learners. I have not run the lab with a class, and I do not know whether the level distinction is teachable in an undergraduate unit or just sounds like hair-splitting to someone who has not yet been surprised by a table.

Two things would change my mind. One is a criterion for membership that turns on how the state was produced and still survives the bit-identical case. The other is a demonstration that every question we ask about a trained model can be answered at the executor level, with the weights treated as input. That would collapse my position into the objection. I do not think it can be done, because naming which program a process is running is not optional, but I have not proved it.

The answers in one table

Two tables, one game, both written by a machine. The classical one has been in the syllabus the whole time, and I was taught around it.

Papers this builds on

• Knuth (1997), the five features of an algorithm. Turing (1936), the analysis of what a person following a fixed procedure can compute.
• Blass and Gurevich (2003), Gurevich (2012) and Moschovakis (2001), on whether algorithm can be defined.
• Wegner (1997) and Cockshott and Michaelson (2007), on interaction and computational power.
• Turing (1950), learning machines and Lady Lovelace's objection.
• Perrenet, Groote and Kaasenbrood (2005), levels of abstraction in the concept of algorithm. Marr and Poggio (1976), levels of description. Mirolo, Izu, Lonati and Scapin (2021), abstraction in computing education.
• Bellettini and colleagues (2024), the notion of algorithm according to students and teachers. Lonati and colleagues (2022), what we talk about when we talk about programs.
• Sorva (2012) and Fincher et al. (2020), notional machines. Tedre, Denning and Toivonen (2021), CT 2.0.
• Watkins and Dayan (1992), Q-learning. Silver et al. (2017), AlphaGo Zero. Valiant (1984), a theory of the learnable.
• Karpathy (2017), Software 2.0. Breiman (2001), the two cultures. Denning (2003), great principles of computing.
• Williams and Perugini (2016), the Futamura projections. Cook and Lämmel (2011), online partial evaluation.

Read the full paper (PDF). It has the method and its five conditions, the full lab and evaluation plan, and every reference.