Hackenbush
ہیکنبش ایک دو کھلاڑیوں کا کھیل ہے جسے ریاضی دان جان ہارٹن کونوے نے ایجاد کیا تھا۔ اسے رنگین لائن کے حصوں کی کسی بھی ترتیب پر کھیلا جا سکتا ہے جو ایک دوسرے سے ان کے اختتامی نکات اور "گراؤنڈ" لائن سے جڑے ہوئے ہیں۔ گیم پلے کا آغاز کھلاڑیوں کے "گراؤنڈ" لائن کھینچنے سے ہوتا ہے (روایتی طور پر، لیکن ضروری نہیں کہ کاغذ یا دوسرے کھیل کے علاقے کے نچلے حصے میں ایک افقی لائن ہو) اور کئی لائن سیگمنٹ جیسے کہ ہر لائن کا حصہ گراؤنڈ سے جڑا ہو، یا تو براہ راست ایک اختتامی نقطہ پر، یا بالواسطہ طور پر، اختتامی نکات سے جڑے دوسرے حصوں کی زنجیر کے ذریعے۔ کسی بھی تعداد میں حصے ایک مقام پر مل سکتے ہیں اور اس طرح زمین پر جانے کے لیے متعدد راستے ہو سکتے ہیں۔ اپنی باری پر، ایک کھلاڑی اپنی پسند کے کسی بھی لائن سیگمنٹ کو "کاٹ" (مٹا دیتا ہے)۔ ہر لائن کا حصہ اب کسی بھی راستے "فالس" سے زمین سے نہیں جڑا ہوا ہے (یعنی مٹ جاتا ہے)۔ مشترکہ گیم تھیوری کے نارمل پلے کنونشن کے مطابق، پہلا کھلاڑی جو حرکت کرنے سے قاصر ہو وہ ہار جاتا ہے۔ ہیکنبش بورڈ محدود طور پر بہت سے ("محدود بورڈ" کے معاملے میں) یا لامحدود طور پر بہت سے ("لامحدود بورڈ" کے معاملے میں) لائن سیگمنٹ پر مشتمل ہو سکتے ہیں۔ لائن سیگمنٹ کی لامحدود تعداد کا وجود گیم تھیوری کے اس مفروضے کی خلاف ورزی نہیں کرتا ہے کہ گیم کو ایک محدود وقت میں ختم کیا جا سکتا ہے، بشرطیکہ صرف محدود طور پر بہت سے لائن سیگمنٹ براہ راست زمین کو "چھو" رہے ہوں۔ ایک لامحدود بورڈ پر، بورڈ کی ترتیب کی بنیاد پر کھیل ہمیشہ کے لیے جاری رہ سکتا ہے، یہ فرض کرتے ہوئے کہ زمین کو چھونے والے لامحدود پوائنٹس ہیں۔ متغیرات ہیکنبش کے اصل لوک داستانوں کے ورژن میں، کسی بھی کھلاڑی کو کسی بھی کنارے کو کاٹنے کی اجازت ہے: چونکہ یہ ایک غیر جانبدار کھیل ہے اس لیے اسپراگ-گرینڈی تھیوریم کا استعمال کرتے ہوئے مکمل تجزیہ دینا نسبتا سیدھا ہے۔ اس طرح مشترکہ گیم تھیوری میں دلچسپی کے ہیکنبش کے ورژن زیادہ پیچیدہ متعصبانہ کھیل ہیں، جس کا مطلب ہے کہ ایک کھلاڑی کے لیے دستیاب اختیارات (حرکتیں) لازمی طور پر دوسرے کھلاڑی کے لیے دستیاب نہیں ہوں گے اگر اسی پوزیشن کو دیکھتے ہوئے حرکت کرنے کی باری ان کی ہو۔ یہ دو طریقوں میں سے ایک میں حاصل کیا جاتا ہے: اصل ہیکنبش: تمام لائن کے حصے ایک ہی رنگ کے ہوتے ہیں اور دونوں میں سے کوئی بھی کھلاڑی اسے کاٹ سکتا ہے۔ اس کا مطلب ہے کہ ادائیگی متناسب ہوتی ہے اور ہر کھلاڑی کے پاس بورڈ پر پوزیشن کی بنیاد پر ایک جیسے آپریشن ہوتے ہیں (اس صورت میں ڈرائنگ کا ڈھانچہ) بلیو ریڈ ہیکنبش: ہر لائن کا حصہ سرخ یا نیلے رنگ کا ہوتا ہے۔ ایک کھلاڑی (عام طور پر پہلا، یا بائیں، کھلاڑی) کو صرف نیلی لکیر کے حصوں کو کاٹنے کی اجازت ہے، جبکہ دوسرے کھلاڑی (عام طور پر دوسرا، یا دائیں، کھلاڑی) کو صرف سرخ لکیر کے حصوں کو کاٹنے کی اجازت ہے۔ بلیو-ریڈ-گرین ہیکنبش: ہر لائن کا حصہ سرخ، نیلے یا سبز رنگ کا ہوتا ہے۔ قواعد وہی ہیں جو بلیو ریڈ ہیکنبش کے لیے ہیں، اس اضافی شرط کے ساتھ کہ گرین لائن کے حصوں کو کوئی بھی کھلاڑی کاٹ سکتا ہے۔ بلیو ریڈ ہیکنبش محض بلیو ریڈ گرین ہیکنبش کا ایک خاص معاملہ ہے، لیکن یہ الگ سے نوٹ کرنے کے قابل ہے، کیونکہ اس کا تجزیہ اکثر بہت آسان ہوتا ہے۔ اس کی وجہ یہ ہے کہ بلیو ریڈ ہیکنبش ایک نام نہاد کولڈ گیم ہے، جس کا مطلب ہے، بنیادی طور پر، کہ پہلی حرکت کرنا کبھی بھی فائدہ مند نہیں ہو سکتا۔ تجزیہ ہیکنبش کو اکثر مشترکہ گیم تھیوری میں تعریفوں اور تصورات کو ظاہر کرنے کے لیے ایک مثال کے طور پر استعمال کیا گیا ہے، جس کا آغاز میدان کے کچھ بانیوں کی کتابوں آن نمبرز اینڈ گیمز اینڈ وننگ ویز فار یور میتھمیٹیکل پلےز میں کیا گیا ہے۔ خاص طور پر بلیو ریڈ ہیکنبش کو حقیقی نمبروں کی تعمیر کے لیے استعمال کیا جا سکتا ہے: محدود بلیو ریڈ ہیکنبش بورڈ ڈائیڈک عقلی نمبروں کی تعمیر کر سکتے ہیں، جبکہ لامحدود بلیو ریڈ ہیکنبش بورڈ کی اقدار حقیقی نمبروں، آرڈینلز اور بہت سی عمومی اقدار کے لیے ذمہ دار ہیں جو نہ تو ہیں۔ بلیو ریڈ گرین ہیکنبش اضافی گیمز کی تعمیر کی اجازت دیتا ہے جن کی اقدار حقیقی اعداد نہیں ہیں، جیسے اسٹار اور دیگر تمام نمبر۔ کھیل کا مزید تجزیہ گراف تھیوری کا استعمال کرتے ہوئے بورڈ کو عمودی اور کناروں کے مجموعے کے طور پر غور کر کے اور زمین پر واقع ہر عمودی کے راستوں کی جانچ کر کے کیا جا سکتا ہے (جسے ایک ممتاز عمودی سمجھا جانا چاہیے-گراف پر ایک لکیر کے بجائے تمام زمینی نکات کو ایک ساتھ شناخت کرنے میں کوئی نقصان نہیں ہوتا ہے)۔ ہیکنبش کے غیر جانبدار ورژن میں (جو کھلاڑی کے مخصوص رنگوں کے بغیر ہے)، کھیل کو کئی صورتوں میں توڑ کر نیم ڈھیر کا استعمال کرنے کے بارے میں سوچا جا سکتا ہے: عمودی، متغیر اور متفرق۔ خاص طور پر لائن سیگمنٹس کے عمودی ڈھیر کے ساتھ کھیلا جاتا ہے، جسے بانس کے ڈنٹھل بھی کہا جاتا ہے، یہ کھیل براہ راست نیم بن جاتا ہے اور اس کا براہ راست تجزیہ کیا جا سکتا ہے۔ مختلف حصے، یا درخت، کھیل میں ایک اضافی جھریاں ڈالتے ہیں اور بڑی آنت کے اصول کے استعمال کی ضرورت ہوتی ہے جس میں کہا گیا ہے کہ جب شاخیں کسی سرے پر اکٹھی ہوتی ہیں، تو کوئی شاخوں کو ان کی لمبائی کے برابر غیر شاخ دار ڈنٹھل سے تبدیل کر سکتا ہے۔ یہ اصول کھیل کی نمائندگی کو بانس کے ڈنٹھل کے زیادہ بنیادی ورژن میں تبدیل کرتا ہے۔ گراف کا آخری ممکنہ سیٹ جو بنایا جا سکتا ہے وہ متغیر ہوتے ہیں، جنہیں من مانی طور پر جڑے ہوئے گراف بھی کہا جاتا ہے۔ فیوژن اصول کا استعمال کرتے ہوئے، ہم یہ کہہ سکتے ہیں کہ گراف کی قدر کو تبدیل کیے بغیر کسی بھی سائیکل کے تمام عمودی حصوں کو ایک ساتھ ملایا جا سکتا ہے۔ لہذا، کسی بھی متغیر گراف کی تشریح بانس کے ڈنٹھل کے سادہ گراف کے طور پر بھی کی جا سکتی ہے۔ تینوں قسم کے گرافوں کو یکجا کرکے ہم گیم میں پیچیدگی کا اضافہ کر سکتے ہیں، گیم کے نیم سم کو کبھی تبدیل کیے بغیر، اس طرح گیم کو نیم کی حکمت عملی اختیار کرنے کی اجازت دے سکتے ہیں۔ کولن اصول کا ثبوت کولن اصول میں کہا گیا ہے کہ جب شاخیں کسی سرے پر اکٹھی ہوتی ہیں تو شاخوں کو ان کی لمبائی کے برابر غیر شاخ دار ڈنٹھل سے تبدیل کیا جا سکتا ہے۔ ایک فکسڈ لیکن صوابدیدی گراف، G پر غور کریں، اور G میں ایک صوابدیدی ورٹیکس، x کا انتخاب کریں۔ H1 اور H2 کو صوابدیدی ٹری (یا گراف) ہونے دیں جن کی اسپراگ-گرینڈی ویلیو ایک جیسی ہو۔ دو گرافوں G1 = Gx: H1 اور G2 = Gx: H2 پر غور کریں، جہاں Gx: Hi ٹری ہائی کو گراف G کے ورٹیکس x سے جوڑ کر بنائے گئے گراف کی نمائندگی کرتا ہے۔ کالون اصول میں کہا گیا ہے کہ دو گراف G1 اور G2 میں ایک ہی اسپراگ-گرینڈی ویلیو ہے۔ دونوں کھیلوں کے مجموعے پر غور کریں۔ یہ دعوی کہ G1 اور G2 کی اسپراگ-گرینڈی ویلیو ایک جیسی ہے، اس دعوے کے برابر ہے کہ دونوں گیمز کے مجموعے میں اسپراگ-گرینڈی ویلیو 0 ہے۔ دوسرے لفظوں میں، ہمیں یہ دکھانا ہے کہ مجموعہ G1 + G2 ایک P پوزیشن ہے۔ ایک کھلاڑی کو جیتنے کی ضمانت دی جاتی ہے اگر وہ G1 + G2 میں منتقل ہونے والا دوسرا کھلاڑی ہے۔ اگر پہلا کھلاڑی کسی ایک کھیل میں جی کے کناروں میں سے ایک کو کاٹ کر حرکت کرتا ہے، تو دوسرا کھلاڑی دوسرے کھیل میں جی میں اسی کنارے کو کاٹتا ہے۔ (اس طرح کی چالوں کی جوڑی کھیلوں سے H1 اور H2 کو حذف کر سکتی ہے، لیکن بصورت دیگر H1 اور H2 پریشان نہیں ہوتے ہیں۔) اگر پہلا کھلاڑی H1 یا H2 میں کنارے کو کاٹ کر حرکت کرتا ہے، تو H1 اور H2 کی اسپراگ-گرینڈی اقدار اب برابر نہیں ہیں، تاکہ H1 یا H2 میں ایک حرکت موجود ہو جو اسپراگ-گرینڈی اقدار کو یکساں رکھے۔ اس طرح آپ کے پاس ہمیشہ اس کی ہر حرکت کا جواب ہوگا۔ اس کا مطلب ہے کہ آپ آخری قدم اٹھائیں گے اور اس طرح جیت جائیں گے۔ حوالہ جات جان ایچ کونوے، آن نمبرز اینڈ گیمز، دوسرا ایڈیشن، اے کے پیٹرز، 2000۔ بیرونی روابط ہیکنسٹرنگس، اور 0.999. بمقابلہ 1 ہیکنبش آن پینسل اینڈ پیپر گیمز ریاضیاتی گیمز تجریدی حکمت عملی کے کھیل مشترکہ گیم تھیوری پیپر اینڈ پینسل گیمز جان ہارٹن کونوے