हिकारू नाकामुरा, जिन्होंने हाल ही में एक कंप्यूटर को चुनौती दी थी।

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

यदि आप रुचि रखते हैं कि शतरंज के इंजनों को कैसे व्यवस्थित किया जाए, तो बिल्ली का स्वागत करें।

परिचय

एक बार मुझे यकीन था कि शतरंज के कार्यक्रम (वे भी इंजन हैं, लेकिन उस पर बाद में और अधिक) बस खेले जाने वाले खेलों को ध्यान में रखें और उनमें अपनी वर्तमान स्थिति का पता लगाएं और सही कदम उठाएं। मेरी राय में, मैंने किसी किताब में इसके बारे में पढ़ा।

यह निस्संदेह एक बहुत ही भोली राय है। शतरंज में एक नई स्थिति दसवीं चाल से प्राप्त की जा सकती है। हालाँकि गो में शतरंज की तुलना में कम स्थान हैं , फिर भी, 3 चालों के बाद (एक चाल सफेद और काले रंग की एक चाल है, एक अर्ध-चाल केवल एक तरफ की चाल है) चालों के पेड़ में लगभग 120 मिलियन नोड्स होते हैं। इसके अलावा, प्रारंभिक स्थिति से 14 अर्ध-चाल के बाद पेड़ का आकार उत्साही लोगों द्वारा एक वर्ष से अधिक समय तक माना जाता रहा है , अब तक लगभग एक तिहाई से उन्नत है।

मैंने यह भी सोचा कि शतरंज के कार्यक्रम, लंबे समय के बावजूदविश्व चैंपियन पर मैच जीतना अभी भी सर्वश्रेष्ठ लोगों की पहुंच के भीतर है। यह भी सच नहीं है।

में हाल ही में एक मिनी मैच मानव मशीन, हिकारू नाकामुरा , में से एक सबसे मजबूत खिलाड़ियों दुनिया में, के साथ खेला Komodo , (दो) में से एक सबसे मजबूत शतरंज कार्यक्रमों दुनिया में। कार्यक्रम को 24-कोर Xeon पर लॉन्च किया गया था। चूंकि लोग अब कंप्यूटर के साथ समान शर्तों पर प्रतिस्पर्धा नहीं कर सकते, इसलिए ग्रैंडमास्टर को 4 खेलों में से प्रत्येक में एक हेड स्टार्ट मिला:

पहले गेम में - एक प्यादा और एक चाल: कंप्यूटर ने ब्लैक खेला और प्यादा f7 के बिना
दूसरे में - केवल एक प्यादा: कंप्यूटर बिना प्यादा f2 के सफेद रंग का खेला
तीसरे में - गुणवत्ता (एक बदमाश और एक हल्के टुकड़े के बीच का अंतर लगभग 2 प्यादों का अनुमान लगाया गया है): एक श्वेत कंप्यूटर बिना एक किश्ती a1, एक आदमी बिना एक बी 8 नाइट और एक बदमाश a8 अपनी जगह पर।
चौथी - चार चालों में: एक व्यक्ति सफेद खेलता है और पहली चाल के बजाय वह बोर्ड के मध्य को पार किए बिना 4 चाल चलता है।

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

इसके अलावा, खेल 45 "+15 'के नियंत्रण के साथ खेले गए, यानी प्रति खेल 45 मिनट और इसके अलावा 15 सेकंडहर कदम। आमतौर पर, छोटे नियंत्रण कंप्यूटर को एक अतिरिक्त लाभ देते हैं, जबकि लंबे समय तक किसी व्यक्ति के अवसरों को थोड़ा बढ़ाते हैं। एक विभाजित सेकंड में भी, कंप्यूटर खुले तौर पर खोने वाली चालों को स्वीप करने का प्रबंधन करेगा, जबकि वेरिएंट ट्री की घातीय वृद्धि के कारण, विश्लेषण में प्रत्येक बाद के सुधार में अधिक समय लगता है।

हालांकि, एक बाधा थी और वह व्यक्ति 2.5-1.5 से हार गया, जिसने पहले 3 गेम ड्रा किए और चौथा हार गया। उसी समय, कमजोर ग्रैंडमास्टर ने काफी आत्मविश्वास से जीत हासिल की2 प्यादों के विकलांग के साथ। इसलिए, इस समय सबसे अच्छे लोगों पर सबसे अच्छे कार्यक्रमों का लाभ विकलांगों के 1 और 2 प्यादों के बीच है। बेशक, यह मूल्यांकन बहुत कठिन है, लेकिन एक सटीक मूल्यांकन के लिए लोगों और कार्यक्रमों के बीच कई हजार खेल खेलना आवश्यक है, और यह संभावना नहीं है कि कोई भी ऐसा करेगा। कृपया ध्यान दें कि अक्सर कार्यक्रमों के लिए इंगित की जाने वाली ELO रेटिंग का लोगों की रेटिंग से कोई लेना-देना नहीं है।

शतरंज इंजन क्या है?

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

वे अभी भी कैसे खेलते हैं?

तो, एक आधुनिक शतरंज इंजन कैसे काम करता है?

बोर्ड प्रस्तुति

किसी भी इंजन का आधार शतरंज की बिसात है। सबसे पहले, कंप्यूटर को शतरंज के सभी नियमों को "समझाना" आवश्यक है और यह शतरंज की स्थिति को बनाए रखने का अवसर देता है। इसके बिना, स्थिति का मूल्यांकन करना और चाल बनाना असंभव है।

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

Bitboards

सौभाग्य से, शतरंज की बिसात पर 64 कोशिकाएँ होती हैं। इसलिए, यदि हम प्रत्येक सेल के लिए एक बिट का उपयोग करते हैं, तो हम पूरे बोर्ड को 64-बिट पूर्णांक में संग्रहीत कर सकते हैं।
एक चर में हम सभी सफेद टुकड़ों को संग्रहीत करेंगे, दूसरे में - सभी काले वाले, और दूसरे 6 में - प्रत्येक प्रकार के आंकड़े अलग-अलग (प्रत्येक रंग के लिए एक और विकल्प 12 बिटबोर्ड हैं और अलग-अलग आंकड़े के प्रकार)।

इस विकल्प का क्या फायदा है?
पहली स्मृति है। जैसा कि हम बाद में सीखते हैं, विश्लेषण के दौरान, बोर्ड के प्रतिनिधित्व को कई बार कॉपी किया जाता है, और, तदनुसार, रैम खाती है। बिटबोर्ड सबसे कॉम्पैक्ट शतरंजबोर्ड अभ्यावेदन में से एक है।
दूसरी बात, गति। कई गणनाएं, उदाहरण के लिए, संभव चाल की गणना, कई बिट संचालन के लिए नीचे आती हैं। इसके कारण, उदाहरण के लिए, POPCNT अनुदेश का उपयोग करके आधुनिक इंजनों को ~ 15% त्वरण दिया जाता है। इसके अलावा, बिटबोर्ड के अस्तित्व के दौरान, कई एल्गोरिदम और अनुकूलन का आविष्कार किया गया था, जैसे कि, "जादू" बिटबोर्ड ।

खोज

अल्पमहिष्ठ

अधिकांश शतरंज इंजनों के दिल में मिनिमैक्स सर्च अल्गोरिथम या गैर-हमैक्स का संशोधन होता है। संक्षेप में, हम पेड़ के नीचे जाते हैं, पत्तियों का मूल्यांकन करते हैं, और फिर ऊपर जाते हैं, हर बार वर्तमान खिलाड़ी के लिए इष्टतम चाल चुनते हैं, एक (काले) के लिए स्कोर को कम करते हुए और दूसरे (सफेद) के लिए अधिकतम करते हैं। इसलिए नाम। एक बार रूट में, हमें चालों का एक क्रम मिलता है जो दोनों खिलाड़ियों के लिए इष्टतम है। मिनिमैक्स और नॉन-हैमैक्स के बीच का अंतर यह है कि पहले मामले में, हम अधिकतम और न्यूनतम रेटिंग के साथ चालें चुनते हैं, और दूसरे में, इसके बजाय, सभी रेटिंग्स के लिए संकेत बदलते हैं और हमेशा अधिकतम चुनें (हम समझ गए कि वे कहां से आए हैं)। अधिक यहाँ और यहाँ ।

अल्फा बीटा

पहला अनुकूलन अल्फा बीटा है । अल्फा-बीटा का विचार सरल है - अगर मेरे पास पहले से ही एक अच्छी चाल है, तो आप चालें काट सकते हैं, जो स्पष्ट रूप से बदतर हैं। बाईं ओर खौफनाक तस्वीर में उदाहरण पर विचार करें। मान लीजिए कि खिलाड़ी A में 2 संभावित चालें हैं - a3 और b3। ए 3 के पाठ्यक्रम का विश्लेषण करने के बाद, कार्यक्रम को +1.75 की रेटिंग मिली। मूव बी 3 का मूल्यांकन करना शुरू करते हुए, कार्यक्रम ने देखा कि खिलाड़ी बी में दो चालें हैं - a6 और a5। पाठ्यक्रम का मूल्यांकन a6 +0.5। चूंकि खिलाड़ी बी न्यूनतम स्कोर के साथ एक चाल का चयन करता है, वह 0.5 से अधिक के स्कोर के साथ एक चाल का चयन नहीं करेगा, जिसका अर्थ है कि b3 के चाल का अनुमान 0.5 से कम है, और इस पर विचार करने का कोई मतलब नहीं है। इस प्रकार, बी 3 के शेष उपप्रकार को काट दिया जाता है।

कतरन के लिए, हम ऊपरी और निचली सीमाओं - अल्फा और बीटा को संग्रहीत करते हैं। यदि विश्लेषण के दौरान एक चाल बीटा से अधिक अंक प्राप्त करती है, तो वर्तमान नोड काट दिया जाता है। यदि स्कोर अल्फा से अधिक है, तो अल्फा को अपडेट किया जाता है।

अल्फा बीटा में नोड्स को 3 श्रेणियों में विभाजित किया गया है:

पीवी-नोड्स - नोड्स जिनका मूल्यांकन खिड़की (अल्फा और बीटा के बीच) में गिर गया। रूट और लेफ्टेस्ट नोड हमेशा इस प्रकार के नोड होते हैं।
कट-नोड्स (या असफल-उच्च नोड्स ) - नोड्स जिसमें बीटा कट-ऑफ हुआ।
ऑल-नोड्स (या विफल-कम नोड्स ) - नोड्स जिसमें मूल्यांकन के अनुसार कोई भी चाल अल्फा से अधिक नहीं थी।

छंटनी की चाल

अल्फा बीटा का उपयोग करते समय, चाल का क्रम महत्वपूर्ण हो जाता है। यदि हम सबसे अच्छा कदम पहले रख सकते हैं, तो बीटा कटऑफ के कारण शेष चालों का बहुत तेजी से विश्लेषण किया जाएगा।

पिछले चलना से हैश और सबसे अच्छे कदम का उपयोग करने के अलावा, छंटाई चाल के लिए कई तकनीकें हैं।

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

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

हैश टेबल या क्रमपरिवर्तन टेबल

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

Iterative खोज

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

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

खोज की अवधि

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

ऐसा करने के लिए, स्थैतिक मूल्यांकन करने से पहले, हम सभी कैप्चर (कभी-कभी चेकर्स) की भी जांच करते हैं और पेड़ को ऐसी स्थिति में ले जाते हैं जिसमें कोई संभावित कैप्चर और चेकर्स नहीं होते हैं। स्वाभाविक रूप से, यदि सभी कैप्चर अनुमान को खराब करते हैं, तो हम वर्तमान स्थिति का अनुमान वापस करते हैं।

चयनात्मक खोज

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

कैप्टर्स, चेकर्स के मामले में गहराई बढ़ जाती है, अगर यह कदम विकल्पों में से केवल एक या बहुत बेहतर है या यदि एक पारित मोहरा है।

कतरन और काटना

कटौती और कटौती के साथ, सब कुछ बहुत दिलचस्प है। वे पेड़ के आकार को काफी कम कर सकते हैं।

संक्षेप में कतरन के बारे में:

- — , . , , . , , , , .
— , -. , , . (1-2).
— , , . . PV . .
Multi-Cut — M(, 6) C(, 3) Cut-node, .
null- — null- ( ) , . , , , , .

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

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

नेगास्काउट और पीवीएस

दो बहुत ही समान तकनीकें जो इस तथ्य का उपयोग करती हैं कि जब हम पीवी-नोड पाते हैं (हमारी चालों को बहुत अच्छी तरह से हल किया जाता है), तो यह सबसे अधिक संभावना नहीं बदलेगी, अर्थात्, शेष सभी नोड्स अल्फा की तुलना में कम रेटिंग वापस करेंगे। इसलिए, हम अल्फा से बीटा में एक खिड़की से खोज करने के बजाय, हम अल्फा से अल्फा + 1 तक एक खिड़की के साथ खोज करते हैं, जो हमें खोज को गति देने की अनुमति देता है। बेशक, अगर कुछ नोड में हमें बीटा क्लिपिंग मिलती है, तो इसे फिर से सराहना मिलनी चाहिए, पहले से ही एक सामान्य खोज द्वारा।

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

समानांतर खोज

अल्फा बीटा का समानांतरकरण एक अलग बड़ा विषय है। मैं इसके बारे में संक्षेप में बताऊंगा, और जो परवाह करता है, साझा मेमोरी मल्टीप्रोसेसर पर समानांतर अल्फा-बीटा खोज की जाँच करें । कठिनाई यह है कि एक समानांतर खोज में, कई थ्रेड-नोड्स का खंडन करने से पहले विश्लेषण किया जाता है कि एक थ्रेड फटने (बीटा स्थापित करता है), जबकि क्रमिक खोज में, अच्छी छँटाई के साथ, इनमें से कई नोड्स काट दिए जाएंगे।

आलसी एसएमपी

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

यंग ब्रदर्स वेट कॉन्सेप्ट (YBWC)

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

डायनेमिक ट्री स्प्लिटिंग (DTS)

फास्ट और जटिल एल्गोरिथ्म। गति के बारे में थोड़ा: खोज की गति को ttd (समय से गहराई तक) के माध्यम से मापा जाता है, अर्थात, वह समय जिसके दौरान खोज एक निश्चित गहराई तक पहुँचती है। यह सूचक आमतौर पर इंजन के विभिन्न संस्करणों या कोर की एक अलग संख्या पर चलने वाले इंजन के काम की तुलना करने के लिए इस्तेमाल किया जा सकता है (हालांकि कोमोडो, उदाहरण के लिए, अधिक कोर के साथ पेड़ की चौड़ाई बढ़ जाती है)। इसके अलावा, ऑपरेशन के दौरान, इंजन nps (प्रति सेकंड नोड्स) में खोज की गति प्रदर्शित करता है। यह मीट्रिक बहुत अधिक लोकप्रिय है, लेकिन यह इंजन को खुद से तुलना करने की अनुमति भी नहीं देता है। आलसी एसएमपी, जिसमें कोई सिंक्रनाइज़ेशन नहीं है, लगभग रैखिक रूप से एनपीएस बढ़ता है, लेकिन बड़ी मात्रा में अनावश्यक काम के कारण इसकी टीटीडी इतनी प्रभावशाली नहीं है। जबकि DTS के लिए, nps और ttd लगभग समान ही बदलते हैं ।

सच कहूं तो, मैं अभी भी इस एल्गोरिदम का पूरी तरह से पता नहीं लगा सका हूं, जो इसकी उच्च दक्षता के बावजूद, इंजन की एक जोड़ी में शाब्दिक रूप से उपयोग किया जाता है। जिनके लिए यह बहुत दिलचस्प है, ऊपर दिए गए लिंक का पालन करें।

मूल्यांकन

इसलिए, हम आवश्यक गहराई तक पहुंच गए हैं, शांत की खोज की है और आखिरकार, हमें स्थिर स्थिति का मूल्यांकन करने की आवश्यकता है।

कंप्यूटर प्यादों में स्थिति का मूल्यांकन करता है: +1.0 का अर्थ है कि व्हाइट में 1 मोहरे के बराबर एक फायदा है, -0.5 का मतलब है कि ब्लैक को आधे मोहरे का एक फायदा है। चटाई का अनुमान 300 प्यादों पर लगाया गया है, और मटका एक्स की चालों की संख्या ज्ञात है (300-0.01x) प्यादों पर। +299.85 का मतलब है कि व्हाइट 15 चालों में संभोग करता है। इस मामले में, कार्यक्रम आमतौर पर सेंटीपीस (1/100 प्यादे) में पूरे अनुमानों के साथ संचालित होता है।

किसी स्थिति का मूल्यांकन करते समय कंप्यूटर किस पैरामीटर को ध्यान में रखता है?

सामग्री और गतिशीलता

सबसे सरल बात। रानी 9-12 प्यादे हैं, किश्ती 5-6, नाइट और बिशप 2.5-4 और मोहरा, क्रमशः, एक मोहरा। सामान्य तौर पर, एक सामग्री किसी स्थिति का मूल्यांकन करने के लिए एक योग्य उत्तराधिकार है और किसी भी स्थितिगत लाभ आमतौर पर एक सामग्री में अंत में बदल जाता है।

गतिशीलता को सरल माना जाता है - वर्तमान स्थिति में संभावित चाल की संख्या। उनमें से अधिक, खिलाड़ी की सेना के लिए अधिक मोबाइल।

आकृति स्थिति तालिकाओं

बोर्ड के कोने में शूरवीर आमतौर पर खराब होता है, दुश्मन के पीछे के करीब पंजे अधिक मूल्यवान हो जाते हैं और इसी तरह। प्रत्येक आंकड़े के लिए, बोर्ड पर अपनी स्थिति के आधार पर बोनस और दंड की एक तालिका संकलित की जाती है।

प्यादा संरचना

डबल पंजे - एक ही ऊर्ध्वाधर पर दो पंजे। कमजोरी माने जाने वाले अन्य प्यादों के साथ अक्सर उनका बचाव करना मुश्किल होता है।
— , . , .
— , . ,
— , . , .

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

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

अन्य

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

सटीक रेटिंग या त्वरित खोज?

पारंपरिक विवाद: जो अधिक प्रभावी है, स्थिति का सही आकलन करता है या अधिक खोज गहराई प्राप्त करता है। अनुभव से पता चला है कि अत्यधिक "भारी" मूल्यांकन कार्य अप्रभावी हैं। दूसरी ओर, अधिक विस्तृत आकलन, अधिक कारकों को ध्यान में रखते हुए, आमतौर पर अधिक "सुंदर" और "आक्रामक" खेल की ओर जाता है।

डेब्यू की किताबें और एंडगेम टेबल

पुस्तकों का विमोचन

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

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

एंडगेम टेबल

वापस परिचय के लिए। स्मृति में कई पदों को संग्रहीत करने और सही चुनने का विचार याद रखें। वहाँ वह है। आंकड़ों की एक छोटी (7 तक) संख्या के लिए, सभी मौजूदा पदों की गणना की जाती है। यही है, इन पदों में कंप्यूटर पूरी तरह से खेलना शुरू कर देता है, न्यूनतम संख्या में चाल में जीतता है। माइनस - पीढ़ी का आकार और समय। इन तालिकाओं के निर्माण ने एंडगेम के अध्ययन में मदद की।

टेबल पीढ़ी

हम आकृतियों के एक निश्चित समूह के साथ सभी संभव (खाते की समरूपता में) स्थिति उत्पन्न करते हैं। उनमें से हम उन सभी पदों को ढूंढते और नामित करते हैं जहां चटाई खड़ी है। अगले पास तक, हम सभी पदों को निरूपित करते हैं जिसमें आप एक चटाई के साथ स्थिति में आ सकते हैं - इन पदों में 1 मोड़ में एक चटाई डाल दी जाती है। इस प्रकार हम सभी पदों को 2,3,4, 549 चालों के साथ पाते हैं । सभी अचिह्नित पदों में - एक ड्रा।

नलिमोव टेबल्स

पहला एंडगेम टेबल 1998 में वापस प्रकाशित हुआ। प्रत्येक स्थिति के लिए, खेल के परिणाम और एक आदर्श खेल के साथ चटाई पर ले जाने की संख्या संग्रहीत की जाती है। सभी छह-आंकड़ा अंत का आकार 1.2 टेराबाइट है।

लोमोनोसोव टेबल्स

2012 में, मॉस्को स्टेट यूनिवर्सिटी में सभी सात-आंकड़ा अंत (6 बनाम 1 को छोड़कर) को लोमोनोसोव सुपर कंप्यूटर पर गिना गया । ये आधार केवल पैसे के लिए उपलब्ध हैं और ये केवल मौजूदा पूर्ण सात-आंकड़ा एंडगेम टेबल हैं।

syzygy

डी वास्तविक मानक। ये ठिकाने नलिमोव ठिकानों की तुलना में बहुत अधिक कॉम्पैक्ट हैं। वे दो भागों से मिलकर बने होते हैं - डब्ल्यूडीएल (विन ड्रा लोस) और डीटीजेड (शून्य करने के लिए दूरी)। खोज के दौरान उपयोग के लिए डब्ल्यूडीएल डेटाबेस का इरादा है। एक बार ट्री नोड को तालिका में पाए जाने के बाद, हमारे पास इस स्थिति में गेम का सटीक परिणाम है। DTZ रूट में उपयोग के लिए अभिप्रेत है - वे चालों की संख्या को नल के काउंटर काउंटर तक ले जाते हैं (प्यादा या कब्जा करके चलते हैं)। इस प्रकार, डब्ल्यूडीएल आधार विश्लेषण के लिए पर्याप्त हैं, और DTZ आधार एंडगेम्स का विश्लेषण करने में उपयोगी हो सकते हैं। सिज़ीजी बहुत छोटा है - छह-अनुमानित डब्ल्यूडीएल के लिए 68 गीगाबाइट और डीटीजेड के लिए 83। कोई सात-आंकड़ा आधार नहीं हैं, क्योंकि उनकी पीढ़ी को लगभग टेराबाइट्स रैम की आवश्यकता होती है।

के उपयोग

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

अन्य रोचक

जिराफ़ या तंत्रिका नेटवर्क शतरंज खेलते हैं

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

ट्यूनिंग पैरामीटर्स

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

सूखी हुई मछली

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

उनका समाधान खुले स्रोत के लिए विशिष्ट है - स्वयंसेवक उन्हें सैकड़ों हजारों गेम चलाने की शक्ति प्रदान करते हैं।

धम

एक प्रोग्राम जो रैखिक प्रतिगमन के माध्यम से मापदंडों का अनुकूलन करता है, विभिन्न मापदंडों के साथ स्वयं के साथ इंजन गेम के परिणामों का उपयोग करता है। Minuses की - एक बहुत ही सीमित कार्य आकार: सौ मापदंडों (इंजन के लिए पूरी तरह से पर्याप्त संख्या) का अनुकूलन करने के लिए यह संभव नहीं है, कम से कम पर्याप्त समय के लिए।

टेक्सल की ट्यूनिंग

पिछली विधि की समस्या को हल करता है। हम बड़ी संख्या में पदों को लेते हैं (लेखक ने 64,000 खेलों से 9 मिलियन पदों की पेशकश की, मैंने लगभग 200,000 में से 8 मिलियन लिया), प्रत्येक के लिए हम खेल के परिणाम को बचाते हैं (व्हाइट ने 1 जीता, ड्रॉ 0.5, पराजित 0)। अब हम त्रुटि को कम करते हैं, जो कि परिणाम के अंतर के वर्गों का योग है और अनुमान का सिग्मोइड है। विधि प्रभावी और लोकप्रिय है, लेकिन यह सभी इंजनों पर काम नहीं करता है।

स्टॉकफिश ट्यूनिंग

नेता से एक और तकनीक। हम एक्स के बराबर एक पैरामीटर लेते हैं, और एक्स-सिग्मा और एक्स + सिग्मा के बराबर पैरामीटर वाले इंजन की तुलना (कई हजारों में कई टन) करते हैं। यदि बड़े पैरामीटर वाला इंजन जीता है, तो इसे थोड़ा ऊपर ले जाएं, अन्यथा - थोड़ा नीचे, और दोहराएं।

इंजन प्रतियोगिताओं

प्रतियोगिताओं के सभी आयोजित परीक्षण में, मैं टीसीईसी को अलग से अलग करना चाहूंगा । यह अपने शक्तिशाली हार्डवेयर, उद्घाटन और लंबे नियंत्रण के सावधानीपूर्वक चयन से अन्य सभी से अलग है। अंतिम फाइनल में, 180 x + 30 "नियंत्रण के साथ 256 गीगाबाइट रैम के साथ 2 x Intel Xeon E5-2690v3 पर 100 गेम खेले गए। ऐसी परिस्थितियों में, ड्रॉ की संख्या बहुत बड़ी थी, और केवल 11 गेम प्रभावी थे।

निष्कर्ष

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

शतरंज की प्रोग्रामिंग विकि
टॉकलेस फोरम
और दूसरा, पहले उल्लेख नहीं किया गया - प्रोग्रामर कॉर्नर

कंप्यूटर शतरंज कैसे खेलता है?