Search & Planningপড়তে ১১ মিনিট লাগবে

মিনিম্যাক্স অ্যালগরিদম (Minimax Algorithm)

সামনের কথা ভাবুন — যদি আপনার প্রতিপক্ষ একদম নিখুঁত চালে খেলে, তবে আপনার সেরা চাল কোনটি হবে?
scope:কোর কনসেপ্ট (মূল ধারণা)difficulty:ইন্টারমিডিয়েট (Intermediate)

দাবা খেলার গ্র্যান্ডমাস্টারদের গোপন কৌশল

একজন দাবার গ্র্যান্ডমাস্টারের খেলা খেয়াল করে দেখুন। প্রতিটি চাল দেওয়ার আগে তারা শুধু নিজেদের সেরা চালটি নিয়েই ভাবে না — তারা ভাবে যে এরপর তার প্রতিপক্ষ (opponent) কী চাল দেবে। আর সেই চালের পর তারা নিজেরা কী করবে। এবং তার উত্তরে প্রতিপক্ষ আবার কী করবে।

এটি যেন মনের ভেতরে চলা এক নীরব কথোপকথন: "আমি যদি আমার ঘোড়াটি এখানে আনি, সে আমার হাতিটি খেয়ে ফেলবে। তারপর আমি আমার সৈন্য বা পন (pawn) এগিয়ে দেব, আর তখন সে বাধ্য হয়ে তার মন্ত্রীকে (queen) পিছিয়ে নেবে..."

সহজ কথায় এটিই হলো মিনিম্যাক্স অ্যালগরিদম (minimax algorithm)। আপনি ধরে নেন যে আপনার প্রতিপক্ষ আপনার সমপর্যায়ের চালাক এবং সে সবসময় তার দিক থেকে সবচেয়ে ভালো চালটিই দেবে। এরপর আপনি সবচেয়ে খারাপ পরিস্থিতির মধ্যেও (worst case) আপনার জন্য সবচেয়ে সেরা ফলাফল আনবে — এমন চালটিই বেছে নেন।

ম্যাক্স এবং মিন-এর পালা

ব্যাপারটিকে বিপরীত লক্ষ্যের দুজন খেলোয়াড় হিসেবে চিন্তা করুন:

  • ম্যাক্স বা Max (আপনি নিজে) — যে নিজের স্কোরকে ম্যাক্সিমাইজ (maximize) বা বাড়াতে চায়।
  • মিন বা Min (আপনার প্রতিপক্ষ) — যে আপনার স্কোরকে মিনিমাইজ (minimize) বা কমাতে চায়।

তারা একে অপরের পর পর নিজেদের চাল বা টার্ন (turn) নেয়। ম্যাক্স সবচেয়ে বেশি স্কোরের চালটি বেছে নেয়। আর মিন বেছে নেয় সবচেয়ে কম স্কোরেরটি। এই অ্যালগরিদমটি গেমের সাম্ভাব্য সব ধরনের অবস্থার ওপর ভিত্তি করে একটি ট্রি (tree) বা গাছ তৈরি করে এবং নিচে থাকা লিফ (leaf)-এর ভ্যালুগুলো হিসাব করতে করতে পেছনের দিকে বা ওপরের দিকে উঠে এসে শুরুর সেরা চালটি খুঁজে বের করে।

একটি উদাহরণের মাধ্যমে দেখা যাক

ধরা যাক, আপনি আর আপনার বন্ধু মিলে নাম্বার বেছে নেওয়ার একটি সহজ খেলছেন। গেম ট্রির একদম নিচে বা লিফে চূড়ান্ত স্কোরগুলো এমন দেওয়া আছে: [3, 5, 2, 9, 1, 7, 4, 6]।

নিচ থেকে পেছনের দিকে এগোতে থাকলে:

  1. মিন-এর পালা (সবচেয়ে নিচে): মিন প্রতিটি জোড়ার ছোট নাম্বারটি নেবে: min(3,5)=3, min(2,9)=2, min(1,7)=1, min(4,6)=4
  2. ম্যাক্স-এর পালা (মাঝখানে): ম্যাক্স এবার বড় নাম্বারগুলো নেবে: max(3,2)=3, max(1,4)=4
  3. মিন-এর পালা (সবচেয়ে ওপরে): মিন এবার ছোটটি নেবে: min(3,4)=3

সুতরাং, উভয় পক্ষের নিখুঁত খেলার পরও, ম্যাক্স তার জন্য 3 স্কোরের গ্যারান্টি নিশ্চিত করতে পারে। এটি হয়তো সবচেয়ে সেরা লিফ (9) নয়, তবে একজন নিখুঁত প্রতিপক্ষের বিরুদ্ধে এটিই গ্যারান্টিযুক্ত (guaranteed) সেরা ফলাফল।

আলফা-বিটা প্রুনিং (Alpha-Beta Pruning): অদরকারি জিনিস খোঁজার দরকার নেই

সাধারণ মিনিম্যাক্স বেশ ব্যয়বহুল একটি পদ্ধতি — কারণ এটি গেমের প্রতিটি সম্ভাব্য অবস্থা খুঁজে দেখে। কিন্তু বেশিরভাগ সময়ই আপনি পুরো ব্রাঞ্চ বা শাখাকেই এড়িয়ে যেতে পারেন। যদি আপনি আগে থেকেই বুঝতে পারেন যে কোনো একটি ব্রাঞ্চ থেকে বর্তমানে পাওয়া ফলাফলের চেয়ে ভালো কিছু আসার আর সুযোগ নেই, তাহলে খামোখা সেটি খুঁজতে যাবেন কেন?

এই অপটিমাইজেশন (optimization) বা পদ্ধতিটিকেই আলফা-বিটা প্রুনিং (alpha-beta pruning) বলা হয়। এটি গেম খুঁজতে যাওয়ার এই বিশাল জায়গাকে প্রায় অর্ধেক কমিয়ে আনতে পারে, যার ফলে ফলাফলের কোনো পরিবর্তন না করেই অ্যালগরিদমটি নাটকীয়ভাবে অনেক বেশি ফাস্ট বা দ্রুত হয়ে যায়।

Minimax with Alpha-Beta Pruning

def minimax(node, depth, is_maximizing, alpha, beta):
    """আলফা-বিটা প্রুনিং-সহ মিনিম্যাক্স।"""
    # বেইস কেইস (Base case): লিফ নোড
    if isinstance(node, int):
        return node
    
    if is_maximizing:
        max_eval = float('-inf')
        for child in node:
            eval_score = minimax(child, depth + 1, False, alpha, beta)
            max_eval = max(max_eval, eval_score)
            alpha = max(alpha, eval_score)
            if beta <= alpha:
                break  # প্রুন (Prune) বা স্কিপ করুন!
        return max_eval
    else:
        min_eval = float('inf')
        for child in node:
            eval_score = minimax(child, depth + 1, True, alpha, beta)
            min_eval = min(min_eval, eval_score)
            beta = min(beta, eval_score)
            if beta <= alpha:
                break  # প্রুন (Prune) বা স্কিপ করুন!
        return min_eval


# গেম ট্রি: নেস্টেড লিস্ট = ব্রাঞ্চ, ইনটিজার = লিফের স্কোর
game_tree = [[3, 5], [2, 9]], [[1, 7], [4, 6]]


# ম্যাক্স-এর জন্য অপ্টিমাল ভ্যালু খুঁজে বের করুন
result = minimax(game_tree, 0, True, float('-inf'), float('inf'))
print(f"ম্যাক্স-এর জন্য অপ্টিমাল ভ্যালু: {result}")
Output
ম্যাক্স-এর জন্য অপ্টিমাল ভ্যালু: 3
Note: ডিপ ব্লু (Deep Blue)-এর গোপন অস্ত্র: ১৯৯৭ সালে আইবিএম (IBM)-এর ডিপ ব্লু যখন দাবার তৎকালীন বিশ্ব চ্যাম্পিয়ন গ্যারি কাসপারভকে হারিয়ে দেয়, তখন তারা এই আলফা-বিটা প্রুনিং যুক্ত মিনিম্যাক্সই ব্যবহার করেছিল — যা প্রতি সেকেন্ডে প্রায় ২০ কোটি সম্ভাব্য পজিশন বা অবস্থা যাচাই করতে পারত। এটি প্রায় ১২টি বা তারও বেশি চালের ভবিষ্যৎ আগে থেকেই দেখতে পেত। বর্তমানে স্টকফিশ (Stockfish)-এর মতো জনপ্রিয় দাবা ইঞ্জিনগুলো আরও ভালো খেলার জন্য নিউরাল নেটওয়ার্কের সাথে এই মিনিম্যাক্সকেই মিলিয়ে ব্যবহার করে থাকে।

সাধারণ গেমের বাইরেও...

মিনিম্যাক্স যে শুধু দাবার জন্যই তা কিন্তু নয়। এটি যেকোনো দুই খেলোয়াড়ের জিরো-সাম (zero-sum) ও পারফেক্ট-ইনফরমেশন (perfect-information) গেমের ক্ষেত্রেই প্রযোজ্য:

  • টিক-ট্যাক-টো (Tic-tac-toe) — মিনিম্যাক্স এটিকে পুরোপুরি সমাধান করতে পারে (নিখুঁত চালে খেললে এটি সবসময়ই ড্র হয়)।
  • চেকারস (Checkers) — ২০০৭ সালে মিনিম্যাক্সেরই একটি ভ্যারিয়েন্ট ব্যবহার করে এই গেমটিকে পুরোপুরি সলভ বা সমাধান করা হয়েছিল।
  • গো বা Go গেম — এটি আবার সাধারণ মিনিম্যাক্সের জন্য অতিরিক্ত জটিল (কারণ পুরো মহাবিশ্বে যতটা পরমাণু বা অ্যাটম আছে, এই গেমে তার চেয়েও বেশি স্টেটস বা অবস্থা তৈরি হতে পারে)। একারণেই আলফাগো (AlphaGo)-তে এর বদলে নিউরাল নেটওয়ার্ক ব্যবহার করা হয়েছিল।

তবে মিনিম্যাক্সের প্রধান অসুবিধা বা সীমাবদ্ধতা হলো: এটি ধরে নেয় যে আপনার প্রতিপক্ষ একদম নিখুঁতভাবে (perfectly) খেলবে। কিন্তু বাস্তব জীবনে মানুষ তো ভুল করেই। তাই মন্টে কার্লো ট্রি সার্চ (Monte Carlo Tree Search)-এর মতো আরও উন্নত অ্যালগরিদমগুলো প্রতিপক্ষকে নিখুঁত মনে করার বদলে, র‍্যান্ডম চাল সিমুলেট (simulate) করে এই ভুল হওয়ার বিষয়টিকেও হিসাবে ধরে নেয়।

ছোট কুইজ

মিনিম্যাক্স-এর ক্ষেত্রে, 'মিন (Min)' খেলোয়াড় কী করার চেষ্টা করে?
Challenge

পড়া চালিয়ে যান