Dynamic Programming এর মাধ্যমে Game Theory Problems গাইড ও নোট

Game Theory এমন একটি শাখা যা সিদ্ধান্ত গ্রহণের পদ্ধতিগুলি বিশ্লেষণ করে, যেখানে প্রতিটি খেলোয়াড়ের সিদ্ধান্ত অন্য খেলোয়াড়দের সিদ্ধান্তের উপর নির্ভর করে। এটি সাধারণত competitive বা strategic interactions এর মধ্যে ব্যবহৃত হয়। অনেক গেম থিওরি সমস্যা Dynamic Programming (DP) এর মাধ্যমে সমাধান করা যেতে পারে, বিশেষত যখন সমস্যাগুলিতে optimal substructure এবং overlapping subproblems থাকে।

এখানে, আমরা Dynamic Programming এর মাধ্যমে দুটি জনপ্রিয় গেম থিওরি সমস্যা সমাধান করব:

1. Nim Game (পাথ সমাধান)
2. Coin Change Problem (যেখানে খেলা খেলা হয়)

1. Nim Game

Nim Game হল একটি জনপ্রিয় গেম থিওরি সমস্যা যেখানে কিছু পাইলস (pile) থাকে এবং প্রতিটি পাইলসে কিছু সংখ্যা থাকে। দুটি খেলোয়াড়ের মধ্যে পালাক্রমে খেলাটি চলে। প্রতিটি খেলোয়াড় একটি পাইলস থেকে ১ বা তার বেশি উপাদান তুলে নেয়। যে খেলোয়াড় শেষ উপাদানটি তুলে নেবে, সে বিজয়ী হবে।

Objective: একটি খেলোয়াড় যদি সঠিকভাবে খেলতে পারে, তবে তাকে নিশ্চিতভাবে জয়ী হতে হবে। এটি Nim-Sum নামক একটি কৌশলের উপর ভিত্তি করে কাজ করে। যদি Nim-Sum (একই বিটের XOR যোগফল) 0 না হয়, তবে প্রথম খেলোয়াড়ের জয় নিশ্চিত।

1.1. Nim Game Problem Statement

• আপনি n পাইলস পাবেন এবং প্রতিটি পাইলসে কিছু উপাদান থাকবে।
• দুটি খেলোয়াড় পালাক্রমে পাইলস থেকে এক বা তার বেশি উপাদান তুলে নেবে।
• যে খেলোয়াড় শেষ উপাদানটি তুলে নেবে, সে বিজয়ী হবে।

1.2. Dynamic Programming Approach for Nim Game

Nim Game এর Dynamic Programming সমাধান একটি dp array তৈরি করে যেখানে dp[i] এইভাবে থাকবে:

• True: যদি খেলা খেলতে শুরু করার পর প্রথম খেলোয়াড় বিজয়ী হয়।
• False: যদি খেলা খেলতে শুরু করার পর প্রথম খেলোয়াড় হারবে।

1.3. Nim Game Implementation in Java

public class NimGame {

    // Function to determine if the first player wins or not
    public boolean canWinNim(int n) {
        // If n is divisible by 4, first player will lose if second player plays optimally
        return n % 4 != 0;
    }

    public static void main(String[] args) {
        NimGame nimGame = new NimGame();
        
        // Example: Number of piles
        int n = 7; // Example input
        
        if (nimGame.canWinNim(n)) {
            System.out.println("First player wins!");
        } else {
            System.out.println("Second player wins!");
        }
    }
}

1.4. Explanation:

• Nim-Sum এর ভিত্তিতে, যখন n % 4 == 0 হয়, তখন দ্বিতীয় খেলোয়াড় সর্বদা প্রথম খেলোয়াড়কে হারাবে যদি সে সঠিকভাবে খেলে। অন্যথায়, প্রথম খেলোয়াড়ের জয় নিশ্চিত।
• এই সমস্যার সমাধানটি O(1) টাইম কমপ্লেক্সিটিতে কাজ করে, কারণ আমাদের শুধুমাত্র সংখ্যার ভাগফল বের করতে হয়।

2. Coin Change Problem

Coin Change Problem একটি গেম থিওরি সমস্যা হতে পারে যেখানে আপনার কিছু মুদ্রা (coins) আছে এবং আপনাকে নির্দিষ্ট একটি পরিমাণ অর্থ (target amount) গঠন করতে হবে। এখানে আমাদের কাজ হল, কিছু মুদ্রা ব্যবহার করে সবচেয়ে কম সংখ্যক মুদ্রা দিয়ে লক্ষ্য পরিমাণটি তৈরি করা।

2.1. Problem Definition:

• আপনি কিছু মুদ্রা পাবেন যেগুলির মান দেওয়া হবে।
• আপনাকে একটি লক্ষ্য পরিমাণ (target amount) গঠন করতে হবে, এবং গঠন করতে ব্যবহৃত মুদ্রাগুলির সংখ্যা সর্বনিম্ন হবে এমন পথ খুঁজতে হবে।

2.2. Dynamic Programming Approach for Coin Change

Coin Change সমস্যাটি একটি unbounded knapsack problem হিসাবে সমাধান করা যেতে পারে। এখানে DP টেবিল তৈরি করা হয়, যেখানে dp[i] হল লক্ষ্য পরিমাণ i তৈরি করার জন্য মুদ্রার সংখ্যা।

1. Subproblem: dp[i] হতে হবে মুদ্রা ব্যবহার করে লক্ষ্য পরিমাণ i তৈরি করতে সর্বনিম্ন মুদ্রার সংখ্যা।
2. Recurrence: $$dp[i] = \min(dp[i], dp[i - coin] + 1)$$ যেখানে coin হল উপলব্ধ মুদ্রাগুলির মধ্যে একটি।

2.3. Coin Change Problem Implementation in Java

public class CoinChange {

    // Function to find the minimum number of coins to make the target amount
    public int coinChange(int[] coins, int amount) {
        // Initialize dp array with maximum value (amount + 1)
        int[] dp = new int[amount + 1];
        dp[0] = 0; // No coins needed to make amount 0
        
        // Fill the dp array with maximum value
        for (int i = 1; i <= amount; i++) {
            dp[i] = amount + 1;
        }

        // Iterate through each coin and compute minimum coins for each amount
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }

        // If dp[amount] is still amount + 1, no solution exists
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        CoinChange coinChange = new CoinChange();
        
        // Example coins and target amount
        int[] coins = {1, 2, 5};
        int amount = 11;
        
        System.out.println("Minimum coins needed: " + coinChange.coinChange(coins, amount));  // Output: 3
    }
}

2.4. Explanation:

• dp[i] টেবিলের মধ্যে আমরা প্রতিটি পরিমাণের জন্য মুদ্রার সংখ্যা হিসাব করি।
• যদি dp[amount] এর মান amount + 1 থাকে, তাহলে তা মানে হল যে, লক্ষ্যমাত্রের জন্য কোনও সমাধান পাওয়া যায়নি (অর্থাৎ মুদ্রাগুলি যথেষ্ট নয়)।
• অন্যথায়, dp[amount] হল প্রয়োজনীয় মুদ্রার সংখ্যা।

3. Time and Space Complexity

• Nim Game:
  • Time Complexity: O(1), কারণ আমরা কেবল একবার n % 4 অপারেশন করি।
  • Space Complexity: O(1), কোনও অতিরিক্ত স্টোরেজ বা মেমরি প্রয়োজন হয় না।
• Coin Change Problem:
  • Time Complexity: O(n * m), যেখানে n হল লক্ষ্য পরিমাণ এবং m হল মুদ্রার সংখ্যা।
  • Space Complexity: O(n), যেখানে n হল লক্ষ্য পরিমাণ, কারণ আমরা একটি 1D DP অ্যারে ব্যবহার করি।

সারাংশ

Game Theory সমস্যা সমাধানে Dynamic Programming একটি কার্যকর কৌশল। এই গাইডে, আমরা দুটি জনপ্রিয় গেম থিওরি সমস্যা সমাধান করেছি:

1. Nim Game: এটি একটি কৌশল নির্ভর গেম যেখানে Nim-Sum ব্যবহার করে বিজয়ী খেলোয়াড় নির্ধারণ করা হয়।
2. Coin Change Problem: এটি একটি অপ্টিমাইজেশন সমস্যা যেখানে সবচেয়ে কম মুদ্রা ব্যবহার করে লক্ষ্য পরিমাণ তৈরি করতে হয়।

Dynamic Programming এর সাহায্যে এই ধরনের সমস্যা গুলি উপযুক্তভাবে এবং কার্যকরভাবে সমাধান করা যায়, বিশেষত যখন একটি সমস্যা অনেক পুনরাবৃত্তি সাব-সমস্যা তৈরি করে।