ज़ोब्रिस्ट हैशिंग

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

हैश वैल्यू की गणना

ज़ोब्रिस्ट हैशिंग एक बोर्ड गेम के प्रत्येक संभावित तत्व के लिए रैंडम्ली जनरेटिंग बिटस्ट्रिंग उत्पन्न करके प्रारंभ होती है, यानी एक पीस और एक पोजीशन के प्रत्येक संयोजन के लिए (चैस के खेल में, यह 12 पीसेस × 64 बोर्ड पोजीशन है, या 18 × 64 यदि किंग्स और रूक्स हैं) अभी भी महल बनाया जा सकता है, और जो प्यादे एन पासेंट को पकड़ सकते हैं, उन्हें दोनों रंगों के लिए भिन्न-भिन्न माना जाता है)। अब किसी भी बोर्ड कॉन्फ़िगरेशन को इंडिपेंडेंट पीसेस/पोजीशन कंपोनेंट्स में विभाजित किया जा सकता है, जो पहले रैंडम बिटस्ट्रिंग जनरेटिंग पर मैप किए जाते हैं। अंतिम ज़ोब्रिस्ट हैश की गणना बिटवाइज़ एक्सओआर का उपयोग करके उन बिटस्ट्रिंग्स को मिलाकर की जाती है। चैस के खेल के लिए उदाहरण छद्म कोड:

constant indices
    white_pawn := 1
    white_rook := 2
    # etc.
    black_king := 12

function init_zobrist():
    # fill a table of random numbers/bitstrings
    table := a 2-d array of size 64×12
    for i from 1 to 64:  # loop over the board, represented as a linear array
        for j from 1 to 12:      # loop over the pieces
            table[i][j] := random_bitstring()
    table.black_to_move = random_bitstring()

function hash(board):
    h := 0
    if is_black_turn(board):
        h := h XOR table.black_to_move
    for i from 1 to 64:      # loop over the board positions
        if board[i] ≠ empty:
            j := the piece at board[i], as listed in the constant indices, above
            h := h XOR table[i][j]
    return h

हैश वैल्यू का उपयोग

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

ज़ोब्रिस्ट हैशिंग टैबुलेशन हैशिंग का पहला ज्ञात उदाहरण है। परिणाम एक K-इंडिपेंडेंट हैशिंग|3-वार इंडिपेंडेंट हैश परिवार है। विशेष रूप से, यह दृढ़ता से यूनिवर्सल हैशिंग है।

उदाहरण के तौर पर, चैस में, किसी भी समय 64 वर्गों में से प्रत्येक खाली हो सकता है, या इसमें खेल के 6 टुकड़ों में से एक हो सकता है, जो या तो काले या सफेद होते हैं। इसके अलावा, खेलने की बारी या तो काले की हो सकती है या सफ़ेद की खेलने की बारी हो सकती है। इस प्रकार किसी को 6 x 2 x 64 + 1 = 769 यादृच्छिक बिटस्ट्रिंग्स उत्पन्न करने की आवश्यकता है। किसी पोजीशन को देखते हुए, कोई यह पता लगाकर कि कौन से पीसेस किस वर्ग पर हैं, और प्रासंगिक बिटस्ट्रिंग्स को एक साथ जोड़कर उसका ज़ोब्रिस्ट हैश प्राप्त करता है। यदि पोजीशन स्थानांतरित करने के लिए काली है, तो ब्लैक-टू-मूव बिटस्ट्रिंग को ज़ोब्रिस्ट हैश में भी शामिल किया गया है।

हैश वैल्यू अद्यतन कर रहा है

हर बार पूरे बोर्ड के लिए हैश की गणना करने के बजाय, जैसा कि ऊपर दिए गए छद्मकोड में होता है, बोर्ड के हैश वैल्यू को केवल परिवर्तित पदों के लिए बिटस्ट्रिंग को एक्सओआर करके और बिटस्ट्रिंग में एक्सओआरing द्वारा वृद्धिशील रूप से अपडेट किया जा सकता है। नये पद.उदाहरण के लिए, यदि चैस की बिसात पर एक मोहरे को दूसरे वर्ग के किश्ती (चैस) से बदल दिया जाता है, तो परिणामी पोजीशन मौजूदा हैश को बिटस्ट्रिंग के साथ एक्सओआरing द्वारा उत्पन्न की जाएगी:

'इस चौक पर मोहरा' (इस चौक पर मोहरे को बाहर निकालना)
'इस चौक पर रुको' (इस चौक पर रुक में एक्सओआरing)
'रूक एट सोर्स स्क्वायर' (एक्सओआरिंग आउट द रूक एट सोर्स स्क्वायर)

यह खेल का पेड़ को पार करने के लिए ज़ोब्रिस्ट हैशिंग को बहुत कुशल बनाता है।

कंप्यूटर जाओ में, इस तकनीक का उपयोग गो#को डिटेक्शन के नियमों के लिए भी किया जाता है।

व्यापक उपयोग

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

यह भी देखें

• अल्फा-बीटा प्रूनिंग