ज़ोब्रिस्ट हैशिंग: Difference between revisions
No edit summary |
No edit summary |
||
| 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> ज़ोब्रिस्ट हैशिंग सामान्यतः यूज़फुल अंडरलाइंग तकनीक का पहला ज्ञात उदाहरण है जिसे [[ सारणीकरण हैशिंग |टैबुलेशन हैशिंग]] कहा जाता है। | ||
==हैश वैल्यू की गणना== | ==हैश वैल्यू की गणना== | ||
| Line 32: | Line 32: | ||
यदि बिटस्ट्रिंग्स पर्याप्त लंबी हैं, तो भिन्न-भिन्न बोर्ड पोज़िशन्स लगभग निश्चित रूप से भिन्न-भिन्न वैल्यूज़ पर हैश होती है; चूंकि लॉन्ग बिटस्ट्रिंग को मैनिपुलेट करने के लिए आनुपातिक रूप से अधिक कंप्यूटर संसाधनों की आवश्यकता होती है। सबसे अधिक उपयोग की जाने वाली बिटस्ट्रिंग (कीज़) की लंबाई 64 बिट है।<ref name="moreland" /> कई गेम इंजन ट्रांसपोज़िशन टेबल में केवल हैश वैल्यू संग्रहीत करते हैं, मेमोरी उपयोग को कम करने के लिए पोजीशन की जानकारी को पूरे प्रकार से छोड़ देते हैं, और यह मानते हैं कि हैश कोलिज़न नहीं होंगे, या यदि वे होते हैं तो टेबल के परिणामों को बहुत इन्फ्लुएंस नहीं करते है। | यदि बिटस्ट्रिंग्स पर्याप्त लंबी हैं, तो भिन्न-भिन्न बोर्ड पोज़िशन्स लगभग निश्चित रूप से भिन्न-भिन्न वैल्यूज़ पर हैश होती है; चूंकि लॉन्ग बिटस्ट्रिंग को मैनिपुलेट करने के लिए आनुपातिक रूप से अधिक कंप्यूटर संसाधनों की आवश्यकता होती है। सबसे अधिक उपयोग की जाने वाली बिटस्ट्रिंग (कीज़) की लंबाई 64 बिट है।<ref name="moreland" /> कई गेम इंजन ट्रांसपोज़िशन टेबल में केवल हैश वैल्यू संग्रहीत करते हैं, मेमोरी उपयोग को कम करने के लिए पोजीशन की जानकारी को पूरे प्रकार से छोड़ देते हैं, और यह मानते हैं कि हैश कोलिज़न नहीं होंगे, या यदि वे होते हैं तो टेबल के परिणामों को बहुत इन्फ्लुएंस नहीं करते है। | ||
ज़ोब्रिस्ट हैशिंग टैबुलेशन हैशिंग का पहला ज्ञात उदाहरण है। | ज़ोब्रिस्ट हैशिंग टैबुलेशन हैशिंग का पहला ज्ञात उदाहरण है। रिजल्ट एक 3-वाइज़ इंडिपेंडेंट हैश फैमिली है। विशेष रूप से, यह स्ट्रॉन्ग्ली से [[यूनिवर्सल हैशिंग]] है। | ||
उदाहरण के | उदाहरण के लिए, [[शतरंज|चैस]] में, किसी भी समय 64 स्क्वायरों में से प्रत्येक खाली हो सकता है, या इसमें खेल के 6 पीसेस में से एक हो सकता है, जो या तो काले या सफेद होते हैं। इसके अतिरिक्त, खेलने की बारी या तो काले की हो सकती है या फिर सफ़ेद की खेलने की बारी हो सकती है। इस प्रकार किसी को 6 x 2 x 64 + 1 = 769 रैंडम बिटस्ट्रिंग्स उत्पन्न करने की आवश्यकता है। किसी पोजीशन को देखते हुए, कोई यह पता लगाकर कि कौन से पीसेस किस स्क्वायर पर हैं, और प्रासंगिक बिटस्ट्रिंग्स को एक साथ जोड़कर उसका ज़ोब्रिस्ट हैश प्राप्त करता है। यदि पोजीशन मूव करने के लिए काली है, तो ब्लैक-टू-मूव बिटस्ट्रिंग को ज़ोब्रिस्ट हैश में भी सम्मिलित किया गया है।<ref name="moreland" /> | ||
यदि पोजीशन | ==अपडेटिंग हैश वैल्यू== | ||
==हैश वैल्यू | पूरे बोर्ड के लिए हर बार हैश की कंप्यूटिंग करने के अतिरिक्त, जैसा कि ऊपर दिए गए सीयूडोकोडे में होता है, बोर्ड के हैश मान को केवल उन पोसिशन्स के लिए बिटस्ट्रिंग को एक्सओआरिंग करके और नए पोसिशन्स के लिए बिटस्ट्रिंग में एक्सओआरिंग द्वारा इंक्रीमेंटली रूप से अपडेट किया जा सकता है।<ref name="moreland" /> उदाहरण के लिए, यदि शतरंज की बिसात पर एक रूक को दूसरे स्क्वायर के पॉन से परिवर्तित कर दिया जाता है, तो रिजल्टिंग पोजीशन उपस्थित हैश को बिटस्ट्रिंग के साथ एक्सओआरिंग द्वारा एक्सीस्ट किया जाता है: | ||
'इस | 'इस स्क्वायर पर पॉन' (इस स्क्वायर पर पॉन को बाहर निकालना) | ||
'इस | 'इस स्क्वायर पर रूक' (इस स्क्वायर पर रुक में एक्सओआरिंग) | ||
'रूक | 'रूक पर सोर्स स्क्वायर' (एक्सओआरिंग आउट द रूक एट सोर्स स्क्वायर) | ||
यह [[ | यह [[गेम ट्री]] को पार करने के लिए ज़ोब्रिस्ट हैशिंग को बहुत एफ्फिसिएंट बनाता है। | ||
[[ कंप्यूटर | [[कंप्यूटर गो]] में इस तकनीक का उपयोग सुपरको डिटेक्शन के लिए भी किया जाता है। | ||
==व्यापक उपयोग== | ==व्यापक उपयोग== | ||
अधिक | अधिक जैनेरिकली, ज़ोब्रिस्ट हैशिंग को एलिमेंट्स के फाइनाइट [[सेट (गणित)]] पर लागू किया जा सकता है (चैस उदाहरण में, ये एलिमेंट्स हैं <math>(piece, position)</math> टुपल्स), जब तक कि प्रत्येक पॉसिबल एलिमेंट्स को एक रैंडम बिटस्ट्रिंग एसाइन्ड किया जा सकता है। यह या तो स्मॉल एलिमेंट्स स्पेसेस के लिए, या इसके अतिरिक्त रैंडम नंबर जनरेटर के साथ किया जा सकता है, या लार्जर एलिमेंट्स के लिए हैश फ़ंक्शन के साथ किया जा सकता है। इस मेथड का उपयोग [[मोंटे कार्लो सिमुलेशन]] के समय सब्स्टिटूशनल एलाय कॉन्फ़िगरेशन को पहचानने के लिए किया गया है जिससे की पहले से ही कैलकुलेट किए गए स्टेट्स पर कम्प्यूटेशनल प्रयास को डिस्ट्रॉय होने से रोका जा सकता है।<ref name="MonteCarlo" /> | ||
==यह भी देखें== | ==यह भी देखें== | ||
* [[अल्फा-बीटा प्रूनिंग]] | * [[अल्फा-बीटा प्रूनिंग]] | ||
Revision as of 10:04, 16 August 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] उदाहरण के लिए, यदि शतरंज की बिसात पर एक रूक को दूसरे स्क्वायर के पॉन से परिवर्तित कर दिया जाता है, तो रिजल्टिंग पोजीशन उपस्थित हैश को बिटस्ट्रिंग के साथ एक्सओआरिंग द्वारा एक्सीस्ट किया जाता है:
'इस स्क्वायर पर पॉन' (इस स्क्वायर पर पॉन को बाहर निकालना) 'इस स्क्वायर पर रूक' (इस स्क्वायर पर रुक में एक्सओआरिंग) 'रूक पर सोर्स स्क्वायर' (एक्सओआरिंग आउट द रूक एट सोर्स स्क्वायर)
यह गेम ट्री को पार करने के लिए ज़ोब्रिस्ट हैशिंग को बहुत एफ्फिसिएंट बनाता है।
कंप्यूटर गो में इस तकनीक का उपयोग सुपरको डिटेक्शन के लिए भी किया जाता है।
व्यापक उपयोग
अधिक जैनेरिकली, ज़ोब्रिस्ट हैशिंग को एलिमेंट्स के फाइनाइट सेट (गणित) पर लागू किया जा सकता है (चैस उदाहरण में, ये एलिमेंट्स हैं टुपल्स), जब तक कि प्रत्येक पॉसिबल एलिमेंट्स को एक रैंडम बिटस्ट्रिंग एसाइन्ड किया जा सकता है। यह या तो स्मॉल एलिमेंट्स स्पेसेस के लिए, या इसके अतिरिक्त रैंडम नंबर जनरेटर के साथ किया जा सकता है, या लार्जर एलिमेंट्स के लिए हैश फ़ंक्शन के साथ किया जा सकता है। इस मेथड का उपयोग मोंटे कार्लो सिमुलेशन के समय सब्स्टिटूशनल एलाय कॉन्फ़िगरेशन को पहचानने के लिए किया गया है जिससे की पहले से ही कैलकुलेट किए गए स्टेट्स पर कम्प्यूटेशनल प्रयास को डिस्ट्रॉय होने से रोका जा सकता है।[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.
