रोटेटेबल बिटबोर्ड: एक पुराने विचार का एक नया दौर

संक्षिप्त विवरण

यह लेख "बिटबोर्ड्स" (64-बिट पूर्णांक, जिनमें से प्रत्येक एक चेकबोर्डबोर्ड क्षेत्र का प्रतिनिधित्व करता है) का उपयोग करने की कुछ बारीकियों के बारे में बात करता है। 1994 में, केप मई, न्यू जर्सी में एसीएम शतरंज संगोष्ठी के बाद, मैंने क्रे ब्लिट्ज (रॉबर्ट हयात, हैरी नेल्सन द्वारा लिखित एक कंप्यूटर प्रोग्राम और क्रे सुपरकंप्यूटर के लिए गवर्निंग प्रोग्राम) को पूरी तरह से बदलने का फैसला किया - लगभग। अनुवाद।)। मुझे शतरंज 4.x में स्लेट और एटकिन द्वारा परीक्षण की गई बिटबोर्ड विधि की कोशिश करने में दिलचस्पी थी (इलिनोइस के नॉर्थवेस्टर्न यूनिवर्सिटी में विकसित एक शतरंज कार्यक्रम और 20 वीं सदी के 70 के दशक में हावी - लगभग। अनुवाद।)। अपने लिए तय करें कि यह शतरंज के लिए उपयुक्त है या नहीं। इस नए कार्यक्रम के विकास के दौरान, "रोटेटेबल बिटबोर्ड" की अवधारणा का आविष्कार किया गया था, और यह पता चला कि स्वीकार्य प्रदर्शन के साथ काम करने के लिए इस प्रकार की डेटा संरचना प्राप्त करने के लिए यह आवश्यक था।

1. परिचय

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

एक शतरंज की बिसात के क्षेत्रों के लिए प्रस्तावित मिलान बिट्स; 1 के मूल्य के साथ एक बिट एक शतरंज की बिसात पर एक टुकड़े की उपस्थिति के संकेत के रूप में सेवा की, जबकि बिट 0 ने इसकी अनुपस्थिति का संकेत दिया। इस प्रकार, सफेद_पॉइन बिटबोर्ड में, जो सफेद पंजे के कब्जे वाले खेतों से मेल खाता है, 1. 1 के मूल्य के साथ सबसे अधिक आठ बिट्स हो सकते हैं (इस लेख में, फ़ील्ड 0 से 63 तक गिने जाते हैं, जहां स्थिति 0 फ़ील्ड A1 से मेल खाती है, 7 फ़ील्ड H1, 56 से मेल खाती है। फ़ील्ड A8, और 63 से फ़ील्ड H8 से मेल खाती है। 64-बिट पूर्णांक में 0 की स्थिति वाले बिट्स को "सबसे महत्वपूर्ण बिट्स" कहा जाता है और 63 में बिट्स को "कम से कम महत्वपूर्ण बिट" कहा जाता है।) (सबसे महत्वपूर्ण बिट, एमएसबी। और कम से कम महत्वपूर्ण बिट, एलएसबी - लगभग अनुवाद।)

इन बारह 64-बिट शब्दों में बोर्ड पर स्थिति की जानकारी संग्रहीत करने के अलावा, स्लेट और एटकिन ने एक अलग तरह की जानकारी के लिए इच्छित बिटबोर्ड के दो अतिरिक्त सेटों को उत्पन्न करने और बाद में अपडेट करने का वर्णन किया। attack_from [64] - प्रत्येक फ़ील्ड के लिए 1 के मान के साथ बिटबोर्ड की एक सरणी जिसे किसी दिए गए फ़ील्ड पर खड़े एक आकृति द्वारा हमला किया जा सकता है। उदाहरण के लिए, attack_from [E4] हमें फ़ील्ड E4 पर खड़े एक आकृति द्वारा सीधे हमला करता है। इसके अलावा, attack_to [64] सरणी में इस क्षेत्र पर हमला करने वाले आंकड़े द्वारा कब्जा किए गए सभी क्षेत्रों के लिए बिट 1 के साथ बिटबोर्ड होते हैं। उदाहरण के लिए, attack_to [E4] एक बिटबोर्ड है जिसमें बोर्ड पर सभी फ़ील्ड्स के लिए बिट्स 1 होता है, जहां एक हड़ताली फ़ील्ड E4 आकृति होती है।

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

बिटबोर्ड के अन्य उपयोगी गुण हैं जो उन्हें शतरंज कार्यक्रमों में बहुत उपयोगी बनाते हैं। इन गुणों में से एक ऐसी चीज है जिसे "बिट-समानांतर" ऑपरेशन कहा जा सकता है। उदाहरण के लिए, पारंपरिक शतरंज कार्यक्रमों में, यदि आपका मोहरा E4 फ़ील्ड पर है और आप चेक करना चाहते हैं कि क्या यह एक चेकपॉइंट है, तो आपको D5, E5, F5, D6, E6, F6, D6, D7, E7, F7 फ़ील्ड चेक करना होगा सुनिश्चित करें कि कोई दुश्मन प्यादे नहीं हैं। इसके लिए नौ तुलनात्मक संचालन की आवश्यकता है। बिटबोर्ड का उपयोग करते हुए, आपको बस प्रत्येक फ़ील्ड के लिए मास्क की सरणी की पूर्व-गणना करने की आवश्यकता है जहां प्यादा खड़े हो सकते हैं, और फिर is_passed_white [E4] मास्क लें और काले पंजे के लिए बिटबोर्ड के साथ "और" ऑपरेशन करें। यदि आपने मुखौटे की सही गणना की है, ताकि नौ शीर्ष क्षेत्रों में से प्रत्येक में इकाइयां हों, तो एक और ऑपरेशन काले पंजे की अनुपस्थिति या, इसके विपरीत, उनकी उपस्थिति निर्धारित कर सकता है, जो ई 4 पर सफेद मोहरे को पारित करने की अनुमति नहीं देगा। वास्तव में, हमने समानांतर में 9 अलग-अलग चेक किए और एक ही ऑपरेशन के साथ एक ही समय में नौ सवालों के जवाब दिए।

अन्य फायदे हैं, लेकिन इस लेख का विषय रोटेटेबल बिटबोर्ड है और उन्हें कैसे उपयोग किया जा सकता है, जैसा कि हमलों से डेटा प्राप्त करने के लिए आवश्यक है [64] और हमलों_को [64] सरणियों, निरंतर अपडेट द्वारा लगाए गए प्रतिबंधों के बिना, और जटिल / धीमी चक्रों के बिना। ।

2. साधारण बिटबोर्ड का उपयोग कर हमलों_फ्रेम सरणी [64] की गणना

घुमाए गए बिटबोर्ड की विधि पर आगे बढ़ने से पहले, कंप्यूटिंग हमलों_फ्रॉम [] की जटिलता पर ध्यान देना आवश्यक है। छोटी दूरी के आंकड़ों के लिए, यह, ज़ाहिर है, बहुत सरल है; उदाहरण के लिए, हम पहले से ही knight_attacks [64] सरणी तैयार कर सकते हैं ताकि यदि घोड़ा F6 फ़ील्ड पर है, तो knight_attacks [F6] सभी क्षेत्रों पर बिट 1 युक्त बिटबोर्ड है जहां घोड़ा F6 फ़ील्ड से हमला कर सकता है (ध्यान दें कि फ़ील्ड घोड़े द्वारा हमला किया गया, शतरंज की चौकी पर टुकड़ों की व्यवस्था पर निर्भर नहीं)। एक ही विचार राजा के लिए और प्यादों के लिए काम करता है (मामूली बदलावों के बाद, क्योंकि प्यादे तिरछे तरीके से टकराते हैं, और एक या दो क्षेत्रों को आगे बढ़ाए बिना)।

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

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

चित्र 1 एक चेकरबोर्ड स्थिति का एक उदाहरण दिखाता है जहाँ पर कब्जे वाले खेतों को "X" के साथ चिह्नित किया गया है और अप्रकाशित फ़ील्ड को "-" के साथ चिह्नित किया गया है।



ध्यान दें कि इससे कोई फर्क नहीं पड़ता कि वास्तव में खेतों में क्या है, क्योंकि किसी भी प्रकार का आंकड़ा सामना करने पर लंबी दूरी की आकृति बंद हो जाती है। यदि एक हाथी F5 क्षेत्र पर खड़ा होता है (स्पष्टता के लिए, इसे चित्र 2 में B के साथ चिह्नित किया गया है), तो हम देखते हैं कि यह सीधे खेतों के निम्नलिखित सेट पर हमला करता है: {B1, C2, D3, E4, G6, H3, G4, E6, D7}। जब हम आक्रमण बिटबोर्ड की गणना करते हैं (यदि यह है कि इस स्थिति से स्वीकार्य हाथी की चाल का उपयोग किया जाएगा), तो हमें उन सभी चालों को बाहर करने की आवश्यकता हो सकती है जो हमारे अपने टुकड़ों को हरा देती हैं। पहले उल्लेखित white_occupied बिटबोर्ड का उपयोग करते हुए, हम इसके लिए पूरक संचालन (बिटवाइज नेगेशन) को लागू कर सकते हैं और फिर AND हमले को बिटबोर्ड के साथ कर सकते हैं, जो उन बिट्स को रीसेट करेगा जो हाथी के हमले वाले कीबोर्ड में हमारे अपने टुकड़ों पर होने वाले पत्राचार से मेल खाते हैं, क्योंकि ये अमान्य चाल हैं।

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

सबसे पहले, हम उन 8 दिशाओं में से प्रत्येक के लिए मुखौटे का एक सेट बनाएंगे, जिसमें आकृति चल सकती है। हम उन्हें प्लस 1 [64], प्लस 7 [64], प्लस 8 [64], प्लस 9 [64], माइनस 1 [64], माइनस 7 [64], माइनस 8 [64], माइनस 9 [64] कहते हैं। इन बिटबोर्ड में किसी भी क्षेत्र के लिए बिट 1 होता है जो किसी दिए गए दिशा में SQ क्षेत्र से एक हाथी पर हमला कर सकता है। हमारे उदाहरण के लिए, दिशा प्लस 7 में F5 पर बिशप के साथ (ये फ़ील्ड F5-E6-D7-C8 हैं), plus7 [F5] चित्र 3 में दिखाए गए की तरह दिखेगा।

यह हमें उन सभी क्षेत्रों को देगा, जो एक हाथी +7 दिशा में हमला कर सकता है, अगर हाथी और बोर्ड के किनारे के बीच के टुकड़े नहीं होते हैं। लेकिन हम जानते हैं कि वे मौजूद हो सकते हैं, और यदि हां, तो हमें इस दिशा में अवरुद्ध आंकड़े खोजने होंगे। ऐसा करने के लिए, हम उपरोक्त बिटबोर्ड को लेते हैं और इसे और कब्जे के बीच बिटबोर्ड से करते हैं। अगर हाथी को इस दिशा में अवरुद्ध किया जाता है, तो हमें एक गैर-खाली बिटबोर्ड मिलेगा जिसमें बिट्स 1 प्रत्येक क्षेत्र के लिए खड़ा होगा, जहां एक आकृति है जो हाथी के आंदोलन को C8 तक तिरछे रोकती है। चूंकि हमें केवल पहले अवरुद्ध आंकड़े की आवश्यकता है, हम FirstOne () फ़ंक्शन का उपयोग करेंगे, जो मूल्य 1 के साथ पहले बिट के सूचकांक को लौटाएगा। उदाहरण के लिए, यदि हाथी C8 और D7 पर अवरुद्ध था, तो FirstOne () को फ़ील्ड नंबर D7 (51) को वापस करना चाहिए।

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

  diag_attacks = plus7 [F5];
	 ब्लॉकर्स = diag_attacks & occupied_squares;
	 block_square = FirstOne (ब्लॉकर्स);
	 diag_attacks ^ = plus7 [block_square]; 

यहां आपको एक बीम के लिए बस इतना करना है। कोड को स्पष्ट करने के लिए, diag_attacks ऊपर वर्णित बिटबोर्ड है जिसमें F7 फ़ील्ड से +7 दिशा में हमला किए गए फ़ील्ड शामिल हैं। ब्लॉकर्स में इस विकर्ण पर स्थित सभी टुकड़ों के साथ एक बिटबोर्ड है। हम पहले अवरुद्ध आंकड़ा पाते हैं और फिर plus7 [block_square] और diag_attacks के बीच एक विशेष "OR" बनाते हैं, जो वास्तव में इसके पीछे आने वाले सभी आक्रमण वाले क्षेत्रों को काट देता है। (आइए यह पता लगाने की कोशिश करें। यदि F5 के साथ बिशप E6 पर अवरुद्ध है, तो इस मामले में plus7 [E6] इस तरह दिखाई देगा: इकाइयों के साथ बिट केवल D7 और C8 पर होंगे। चूंकि D7 / C8 बिट्स दोनों बिटबोर्ड में गैर-शून्य हैं, फिर अनन्य "के बाद। या "बिटबोर्ड के बीच, ये (और केवल ये) बिट्स रीसेट हैं।"

हम इसे केवल अंतर के साथ चारों दिशाओं के लिए दोहराते हैं कि माइनस दिशाओं के लिए हम फ़र्स्टऑन () का उपयोग नहीं करते हैं, क्योंकि हमें अंतिम अवरोधन आंकड़ा खोजने की आवश्यकता है। इसके बजाय, हम लास्टऑन () में स्विच करते हैं। अब चारों दिशाओं में हाथी के हमलों की गिनती के लिए कोड इस तरह दिखता है:

  diag_attacks = plus7 [F5];
	 ब्लॉकर्स = diag_attacks & occupied_squares;
	 block_square = FirstOne (ब्लॉकर्स);
	 bishop_attacks = diag_attacks ^ plus7 [block_square];
	 diag_attacks = plus9 [F5];
	 ब्लॉकर्स = diag_attacks & occupied_squares;
	 block_square = FirstOne (ब्लॉकर्स);
	 bishop_attacks | = diag_attacks ^ plus9 [block_square];
	 diag_attacks = minus7 [F5];
	 ब्लॉकर्स = diag_attacks & occupied_squares;
	 block_square = LastOne (ब्लॉकर्स);
	 bishop_attacks | = diag_attacks ^ minus7 [block_square];
	 diag_attacks = minus9 [F5];
	 ब्लॉकर्स = diag_attacks & occupied_squares;
	 block_square = LastOne (ब्लॉकर्स);
	 bishop_attacks | = diag_attacks ^ minus9 [block_square]; 

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

यह भी ध्यान दिया जाना चाहिए कि फर्स्टऑन () / लास्टऑन () फ़ंक्शन सी में प्रक्रियाओं के रूप में निष्पादित होने पर बहुत महंगे हैं, क्योंकि पहले या आखिरी बिट को ढूंढना एक गैर-तुच्छ कार्य है जिसे हमलों की उपरोक्त गणना में बहुत समय की आवश्यकता होती है। सौभाग्य से, आधुनिक माइक्रोप्रोसेसर के पास इन मूल्यों की गणना के लिए हार्डवेयर निर्देश हैं (X86 आर्किटेक्चर में Intel में BSF / BSR [बिट-स्कैन फॉरवर्ड, बिट-स्कैन रिवर्स] निर्देश हैं), जो इन कार्यों को बेहद तेज बनाता है। अन्य प्रकार की वास्तुकला भी इसी तरह के निर्देश प्रदान करती हैं।

3. रोटेटेबल बिटबोर्ड

सितंबर 1994 में बिटबोर्ड का उपयोग करने वाले क्राफ्टी संस्करण के बाद, मैंने UAB (सेफ्टी - रॉबर्ट हयात द्वारा लिखित एक शतरंज कार्यक्रम, UAB - यूनिवर्सिटी ऑफ अलाबामा में बर्मिंघम - लगभग अनुवाद।) में सेमिनार आयोजित करना शुरू कर दिया। 64-बिट का अध्ययन करने के लिए। कार्यकुशलता बढ़ाने के लिए नए तरीके विकसित करना और विकसित करना पहली चर्चाओं में से एक यह आया कि क्षैतिज के साथ लंबी दूरी की आकृति की गति को उत्पन्न करना कितना आसान है।

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

इसे ध्यान में रखते हुए, रैंक_टैक्स [64] [256] बिटबोर्ड की एक सरणी पर विचार करें। इस सरणी को आरंभीकृत करने के लिए, किसी भी फ़ील्ड को लें, उदाहरण के लिए A1 आप देख सकते हैं कि इसके क्षैतिज में केवल 256 अलग-अलग राज्य हैं, इस पर निर्भर करता है कि कौन से क्षेत्र पर कब्जा है और कौन से नहीं हैं। यदि खेल शुरू करने से पहले हम पहले से गणना कर सकते हैं कि A1 से बदमाश कौन से फ़ील्ड में जा सकते हैं, इस क्षैतिज पर सिंगल बिट्स के सभी 256 अलग-अलग संयोजनों को ध्यान में रखते हुए, हम बिटबोर्ड रैंक_attacks [A1] [सामग्री] का हवाला देकर इस क्षैतिज पर हमला कर सकते हैं। जहां सामग्री किसी दिए गए क्षैतिज की स्थिति का 8-बिट प्रतिनिधित्व है। हम सभी को 64 क्षेत्रों में से प्रत्येक के लिए बिटबोर्ड के एक सेट की गणना करने की जरूरत है और सभी 256 अलग-अलग राज्यों में क्षैतिज स्थित हैं, जिस पर ये क्षेत्र स्थित हैं (हाँ, यदि आप इसके बारे में सोचते हैं, तो क्षैतिज में केवल 128 राज्य हो सकते हैं, क्योंकि हम जानते हैं कि उस पर) खेतों में से एक किश्ती है, लेकिन इस सरलीकरण को अनदेखा करना आसान है)। यहां यह ध्यान दिया जाना चाहिए कि हालांकि क्षैतिज में 8 स्थिति बिट्स हैं, दो चरम बिट्स (एलएसबी और एमएसबी) कुछ भी नहीं बदलते हैं, क्योंकि उन पर हमला किया जाता है, भले ही उन पर कोई आंकड़ा हो या नहीं। परिणामस्वरूप, हम उन्हें प्रत्येक क्षैतिज के लिए तालिका आकार को 75% तक कम करने के लिए आगे की गणना से हटा देते हैं। इस प्रकार, हम rank_attacks सरणी का आकार रैंक_attacks [64] [64] तक कम कर देते हैं। अन्य सभी समान सरणियाँ समान सरलीकरण का उपयोग करेंगी।

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

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



स्मरण करो कि A1 शून्य बिट बिट (MSB) है, और H8 कब्जे वाले_सक्वेयर बिटबोर्ड में 63 वां बिट (LSB) है। पहले चीजें पहले, हम ऊर्ध्वाधर बिट्स को सन्निहित बनाने के लिए इसे 90 डिग्री पर बाईं ओर घुमाते हैं (ध्यान दें कि निचले बाएं कोने में 64-बिट बिटबोर्ड में शून्य बिट रहता है, और ऊपरी दाएं कोने में हमेशा सीरियल नंबर 63 होगा), जैसा कि दिखाया गया है। आंकड़ा 5 में।

फिर हम मूल 45 डिग्री को बाईं ओर घुमाते हैं, जैसा कि चित्र 6 में दिखाया गया है।



इस घुमाए गए बिटबोर्ड में, निचला क्षेत्र (A1) शून्य बिट बन जाता है, और निम्न क्रम में बन जाते हैं। तो, उदाहरण के लिए, ए 2 बिट 1 हो जाता है, बी 1 बिट 2 हो जाता है, और इसी तरह एच 8 तक, जो बिट 63 हो जाता है।

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

अब हम अन्य विकर्णों पर आसन्न बिट्स बनाने के लिए मूल बिटबोर्ड को 45 डिग्री तक घुमाते हैं, जैसा कि चित्र 7 में बिटबोर्ड में है।

अब जबकि हमारे पास यह सब है, तो यह स्पष्ट हो जाता है कि हमें पहले से विचार किए गए रैंक_टैक्स [64] [64] के अलावा हमलों के लिए तीन और बिटबोर्डों को जोड़ने की आवश्यकता है। File_attacks [64] [64], diaga1h8_attacks [64] [64] और diagh1a8_attacks [64] [64] को जोड़ा जाता है, और यदि हम मूल occupied_squest बिटबोर्ड को घुमाना सीखते हैं, तो हम उसी अनुक्रमण योजना का उपयोग कर सकते हैं, जो हमें जटिल को बदलने की अनुमति देगा। हाथियों या बदमाशों के लिए टेबल पर दो और रानियों के लिए चार के लिए अद्यतन प्रक्रिया।

बाद में, अधिभोग_सक्वेयर बिटबोर्ड को घुमाने के बारे में बहुत चर्चा के बाद, एक सरल समाधान मिला। केवल कब्जे वाले_बोर्ड को बिटबोर्ड पर संग्रहीत करने और यदि आवश्यक हो (जिसे हम अक्षमता के कारण लगभग असंभव मानते हैं) को घुमाने के बजाय, हम कब्जे वाले खेतों के लिए चार बिटबोर्ड को स्टोर कर सकते हैं: सामान्य और घुमाया हुआ 90 डिग्री, बाएं से 45 डिग्री और दाईं ओर 45 डिग्री। यह वास्तव में काफी आसान है, क्योंकि मेकमोव () आकृति को स्थानांतरित करने की प्रक्रिया में, हम व्याप्त_सक्वेयर बिटबोर्ड को अद्यतन करने के लिए समान कोड पा सकते हैं:

occupied_squares ^ = set_mask [from] | set_mask [को];

यह साधारण चालों के लिए एक सरल तंत्र है (गलियारे को पकड़ना, निकालना और संभालना थोड़ा अलग तरीके से संभाला जाता है), क्योंकि हम जानते हैं कि occupied_squares में प्रारंभ फ़ील्ड बिट का मान 1 होना चाहिए (अन्यथा, इस फ़ील्ड पर जाने के लिए कोई आंकड़ा नहीं होगा ); और हम यह भी जानते हैं कि अधिगत_सक्वेयर बिटबोर्ड में अंतिम "टू" फ़ील्ड का शून्य का मान होना चाहिए (अन्यथा यह एक लेना होगा)। तो, अनन्य "OR" का उपयोग करके, स्टार्ट फ़ील्ड बिट रीसेट है, और अंतिम फ़ील्ड बिट सेट है।

सेट_मस्क के सभी तत्व [64] बिटबोर्ड सरणी में संबंधित स्थिति में केवल 1 सेट बिट होता है। उदाहरण के लिए, set_mask [0] में सबसे छोटा बिट सेट (शून्य बिट) होता है, जबकि set_mask [63] में सबसे कम बिट सेट (63 वां बिट) होता है। रोटेटेबल बिटबोर्ड के साथ काम करने के लिए, हमने ऐसे मास्क के तीन नए सेट बनाए: set_mask_rl90 [64], set_mask_rr45 [64] और set_mask_rl45 [64]। उनमें से प्रत्येक फ़ील्ड नंबर को एक इंडेक्स के रूप में लेता है, और एक बिटबोर्ड लौटाता है जिसमें संबंधित बिट को व्याप्त_सचिव रोटेटेबल बिटबोर्ड में सेट किया जाता है। उदाहरण के लिए, set_mask_rl90 [0] में, सातवां बिट वास्तव में सेट किया गया है, क्योंकि यदि आप चित्र को देखते हैं, तो रोटेट_लेफ्ट बिटबोर्ड में, बिट 0 सातवें हो जाता है।

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

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

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

4. रोटेटेबल बिटबोर्ड का उपयोग करते हुए attack_from [64] की गणना

हमलों की गणना करने के लिए, हम 4 अलग-अलग सरणियों का उपयोग करते हैं: एक क्षैतिज हमलों के लिए, एक ऊर्ध्वाधर हमलों के लिए और एक दो विकर्णों के लिए जो क्षेत्र से गुजरते हैं। हमने इन सरणियों को रैंक_एटैक्स [64] [64], फ़ाइल_एटैक्स [64] [64], डायगा 1 एच 8_एटैक्स [64] [64] और डायघ 1 ए 8_टैक्स [64] [64] नाम दिया है।

इन सरणियों को शुरू करने के लिए (यह तब होता है जब आवेदन शुरू होता है, और उसके बाद से सरणियाँ अपरिवर्तित रहती हैं), हमने बस यह मान लिया था कि क्षेत्र पर एक लंबी दूरी की आकृति है जो प्रश्न में दिशा में कदम रख सकती है (उदाहरण के लिए, रानी)। फिर प्रत्येक क्षेत्र के लिए हमने रैंक_टैक्स [वर्ग] [रैंक_ कॉन्टेंट्स] पेश किया - एक बिटबोर्ड जो दिखाता है कि स्क्वायर स्क्वायर पर खड़ी रो / क्वीन किस क्षैतिज रेखा को स्थानांतरित कर सकती है, जब रैंक के इस बिट्स के अनुसार इस क्षैतिज के क्षेत्र पर कब्जा कर लिया जाता है। "। उदाहरण के लिए, पहले से माना हुआ कब्जा किया हुआ बिटबोर्ड ले लीजिए, लेकिन F5 फ़ील्ड पर बिशप के बजाय, पिछले उदाहरण के अनुसार, हम वहां एक रॉक (चित्र 8) डालते हैं। मान लें कि हम रैंक_एटैक्स [37] [100] को शुरू करने की कोशिश कर रहे हैं (37 फील्ड एफ 5 है, और 100 इस क्षैतिज क्षेत्र पर कब्जा कर लेते हैं - 01100100)।हम इस तत्व रैंक_टैक्स को इनिशियलाइज़ करते हैं, जैसा कि चित्र 9 में दिखाया गया है। यह पूरी तरह से उन फ़ील्ड्स से मेल खाता है, जो कि 5 वें हॉरिजॉन्टल पर रूक / क्वीन हमला कर सकते हैं, यदि यह टुकड़ा F5 पर है और हॉरिजॉन्टल के तीन टुकड़े हैं, जैसा ऊपर बताया गया है।



खैर, बुरा नहीं है। ऐसा करने से, हम जल्दी से क्षैतिज के साथ बदमाश हमले कर सकते हैं। लेकिन अब हमें क्षैतिज रूप से नहीं बल्कि ऊर्ध्वाधर के साथ हमलों की गणना करने की आवश्यकता है। ऐसा करने के लिए, हम occupied_rl90 बिटबोर्ड लेते हैं, जो कि पिछली occupied_squares की एक सटीक प्रतिलिपि है, लेकिन 90 डिग्री घुमाया गया है, जैसा कि चित्र 10 में दिखाया गया है।

जब हम तीसरे "क्षैतिज" को निकालते हैं, तो हम वास्तव में ऊर्ध्वाधर F पर रोजगार के बारे में जानकारी प्राप्त करते हैं (शायद वहाँ है) ऊपर से तीसरा दृश्य - लगभग अनुवाद।)। पहले से गणना किए गए हमले के बिटबोर्ड का उपयोग फिर से किया जाता है, लेकिन इस बार हम हमलों_फाइल [37] [251] (फिर से, 37 का अर्थ है फील्ड एफ 5, और इस ऊर्ध्वाधर रूप में 11111011 पर कब्जा कर लिया फ़ील्ड), जिसका मूल्य हमने निर्धारित किया, जैसा कि आंकड़े में दिखाया गया है। 11।



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

 बिटबर्ड हमले = 0;
    अगर (बिशपओवर (टुकड़ा)) {
      diaga1 स्थिति प्राप्त करें (शिफ्ट / AND); / * 6 बिट्स * /
      हमले | = diaga1h8_attacks [वर्ग] [स्थिति];
      diagh1 स्थिति (शिफ्ट / AND) प्राप्त करें; / * 6 बिट्स * /
      हमले | = diagh1a8_attacks [वर्ग] [स्थिति];
     }
    अगर (RookMover (टुकड़ा)) {
      रैंक दर्जा प्राप्त करें (शिफ्ट / और); / * 6 बिट्स * /
      हमलों | = rank_attacks [वर्ग] [स्थिति];
      फ़ाइल स्थिति (शिफ्ट / और) प्राप्त करें; / * 6 बिट्स * /
      हमलों | = file_attacks [वर्ग] [स्थिति];
     } 

और यह पूरी तरह से हो गया है। बिशपमोवर () और रूकमोवर () दो स्थितियां वापस आती हैं यदि टुकड़ा तिरछे एक हाथी (हाथी या रानी) की तरह चलता है या एक बदमाश (बदमाश या रानी) की तरह चलता है। चालाक में, यह आकार प्रकार में एन्कोडेड है, जहां पी = 1, एन = 2, के = 3, बी = 5, आर = 6, और क्यू = 7। इन नंबरों का विश्लेषण करते समय, piece_type & 4 के परिणाम की जाँच की जाती है, और यदि परिणाम नॉनज़रो है, तो यह एक लंबी दूरी की आकृति है। इसके अलावा, अगर piece_type और 1 का परिणाम nonzero है, तो यह आंकड़ा विकर्ण के साथ आगे बढ़ता है, और अगर piece_type और 2 का परिणाम nonzero है, तो यह आंकड़ा क्षैतिज / ऊर्ध्वाधर के साथ आगे बढ़ सकता है।

5. हमलों की गणना_ [64]

हमलों_को [] बिटबोर्ड को स्लेट और एटकिन द्वारा प्रत्येक क्षेत्र के लिए एक बिट के साथ एक बिटबोर्ड के रूप में परिभाषित किया गया था, जहां से इस क्षेत्र पर हमला किया जाता है। उदाहरण के लिए, attack_to [28] (28 = E4) चित्र 12 की तरह लग सकता है, यह मानते हुए कि E4 E8 पर एक काले बदमाश और F6 पर एक काले शूरवीर द्वारा हमला किया गया है, और E1 पर एक सफेद बदमाश और D3 पर एक सफेद मोहरा द्वारा बचाव किया गया है (E4) "लक्ष्य" से पत्र टी के साथ चिह्नित)।



इस चित्र में, "टी" पर हमला किया गया क्षेत्र है, वास्तव में, यह बिटबोर्ड में बिट 0 से मेल खाता है। चार बिट्स एक्स (बिट्स 1) चार फ़ील्ड दिखाते हैं जिनसे उन पर खड़े आंकड़े ई 4 क्षेत्र पर हमले करते हैं। अगर हम यह जानना चाहते हैं कि कितने काले टुकड़े ई 4 अटैक करते हैं, तो हम कर सकते हैं और इस पर कब्जा कर लिया है_ काले मोहरों के लिए बिटबोर्ड। परिणाम E4 पर हमला करने वाले एक काले टुकड़े द्वारा कब्जा किए गए प्रत्येक क्षेत्र पर बिट्स 1 होगा। इसी तरह ई 4 पर हमला करने वाले सफ़ेद टुकड़ों के साथ, हम सफ़ेद टुकड़ों के लिए ऑक्यूपाइड_सक्वेयर बिटबोर्ड के साथ भी ऐसा ही करते हैं।

प्रश्न इस प्रकार हैं: (ए) हम इस तरह के एक बिटबोर्ड की गणना कैसे कर सकते हैं और (बी) यह कितना श्रमसाध्य है? अटैक बिटबोर्ड बनाने की उपरोक्त विधि का उपयोग करना (याद रखें कि शॉर्ट-रेंज के आंकड़ों के लिए अटैक बिटबोर्ड की पीढ़ी तुच्छ है, क्योंकि लंबी दूरी के आंकड़ों के विपरीत, सभी फ़ील्ड अनुप्रयोग के प्रारंभ में गणना की जा सकती हैं और भविष्य में नहीं बदलेगी), हम E4 पर हाथी के हमले की गणना करेंगे। और फिर सफेद / काले बिशप और रानियों के लिए एक बिटबोर्ड के साथ करो, जो हमें प्रत्येक बिशप / रानी के लिए 1 बिट देगा, चाहे उनका रंग कैसा भी हो, जो लक्ष्य क्षेत्र पर हमला करते हैं। हम परिणाम को याद करते हैं और बदमाशों और बदमाशों / रानियों को मारते हैं। फिर हम घोड़े के हमले के बीटबोर्ड को लेते हैं, सफेद / काले घोड़ों के लिए बीटबोर्ड के साथ करते हैं, और राजाओं और प्यादों के लिए इसे दोहराते हैं। परिणामस्वरूप, हमारे पास पाँच बिटबोर्ड हैं, जो यदि हम उनके बीच OR करते हैं, तो वे सभी क्षेत्रों को दिखाएंगे,जिससे E4 पर हमला।

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

6. शतरंज इंजन में बिटबोर्ड का उपयोग

यह ध्यान रखना महत्वपूर्ण है कि संकेतित एल्गोरिथ्म किसी भी चक्र के उपयोग के बिना, किसी न किसी टुकड़े की चाल के पूर्ण सेट के साथ एक बिटबोर्ड देता है। हालांकि, शतरंज कार्यक्रम में, इन आंदोलनों को उनका मूल्यांकन करने के लिए "से / के लिए" अलग चाल के एक सेट में विभाजित किया जाना है, और यह प्रक्रिया निश्चित रूप से एक चक्र होगी, हालांकि यह बहुत सरल है। "से" फ़ील्ड ज्ञात है, इसलिए हम पहले बिट को "जहां" फ़ील्ड के अनुरूप पूर्णांक में बदलने के लिए फर्स्टऑन () फ़ंक्शन का उपयोग करते हैं, और फिर इस बिट को रीसेट करते हैं। जब तक सभी बिट्स रीसेट नहीं हो जाते तब तक चक्र जारी रहता है। नीचे वास्तविक कोड है जो कि सफेद रानी के लिए बस करता है: (ध्यान दें कि चालाक में चाल 21 बिट्स में संग्रहीत होती है। निचले 6 बिट्स "FROM" फ़ील्ड को इंगित करते हैं (जहां से), अगले 6 बिट्स "TO" फ़ील्ड (जहां) को इंगित करते हैं, अभी तक। 3 MOVING_PIECE (जंगम आकृति) है, और अंतिम 3 PROMOTE_TO आंकड़ा है।जिसमें आयोजित पंजे मुड़ जाते हैं।)

 piecebd=WhiteQueens;
    while (piecebd) {
      from=LastOne(piecebd);
      moves=AttacksQueen(from);
      temp=from+(queen<<12);
      while (moves) {
        to=LastOne(moves);
        move_list[i++]=temp+to<<6;
        Clear(to,moves);
       }
      Clear(from,piecebd);
     } 

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

 टुकड़ा = सफ़ेद क्यू;
    जबकि (टुकड़ा) {
      से = लास्टऑन (टुकड़ा);
      मूव्स = AttacksQueen (से) और ब्लैकपाइन्स;
      अस्थायी = से + (रानी << 12);
      जबकि (चलता है) {
        को = लास्टऑन (चाल);
        Move_list [i ++] = अस्थायी + से << 6;
        स्पष्ट (करने के लिए, ले जाता है);
       }
      स्पष्ट (से, टुकड़ा);
     } 

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

जैसा कि पहले दिखाया गया है, यदि आवश्यक हो तो [_] बिटबोर्ड पर हमला करना बहुत आसान है। इसमें उच्च कम्प्यूटेशनल जटिलता नहीं है, आसानी से लागू किया जाता है और कार्यक्षमता प्रदान करता है (attack_to [sq]), यदि / जब इसकी आवश्यकता होती है। इस तरह की जानकारी के लिए सबसे आम आवेदन प्रश्न का उत्तर "चेक के तहत राजा?" है, जो पहले वर्णित की तुलना में करना भी आसान है। प्रत्येक प्रकार के टुकड़ों (बिशप / रानी, ​​रोक / रानी, ​​शूरवीर, राजा और प्यादा) के लिए हम हमलों का एक बिटबोर्ड उत्पन्न करते हैं और फिर दुश्मन के टुकड़े के एक बिटबोर्ड के साथ उनमें से प्रत्येक के लिए करते हैं (हम परवाह नहीं करते हैं कि हमारे टुकड़े हमारे अपने राजा पर हमला करते हैं, केवल महत्वपूर्ण प्रतिद्वंद्वी के टुकड़े), और यदि परिणाम गैर-शून्य है, तो हम तुरंत "TRUE" यह कहते हुए वापस कर देते हैं कि "हाँ, राजा पर भी जाँच के तहत हमला किया गया है"।

इसका उपयोग मूवमेंट के मूल्यांकन में उपयोग किए जाने वाले एक स्थिर विनिमय गणना ब्लॉक को लागू करने के लिए भी किया जा सकता है। कुछ क्षेत्र के लिए जहां एक्सचेंजों के अनुक्रम की गणना करना आवश्यक है, हम सबसे पहले attack_to [sq] लेते हैं, जो प्रत्येक आंकड़े को इस क्षेत्र पर सीधे हमला करने की सुविधा देता है। हम कम से कम महत्वपूर्ण दुश्मन का आंकड़ा पाते हैं जो इस क्षेत्र पर हमला करता है; ऐसा करने के लिए, हम करते हैं और हमलों के बीच और दुश्मन के टुकड़ों के लिए छह बिटबोर्ड में से प्रत्येक, पंजे के साथ शुरू करते हैं और टुकड़े के मूल्य को राजा तक बढ़ाते हैं। जब AND परिणाम एक गैर-शून्य परिणाम होता है, तो हम उस आंकड़े का मूल्य ज्ञात करते हैं, जो लक्ष्य क्षेत्र पर हमला करने वाला पहला होगा। हम हमलों के इस आंकड़े को हमलों_ से रीसेट करते हैं, क्योंकि यह पहले से ही उपयोग किया गया है, जिसके बाद हम करते हैं और परिणामी हमलों_को हमारे आंकड़ों के लिए छह बिटबोर्ड के साथ करते हैं,कम से कम लागत के साथ एक रक्षक पाने के लिए। हमलों को दोहराएं जब तक कि खाली नहीं है।

हालांकि, लंबी दूरी के आंकड़े के बारे में क्या लक्ष्य क्षेत्र पर हमला करते हैं ताकि एक दूसरे के पीछे हो? यह गणना करना भी आसान है। हम उस टुकड़े को जानते हैं जो हमने सिर्फ "उपयोग" किया था, इसे attack_to बिटबोर्ड से ड्रॉप करके, ताकि हम यह निर्धारित कर सकें कि यह लंबी दूरी की है या नहीं (उदाहरण के लिए, एक मोहरा, बिशप, किश्ती या रानी, ​​जिसके पीछे अन्य टुकड़े हैं, एक "बैटरी" बना सकते हैं) )। हमें केवल यह पता लगाने के लिए कि क्या हमारे द्वारा उपयोग किए जाने के पीछे इस दिशा में एक और आंकड़ा है, हमें यह पता लगाने के लिए एक और AND ऑपरेशन करने की आवश्यकता है। यदि ऐसा है, और यह उचित प्रकार का है (विकर्णों के लिए बिशप / रानी, ​​समोच्च / ऊर्ध्वाधर के लिए किश्ती / रानी), तो हम बस इस हमले के लिए OR_ के साथ करते हैं, जिसके परिणामस्वरूप अब यह लक्ष्य क्षेत्र पर हमला करता है, बिना किसी बाधा के। (अब हम परिचित बिटबोर्ड प्लसएन [] / माइनस [] का उपयोग करते हैं,और पाठक के लिए एक अभ्यास के रूप में यह कैसे करें के सवाल का जवाब छोड़ दें।)

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

7. निष्कर्ष

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

वर्तमान 64-बिट आर्किटेक्चर (अल्फा, HP, MIPS - ये उनमें से कुछ हैं) के लिए और नए 64-बिट आर्किटेक्चर के लिए, जैसे Intel Merced प्रोसेसर, बिटबोर्ड का उपयोग बहुत मायने रखता है, क्योंकि यहां बिटबोर्ड को प्रोसेसर के आंतरिक रजिस्टर के आकार से सबसे अधिक मिलता है और टायर। उदाहरण के लिए, 32-बिट मशीनों पर सबसे आम बिट संचालन (और, या, एक्सओआर, शिफ्ट, और इसी तरह) कम से कम दो निर्देशों का उपयोग करते हैं - 64-बिट बिटबोर्ड के प्रत्येक आधे के लिए एक। एक ही घड़ी की गति के साथ 64-बिट आर्किटेक्चर पर, ये ऑपरेशन दो बार तेजी से किए जाते हैं, क्योंकि उन्हें प्रक्रिया के लिए केवल एक निर्देश की आवश्यकता होती है। यह एक प्रदर्शन लाभ है जिसे उपेक्षित नहीं किया जाना चाहिए, क्योंकि यह बिल्कुल मुफ्त है।

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

द्वारा पोस्ट किया गया: रॉबर्ट हयात
मूल: http://www.cis.uab.edu/info/facademy/hyatt/bitmaps.html

अनुवादक से

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

एक गाइड के रूप में, मैं निम्नलिखित लिंक देखने की सलाह देता हूं:
www.frayn.net/beowulf/theory.html#bitboards
www.craftychess.com

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

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

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