कंप्यूटर वैज्ञानिक जो खेलों में जीवन के सबक ढूंढता है

के लिए शांग-हुआ टेंगो, सैद्धांतिक कंप्यूटर विज्ञान कभी भी विशुद्ध सैद्धांतिक नहीं रहा है। अब 58 साल के टेंग दक्षिणी कैलिफोर्निया विश्वविद्यालय में कंप्यूटर विज्ञान के प्रोफेसर हैं और गोडेल पुरस्कार के दो बार विजेता हैं, जो अभूतपूर्व सैद्धांतिक कार्य को मान्यता देने वाला एक वार्षिक पुरस्कार है। लेकिन वह अक्सर उस अमूर्त सिद्धांत को व्यावहारिक और चंचल दोनों तरीकों से रोजमर्रा की जिंदगी से जोड़ने का प्रयास करते हैं।

चीनी सांस्कृतिक क्रांति की पूर्व संध्या पर बीजिंग में जन्मे, टेंग कंप्यूटर वास्तुकला का अध्ययन करने की योजना बनाकर स्नातक स्कूल के लिए संयुक्त राज्य अमेरिका आए थे, लेकिन उन्होंने जल्द ही अधिक अमूर्त गणितीय सिद्धांत पर ध्यान केंद्रित करने के लिए दिशा बदल दी। उन्होंने 1991 में कार्नेगी मेलन विश्वविद्यालय में डॉक्टरेट की उपाधि प्राप्त की, जिसमें ग्राफ़ को विभाजित करने के सर्वोत्तम तरीके के बारे में एक प्रमेय साबित किया गया था - बिंदुओं के जाल, या नोड्स, रेखाओं या किनारों से जुड़े हुए।

यद्यपि सैद्धांतिक, कार्य में व्यावहारिक अनुप्रयोग थे - और अक्सर, उन्होंने पाया, व्यावहारिक अनुप्रयोगों ने नई सैद्धांतिक अंतर्दृष्टि को जन्म दिया। 1993 की नासा ग्रीष्मकालीन फ़ेलोशिप के दौरान, टेंग "परिमित-तत्व" विधियों का उपयोग करके द्रव गतिशीलता का अनुकरण करने वाली एक टीम में शामिल हो गए, जो कई छोटे टुकड़ों के संयोजन के रूप में जटिल संरचनाओं का मॉडल बनाती है। इन संयोजनों को ग्राफ़ के रूप में माना जा सकता है, और टेंग का कार्य अपने स्नातक अनुसंधान से विभाजन पद्धति को इस नई सेटिंग में अनुकूलित करना था। लेकिन वह उस विभाजन तकनीक के बारे में उत्सुक हो गए जिसे नासा टीम ने पहले इस्तेमाल किया था, और साथी कंप्यूटर वैज्ञानिक के साथ मिलकर इसकी अंतर्निहित गणितीय संरचना की जांच करना शुरू कर दिया। डेनियल स्पीलमैन, अब येल विश्वविद्यालय में कंप्यूटर विज्ञान के प्रोफेसर हैं। उस संयुक्त अनुसंधान परियोजना ने दशकों पुराने सहयोग को जन्म दिया जिसने उन्हें दो गोडेल पुरस्कार जीते।

यह एकमात्र मौका नहीं था जब उन्होंने सिद्धांत और व्यवहार के बीच गहरा संबंध देखा। टेंग ने कहा, "हर बार, इन पूरी तरह से व्यावहारिक चीजों के पीछे यह सुंदर गणित होता था।"

हाल ही में, टेंग ने अपना ध्यान टिक-टैक-टो, शतरंज और गो जैसे खेलों के पीछे के सुंदर गणित की ओर लगाया है। ऐसे "कॉम्बिनेटोरियल" खेलों में, मौका का कोई तत्व नहीं होता है, और दोनों खिलाड़ी हमेशा बोर्ड की स्थिति के बारे में सब कुछ जानते हैं। फिर भी संयोजनात्मक खेल चुनौतीपूर्ण बने हुए हैं क्योंकि एक खेल को खेलने के तरीकों की संख्या आश्चर्यजनक रूप से बड़ी हो सकती है।

गेम थ्योरी शोधकर्ता ऐसे गेम को बड़े बोर्डों पर सामान्यीकृत करना पसंद करते हैं - टिक-टैक-टो को 3-बाय-3 वर्ग से बढ़ाकर n-द्वारा-n, उदाहरण के लिए - और यह निर्धारित करने में कठिनाई को मापें कि कौन सा खिलाड़ी कुछ प्रारंभिक बोर्ड स्थिति को देखते हुए जीतेगा। अलग-अलग संभावित उत्तर गेम को उसी में क्रमबद्ध करते हैं "जटिलता वर्ग“यह पूरे सैद्धांतिक कंप्यूटर विज्ञान में सामने आता है।

एक प्रसिद्ध जटिलता वर्ग को "बहुपद समय" के लिए गद्य नाम पी से जाना जाता है, और इसमें ऐसी समस्याएं शामिल हैं जिन्हें मोटे तौर पर उचित समय में हल किया जा सकता है। समान रूप से प्रसिद्ध वर्ग एनपी में समस्याओं को हल करने में अनुचित समय लग सकता है, लेकिन उनके समाधान की जांच करना आसान है। एक अन्य जटिलता वर्ग, जिसे पीएसपीएसीई कहा जाता है, की समस्याओं के लिए भी ऐसे कुशल सत्यापन की गारंटी नहीं है। जब शोधकर्ता दो-खिलाड़ियों के खेल के "गहरे तर्क" पर विचार करते हैं - "यदि आप एक्स करते हैं, और फिर यदि मैं वाई करता हूं, और फिर यदि आप जेड करते हैं," और इसी तरह - तो वे अक्सर खुद को पीएसपीएसीई के बारे में बात करते हुए पाते हैं। लेकिन जैसा कि टेंग ने साबित करने में मदद की है, कॉम्बिनेटरियल गेम्स का गणित हमेशा सीधा नहीं होता है।

क्वांटा कंप्यूटर विज्ञान के प्रति अपने मार्ग, बोर्ड गेम में अंतर्निहित गणित और अपने पिता के प्रभाव पर चर्चा करने के लिए हाल ही में टेंग से बात की। स्पष्टता के लिए साक्षात्कार को संक्षिप्त और संपादित किया गया है।

चीन में शिक्षा प्राप्त करना कैसा था?

मेरा जन्म सांस्कृतिक क्रांति से थोड़ा पहले हुआ था, और मेरे पिता सिविल इंजीनियरिंग में विश्वविद्यालय विभाग के अध्यक्ष थे। जब क्रांति हुई तो वह कैंपस में कैद में थे। फिर पूरे परिसर को ग्रामीण इलाकों में भेज दिया गया।

जब तक मैं व्यावहारिक रूप से जूनियर हाई की पढ़ाई पूरी नहीं कर रहा था, तब तक मैं बेचने के लिए कूड़ा इकट्ठा करता था, और फिर अचानक चीन बदल गया। यदि आपने पढ़ाई की तो आप कॉलेज में प्रवेश ले सकते थे, और हमारे पास नियमित नौकरी की कोई अन्य संभावना नहीं थी। मैं उठा, और मैंने कहा, "मुझे अध्ययन करने की आवश्यकता है।"

आपने कंप्यूटर विज्ञान कैसे चुना?

मैं हाई स्कूल के बाद जीव विज्ञान पढ़ना चाहता था। मुझे नहीं पता क्यों, लेकिन मेरे पिता इससे बहुत खुश नहीं थे। मैं गणित में ठीक कर रहा था, और उसने मुझसे पूछा कि क्या मैं गणित करना चाहता हूँ। मैंने कहा नहीं। [हंसते हैं।] और फिर उन्होंने कहा, "आप जानते हैं, कंप्यूटर विज्ञान नामक एक नया अनुशासन है, और यह वास्तव में अच्छा है।" किसी तरह, उन्होंने मुझे कंप्यूटर विज्ञान में पढ़ाई करने के लिए प्रेरित किया।

उस समय की शिक्षा बहुत ही बुनियादी थी। हम अधिकांश चीज़ों से परिचित नहीं थे, और कंप्यूटर विज्ञान कोई विभाग भी नहीं था; यह इलेक्ट्रिकल इंजीनियरिंग में एक प्रमुख विषय था। लेकिन पूरी तरह से यादृच्छिक भाग्य से हमें गणित के छात्रों के रूप में कैलकुलस में प्रशिक्षित किया गया, और मैंने कुछ चीजें सीखीं जो अंततः एक सिद्धांतकार बनने के लिए उपयोगी थीं। इसके बिना मेरे पास पास होने का शायद शून्य मौका होता। इन दिनों बच्चे कहीं अधिक प्रतिभाशाली हैं: हाई स्कूल के बाद से वे उस समय की तुलना में अधिक प्रतिभाशाली गणितज्ञ हैं जब मैं इस देश में आया था।

आपके ज्ञान में उन कमियों ने स्नातक विद्यालय के आपके अनुभव को कैसे प्रभावित किया?

एक दिन [मेरे सलाहकार, गैरी मिलर] को पता चला कि मैंने एनपी के बारे में कभी नहीं सुना था। यह चर्चा में था. उन्होंने कहा, "यह समस्या एनपी-हार्ड दिखती है।" मैंने कहा, "उह-हह।" उन्होंने कहा, "तुम्हें मुझ पर विश्वास नहीं है?" और फिर उसने इसे साबित करना शुरू कर दिया, और आधे रास्ते में वह तेजी से मेरी ओर मुड़ा, क्योंकि मैं वहीं बैठा था, और उसने कहा, "क्या आप जानते हैं कि एनपी-हार्ड क्या है?" मैंने कहा नहीं।

मैंने सोचा कि वह उनके साथ काम करने का आखिरी दिन था, लेकिन उन्होंने जारी रखा और मुझे परिभाषा बताई। उन्होंने कहा, "अगर आप नहीं जानते तो कोई बात नहीं, जब तक आप सोचने में सक्षम हैं।" उनका मुझ पर जबरदस्त प्रभाव पड़ा।'

आप मुख्य रूप से एक सिद्धांतकार हैं, लेकिन अपने पूरे करियर के दौरान आपने उद्योग में प्रवेश किया है। यह व्यावहारिक कार्य आपके सैद्धांतिक शोध से कैसे जुड़ा?

अपनी थीसिस में मैंने ग्राफ़ को विभाजित करने के लिए कुछ ज्यामितीय तरीके विकसित किए। मैं यह दिखाने में सक्षम था कि ज्यामितीय तरीकों के इस परिवार ने परिमित-तत्व ग्राफ़ के लिए काफी अच्छे कट दिए हैं।

अपने गुरु की अनुशंसा पर, मैंने नासा और बोइंग एयरोस्पेस में व्याख्यान देना शुरू किया। बोइंग में, मुझे याद है कि पंखों में से एक के 3डी मॉडल में पहले से ही लगभग दस लाख तत्व थे - वे उसे एक मशीन में लोड भी नहीं कर सकते थे। इसलिए वे इस ग्राफ़ को विभिन्न घटकों में काटना चाहते थे, उन्हें समान कम्प्यूटेशनल भार वाली विभिन्न मशीनों पर रखना चाहते थे, और संचार को कम करना चाहते थे। इसीलिए गणितीय रूप से सूत्र एक ग्राफ़ कट है।

सैद्धांतिक कंप्यूटर विज्ञान में, अक्सर अंतर्निहित गणितीय सिद्धांत अपरिवर्तित रहते हैं, भले ही समस्या की उपस्थिति अनुकूलन से गेम सिद्धांत तक काफी बदल जाती है। जब आप शोध कर रहे होते हैं, तो यह कोई बड़ा बदलाव जैसा नहीं लगता।

गेम थ्योरी की बात करें तो मैंने देखा कि आपने एक बोर्ड गेम डिज़ाइन करने में मदद की। वह कैसे हुआ?

ओह, मुझे बोर्ड गेम पसंद हैं! जटिलता सिद्धांत के साथ सुंदर संबंध हैं। लेकिन अधिकतर मैं अपने छात्रों का छात्र हूं।

मैं बोस्टन विश्वविद्यालय में स्पर्नर लेम्मा नामक एक सुंदर पृथक प्रमेय के बारे में भाषण दे रहा था। यह एक आयाम में बहुत सरल है। आपके पास एक रेखाखंड है जिसका एक सिरा लाल है और एक सिरा नीला है। आप इसे उपखंडों में विभाजित करें [दोनों सिरों पर नोड्स के साथ] और प्रत्येक नए नोड को या तो लाल या नीला रंग दें। फिर [कोई फर्क नहीं पड़ता कि आप उन्हें कैसे रंगते हैं] हम जानते हैं कि एक खंड ऐसा होना चाहिए जिसमें दोनों रंग हों।

दो आयामों में, यह बहुत आकर्षक है। आपके पास एक त्रिकोण है, और अब आपके पास तीन रंग हैं: एक कोना लाल है, एक नीला है और एक हरा है। आप इस त्रिभुज को छोटे त्रिभुजों में विभाजित करते हैं, ताकि किनारे खंडों में टूट जाएँ। प्रत्येक बाहरी किनारा एक-आयामी नियम का पालन करता है: नोड्स केवल दो सिरों के रंगों का उपयोग कर सकते हैं। त्रिकोण के अंदर, आप अपनी पसंद के अनुसार तीनों रंग बना सकते हैं। स्पर्नर की लेम्मा कहती है कि आप इसे किसी भी तरह से विभाजित करें, यदि आप यह रंग भरते हैं, तो एक त्रिकोण होना चाहिए जिसमें सभी तीन रंग हों।

काइल बर्क मेरे छात्र थे, जो उस समय संख्यात्मक विश्लेषण पर काम कर रहे थे। वह मेरे कार्यालय में आए और कहा कि स्पर्नर की लेम्मा का एक सुंदर बोर्ड गेम हो सकता है: दो खिलाड़ी एक बोर्ड को पुनरावृत्त रूप से रंगते हैं, और जो कोई तीन-रंग का त्रिकोण बनाता है वह गेम हार जाएगा। सर्वश्रेष्ठ बोर्ड गेम में टाई के बजाय विजेता होते हैं, और यहां, स्पष्ट रूप से कोई न कोई जीतेगा। क्यों? क्योंकि स्पर्नर की लेम्मा!

मैंने इर्विन से अपने दोस्त डेविड एप्स्टीन को इस बारे में बात करने के लिए बुलाया कि एक अच्छा बोर्ड गेम क्या होता है। उन्होंने कहा, "एक अच्छे गेम में सरल नियम और एक सुंदर बोर्ड होता है, और इसे PSPACE-हार्ड होना चाहिए।" क्योंकि यदि आप इसे बहुपद समय में हल कर सकते हैं, तो कंप्यूटर आपको हर समय हरा देगा।

इसलिए हम उन मानदंडों से गुजरे। काइल ने कहा, "क्या यह खेल सरल है?" मैंने कहा, "हाँ, यह एक वाक्य है!" उन्होंने कहा, "क्या यह खेल रंगीन है?" मैंने कहा, "डिज़ाइन के अनुसार!" फिर उन्होंने कहा, "अगर मैं साबित कर दूं कि यह पीएसपीएसीई-कठिन है, तो क्या मुझे पीएचडी मिल सकती है?" मैंने हाँ कहा, और उसने हाँ कहा। उनके प्रमेय के कई अलग-अलग पहलू हैं। यह निश्चित बिंदुओं के बारे में कुछ बातें बताता है, जो गणित में एक बहुत ही सुंदर अवधारणा है।

क्या मैं कहीं भी गेम खेल सकता हूँ?

यह कुछ बदलावों के साथ उपलब्ध है, ऑनलाइन.

आप कौन से खेल खेलना पसंद करते हैं?

मैं खेलों का सिद्धांतकार हूं। [हंसते हैं।] मैं अपनी बेटी के साथ थोड़ा खेलता हूं, लेकिन मैं उनके साथ खेलते हुए बड़ी नहीं हुई। मेरे विद्यार्थियों के विपरीत, जिन्होंने जीवन भर खेल खेले हैं।

आपने बोर्ड गेम के गणित पर और क्या काम किया है?

हमारे पास काग़ज़ हाल ही में एक खुले प्रश्न के बारे में: यदि आप दो बहुपद-समय-समाधान योग्य खेलों को एक साथ, एक साथ रखते हैं, तो क्या यह उन्हें PSPACE-कठिन बना देगा? प्रत्येक चाल पर आप उनमें से केवल एक ही खेल सकते हैं। इसे खेलों का योग कहते हैं।

दो खेलों को एक साथ रखने का क्या मतलब है?

प्राचीन गेम गो में, जब आप पर्याप्त पत्थर डालते हैं, तो आपको कई अलग-अलग क्षेत्र मिलते हैं, इसलिए कुछ अर्थों में आप कुल गेम खेल रहे हैं। इस कोने की, उस कोने की चिंता करनी है. आप पूरी चीज़ जीतना चाहते हैं, लेकिन इसका मतलब यह नहीं है कि आपको हर हिस्सा जीतना होगा।

यह दार्शनिक रूप से दिलचस्प है, है ना? यह ऐसा है जैसे आपके पास एक युद्ध है, और इसमें कई लड़ाइयाँ हैं, लेकिन आपका ध्यान सीमित है। किसी भी क्षण आप युद्धक्षेत्रों में से किसी एक पर केवल एक ही निर्णय ले सकते हैं, और आपका प्रतिद्वंद्वी या तो प्रतिक्रिया दे सकता है या किसी अन्य युद्धक्षेत्र में दोगुना हो सकता है। मैं अपने पिता को यह समझाने की कोशिश कर रहा था।' जब आप कुल गेम खेलते हैं, तो इसका वास्तव में मतलब होता है: आप रणनीतिक रूप से कैसे हारते हैं?

हमने इसे दो गेमों के लिए साबित किया है, लेकिन आप तीन गेम एक साथ रख सकते हैं और प्रमेय अभी भी सच है: तीन बहुपद-समय वाले गेम एक साथ रखे जाने पर PSPACE-हार्ड बन सकते हैं।

चूंकि उन्होंने आपको कंप्यूटर विज्ञान की ओर प्रेरित किया, तो आपके पिता ने वर्षों में आपके द्वारा किए गए विभिन्न कार्यों पर क्या प्रतिक्रिया दी?

वह अक्सर मुझसे पूछते थे, "तुम ऐसा क्यों कर रहे हो?" सिद्धांत में काम करते हुए, अक्सर आपको वर्षों तक कोई परिणाम नहीं मिलता है, और वह धीरे-धीरे यह समझ गया। आरंभ में मैं परिमित-तत्व पद्धति के बारे में बात कर सकता था - वे इसे सिविल इंजीनियरिंग में भी पढ़ाते हैं। लेकिन मैं समझ नहीं पा रहा था कि इस मनोरंजक गणित के बारे में कैसे बात करूं।

फिर मैंने इस प्रसिद्ध चीनी उपन्यास से प्राप्त एक मुहावरे के बारे में सोचा जिसका नाम है तीन राज्यों के रोमांस. पात्रों में से एक, ज़ुगे लियांग, लगभग एक आदर्श रणनीतिकार था, और मुहावरा कहता है, "तीन जूते ठीक करने वाले ज़ुगे लियांग से बेहतर हैं।" इसका उपयोग इस हल्के-फुल्के अंदाज में यह कहने के लिए किया जाता है कि जब तीन औसत लोग एक साथ दिमाग लगाते हैं तो वे परिपूर्ण हो सकते हैं। लेकिन जब आप इस मुहावरे के इतिहास को देखते हैं, तो विभिन्न क्षेत्रों में चीजों का उच्चारण अलग-अलग किया जाता था, और "जूता ठीक करने वाले" की ध्वनि "फ़ील्ड जनरल" के समान ही थी। तो यह कहता है, "तीन फील्ड जनरल एक साथ इस आदर्श रणनीतिकार से बेहतर हैं।"

मैंने अपने पिता से कहा कि यह बिल्कुल वही प्रमेय है जिसे हमने खेलों के योग से सिद्ध किया है। फ़ील्ड जनरल बहुपद-समय के खेल [हल करने के लिए एल्गोरिदम] का प्रतिनिधित्व करते हैं: प्रत्येक युद्ध के मैदान पर, वे जानते हैं कि कैसे जीतना है। लेकिन कठिन हिस्सा यह जानना है कि कब हारना है, न कि प्रत्येक घटक गेम को कैसे जीतना है। यदि कोई वह कठिन खेल खेल सकता है, तो वह वास्तव में सबसे अच्छा रणनीतिकार है। फ़ील्ड जनरल ऐसे गहरे तर्कपूर्ण निर्णय नहीं लेते हैं, लेकिन अगर आप उन्हें अच्छी तरह से एक साथ रखते हैं, तो वे इस आदर्श रणनीतिकार से बदतर नहीं हैं।

मैंने अपने पिताजी से कहा, "आखिरकार मुझे इस गणित प्रमेय का एहसास हुआ जो हमारे प्रसिद्ध मुहावरों में से एक के बराबर है!" वह उस समय 94 वर्ष के थे, बहुत तेज़, और उन्होंने कहा, "यह एक अच्छा प्रयास है।" मैंने उसे पूरी तरह आश्वस्त नहीं किया। वह उनके साथ मेरी आखिरी तकनीकी बातचीत थी; कुछ महीने बाद वह गुजर गया। जब भी मैं अपने काम को समझाने के बारे में सोचता हूं तो यही मेरा मुख्य आकर्षण होता है।