খেলার search — minimax আর alpha-beta

আগের তিন পর্বে (পর্ব ৩৯, ৪০ আর ৪১) search-এর জগৎ ছিল শান্ত: রিকশাওয়ালা মিরপুর থেকে মতিঝিলের রাস্তা খোঁজেন, আর রাস্তাগুলো তাঁর বিরুদ্ধে ষড়যন্ত্র করে না। এই পর্বে জগতে আরেকজন agent আসছে, যে চায় আপনি হারুন। এটিই adversarial search: চায়ের দোকানে দাবার বোর্ডের দুই পাশের হিসাব, কম্পিউটারের ভাষায়। Graph আর DFS-এর data-structure দিক DSA কোর্সের DFS আর recursion পর্বে; এখানে দেখব খেলাকে কীভাবে search সমস্যা হিসেবে লেখা হয়, আর কম খরচে নিখুঁত চাল কীভাবে বের হয়।

১ · প্রতিপক্ষসহ search — কোন খেলা, আর খেলার সংজ্ঞা

সব খেলা এক রকম নয়। এই পর্বের মূল পদ্ধতিগুলো (minimax, alpha-beta) সবচেয়ে পরিষ্কারভাবে কাজ করে এমন খেলায়, যার চারটি বৈশিষ্ট্য আছে:

• দুই খেলোয়াড়, পালা করে চাল: নাম দেব MAX (যে মান বাড়াতে চায়) আর MIN (যে কমাতে চায়)।
• Zero-sum: একজনের জয় মানে অন্যজনের হার (জয় +1, হার −1, ড্র 0); তাই MAX-এর মান যত কম, MIN তত খুশি।
• Perfect information: সব দেখা যায়, কিছু লুকানো নেই; পর্ব ১-এর ভাষায় fully observable.
• ভাগ্যের ভূমিকা নেই: ছক্কা বা তাস বাটা নেই, মানে deterministic.

একটি খেলার আনুষ্ঠানিক সংজ্ঞা

পর্ব ৩৯-এ একটি সমস্যাকে state, action, transition আর goal দিয়ে লিখেছিলেন, আর সব state মিলে একটি state space. খেলার জন্য এর সঙ্গে দুটি জিনিস যোগ হয়: কার পালা, আর শেষে কে কত পেল। Tic-tac-toe দিয়ে ছয়টি অংশ:

খেয়াল করুন, utility সবসময় MAX-এর চোখে: O জিতলে −1, যা MIN-এর জন্য ভালো। Zero-sum বলে একটি সংখ্যাতেই দুজনের মনোভাব ধরা যায়। এই ছয়টি অংশই নিচের কোডে ছয়টি ছোট function.

২ · খেলার গাছ কত বড়

প্রথম চালে X-এর ৯টি বিকল্প, তারপর O-এর ৮টি, তারপর ৭টি… খেলা কখনো আগে শেষ না হলে চালের মোট ক্রম হতো 9! = 9 × 8 × … × 1 = ৩,৬২,৮৮০টি (factorial, পর্ব ৩৫)। কিন্তু অনেক খেলা পাঁচ, ছয় বা সাত চালেই কেউ জিতে শেষ হয়, তখন বাকি চাল আর দেওয়া হয় না। তাই আসল সংখ্যা কম। লেখকের যন্ত্রে পুরো গাছ গুনে পাওয়া গেছে (অংশ ৪-এর কোড একই সংখ্যা পাতাতেই বের করে):

তিনটি কলাম তিনটি আলাদা প্রশ্নের উত্তর। আলাদা খেলা ২,৫৫,১৬৮টি: শুরু থেকে শেষ পর্যন্ত চালের সম্পূর্ণ ক্রম (X জেতে ১,৩১,১৮৪টিতে, O ৭৭,৯০৪টিতে, ড্র ৪৬,০৮০)। গাছের node ৫,৪৯,৯৪৬টি: সাধারণ minimax যতবার একটি অবস্থায় ঢোকে। আলাদা বোর্ড-অবস্থা মাত্র ৫,৪৭৮টি, কারণ ভিন্ন ক্রমের চালে একই বোর্ডে পৌঁছানো যায় (X কোণায় তারপর মাঝে, বা উল্টো)। ছয় চালে node আলাদা অবস্থার প্রায় ৩৬ গুণ; এই ফাঁকটিই অংশ ৪-এ memoization কাজে লাগাবে। (সমমিতি, মানে বোর্ড ঘোরানো বা উল্টানো, এক ধরা হয়নি।)

দাবায় সংখ্যাগুলো গোনা যায় না, শুধু অনুমান করা যায়। Claude Shannon ১৯৫০ সালে মোটা দাগে ধরেছিলেন, প্রতি চালে প্রায় ৩০টি বিকল্প আর খেলায় প্রায় ৪০ জোড়া চাল, ফলে চালের ক্রম প্রায় 10¹²⁰; এটি এখন “Shannon number” নামে উদ্ধৃত হয়, তবে এটি একটি মোটা অনুমান, গণনা নয়। দাবার বৈধ অবস্থার নানা অনুমান 10⁴³ থেকে 10⁴⁷-এর মতো পরিসরে, আর Go-র বৈধ অবস্থা প্রায় 2 × 10¹⁷⁰ বলে গণনা প্রকাশিত হয়েছে (John Tromp ও সহকর্মীরা, ২০১৬)। শিক্ষাটি একই: বড় খেলার পুরো গাছ কোনো কম্পিউটার দেখতে পারবে না.

৩ · Minimax — হাতে দুই ply-এর গাছ, তারপর কোড

ক্রিকেটের অধিনায়কের কথা ভাবুন। তিনি ফিল্ডিং সাজানোর সময় ভাবেন না “ব্যাটসম্যান হয়তো ভুল শট খেলবে”; ভাবেন “ব্যাটসম্যান সবচেয়ে ভালো শটটি খেললে কী হবে”। Minimax ঠিক এই সতর্ক চিন্তা: প্রতিপক্ষ সবসময় আপনার জন্য সবচেয়ে খারাপ জবাবটি দেবে, এটা ধরে নিয়ে নিজের সেরা চাল বাছা।

নিয়মটি recursive (নিজেকে ডাকা):

Minimax(s) = Utility(s), যদি s শেষ অবস্থা
= max_a Minimax(Result(s, a)), যদি MAX-এর পালা
= min_a Minimax(Result(s, a)), যদি MIN-এর পালা

এখানে max_a মানে “সব বৈধ চাল a-এর মধ্যে সবচেয়ে বড়”। Leaf থেকে শুরু করে মানগুলো এক স্তর এক স্তর করে ওপরে ওঠে, যাকে বলে backing up. গাছটি DFS-এর ক্রমে ঘোরা হয় (DFS), তাই memory লাগে শুধু গভীরতার সমান, O(bm), কিন্তু সময় লাগে O(b^m).

নিচের ছোট গাছটি কোনো আসল খেলার নয়, হাতে হিসাবের জন্য বানানো। Root-এ MAX-এর তিনটি চাল A, B, C; প্রতিটির পর MIN-এর তিনটি জবাব, আর leaf-এর সংখ্যাগুলো MAX-এর চোখে utility. “পরে” চেপে মান ওপরে উঠতে দেখুন।

এবার একই গাছ কোডে। নিচের function গাছটিকে nested Python dict আর list হিসেবে নেয়, recursive ভাবে প্রতিটি node-এর মান বের করে আর তা ছাপে। ছাপার ক্রম খেয়াল করুন: সন্তানের মান আগে, মা-বাবার পরে, ঠিক backing up-এর মতো। প্রথমবার চালালে ব্রাউজারে Python নামতে কয়েক সেকেন্ড লাগতে পারে।

tree = {"A": [5, 8, 6], "B": [3, 9, 7], "C": [10, 4, 2]}   # MIN-এর তিনটি node

def minimax(node, is_max, name="root", depth=0):
    if isinstance(node, int):                 # leaf: খেলা শেষ, utility জানা
        return node
    if isinstance(node, dict):
        items = list(node.items())
    else:
        items = [(f"{name}[{i}]", x) for i, x in enumerate(node)]
    vals = {k: minimax(v, not is_max, k, depth + 1) for k, v in items}
    best = max(vals.values()) if is_max else min(vals.values())
    who = "MAX" if is_max else "MIN"
    print("    " * depth + f"{who} {name}: সন্তানের মান {list(vals.values())} -> {best}")
    return best

value = minimax(tree, True)
print("root-এর মান:", value)
moves = {k: min(v) for k, v in tree.items()}
print("MAX-এর সেরা চাল:", max(moves, key=moves.get))

    MIN A: সন্তানের মান [5, 8, 6] -> 5
    MIN B: সন্তানের মান [3, 9, 7] -> 3
    MIN C: সন্তানের মান [10, 4, 2] -> 2
MAX root: সন্তানের মান [5, 3, 2] -> 5
root-এর মান: 5
MAX-এর সেরা চাল: A

৪ · Tic-tac-toe পুরোটা সমাধান — memoization আর ড্র

এবার আসল খেলা। অংশ ১-এর ছয়টি অংশ এখানে ছয়টি ছোট function: player, actions, result, terminal, utility আর বোর্ড একটি ৯ অক্ষরের string ("X...O...X" মানে ঘর 0 আর 8-এ X, ঘর 4-এ O; ঘরের নম্বর বাঁ থেকে ডানে, ওপর থেকে নিচে 0 থেকে 8).

অংশ ২-এ দেখেছেন, গাছে ৫,৪৯,৯৪৬টি node থাকলেও আলাদা বোর্ড মাত্র ৫,৪৭৮টি। তাই একই বোর্ডের minimax মান বারবার হিসাব করা অপচয়। সমাধান memoization: প্রথমবার হিসাবের পর উত্তর একটি dict-এ রেখে দেওয়া, পরের বার সেখান থেকে নেওয়া। Python-এ functools.lru_cache decorator ঠিক এটি করে (Python কোর্সের functional tools পর্ব); DSA কোর্সে একই ধারণা dynamic programming-এর ভিত্তি নামে আছে। খেলার প্রোগ্রামে এই মনে রাখার টেবিলকে বলে transposition table. বোর্ড string বলে hash করা যায়, তাই cache-এর key হিসেবে সরাসরি চলে।

নিচের কোড চারটি কাজ করে: খালি বোর্ডের minimax মান, memo-তে কতগুলো আলাদা অবস্থা জমা হলো, পুরো গাছের খেলা ও node গোনা (tally, এটিও memo দিয়ে, তাই ৫ লাখ node আসলে না ঘুরেই গোনা যায়), আর একটি নির্দিষ্ট অবস্থায় সেরা চাল। এর পরের দুটি কোড ব্লক এই function-গুলোই ব্যবহার করবে (data-shared), তাই প্রথমে এটি চালান।

from functools import lru_cache
LINES = [(0,1,2), (3,4,5), (6,7,8), (0,3,6), (1,4,7), (2,5,8), (0,4,8), (2,4,6)]
def winner(b):
    for i, j, k in LINES:
        if b[i] != "." and b[i] == b[j] == b[k]:
            return b[i]
    return None
def player(b):    return "X" if b.count("X") == b.count("O") else "O"
def actions(b):   return [i for i, c in enumerate(b) if c == "."]
def result(b, a): return b[:a] + player(b) + b[a+1:]
def terminal(b):  return winner(b) is not None or "." not in b
def utility(b):   return {"X": 1, "O": -1, None: 0}[winner(b)]
@lru_cache(maxsize=None)              # memoization: একই অবস্থা দ্বিতীয়বার হিসাব নয়
def minimax(b):
    if terminal(b):
        return utility(b)
    vals = [minimax(result(b, a)) for a in actions(b)]
    return max(vals) if player(b) == "X" else min(vals)
@lru_cache(maxsize=None)
def tally(b):                         # (খেলা, X জেতে, O জেতে, ড্র, গাছের node)
    if terminal(b):
        u = utility(b)
        return (1, int(u == 1), int(u == -1), int(u == 0), 1)
    s = [sum(t) for t in zip(*(tally(result(b, a)) for a in actions(b)))]
    return (*s[:4], s[4] + 1)
empty = "." * 9
print("খালি বোর্ডের minimax মান:", minimax(empty))
print("memo-তে আলাদা অবস্থা:", minimax.cache_info().currsize)
print("খেলা, X জয়, O জয়, ড্র, গাছের node:", tally(empty))
pos = "X...O...X"                     # X: 0 আর 8, O: 4; এখন O-র চাল
vals = {a: minimax(result(pos, a)) for a in actions(pos)}
print("O-র চালগুলোর মান:", vals)
print("O-র নিরাপদ চাল:", [a for a, v in vals.items() if v == min(vals.values())])

খালি বোর্ডের minimax মান: 0
memo-তে আলাদা অবস্থা: 5478
খেলা, X জয়, O জয়, ড্র, গাছের node: (255168, 131184, 77904, 46080, 549946)
O-র চালগুলোর মান: {1: 0, 2: 1, 3: 0, 5: 0, 6: 1, 7: 0}
O-র নিরাপদ চাল: [1, 3, 5, 7]

৫ · Alpha-beta pruning — α, β আর কাটা শাখা

অংশ ৩-এর গাছে ফিরে যান। A দেখার পর MAX জানে, root-এ অন্তত 5 নিশ্চিত। এবার B-র প্রথম leaf 3. MIN B-তে অন্তত 3-এ নামাতে পারবে, হয়তো আরও কম, কিন্তু কখনো 3-এর বেশি দেবে না। তাহলে B-র মান ≤ 3 < 5, আর MAX কখনো B খেলবে না। B-র বাকি দুটি leaf (9 আর 7) যা-ই হোক, root-এর সিদ্ধান্ত বদলাবে না। তাদের দেখারই দরকার নেই। এটিই alpha-beta pruning-এর পুরো ধারণা।

চলার পথে দুটি সংখ্যা সঙ্গে রাখা হয়:

• α (alpha): এ পর্যন্ত পাওয়া পথে MAX নিশ্চিতভাবে যত পেতে পারে, তার সেরা মান। শুরুতে −∞; শুধু MAX node-এ বাড়ে।
• β (beta): এ পর্যন্ত পাওয়া পথে MIN নিশ্চিতভাবে MAX-কে যত কমে আটকে রাখতে পারে, তার সেরা মান। শুরুতে +∞; শুধু MIN node-এ কমে।
• কাটার নিয়ম: কোনো node-এ α ≥ β হলেই বাকি সন্তানদের দেখা বন্ধ। MIN node-এ এটি ঘটলে বলে α-cut, MAX node-এ β-cut.

α আর β মিলে একটি “জানালা” (α, β): এই জানালার বাইরের কোনো মান root পর্যন্ত পৌঁছাতে পারে না। নিচে একই গাছে leaf এক এক করে দেখুন।

৬ · চালের ক্রম — কেন একই গাছে কখনো অনেক, কখনো সামান্য কাটা

অংশ ৫-এর গাছে leaf-গুলো যদি উল্টো ক্রমে থাকত, ধরুন A-র জায়গায় C আগে আসত, তাহলে প্রথমে α হতো 2, আর পরে কাটার সুযোগ কমে যেত। কাটা হয় তখনই, যখন সেরা চালটি আগে দেখা হয়: তাড়াতাড়ি একটি ভালো α বা β পেলে বাকি খারাপ বিকল্প দ্রুত বাদ পড়ে। একে বলে move ordering.

Donald Knuth আর Ronald Moore ১৯৭৫ সালের একটি বিখ্যাত বিশ্লেষণে দেখান, b branching factor আর d গভীরতার সমান-আকারের গাছে নিখুঁত ক্রম পেলে alpha-beta ঠিক b^⌈d/2⌉ + b^⌊d/2⌋ − 1টি leaf দেখে (⌈ ⌉ মানে ওপরের দিকে, ⌊ ⌋ মানে নিচের দিকে পূর্ণসংখ্যায় গোল করা)। এটি মোটামুটি O(b^d/2), মানে minimax-এর b^d-এর বর্গমূল। একই সময়ে প্রায় দ্বিগুণ গভীরে দেখা যায়। খারাপ ক্রমে কাটা প্রায় হয় না, খরচ minimax-এর কাছাকাছি, O(b^d). এলোমেলো ক্রমে মাঝামাঝি, প্রায়ই O(b^3d/4)-এর কাছাকাছি বলে উদ্ধৃত হয়।

সূত্রটি লেখকের যন্ত্রে একটি বানানো গাছে যাচাই করা হলো: b = 4, d = 6, মানে ৪,০৯৬টি leaf, প্রতিটিতে seed 42 দিয়ে 0 থেকে 99-এর এলোমেলো সংখ্যা। “সেরা চাল আগে” ক্রমের জন্য আগে সাধারণ minimax দিয়ে আসল মান বের করা হয়েছে, যা বাস্তবে সম্ভব নয়; এটি শুধু তাত্ত্বিক সেরা অবস্থা।

$ python ordering_lab.py
minimax: মান 26 | leaf 4096
alpha-beta, 0,1,2,3 ক্রমে: মান 26 | leaf 687
alpha-beta, সেরা চাল আগে: মান 26 | leaf 127
alpha-beta, সবচেয়ে খারাপ চাল আগে: মান 26 | leaf 3568
Knuth-Moore সূত্র b^ceil(d/2) + b^floor(d/2) - 1 = 127

সত্যিকারের run (Python 3.14.4, শুধু standard library; স্ক্রিপ্টে random.Random(42), lru_cache আর অংশ ৫-এর মতো alpha-beta). চারটি পদ্ধতিরই মান 26, উত্তর এক। নিখুঁত ক্রমে ঠিক ১২৭টি leaf, সূত্রের সঙ্গে হুবহু: ৪,০৯৬-এর মাত্র ৩%. সাধারণ (0, 1, 2, 3) ক্রমে ৬৮৭টি, আর প্রতিটি স্তরে সবচেয়ে খারাপটি আগে দিলে ৩,৫৬৮টি, প্রায় পুরো গাছ।

এবার tic-tac-toe-তে। নিচের কোড একটি সাধারণ alpha-beta লেখে, যা যেকোনো গাছে চলে: শুধু বলে দিতে হয় কোনো অবস্থার সন্তান কারা (kids) আর শেষ অবস্থার মান কী (value). প্রথমে অংশ ৫-এর হাতের গাছে চালিয়ে stepper মেলানো হয়, তারপর খালি বোর্ড থেকে চার রকম ক্রমে। “মাঝ-কোণা-ধার” একটি সহজ heuristic: মাঝের ঘর চারটি লাইনে, কোণা তিনটিতে, ধার দুটিতে পড়ে, তাই মাঝ আগে দেখা স্বাভাবিক। “সেরা চাল আগে” আবার একটি তাত্ত্বিক সেরা অবস্থা, আগের ব্লকের memo করা minimax ব্যবহার করে।

import math
def alphabeta(s, alpha, beta, is_max, kids, value, stat):
    stat["node"] += 1
    ks = kids(s)
    if not ks:                                # terminal
        return value(s)
    v = -math.inf if is_max else math.inf
    for i, k in enumerate(ks):
        x = alphabeta(k, alpha, beta, not is_max, kids, value, stat)
        if is_max: v = max(v, x); alpha = max(alpha, v)
        else:      v = min(v, x); beta = min(beta, v)
        if alpha >= beta:                     # বাকি ভাইবোনদের দেখার দরকার নেই
            stat["cut"] += ks[i + 1:]
            break
    return v
hand = [[5, 8, 6], [3, 9, 7], [10, 4, 2]]
st = {"node": 0, "cut": []}
v = alphabeta(hand, -math.inf, math.inf, True,
              lambda t: t if isinstance(t, list) else [], lambda t: t, st)
print("হাতের গাছ: মান", v, "| node দেখা", st["node"], "of 13 | বাদ পড়া leaf", st["cut"])
def ttt_kids(order):
    return lambda b: [] if terminal(b) else [result(b, a) for a in order(b)]
def pref(p): return lambda b: [i for i in p if b[i] == "."]
orders = {"0..8 ক্রমে":     actions,
          "মাঝ-কোণা-ধার":  pref([4, 0, 2, 6, 8, 1, 3, 5, 7]),
          "ধার-কোণা-মাঝ":  pref([1, 3, 5, 7, 0, 2, 6, 8, 4]),
          "সেরা চাল আগে":  lambda b: sorted(actions(b), reverse=player(b) == "X",
                                            key=lambda a: minimax(result(b, a)))}
print("pruning ছাড়া minimax:", tally(empty)[4], "node")
for name, order in orders.items():
    st = {"node": 0, "cut": []}
    v = alphabeta(empty, -2, 2, True, ttt_kids(order), utility, st)
    print(f"alpha-beta, {name}: মান {v}, node {st['node']}")

হাতের গাছ: মান 5 | node দেখা 10 of 13 | বাদ পড়া leaf [9, 7, 2]
pruning ছাড়া minimax: 549946 node
alpha-beta, 0..8 ক্রমে: মান 0, node 18297
alpha-beta, মাঝ-কোণা-ধার: মান 0, node 7275
alpha-beta, ধার-কোণা-মাঝ: মান 0, node 42094
alpha-beta, সেরা চাল আগে: মান 0, node 2312

৭ · Nim — search-এর উত্তর গণিতের সঙ্গে মেলানো

Search-এর কোড লিখলেন, উত্তরও এলো। কিন্তু উত্তর যে ঠিক, তা কীভাবে জানবেন? সবচেয়ে ভালো উপায় এমন একটি খেলা, যার উত্তর অন্য পথে আগে থেকেই জানা। Nim ঠিক তেমন খেলা। কয়েকটি স্তূপে দিয়াশলাইয়ের কাঠি রাখা। নিজের পালায় একটি স্তূপ বেছে সেখান থেকে যত খুশি (অন্তত একটি) কাঠি তুলতে হয়। যে শেষ কাঠিটি তোলে, সে জেতে।

Charles L. Bouton ১৯০১ সালে Annals of Mathematics-এ প্রকাশিত প্রবন্ধে এই খেলার পূর্ণ গাণিতিক সমাধান দেন। সব স্তূপের কাঠির সংখ্যার bitwise XOR (প্রতিটি bit আলাদা করে যোগ, ২ দিয়ে ভাগশেষ) নিন; একে বলে nim-sum. Bouton-এর নিয়ম: nim-sum শূন্য হলে যার চাল, সে হারবে (প্রতিপক্ষ নিখুঁত খেললে); শূন্য না হলে সে জিতবে, আর জেতার চাল হলো এমন একটি চাল যা nim-sum শূন্য করে দেয়।

হাতে একটি উদাহরণ: স্তূপ (3, 4, 5). Binary-তে 011, 100, 101. XOR: 011 ⊕ 100 = 111, তারপর 111 ⊕ 101 = 010, মানে nim-sum 2 ≠ 0, তাই প্রথমজন জিতবে। কোন স্তূপে চাল? যে স্তূপের h-এর জন্য h ⊕ 2 < h: 3 ⊕ 2 = 1 < 3, তাই প্রথম স্তূপ 3 থেকে 1-এ নামান (২টি কাঠি তুলুন)। নতুন অবস্থা (1, 4, 5): 001 ⊕ 100 ⊕ 101 = 000, প্রতিপক্ষ এখন হারার অবস্থায়।

এবার search দিয়ে একই প্রশ্ন, কোনো XOR না জেনে। একটি অবস্থা “জেতার” যদি এমন অন্তত একটি চাল থাকে যা প্রতিপক্ষকে “হারার” অবস্থায় পাঠায়; নইলে “হারার”। এটি আসলে minimax, শুধু utility +1/−1 আর মান সবসময় যার চাল তার চোখে (negamax-এর ধাঁচে)। স্তূপের ক্রম ফলে প্রভাব ফেলে না, তাই sorted করে অবস্থা কমানো হয়েছে। লেখকের যন্ত্রে সত্যিকারের run (Python 3.14.4):

from functools import lru_cache
from itertools import product

@lru_cache(maxsize=None)
def wins(heaps):                     # যার চাল, সে কি জোর করে জিততে পারে?
    for i, h in enumerate(heaps):
        for take in range(1, h + 1):
            nxt = tuple(sorted(heaps[:i] + (h - take,) + heaps[i + 1:]))
            if not wins(nxt):        # প্রতিপক্ষকে হারার অবস্থায় পাঠানো গেলে জয়
                return True
    return False                     # (0,0,0)-তে কোনো চাল নেই: আগের জন শেষ কাঠি নিয়েছে

def xor_rule(heaps):                 # Bouton (1901): nim-sum শূন্য না হলে জয়
    x = 0
    for h in heaps:
        x ^= h
    return x != 0

agree = total = 0
for hs in product(range(6), repeat=3):          # প্রতিটি স্তূপে 0 থেকে 5টি কাঠি
    total += 1
    agree += wins(tuple(sorted(hs))) == xor_rule(hs)
print("মিলেছে:", agree, "/", total, "| memo-তে অবস্থা:", wins.cache_info().currsize)
print("হারার অবস্থা:", sorted({tuple(sorted(h)) for h in product(range(6), repeat=3)
                                if not wins(tuple(sorted(h)))}))
h = (3, 4, 5)
x = 3 ^ 4 ^ 5
print("(3, 4, 5): nim-sum", x, "| জয়?", wins(h))
print("জেতার চাল:", [(i, v, v ^ x) for i, v in enumerate(h) if v ^ x < v])

$ python nim_check.py
মিলেছে: 216 / 216 | memo-তে অবস্থা: 56
হারার অবস্থা: [(0, 0, 0), (0, 1, 1), (0, 2, 2), (0, 3, 3), (0, 4, 4), (0, 5, 5), (1, 2, 3), (1, 4, 5)]
(3, 4, 5): nim-sum 2 | জয়? True
জেতার চাল: [(0, 3, 1)]

২১৬টি অবস্থার প্রতিটিতে search আর XOR নিয়ম একই কথা বলেছে; সাজানোর পর আলাদা অবস্থা মাত্র ৫৬টি। হারার অবস্থায় দুটি সমান স্তূপ (প্রতিপক্ষ শুধু আপনার চাল নকল করে), আর (1, 2, 3), (1, 4, 5), যেখানে XOR শূন্য। শেষ লাইন হাতের হিসাব মেলায়: স্তূপ 0, 3 থেকে 1.

৮ · বড় খেলা — গভীরতার সীমা, evaluation function, horizon effect আর দান

দাবায় alpha-beta নিখুঁত ক্রমেও খেলার শেষ পর্যন্ত দেখতে পারে না। তাই Shannon-এর প্রস্তাব মেনে প্রোগ্রাম একটি নির্দিষ্ট গভীরতায় থামে (depth-limited search), আর সেখানে আসল utility-র বদলে একটি evaluation function Eval(s) দিয়ে অবস্থার মান অনুমান করে। নিয়মটি হয়:

H-Minimax(s, d) = Utility(s), যদি s শেষ অবস্থা
= Eval(s), যদি d = গভীরতার সীমা
নইলে আগের মতো max বা min, d + 1 গভীরতায়

ভালো evaluation function শেষ অবস্থায় utility-র সঙ্গে একই ক্রম দেয়, দ্রুত হিসাব হয় (লাখ লাখ বার ডাকা হবে), আর জেতার সম্ভাবনার সঙ্গে শক্ত সম্পর্ক রাখে। দাবায় পুরোনো সহজ রূপ ঘুঁটির মানের যোগ (প্রচলিত মোটা অনুপাতে বোড়ে 1, ঘোড়া ও হাতি প্রায় 3, নৌকা 5, মন্ত্রী 9), সঙ্গে রাজার নিরাপত্তার মতো বিষয়ের ওজন। এগুলো heuristic: অভিজ্ঞতার আন্দাজ, প্রমাণ নয়।

Tic-tac-toe-এর একটি সহজ evaluation

একটি লাইন (সারি, কলাম বা কর্ণ, মোট ৮টি) X-এর জন্য “খোলা” যদি সেখানে কোনো O না থাকে। ধরা যাক Eval(s) = X-এর খোলা লাইন − O-এর খোলা লাইন। প্রথম চালের পর হিসাব:

এই evaluation-ই অংশ ৬-এর “মাঝ-কোণা-ধার” ক্রমের যুক্তি। লেখকের যন্ত্রে দুই ply গভীর হিসাবে (জয় বা হার ±100, যাতে আসল ফল অনুমানের চেয়ে ভারী) মাঝের চালের মান 1, কোণার −1, ধারের −2 এসেছে, তাই প্রোগ্রাম মাঝ বাছে। কিন্তু নিখুঁত হিসাবে সব প্রথম চালই 0: অগভীর search একটি পছন্দ দেয়, প্রমাণ নয়।

Horizon effect

ধরুন দাবায় প্রোগ্রাম ৬ ply দেখে, আর ৮ ply পরে তার মন্ত্রী হারানো অনিবার্য। প্রোগ্রাম তখন একটি বোড়ে বিসর্জন দিয়ে কয়েকটি কিস্তি দেয়, যাতে মন্ত্রী হারানো সীমার ওপারে চলে যায়; সীমার ভেতরে সে দেখে “বোড়ে গেল, মন্ত্রী আছে”। আসলে দুটিই যাবে। এর নাম horizon effect. প্রচলিত প্রতিকার quiescence search: সীমায় অবস্থা অস্থির হলে (ঘুঁটি খাওয়ার চাল বাকি) শুধু সেই চালগুলো দিয়ে আরও খোঁজা। এটি সমস্যা কমায়, দূর করে না।

দানের খেলা: expectiminimax

লুডুতে চাল দেওয়ার আগে ছক্কা পড়ে। এমন stochastic খেলার গাছে MAX আর MIN node-এর মাঝে আসে chance node, যার মান সন্তানদের মানের সম্ভাবনা-ওজনসহ গড়, মানে expected value (পর্ব ৩৬): Value = ∑ P(r) × Value(Result(s, r)), যেখানে r ছক্কার একটি ফল। এটিই expectiminimax. একটি ছোট উদাহরণ: MAX-এর চাল ক নিশ্চিতভাবে 3 দেয়। চাল খ-এর পর একটি মুদ্রা টস: অর্ধেক সম্ভাবনায় 8, অর্ধেক সম্ভাবনায় −1. খ-এর মান 0.5 × 8 + 0.5 × (−1) = 3.5 > 3, তাই MAX খ নেবে।

এবার 8-এর জায়গায় 5 বসান। Leaf-গুলোর ক্রম একই থাকে (−1 < 3 < 5), কিন্তু খ-এর মান 0.5 × 5 + 0.5 × (−1) = 2 < 3, সিদ্ধান্ত উল্টে গেল। সাধারণ minimax-এ শুধু মানের ক্রম গুরুত্বপূর্ণ; expectiminimax-এ মানের আসল মাপও গুরুত্বপূর্ণ। তাই দানের খেলায় evaluation function-কে জেতার সম্ভাবনার সঙ্গে আনুপাতিক হতে হয়। অনিশ্চয়তায় সিদ্ধান্তের পুরো কাঠামো (expected utility আর MDP) পর্ব ৫৪-এ আসবে।

৯ · Monte Carlo tree search — এলোমেলো খেলা থেকে চাল বাছা

Go-র বোর্ড ১৯×১৯, প্রতি চালে প্রায়ই দুইশোর বেশি বিকল্প, আর ভালো evaluation function বহু বছর কেউ বানাতে পারেনি; alpha-beta তাই সেখানে দুর্বল ছিল। বিকল্প ধারণা: অবস্থার মান হিসাব না করে অনেকবার এলোমেলো খেলে দেখা। দুজনেই এলোমেলো চালে খেলা শেষ করা হলো একটি playout; হাজারটি playout-এ যে চালের পর বেশি জয়, সেটি সম্ভবত ভালো। এটি পর্ব ৩৬-এর Monte Carlo simulation-এর ধারণা (DSA কোর্সের randomized অ্যালগরিদম পর্বও দেখুন)।

শুধু playout-এর গড় (একে বলে flat Monte Carlo) একটি দুর্বলতা রাখে: এলোমেলো প্রতিপক্ষ ভুল করে, তাই এমন চালও ভালো দেখায় যা নিখুঁত প্রতিপক্ষের বিরুদ্ধে হারে। Monte Carlo tree search (MCTS) এর সমাধান দেয় ধীরে ধীরে একটি গাছ বানিয়ে, প্রতিটি পুনরাবৃত্তিতে চারটি ধাপে:

1. Selection: root থেকে একটি সূত্র দিয়ে সন্তান বেছে নিচে নামা।
2. Expansion: একটি নতুন সন্তান গাছে যোগ।
3. Simulation: সেখান থেকে একটি playout.
4. Backup: পথের প্রতিটি node-এ ভিজিট n আর জয় w হালনাগাদ।

Selection-এর প্রচলিত সূত্র UCB1 (Auer, Cesa-Bianchi আর Fischer, ২০০২), গাছে প্রয়োগের নাম UCT (Kocsis আর Szepesvári, ২০০৬)। সূত্রটি শুধু দেখানো হচ্ছে, প্রমাণ নয়:

UCB1(সন্তান i) = w_i / n_i + c √( ln N / n_i )

w_i হলো সন্তানটির জয়ের সংখ্যা (ড্র অর্ধেক), n_i তার ভিজিট, N মা-বাবার ভিজিট, ln স্বাভাবিক logarithm, আর c একটি ধ্রুবক (প্রায়ই √2 ≈ 1.414). প্রথম পদ এ পর্যন্ত যে চাল ভালো ফল দিয়েছে তাকে টানে (exploitation); দ্বিতীয় পদ কম চেষ্টা করা চালকে সুযোগ দেয়, কারণ n_i ছোট হলে পদটি বড় (exploration). এই টানাপোড়েনের নাম exploration–exploitation trade-off, যা reinforcement learning-এও কেন্দ্রীয় (পর্ব ৫৫)। নিচে একটি পুনরাবৃত্তি সংখ্যাসহ দেখুন।

এবার অংশ ৪-এর ফাঁদের অবস্থাটি ("X...O...X", O-র চাল, কোণা খেললে হার, ধার খেললে ড্র) দুই পদ্ধতিতে দেওয়া যাক: প্রতিটি চালের পর ১,০০০টি playout-এর flat Monte Carlo, আর ৩,০০০ পুনরাবৃত্তির UCT. দুটিই seed দেওয়া random.Random(1) ব্যবহার করে, তাই প্রতিবার একই ফল। কোডটি অংশ ৪-এর function-গুলোর ওপর দাঁড়িয়ে (data-shared).

import math, random
def playout(b, rng):                      # এলোমেলো চালে খেলা শেষ পর্যন্ত
    while not terminal(b):
        b = result(b, rng.choice(actions(b)))
    return winner(b)
def score(w, me): return 1 if w == me else 0.5 if w is None else 0
def flat_mc(b, n, rng):                   # প্রতিটি চালের পর n টি playout-এর গড়
    me = player(b)
    return {a: sum(score(playout(result(b, a), rng), me) for _ in range(n)) / n
            for a in actions(b)}
class Node:
    def __init__(s, b, parent=None):
        s.b, s.parent, s.kids, s.n, s.w = b, parent, {}, 0, 0.0
        s.todo = [] if terminal(b) else actions(b)
def uct(b, iters, rng, c=math.sqrt(2)):
    root = Node(b)
    for _ in range(iters):
        node = root
        while not node.todo and node.kids:                       # ১. select
            node = max(node.kids.values(), key=lambda k:
                       k.w / k.n + c * math.sqrt(math.log(node.n) / k.n))
        if node.todo:                                            # ২. expand
            a = node.todo.pop(rng.randrange(len(node.todo)))
            child = Node(result(node.b, a), node)
            node.kids[a] = child; node = child
        w = playout(node.b, rng)                                 # ৩. simulate
        while node:                                              # ৪. back up
            mover = "O" if player(node.b) == "X" else "X"        # যে এই node-এ চাল দিল
            node.n += 1; node.w += score(w, mover); node = node.parent
    return {a: k.n for a, k in root.kids.items()}
pos = "X...O...X"
f = flat_mc(pos, 1000, random.Random(1))
print("flat MC গড়:", {a: round(v, 3) for a, v in f.items()}, "-> বাছাই", max(f, key=f.get))
u = uct(pos, 3000, random.Random(1))
print("UCT-এর ভিজিট:", dict(sorted(u.items())), "-> বাছাই", max(u, key=u.get))

flat MC গড়: {1: 0.553, 2: 0.589, 3: 0.563, 5: 0.546, 6: 0.544, 7: 0.528} -> বাছাই 2
UCT-এর ভিজিট: {1: 698, 2: 143, 3: 671, 5: 662, 6: 147, 7: 679} -> বাছাই 1

খেলা যখন বাস্তব প্রতিপক্ষের মডেল

নিরাপত্তায় আক্রমণকারী আর রক্ষাকারীকে দুই খেলোয়াড় ধরে “আক্রমণকারী সবচেয়ে খারাপ কাজটি করবে” ধরে নকশা করা minimax-এর মতো worst-case চিন্তা, যা cybersecurity কোর্সের threat modeling-এর মূল সুর; দরদাম বা নিলামেও প্রতিপক্ষের জবাব আগে ভাবা হয়।

কিন্তু বাস্তবের প্রতিপক্ষ সাধারণত zero-sum নয় (দরদামে দুজনই লাভবান হতে পারেন), তার utility অজানা, তথ্য লুকানো, আর মানুষ নিখুঁত হিসাব করে না। তখন worst-case অনুমান কখনো অতিরিক্ত ভীতু সিদ্ধান্ত দেয়। মানুষকে “প্রতিপক্ষ” হিসেবে মডেল করার নৈতিক দিক পরের AI ethics কোর্সে আসবে। মডেলটি চিন্তার হাতিয়ার, বাস্তবের হুবহু ছবি নয়।

১০ · AI-এর যুগে — AI সহকারীর লেখা খেলার search যাচাই

“Tic-tac-toe-এর জন্য alpha-beta লিখে দাও” বললে AI সহকারী কয়েক সেকেন্ডে চলনসই কোড দেবে। সমস্যা হলো, খেলার search-এর ভুলগুলো প্রায়ই চুপচাপ থাকে: প্রোগ্রাম চলে, চাল দেয়, শুধু মাঝে মাঝে ভুল চাল দেয়। AI সহকারীরা প্রায়ই যা করে:

• দৃষ্টিকোণের ভুল: utility একবার X-এর চোখে, একবার “যার চাল” তার চোখে; negamax-এ চিহ্ন উল্টাতে ভুলে যাওয়া; দুই স্তরেই max.
• Alpha-beta-র সূক্ষ্ম ভুল: লুপের ভেতরে হালনাগাদ করা α/β-র বদলে পুরোনো মান নিচে পাঠানো, >=-এর জায়গায় ভুল শর্ত, আর কাটা পড়া node-এর সীমাকে নিখুঁত মান ধরে cache-এ রাখা।
• বোর্ড নষ্ট করা: একটি list-এ চাল বসিয়ে ফেরার সময় মুছতে ভুলে যাওয়া (undo নেই), বা mutable বোর্ডকে cache-এর key করা।
• গভীরতার সীমার আগে terminal test না করা, ফলে জেতা অবস্থাকেও evaluation দিয়ে অনুমান করা।
• ভুল দাবি: “Deep Blue neural network ব্যবহার করত”, “MCTS সবসময় সেরা চাল দেয়”, “tic-tac-toe-তে প্রথমজন জেতে”, বা seed ছাড়া একবারের playout-কে প্রমাণ বলা।

AI-এর কোড হাতে পেলে — যাচাইয়ের চেকলিস্ট

• হাতে হিসাব করা একটি ছোট গাছে (যেমন অংশ ৩-এর 5, 3, 2 → 5) কোডের উত্তর মিলিয়েছি
• অনেক এলোমেলো অবস্থা বা গাছে alpha-beta আর সাধারণ minimax-এর মান তুলনা করেছি; একটিও অমিল নেই
• জানা সংখ্যা মিলিয়েছি: ২,৫৫,১৬৮টি খেলা, ৫,৪৭৮টি অবস্থা, খালি বোর্ডে ড্র, বা Nim-এর XOR নিয়ম
• utility কার চোখে, কোডে আর মন্তব্যে একই; প্রতিটি স্তরে কে MAX, কে MIN তা পরিষ্কার
• এলোমেলো অংশে (playout) seed দেওয়া আছে, আর ফল কয়েকটি seed-এ যাচাই করেছি
• ইতিহাস বা সংখ্যার দাবি (Deep Blue, AlphaGo, Shannon number) মূল উৎস বা নির্ভরযোগ্য সূত্রে মিলিয়েছি