গেম থিওরি

অ্যালগোরিদম গেম থিওরি ৩ (স্প্র্যাগ-গ্রান্ডি সংখ্যা)

আমরা এখন নিম-গেম কিভাবে সমাধান করতে হয় জানি, এখন আমরা গ্রান্ডি সংখ্যা দিয়ে কিছু কম্পোজিট গেম এর সমাধান করবো। একটা গেম এর কথা চিন্তা করি যেখানে $s$ টা পাথরের একটা স্তুপ(pile) আছে, প্রতিবার কোনো খেলোয়াড় ১টা বা ২টা পাথর তুলে নিতে পারে, শেষ পাথরটা যে তুলে নিবে সে জিতবে। পাথরের সংখ্যা দেখে তোমাকে বলতে হবে অপটিমাল পদ্ধতিতে খেললে প্রথম খেলোয়াড় জিততে পারবে কিনা। প্রথম পর্ব পড়ে থাকলে এটা সমাধান করা তোমার জন্য খুবই সহজ। আমাদের সুডোকোডটা হবে এরকম: [crayon-59c3796fc8310778066871/] এখন ধরো পাথরের স্তুপের সংখ্যা একটার বদলে যদি $n$ টা এবং প্রতিটা স্তুপে $s_1,s_2......s_n$ টা পাথর আছে। কোনো ...
Read More

অ্যালগোরিদম গেম থিওরি-২ (নিম গেম)

আগের পর্বে গেম থিওরি কিছু বেসিক শিখেছি, এবারের পর্বে আমরা জানবো নিম-গেম নিয়ে। নিম-গেম খুবই গুরুত্বপূর্ণ কারণ অনেক ধরণের গেমকে নিম গেম এ রূপান্তর করে ফেলা যায়। নিম-গেম এ দুইজন খেলোয়ার আর কিছু পাথরের স্তুপ(pile) থাকে। প্রতি চালে একজন খেলোয়াড় যেকোনো একটা স্তুপ থেকে এক বা একাধিক পাথর তুলে নিতে পারে। কেও চাল দিতে ব্যার্থ হলে হেরে যাবে। অর্থাৎ শেষ পাথরটা যে তুলে নিয়েছে সে গেমে জিতবে। উপরের ছবিতে ৩টা পাথরের স্তুপ দেখা যাচ্ছে, প্রথমটায় ৬টা, দ্বিতীয়টায় ৯টা এবং তৃতীয়টায় ৩টা পাথর আছে। আগের গেমগুলার মতো এখানেও প্রত্যেক খেলোয়াড় অপটিমাল পদ্ধতিতে খেলবে, কেও কোনো ভুল চাল দিবে না। তোমাকে...
Read More

অ্যালগোরিদম গেম থিওরি – ১

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