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

১. গেমের বোর্ড, চাল ইত্যাদি সম্পর্কে পূর্নাঙ্গ তথ্য আমাদের কাছে আছে, প্রতিপক্ষ কি অবস্থায় আছে সেটাও আমরা জানি।
২. খেলায় কোনো ভাগ্যের সহায়তা দরকার হয় না।
৩. খেলা শেষে কেও একজন জিতবে বা হারবে।
৪. খেলায় দুইজন মাত্র খেলোয়াড় থাকবে, প্রথম ও দ্বিতীয় খেলোয়াড় পালাবদল করে চাল দিতে থাকবে।
৫. দুইজন খেলোয়াড়ই খেলার যেকোনো সময় সবথেকে সেরা চালটি দিবে, কেও কোনো ভুল চাল দিবে না। কোনো খেলোয়াড়ের জয়ের সম্ভাবনা থাকলে সে অবশ্যই জিতবে, সম্ভাবনা না থাকলে প্রতিপক্ষের ভুলে সে কখনো জিততে পারবে না। এককথায়, প্রতিটা খেলোয়াড় সবসময় ‘অপটিমাল’ চালটি দিবে।

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

এই ধরনের খেলায় একদম শুরুতে বা খেলার মাঝে খেলার নিয়মগুলো দেখে এবং দুই খেলোয়াড়ের বর্তমান অবস্থা দেখেই বলে দেয়া যায় যে দুইজনই অপটিমাল চাল দিলে কে খেলায় জিতবে। বাস্তবে এ ধরণের খেলা বোরিং মনে হলেও গেম থিওরির বাস্তব জীবনে অনেক ব্যবহার আছে, অর্থনীতি, রাজনীতি, জীববিজ্ঞান ইত্যাদিতে গেম থিওরি অনেক ব্যবহার হয়, তবে এই টিউটোরিয়ালে আমরা গেম থিওরির একটা ছোটো সাবসেট ‘অ্যালগরিদম গেম’ নিয়ে জানবো।

ছোটোবেলায় টিভিতে ম্যাগাজিন অনুষ্ঠানে একটা খেলা দেখেছিলাম, টেবিলে কিছু মার্বেল রাখা থাকে, একজন দর্শককে স্টেজে নিয়ে আসা হয়। দর্শকের সাথে উপস্থাপক একটা খেলা খেলে এরকম, প্রথম চালে দর্শক বা ১ম খেলোয়াড় ২টা, ৩টা বা ৫টা মার্বেল তুলে নিতে পারবে, পরের চালে উপস্থাপক বা ২য় খেলোয়াড় ২, ৩ বা ৫টা মার্বেল তুলে নিতে পারবে, এরপর দর্শক আবার একই ভাবে মার্বেল তুলবে। এভাবে চলতে থাকবে যতক্ষণ না কারো পক্ষে আর চাল দেয়া সম্ভব না হয়। শেষবার যে মার্বেলগুলো তুলেছে সে খেলাটা জিতে যাবে।

অনুষ্ঠানে দেখা যেত একের পর এক দর্শক আসছে আর হেরে যাচ্ছে, কোনোভাবেই উপস্থাপককে হারানো সম্ভব হচ্ছে না। আমরা এখন খেলাটাকে বিশ্লেষণ করলেই বুঝে যাবো কেন তাকে হারানো সম্ভব হয় নি সবথেকে বুদ্ধিমান দর্শকের পক্ষেও।

এই খেলায় খেলোয়াররা কোনো সময় কি অবস্থানে আছে সেটা জানার জন্য আমাদের দুইটা তথ্য দরকার, বর্তমানে কয়টা মার্বেল আছে, এবং কার চাল দেয়ার পালা। যদি ৫টা মার্বেল থাকে তাহলে এখন যে খেলোয়াড়ের চাল দেয়ার পালা সে একটা ‘উইনিং পজিশন’ বা ‘বিজয়ী অবস্থা’ তে চলে গিয়েছে, সে কোনো ভুল না করলে তাকে আর হারানো সম্ভব না, ৫টা মার্বেল তুলে নিয়ে সে খেলাটা শেষ করে দিবে। কিন্তু টেবিলে যদি ১টা বা ০টা মার্বেল থাকে তাহলে যে খেলোয়াড়ের চাল দেবার পালা সে ‘লুজিং পজিশন’ বা ‘পরাজিত অবস্থা’ য় চলে গিয়েছে। আমরা এখন দেখাবো যে টেবিলে মার্বেলের সংখ্যা যতই হোক না কেন, প্রথম খেলোয়ার অর্থাৎ যে এখন চাল দিবে পরাজিত অবস্থা না বিজয়ী অবস্থায় আছে আগেই জেনে যাওয়া সম্ভব। আমরা ধরে নিচ্ছি কোনো খেলোয়ারই ভুল চাল দিবে না।

মনে করি টেবিলে মার্বেল আছে $n$ টা।

৩টা জিনিস আমাদের মাথায় রাখতে হবে:

১. যেসব অবস্থা থেকে আর কোনো চাল দেয়া সম্ভব না সেগুলো পরাজিত অবস্থা বা লুজিং পজিশন। যেমন এই খেলায় $n=1$ এবং $n=0$ হলো লুজিং পজিশন। এগুলোকে টার্মিনাল পজিশন বলা হয় কারণ এই অবস্থা থেকে আর কোনো চাল দেয়া সম্ভব না।

২. যদি আমরা টার্মিনাল পজিশনে না থাকি তাহলে দেখতে হবে কোনো চাল দিয়ে প্রতিপক্ষকে একটা লুজিং পজিশনে ফেলে দেয়া যায় নাকি। যদি যায় তাহলে বর্তমান খেলোয়ার উইনিং পজিশন এ আছে। যেমন $n=5$ হলে আমি চাইলে ২, ৩ বা ৫টি মার্বেল তুলে নিয়ে টেবিলে ৫-২=৩টি অথবা ৫ – ৩ = ২টি অথবা ৫ – ৫ = ০ টি মার্বেল রেখে দিতে পারি। আমরা আগেই জানি $n=0$ একটা লুজিং পজিশন যেখান থেকে কোনো খেলোয়াড়ের পক্ষে জেতা সম্ভব না। যেহেতু টেবিলে ৫টা মার্বেল থাকলে প্রতিপক্ষকে লুজিং পজিশনে নিয়ে যাওয়া সম্ভব হচ্ছে, $n=5$ একটা উইনিং পজিশন, বর্তমান খেলোয়াড় কোনো ভুল না করলে তাকে এই অবস্থা থেকে কিছুতেই হারানো সম্ভব না।

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

এখন আমরা সহজেই যে কোনো n এর জন্য বর্তমান খেলোয়াড় কি অবস্থায় আছে বের করে ফেলতে পারি নিচের কোড দিয়ে:

আমরা প্রতিটা $n$ এর জন্য নিচের মত আউটপুট পাবো:

০ মানে হলো লুজিং পজিশন, ১ মানে উইনিং। এখান থেকে স্পষ্ট যে $n=15$ এর জন্য বর্তমান খেলোয়াড় কখনো জিততে পারবে না। ১৫টা মার্বেল থেকে ২, ৩ বা ৫টা মার্বেল তুলে আমরা ১৩, ১২ বা ১০টা মার্বেল রেখে দিতে পারি, কিন্তু টেবিল থেকে দেখা যাচ্ছে সবগুলোই উইনিং পজিশন, তাই বর্তমান অবস্থা থেকে জেতা সম্ভব না। টিভির সেই অনুষ্ঠানে যদি উপস্থাপক ১৫টি মার্বেল নিয়ে দর্শককে প্রথম খেলোয়াড় বানিয়ে খেলা শুরু করে এবং সে যদি বুদ্ধিমান হয় তাহলে তাকে হারানো অসম্ভব!

আমি নিশ্চিত এখন তোমরা বুঝে গিয়েছো কিভাবে এধরণের সমস্যা সমাধান করতে হয়। চিন্তা করার মতো কিছু সমস্যা দিলাম, সবগুলোই উপরের সমস্যাটার মতো:

১. এলিস আর বব একটা খেলা খেলছে, তাদের কাছে একটা সংখ্যা আছে $p=1$। প্রতি চালে একজন খেলোয়ার $p$ এর সাথে ২ থেকে ৯ এর ভিতর একটা সংখ্যা গুণ করতে পারে। গুণ করার পর সংখ্যাটা $x$ এর থেকে বড় হয়ে গেলে সে জিতে যাবে। $x$ এর মান দেয়া আছে, এলিস সবসময় প্রথম চাল দেয়। খেলায় কে জিতবে?(UVA 847)

২. UVA 11489

৩. আরেকটু কঠিন সমস্যা সমাধান করতে চাইলে UVA 10891

পরের পর্বে অ্যালগোরিদম গেম এর সবথেকে গুরুত্বপূর্ণ বিষয় “নিম গেম” নিয়ে আলোচনা করবো।

রেফারেন্স:

https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/