Game Theory Coding Problems: 12 Questions with Solutions
12 game theory coding problems — 3 easy · 6 medium · 3 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 7-day plan.
- Problems: 12
- By difficulty: 3 easy · 6 medium · 3 hard
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
- Cost: Free on every plan; sign in to run and submit
Two players alternate moves and both play perfectly: who wins? The answer is usually a pattern in the small cases (a position is losing when every move leads to a winning one) or a parity argument. These problems practise finding that pattern by hand before writing code, and recognising when a dynamic-programming table over positions is needed instead.
How game theory works, step by step
take 1, 2 or 3 stones; last stone wins; n = 0..12- Take 1, 2 or 3 stones; whoever takes the last stone wins. With 0 stones the player to move has already lost, so 0 is a losing position (L). Work upwards: a position is winning (W) if some move leaves an L, and losing if every move leaves a W.
- From 1 the only move leaves 0, which is L for the opponent, so 1 is W: take the last stone.
- From 2 you can leave 1 or 0. Leaving 0 hands the opponent a losing position, so taking 2 stones wins: 2 is W.
- From 3 you can leave 2, 1 or 0. Leaving 0 hands the opponent a losing position, so taking 3 stones wins: 3 is W.
- From 4 every move — leaving 3, 2 or 1 — hands the opponent a winning position, so 4 is L. Whoever faces 4 stones loses against best play.
- From 5 you can leave 4, 3 or 2. Leaving 4 hands the opponent a losing position, so taking 1 stone wins: 5 is W.
- From 6 you can leave 5, 4 or 3. Leaving 4 hands the opponent a losing position, so taking 2 stones wins: 6 is W.
- From 7 you can leave 6, 5 or 4. Leaving 4 hands the opponent a losing position, so taking 3 stones wins: 7 is W.
- From 8 every move — leaving 7, 6 or 5 — hands the opponent a winning position, so 8 is L. The losing positions so far, 0, 4 and 8, are 4 apart.
- The same check runs on: 9, 10 and 11 can each leave 8, an L, so they are W; 12 can only leave W positions, so it is L.
- The L positions are 0, 4, 8 and 12, the multiples of 4: from a multiple of 4, any take of 1 to 3 leaves a non-multiple, and the opponent takes 4 minus that to restore one. The table costs O(n) with 3 moves per position; the pattern answers in O(1): the first player wins exactly when n % 4 ≠ 0.
Game Theory study plan
All 12 Game Theory problems (3 easy, 6 medium and 3 hard) over 7 days, about 7 h 15 min in all — the pattern first, then easiest to hardest. Then move on to Geometry.
Day 1
Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.
- Nim Game Easy
- Divisor Game Easy
- Find the Winning Player in Coin Game Easy
Day 2
Medium problems: the same pattern with one twist each. Name the twist before you code.
- Predict the Winner Medium
- Stone Game Medium
Day 3
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Maximum Number of Coins You Can Get Medium
- Stone Game IX Medium
Day 4
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Stone Game II Medium
- Stone Game VII Medium
Day 5
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
- Stone Game III Hard
Day 6
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
- Stone Game IV Hard
Day 7
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
- Stone Game VIII Hard
Game Theory: the essentials
When to reach for it
"Both players play optimally", "Alice moves first", "return true if the first player wins", "the most the first player can score". Two families recur: win-or-lose games over a position (take one to three stones, replace n by n − x for a divisor x), and score games where players take from the ends of a row or the front of a pile.
The pattern
For win-or-lose games, compute win[p] for small positions bottom-up; the table often exposes a rule that replaces it — in Nim with moves of one to three stones, a multiple of 4 loses. For score games, track one difference instead of two scores: best(i, j) is the most the player to move can finish ahead on nums[i..j], and each choice subtracts the opponent's best on what remains.
from functools import lru_cache
def first_player_wins(nums): # Predict the Winner: a tie wins
@lru_cache(None)
def best(i, j): # mover's lead over nums[i..j]
if i > j:
return 0
return max(nums[i] - best(i + 1, j), nums[j] - best(i, j - 1))
return best(0, len(nums) - 1) >= 0Cost
Positions × moves per position: O(n²) for the interval games above and O(n × moves) for single-pile games. A rule, once proved, is O(1).
Common mistakes
- Playing both sides greedily: taking the larger end every turn is not optimal play.
- Keeping both scores in the state instead of their difference, which multiplies the number of states.
- Misreading ties: check whether a draw counts as a win for the first player.
- Trusting a pattern spotted in three or four small cases without checking more, or proving it.
Start with
- Nim Game: a table that collapses to one rule.
- Divisor Game: parity decides it.
- Predict the Winner: a score difference over an interval.
All game theory problems
Easy (3)
- Find the Winning Player in Coin Game Math
- Nim Game Math, Brainteaser
- Divisor Game Math, Dynamic Programming, Brainteaser
Medium (6)
- Stone Game VII Array, Math, Dynamic Programming
- Stone Game II Array, Dynamic Programming, Prefix Sum
- Predict the Winner Array, Dynamic Programming, Recursion
- Stone Game IX Array, Math, Greedy
- Maximum Number of Coins You Can Get Array, Math, Greedy
- Stone Game Array, Math, Dynamic Programming
Hard (3)
- Stone Game VIII Array, Math, Dynamic Programming
- Stone Game IV Math, Dynamic Programming
- Stone Game III Array, Dynamic Programming
Companies that ask game theory problems
Next topic: Geometry