Look at the State, Make a Move

Look at the State, Make a Move

INFO 6205 — Algorithms · Nik Bear Brown · Northeastern University

A Rubik's Cube is a tiny model of what an algorithm is: look at the state, pick a move by a rule, make the move, look again — until solved. That is how a speedcuber works: recognise the pattern, apply the memorised sequence, recognise, apply. Liam, in for Bear, draws one cube twice — the cube itself on the left, its state graph on the right — so every turn on the cube is visibly one step along an edge of the graph. Then the loop is written as three lines of code, the 43-quintillion-node graph and God's number 20 get their receipts, and a viral post's claim that "this is exactly how AI thinks" gets the Teardown: a chess engine and a navigation app do search a graph, and the cube's rule is deterministic — same state, same move, same next state — but a language model samples its next token from a probability distribution. A metaphor, not a mechanism.

Chapters 0:00 Cold open — Liam, in for Bear 0:16 Not how AI thinks — what an algorithm is 0:30 Four terms: state, move, state graph, rule 0:47 One cube, drawn twice 1:04 One move is one edge 1:21 Twist until it looks right — the random walk 1:36 The recipe — how a speedcuber solves 1:56 The loop, in three lines of code 2:12 Commit: how many nodes? 2:20 Forty-three quintillion states, twenty turns 2:43 Deterministic, not probabilistic — the post's claim 3:04 Verdict 3:26 Your turn 4:07 Outro

Your turn — paste this into Claude: I just watched a film that treats an algorithm as a loop: look at the state, pick a move by a rule, make the move, look again, the way a speedcuber solves a Rubik's Cube. Take the 15-puzzle, the 4-by-4 sliding-tile puzzle with one blank. (1) Write that loop in pseudocode for the 15-puzzle: what is the state, what counts as one move, and what is the rule? (2) Mark which line is "recognise" and which line is "apply". (3) Explain what a deterministic rule means here: same state, same move, every time. (4) Then say honestly whether you, a language model, followed a rule like that to write this answer, or sampled it.

Receipts

• 43,252,003,274,489,856,000 reachable states: 8! × 3^7 × 12! × 2^10.
• God's number is 20 in the half-turn metric: Rokicki, Kociemba, Davidson and Dethridge, July 2010 (cube20.org) — about 35 CPU-years, donated by Google, over a coset partition of the state space, not a brute-force walk of every node.
• CFOP: cross, first two layers, orient last layer (57 cases), permute last layer (21 cases) — recognise a case, apply its sequence.

Every factual claim in this video was checked against primary sources before rendering.

Course: INFO 6205 — Program Structure and Algorithms, Northeastern University. Textbook: INFO 6205 Algorithms and Data Structures (Brown & Magre), github.com/nikbearbrown/Coursera_INFO_6205_Algorithms

youtube.com/@NikBearBrown

▶ The full series playlist — Brutalist https://www.youtube.com/playlist?list=PLG9H-C6rp5RU

What this video covers

• 0:00 — Cold open — Liam, in for Bear
• 0:16 — Not how AI thinks — what an algorithm is
• 0:30 — Four terms: state, move, state graph, rule
• 0:47 — One cube, drawn twice
• 1:04 — One move is one edge
• 1:21 — Twist until it looks right — the random walk
• 1:36 — The recipe — how a speedcuber solves
• 1:56 — The loop, in three lines of code
• 2:12 — Commit: how many nodes?
• 2:20 — Forty-three quintillion states, twenty turns
• 2:43 — Deterministic, not probabilistic — the post's claim
• 3:04 — Verdict
• 3:26 — Your turn
• 4:07 — Outro

Transcript

A lightly formatted transcript of the video, with timestamps so you can jump to any section on YouTube.

Cold open — Liam, in for Bear

[0:00] Marhaba, this is Liam in for Bear with info 6205 algorithms at Northeastern. A post going round says solving a Rubik's Cube is exactly how AI thinks. Half of that is right and the right half is worth a whole film. Look at the state, make a move, look again. That is what an algorithm is.

Not how AI thinks — what an algorithm is

[0:16] Solving a Rubik's Cube is a tiny model of what an algorithm is, not of how AI thinks. We will get to that. An algorithm is a loop. Look at the state, pick the next move by a rule, make it, look again. A speedcuber does exactly this faster than you can follow.

Four terms: state, move, state graph, rule

[0:30] Four terms, a state, one full arrangement of the cube's 54 stickers, a move, one turn of one face. It takes a state to a neighboring state. The state graph, every state a node, every move an edge between two of them. And a rule, what you do when you see a given state. A speedcuber's rules are memorized sequences.

One cube, drawn twice

[0:47] Here is a scrambled cube drawn twice. On the left, the cube itself, three faces you can see, nine stickers each. On the right, the state graph, every dot is one arrangement of the stickers. Every line is one turn that takes you between two of them. The terracotta dot is where this cube is right now. The center is solved. Turn the top face a quarter

One move is one edge

[1:06] Turn. On the left, the stickers move. The top nine rotate and the top rows of the side faces slide round. On the right, the dot steps along one edge to a neighboring node. Turn the right face another step. Every move on the cube is one step on the graph. That linkage is the whole film.

Twist until it looks right — the random walk

[1:21] Most people's method, twist until it looks right. Watch it on the graph, eight turns chosen by feel. The dot wanders ring to ring and the counter climbs. Nothing steers it toward the center. The moves are legal, the loop is real, but there is no rule. Twisting is not an algorithm.

The recipe — how a speedcuber solves

[1:36] Back to the scramble, a speedcuber does not twist. She recognizes the pattern in front of her, applies the sequence she memorized for it, and looks again. Her method has four stages, cross, first two layers, orient the last layer, permute it. Each stage is the same move, recognize one of a fixed set of patterns, apply its sequence. The rule steers every step toward the center.

The loop, in three lines of code

[1:56] Write the recipe as code and it is three lines. While not solved, look at the state, choose the move by the rule, apply it, then round again. Watch the dot run the lines while the cube runs the moves. Look, choose, apply, look, choose, apply. When the state is solved, the condition fails and the loop ends. That is an algorithm.

Commit: how many nodes?

[2:12] Before the number, how many nodes does this graph have? How many arrangements can legal turns reach? A million? A billion? More? Commit to a number.

Forty-three quintillion states, twenty turns

[2:21] 43 quintillion, written out 20 digits. In 2010, Rokicki, Kociemba, Davidson, and Demaine showed that every one of them is at most 20 face turns from solved. God's number, found by exhaustive search, about 35 CPU years donated by Google. A human recipe is not that path. A beginner's method takes about 100 turns, a speed cuber's 50 to 60. Search finds the shortest path, the recipe finds a path.

Deterministic, not probabilistic — the post's claim

[2:43] Now the posts claim, write a chess engine searches a tree of moves, a navigation app searches a graph of roads, and the cube is a graph search, deterministic. Same state, same move, same next state every time, over each a language which model does not search a state graph. It takes the text so far and samples the next token from a probability distribution. Same input, different output, metaphor, not mechanism. Let's recap with Claude. An

Verdict

[3:06] Algorithm is a loop. Look at the state, pick a move by a rule, make it, look again. Every move on the cube is one edge on the state graph, and a recipe is a policy that walks it inward. 43 quintillion states, all within 20 face turns of solved. That is exhaustive search. A recipe takes 50 to 100, and the cube is deterministic, where a language model samples. AI does the same thing is a metaphor, not a mechanism.

Your turn

[3:27] Your turn. Paste this into Claude. I just watched a film that treats an algorithm as a loop. Look at the state, pick a move by a rule, make the move, look again, the way a speed cuber solves a Rubik's Cube. Take the 15 puzzle, the 4 by 4 sliding tile puzzle with one blank. One, write that loop in pseudo code for the 15 puzzle. What is the state? What counts as one move? And what is the rule? Two, mark which line is recognize and which line is apply. Three, explain what a deterministic rule means here. Same state, same move every time. Four, then say honestly whether you, a language model, followed a rule like that to write this answer or sampled it. Two things to look for. Does its state include the whole board and does its rule change only one tile per move? And on the last question, does it admit that it sampled? Look at the

Outro

[4:07] State, make a move at Nick Bear Brown.