AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started

Topic

Game Theory coding problems

Two players alternate moves and both play perfectly: who wins?

19 problems · 3 easy · 11 medium · 5 hard · judged by hidden tests in 13 languages

19problems

3 easy

11 medium

5 hard

Sign in to tick off what you solve.

Study plan: 13 problems · about 7 h 50 min

Start the study plan

Next up: Nim Game

How it works

Game Theory, step by step

Who wins the take-1-to-3 stone game, with winning and losing positions

take 1, 2 or 3 stones; last stone wins; n = 0..12

stones0123456789101112L0: no move left, L

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.

0:01 / 0:35Step 1 of 11
Transcript · 11 steps

Study plan

Learn game theory in 8 days

13 of the 19 Game Theory problems (3 easy, 7 medium and 3 hard) over 8 days, about 7 h 50 min in all — the pattern first, then easiest to hardest. After that, the other 6 in the full list below are practice at your own pace. Then move on to Geometry.

  1. Day 1

    about 1 h 15 min

    Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

  2. Day 2

    about 1 h 10 min

    Medium problems: the same pattern with one twist each. Name the twist before you code.

  3. Day 3

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  4. Day 4

    about 1 h 10 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  5. Day 5

    about 35 min

    More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

  6. Day 6

    about 50 min

    Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

  7. Day 7

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

  8. Day 8

    about 50 min

    Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

    Next topic: Geometry

Game Theory Coding Problems: 19 Questions with Solutions

19 game theory coding problems — 3 easy · 11 medium · 5 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.

  • Problems: 19
  • By difficulty: 3 easy · 11 medium · 5 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

stones0123456789101112LWWWLWWWLWWWLL = {0, 4, 8, 12}: n % 4 == 0first player wins when n % 4 != 0
Who wins the take-1-to-3 stone game, with winning and losing positions. Example: take 1, 2 or 3 stones; last stone wins; n = 0..12
  1. 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.
  2. From 1 the only move leaves 0, which is L for the opponent, so 1 is W: take the last stone.
  3. From 2 you can leave 1 or 0. Leaving 0 hands the opponent a losing position, so taking 2 stones wins: 2 is W.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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

13 of the 19 Game Theory problems (3 easy, 7 medium and 3 hard) over 8 days, about 7 h 50 min in all — the pattern first, then easiest to hardest. After that, the other 6 in the full list below are practice at your own pace. Then move on to Geometry.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 5

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 6

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Day 7

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Day 8

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Next topic: Geometry

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) >= 0

Cost

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

All game theory problems

Easy (3)

Medium (11)

Hard (5)

Companies that ask game theory problems

Next topic: Geometry