उत्तरच बदलून टाकणारा गो खेळाचा नियम

एखादा खेळ सोडवणे म्हणजे दोन्ही बाजू परिपूर्ण खेळल्या तर त्याचा निकाल काय येतो हे जाणणे. गोच्या पटावर हा निकाल म्हणजे एक मूल्य: परिपूर्ण खेळात काळा किती गुणांनी जिंकतो ती संख्या — 4×7 पटावर 28 म्हणजे सर्व 28 छेदनबिंदू काळ्याचे. चेकर्स 2007 मध्ये सोडवला गेला, आणि लहान पटांवरचा हेक्सही. गो साठी, 30 छेदनबिंदूंपर्यंतच्या अनेक पटांसाठी संगणकीय सिद्धता आहेत, बहुतेक MIGOS नावाच्या प्रोग्रामकडून (2003 आणि 2009).

पण एक गोम आहे. ते अभिजात निकाल पुनरावृत्त स्थितींसाठी एक सोपा केलेला नियम वापरतात — मूलभूत “को” नियम — ज्या एकट्या दगडाने आत्ताच आपला एक दगड पकडला, तो खेळाडूला लगेच परत पकडता येत नाही, अन्यथा त्याच दोन चाली अखंड फिरत राहिल्या असत्या — आणि त्याबरोबर खास संकेत: पास केल्याने को-बंदी उठते, पुनरावृत्त स्थितीवर खेळ थांबतो, इत्यादी. एखाद्या स्थितीचे मूल्य ती कशी गाठली गेली यावर अवलंबून राहू नये, यासाठी हे संकेत आखले होते.

लोक प्रत्यक्षात खेळतात तो नियम

लिखित स्वरूपातील चिनी नियम, आणि संगणकीय गो, स्थितिगत सुपरको (positional superko) वापरतात: कोणतीही चाल खेळात आधीच येऊन गेलेली कोणतीही संपूर्ण-पट स्थिती पुन्हा निर्माण करू शकत नाही. या नियमाखाली सोडवणे खूपच कठीण आहे, कारण आता एखाद्या चालीची वैधता खेळाच्या संपूर्ण इतिहासावर अवलंबून असते. सोडवणे शक्य करणारी तीन साधने यामुळे मोडतात:

दुसऱ्या मार्गाने गाठलेल्या त्याच स्थितीचे निकाल पुन्हा वापरणे — दोन मार्ग वेगवेगळ्या चालींना मनाई करू शकतात;
शोधाशिवाय सुरक्षित गट आणि प्रदेश ओळखणे, जे असे गृहीत धरते की मालक घुसखोरांना नेहमी पकडू शकतो — सुपरकोखाली असे पकडणे निषिद्ध ठरू शकते;
कधीच उपयोगी न पडणाऱ्या चालींची छाटणी, जसे स्वतःचा डोळा (eye) भरणे — एखाद्या गटाला जिवंत राहण्यासाठी लागणाऱ्या रिकाम्या बिंदूंपैकी एक — सुपरकोखाली अशी चाल निर्णायक ठरू शकते.

किंमत प्रचंड होती: सुपरकोच्या एका प्रकारासह MIGOS ला 4×4 पटासाठी 1.1 तास लागले, मूलभूत कोखाली 3.3 सेकंदांच्या तुलनेत. 5×5 चे पहिले सुपरको उत्तर, 2024 मध्ये, सहा प्रक्रियांवर 5.25 तास घेऊन आले. 5×5 पलीकडील, किमान दोन ओळी असलेला कोणताही पट सुपरकोखाली सोडवला गेला नव्हता.

निर्दोष राहणारा शॉर्टकट

बर्लिनच्या झूस इन्स्टिट्यूटचे (Zuse Institute Berlin) सामी खार्मा आणि फ्लोरियन शिंट्के यांनी Sanko बांधला. त्याचा गाभा म्हणजे एक साधे सिद्धता-हस्तांतरण प्रमेय (proof-transfer theorem): एखादा खेळाडू जिंकतो याची साठवलेली सिद्धता नव्या मार्गावर वैध राहते, जोपर्यंत विजेत्याला निर्माण कराव्या लागणाऱ्या एखाद्या पटाची आधीच नोंद झालेली नाही. फक्त विजेत्याचे पट महत्त्वाचे — पराभूत खेळाडू एखादी स्थिती पुन्हा निर्माण करू शकत नसेल, तर तो फक्त एक पर्याय गमावतो. हे तपासायला लागणारा वेळ सिद्धतेच्या आकाराच्या नव्हे, तर मार्गाच्या लांबीच्या प्रमाणात असतो. 3×7 पटावर, फक्त या शॉर्टकटमुळे काम 664 अब्ज पायऱ्यांवरून 11.2 कोटी पायऱ्यांपर्यंत घटते.

त्यांनी सुरक्षित गट ओळखण्याची अभिजात पद्धतही सुपरकोखाली अचूक राहील अशी जुळवून घेतली, आणि ज्या बाजूचा विजय ते सिद्ध करू पाहत होते, फक्त तिच्याच चालींची छाटणी केली, जेणेकरून अयशस्वी शोध “अज्ञात” म्हणून नोंदवला जावा, दुसऱ्या बाजूचा विजय म्हणून कधीच नाही.

नवी मूल्ये

5×5 सहा थ्रेड्सवर 15.7 मिनिटांत — आधीपेक्षा सुमारे 20 पट वेगवान, अंशतः चांगल्या हार्डवेअरमुळे; एकाच थ्रेडवर 4×4 58 पट वेगाने सुटतो. 192 थ्रेड्सच्या एका यंत्रावर 5×5 ला सुमारे दीड मिनिट लागते.
आणखी 23 पटांची पहिली सुपरको मूल्ये; त्यांपैकी 11 कोणत्याही नियमाखाली कधीच सोडवले गेले नव्हते. 3×10 काळ्यासाठी 8 गुणांचा आहे — MIGOS ने फक्त किमान 6 सिद्ध केले होते, आणि दोन महिन्यांच्या शोधानेही वरची मर्यादा सापडली नव्हती.
एका ओळीच्या पटांवर, 1×9 ते 1×15 ची मूल्ये 0, 1, 2, 2 अशी पुनरावृत्त होतात — पण 1×16 हा आकृतिबंध मोडतो, 2 ऐवजी 1 मूल्याचा.

4×7 चे आश्चर्य

जुन्या नियमांखाली 4×7 हा पूर्ण-पट विजय आहे: काळा सर्व काही पकडतो, 28–0. सुपरकोखाली त्याचे मूल्य 12 आहे. लेखकांनी MIGOS साठी प्रकाशित केलेला 31 चालींचा इष्टतम क्रम पुन्हा खेळून पाहिला: प्रत्येक चाल वैध आहे, आणि तरीही काळा संपूर्ण पट घेतो. क्रम उलट्या दिशेने सोडवताना त्यांना 25 व्या चालीनंतर लगेचच मोडणी सापडली: काळ्याने खेळलेल्या 25 व्या चालीनंतरच्या स्थितीत पांढऱ्याने A2 ऐवजी G2 (किंवा C1) खेळायला हवे.

पुढे जे घडते तो एक विचित्र को आहे. पांढरा पकडतो; काळ्याने परत पकडले तर आधीचा पट पुन्हा निर्माण होईल — ते निषिद्ध. काळ्याची इतर प्रत्येक चाल स्वतःच्याच गटाला धोक्यात घालते. काळ्याला पास करावे लागते, पांढरा पास करतो, आणि पांढऱ्याचा गट जिवंत असताना खेळ संपतो: MIGOS च्या लेखकांनी ज्याला आधीच “चांदण्यातील जीवन” (moonshine life) म्हटले होते. जुन्या नियमांखाली पास केल्याने बंदी उठली असती आणि काळ्याने परत पकडून सर्व काही जिंकले असते. सुपरकोखाली या क्रमात काळ्याला मिळू शकणारे सर्वोत्तम म्हणजे फक्त 3 गुणांचे सामायिक जीवन (seki), त्यामुळे परिपूर्ण खेळ प्रकाशित क्रमातून आधीच वेगळा होतो — आणि रिकाम्या पटापासून काळा मिळवू शकतो ते सर्वोत्तम मूल्य 12.

कोणताही शोध चुकीचा नव्हता. फरक अशा नियमांमधून येतो जे खेळाच्या अगदी शेवटीच महत्त्वाचे ठरतात. लेखकांचा सल्ला: पुनरावृत्ती निरुपद्रवी करणाऱ्या संकेतांखाली काढलेली मूल्ये तपासल्याशिवाय सुपरको गोची मूल्ये म्हणून उद्धृत करू नयेत.

कोणीही तपासू शकेल असे

प्रत्येक मूल्य दोन स्वतंत्र सिद्धतांवर आधारलेले आहे, आणि सोडवणाऱ्या प्रोग्रामने दहापट हजारो उलटतपासण्या एकही विसंगती न येता पार केल्या. रिकाम्या गो-पटांच्या आधीच्या उत्तरांप्रमाणे नव्हे, तर इथे सोडवणाऱ्याचा स्रोत-कोड आणि प्रत्येक निकालामागची नेमकी आज्ञा सार्वजनिक आहेत; 4×7 ची सिद्धता-साखळी वीस सेकंदांपेक्षा कमी वेळात पुन्हा चालते. या सिद्धता अजून अशी प्रमाणपत्रे नाहीत जी बाहेरची व्यक्ती स्वतंत्रपणे पडताळू शकेल, आणि 6×6 अजूनही आवाक्याबाहेर आहे — लेखकांच्या बहिर्वेशनानुसार, त्यांच्या एका यंत्रावर सुमारे 50 दिवस, किंवा अधिक.