घुटने पर हैशलाइफ

तीन आयामी खेल "लाइफ" के साथ उपद्रव के बाद , मुझे याद आया कि इस खेल के एक साधारण, काफिले संस्करण के लिए, "हैशलाइफ" नामक एक एल्गोरिथ्म है । विकिपीडिया पर कई वाक्यांशों में इसका वर्णन किया गया था, और इस टिप्पणी के साथ वहां की तस्वीर ("6 ऑक्टिलियन पीढ़ियों के माध्यम से कॉन्फ़िगरेशन") मेरे लिए इस विचार से दूर रहने के लिए पर्याप्त थी: इस एल्गोरिथ्म को कितने संसाधनों की आवश्यकता है? क्या मुझे इसे बिल्कुल लेना चाहिए?

एल्गोरिथ्म का सामान्य विचार यह है।

मान लीजिए कि हमारे पास आकार N * N के क्षेत्र का एक वर्ग है (N> = 4 दो की शक्ति है)। तब हम विशिष्ट रूप से इसके आकार के मध्य क्षेत्र (N / 2) * (N / 2) की स्थिति को T = N / 4 चरणों के अनुसार निर्धारित कर सकते हैं। यदि हम मूल वर्ग की स्थिति और शब्दकोश में इसके विकास के परिणाम को याद करते हैं, तो अगली बार जब हम इस तरह के वर्ग से मिलते हैं, तो हम तुरंत यह निर्धारित कर सकते हैं कि इससे क्या बन जाएगा।

मान लीजिए कि एन * एन वर्गों के लिए हम एन / 4 चरणों पर विकास की गणना कर सकते हैं। मान लीजिए हमारे पास एक वर्ग 2N * 2N है। एन / 2 चरणों पर इसके विकास की गणना करने के लिए, आप निम्न कार्य कर सकते हैं।

हम साइड एन / 2 के साथ वर्ग को 16 वर्गों में विभाजित करते हैं। हम साइड एन के साथ 9 वर्ग बनाते हैं, उनमें से प्रत्येक के लिए हम एन / 4 चरणों द्वारा विकास का परिणाम पाते हैं। साइड N / 2 के साथ 9 वर्ग प्राप्त करें। बदले में, हम पहले से ही साइड एन के साथ उनके 4 वर्ग बना देंगे, और उनमें से प्रत्येक के लिए हम एन के 4 चरणों द्वारा विकास का परिणाम पाएंगे। साइड एन / 2 के साथ परिणामी 4 वर्ग साइड एन के साथ एक वर्ग में संयुक्त हैं - इसका उत्तर होगा।





एल्गोरिथ्म को लागू करने के लिए, हमें निम्नलिखित करने में सक्षम होना चाहिए:

1. वर्ग को चार वर्गों में तोड़ें;
2. वर्ग के विकास का परिणाम खोजें;
3. चौकों से उनमें से वर्ग को खोजें।

यदि आप वर्ग के निर्माण के समय विकास के परिणाम की तलाश करते हैं, तो यह 5 क्षेत्रों के साथ एक संरचना के लिए पर्याप्त है:

  वर्ग वर्ग {
	 आंतरिक स्क्वायर एलबी, आरबी, एलटी, आरटी, रेस;
 } 

फिर एक में चार वर्गों के संयोजन के लिए एल्गोरिथ्म निम्नानुसार लिखा जा सकता है:

 स्क्वायर यूनाइट (स्क्वायर ए, स्क्वायर ए 1, स्क्वायर ए 2, स्क्वायर ए 3) {
	 स्क्वायर रेस = फाइंडइन्डोएयर (ए 0, ए 1, ए 2, ए 3);
	 if (रेस! = null) वापसी res;
 // परत T = N / 4 पर
	 स्क्वायर बी 1 = यूनाइट (a0.RB, a1.LB, a0.RT, a1.LT )Res;
	 वर्ग b3 = यूनाइट (a0.LT, a0.RT, a2.LB, a2.RB )Res;
	 स्क्वायर b4 = यूनाइट (a0.RT, a1.LT, a2.RB, a3.LB )Res;
	 वर्ग b5 = यूनाइट (a1.LT, a1.RT, a3.LB, a3.RB )Res;
	 स्क्वायर b7 = यूनाइट (a2.RB, a3.LB, a2.RT, a3.LT )Res;
 // परत T = N / 2 पर	
	 स्क्वायर c0 = यूनाइट (a0.Res, b1, b3, b4) .Res;
	 स्क्वायर c1 = यूनाइट (b1, a1.Res, b4, b5) .Res;
	 स्क्वायर c2 = यूनाइट (b3, b4, a2.Res, b7) .Res;
	 स्क्वायर c3 = यूनाइट (b4, b5, b7, a3.Res) .Res;
	 AddToDictionary (नया स्क्वायर () {LB = a0, RB = a1, LT = a1, RT = a3, Res = Unite (c0, c1, c2, c3)});
 }

दरअसल, बस इतना ही। छोड़ी छोटी चीजें:

पुनरावृत्ति को रोकें। ऐसा करने के लिए, सभी 4 * 4 वर्ग और 1 चरण में उनके विकास के परिणाम को शब्दकोश में दर्ज किया जाता है (वास्तव में, केवल इस स्थान पर कार्यक्रम को खेल के नियमों के ज्ञान की आवश्यकता होती है)। 2 * 2 वर्गों के लिए, आधे चरण के विकास की गणना नहीं की जाती है, उन्हें कुछ विशेष तरीके से चिह्नित किया जाता है।

विकासवादी कदमों की संख्या को दोगुना करें। एल्गोरिथ्म के संदर्भ में, यह मूल क्षेत्र वाले वर्ग के आकार को दोगुना करने के समान है। यदि हम केंद्र को वर्ग में छोड़ना चाहते हैं, तो इसमें शून्य जोड़कर, हम यह कर सकते हैं:

  वर्ग विस्तार (वर्ग x) {
	 स्क्वायर c0 = यूनाइट (ज़ीरो, ज़ीरो, ज़ीरो, x.LB);
	 स्क्वायर c1 = यूनाइट (ज़ीरो, ज़ीरो, x.RB, ज़ीरो);
	 स्क्वायर c2 = यूनाइट (ज़ीरो, x.LT, ज़ीरो, ज़ीरो);
	 स्क्वायर c3 = यूनाइट (x.RT, Zero, Zero, Zero);
	 वापसी यूनाइट (c0, c1, c2, c3);
 }

यहाँ शून्य एक विशेष वर्ग है, सभी भाग और जिसके परिणाम स्वयं के बराबर हैं।

या आप केवल वैकल्पिक क्रियाएँ x = Unite (x, Zero, Zero, Zero) और x = Unite (Zero, Zero, Zero, x) को वैकल्पिक कर सकते हैं। मूल वर्ग केंद्र में कहीं होगा।

एक शब्दकोश को लागू करें। यहां मुझे एक सुंदर समाधान नहीं मिला: मुझे कुंजी द्वारा वस्तु की खोज करने की आवश्यकता है, जो इस वस्तु का 80% है (और न केवल शेष 20% है, बल्कि वस्तु को भी स्वयं खोजना होगा)। विभिन्न प्रकार के संग्रहों से युक्त होने के बाद, मैंने अपना हाथ लहराया और फोरट्रान में अभिनय किया: पांच पूर्णांक सरणियों (एलटी, आरटी, एलबी, आरबी, आरईएस) का वर्णन किया और कहा कि वर्ग इन सरणियों में पूर्णांक-सूचकांक द्वारा निर्धारित किया जाता है। 0 से 15 तक के सूचकांक 2 * 2 वर्गों के लिए आरक्षित हैं। छठी सरणी, दो बार लंबाई, हैशिंग के लिए उपयोग किया जाता है।

आपको फ़ील्ड सेट करने और परिणाम पढ़ने की भी आवश्यकता है - लेकिन यह तकनीक का मामला है। हालाँकि आपको पढ़ने में सावधानी बरतने की ज़रूरत है: यदि आप 63 बार से अधिक का विस्तार करते हैं, तो फ़ील्ड के किनारे की लंबाई अब 64 बिट में फिट नहीं होगी।

मैंने ऐसे निर्माणों पर एल्गोरिथ्म का परीक्षण किया:

"कचरा डिस्पेंसर।"


यह सी / 2 की गति से चलता है, इसके पीछे बहुत सारा मलबा छोड़ देता है और हर 240 कदम पर एक जोड़ी ग्लाइडर छोड़ता है। एक ट्रिलियन पीढ़ी (अधिक सटीक, 2 ^ 40) की गणना 0.73 सेकंड में की गई। लगभग 120,000 वर्ग (प्रत्येक दोहरीकरण के लिए 1,500) शब्दकोष में गिर गए, क्षेत्र पर जीवित कोशिकाओं की संख्या 600 बिलियन है।
परिणामी फ़ील्ड का एक टुकड़ा इस तरह दिखता है:
(2001x2001, 82 KB)

ग्लाइडर बंदूकें की लड़ाई

दो ग्लाइडर बंदूकें एक दूसरे से 800 कोशिकाओं की दूरी पर स्थित हैं, उनके द्वारा छोड़ी गई धाराएं टकराती हैं:
(टी = 2048, 804x504, 11 केबी)
टक्कर के तुरंत बाद, ग्लाइडर्स मलबे के ढेर से बाहर निकलते हैं, जो पहले एक बंदूक को नष्ट करते हैं:
(T = 4096, 1098x1024, 30 Kb)
और फिर दूसरा (जिसके बाद विकास जल्दी समाप्त हो जाता है):
(T = 8192, 3146x3252, 190 Kb)
गिनती का समय 0.84 सेकंड है, शब्दकोश में तत्वों की संख्या लगभग 270,000 है।

"रैंडम फिलिंग"

फ़ील्ड 1024 * 1024 बेतरतीब ढंग से 1/3 के घनत्व वाली कोशिकाओं से भरा होता है। एल्गोरिथ्म के लिए, यह सबसे कठिन मामला है: कॉन्फ़िगरेशन धीरे-धीरे स्थिर हो जाता है, और वर्ग तुरंत दोहराना शुरू नहीं करते हैं।
यहाँ विन्यास में से एक के विकास का एक उदाहरण है:
(T = 0, 1024x1024, 300 Kb)
(T = 1024, 1724x1509, 147 Kb)
(टी = 2048, 2492x2021, 177 Kb)
(टी = 4096, 4028x3045, 300 Kb)
(टी = 8192, 7100x5093, 711 Kb)
मतगणना का समय 14 सेकंड है, शब्दकोश में तत्वों की संख्या लगभग 15 मिलियन है, लगभग 35,000 अंक मैदान पर बने हुए हैं।

इस एल्गोरिथ्म में क्या असामान्य है? मैं निम्नलिखित नोट करूंगा:

1. लगभग प्रयास के बिना, हमें एक ऐसा कार्यक्रम मिला जो खाली क्षेत्रों को सक्रिय लोगों से अलग कर सकता है, सक्रिय क्षेत्रों को ट्रैक कर सकता है और उनकी सहभागिता का काम कर सकता है। यदि हमने कई गतिशील दो-आयामी सरणियों के माध्यम से इस तरह के विश्लेषण को सीधे लिखा, तो कार्यक्रम बहुत अधिक जटिल होगा।
2. एल्गोरिथ्म न केवल टी चरणों के माध्यम से क्षेत्र की स्थिति की गणना करता है - यह पूरे विकास को याद करता है। अपने काम के परिणाम से, कोई भी आसानी से किसी भी अंतराल के माध्यम से राज्य को निकाल सकता है T_k = 2 ^ k (एक समय के बाद क्षेत्र की स्थिति कैसे प्राप्त करें जो दो की शक्ति नहीं है एक अलग प्रश्न है)। एक ही समय में, पूरे विकास को अच्छी तरह से पैक किया जाता है - फिर से, विशेष प्रयासों के बिना: "^ कचरा ट्रक" की 40 पीढ़ी 3 एमबी में फिट होती हैं।
3. इस तथ्य के बावजूद कि शब्दकोश प्रारंभिक कॉन्फ़िगरेशन के अनुसार बनाया गया है, इसकी सामग्री इस कॉन्फ़िगरेशन पर निर्भर नहीं करती है। कुछ गणना समाप्त करने के बाद, हम नए कॉन्फ़िगरेशन के लिए एक ही शब्दकोश का उपयोग कर सकते हैं, और भाग्य के साथ, बहुत समय बचा सकते हैं (हालांकि मैंने यह कोशिश नहीं की है)।
4. औपचारिक रूप से, विमान पर विन्यास 4-पेड़ों के रूप में प्रस्तुत किए जाते हैं। लेकिन पड़ोसी शाखाओं के चरम बिंदुओं के बीच बातचीत का विश्लेषण करने के लिए, हम स्पष्ट रूप से इन बिंदुओं पर नीचे नहीं जाते हैं, लेकिन केवल 1-2 कदम नीचे जाते हैं, जिसके बाद हम अपनी समस्या को हल करने के लिए उपयुक्त एक पेड़ की तलाश / निर्माण करते हैं। हालाँकि, यहाँ कुछ भी असामान्य नहीं है - सिर्फ इसलिए कि हम नए नोड के निर्माण के कारण समय नहीं गंवाते हैं, बल्कि इसके विपरीत।
5. एल्गोरिथ्म में, न तो "परमाणु" कोशिकाओं के वास्तविक आकार और न ही उनके राज्यों की संख्या का उपयोग कहीं भी किया जाता है। न्यूनतम स्तर जो पुनरावृत्ति को कम कर सकता है, वह 16 राज्यों वाली कोशिकाएं हैं, जिन्हें हम 2 * 2 वर्ग के रूप में देखते हैं। इस स्तर पर अंतरिक्ष-समय (एल्गोरिथ्म के लिए) एक चेहरा-केंद्रित जाली (एक तीन-आयामी शतरंजबोर्ड जिसमें से केवल काली कोशिकाओं को लिया गया था) जैसा दिखता है। 16 की संख्या हमने कॉनवे के नियमों के आधार पर खुद का आविष्कार किया। एल्गोरिथ्म में, यह कुछ भी हो सकता है, मुख्य कोड इस पर निर्भर नहीं करता है