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