Poset game
مشترکہ گیم تھیوری میں، پوزیٹ گیمز حکمت عملی کے ریاضیاتی کھیل ہیں، جو نیم اور چومپ جیسے بہت سے معروف کھیلوں کو عام کرتے ہیں۔ اس طرح کے کھیلوں میں، دو کھلاڑی پوزیٹ (جزوی طور پر ترتیب شدہ سیٹ) سے آغاز کرتے ہیں، اور باری باری پوزیٹ میں ایک پوائنٹ کا انتخاب کرتے ہیں، اسے ہٹا دیتے ہیں اور تمام پوائنٹس جو زیادہ ہوتے ہیں۔ جس کھلاڑی کے پاس انتخاب کرنے کے لیے کوئی پوائنٹ نہیں بچا ہے، وہ ہار جاتا ہے۔ گیم پلے کو جزوی طور پر ترتیب شدہ سیٹ (P، <) دیا گیا ہے، آئیے P سے x کو ہٹانے سے بننے والے پوسیٹ کو ظاہر کریں۔ P پر ایک پوسیٹ گیم، جو روایتی طور پر ایلس اور باب نامی دو کھلاڑیوں کے درمیان کھیلا جاتا ہے، مندرجہ ذیل ہے: ایلس ایک پوائنٹ x bul P کا انتخاب کرتی ہے۔ اس طرح P کو Px سے تبدیل کرتی ہے، اور پھر باب کو موڑ دیتی ہے جو Px پر کھیلتا ہے، اور باری ایلس کو منتقل کرتا ہے۔ ایک کھلاڑی ہار جاتا ہے اگر اس کی باری ہو اور منتخب کرنے کے لیے کوئی پوائنٹس نہ ہوں۔ مثال کے طور پر اگر P ایک مکمل طور پر ترتیب شدہ سیٹ ہے، تو P میں گیم پلے بالکل وہی ہے جو نیم کے گیم میں سائز کے ڈھیر |P | کے ساتھ کھیلا جاتا ہے۔ کیونکہ، دونوں کھیلوں میں، ایک ایسی حرکت کا انتخاب کرنا ممکن ہے جو ایک ہی قسم کے کھیل کی طرف لے جائے جس کا سائز |P | سے چھوٹا کوئی نمبر ہو۔ اسی طرح، کل آرڈرز کے جداگانہ اتحاد کے ساتھ ایک پوزیٹ گیم نیم کے کھیل کے برابر ہے جس میں متعدد ڈھیر ہوتے ہیں جن کے سائز پوزیٹ میں زنجیروں کے برابر ہوتے ہیں۔ ہیکنبش کا ایک خاص معاملہ، جس میں تمام کنارے سبز ہوتے ہیں (کسی بھی کھلاڑی کے ذریعے کاٹے جا سکتے ہیں) اور ہر ترتیب جنگل کی شکل اختیار کرتی ہے، اسی طرح ایک پوسیٹ پر پوسیٹ گیم کے طور پر ظاہر کیا جا سکتا ہے، جس میں، ہر عنصر x کے لیے، زیادہ سے زیادہ ایک عنصر y ہوتا ہے جس کے لیے x y کا احاطہ کرتا ہے۔ اگر x y کا احاطہ کرتا ہے، تو y جنگل میں x کا پیرنٹ ہے جس پر کھیل کھیلا جاتا ہے۔ چومپ کا اظہار اسی طرح کیا جا سکتا ہے، کل آرڈرز کے پروڈکٹ پر ایک پوزیٹ گیم کے طور پر جس سے انفیمیم کو ہٹا دیا گیا ہے۔ گرونڈی ویلیو پوسیٹ گیمز غیر جانبدار کھیل ہیں، جس کا مطلب ہے کہ ایلس کے لیے دستیاب ہر حرکت باب کے لیے بھی دستیاب ہوگی اگر ایلس کو پاس کرنے کی اجازت دی جائے، اور اس کے برعکس۔ لہذا، اسپراگ-گرینڈی تھیوریم کے مطابق، پوزیٹ گیم میں ہر پوزیشن کی ایک گرینڈی ویلیو ہوتی ہے، ایک نمبر جو نیم کے کھیل میں مساوی پوزیشن کو بیان کرتا ہے۔ پوزیٹ کی گرونڈی ویلیو کا حساب سب سے کم قدرتی نمبر کے طور پر کیا جا سکتا ہے جو کسی بھی Px، x Π کی گرونڈی ویلیو نہیں ہے۔ یعنی، یہ نمبر پوزیٹ گیم میں زیادہ سے زیادہ گیم پلے کو بیان کرنے کے لیے استعمال کیا جا سکتا ہے۔ خاص طور پر، گرونڈی ویلیو غیر صفر ہوتی ہے جب کھلاڑی جس کی باری ہوتی ہے اس کی جیت کی حکمت عملی ہوتی ہے، اور صفر جب موجودہ کھلاڑی اپنے مخالف کے زیادہ سے زیادہ کھیل کے خلاف نہیں جیت سکتا ہے۔ کھیل میں جیتنے کی حکمت عملی اس پوزیشن پر منتقل ہونے پر مشتمل ہوتی ہے جس کی گرونڈی ویلیو صفر ہوتی ہے، جب بھی ممکن ہو۔ حکمت عملی چوری کرنا حکمت عملی چوری کرنے کی دلیل سے پتہ چلتا ہے کہ ہر پوزیشن کے لیے گرونڈی ویلیو غیر صفر ہے جس میں بالادستی ہے۔ کیونکہ، x کو جزوی طور پر ترتیب شدہ سیٹ P کا بالادستی مان لیں۔ اگر Px کی گرونڈی ویلیو صفر ہے، تو اوپر کے فارمولے کے مطابق P کی خود ایک غیر صفر ویلیو ہے۔ اس صورت میں، x P میں ایک جیتنے والی حرکت ہے۔ اگر، دوسری طرف، Px کی غیر صفر گرونڈی ویلیو ہے، تو Px میں ایک جیتنے والی حرکت y ہونی چاہیے، جیسے کہ (Px) y کی گرونڈی ویلیو صفر ہو۔ لیکن اس مفروضے کے مطابق کہ x ایک بالادستی ہے، x> y اور (Px) y = پائی، اس لیے جیتنے والی حرکت y بھی P میں دستیاب ہے اور پھر P کی غیر صفر گرونڈی قدر ہونی چاہیے۔ زیادہ معمولی وجوہات کی بناء پر لامحدود کے ساتھ ایک پوسیٹ کی بھی غیر صفر گرونڈی ویلیو ہوتی ہے: لامحدود کی طرف بڑھنا ہمیشہ ایک جیتنے والا اقدام ہوتا ہے۔ پیچیدگی صوابدیدی محدود پوزیٹ گیم کے فاتح کا فیصلہ کرنا پی ایس پی اے سی ای مکمل ہے۔ اس کا مطلب یہ ہے کہ جب تک کہ P = PSPACE، صوابدیدی پوزیشن گیم کی گرونڈی ویلیو کا حساب لگانا کمپیوٹیشنل طور پر مشکل ہے۔ حوالہ جات مشترکہ گیم تھیوری ریاضیاتی گیمز