স্প্র্যাগ-গ্রান্ডি উপপাদ্য। নিম#
ভূমিকা#
এই উপপাদ্যটি তথাকথিত ইমপার্শিয়াল (পক্ষপাতহীন) দুই-খেলোয়াড়ের গেম বর্ণনা করে, অর্থাৎ যেগুলোতে উপলব্ধ চাল এবং জয়/পরাজয় শুধুমাত্র গেমের অবস্থার উপর নির্ভর করে। অন্য কথায়, দুই খেলোয়াড়ের মধ্যে একমাত্র পার্থক্য হলো তাদের একজন প্রথমে চাল দেয়।
অতিরিক্তভাবে, আমরা ধরে নিচ্ছি গেমে পরিপূর্ণ তথ্য আছে, অর্থাৎ কোনো তথ্য খেলোয়াড়দের কাছ থেকে লুকানো নেই (তারা নিয়ম এবং সম্ভাব্য চাল জানে)।
ধরে নেওয়া হয় গেমটি সসীম, অর্থাৎ একটি নির্দিষ্ট সংখ্যক চালের পরে, একজন খেলোয়াড় একটি পরাজিত অবস্থানে পড়বে — যেখান থেকে সে অন্য অবস্থানে যেতে পারবে না। অন্যদিকে, যে খেলোয়াড় প্রতিপক্ষকে এই অবস্থানে ফেলেছে সে জিতবে। বোঝাই যায়, এই গেমে কোনো ড্র নেই।
এই ধরনের গেমকে সম্পূর্ণরূপে একটি ডিরেক্টেড অ্যাসাইক্লিক গ্রাফ দিয়ে বর্ণনা করা যায়: ভার্টেক্সগুলো হলো গেমের অবস্থা এবং এজগুলো হলো ট্রানজিশন (চাল)। কোনো আউটগোয়িং এজ নেই এমন ভার্টেক্স হলো পরাজিত ভার্টেক্স (এই ভার্টেক্স থেকে চাল দিতে বাধ্য খেলোয়াড় হারবে)।
যেহেতু কোনো ড্র নেই, আমরা সব গেম অবস্থাকে জয়ী বা পরাজিত হিসেবে শ্রেণীবদ্ধ করতে পারি। জয়ী অবস্থা হলো সেগুলো যেখান থেকে এমন একটি চাল আছে যা প্রতিপক্ষের অনিবার্য পরাজয় ঘটায়, তার সেরা প্রতিক্রিয়া সত্ত্বেও। পরাজিত অবস্থা হলো সেগুলো যেখান থেকে সব চাল প্রতিপক্ষের জন্য জয়ী অবস্থায় নিয়ে যায়। সংক্ষেপে, একটি অবস্থা জয়ী যদি অন্তত একটি ট্রানজিশন একটি পরাজিত অবস্থায় যায় এবং পরাজিত যদি কোনো ট্রানজিশন পরাজিত অবস্থায় না যায়।
আমাদের কাজ হলো প্রদত্ত গেমের অবস্থাগুলো শ্রেণীবদ্ধ করা।
এই ধরনের গেমের তত্ত্ব স্বাধীনভাবে রোল্যান্ড স্প্র্যাগ ১৯৩৫ সালে এবং প্যাট্রিক মাইকেল গ্রান্ডি ১৯৩৯ সালে তৈরি করেছিলেন।
নিম#
এই গেমটি উপরে বর্ণিত সীমাবদ্ধতাগুলো মেনে চলে। তদুপরি, যেকোনো পরিপূর্ণ-তথ্য ইমপার্শিয়াল দুই-খেলোয়াড়ের গেমকে নিম গেমে রূপান্তর করা যায়। এই গেমটি অধ্যয়ন করলে আমরা অন্য সব অনুরূপ গেম সমাধান করতে পারব, তবে সে বিষয়ে পরে আলোচনা।
ঐতিহাসিকভাবে এই গেমটি প্রাচীনকালে জনপ্রিয় ছিল। এর উৎপত্তি সম্ভবত চীনে — বা অন্তত জিয়ানশিজি গেমটি এর সাথে খুবই সাদৃশ্যপূর্ণ। ইউরোপে এর প্রাচীনতম উল্লেখ ষোড়শ শতাব্দী থেকে। চার্লস বাউটন ১৯০১ সালে এই গেমের পূর্ণ বিশ্লেষণ প্রকাশ করে এটির নামকরণ করেন।
গেমের বিবরণ#
বেশ কয়েকটি স্তূপ আছে, প্রতিটিতে কিছু পাথর। একটি চালে একজন খেলোয়াড় যেকোনো একটি স্তূপ থেকে যেকোনো ধনাত্মক সংখ্যক পাথর নিয়ে ফেলে দিতে পারে। একজন খেলোয়াড় হারে যদি সে চাল দিতে না পারে, যা ঘটে যখন সব স্তূপ খালি।
গেমের অবস্থা একটি ধনাত্মক পূর্ণ সংখ্যার মাল্টিসেট দ্বারা দ্ব্যর্থহীনভাবে বর্ণনা করা যায়। একটি চাল হলো একটি নির্বাচিত পূর্ণ সংখ্যাকে কঠোরভাবে হ্রাস করা (এটি শূন্য হলে সেটি সেট থেকে সরিয়ে ফেলা হয়)।
সমাধান#
চার্লস এল. বাউটনের সমাধানটি এরকম:
উপপাদ্য। বর্তমান খেলোয়াড়ের জয়ী কৌশল আছে যদি এবং কেবল যদি স্তূপের আকারগুলোর xor-যোগফল অশূন্য হয়। একটি ক্রম $a$-র xor-যোগফল হলো $a_1 \oplus a_2 \oplus \ldots \oplus a_n$, যেখানে $\oplus$ হলো বিটওয়াইজ এক্সক্লুসিভ অর।
প্রমাণ। প্রমাণের মূল হলো প্রতিপক্ষের জন্য সিমেট্রিক কৌশলের উপস্থিতি। আমরা দেখাব যে xor-যোগফল শূন্য এমন একটি অবস্থানে একবার থাকলে, খেলোয়াড় দীর্ঘমেয়াদে এটিকে অশূন্য করতে পারবে না — যদি সে অশূন্য xor-যোগফলবিশিষ্ট অবস্থানে যায়, প্রতিপক্ষের সবসময় একটি চাল থাকবে xor-যোগফলকে শূন্যতে ফিরিয়ে আনার।
আমরা গাণিতিক আরোহ দ্বারা উপপাদ্যটি প্রমাণ করব।
একটি খালি নিমের জন্য (যেখানে সব স্তূপ খালি অর্থাৎ মাল্টিসেট খালি) xor-যোগফল শূন্য এবং উপপাদ্যটি সত্য।
এখন ধরি আমরা একটি অ-খালি অবস্থায় আছি। আরোহ অনুমান ব্যবহার করে (এবং গেমের অচক্রাকার ধর্ম) আমরা ধরে নিচ্ছি যে বর্তমান অবস্থা থেকে পৌঁছানো সব অবস্থার জন্য উপপাদ্যটি প্রমাণিত।
তখন প্রমাণটি দুই ভাগে বিভক্ত: যদি বর্তমান অবস্থানের xor-যোগফল $s = 0$ হয়, আমাদের প্রমাণ করতে হবে যে এই অবস্থা পরাজিত, অর্থাৎ সব পৌঁছানোযোগ্য অবস্থার xor-যোগফল $t \neq 0$। যদি $s \neq 0$, আমাদের প্রমাণ করতে হবে যে $t = 0$ এমন একটি অবস্থায় যাওয়ার চাল আছে।
ধরি $s = 0$ এবং যেকোনো চাল বিবেচনা করি। এই চালটি একটি স্তূপের আকার $x$ থেকে $y$-তে কমায়। $\oplus$-র প্রাথমিক ধর্ম ব্যবহার করে, আমরা পাই
\[ t = s \oplus x \oplus y = 0 \oplus x \oplus y = x \oplus y \]যেহেতু $y < x$, $y \oplus x$ শূন্য হতে পারে না, তাই $t \neq 0$। এর অর্থ যেকোনো পৌঁছানোযোগ্য অবস্থা জয়ী (আরোহ অনুমান অনুসারে), তাই আমরা পরাজিত অবস্থানে আছি।
ধরি $s \neq 0$। $s$ সংখ্যাটির বাইনারি প্রকাশ বিবেচনা করি। ধরি $d$ হলো এর সর্বোচ্চ (সবচেয়ে বড় মানের) অশূন্য বিটের ইনডেক্স। আমাদের চাল হবে সেই স্তূপে যার আকারের $d$ নম্বর বিট সেট আছে (এটি থাকতেই হবে, অন্যথায় বিটটি $s$-এ সেট থাকত না)। আমরা এর আকার $x$ থেকে $y = x \oplus s$-এ কমাব। $d$-র চেয়ে বড় অবস্থানের সব বিট $x$ ও $y$-তে মিলে যায় এবং বিট $d$ $x$-এ সেট কিন্তু $y$-তে সেট নয়। সুতরাং, $y < x$, যা চালটি বৈধ হওয়ার জন্য প্রয়োজন। এখন আমরা পাই:
\[ t = s \oplus x \oplus y = s \oplus x \oplus (s \oplus x) = 0 \]এর অর্থ আমরা একটি পৌঁছানোযোগ্য পরাজিত অবস্থা খুঁজে পেয়েছি (আরোহ অনুমান অনুসারে) এবং বর্তমান অবস্থা জয়ী।
অনুসিদ্ধান্ত। নিমের যেকোনো অবস্থা সমতুল্য অবস্থা দিয়ে প্রতিস্থাপন করা যায় যতক্ষণ xor-যোগফল পরিবর্তন না হয়। তদুপরি, একাধিক স্তূপবিশিষ্ট নিম বিশ্লেষণ করার সময়, আমরা এটিকে $s$ আকারের একটি মাত্র স্তূপ দিয়ে প্রতিস্থাপন করতে পারি।
মিজের গেম#
একটি মিজের গেমে, গেমের লক্ষ্য বিপরীত, তাই যে খেলোয়াড় শেষ কাঠি সরায় সে হারে। দেখা যায় যে মিজের নিম গেমটি প্রায় স্ট্যান্ডার্ড নিম গেমের মতোই অপটিমালভাবে খেলা যায়। ধারণাটি হলো প্রথমে মিজের গেমটি স্ট্যান্ডার্ড গেমের মতো খেলা, কিন্তু গেমের শেষে কৌশল পরিবর্তন করা। নতুন কৌশলটি এমন পরিস্থিতিতে চালু করা হবে যেখানে পরবর্তী চালের পরে প্রতিটি স্তূপে সর্বাধিক একটি কাঠি থাকবে। স্ট্যান্ডার্ড গেমে, আমাদের এমন চাল নির্বাচন করা উচিত যেখানে একটি কাঠিবিশিষ্ট স্তূপের সংখ্যা জোড়। তবে, মিজের গেমে, আমরা এমন চাল নির্বাচন করি যেখানে একটি কাঠিবিশিষ্ট স্তূপের সংখ্যা বিজোড়। এই কৌশলটি কাজ করে কারণ কৌশল পরিবর্তনের অবস্থা সবসময় গেমে আসে, এবং এই অবস্থা একটি জয়ী অবস্থা, কারণ এতে ঠিক একটি স্তূপ আছে যেখানে একের বেশি কাঠি আছে তাই নিম যোগফল ০ নয়।
ইমপার্শিয়াল গেম এবং নিমের সমতুল্যতা (স্প্র্যাগ-গ্রান্ডি উপপাদ্য)#
এখন আমরা শিখব যেকোনো ইমপার্শিয়াল গেমের যেকোনো গেম অবস্থার জন্য নিমের একটি সংশ্লিষ্ট অবস্থা কীভাবে খুঁজে বের করতে হয়।
বৃদ্ধিসহ নিম সম্পর্কে লেমা#
আমরা নিমের নিম্নলিখিত পরিবর্তন বিবেচনা করি: আমরা একটি নির্বাচিত স্তূপে পাথর যোগ করারও অনুমতি দিই। কীভাবে এবং কখন বৃদ্ধি অনুমোদিত তার সঠিক নিয়ম আমাদের আগ্রহের নয়, তবে নিয়মগুলো আমাদের গেমকে অচক্রাকার রাখতে হবে। পরবর্তী অনুচ্ছেদে উদাহরণ গেম বিবেচনা করা হয়েছে।
লেমা। নিমে বৃদ্ধি যোগ করা জয়ী ও পরাজিত অবস্থা নির্ধারণে কোনো পরিবর্তন আনে না। অন্য কথায়, বৃদ্ধি অর্থহীন, এবং জয়ী কৌশলে আমাদের এগুলো ব্যবহার করার দরকার নেই।
প্রমাণ। ধরি একজন খেলোয়াড় একটি স্তূপে পাথর যোগ করলো। তাহলে তার প্রতিপক্ষ সহজেই তার চাল বাতিল করতে পারে — সংখ্যাটিকে আগের মানে কমিয়ে আনতে পারে। যেহেতু গেমটি অচক্রাকার, কিছুক্ষণ পর বর্তমান খেলোয়াড় আর বৃদ্ধি চাল ব্যবহার করতে পারবে না এবং সাধারণ নিম চাল দিতে বাধ্য হবে।
স্প্র্যাগ-গ্রান্ডি উপপাদ্য#
ধরি $v$ একটি দুই-খেলোয়াড়ের ইমপার্শিয়াল গেমের একটি অবস্থা এবং $v_i$ হলো এটি থেকে পৌঁছানোযোগ্য অবস্থা (যেখানে $i \in \{ 1, 2, \dots, k \} , k \ge 0$)। এই অবস্থার জন্য, আমরা $x$ আকারের একটি স্তূপবিশিষ্ট নিমের একটি সম্পূর্ণ সমতুল্য গেম নির্ধারণ করতে পারি। $x$ সংখ্যাটিকে $v$ অবস্থার গ্রান্ডি মান বা নিম-মান বলা হয়।
তদুপরি, এই সংখ্যাটি নিম্নলিখিত রিকার্সিভভাবে খুঁজে বের করা যায়:
$$ x = \text{mex}\ \{ x_1, \ldots, x_k \}, $$যেখানে $x_i$ হলো $v_i$ অবস্থার গ্রান্ডি মান এবং $\text{mex}$ (মিনিমাম এক্সক্লুড্যান্ট) ফাংশনটি হলো প্রদত্ত সেটে পাওয়া যায় না এমন ক্ষুদ্রতম অ-ঋণাত্মক পূর্ণ সংখ্যা।
গেমটিকে গ্রাফ হিসেবে দেখলে, আমরা ধাপে ধাপে আউটগোয়িং এজ নেই এমন ভার্টেক্স থেকে শুরু করে গ্রান্ডি মান হিসাব করতে পারি। গ্রান্ডি মান শূন্য হওয়ার অর্থ একটি পরাজিত অবস্থা।
প্রমাণ। আমরা আরোহ দ্বারা প্রমাণ ব্যবহার করব।
চাল নেই এমন ভার্টেক্সের জন্য, $x$-র মান একটি খালি সেটের $\text{mex}$, যা শূন্য। এটি সঠিক, কারণ খালি নিম পরাজিত।
এখন যেকোনো অন্য ভার্টেক্স $v$ বিবেচনা করি। আরোহ অনুসারে, আমরা ধরে নিচ্ছি এর পৌঁছানোযোগ্য ভার্টেক্সের সাথে সংশ্লিষ্ট $x_i$ মানগুলো ইতিমধ্যে হিসাব করা আছে।
ধরি $p = \text{mex}\ \{ x_1, \ldots, x_k \}$। তাহলে আমরা জানি যে যেকোনো পূর্ণ সংখ্যা $i \in [0, p)$ এর জন্য গ্রান্ডি মান $i$ বিশিষ্ট একটি পৌঁছানোযোগ্য ভার্টেক্স আছে। এর অর্থ $v$ বৃদ্ধিসহ নিম গেমের $p$ আকারের একটি স্তূপবিশিষ্ট অবস্থার সমতুল্য। এই ধরনের গেমে আমরা $p$-র চেয়ে ছোট প্রতিটি আকারের স্তূপে ট্রানজিশন করতে পারি এবং সম্ভবত $p$-র চেয়ে বড় আকারের স্তূপেও ট্রানজিশন করতে পারি। সুতরাং, $p$ সত্যিই বর্তমান বিবেচিত অবস্থার কাঙ্ক্ষিত গ্রান্ডি মান।
উপপাদ্যের প্রয়োগ#
সবশেষে, আমরা গেমের জয়/পরাজয় ফলাফল নির্ধারণ করার একটি অ্যালগরিদম বর্ণনা করি, যা যেকোনো ইমপার্শিয়াল দুই-খেলোয়াড়ের গেমে প্রযোজ্য।
প্রদত্ত অবস্থার গ্রান্ডি মান হিসাব করতে আপনাকে:
এই অবস্থা থেকে সব সম্ভাব্য ট্রানজিশন পেতে হবে
প্রতিটি ট্রানজিশন স্বাধীন গেমগুলোর যোগফলে নিয়ে যেতে পারে (অবক্ষয়িত ক্ষেত্রে একটি গেম)। প্রতিটি স্বাধীন গেমের গ্রান্ডি মান হিসাব করুন এবং এগুলোর xor-যোগফল নিন। শুধু একটি গেম থাকলে অবশ্যই xor কিছু করে না।
প্রতিটি ট্রানজিশনের গ্রান্ডি মান হিসাব করার পরে আমরা এই সংখ্যাগুলোর $\text{mex}$ হিসেবে অবস্থার মান খুঁজে পাই।
যদি মান শূন্য হয়, তাহলে বর্তমান অবস্থা পরাজিত, অন্যথায় এটি জয়ী।
পূর্ববর্তী অনুচ্ছেদের তুলনায়, আমরা বিবেচনায় নিচ্ছি যে সম্মিলিত গেমে ট্রানজিশন হতে পারে। আমরা এগুলোকে স্বাধীন গেমের গ্রান্ডি মানের সমান স্তূপ আকারবিশিষ্ট নিম হিসেবে বিবেচনা করি। বাউটনের উপপাদ্য অনুসারে আমরা সাধারণ নিমের মতোই এদের xor-যোগফল নিতে পারি।
গ্রান্ডি মানে প্যাটার্ন#
অনেক সময় গ্রান্ডি মান ব্যবহার করে নির্দিষ্ট সমস্যা সমাধান করার সময়, মানগুলোর টেবিল অধ্যয়ন করে প্যাটার্ন খোঁজা উপকারী হতে পারে।
অনেক গেমে, যেগুলো তাত্ত্বিক বিশ্লেষণের জন্য বেশ কঠিন মনে হতে পারে, গ্রান্ডি মানগুলো পর্যায়বৃত্তিক বা সহজে বোধগম্য আকারের হয়ে থাকে। অধিকাংশ ক্ষেত্রে পর্যবেক্ষিত প্যাটার্ন সত্য হয় এবং চাইলে আরোহ দ্বারা প্রমাণ করা যায়।
তবে, গ্রান্ডি মানে সবসময় এই ধরনের নিয়মিততা থাকে না এবং এমনকি কিছু খুব সরল গেমের জন্যও, সেই নিয়মিততা আছে কিনা এই প্রশ্নটি এখনও উন্মুক্ত (যেমন “গ্রান্ডির গেম”)।
উদাহরণ গেম#
ক্রসেস-ক্রসেস#
নিয়ম। $1 \times n$ আকারের একটি চেকারড স্ট্রিপ বিবেচনা করুন। একটি চালে, খেলোয়াড়কে একটি ক্রস বসাতে হবে, কিন্তু দুটি ক্রস পাশাপাশি (সংলগ্ন ঘরে) বসানো নিষিদ্ধ। যথারীতি, বৈধ চাল নেই এমন খেলোয়াড় হারে।
সমাধান। যখন কোনো খেলোয়াড় কোনো ঘরে ক্রস বসায়, আমরা ভাবতে পারি স্ট্রিপটি দুটি স্বাধীন অংশে বিভক্ত হচ্ছে: ক্রসের বামে এবং ডানে। এই ক্ষেত্রে, ক্রসবিশিষ্ট ঘর এবং তার বাম ও ডান প্রতিবেশী ধ্বংস হয়ে যায় — সেখানে আর কিছু বসানো যায় না। সুতরাং, যদি আমরা ঘরগুলোকে $1$ থেকে $n$ পর্যন্ত নম্বর দিই তাহলে $1 < i < n$ অবস্থানে ক্রস বসালে স্ট্রিপটি $i-2$ এবং $n-i-1$ দৈর্ঘ্যের দুটি স্ট্রিপে ভাঙে অর্থাৎ আমরা $i-2$ ও $n-i-1$ গেমের যোগফলে যাই। $1$ বা $n$ অবস্থানে ক্রস বসানোর প্রান্তিক ক্ষেত্রে, আমরা $n-2$ গেমে যাই।
সুতরাং, গ্রান্ডি মান $g(n)$ এর আকার:
$$g(n) = \text{mex} \Bigl( \{ g(n-2) \} \cup \{g(i-2) \oplus g(n-i-1) \mid 2 \leq i \leq n-1\} \Bigr) .$$এভাবে আমরা একটি $O(n^2)$ সমাধান পেয়েছি।
আসলে, $g(n)$-র পর্যায়কাল ৩৪, $n=52$ থেকে শুরু।