कई लोग सेटी @ होम प्रोजेक्ट से परिचित हैं: दुनिया भर के लाखों कंप्यूटरों की क्षमता ("मैट्रिक्स") का उपयोग करते हुए, आकाश से प्राप्त आंकड़ों के समुद्र में अलौकिक सभ्यताओं के निशान खोजने के लिए एक शक्तिशाली पहल।

हालाँकि अभी तक एलियन की खोज नहीं की गई है, सेटी @ होम काफी बड़े पैमाने पर वितरित कंप्यूटिंग की क्षमता को सफलतापूर्वक प्रदर्शित करता है। BOINC जैसी परियोजनाओं ने अन्य क्षेत्रों में भी इसी तरह की पहल की है: जीव विज्ञान, चिकित्सा और भौतिकी।

पिछले सप्ताहांत में, जोशफायर टीम ( थॉमस , नाथन , माइकल और आई ) ने 48 घंटे की नोड नॉकआउट प्रतियोगिता में भाग लिया। नियम सरल थे: सप्ताहांत में सबसे व्यस्त चीज़ को एनकोड करें, जो सर्वर-साइड जावास्क्रिप्ट का उपयोग करता है।

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

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

हम में से कोई भी एक अच्छा शतरंज खिलाड़ी नहीं है, लेकिन गिनीज बुक ऑफ रिकॉर्ड्स में हमने सबसे बड़े शतरंज एआई का उल्लेख पाया, जिसमें 2070 नोड्स शामिल थे, और फैसला किया कि हम उसे हरा सकते हैं। इसलिए शतरंज @ घर परियोजना का जन्म हुआ।

48 घंटों के बाद, प्रोटोटाइप में अभी भी कई बग थे, लेकिन यह पूरी तरह से खेलने योग्य स्थिति में था और इस तरह दिखता था:

वितरित शतरंज एआई की समस्याएं

अध्ययन शुरू करते हुए, हमने निम्नलिखित समस्या क्षेत्रों की पहचान की:

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

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

समानांतरवाद। प्रतिक्रिया समय का अनुकूलन करने का मतलब है कि आपको प्रत्येक कैलकुलेटर पर प्रसंस्करण के लिए छोटे वॉल्यूम भेजने की आवश्यकता है। इसलिए हमें यह पता लगाना था कि कोड गणना को हजारों छोटे टुकड़ों में कैसे तोड़ा जाए।

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

• कैलकुलेटर आम तौर पर आम चर पर निर्भर नहीं होना चाहिए वेब सॉकेट क्लाइंट-क्लाइंट योजना के अनुसार काम नहीं करते हैं (और सर्वर के माध्यम से डेटा को चलाने से स्केलिंग में हस्तक्षेप होता है);
  
• प्रत्येक चाल की गणना को हजारों छोटे कार्यों में विभाजित किया जाना चाहिए।
  

हमें दो संभावित उम्मीदवार मिले: APHID (सरल, ChessBrain.net , वर्तमान गिनीज वर्ल्ड रिकॉर्ड चैंपियन) और YBWC भिन्नताएं (कठिन लेकिन अधिक कुशल)। 48-घंटे की कोडिंग सीमा के साथ, हमने APHID के साथ शुरुआत करने का निर्णय लिया।

जावास्क्रिप्ट प्रदर्शन । सबसे ठंडा शतरंज AI सबसे उन्नत लोहे का उपयोग करके 15 मिलियन ट्री नोड्स प्रति सेकंड (NPS = नोड्स प्रति सेकंड) की यात्रा कर सकता है। हमने GarboChess को लिया, जावास्क्रिप्ट के साथ एक ओपन-सोर्स शतरंज एआई, जिसका प्रदर्शन आधुनिक मैकबुक प्रो पर क्रोम के लिए 100k एनपीएस है। 150 के गुणांक ने हमें बहुत परेशान नहीं किया, खासकर 48 घंटों के बाद से हमारे पास उस कोड को प्रोफाइल करने और अनुकूलित करने का समय नहीं होगा जो केवल एक कंप्यूटर का उपयोग करके हम में से किसी को हरा सकता है।

संदर्भ के लिए, वे कहते हैं कि डीप ब्लू ने कास्परोव को हराने के लिए 200 मीटर एनपीएस की गति से काम किया, जो सामान्य रूप से हमारे 2070-नोड लक्ष्य पर सैद्धांतिक रूप से प्राप्त करने योग्य था।

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

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

48 घंटों में प्रोटोटाइप का कार्यान्वयन

यहाँ हमारे प्रोटोटाइप का आरेख है:


आइए मुख्य घटकों का विश्लेषण करें:

• dnode । दो-तरफा अतुल्यकालिक दूरस्थ विधि कॉल के लिए Node.js लाइब्रेरी। यह सॉकेट और वेब सॉकेट (सॉकेट का उपयोग करके ) की शैली में परिवहन प्रदान करता है ताकि सिस्टम प्रक्रियाएं एक-दूसरे के साथ और एक ही इंटरफ़ेस का उपयोग करके ब्राउज़र में चलने वाली प्रक्रियाओं के साथ संवाद कर सकें। हमने लगभग सभी नेटवर्क इंटरैक्शन के लिए इसका उपयोग किया।
  
• वेब वर्कर्स (वेब कंप्यूटर)। एकल-थ्रेड (एकल-थ्रेड) जावास्क्रिप्ट वातावरण जो एकल स्क्रिप्ट के निष्पादन को सीमित करता है ताकि उपयोगकर्ता इंटरफ़ेस लटका न हो। वेब वर्कर्स हमें कम्प्यूटेशनल रूप से मांग वाले कार्यों को हल करने के लिए बड़े रनटाइम के साथ स्क्रिप्ट चलाने की अनुमति देते हैं, लेकिन इंटरफ़ेस या अन्य उपयोगकर्ता इंटरैक्शन स्क्रिप्ट को अवरुद्ध किए बिना। सर्वर साइड पर, हमने नोड-वेबवर्क (वेब वर्कर के लिए नोड का एक कार्यान्वयन) का उपयोग किया था, इसलिए हमारे पास एआई के साथ संवाद करने के लिए एक ही इंटरफ़ेस था।
  
• MongoDB । MongoHQ ने नोड नॉकआउट को प्रायोजित किया, और हमने गेम स्टेट्स और एक संभावित बड़ी स्थिति कैश को स्टोर करने के लिए MongoDB के ऑफ-द-शेल्फ उदाहरणों का उपयोग करने का निर्णय लिया।
  
• नोड वास्तुकला में केंद्रीय लिंक, नोड में दोनों तेजी से विकास (सर्वर और क्लाइंट दोनों पर समान कोड) और उच्च प्रदर्शन (इसकी गैर-अवरुद्ध I / O प्रतिमान इसकी प्रतिस्पर्धी क्षमता और गति की पुष्टि की है)।
  
• सर्वर पर स्थानीय ए.आई. इस जगह को स्पष्ट रूप से छोटा नहीं किया गया है, लेकिन फिर भी हमें सर्वर पर कई एआई कॉल करने पड़ते हैं, मुख्यतः क्योंकि क्लाइंट के बीच काम को वितरित करने के लिए APHID को एक छोटे पेड़ की शुरुआत में बनाया जाना चाहिए। शायद भविष्य में हम इसे हटा देंगे।
  

इस कार्यान्वयन में सुधार करने के लिए कुछ है, लेकिन यह मत भूलो - सब कुछ 48 घंटों में किया गया था। लेकिन वेब वर्कर्स पर AI चलाने से ब्राउजर और सर्वर दोनों ही मुख्य विचार बने रहेंगे।

आगे क्या है

विगेट्स के लिए नैतिकता । आमतौर पर, अन्य लोगों की कंप्यूटिंग शक्ति का उपयोग करने के लिए, उनके मालिक की सहमति आवश्यक होती है: लोग SETI @ होम या BOINC सॉफ़्टवेयर स्थापित करते हैं, इस प्रकार उन्हें अपने प्रोसेसर तक पहुंचने की अनुमति मिलती है। जावास्क्रिप्ट आपको स्पष्ट अनुमति के बिना अन्य लोगों के प्रोसेसर का उपयोग करने की अनुमति देता है, आपको बस विजेट के साथ पृष्ठ पर जाना होगा, जो बहुत अच्छा नहीं है।

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

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

ऐ सुधार । कुछ शेष इंटरफ़ेस बग्स का पता लगाने के बाद, हम निम्नलिखित क्षेत्रों में AI अनुकूलन जारी रखेंगे:

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

घंटे X की योजना बनाएं। जब एआई पर्याप्त मजबूत हो जाता है, तो हम सबसे रोमांचक शतरंज खेल का संचालन करने के लिए असली फ्रांसीसी ग्रैंडमास्टर और गिनीज के प्रतिनिधि को बुलाएंगे!

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

यदि आपके पास अधिकतम लोगों को जोड़ने के बारे में विचार हैं, तो कृपया हमें बताएं! हम ऊपर वर्णित सभी चीजों से निपटने के लिए प्रतिभाशाली जावास्क्रिप्ट डेवलपर्स की भी तलाश कर रहे हैं।

यदि आप हमारी सहायता करना चाहते हैं, तो कार्यों की वर्तमान सूची देखें या शतरंज @ घर पर नए खोजने का प्रयास करें। मैट्रिक्स के साथ लड़ाई में गुड लक!

PS हमने पूर्णता की श्रेणी में नोड नॉकआउट जीता।

---

उन लोगों के लिए जो Habr का उपयोग करने में सक्षम नहीं हैं:

• अनूदित: असंबद्ध
• गीतकार: सिल्वेन ज़िमर
• मूल: शतरंज @ घर: अब तक का सबसे बड़ा शतरंज एआई का निर्माण