बिट्स पर घोड़ा चलता है। शतरंज की बिसात

शुभ दोपहर मैंने इस लेख को विशेष रूप से OTUS में "डेवलपर्स के लिए एल्गोरिदम" पाठ्यक्रम के छात्रों के लिए लिखा था और आज मैं इसे हमारे ब्लॉग के सभी पाठकों के साथ साझा करना चाहता हूं।

एक शतरंज का घोड़ा शतरंज की बिसात पर खड़ा होता है और शतरंज की बिसात में सोच-समझकर चलता है।
वह कितने अलग-अलग चाल चल सकता है?



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

तो कैसे जल्दी से इस विचार का उपयोग करके एक शतरंज के घोड़े की चाल की संख्या का पता लगाएं?

दिया गया: knightNr - बोर्ड की सेल संख्या जहाँ घोड़ा है (0 से 63 तक)।
यह आवश्यक है: मूवमेंट - फ़ील्ड्स की संख्या जहां वह जा सकती है (2 से 8 तक)।

एल्गोरिथ्म।

1. घोड़े के पिंजरे की संख्या को ulong में परिवर्तित करें - बिट बोर्ड का मान
knightNr -> knightBits

2. घोड़े की सभी संभव चाल के लिए बिट्स सेट करें
knightBits -> मूव्सबिट्स

3. यूनिट बिट्स की संख्या बढ़ाएँ
चलता है -> चलता है



पहला चरण बहुत सरल है, आपको निर्दिष्ट पदों की संख्या से शून्य बिट को बाईं ओर स्थानांतरित करने की आवश्यकता है।

ulong knightBits = 1 << knightNr; 

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

आइए बोर्ड के बाईं ओर से दाईं ओर की चालों को सूचीबद्ध करना शुरू करें:

  movesBits = knightBits << 6 | knightBits >> 10 //  b5  b3 | knightBits << 15 | knightBits >> 17 //  c6  c2 | knightBits << 17 | knightBits >> 15 //  e6  e2 | knightBits << 10 | knightBits >> 6 //  f5  f3; 

सच है, शांत?

दुर्भाग्य से, बोर्ड के किनारों पर "ब्लैक होल" हैं। उदाहरण के लिए, इस एल्गोरिथ्म के अनुसार, सेल a4 (बिट # 24) से आप सेल g2 (बिट # 14 = 24 - 10) तक प्राप्त कर सकते हैं, यह छलांग एक ब्लैक होल के माध्यम से एक बोर्ड पर एक गोलाकार शतरंज के घोड़े का एक ब्लैक होल के माध्यम से चरम ऊर्ध्वाधर तक होता है ...

बोर्ड के किनारे पर घोड़े की क्वांटम कूद को बाहर करने के लिए, चलती के बाद चरम बैंड को "डिस्कनेक्ट" करना आवश्यक है। उदाहरण के लिए, चाल +6 और -10 (बाईं ओर दो कोशिकाएं) के लिए, जी और एच वर्टिकल पर प्राप्त मूल्यों को रद्द करना आवश्यक है, क्योंकि आप "लेफ्ट" दो चाल चलने के बाद इन ऊर्ध्वाधर पर समाप्त नहीं हो सकते हैं।

ऐसा करने के लिए, हमें 4 बिट ग्रिड स्थिरांक की आवश्यकता होती है, जिसमें सभी बिट्स को 1 पर सेट किया जाता है, जो कि संकेतित ऊर्ध्वाधर को छोड़कर। अर्थात्:

  ulong nA = 0xFeFeFeFeFeFeFeFe; ulong nAB = 0xFcFcFcFcFcFcFcFc; ulong nH = 0x7f7f7f7f7f7f7f7f; ulong nGH = 0x3f3f3f3f3f3f3f3f; 

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

अब अनुमेय हार्स चाल उत्पन्न करने के लिए एल्गोरिथ्म इस तरह दिखता है:

  movesBits = nGH & (knightBits << 6 | knightBits >> 10) | nH & (knightBits << 15 | knightBits >> 17) | nA & (knightBits << 17 | knightBits >> 15) | nAB & (knightBits << 10 | knightBits >> 6); 

यह बहुत तेज़ (!) काम करता है।

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

यह बिट्स की संख्या की गणना करने के लिए बनी हुई है

सबसे आसान तरीका नंबर 1 को दाईं ओर शिफ्ट करना और लोगों को गिनना है। कठिनाई - 64 ऑपरेशन। मेमोरी - 64 बिट्स।

सबसे तेज़ तरीका 65536 तत्वों के साथ कैश / ऐरे बनाना है, जिसमें प्रत्येक इंडेक्स के लिए बिट्स की संख्या 0 से 65535 तक लिखी गई है। और इस एरे से 4 तत्वों को जोड़ें जो कि संख्या के अगले 16-बिट सेगमेंट के अनुरूप हैं।
कठिनाई - 4 ऑपरेशन। मेमोरी - 64 किलोबाइट।

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

शुरू करने के लिए, हम ध्यान दें कि एक इकाई को एक संख्या से घटाते हुए, हम सभी "सही" शून्य को इकाइयों में और बाहरी इकाई को शून्य में बदलते हैं:

 1001010100010000 - 1 = 1001010100001111 

अगला, इन नंबरों के लिए तार्किक "और" ऑपरेशन लागू करें:

 1001010100010000 & 1001010100001111 = 1001010100000000 

जैसा कि आप देख सकते हैं, इस तरह के मुश्किल तरीके से हम सबसे सही इकाई को शून्य पर रीसेट करते हैं। इस ऑपरेशन को तब तक दोहराएं जब तक कि हमें परिणाम नहीं मिलता। कितने पुनरावृत्तियों, इतने सारे बिट्स। सच है, महान?

इस तरह से इस एल्गोरिथ्म को पूरा लिखा गया है:

  int movesCount = 0; while (movesBits != 0) { movesBits &= (movesBits - 1); movesCount ++; } 

समस्या हल हो गई!

इस कार्य में एक और, बहुत सरल, विशुद्ध रूप से तार्किक समाधान है: शतरंज के छोर से शूरवीर की दूरी निर्धारित करने के लिए (कोने में 2 चालें हैं, किनारे के पास 3 से 6 चालें हैं, केंद्र में 8 चालें हैं)। लेकिन अगर हम इस तरह से "हेड ऑन" समस्या को हल करने के लिए थे, तो हमें बिट बोर्ड के बारे में नहीं पता होगा, ऊर्ध्वाधर बिट मास्क के बारे में, एकल बिट्स की गिनती के लिए एल्गोरिथ्म के बारे में और वैक्यूम में गोलाकार घोड़ों के लिए ब्लैक होल के बारे में ...

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

करो-खुद काम: शतरंज के बादशाह के लिए भी यही करो।