Solving chess
شطرنج کو حل کرنا شطرنج کے کھیل کے لیے ایک بہترین حکمت عملی تلاش کرنے پر مشتمل ہے۔ یعنی، جس کے ذریعے کھلاڑی (سفید یا سیاہ) ہمیشہ فتح پر مجبور کر سکتا ہے، یا یا تو ڈرا پر مجبور کر سکتا ہے (حل شدہ کھیل دیکھیں)۔ اس کا تعلق زیادہ عام طور پر شطرنج جیسے کھیلوں کو حل کرنے سے بھی ہے (یعنی۔ کامل معلومات کے مشترکہ کھیل) جیسے کیپابلانکا شطرنج اور لامحدود شطرنج۔ کمزور معنوں میں، شطرنج کو حل کرنے کا مطلب یہ ثابت کرنا ہو سکتا ہے کہ تین ممکنہ نتائج میں سے کون سا (سفید جیت ؛ سیاہ جیت ؛ ڈرا) دو کامل کھلاڑیوں کا نتیجہ ہے، بغیر ضروری طور پر زیادہ سے زیادہ حکمت عملی کو ظاہر کیے (بالواسطہ ثبوت دیکھیں)۔ دونوں حواس میں سے کسی میں بھی شطرنج کا کوئی مکمل حل معلوم نہیں ہے، اور نہ ہی یہ توقع کی جاتی ہے کہ شطرنج مستقبل قریب میں حل ہو جائے گا (اگر کبھی ہو)۔ اس بات پر اختلاف ہے کہ آیا کمپیوٹنگ پاور کی موجودہ تیز رفتار ترقی اتنی طویل عرصے تک جاری رہے گی کہ کسی دن اسے "بروٹ فورس" کے ذریعے حل کرنے کی اجازت دے، یعنی۔ تمام امکانات کی جانچ کر کے۔ آج تک کی پیش رفت انتہائی محدود ہے۔ ٹکڑوں کی ایک چھوٹی سی تعداد (سات تک) کے ساتھ کامل اینڈگیم کھیل کے ٹیبل بیس موجود ہیں، اور شطرنج کے کچھ متغیرات کو کم از کم کمزور طریقے سے حل کیا گیا ہے۔ گیم ٹری کی پیچیدگی اور شطرنج کی ریاستی جگہ کی پیچیدگی کے حساب سے تخمینے موجود ہیں جو گیم کو حل کرنے کے لیے درکار کمپیوٹیشنل کوشش کے بارے میں پرندوں کی نظر فراہم کرتے ہیں۔ جزوی نتائج اینڈگیم ٹیبل بیس کمپیوٹرائزڈ ڈیٹا بیس ہوتے ہیں جن میں پوزیشنوں کے پہلے سے حساب شدہ مکمل تجزیے ہوتے ہیں جن میں بورڈ پر تھوڑی تعداد میں ٹکڑے باقی رہتے ہیں۔ ٹیبل بیس نے شطرنج کو ایک محدود حد تک حل کیا ہے، جس سے متعدد اختتامی کھیلوں میں کامل کھیل کا تعین ہوتا ہے، بشمول تمام غیر معمولی اختتامی کھیل جن میں سات سے زیادہ ٹکڑے یا پیادے (بشمول دو بادشاہ) نہیں ہوتے ہیں۔ سات ٹکڑے والے اینڈ گیم ٹیبل بیس کو تیار کرنے کا ایک نتیجہ یہ ہے کہ شطرنج کے بہت سے دلچسپ نظریاتی اختتام پائے گئے ہیں۔ سب سے طویل سات ٹکڑوں کی مثال 50-حرکت کے اصول کو نظر انداز کرتے ہوئے گائے ہاورتھ کے ذریعہ لومونوسوف ٹیبل بیس میں دریافت کی گئی میٹ-ان-549 پوزیشن ہے۔ اس طرح کی پوزیشن کسی بھی انسان کی حل کرنے کی صلاحیت سے باہر ہے، اور کوئی بھی شطرنج کا انجن اسے ٹیبل بیس تک رسائی کے بغیر صحیح طریقے سے نہیں کھیلتا، جس کے لیے ابتدائی طور پر (2014 میں) 140 ٹی بی اسٹوریج کی جگہ اور سپر کمپیوٹر کے استعمال کی ضرورت تھی لیکن بعد میں اسے کم کر کے 18.4 ٹی بی کر دیا گیا۔ جنوری 2023 تک، آٹھ ٹکڑوں والے ٹیبل بیس (50 چالوں کے اصول کو بھی نظر انداز کرتے ہوئے) کے لیے سب سے طویل معلوم جبری ملاپ کا سلسلہ 584 چالوں کا تھا۔ اسے 2022 کے وسط میں ڈویلپر، کمپیوٹر شطرنج کے شوقین، اور طبیعیات دان مارک بورزوٹسکی نے دریافت کیا تھا۔ ایٹ پیس ٹیبل بیس فی الحال نامکمل ہے، تاہم، اس لیے اس بات کی ضمانت نہیں ہے کہ یہ ایٹ پیس ٹیبل بیس کے لیے مطلق حد ہے۔ شطرنج کی مختلف شکلیں شینن کی طرف سے سب سے پہلے بیان کردہ ایک قسم شطرنج کی گیم تھیوریٹک ویلیو کے بارے میں ایک دلیل فراہم کرتی ہے: وہ "پاس" کی حرکت کی اجازت دینے کی تجویز پیش کرتا ہے۔ اس قسم میں، یہ حکمت عملی چوری کرنے کی دلیل سے ثابت ہوتا ہے کہ پہلے کھلاڑی کے پاس کم از کم ڈرا ہوتا ہے اس طرح: اگر پہلے کھلاڑی کے پاس جیتنے والی حرکت ہے، تو اسے کھیلنے دیں، ورنہ پاس کریں۔ دوسرے کھلاڑی کو اب بورڈ کی آئینے کی تصویر کی ہم آہنگی کی وجہ سے اسی صورتحال کا سامنا کرنا پڑتا ہے: اگر پہلے کھلاڑی کے پاس پہلی بار میں کوئی جیتنے والی حرکت نہیں تھی، تو دوسرے کھلاڑی کے پاس اب کوئی حرکت نہیں ہے۔ لہذا، دوسرا کھلاڑی بہترین ڈرا کر سکتا ہے، اور پہلا کھلاڑی کم از کم ڈرا کر سکتا ہے، لہذا ایک کامل کھیل کے نتیجے میں پہلا کھلاڑی جیتتا ہے یا ڈرا کرتا ہے۔ شطرنج کے کچھ متغیرات جو شطرنج سے زیادہ آسان ہیں حل کیے گئے ہیں۔ مہاراجہ اور سپاہیوں میں سیاہ فاموں کے لیے جیت کی حکمت عملی کو آسانی سے حفظ کیا جا سکتا ہے۔ 5×5 گارڈنر کی منیچیس قسم کو ڈرا کے طور پر کمزور طریقے سے حل کیا گیا ہے۔ اگرچہ شطرنج ہارنا 8x8 بورڈ پر کھیلا جاتا ہے، لیکن اس کا جبری گرفتاری کا اصول اس کی پیچیدگی کو بہت محدود کرتا ہے، اور ایک کمپیوٹیشنل تجزیہ اس قسم کو وائٹ کی جیت کے طور پر کمزور طریقے سے حل کرنے میں کامیاب رہا۔ انفرادی، مخصوص، شطرنج جیسے کھیلوں کو حل کرنے کا امکان زیادہ مشکل ہو جاتا ہے کیونکہ بورڈ کے سائز میں اضافہ ہوتا ہے، جیسے کہ شطرنج کی بڑی اقسام، اور لامحدود شطرنج میں۔ 1950 میں شطرنج کے انفارمیشن تھیوریسٹ کلاڈ شینن کی پیچیدگی نے ایک کامل کھیل کھیلنے کے لیے ایک نظریاتی طریقہ کار کا خاکہ پیش کیا (یعنی۔ شطرنج کو حل کرنا): شینن نے پھر اندازہ لگایا کہ اس طریقہ کار کے مطابق شطرنج کو حل کرنے کے لیے کھیل کے تقریبا 10 ممکنہ تغیرات کا موازنہ کرنے کی ضرورت ہوگی، یا تقریبا 10 ممکنہ بورڈ پوزیشنوں (فی الحال تقریبا 5x10 کے طور پر جانا جاتا ہے) میں سے ہر ایک کے لیے ایک بہترین حرکت کی نشاندہی کرنے والی "ڈکشنری" کی ضرورت ہوگی۔ تاہم، شطرنج کو حل کرنے کے لیے درکار ریاضیاتی کارروائیوں کی تعداد شطرنج کے پورے کھیل کے درخت کو تیار کرنے کے لیے درکار کارروائیوں کی تعداد سے نمایاں طور پر مختلف ہو سکتی ہے۔ خاص طور پر، اگر وائٹ کو زبردستی جیت حاصل ہوتی ہے، تو گیم ٹری کے صرف ایک ذیلی سیٹ کو اس بات کی تصدیق کے لیے تشخیص کی ضرورت ہوگی کہ جبری جیت موجود ہے (یعنی۔ سیاہ سے کوئی تردید کے بغیر)۔ مزید برآں، شطرنج کی پیچیدگی کے لیے شینن کا حساب کھیل کی اوسط لمبائی 40 چالوں کا فرض کرتا ہے، لیکن یہ کہنے کی کوئی ریاضیاتی بنیاد نہیں ہے کہ دونوں طرف سے زبردستی جیت کا اس کھیل کی لمبائی سے کوئی تعلق ہوگا۔ درحقیقت، مہارت سے کھیلے گئے کچھ کھیل (گرینڈ ماسٹر سطح کا کھیل) اتنے ہی مختصر رہے ہیں جتنے کہ 16 حرکتیں۔ ان وجوہات کی بناء پر، ریاضی دان اور گیم تھیوریسٹ واضح طور پر یہ بتانے سے گریزاں رہے ہیں کہ شطرنج کو حل کرنا ایک ناقابل حل مسئلہ ہے۔ 1950 میں، شینن نے 10 کی گیم ٹری کی پیچیدگی اور ایک میگا ہرٹز پر کام کرنے والے کمپیوٹر کی بنیاد پر حساب لگایا (اس وقت ایک بڑا حصہ: 1951 میں متعارف کرایا گیا UNIVAC 1 ~ 2000 آپریشن فی سیکنڈ یا 2 کلو ہرٹز انجام دے سکتا ہے) جو 1 مائیکرو سیکنڈ میں ٹرمینل نوڈ کا اندازہ لگا سکتا ہے اسے اپنی پہلی حرکت کرنے میں 10 سال لگیں گے۔ یہاں تک کہ تکنیکی ترقی کی اجازت دینا، شطرنج کو عملی وقت کے اندر حل کرنا کسی بھی قابل فہم ٹیکنالوجی سے بالاتر معلوم ہوتا ہے۔ برکلے میں یونیورسٹی آف کیلیفورنیا میں ریاضی اور بائیو فزکس کے پروفیسر ہنس جوآخم بریمرمین نے 1965 کے ایک مقالے میں مزید دلیل دی کہ "مستقبل کے کسی بھی ممکنہ کمپیوٹر آلات کی رفتار، یادداشت اور پروسیسنگ کی صلاحیت مخصوص جسمانی رکاوٹوں سے محدود ہے: روشنی کی رکاوٹ، کوانٹم رکاوٹ، اور تھرموڈینامکل رکاوٹ۔ مثال کے طور پر، ان حدود کا مطلب یہ ہے کہ کوئی بھی کمپیوٹر، چاہے جو بھی بنایا گیا ہو، شطرنج کے کھیل کے ممکنہ حرکت کے سلسلے کے پورے درخت کی جانچ پڑتال کرنے کے قابل نہیں ہوگا۔ بہر حال، بریمرمین نے اس امکان کو پیش گوئی نہیں کی کہ کمپیوٹر کسی دن شطرنج کو حل کرنے کے قابل ہو جائے گا۔ انہوں نے لکھا، "کمپیوٹر کو ایک کامل یا تقریبا کامل گیم کھیلنے کے لیے، یا تو گیم کا مکمل تجزیہ کرنا ضروری ہوگا۔ یا گیم کا تخمینہ انداز میں تجزیہ کرنا اور اسے محدود مقدار میں ٹری سرچ کے ساتھ جوڑنا ضروری ہوگا۔ تاہم، اس طرح کے تحقیقی پروگرامنگ کی نظریاتی تفہیم اب بھی بہت زیادہ مطلوب ہے۔ " حالیہ سائنسی پیشرفتوں نے ان تشخیصوں کو نمایاں طور پر تبدیل نہیں کیا ہے۔ چیکرز کا کھیل (کمزور طور پر) 2007 میں حل کیا گیا تھا، لیکن اس میں شطرنج میں پوزیشنوں کی تعداد کا تقریبا مربع جڑ ہے۔ اس کوشش کی قیادت کرنے والے سائنسدان جوناتھن شیفر نے کہا کہ شطرنج کو حل کرنے کی کوشش کرنے سے پہلے کوانٹم کمپیوٹنگ جیسی پیشرفت کی ضرورت ہوگی، لیکن وہ اس امکان کو مسترد نہیں کرتے ہیں، یہ کہتے ہوئے کہ انہوں نے چیکرز کو حل کرنے کی اپنی 16 سالہ کوشش سے جو ایک چیز سیکھی ہے وہ یہ ہے کہ "ٹیکنالوجی میں ہونے والی پیشرفت کو کبھی کم نہ سمجھا جائے"۔ شینن نمبر (شطرنج کے کھیل کے درخت کی پیچیدگی کی نچلی حد کا حساب) شطرنج کے حوالہ جات میں پہلی حرکت کا فائدہ بیرونی لنکس "لامحدود شطرنج، پی بی ایس لامحدود سیریز" لامحدود شطرنج، پی بی ایس لامحدود سیریز بھی دیکھیں۔ شطرنج کا نظریہ