Green Hackenbush
এই পর্বটি পড়ার আগে ব্যাসিক গেম থিওরি শিখা জরুরী। ব্যাসিক গেম থিওরি শিখতে নিচের পর্বগুলো পড়তে হবে।
মনে করি, আমাকে অনেকগুলো বাঁশ গাছ দেয়া আছে। প্রতিটি গাছের উচ্চতা h[i] একক। এখন, দুইজন প্লেয়ার যেকোন একটি বাঁশ গাছের যেকোন জায়গায় কাটতে পারবে। যে প্লেয়ার শেষ গাছের শেষ এজটি কাটবে সে জিতবে।
৩য় গাছের ১ম এজ কাটলে উপরে দুইটি এজ সম্পূর্ণ অক্ষত থাকলেও পরবর্তীতে ওই এজগুলো আর কাটা যাবে না। কারণ সেটি গাছের মূল থেকে বিচ্ছিন্ন!
একটু ভালো করে লক্ষ করলে দেখবে এটি সিম্পল একটি নিম এর প্রব্লেম। নিমে যেরকম অনেকগুলো পাথরের স্তুপ দেয়া আছে। প্রতি চালে একজন প্লেয়ার যেকোন স্তুপ থেকে যেকোন সংখ্যক পাথর উঠাতে পারে।
তাহলে, এই প্রব্লেমের সমাধানও একই। প্রতিটি বাঁশ গাছের উচ্চতার এক্সর করতে হবে। এক্সর = ০ হলে, ২য় প্লেয়ার জিতবে। অন্যথায়, প্রথম প্লেয়ার জিতবে।
এখন বিপত্তি বাধবে যদি গাছগুলো বাঁশগাছ না হয়😜
নিচের ছবিটি লক্ষ কর।
এরকম হলে প্রব্লেমটির সলুশন কেমন হবে?
এই ক্ষেত্রে, আমরা Colon Principle ব্যাবহার করে প্রব্লেমটিকে আবারও নিম প্রব্লেমে কনভার্ট করতে পারি।
Colon Principle: এই নীতি, আমাদের বলে যখন কোন ভার্টেক্স থেকে একাধিক ব্রাঞ্চ বের হয় তখন সবগুলো ব্রাঞ্চ এর উচ্চতার এক্সর এর সমান উচ্চতাবিশিষ্ট একটি সিম্পল পাথ দ্বারা আমরা সবগুলো ব্রাঞ্চ কে রিপ্লেস করে দিতে পারি।
তাহলে উপরের প্রব্লেমটির সরলীকৃত রূপ হবে অনেকটি নিচের প্রব্লেমের মতো।
দুটি চিত্রে, আয়তাকার চিহ্ন দিয়ে সেই ভার্টেক্সকে বুঝানো হয়েছে যেখান থেকে একাধিক পাথ বের হয়েছিলো।
এখন, তাহলে সহজেই নিম ব্যাবহার করে প্রব্লেমটি সলভ করা যাবে।
এখন, গাছগুলো যদি বাস্তব জগতের গাছ এর মতো না হয়? অর্থাৎ, গাছ এ যদি লুপ থাকে! তাহলে কী হবে?
এখন, আমরা এটিকে সিপ্লিপাই করতে পারি Fusion Principle অনুসারে।
Fusion Principle: এই নীতি অনুসারে, একটা সাইকেলের দৈর্ঘ্য যতো, সাইকেলের শুরুর নোডে ততোগুলো ১ একক দৈর্ঘ্যের এজ যোগ করে সাইকেল টা কে রিমুভ করা যায়। শুরুর নোড ব্যাতীত অন্য কোন নোড থেকে কোন ব্রাঞ্চ বের হলে সেটি হুবহু সাইকেলের শুরুর নোডে এসে বসে যাবে।
এখন, উপরের প্রব্লেমের প্রথম সাইকেল রিমুভ করলে যা আসবেঃ
এখন, ২য় সাইকেল রিমুভ করলে যা আসবেঃ
এবার, আমরা কোলন নীতি অনুসারে ব্রাঞ্চগুলো রিমুভ করতে পারি। এরপর, প্রব্লেমটি পুরোপুরিভাবে নিম প্রব্লেমে রূপান্তরিত হলো।
এই ধরনের প্রব্লেমই Green Hackenbush প্রব্লেম নামে পরিচিত।
Suggested Problem For This Topic: Game of CS
Happy Coding😊
Comments
Post a Comment