Skip to content

141 — Game Theory Basics

Game theory trilogy-র প্রথম ধাপ — পরের দুটো (142 Nim, 143 Grundy) এরই উপর দাঁড়াবে, তাই লাফিয়ো না। এখানে শিখব দুই player-এর পালা-খেলায় প্রতিটা অবস্থানকে "জিতবে (W)" না "হারবে (L)" — সেই ট্যাগ পেছন থেকে কীভাবে ভরতে হয়। মনে রাখো, এই level CP-leaning, interview-এর জন্য optional (repo-র plan অনুযায়ী)।

Source

  • Original source: CP-Algorithms — Sprague-Grundy theorem & Nim (game theory basics)
  • Platform: CP-Algorithms — https://cp-algorithms.com/game_theory/sprague-grundy-nim.html
  • Topic: Math-based programming fundamentals → Level 11: Hard Mixed CP Patterns
  • Difficulty: Medium
  • Pattern: W/L labeling (backward DP over game states)
  • Basic idea inherited from: — (game theory-র শিকড়; নতুন শাখা)

1. Problem in simple words

দুই player পালা করে চাল দেয়। একটা সাধারণ game ধরি: একটা স্তূপে nটা পাথর; প্রতি চালে যে কেউ 1, 2 বা 3টা পাথর নিতে পারে। যে আর চাল দিতে পারে না (অর্থাৎ পাথর শেষ, n = 0-তে তার পালা) সে হারে (এটাকে বলে normal play)।

দুজনেই নিখুঁত খেলে। জিজ্ঞেস: শুরুতে n পাথর থাকলে প্রথম player জিতবে কি?

এর উত্তর শুধু "হ্যাঁ/না" নয় — আমরা প্রতিটা n-এর জন্য ট্যাগ বসাব: W (এখান থেকে যার চাল সে জেতে) বা L (এখান থেকে যার চাল সে হারে)। এই W/L-চিন্তাই game theory-র ভিত্তি।

এটা CP-leaning level। Interview-পথে থাকলে এড়িয়ে মূল DS topic-এ যেতে পারো; পরে ফিরে এলে এই recursive W/L-চিন্তা ভালো লাগবে।

2. What is the math idea?

মূল ধারণা backward induction — শেষ অবস্থা থেকে পেছনে হেঁটে প্রতিটা position-এ W/L ঠিক করা। দুটো নিয়ম সব impartial game-এ একই:

  • একটা position L (losing): তার সব চাল গিয়ে পড়ে W position-এ (যেদিকেই যাও, opponent জেতে)।
  • একটা position W (winning): অন্তত একটা চাল আছে যা গিয়ে পড়ে L position-এ (opponent-কে ফাঁদে ফেলা যায়)।

ভিত্তি (base): যে position থেকে কোনো চাল-ই নেই (n = 0) — সেখানে যার পালা সে হেরে গেছে, তাই সেটা L।

3. Which basic idea does this inherit from?

এটা game theory-র একদম শিকড় (তাই inherited from: —)। তবে কৌশলটা চেনা: এটা আসলে একটা DP over states, পেছন থেকে ভরা। ছোট n থেকে বড় n-এর দিকে table ভরি, প্রতিটা cell-এর মান আগের cell-গুলোর উপর নির্ভর করে — ঠিক যেমন Fibonacci বা coin-change DP।

নতুন যেটা শিখছি: cell-এ সংখ্যা না রেখে W/L রাখা, আর transition-এ "any/all" যুক্তি (W ⟺ অন্তত একটা চাল L-এ যায়)। এই W/L table-ই পরের দুটো problem-এর (Nim, Grundy) ভিত্তি — 142-এ এই table থেকে XOR pattern বেরোবে, 143-এ W/L-এর জায়গায় আসবে Grundy সংখ্যা।

4. Real-life analogy

ভাবো একটা সিঁড়ি খেলা: তুমি আর বন্ধু পালা করে কিছু ধাপ নিচে নামো। যে নিচে পৌঁছাতে পারে (বা যে আটকে যায়) — তার ভাগ্য খেলার নিয়মে ঠিক।

কে জিতবে বুঝতে তুমি শেষ থেকে ভাবো: "যদি আমি একদম শেষ ধাপে আটকে থাকি, আমি হারলাম (L)।" তারপর এক ধাপ পেছনে: "এখান থেকে কি এমন একটা চাল আছে যা বন্ধুকে ওই হারা-অবস্থায় ফেলবে? থাকলে আমি জিতি (W)।" এভাবে পেছন থেকে প্রতিটা ধাপে "আমি এখানে থাকলে জিতি না হারি" লিখে ফেলো — শুরুর ধাপে পৌঁছালেই উত্তর।

মূল কথা: locally ভালো চাল মানেই জেতা নয় — জেতা মানে opponent-কে হারা-অবস্থায় ঠেলে দেওয়া।

5. Visual explanation

পেছন থেকে W/L ভরা (n পাথর, নেওয়া যায় 1/2/3):

n:    0   1   2   3   4   5   6   7   8
      L   W   W   W   L   W   W   W   L
      ^                   ^               ^
   base (চাল নেই)      4-এর গুণিতকে L

কীভাবে ভরলাম (তীর = কোন চালে কোথায় যায়):
  n=0 : চাল নেই            -> L  (base)
  n=1 : 1 নিলে -> 0 (L)    -> W  (অন্তত একটা L-এ যায়)
  n=2 : 1->1(W) 2->0(L)    -> W
  n=3 : 1->2(W) 2->1(W) 3->0(L) -> W
  n=4 : 1->3(W) 2->2(W) 3->1(W) -> সব W  -> L !
  n=5 : 1->4(L) ...        -> W  (4=L এ ফেলতে পারি)

pattern ফুটে উঠল:  n % 4 == 0  <=>  L

লক্ষ করো — n = 4-এ সব চাল W-তে যায়, তাই L; আর 4-এর প্রতিটা গুণিতকে এটাই ঘটে।

6. Example input and output

n    প্রথম player   কারণ
--------------------------------------------------
0    হারে (L)       চাল-ই নেই
1    জেতে (W)       1 নিয়ে 0 (L) এ ফেলে
3    জেতে (W)       3 নিয়ে 0 (L) এ ফেলে
4    হারে (L)       যা-ই নাও (1/2/3), opponent বাকিটা শেষ করে
8    হারে (L)       4-এর গুণিতক
7    জেতে (W)       3 নিয়ে 4 (L) এ ফেলে

মূল edge case: n = 0 হলো base — সেখানে যার পালা সে হেরে গেছে (L)। আর pattern: n % 4 == 0 মানেই L, বাকি সব W।

7. Brute force thinking

সবচেয়ে সোজা ভাবনা: recursion দিয়ে সরাসরি "এই position থেকে কি জেতা যায়?" জিজ্ঞেস করা। একটা position W যদি কোনো চালে opponent-কে L-এ ফেলা যায়:

def win_brute(n, moves=(1, 2, 3)):
    if n == 0:
        return False                       # চাল নেই -> হার (L)
    for m in moves:
        if n >= m and not win_brute(n - m, moves):
            return True                    # opponent-কে L-এ ফেললাম -> W
    return False                           # সব চাল W-তে যায় -> L

এটা definition-এর হুবহু অনুবাদ — ঠিক উত্তর দেয়। win_brute(4) → False (L), win_brute(5) → True (W)।

8. Why brute force may be slow

সমস্যা — memoization ছাড়া এই recursion একই position বারবার গোনে। win(n) ডাকে win(n-1), win(n-2), win(n-3), যাদের প্রত্যেকে আবার নিচের গুলো — গাছটা exponentially ছড়ায় (Fibonacci-র মতো)।

n = 40 (memo ছাড়া) -> প্রায় 3^40 / ... টা call — অসম্ভব ধীর

memo / DP দিয়ে      -> প্রতিটা n একবার, O(n · |moves|) — দ্রুত

মূল শিক্ষা: game state গুলো একে অপরের সাথে overlap করে, তাই প্রতিটা একবার গোনাই যথেষ্ট — DP।

9. Better thinking

মূল insight: position গুলো সীমিত (0 থেকে n), তাই পেছন থেকে একটা table-এ প্রতিটার W/L একবার করে ভরে ফেলো। win[0] = False (base) থেকে শুরু করে বড় n-এর দিকে:

win[k] = True  যদি  কোনো move m-এ  win[k - m] == False  (opponent L-এ)
       = False অন্যথায়

এটা O(n · |moves|) — দ্রুত আর নির্ভুল। আর table ভরার পর একটা bonus: pattern চোখে পড়ে (n % 4 == 0 → L), যা থেকে O(1) সূত্রও বেরোয়।

10. Thinking tweak

এক লাইনের "আহা": "আমি কি জিতব?" প্রশ্নটা উল্টে দাও — "এমন কি একটা চাল আছে যা opponent-কে হারা-অবস্থায় ফেলে?" থাকলে W, না থাকলে L।

আর সবচেয়ে শক্তিশালী tweak: ছোট case-এ W/L table হাতে ভরো → pattern খোঁজো → প্রমাণ করো → O(1) সূত্র। পেছন-থেকে-label শুধু উত্তর দেয় না, pattern আবিষ্কার করিয়ে দেয় (এই game-এ n % 4 == 0 → L)। ফাঁদ: "greedy চাল = জেতা" ভাবা ভুল (concept-notes mistake #3) — locally বেশি পাথর নেওয়া মানেই জেতা নয়।

11. Step-by-step dry run

n = 5 পর্যন্ত table ভরি (moves = 1, 2, 3):

  1. win[0] = False — base, চাল নেই → L।
  2. win[1]: চাল 1 → win[0] = False (L)। অন্তত একটা L পেলাম → W।
  3. win[2]: 1→win[1]=W, 2→win[0]=L। L পেলাম → W।
  4. win[3]: 1→win[2]=W, 2→win[1]=W, 3→win[0]=L। L পেলাম → W।
  5. win[4]: 1→win[3]=W, 2→win[2]=W, 3→win[1]=W। সব W, কোনো L নেই → L!
  6. win[5]: 1→win[4]=L। L পেলাম → W।

ফল: [L, W, W, W, L, W]। n=4-এ L — pattern n % 4 == 0 শুরু।

12. Python solution

def label_win_lose(N, moves=(1, 2, 3)):
    """0..N প্রতিটা position-এ W (True) / L (False) ট্যাগ ফেরত দেয়।"""
    win = [False] * (N + 1)                 # win[0] = False: চাল নেই, হার (L)
    for n in range(1, N + 1):
        # কোনো move m কি opponent-কে L position-এ ফেলে?
        win[n] = any(n >= m and not win[n - m] for m in moves)
    return win


def first_player_wins(n, moves=(1, 2, 3)):
    """একটা n-এ প্রথম player জেতে কি না।"""
    return label_win_lose(n, moves)[n]


def win_brute(n, moves=(1, 2, 3)):
    """memo-হীন সরল recursion — মিলিয়ে দেখার জন্য।"""
    if n == 0:
        return False
    return any(n >= m and not win_brute(n - m, moves) for m in moves)


# --- ছোট test গুলো (সব pass করা উচিত) ---
labels = label_win_lose(12)
# n % 4 == 0 হলে L (False), নাহলে W (True)
for n in range(13):
    assert labels[n] == (n % 4 != 0), n

# brute force-এর সাথে মিল (definition নিজেই ঠিক কিনা)
for n in range(15):
    assert first_player_wins(n) == win_brute(n), n

# অন্য move set: শুধু {1, 2} -> pattern n % 3 == 0 -> L
lab2 = label_win_lose(12, moves=(1, 2))
for n in range(13):
    assert lab2[n] == (n % 3 != 0), n

print([("L", "W")[w] for w in labels])   # ['L','W','W','W','L',...]
print(first_player_wins(4))               # False (L)
print(first_player_wins(7))               # True (W)
print("সব test pass!")

13. Line-by-line explanation

    win = [False] * (N + 1)

win[n] রাখবে position n-এ যার পালা সে জেতে কিনা। শুরুতে সব False; বিশেষভাবে win[0] = False — base case, চাল নেই মানে হার (L)।

        win[n] = any(n >= m and not win[n - m] for m in moves)

এটাই হৃদয়। প্রতিটা সম্ভাব্য চাল m-এর জন্য দেখি: m নেওয়া গেলে (n >= m) opponent পড়ে win[n - m] position-এ; সেটা যদি L (not win[n-m]) হয়, তবে আমি জিতি। any(...) মানে "অন্তত একটা এমন চাল আছে?" — থাকলেই W।

def first_player_wins(n, moves=(1, 2, 3)):
    return label_win_lose(n, moves)[n]

পুরো table ভরে শুধু n-এর ঘরটা ফেরত — একটা নির্দিষ্ট প্রশ্নের সরাসরি উত্তর।

বাকি win_brute definition-এর সরল recursion, আর assert গুলো তিনভাবে যাচাই করছে: (১) n % 4 pattern, (২) brute force-এর সাথে মিল, (৩) ভিন্ন move set-এ n % 3 pattern। সব মিললে শেষে সব test pass!।

14. Output walkthrough

চালালে ছাপবে:

['L', 'W', 'W', 'W', 'L', 'W', 'W', 'W', 'L', 'W', 'W', 'W', 'L']
False
True
সব test pass!

প্রথম লাইন n = 0..12-এর W/L — 0, 4, 8, 12-এ L (n % 4 == 0)। দ্বিতীয় লাইন n=4 → False (প্রথম player হারে)। তৃতীয় n=7 → True (জেতে)। তার আগের assert গুলো চুপচাপ pass করেছে। সবশেষে সব test pass!।

15. Time complexity

O(N · |moves|) — table-এর প্রতিটা ঘর (N+1টা) ভরতে প্রতিটা move দেখা (|moves|টা)। উপরের game-এ moves মাত্র 3টা, তাই কার্যত O(N)। আর pattern (n % 4) ধরা পড়লে O(1) সূত্রও বেরোয়।

16. Space complexity

O(N) — win array-টা N+1 ঘরের। চাইলে শুধু শেষ কয়েকটা ঘর রেখে O(|moves|)-এও নামানো যায় (যেহেতু win[n] কেবল আগের কয়েকটা ঘর দেখে), কিন্তু পুরো table থাকলে pattern খুঁজতে সুবিধা।

17. Common mistakes

  1. Greedy চাল = জেতা ভাবা — locally ভালো চাল মানেই জেতা নয়; W/L recursive (concept-notes mistake #3)।
  2. Base case ভুল — win[0] হলো L (চাল নেই = হার, normal play); এটাকে W ভাবলে পুরো table উল্টে যায়।
  3. "any" আর "all" গুলিয়ে ফেলা — W ⟺ অন্তত একটা চাল L-এ (any); L ⟺ সব চাল W-তে (all)। উল্টে ফেললে সব ভুল।
  4. Misère variant গুলিয়ে ফেলা — "শেষ পাথর নিলে হার" (misère) আলাদা নিয়ম; এখানে normal play (চাল না দিতে পারলে হার)।
  5. Memo ছাড়া recursion — exponential হয়ে TLE; DP/memo লাগবেই।

18. Harder problems that inherit this idea

19. Pattern learned

W/L labeling (backward induction over game states) — base = চাল-হীন position L; তারপর পেছন থেকে: position W ⟺ অন্তত একটা চাল L-এ যায়, L ⟺ সব চাল W-তে। ছোট table থেকে pattern → O(1) সূত্র।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "পালা-খেলায় কে জেতে — পেছন থেকে W/L ভরো: চাল-হীন position L; W ⟺ অন্তত একটা চাল opponent-কে L-এ ফেলে। ছোট case-এ table বানিয়ে pattern খোঁজো (এই game-এ n % 4 == 0 → L)।"

পরের ধাপ → 142 — Nim Game (এই W/L-চিন্তা + XOR theorem)। তারপর → 143 — Grundy Number Intro।

ফিরে দেখা: এই level-এর map → ../README.md · চিন্তার ছাঁচ → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — বরং "CP-style pattern" / "common interview pattern" বলা হয়েছে।