Game Theory ( Sprague Grundy Theorem )

 Sprague Grundy আসলে Nim game এর এই একটা variant . Nim Game এ কি থাকে অনেক গুলা পাইপ/বাক্স এমনসব জিনিস একটা row তে থাকে এবং তাদের মধ্যে কিছু সংখ্যক জিনিসপাতি থাকে ( কার্ড , বল এইসব হাবিজাবি ) একটা single move এ কোন player যে কোন সংখ্যক জিনিসপাতি একটা নিদিষ্ট  পাইপ/ বাক্স থেকে তুলে ফেলতে পারে । যদি কোন player কোন move এ কোন item  তুলতে না পারি তাহলে ও এই গেম হেরে যাবে । solution টা কি আমি চোখ বন্ধ করে পাইপে যা কিছু আসে এই ভ্যালু গুলারে xor করতে  থাকি  যদি Ans non zero কিছু হয় তাহলে আমার প্রথম player জিতে যাবে যদি তা না হয় তাহলে জয় লাভ করবে আমার second player . এইটা কেন হয় একটু ব্যাখ্যা করে নেই । ধরে নেই আমার কাছে ১৬টা কার্ড আছে । এইগুলা বিভিন্ন row তে আছে । ধরলাম ৪টা row তে আছে ।

• ১ নাম্বার row এ আছে ১টা কার্ড

• ২ নাম্বার row এ আছে ৩টা কার্ড

• ৩ নাম্বার row এ আছে ৫টা কার্ড

• ৭ নাম্বার row এ আছে ৭টা কার্ড

আমি যে কোন move এ যে  কোন সংখ্যক কার্ড যে কোন row থেকে তুলে নিতে পারি । আমি বলতে আসলে এইখানে যে দুই জন player খেলছেন । যখন কোন player কোন কার্ড তুলতে পারবে না তিনি হেরে যাবেন । এর solution process এ প্রতিটি row যে যত সংখ্যক কার্ড আছে তাদেরকে binary number এ represent করা হয় । তাদের প্রতিটা পজিশন এর xor value calculate করা হয় । এদের ভ্যালু হচ্ছে আমার সেই state এর Nim sum .যদি কোন state এর Nim sum non zero কোন কিছু হয় তাহলে এইটা হল winning state ( মানে এই state এ যে player আছেন তিনি optimal game খেললে জিতবেন ) আর zero থাকলে losing state ( হেরে যাবেন ) । যেমন এইখানে লক্ষ্য করি

for 1st row here is one card   -->  001
for 2nd row 3 cards so          --->  011
for 3rd                                   ->  101
And for 4th row                  ----- >111
                                    _________________
                                                  000 ( xor each position bit , if even numbers of 1 or o its o other wise its 1 )

এই অবস্থায় প্রথম player যাই দেন না কেন second player always Nim sum zero করে তার কাছে next move পাঠাবে । এতে দেখা যায় এমন কিছু থাকলে কখনই প্রথম player win করতে পারে না ।
wiki তে এর একটা proof দেখানো হইছে লিঙ্ক

এখন যদি আমাকে restriction দিয়ে দেয় যে না ভাই তুমি যা খুশী চাইলেই তুলে নিতে পারবা না । কিছু রুল থাকবে । ঐ সংখ্যক নেওয়া যাবে ( যদি যায় ) তাহলে কোন state এর Nim sum 0 থাকলেও দেখা যেতে পারে যে player restricted rule এর কারণে win করছে । তাহলে আমরা কিভাবে বুঝব যে কে জিততে যাচ্ছে । এর উত্তর নিয়ে আসে Sprague grundy theorem । এইখানে বলা হয় কোন state এর grundy value হচ্ছে সেই state থেকে যে সব state এ যাওয়া যায় তাদের ভ্যালুর মধ্যে যে সর্বনিম্ন ভ্যালুটা নেই ওটা । মানে হইল ধরি কোন state A থেকে B , C , D তিনটা state এ যাওয়া যায় যাদের grundy value হল যথাক্রমে {০,১,৪} তাহলে A state এর grundy value কত ? এইখানে A এর grundy value হবে ২ , কারণ A থেকে যাদের কাছে যাওয়া যায় তাদের কারো কাছে নেই এমন সব থেকে ছোট  ২  । কোন state এর grundy value 0 হওয়া মানে হইল এই state টা হচ্ছে হারার state . ০ বাদে যে কোন স্টেটই হচ্ছে আমার জিতার state . এইভাবে Sprague grundy solution এ আমার সবগুলা পাইপ এর grundy value বের করে Nim এর মত xor করা হয় যদি পজিটিভ কিছু থাকে তাহলে প্রথম player জিতবে নতুবা হারবে । যে কোন জিনিস বুঝার সব থেকে ভাল উপায় হল এর কোন প্রবলেম দেখা । আমরা এখন একটা basic problem দেখি ।  

প্রবলেম link এই প্রবলেম এ বলা হইছে দুই জন player খেলছে little chef আর head chef . তাদের সামনে অনেকগুলা piles আছে যেসব pile এ stone আছে । একটা single move এ একজন n^n আকারে stone কোন pile থেকে রিমুভ করতে পারে । মানে ( 1^1 ==1 , 2^2 == 4 , 3^3 == 27 , 4^4 == 256 ..... ) এমন সংখ্যক । আমাকে বলতে হবে যদি তারা optimal খেলে তাহলে কে জিতবে এবং little chef first move টা দেয় । এইখানে constrain থেকে দেখা যায় প্রতিটা pile এ highest stone থাকতে পারে 100000 মানে আমি highest 6^6 = 46656 টা stone নিতে পারি । এখন আমি কোডটা দেখি 

কোড

এইখানে আমি প্রতিটা pile এর grundy value বের করে xor করে দেখব । positive হলে little chef আর না হলে head chef জিতবে । প্রায় একই রকম একটা প্রবলেম হচ্ছে light oj 1315 - Game of Hyper Knights .
এইখানে pile এর বদলে আমাকে দাবা খেলার ঘোড়া দিয়েছে এবং তাদের মুভ restricted করে দিয়েছে । আমাকে বলতে হবে কে জিতবে Bob ভাইয়া না Alice আপু । এইখানেও base case হচ্ছে (০,০) নাম্বার পজিশন যার grundy value হচ্ছে ০ ( হারার স্টেট বলে ) । উপরের প্রসেসটা বুঝা গিয়ে থাকলে এই প্রবলেমটা এখন সবার পারা উচিত ।

যাই হোক এইটুকুই আসলে আমি জানি  Sprague Grundy  সম্পর্কে । এর জন্য আমি বিশেষ ধন্যবাদ দিতে চাই one and only halfo কে :D যার কাছ থেকে আমি এই সুন্দর জিনিসটা শিখছিলাম । এখন আর একটু নেট ঘাটাঘাটি করে সবাইকে বাকিটুকু শিখতে হবে ।

[ বিদ্রঃ আমি নিজে খুবই বাজে কোডার । আমার কোন লেখাই অন্ধ বিশ্বাসে ঠিক ধরে নেওয়া বোকামি । আমি তো নিজেকে নিজেই ভুলবাল বুঝাই :P তাই এইখানেও অনেক ভুল জিনিস থাকতে পারে । সব সময়ই সব কিছু নেট থেকে যাচাই করে নিতে হবে ] 

MINMAX ALGORITHM

Game Theory এর প্রবলেমগুলো অনেক মজার হয় । প্রথমত তা পড়তে অনেক মজার ( আপনি কোড করতে পারেন আর নাই পারেন প্রবলেম পড়ে অবশ্যই আপনি মজা পাবেন ) আর দ্বিতীয়ত অধিকাংশ ক্ষেত্রেই কোড খুব একটা বড় হয় না। Game Theory কথা আসলেই আমার কাছে অতি বিখ্যাত ভাইবোন Alice  আর Bob  এর কথা মনে পড়ে। যাদের সারাদিন তেমন কোন পড়াশোনা নাই, নতুন নতুন আজাইরা গেম আবিষ্কার করে খেলা ছাড়া। তাদের খেলার কিছু অলিখিত  Rule  আছে –                                                                                                                                                                         

       ১. তারা সব সময় Optimal খেলবে । Optimal খেলবে মানে হল কেউ কখনই কোন ভুল মুভ করবে না যাতে অপর পক্ষের কোন প্রকার লাভ হইতে পারে ।  মানে খেলার প্রাথমিক অবস্থা দেখেও আপনি বুঝে উঠতে পারেন কে জিততে যাচ্ছে ( initial state দেখে বুঝা গেলেও তারা খেলবে কারণ  খেলা ছাড়া তাদের কোন কাম কাজ নাই )

      ২. সর্বদাই Alice ( মেয়ে তো ) First Move দিবে। আমি এখন পর্যন্ত এমন কোন প্রবলেম পাইলাম না যেইখানে বেচারা Bob কে Alice First Move করতে দিছে।

এখন আসি Minmax বা Minimax Algorithm এ । নাম শুনেই বুঝা যায় একজন Maximum Result  এর চেষ্টা করবে আর অন্যজন অপরজনের এর Maximum Output কে Minimum করার চেস্টা করবে । এই ধরনের প্রবলেমগুলোকে Recursion Relation এ প্রকাশ করা গেলে  খুব সহজেই রেজাল্ট পাওয়া যায়। আমরা এইখানে চেস্টা করব সকল Condition  নিয়ে একটা Game Tree বানানোর ( প্রতি Move এর all possible result ) । একটু কঠিন হচ্ছে , আমরা একটা প্রবলেম নিয়ে আলোচনা করলেই জিনিসটা অনেক সহজ হয়ে যাবে।

Problem :::::::::

আবার সেই বিখ্যাত ভাইবোন Alice আর Bob । তারা কোন Box এ N টা বল রাখল। প্রতি Move কেউ হয় ৩টা নাহয় ৫টা না হয় ১টা বল তুলতে পারবে । মানে হল Valid Move হল ১,৩,৫  যখন কেউ তার টার্মে কোন বল তুলতে পারবে না ও হেরে যাবে অর্থাৎ যে N টা বলের মধ্যে সর্বশেষ বলটা তুলবে ও জিতে যাবে। অপরজন তাকে ফান্টা খাওয়াবে । আর অবশ্যই Alice আপু First Move টা দিবে :P 

Solution ::::::::::::                                                                                                                                        Minimax  বা এমন ধরণের problem করার সময় আমাদের প্রথম ফরজ কাজ হল সকল প্রকার Move নিয়ে Game Tree বানিয়ে ফেলা । ধরি N=6  এখন দেখি কি কি Move Possible  

এখন Alice আর Bob এর খেলার Strategy গুলো খেয়াল করি । Alice তার All possible Move এর মধ্যে থেকে সেই Move টাই করবে যার থেকে Bob এর পক্ষে কোন ভাবেই শেষ বলটা তুলে ফেলা Possible না হয়। তেমনি Bob এর ক্ষেত্রেও একই জিনিস প্রযোজ্য। আচ্ছা এখন আমরা Last Case গুলা খেয়াল করি । যদি কেউ ১,৩ বা ৫ টা বল তার টার্মে পায় তাহলে সে এক Move এই জিতে যাচ্ছে । এর মানে হল ১,৩,৫ হল জিতার state ।   এখন যে যে State থেকে এই ১,৩,৫ এ আসা হল তা অবশ্যই হবে হারার State ।  যেমন ২ অর্থাৎ যার কাছে ২ যাবে ও অবশ্যই হারবে কারণ  ২ থেকে শুধু মাত্র ১ এ যাওয়া যায় যা  বিপক্ষ খেলোয়াড় এর জন্য জিতার State মানে হল তার জন্য এইটা হারার State , এখন আবার যে যে state  থেকে হারার State এ আসা যায় তা অবশ্যই হবে জিতার state । যেমন ৩ , কারণ ৩ থেকে ২তে আসা যায় ( আপনি আবার একবার ও কিন্তু ০ করে দিতে পারেন মানে জিতে যেতে পারেন ,আমরা শুধুমাত্র বুঝার জন্য ধরছি আপনি ২ তে যাবেন ) এবং ২ হচ্ছে একটি হারার state অর্থাৎ ৩ হল জিতার state । এখন N=8 এর জন্য আমরা সকল State গুলো দেখি ।

এখন আমরা Code টা দেখি ।

কোড দেখলে দেখব যে আমরা Valid_Move নামে একটি Function রেখেছি যার কাজ হচ্ছে কোন Move Possible কিনা তা চেক করা। এখন কোন State থেকে যদি এমন কোন Move পাওয়া যায় যাতে বিপক্ষ খেলোয়াড় হেরে যাবে এমন সেই move এ যাব। অর্থাৎ এমন কোন Move পাওয়া মানে আমার জিতে যাওয়া তাই আমি true return করব । নতুবা False ।

এখন সবকিছু বুঝা হয়ে গেলে Uva 10404 প্রবলেম টা করা যেতে পারে ।

Practice Problem : 1