Winning & Losing States in Games
Reason about who wins with optimal play.
Winning & Losing States in Games is a free Coding Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Two Players, Perfect Play
In a combinatorial game, two players alternate moves, both play perfectly, and the one who cannot move loses. Your job is just to predict the winner. 🎯
Every Position Has a Label
Each game position is a state. Your whole task is to label every state as either a win or a loss for the player about to move.
What a Winning State Means
A state is a winning state if the player to move has at least one move leading to a losing state for the opponent.
What a Losing State Means
A state is a losing state when every single move you make hands the opponent a winning state. You are stuck no matter what.
The Base Case
The position where you cannot move at all is the base case. The player facing it has already lost, so label it a loss.
Build Up from the Bottom
Start from base cases and work outward. Each new state's label depends only on the states its moves lead to.
One Good Move Is Enough
To win, you only need one move into a losing state for the opponent. Finding any single escape route is enough.
A Tiny Example
Take 1 or 2 stones from a pile, last to take wins. With 0 stones the mover loses, so it is a losing state.
Code the Win Check
This recursion labels a state by trying every move and recursing on the result. ⚙️
def win(n):
if n == 0:
return False
return any(not win(n - k) for k in (1, 2))Memoize to Stay Fast
States repeat across branches, so cache each result. A simple memo turns exponential work into linear time.
from functools import lru_cache
@lru_cache(None)
def win(n):
return n != 0 and any(not win(n - k) for k in (1, 2))Symmetry Is a Shortcut
If a position is perfectly symmetric, the second player can often mirror moves and win. Watch for that mirroring trick.
Quick Check
You face a state. When is it a losing state for you?
Recap
You now label states: a win has one move to an opponent loss, a loss has none. Build from base cases and memoize. 🧠
Frequently asked questions
Is the “Winning & Losing States in Games” lesson free?
Yes — the full text of “Winning & Losing States in Games” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Winning & Losing States in Games”?
Reason about who wins with optimal play. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Winning & Losing States in Games” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Winning & Losing States in Games
- Nim and the Grundy Number
- Meet in the Middle
- Debug Fast: Stress Tests & Triage