ज़ोब्रिस्ट हैशिंग: Difference between revisions

From Vigyanwiki
(Created page with "{{short description|Hash function construction used in computer programs that play abstract board games}} ज़ोब्रिस्ट हैशिंग (जिसे ज...")
 
 
(6 intermediate revisions by 2 users not shown)
Line 1: Line 1:
{{short description|Hash function construction used in computer programs that play abstract board games}}
{{short description|Hash function construction used in computer programs that play abstract board games}}
ज़ोब्रिस्ट हैशिंग (जिसे ज़ोब्रिस्ट कुंजी या ज़ोब्रिस्ट हस्ताक्षर भी कहा जाता है <ref name="moreland" >Bruce Moreland. [https://web.archive.org/web/20070822204038/http://www.seanet.com/~brucemo/topics/zobrist.htm Zobrist keys: a means of enabling position comparison.]</ref>) एक [[हैश फंकशन]] निर्माण है जिसका उपयोग [[कंप्यूटर प्रोग्राम]]ों में किया जाता है जो [[कंप्यूटर शतरंज]] और [[ कंप्यूटर जाओ ]] जैसे अमूर्त बोर्ड गेम खेलते हैं, [[स्थानान्तरण तालिका]] को लागू करने के लिए, एक विशेष प्रकार की [[ हैश तालिका ]] जिसे बोर्ड स्थिति द्वारा अनुक्रमित किया जाता है और उसी स्थिति का विश्लेषण करने से बचने के लिए उपयोग किया जाता है एक से ज्यादा बार। ज़ोब्रिस्ट हैशिंग का नाम इसके आविष्कारक, [[अल्बर्ट लिंडसे ज़ोब्रिस्ट (कंप्यूटर वैज्ञानिक)]] के नाम पर रखा गया है।<ref>Albert Lindsey Zobrist, [https://www.cs.wisc.edu/techreports/1970/TR88.pdf ''A New Hashing Method with Application for Game Playing''], Tech. Rep. 88, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, (1969).</ref> इसे क्रिस्टलीय सामग्रियों के सिमुलेशन में संस्थागत मिश्र धातु विन्यास को पहचानने की एक विधि के रूप में भी लागू किया गया है।<ref name=MonteCarlo/> ज़ोब्रिस्ट हैशिंग आम तौर पर उपयोगी अंतर्निहित तकनीक का पहला ज्ञात उदाहरण है जिसे [[ सारणीकरण हैशिंग ]] कहा जाता है।
'''ज़ोब्रिस्ट हैशिंग''' (जिसे ज़ोब्रिस्ट कीज़ या ज़ोब्रिस्ट सिग्नेचर्स भी कहा जाता है।<ref name="moreland" >Bruce Moreland. [https://web.archive.org/web/20070822204038/http://www.seanet.com/~brucemo/topics/zobrist.htm Zobrist keys: a means of enabling position comparison.]</ref>) एक [[हैश फंकशन]] कंस्ट्रक्शन, जिसका उपयोग [[कंप्यूटर प्रोग्राम|कंप्यूटर प्रोग्रामों]] में किया जाता है, इसी प्रकार जो [[कंप्यूटर शतरंज|कंप्यूटर चैस]] और [[ कंप्यूटर जाओ |कंप्यूटर गो]] जैसे अब्स्ट्रैक्ट बोर्ड गेम खेलते हैं, [[स्थानान्तरण तालिका|ट्रांस्पोसिशन टेबल]] को लागू करने के लिए, एक विशेष प्रकार की [[ हैश तालिका |हैश टेबल]] जिसे बोर्ड पोजीशन द्वारा अनुक्रमित किया जाता है और उसी पोजीशन को एनालाइज़िंग करने से बचने के लिए उपयोग किया जाता है एक से ज्यादा बार ज़ोब्रिस्ट हैशिंग का नाम इसके आविष्कारक, [[अल्बर्ट लिंडसे ज़ोब्रिस्ट (कंप्यूटर वैज्ञानिक)]] के नाम पर रखा गया है।<ref>Albert Lindsey Zobrist, [https://www.cs.wisc.edu/techreports/1970/TR88.pdf ''A New Hashing Method with Application for Game Playing''], Tech. Rep. 88, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin, (1969).</ref> इसे क्रिस्टलीय सामग्रियों के सिमुलेशन में सब्स्टिटयूशनल एलॉय कॉन्फ़िगरेशन को पहचानने के एक मेथड के रूप में भी लागू किया गया है।<ref name="MonteCarlo">{{Cite journal | last1 = Mason | first1 = D. R. | last2 = Hudson | first2 = T. S. | last3 = Sutton | first3 = A. P. | title = ज़ोब्रिस्ट कुंजी का उपयोग करके गतिज मोंटे कार्लो सिमुलेशन में राज्य-इतिहास की तेजी से याद| doi = 10.1016/j.cpc.2004.09.007 | journal = Computer Physics Communications | volume = 165 | pages = 37–48 | year = 2005 | issue = 1 |bibcode = 2005CoPhC.165...37M }}</ref> इसी प्रकार ज़ोब्रिस्ट हैशिंग सामान्यतः यूज़फुल अंडरलाइंग तकनीक का पहला ज्ञात उदाहरण है जिसे [[ सारणीकरण हैशिंग |टैबुलेशन हैशिंग]] कहा जाता है।


==हैश मान की गणना==
==हैश वैल्यू की गणना==
ज़ोब्रिस्ट हैशिंग एक बोर्ड गेम के प्रत्येक संभावित तत्व के लिए [[छद्म यादृच्छिक संख्या जनरेटर]] [[बिटस्ट्रिंग]]्स द्वारा शुरू होती है, यानी एक टुकड़े और एक स्थिति के प्रत्येक संयोजन के लिए (शतरंज के खेल में, यह 12 टुकड़े × 64 बोर्ड स्थिति है, या 18 × 64 यदि राजा और बदमाश हैं) वह अभी भी महल बना सकता है, और प्यादे जो एन पासेंट को पकड़ सकते हैं, दोनों रंगों के लिए अलग-अलग व्यवहार किया जाता है)। अब किसी भी बोर्ड कॉन्फ़िगरेशन को स्वतंत्र टुकड़े/स्थिति घटकों में विभाजित किया जा सकता है, जो पहले उत्पन्न यादृच्छिक बिटस्ट्रिंग्स पर मैप किए जाते हैं। अंतिम ज़ोब्रिस्ट हैश की गणना बिटवाइज़ [[XOR]] का उपयोग करके उन बिटस्ट्रिंग्स को मिलाकर की जाती है। शतरंज के खेल के लिए उदाहरण छद्म कोड:{{cn|date=September 2019}}
ज़ोब्रिस्ट हैशिंग एक बोर्ड गेम के प्रत्येक संभावित तत्व के लिए [[रैंडम्ली जनरेटिंग बिटस्ट्रिंग]] उत्पन्न करके प्रारंभ होती है, यानी एक पीस और एक पोजीशन के प्रत्येक संयोजन के लिए (चैस के खेल में, यह 12 पीसेस × 64 बोर्ड पोजीशन है, या 18 × 64 यदि किंग्स और रूक्स हैं) अभी भी महल बनाया जा सकता है, और जो प्यादे एन पासेंट को पकड़ सकते हैं, इसी प्रकार उन्हें दोनों रंगों के लिए भिन्न-भिन्न माना जाता है। अब किसी भी बोर्ड कॉन्फ़िगरेशन को इंडिपेंडेंट पीसेस/पोजीशन कंपोनेंट्स में विभाजित किया जा सकता है, जो पहले रैंडम बिटस्ट्रिंग जनरेटिंग पर मैप किए जाते हैं। इसी प्रकार फाइनल ज़ोब्रिस्ट हैश की कंप्यूटिंग बिटवाइज़ [[एक्सओआर]] का उपयोग करके उन बिटस्ट्रिंग्स को मिलाकर की जाती है। चैस के खेल के लिए उदाहरण सीयूडोकोड:<syntaxhighlight lang="c">
constant indices
    white_pawn := 1
    white_rook := 2
    # etc.
    black_king := 12


निरंतर सूचकांक
function init_zobrist():
    सफ़ेद_प्यादा := 1
    # fill a table of random numbers/bitstrings
    सफ़ेद_रूक := 2
    table := a 2-d array of size 64×12
    # वगैरह।
    for i from 1 to 64: # loop over the board, represented as a linear array
    ब्लैक_किंग := 12
        for j from 1 to 12:     # loop over the pieces
            table[i][j] := random_bitstring()
फ़ंक्शन init_zobrist():
    table.black_to_move = random_bitstring()
    # यादृच्छिक संख्याओं/बिटस्ट्रिंग्स की एक तालिका भरें
    तालिका:= 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]
    वापसी ज


==हैश मान का उपयोग==
function hash(board):
यदि बिटस्ट्रिंग्स पर्याप्त लंबी हैं, तो अलग-अलग बोर्ड स्थितियां लगभग निश्चित रूप से अलग-अलग मानों पर हैश होंगी; हालाँकि लंबे बिटस्ट्रिंग को हेरफेर करने के लिए आनुपातिक रूप से अधिक कंप्यूटर संसाधनों की आवश्यकता होती है। सबसे अधिक उपयोग की जाने वाली बिटस्ट्रिंग (कुंजी) की लंबाई 64 बिट है।<ref name="moreland" />कई गेम इंजन ट्रांसपोज़िशन टेबल में केवल हैश मान संग्रहीत करते हैं, मेमोरी उपयोग को कम करने के लिए स्थिति की जानकारी को पूरी तरह से छोड़ देते हैं, और यह मानते हैं कि हैश टकराव नहीं होंगे, या यदि वे होते हैं तो तालिका के परिणामों को बहुत प्रभावित नहीं करेंगे।
    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
</syntaxhighlight>


ज़ोब्रिस्ट हैशिंग सारणीकरण हैशिंग का पहला ज्ञात उदाहरण है। परिणाम एक K-स्वतंत्र हैशिंग|3-वार स्वतंत्र हैश परिवार है। विशेष रूप से, यह दृढ़ता से [[यूनिवर्सल हैशिंग]] है।
==हैश वैल्यू का उपयोग==
यदि बिटस्ट्रिंग्स पर्याप्त लंबी हैं, तो भिन्न-भिन्न बोर्ड पोज़िशन्स लगभग निश्चित रूप से भिन्न-भिन्न वैल्यूज़ पर हैश होती है; चूंकि लॉन्ग बिटस्ट्रिंग को मैनिपुलेट करने के लिए आनुपातिक रूप से अधिक कंप्यूटर संसाधनों की आवश्यकता होती है। इसी प्रकार सबसे अधिक उपयोग की जाने वाली बिटस्ट्रिंग (कीज़) की लंबाई 64 बिट है।<ref name="moreland" /> कई गेम इंजन ट्रांसपोज़िशन टेबल में केवल हैश वैल्यू संग्रहीत करते हैं, मेमोरी उपयोग को कम करने के लिए पोजीशन की जानकारी को पूरे प्रकार से छोड़ देते हैं, और यह मानते हैं कि हैश कोलिज़न नहीं होंगे, या यदि वे होते हैं तो टेबल के परिणामों को बहुत इन्फ्लुएंस नहीं करते है।


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


उदाहरण के लिए, [[शतरंज|चैस]] में, किसी भी समय 64 स्क्वायरों में से प्रत्येक खाली हो सकता है, या इसमें खेल के 6 पीसेस में से एक हो सकता है, जो या तो काले या सफेद होते हैं। इसके अतिरिक्त, खेलने की बारी या तो काले की हो सकती है या फिर सफ़ेद की खेलने की बारी हो सकती है। इस प्रकार किसी को 6 x 2 x 64 + 1 = 769 रैंडम बिटस्ट्रिंग्स उत्पन्न करने की आवश्यकता है। किसी पोजीशन को देखते हुए, कोई यह पता लगाकर कि कौन से पीसेस किस स्क्वायर पर हैं, और प्रासंगिक बिटस्ट्रिंग्स को एक साथ जोड़कर उसका ज़ोब्रिस्ट हैश प्राप्त करता है। यदि पोजीशन मूव करने के लिए काली है, तो ब्लैक-टू-मूव बिटस्ट्रिंग को ज़ोब्रिस्ट हैश में भी सम्मिलित किया गया है।<ref name="moreland" />
==अपडेटिंग हैश वैल्यू==
इसी प्रकार पूरे बोर्ड के लिए हर बार हैश की कंप्यूटिंग करने के अतिरिक्त, जैसा कि ऊपर दिए गए सीयूडोकोड में होता है, बोर्ड के हैश मान को केवल उन पोसिशन्स के लिए बिटस्ट्रिंग को एक्सओआरिंग करके और नए पोसिशन्स के लिए बिटस्ट्रिंग में एक्सओआरिंग द्वारा इंक्रीमेंटली रूप से अपडेट किया जा सकता है।<ref name="moreland" /> उदाहरण के लिए, यदि शतरंज की बिसात पर एक रूक को दूसरे स्क्वायर के पॉन से परिवर्तित कर दिया जाता है, तो रिजल्टिंग पोजीशन उपस्थित हैश को बिटस्ट्रिंग के साथ एक्सओआरिंग द्वारा एक्सीस्ट किया जाता है:
'pawn at this square'      (XORing ''out'' the pawn at this square)
'rook at this square'      (XORing ''in'' the rook at this square)
'rook at source square'    (XORing ''out'' the rook at the source square)
यह [[गेम ट्री]] को पार करने के लिए ज़ोब्रिस्ट हैशिंग को बहुत एफ्फिसिएंट बनाता है।


==हैश मान अद्यतन कर रहा है==
[[कंप्यूटर गो]] में इस तकनीक का उपयोग सुपरको डिटेक्शन के लिए भी किया जाता है।
हर बार पूरे बोर्ड के लिए हैश की गणना करने के बजाय, जैसा कि ऊपर दिए गए छद्मकोड में होता है, बोर्ड के हैश मान को केवल परिवर्तित पदों के लिए बिटस्ट्रिंग को XOR करके और बिटस्ट्रिंग में XORing द्वारा वृद्धिशील रूप से अपडेट किया जा सकता है। नये पद.<ref name="moreland" />उदाहरण के लिए, यदि शतरंज की बिसात पर एक मोहरे को दूसरे वर्ग के किश्ती (शतरंज) से बदल दिया जाता है, तो परिणामी स्थिति मौजूदा हैश को बिटस्ट्रिंग के साथ XORing द्वारा उत्पन्न की जाएगी:
 
'इस चौक पर मोहरा' (इस चौक पर मोहरे को बाहर निकालना)
'इस चौक पर रुको' (इस चौक पर रुक में XORing)
'रूक एट सोर्स स्क्वायर' (एक्सओआरिंग आउट द रूक एट सोर्स स्क्वायर)
 
यह [[ खेल का पेड़ ]] को पार करने के लिए ज़ोब्रिस्ट हैशिंग को बहुत कुशल बनाता है।
 
[[ कंप्यूटर जाओ ]] में, इस तकनीक का उपयोग गो#को डिटेक्शन के नियमों के लिए भी किया जाता है।


==व्यापक उपयोग==
==व्यापक उपयोग==
अधिक उदारतापूर्वक, ज़ोब्रिस्ट हैशिंग को तत्वों के परिमित [[सेट (गणित)]] पर लागू किया जा सकता है (शतरंज उदाहरण में, ये तत्व हैं <math>(piece, position)</math> टुपल्स), जब तक प्रत्येक संभावित तत्व को एक यादृच्छिक बिटस्ट्रिंग सौंपी जा सकती है। यह या तो छोटे तत्व स्थानों के लिए यादृच्छिक संख्या जनरेटर के साथ किया जा सकता है, या बड़े तत्वों के लिए हैश फ़ंक्शन के साथ किया जा सकता है। इस पद्धति का उपयोग [[मोंटे कार्लो सिमुलेशन]] के दौरान संस्थागत मिश्र धातु विन्यास को पहचानने के लिए किया गया है ताकि पहले से ही गणना किए गए राज्यों पर कम्प्यूटेशनल प्रयास को बर्बाद करने से रोका जा सके।<ref name=MonteCarlo>{{Cite journal | last1 = Mason | first1 = D. R. | last2 = Hudson | first2 = T. S. | last3 = Sutton | first3 = A. P. | title = ज़ोब्रिस्ट कुंजी का उपयोग करके गतिज मोंटे कार्लो सिमुलेशन में राज्य-इतिहास की तेजी से याद| doi = 10.1016/j.cpc.2004.09.007 | journal = Computer Physics Communications | volume = 165 | pages = 37–48 | year = 2005 | issue = 1 |bibcode = 2005CoPhC.165...37M }}</ref>
अधिक जैनेरिकली, ज़ोब्रिस्ट हैशिंग को एलिमेंट्स के फाइनाइट [[सेट (गणित)]] पर लागू किया जा सकता है (चैस उदाहरण में, ये एलिमेंट्स हैं <math>(piece, position)</math> टुपल्स), जब तक कि प्रत्येक पॉसिबल एलिमेंट्स को एक रैंडम बिटस्ट्रिंग एसाइन्ड किया जा सकता है। यह या तो स्मॉल एलिमेंट्स स्पेसेस के लिए, या इसके अतिरिक्त रैंडम नंबर जनरेटर के साथ किया जा सकता है, या लार्जर एलिमेंट्स के लिए हैश फ़ंक्शन के साथ किया जा सकता है। इसी प्रकार इस मेथड का उपयोग [[मोंटे कार्लो सिमुलेशन]] के समय सब्स्टिटूशनल एलाय कॉन्फ़िगरेशन  को पहचानने के लिए किया गया है जिससे की पहले से ही कैलकुलेट किए गए स्टेट्स पर कम्प्यूटेशनल प्रयास को डिस्ट्रॉय होने से रोका जा सकता है।<ref name="MonteCarlo" />
 
 
==यह भी देखें==
==यह भी देखें==
* [[अल्फा-बीटा प्रूनिंग]]
* [[अल्फा-बीटा प्रूनिंग]]
Line 64: Line 57:
[[Category: Machine Translated Page]]
[[Category: Machine Translated Page]]
[[Category:Created On 09/08/2023]]
[[Category:Created On 09/08/2023]]
[[Category:Vigyan Ready]]

Latest revision as of 07:18, 16 October 2023

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

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

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

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

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

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

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

'pawn at this square'      (XORing out the pawn at this square)
'rook at this square'      (XORing in the rook at this square)
'rook at source square'    (XORing out the rook at the source square)

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

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

व्यापक उपयोग

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

यह भी देखें

संदर्भ

  1. ↑ 1.0 1.1 1.2 1.3 Bruce Moreland. Zobrist keys: a means of enabling position comparison.
  2. ↑ 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. ↑ 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.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=ज़ोब्रिस्ट_हैशिंग&oldid=267650’