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 তাই এইখানেও অনেক ভুল জিনিস থাকতে পারে । সব সময়ই সব কিছু নেট থেকে যাচাই করে নিতে হবে ]