Octal game
آکٹل گیمز دو کھلاڑیوں کے کھیلوں کی ایک کلاس ہے جس میں ٹوکن کے ڈھیر سے ٹوکن (گیم کے ٹکڑے یا پتھر) کو ہٹانا شامل ہے۔ ان کا مطالعہ مشترکہ گیم تھیوری میں نیم، کیلز اور اسی طرح کے کھیلوں کی عمومی شکل کے طور پر کیا گیا ہے۔ آکٹل گیمز غیر جانبدار ہوتے ہیں جس کا مطلب ہے کہ ایک کھلاڑی کے لیے دستیاب ہر حرکت دوسرے کھلاڑی کے لیے بھی دستیاب ہوتی ہے۔ وہ ٹوکن کی تعداد میں ایک دوسرے سے مختلف ہیں جنہیں ایک ہی حرکت میں ہٹایا جا سکتا ہے، اور (اس تعداد پر منحصر ہے) آیا اسے پورے ڈھیر کو ہٹانے، ڈھیر کے سائز کو کم کرنے، یا ڈھیر کو دو ڈھیر میں تقسیم کرنے کی اجازت ہے۔ ان قواعد کے تغیرات کو آکٹل ہندسوں کا استعمال کرتے ہوئے کوڈنگ سسٹم کے ذریعے کمپیکٹ طور پر بیان کیا جا سکتا ہے۔ گیم کی تفصیلات ایک آکٹل گیم ٹوکن کے ساتھ کھیلا جاتا ہے جسے ڈھیر میں تقسیم کیا جاتا ہے۔ دو کھلاڑی باری باری حرکت کرتے ہیں جب تک کہ کوئی حرکت ممکن نہ ہو۔ ہر اقدام میں صرف ایک ڈھیر کا انتخاب کرنا، اور یا تو ڈھیر میں موجود تمام ٹوکن کو ہٹانا، کوئی ڈھیر نہیں چھوڑنا، کچھ کو ہٹانا لیکن تمام ٹوکن کو نہیں، ایک چھوٹا ڈھیر چھوڑنا، یا کچھ ٹوکن کو ہٹانا اور بقیہ ٹوکن کو دو غیر خالی ڈھیر میں تقسیم کرنا شامل ہے۔ منتخب ڈھیر کے علاوہ دیگر ڈھیر تبدیل نہیں ہوتے ہیں۔ منتقل کرنے والا آخری کھلاڑی عام کھیل میں جیت جاتا ہے۔ یہ کھیل مسیر پلے میں بھی کھیلا جا سکتا ہے، جس میں حرکت کرنے والا آخری کھلاڑی ہار جاتا ہے۔ اس انداز میں ڈھیر کے ساتھ کھیلے جانے والے کھیل، جن میں ہر ڈھیر کے لیے اجازت شدہ چالوں کا تعین اصل ڈھیر کے سائز سے ہوتا ہے، ادب میں ٹیکنگ اینڈ بریکنگ گیمز کہلاتے ہیں۔ آکٹل گیمز لینے اور توڑنے والے گیمز کا ایک ذیلی مجموعہ ہیں جس میں اجازت شدہ چالوں کا تعین ڈھیر سے ہٹائے گئے ٹوکن کی تعداد سے کیا جاتا ہے۔ کھیل کے لیے آکٹل کوڈ کو 0 کے طور پر متعین کیا جاتا ہے۔ ڈی 1 ڈی 2 ڈی 3 ڈی 4۔، جہاں آکٹل ہندسہ ڈی این اس بات کی وضاحت کرتا ہے کہ آیا کھلاڑی کو ڈھیر سے این ٹوکن ہٹانے کے بعد صفر، ایک، یا دو ڈھیر چھوڑنے کی اجازت ہے۔ ہندسوں کا ڈی این 1 کا مجموعہ ہے اگر صفر ڈھیر چھوڑنے کی اجازت ہے، 0 بصورت دیگر ؛ 2 اگر ایک ڈھیر چھوڑنے کی اجازت ہے، 0 بصورت دیگر ؛ اور 4 اگر دو ڈھیر چھوڑنے کی اجازت ہے، 0 بصورت دیگر۔ صفر ٹوکن کو ڈھیر کے طور پر شمار نہیں کیا جاتا ہے۔ اس طرح ہندسہ ڈی این عجیب ہے اگر این ٹوکن کے ڈھیر کو مکمل طور پر ہٹا دیا جا سکتا ہے، اور دوسری صورت میں بھی۔ ڈی این میں ایک ہیپ کے نتائج کی وضاحت کا اطلاق این سے زیادہ کے ڈھیر سے این ٹوکن کو ہٹانے پر ہوتا ہے۔ ڈی این میں دو ہیپ کے نتائج کا اطلاق کم از کم این + 2 کے ڈھیر سے این ٹوکن کو ہٹانے اور بقیہ کو دو غیر خالی ڈھیر میں الگ کرنے پر ہوتا ہے۔ آکٹل گیمز اعشاریہ پوائنٹ کے بائیں طرف 4 کے ہندسے کا استعمال کرتے ہوئے، کسی بھی ٹوکن کو ہٹائے بغیر ڈھیر کو دو حصوں میں تقسیم کرنے کی اجازت دے سکتے ہیں۔ یہ گرونڈی کے کھیل کے اقدام سے ملتا جلتا ہے، جو کہ ڈھیر کو دو غیر مساوی حصوں میں تقسیم کرنا ہے۔ تاہم، معیاری آکٹل گیم نوٹیشن میں غیر مساوی حصوں کی رکاوٹ کا اظہار کرنے کی طاقت نہیں ہے۔ صرف غیر صفر ہندسوں کی محدود تعداد والے آکٹل گیمز کو محدود آکٹل گیمز کہا جاتا ہے۔ خاص آکٹل گیمز نیم مشترکہ گیم تھیوری میں سب سے بنیادی گیم نیم ہے، جس میں کسی بھی تعداد میں ٹوکن کو ڈھیر سے ہٹایا جا سکتا ہے، جس سے صفر یا ایک ڈھیر پیچھے رہ جاتا ہے۔ نیم کے لیے آکٹل کوڈ 0.333 ہے، جو شائع شدہ ادب میں ظاہر ہوتا ہے، جو دہرائے جانے والے حصے کو دہرائے جانے والے اعشاریہ کی طرح ظاہر کرتا ہے۔ تاہم، یہ سمجھنا ضروری ہے کہ دہرایا ہوا حصہ وہی کردار ادا نہیں کرتا جو آکٹل فریکشن میں ہوتا ہے، اس میں کھیل اور آکٹل فریکشن کے طور پر ان کی مساوات کے باوجود ایک جیسے نہیں ہوتے ہیں۔ Kayles کھیل Kayles عام طور پر n پنوں کی ایک قطار کے ساتھ کھیلا جاتا ہے، لیکن n کاؤنٹرز کے ڈھیر کی طرف سے ماڈل کیا جا سکتا ہے. ایک کو ڈھیر سے ایک یا دو ٹوکن ہٹانے اور بقیہ کو صفر، ایک یا دو ڈھیر میں ترتیب دینے کی اجازت ہے۔ کیلیس کے لیے آکٹل کوڈ 0.77 ہے۔ ڈاسن کا شطرنج ایک کھیل ہے جو 1938 میں کیسا کے وائلڈ روزز میں تھامس رینر ڈاسن کی طرف سے پیش کردہ شطرنج کے پہیلی سے پیدا ہوتا ہے۔ پہیلی کو اس طرح پیش کیا گیا تھا کہ اس میں پیادوں کی مخالف قطاریں شامل تھیں جنہیں ایک ہی درجہ سے الگ کیا گیا تھا۔ اگرچہ پہیلی کو غیر جانبدارانہ کھیل کے طور پر پیش نہیں کیا گیا ہے، لیکن یہ مفروضہ کہ کیپچرز لازمی ہیں اس کا مطلب یہ ہے کہ کسی کھلاڑی کے کسی بھی فائل میں منتقل ہونے کے نتیجے میں صرف اس فائل اور اس کے پڑوسیوں (اگر کوئی ہو) کو مزید غور سے ہٹا دیا جاتا ہے، جس میں مخالف کھلاڑی کو منتقل ہونا پڑتا ہے۔ اسے این ٹوکن کے ڈھیر کے طور پر ماڈلنگ کرتے ہوئے، ایک کھلاڑی ایک، دو، یا تین ٹوکن کے پورے ڈھیر کو ہٹا سکتا ہے، کسی بھی ڈھیر کو دو یا تین ٹوکن سے کم کر سکتا ہے، یا تین ٹوکن ہٹانے کے بعد ڈھیر کو دو حصوں میں تقسیم کر سکتا ہے۔ اس طرح ڈاسن کے شطرنج کی نمائندگی آکٹل کوڈ 0.137 کے ذریعے کی جاتی ہے۔ ڈاؤسن کی کیلز گیم 0.07 میں، جسے ڈاؤسن کی کیلز کہا جاتا ہے، ایک اقدام یہ ہے کہ ڈھیر سے بالکل دو ٹوکن ہٹائے جائیں اور بقیہ کو صفر، ایک یا دو ڈھیر میں تقسیم کیا جائے۔ ڈاسن کے کیلز کا نام ڈاسن کے شطرنج سے اس کی (غیر واضح) مماثلت کے لیے رکھا گیا ہے، اس میں ڈاسن کے کیلز کا n + 1 ٹوکن کا ڈھیر بالکل ڈاسن کے شطرنج کے n ٹوکن کے ڈھیر کی طرح کام کرتا ہے۔ کہا جاتا ہے کہ ڈاسن کا کیلیس ڈاسن کے شطرنج کا پہلا کزن ہے۔ نیم جیسے دوسرے اڈوں پر عمومی آکٹل گیمز، جس میں ہر حرکت ڈھیر کو صفر یا ایک ڈھیر میں تبدیل کر دیتی ہے، کو کواٹرنیری گیمز کہا جاتا ہے کیونکہ ظاہر ہونے والے صرف ہندسے 0، 1، 2 اور 3 ہوتے ہیں۔ آکٹل نوٹیشن کو ہیکساڈیسیمل گیمز کو شامل کرنے کے لیے بھی بڑھایا جا سکتا ہے، جس میں ہندسے ڈھیر کو تین حصوں میں تقسیم کرنے کی اجازت دیتے ہیں۔ درحقیقت، من مانی طور پر بڑے اڈے ممکن ہیں۔ کواٹرنیری، آکٹل اور ہیکساڈیسیمل گیمز کے تجزیے سے پتہ چلتا ہے کہ گیمز کی یہ کلاسیں ایک دوسرے سے نمایاں طور پر مختلف ہیں، اور بڑے اڈوں کے رویے کو اتنی جانچ پڑتال نہیں ملی ہے۔ نیم ترتیب اسپراگ-گرینڈی تھیوریم کا مطلب ہے کہ سائز n کا ڈھیر کسی دیئے گئے سائز کے نیم ڈھیر کے برابر ہوتا ہے، جسے عام طور پر G (n) کہا جاتا ہے۔ اس کے بعد آکٹل گیم کا تجزیہ بڑھتے ہوئے سائز کے ڈھیر کے لیے نیم ویلیوز کی ترتیب تلاش کرنے پر مشتمل ہوتا ہے۔ یہ ترتیب G (0)، G (1)، G (2). عام طور پر کھیل کی نیم ترتیب کہلاتی ہے۔ اب تک تجزیہ کیے گئے تمام محدود آکٹل گیمز نے بالآخر وقتا فوقتا ایک نیم تسلسل دکھایا ہے، اور کیا تمام محدود آکٹل گیمز بالآخر وقتا فوقتا ہوتے ہیں یہ ایک کھلا سوال ہے۔ اسے رچرڈ گائے نے مشترکہ کھیلوں کے میدان میں ایک اہم مسئلہ کے طور پر درج کیا ہے۔ کمپیوٹیشن ریکارڈز آکٹل گیم کے مکمل تجزیے کے نتیجے میں اس کی مدت اور اس کی نیم ترتیب کی ابتدائی مدت کا پتہ چلتا ہے۔ یہ آپ کے ریاضیاتی ڈراموں کے جیتنے کے طریقوں میں دکھایا گیا ہے کہ یہ ثابت کرنے کے لیے کہ ایک محدود آکٹل گیم وقتا فوقتا ہوتی ہے، نیم ترتیب کی اقدار کی صرف ایک محدود تعداد کی ضرورت ہوتی ہے، جس نے کمپیوٹر کے ساتھ کمپیوٹیشن کا دروازہ کھول دیا۔ سالوں کے دوران زیادہ سے زیادہ 3 آکٹل ہندسوں والے آکٹل گیمز کا تجزیہ کیا گیا ہے۔ 79 غیر معمولی آکٹل گیمز ہیں، جن میں سے 14 کو حل کیا گیا ہے: جیک کینین نے 1967 میں.............................................................................................................................................................................. حوالہ جات مشترکہ گیم تھیوری ریاضیاتی گیمز