আগের পর্বে গেম থিওরি কিছু বেসিক শিখেছি, এবারের পর্বে আমরা জানবো নিম-গেম নিয়ে। নিম-গেম খুবই গুরুত্বপূর্ণ কারণ অনেক ধরণের গেমকে নিম গেম এ রূপান্তর করে ফেলা যায়।

নিম-গেম এ দুইজন খেলোয়ার আর কিছু পাথরের স্তুপ(pile) থাকে। প্রতি চালে একজন খেলোয়াড় যেকোনো একটা স্তুপ থেকে এক বা একাধিক পাথর তুলে নিতে পারে। কেও চাল দিতে ব্যার্থ হলে হেরে যাবে। অর্থাৎ শেষ পাথরটা যে তুলে নিয়েছে সে গেমে জিতবে।

উপরের ছবিতে ৩টা পাথরের স্তুপ দেখা যাচ্ছে, প্রথমটায় ৬টা, দ্বিতীয়টায় ৯টা এবং তৃতীয়টায় ৩টা পাথর আছে।

আগের গেমগুলার মতো এখানেও প্রত্যেক খেলোয়াড় অপটিমাল পদ্ধতিতে খেলবে, কেও কোনো ভুল চাল দিবে না। তোমাকে কোন স্তুপে কয়টি পাথর আছে সেটা দেখে বলতে হবে প্রথম খেলোয়ার জিতবে নাকি হারবে।

এখন মনে করো $n$ টা স্তুপে যথাক্রমে $a_1, a_2…..,a_n$ টা পাথর আছে। খেলায় প্রথম খেলোয়াড় হারবে শুধুমাত্র যদি $xorsum=a_1 ⊕ a_2 ⊕ …. ⊕ a_n=0$ হয়। এখানে ⊕ দিয়ে xor অপারেটর বুঝানো হচ্ছে।

উপরের ছবির উদাহরণে $xorsum=6 ⊕ 9 ⊕ 3 = 12 !=0$ । এখানে xorsum শুন্য না, তাই অপটিমাল পদ্ধতিতে খেললে প্রথম খেলোয়াড়কে হারানো সম্ভব না।

এখন প্রশ্ন হলো এটা কেন আর কিভাবে কাজ করছে? $xorsum=0$ যদি লুজিং স্টেট হয়ে থাকে তাহলে বর্তমান খেলোয়াড় যেভাবেই চাল দিক না কেন সে গেমটাকে একটা উইনিং স্টেট এ নিয়ে যাবে।

মনে করো $n=4$ এবং স্তুপ গুলোতে পাথরের সংখ্যার সেট $\{9,7,11,5\}$। এদেরকে বাইনারিতে নিচের মত করে লিখি:

1 0 0 1 (= 9)
0 1 1 1 (= 7)
1 0 1 1 (= 11)
0 1 0 1 (= 5)

আমরা বাইনারি সংখ্যাগুলোকে একটা $৪ \times ৪$ গ্রিড হিসাবে চিন্তা করতে পারি। লক্ষ্য করো প্রতিটা কলামেই জোড় সংখ্যক $1$ আছে, তাই $xorsum=0$ হবে, এটা একটা লুজিং স্টেট। এখন বর্তমান খেলোয়াড় একটা স্তুপ বেছে নিয়ে কিছু পাথর উঠিয়ে নিলো। সে এই কাজটা যেভাবেই করুক, কোনো একটা সারির অন্তত ১টি $1$ কে $0$ তে পরিবর্তন করতে হবে। ফলে অন্তত একটা কলামে বিজোড় সংখ্যক $1$ থেকে যাবে এবং $xorsum > 0$ হয়ে যাবে।

তারমানে বর্তমান স্টেট এ $xorsum=0$ হলে তুমি যেভাবেই চাল দাও না কেনো $xorsum > 0$ হয়ে যাবে।

এখন বর্তমান স্টেট এ যদি $xorsum > 0$ হয় তাহলে দেখানো যায় যে বর্তমান খেলোয়াড়ের পক্ষে এমন চাল দেয়া সম্ভব যাতে গেমটা লুজিং স্টেট এ চলে যায়, অর্থাৎ $xorsum=0$ হয়ে যায়।

মনে করো পাথরের সংখ্যার সেট $\{5,14,9,5\}$।

0 1 0 1 =(5)
1 1 1 0 =(14)
1 0 0 1 =(9)
0 1 0 1 = (5)

বাম থেকে ২য় এবং ৩য় কলামে বিজোড় সংখ্যক $1$ আছে, তাই $xorsum > 0$ হবে। এখন আমি এমন চাল দিতে চাই যেনো xorsum=0 হয়ে যায়। এজন্য প্রথমেই সবথেকে বামের কলামটা খুজে বের করবো যেটাই বিজোড় সংখ্যা 1 আছে, এক্ষেত্রে সেটা ২য় কলাম। এবার ২য় কলামে $1$ আছে এমন একটা রো বেছে নিবো , এক্ষেত্রে সেটা হতে পারে প্রথম, দ্বিতীয় বা চতুর্থ রো। এবার সেই রো এর ২য় কলামের $1$ টাকে $0$ বানিয়ে দাও এবং অন্যান্য কলামের $0$ বা $1$ কে এমন ভাবে পরিবর্তন করো যেন প্রতিটা কলামে জোড় সংখ্যক পাথর থাকে। তাহলেই $xorsum=0$ হয়ে গেলো!

তারমানে বর্তমান স্টেট এ $xorsum > 0$ হলে বর্তমান খেলোয়াড় সহজেই এমন চাল দিতে পারবে যেনো $xorsum=0$ হয়ে যায়।

তাহলে দেখা যাচ্ছে লুজিং স্টেট ($xorsum=0$) থেকে যেভাবই চাল দেয়া হোক না কেনো শুধুমাত্র উইনিং স্টেট ($xorsum > 0$) এ যাওয়া যায়, আবার বুদ্ধিমানের মত খেললে উইনিং স্টেট ($xorsum > 0$) থেকে সবসময় লুজিং স্টেট এ যাওয়া যায় ($xorsum=0$) । তাই শুরুতে $xorsum > 0$ হলে প্রথম খেলোয়াড়কে কখনোই হারানো সম্ভব না সে যদি অপটিমাল পদ্ধতিতে খেলে।

এখন আমরা নিম গেম এর কিছু ভ্যারিয়েশন দেখি।

মিজেরা(Misere) নিম

Misere একটা ফ্রেঞ্চ শব্দ। মিজেরা নিমগেম এ যে খেলোয়ার শেষ পাথরটা তুলে নিবে সে হেরে যাবে। মিজেরা নিম এও $xorsum > 0$ উইনিং পজিশন। তবে প্রথম খেলোয়াড়কে স্ট্রাটেজি কিছুটা পরিবর্তন করতে হবে। শেষ চালে সবগুলো পাথর তুলে না নিয়ে একটা মাত্র পাথর রেখে দিতে হবে, দ্বিতীয় খেলোয়াড় তখন শেষ পাথরটা তুলতে বাধ্য হবে। তবে যদি প্রতিটা স্তুপেই ঠিক ১টা করে পাথর থাকে তখন আর xorsum দিয়ে কাজ হবে না। তখন দেখতে হবে স্তুপের সংখ্যা জোড় নাকি বেজোড়। যদি বেজোড় সংখ্যা স্তুপ থাকে এবং প্রতিটাতে ১টা করে পাথর থাকে তাহলে বর্তমান খেলোয়াড়কে হারানো সম্ভব না।

প্রাইম পাওয়ার গেম

একটা সংখ্যা $n$ দেয়া আছে। একজন খেলোয়াড় তার চালে $n$ কে কোনো একটা প্রাইম সংখ্যার পাওয়ার দিয়ে ভাগ করতে পারে। সংখ্যাটা যদি ১ হয়ে যায় তাহলে বর্তমান খেলোয়াড় জিতে যাবে।
লক্ষ্য করো যেকোনো সংখ্যা n কে কিছু প্রাইম সংখ্যারগুণফল হিসাবে লেখা যায়। যেমন $n=56700$ হলে আমরা লিখতে পারি $n=(2×2)×(3×3×3×3)×(5×5)×(7) = 2^2 \times 3^4 \times 5^2 \times 7^1$। এখন তুমি মনে করে ৪টা পাথরের স্তুপ আছে, এবং পাথরের সংখ্যার সেট $\{2,4,2,1\}$। এখন এটা নিম গেম এ পরিণত হয়েছে, তুমি যেকোনো একটা স্তুপ থেকে এক বা একাধিক পাথর তুলে নিতে পারো!

নিম্বল(Nimble)

নিম্বল গেম এ $n$ টা ঘর থাকে যাদেরকে $0$ থেকে $n-1$ দিয়ে চিহ্নিত করা হয়। প্রতিটা ঘরে এক বা একাধিক কয়েন থাকে। নিচের ছবি দেখো:

প্রতি চালে কোনো একটা ঘর থেকে একটামাত্র কয়েন সরিয়ে বামের কোনো একটা ঘরে রাখা যায়। যে চাল দিতে পারবে না সে হেরে যাবে। সবগুলো পাথর যখন ০-তম ঘরে চলে আসবে তখন আর চাল দেয়া সম্ভব হবে না।

লক্ষ্য করো ২ নম্বর ঘরে ৩টা পাথর আছে এবং প্রতিটা কয়েনকে ঠিক ২বার করে সরানো সম্ভব। আবার ১ নম্বর ঘরের প্রতিটি কয়েনকে ১বার এবং ৪ নম্বর ঘরের প্রতিটি কয়েনকে ৪ বার করে সরানো সম্ভব।

আমরা $i$-তম ঘরের প্রতিটা কয়েনকে $i$ আকারের পাথরের স্তুপ হিসাবে চিন্তা করতে পারি কারণ কয়েনটা ঠিক $i$ বার সরানো সম্ভব। তাহলে উপরের উদাহরণে পাথরের স্তুপের সেট হবে এরকম $\{1,1,2,2,2,4,4,4,4,4,4\}$ । ৬টা স্তুপের আকার ৪ কারণ ৪ নম্বর ঘরে ৬টা কয়েন আছে। এখন গেমটা সাধারণ নিমগেমে পরিণত হয়েছে!

ম্যাট্রিক্স গেম

একটা $n \times m$ আকারের গ্রীড দেয়া আছে। প্রতিটি ঘরে কিছু পাথর রাখা আছে। একজন খেলোয়াড় যেকোনো একটা সারির এক বা একাধিক কলাম থেকে কিছু পাথর তুলে নিতে পারে। প্রতি চালে অন্তত একটা পাথর তুলতেই হবে। শেষ পাথরটা যে তুলবে সে জিতে যাবে।

এই গেমটাকেও সহজে সাধারণ নিম গেম এ রূপান্তর করা যায়। প্রতিটি সারির মোট পাথরসংখ্যাকে একটা স্তুপ হিসাবে চিন্তা করতে হবে। তারপর xorsum বের করলেই কাজ শেষ।

পোকার নিম

পোকার নিম হলো একধরণের বোগাস নিম। বোগাস নিম এ পাথর শুধু তোলাই যায় না, পাথর যোগও করা যায়। পোকার নিম এর নিয়ম হলো যেকোনো স্তুপে এক বা একাধিক পাথর যোগ করা যাবে। কোনো স্তুপ এর আকার যদি শুরুতে হয় $m$ তাহলে পাথর যোগ করার পরেও আকার $m$ এর বেশি হতে পারবে না। আর গেমটা যাতে অসীম সময় ধরে না চলে সে জন্য কোনো খেলোয়াড় $k$ বার এর বেশি পাথর যোগ করতে পারবে না।

এই গেম এ যদি প্রথম খেলোয়াড় উইনিং স্টেট এ থাকে ($xorsum > 0$) তাহলে ২য় খেলোয়াড় যখন কিছু পাথর যোগ করবে, প্রথম খেলোয়াড় পাথরগুলো সরিয়ে ফেলে গেমটাকে আবার এই স্টেট এ নিয়ে আসবে! তাই সাধারণ নিম এর মতই $xorsum$ দেখে বলে দেয়া যায় গেম এ কে জিতবে।

পরের পর্বে আমরা আরো কিছু ভ্যারিয়েশন দেখবো এবং গ্রানডি সংখ্যা নিয়ে জানবো। এখন লাইটওজে তে এই সমস্যাগুলো সমাধান করার চেষ্টা করো। নিম এর আরো কিছু ভ্যারিয়েশন পাবে এখানে।