ज़ोब्रिस्ट हैशिंग
ज़ोब्रिस्ट हैशिंग (जिसे ज़ोब्रिस्ट कुंजी या ज़ोब्रिस्ट हस्ताक्षर भी कहा जाता है [1]) एक हैश फंकशन निर्माण है जिसका उपयोग कंप्यूटर प्रोग्रामों में किया जाता है जो कंप्यूटर शतरंज और कंप्यूटर जाओ जैसे अमूर्त बोर्ड गेम खेलते हैं, स्थानान्तरण तालिका को लागू करने के लिए, एक विशेष प्रकार की हैश तालिका जिसे बोर्ड स्थिति द्वारा अनुक्रमित किया जाता है और उसी स्थिति का विश्लेषण करने से बचने के लिए उपयोग किया जाता है एक से ज्यादा बार। ज़ोब्रिस्ट हैशिंग का नाम इसके आविष्कारक, अल्बर्ट लिंडसे ज़ोब्रिस्ट (कंप्यूटर वैज्ञानिक) के नाम पर रखा गया है।[2] इसे क्रिस्टलीय सामग्रियों के सिमुलेशन में संस्थागत मिश्र धातु विन्यास को पहचानने की एक विधि के रूप में भी लागू किया गया है।[3] ज़ोब्रिस्ट हैशिंग आम तौर पर उपयोगी अंतर्निहित तकनीक का पहला ज्ञात उदाहरण है जिसे सारणीकरण हैशिंग कहा जाता है।
हैश मान की गणना
ज़ोब्रिस्ट हैशिंग एक बोर्ड गेम के प्रत्येक संभावित तत्व के लिए छद्म यादृच्छिक संख्या जनरेटर बिटस्ट्रिंग्स द्वारा शुरू होती है, यानी एक टुकड़े और एक स्थिति के प्रत्येक संयोजन के लिए (शतरंज के खेल में, यह 12 टुकड़े × 64 बोर्ड स्थिति है, या 18 × 64 यदि राजा और बदमाश हैं) वह अभी भी महल बना सकता है, और प्यादे जो एन पासेंट को पकड़ सकते हैं, दोनों रंगों के लिए अलग-अलग व्यवहार किया जाता है)। अब किसी भी बोर्ड कॉन्फ़िगरेशन को स्वतंत्र टुकड़े/स्थिति घटकों में विभाजित किया जा सकता है, जो पहले उत्पन्न यादृच्छिक बिटस्ट्रिंग्स पर मैप किए जाते हैं। अंतिम ज़ोब्रिस्ट हैश की गणना बिटवाइज़ XOR का उपयोग करके उन बिटस्ट्रिंग्स को मिलाकर की जाती है। शतरंज के खेल के लिए उदाहरण छद्म कोड:[citation needed]
निरंतर सूचकांक
सफ़ेद_प्यादा := 1
सफ़ेद_रूक := 2
# वगैरह।
ब्लैक_किंग := 12
फ़ंक्शन init_zobrist():
# यादृच्छिक संख्याओं/बिटस्ट्रिंग्स की एक तालिका भरें
तालिका:= 64×12 आकार की 2-डी सरणी
1 से 64 तक i के लिए: बोर्ड पर # लूप, एक रैखिक सरणी के रूप में दर्शाया गया है
1 से 12 तक j के लिए: # टुकड़ों पर लूप
तालिका[i][j] := रैंडम_बिटस्ट्रिंग()
टेबल.ब्लैक_टू_मूव = रैंडम_बिटस्ट्रिंग()
फ़ंक्शन हैश(बोर्ड):
एच := 0
यदि is_black_turn(बोर्ड):
h := h XOR टेबल.black_to_move
1 से 64 तक के लिए: # बोर्ड स्थितियों पर लूप
यदि बोर्ड[i] ≠ खाली है:
जे: = बोर्ड पर टुकड़ा [i], जैसा कि ऊपर स्थिर सूचकांकों में सूचीबद्ध है
h := h XOR तालिका[i][j]
वापसी ज
हैश मान का उपयोग
यदि बिटस्ट्रिंग्स पर्याप्त लंबी हैं, तो अलग-अलग बोर्ड स्थितियां लगभग निश्चित रूप से अलग-अलग मानों पर हैश होंगी; हालाँकि लंबे बिटस्ट्रिंग को हेरफेर करने के लिए आनुपातिक रूप से अधिक कंप्यूटर संसाधनों की आवश्यकता होती है। सबसे अधिक उपयोग की जाने वाली बिटस्ट्रिंग (कुंजी) की लंबाई 64 बिट है।[1]कई गेम इंजन ट्रांसपोज़िशन टेबल में केवल हैश मान संग्रहीत करते हैं, मेमोरी उपयोग को कम करने के लिए स्थिति की जानकारी को पूरी तरह से छोड़ देते हैं, और यह मानते हैं कि हैश टकराव नहीं होंगे, या यदि वे होते हैं तो तालिका के परिणामों को बहुत प्रभावित नहीं करेंगे।
ज़ोब्रिस्ट हैशिंग सारणीकरण हैशिंग का पहला ज्ञात उदाहरण है। परिणाम एक K-स्वतंत्र हैशिंग|3-वार स्वतंत्र हैश परिवार है। विशेष रूप से, यह दृढ़ता से यूनिवर्सल हैशिंग है।
उदाहरण के तौर पर, शतरंज में, किसी भी समय 64 वर्गों में से प्रत्येक खाली हो सकता है, या इसमें खेल के 6 टुकड़ों में से एक हो सकता है, जो या तो काले या सफेद होते हैं। इसके अलावा, खेलने की बारी या तो काले की हो सकती है या सफ़ेद की खेलने की बारी हो सकती है। इस प्रकार किसी को 6 x 2 x 64 + 1 = 769 यादृच्छिक बिटस्ट्रिंग्स उत्पन्न करने की आवश्यकता है। किसी स्थिति को देखते हुए, कोई यह पता लगाकर कि कौन से टुकड़े किस वर्ग पर हैं, और प्रासंगिक बिटस्ट्रिंग्स को एक साथ जोड़कर उसका ज़ोब्रिस्ट हैश प्राप्त करता है। यदि स्थिति स्थानांतरित करने के लिए काली है, तो ब्लैक-टू-मूव बिटस्ट्रिंग को ज़ोब्रिस्ट हैश में भी शामिल किया गया है।[1]
हैश मान अद्यतन कर रहा है
हर बार पूरे बोर्ड के लिए हैश की गणना करने के बजाय, जैसा कि ऊपर दिए गए छद्मकोड में होता है, बोर्ड के हैश मान को केवल परिवर्तित पदों के लिए बिटस्ट्रिंग को XOR करके और बिटस्ट्रिंग में XORing द्वारा वृद्धिशील रूप से अपडेट किया जा सकता है। नये पद.[1]उदाहरण के लिए, यदि शतरंज की बिसात पर एक मोहरे को दूसरे वर्ग के किश्ती (शतरंज) से बदल दिया जाता है, तो परिणामी स्थिति मौजूदा हैश को बिटस्ट्रिंग के साथ XORing द्वारा उत्पन्न की जाएगी:
'इस चौक पर मोहरा' (इस चौक पर मोहरे को बाहर निकालना) 'इस चौक पर रुको' (इस चौक पर रुक में XORing) 'रूक एट सोर्स स्क्वायर' (एक्सओआरिंग आउट द रूक एट सोर्स स्क्वायर)
यह खेल का पेड़ को पार करने के लिए ज़ोब्रिस्ट हैशिंग को बहुत कुशल बनाता है।
कंप्यूटर जाओ में, इस तकनीक का उपयोग गो#को डिटेक्शन के नियमों के लिए भी किया जाता है।
व्यापक उपयोग
अधिक उदारतापूर्वक, ज़ोब्रिस्ट हैशिंग को तत्वों के परिमित सेट (गणित) पर लागू किया जा सकता है (शतरंज उदाहरण में, ये तत्व हैं टुपल्स), जब तक प्रत्येक संभावित तत्व को एक यादृच्छिक बिटस्ट्रिंग सौंपी जा सकती है। यह या तो छोटे तत्व स्थानों के लिए यादृच्छिक संख्या जनरेटर के साथ किया जा सकता है, या बड़े तत्वों के लिए हैश फ़ंक्शन के साथ किया जा सकता है। इस पद्धति का उपयोग मोंटे कार्लो सिमुलेशन के दौरान संस्थागत मिश्र धातु विन्यास को पहचानने के लिए किया गया है ताकि पहले से ही गणना किए गए राज्यों पर कम्प्यूटेशनल प्रयास को बर्बाद करने से रोका जा सके।[3]
यह भी देखें
संदर्भ
- ↑ 1.0 1.1 1.2 1.3 Bruce Moreland. Zobrist keys: a means of enabling position comparison.
- ↑ Albert Lindsey Zobrist, A New Hashing Method with Application for Game Playing, Tech. Rep. 88, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, (1969).
- ↑ 3.0 3.1 Mason, D. R.; Hudson, T. S.; Sutton, A. P. (2005). "ज़ोब्रिस्ट कुंजी का उपयोग करके गतिज मोंटे कार्लो सिमुलेशन में राज्य-इतिहास की तेजी से याद". Computer Physics Communications. 165 (1): 37–48. Bibcode:2005CoPhC.165...37M. doi:10.1016/j.cpc.2004.09.007.
