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

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

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

ज़ोब्रिस्ट हैशिंग एक बोर्ड गेम के प्रत्येक संभावित तत्व के लिए रैंडम्ली जनरेटिंग बिटस्ट्रिंग उत्पन्न करके प्रारंभ होती है, यानी एक पीस और एक पोजीशन के प्रत्येक संयोजन के लिए (चैस के खेल में, यह 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 बिट है। कई गेम इंजन ट्रांसपोज़िशन टेबल में केवल हैश वैल्यू संग्रहीत करते हैं, मेमोरी उपयोग को कम करने के लिए पोजीशन की जानकारी को पूरे प्रकार से छोड़ देते हैं, और यह मानते हैं कि हैश कोलिज़न नहीं होंगे, या यदि वे होते हैं तो टेबल के परिणामों को बहुत इन्फ्लुएंस नहीं करते है।

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

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

अपडेटिंग हैश वैल्यू

पूरे बोर्ड के लिए हर बार हैश की कंप्यूटिंग करने के अतिरिक्त, जैसा कि ऊपर दिए गए सीयूडोकोडे में होता है, बोर्ड के हैश मान को केवल उन पोसिशन्स के लिए बिटस्ट्रिंग को एक्सओआरिंग करके और नए पोसिशन्स के लिए बिटस्ट्रिंग में एक्सओआरिंग द्वारा इंक्रीमेंटली रूप से अपडेट किया जा सकता है। उदाहरण के लिए, यदि शतरंज की बिसात पर एक रूक को दूसरे स्क्वायर के पॉन से परिवर्तित कर दिया जाता है, तो रिजल्टिंग पोजीशन उपस्थित हैश को बिटस्ट्रिंग के साथ एक्सओआरिंग द्वारा एक्सीस्ट किया जाता है:

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

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

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

व्यापक उपयोग

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

यह भी देखें

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