पहला भाग (कोड विश्लेषण) यहाँ है: https://habr.com/post/420725/ ।

एल्गोरिथ्म

विवरण

एल्गोरिथ्म लगातार निम्न चरण करता है:

1. वह तब तक इंतजार करता है जब तक कि एक नया टेट्रीमिनो नहीं बन जाता।
2. नए बनाए गए tetrimino के प्रकार, अगले tetrimino के प्रकार (पूर्वावलोकन क्षेत्र में आकृति) और खेल के मैदान की सामग्री की जाँच करता है।
3. खेल के मैदान में दो टेट्रिमिनोज को जोड़ने के लिए सभी संभावित तरीकों की व्याख्या करता है और प्रत्येक संभावना का मूल्यांकन करता है।
4. नव निर्मित टेट्रिमिनो को स्थानांतरित करता है ताकि यह सबसे अच्छी तरह से ज्ञात संभावना के स्थान से मेल खाता हो।

इनमें से प्रत्येक चरण का वर्णन नीचे विस्तार से किया गया है।

लॉक खोज

टेट्रिस के एक सरलीकृत संस्करण पर विचार करें, जिसमें आकार स्वचालित रूप से नहीं आते हैं। आंकड़ा नीचे लाने का एकमात्र तरीका यह है कि इसे धीरे से कम किया जाए। खेल से समय निकालने के बाद, हम अपनी स्थिति और अभिविन्यास द्वारा सक्रिय टेट्रीमिनो की स्थिति का पूरी तरह से वर्णन कर सकते हैं। आकृति में प्रारंभिक निर्माण का एक ज्ञात स्थान होता है, और एक राज्य से दूसरे राज्य में बदलने के लिए निम्नलिखित कार्यों का उपयोग किया जाता है:

• एक कदम नीचे
• एक कदम बाकी है
• एक कदम दाईं ओर ले जाएं
• एक कदम वामावर्त घुमाएं
• दक्षिणावर्त घूमना

ये ऑपरेशन तभी लागू होते हैं, जब परिणामस्वरूप टेट्रिमिनो के वर्ग खेल मैदान की खाली कोशिकाओं के अनुरूप होते हैं। जब एक कदम नीचे जाना असंभव है, तो राज्य को अवरुद्ध माना जाता है। हालांकि, चूंकि हमने टेट्रिस का सरलीकरण किया है और लॉकिंग की प्रतीक्षा अनिवार्य रूप से अनंत है, इसलिए लॉक किए गए राज्य को फिसलने और स्क्रॉल करके अन्य ऑपरेशनों द्वारा और अधिक रूपांतरित किया जा सकता है।

कई अवरुद्ध राज्य संचालन के न्यूनतम अनुक्रम के साथ हैं जो उन्हें बनाते हैं, जिन्हें पहले-पहले खोज (बीएफएस) का उपयोग करके पाया जा सकता है। जैसा कि नीचे कहा गया है, यह मध्यवर्ती परिणामों को संग्रहीत करने के लिए एक कतार का उपयोग करता है।

1. हम राज्य का निर्माण करते हैं।
2. हम राज्य को कतार से हटाते हैं।
3. रूपांतरण प्रक्रिया का उपयोग करके हमें निम्नलिखित राज्य मिलते हैं।
4. यदि उनके बीच कोई नीचे की ओर गति नहीं है, तो कतार से हटा दिया गया राज्य अवरुद्ध है।
5. हम बाद में बताते हैं कि हमने अभी तक दौरा नहीं किया है।
6. यदि कतार खाली नहीं है, तो चरण 2 से दोहराएं।

कार्यक्रम निम्नलिखित क्षेत्रों के साथ एक वस्तु के रूप में प्रत्येक राज्य का प्रतिनिधित्व करता है:

{ x, y, rotation, visited, predecessor }

तैयारी की प्रक्रिया में, कार्यक्रम राज्य वस्तुओं का एक त्रि-आयामी सरणी बनाता है (20 पंक्तियों × 10 कॉलम × 4 बदल जाता है), x , y और rotation तदनुसार प्रारंभ करना।

जब राज्य पंक्तिबद्ध होता है, तो visited फ़ील्ड को चिह्नित visited जाता है। बीएफएस में, यह मान्य है क्योंकि प्रत्येक बाद की स्थिति में कुल पथ लंबाई 1 से बढ़ जाती है। अर्थात्, पथ की लंबाई को बढ़ाकर एक बाद की स्थिति बनाना असंभव है जिसे आदेश बनाए रखने के लिए कतार के अंत के अलावा कहीं और सम्मिलित करने की आवश्यकता होती है।

predecessor क्षेत्र उस राज्य वस्तु को इंगित करता है जिससे वर्तमान स्थिति उत्पन्न होती है। यह तब निर्धारित किया जाता है जब राज्य पंक्तिबद्ध होता है। सृजन राज्य का कोई पिछला राज्य नहीं है।

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

राज्य वस्तुओं का एक त्रि-आयामी सरणी, एक कतार और BFS को एक वर्ग में पैक किया जाता है। उसके पास एक खोज विधि है जो खेल के मैदान (द्वि-आयामी सरणी), टेट्रीमिनो और श्रोता के प्रकार को प्राप्त करती है। हर बार जब एक लॉक अवस्था का पता लगाया जाता है, तो टेट्रीमिनो को उपयुक्त स्थान पर जोड़कर खेल का मैदान अपडेट किया जाता है। फिर, परिवर्तन के बारे में जानकारी के साथ परिवर्तित किया गया खेल मैदान प्रसंस्करण के लिए श्रोता को प्रेषित किया जाता है। श्रोता के लौटने के बाद, खेल का मैदान बहाल हो जाता है।

श्रोता का उपयोग कई खोज परिचालनों को एक श्रृंखला में संयोजित करने के लिए किया जाता है, जिससे खेल के मैदान में दो (या अधिक) टेट्रिमिनोज को जोड़ने के सभी संभावित तरीकों को खोजना संभव हो जाता है। श्रृंखला में पहला खोज इंजन केवल एक बार बीएफएस निष्पादित करता है। हालाँकि, दूसरा खोज इंजन हर बार BFS को निष्पादित करता है जब पहली खोज एक बंद अवस्था का पता लगाती है। और इसी तरह, यदि श्रृंखला में अन्य खोज इंजन हैं।

अंतिम खोज इंजन का श्रोता बदले हुए खेल क्षेत्र का मूल्यांकन करता है। जब वह खेल के मैदान को पहले की जांच से बेहतर पाता है, तो वह बंद अवस्था के उपयोग किए गए ऑब्जेक्ट को लिखता है, जो इस समय श्रृंखला में पहले खोज इंजन का उपयोग करता है। चूंकि पहला खोज इंजन बीएफएस को केवल एक बार निष्पादित करता है, इसके राज्य की वस्तुओं के predecessor क्षेत्र पूरी खोज प्रक्रिया के पूरा होने तक मान्य रहते हैं। यही है, अंतिम श्रोता अनिवार्य रूप से उस पथ को रिकॉर्ड करता है जिसके साथ पहली टेट्रीमिनो को खेल मैदान के सर्वश्रेष्ठ कॉन्फ़िगरेशन पर पहुंचने के लिए जाना चाहिए।

मूल्यांकन समारोह

स्कोरिंग फ़ंक्शन बदले हुए खेल के मैदान में एक मूल्य प्रदान करता है - विभिन्न प्रभावित मापदंडों का एक भारित योग। इस मामले में प्रयुक्त मूल्यांकन समारोह इस्लाम अल-असी द्वारा विकसित समारोह पर आधारित है। यह निम्नलिखित मापदंडों का उपयोग करता है:

• पंक्तियों की कुल संख्या को मंजूरी दी : यह कुल पंक्तियों की संख्या है जो दो टेट्रिमिनोस के अतिरिक्त द्वारा साफ हो जाएगी।
• कुल अवरुद्ध ऊंचाई : अवरुद्ध ऊंचाई खेल के मैदान के फर्श से ऊपर की ऊंचाई है जिस पर आंकड़ा बंद है। यह ऊर्ध्वाधर दूरी है जो एक बंद आंकड़ा गिर जाता है यदि आप खेल के मैदान के अन्य सभी कब्जे वाले वर्गों को हटा देते हैं और आंकड़े का उन्मुखीकरण रखते हैं। कुल अवरुद्ध ऊंचाई दो tetriminos की अवरुद्ध ऊंचाइयों का योग है।
• "अच्छी तरह से" कोशिकाओं की कुल संख्या : एक अच्छी तरह से सेल एक खाली सेल है जो एक कॉलम में सभी कब्जे वाली कोशिकाओं के ऊपर स्थित है ताकि उसके बाएं और दाएं पड़ोसी कब्जे वाली कोशिकाएं हों; कुओं का निर्धारण करते समय, खेल मैदान की दीवारों को कब्जे वाली कोशिकाएँ माना जाता है। विचार यह है कि एक कुआं एक संरचना है जो शीर्ष पर खुला है, नीचे से बंद है और दोनों तरफ की दीवारों से घिरा हुआ है। कुएं की दीवारों में आंतरायिक अंतराल की संभावना का मतलब है कि एक स्तंभ के भीतर लगातार ढेर में अच्छी तरह से कोशिकाएं जरूरी नहीं होती हैं।
• स्तंभों में छेदों की कुल संख्या : कॉलम में छेद एक खाली सेल है जो कब्जे वाले सेल के ठीक नीचे स्थित है। खेल के मैदान के लिंग की तुलना इसके ऊपर की कोशिका से नहीं की जाती है। खाली कॉलम में कोई छेद नहीं हैं।
• स्तंभों में संक्रमण की कुल संख्या : स्तंभों में एक संक्रमण एक एकल स्तंभ के भीतर एक व्यस्त सेल (या इसके विपरीत) से सटे एक खाली सेल है। सबसे ऊपर के कब्जे वाले स्तंभ ब्लॉक के ऊपर खाली जगह के संयोजन को संक्रमण नहीं माना जाता है। इसी तरह, खेल के मैदान के फर्श की तुलना इसके ऊपर की कोशिका से भी नहीं की जाती है। इसलिए, पूरी तरह से खाली कॉलम में कोई संक्रमण नहीं हैं।
• पंक्तियों में संक्रमण की कुल संख्या : पंक्तियों में एक संक्रमण उसी पंक्ति के भीतर एक व्यस्त सेल (या इसके विपरीत) से सटे एक खाली सेल है। खेल मैदान की दीवारों के पास खाली कोशिकाओं को संक्रमण माना जाता है। कुल राशि की गणना खेल मैदान की सभी लाइनों के लिए की जाती है। हालांकि, संक्रमणों की कुल संख्या में पूरी तरह से खाली लाइनों को ध्यान में नहीं रखा गया है।

El-Ashi ने सुझाव दिया कि उपयोगी भार कण swarm अनुकूलन (PSO) एल्गोरिथ्म का उपयोग करके पाया जा सकता है, जो प्रकृति में देखे गए झुंड व्यवहार की नकल करके समाधान के सेट को बेहतर बनाता है। हमारे मामले में, प्रत्येक समाधान एक वेट वेक्टर है, और विकल्प की फिटनेस टेट्रिस में खेल द्वारा निर्धारित की जाती है; यह टेट्रिमिनोस की कुल संख्या है जिसके दौरान वह खेल के अंत तक जीवित रहा।

इन विचारों को नीचे वर्णित जावा संस्करण में लागू किया जाता है; यह FCEUX के बाहर चलता है और इसे बहुत अधिक गति से चलने वाले गैर-ग्राफिक, इन-मेमोरी गेम के लिए कॉन्फ़िगर किया जा सकता है। पीएसओ तैयार करने के बाद, मुझे यह देखकर आश्चर्य हुआ कि प्रारंभिक पुनरावृत्ति के बाद एल्गोरिथ्म आगे नहीं बढ़ता है। इस पुनरावृत्ति के बाद, कई बेतरतीब ढंग से उत्पन्न समाधान वेरिएंट पहले से ही काफी अच्छी तरह से खेले। कई दिनों तक, इस सेट का आकार तब तक कम हो गया जब तक कि केवल एक विकल्प नहीं रहा। यहाँ इस समाधान के लिए मान हैं:

पैरामीटर	भार
पंक्तियों की कुल संख्या साफ हो गई	1.000000000000000
कुल अवरुद्ध ऊंचाई	12.885008263218383
अच्छी तरह से कोशिकाओं की कुल संख्या	15.842707182438396
स्तंभों में छेदों की कुल संख्या	26.894496507795950
स्तंभों में संक्रमण की कुल संख्या	27.616914062397015
कुल लाइन कूदता है	30.185110719279040

खेल के मैदान को उनके संबंधित वजन से मापदंडों को गुणा करके और परिणामों को जोड़कर अनुमान लगाया गया था। जितना कम मूल्य, उतना बेहतर समाधान। चूंकि सभी मापदंडों और भारों में सकारात्मक मूल्य हैं, सभी पैरामीटर समग्र मूल्यांकन को नुकसान पहुंचाते हैं; उनमें से प्रत्येक को कम से कम किया जाना चाहिए। इसका मतलब यह भी है कि सर्वश्रेष्ठ स्कोर 0 है।

चूंकि इन भारों को यादृच्छिक रूप से चुना गया था, इसलिए उपयुक्त मानों की सीमा बहुत विस्तृत हो सकती है। यह विशेष रूप से संख्याओं का सेट और प्रत्येक पैरामीटर का अनुमानित सापेक्ष महत्व प्रासंगिक नहीं हो सकता है। फिर भी, उन्हें करीब से देखना दिलचस्प होगा।

कम से कम हानिकारक पैरामीटर कुल पंक्तियों की संख्या है। तथ्य यह है कि यह विकल्प हानिकारक है, प्रतिसंतुलित है। लेकिन एआई का मुख्य लक्ष्य अस्तित्व है। वह अधिकांश बिंदुओं के लिए प्रयास नहीं करता है। इसके बजाय, वह रूढ़िवादी रूप से खेलता है, आमतौर पर एक बार में रैंकों को साफ करता है। डबल, ट्रिपल या टेट्रिस प्राप्त करने के लिए, आपको एक गुच्छा विकसित करना होगा जो दीर्घकालिक लक्ष्य के खिलाफ जाता है।

सूची में अगला कुल अवरुद्ध ऊंचाई है। जितना संभव हो मंजिल के करीब टेट्रीमिनो को कम करके इसे कम किया जा सकता है। यह एक सरल रणनीति है जो लंबे समय तक जीवित रहने में योगदान देती है, और टुकड़ों की गुणवत्ता पैकेजिंग के लिए कम समय में।

अच्छी तरह से कोशिकाओं की कुल संख्या को सौंपा गया वजन थोड़ा आश्चर्यचकित करता है, क्योंकि अनुभवी खिलाड़ी आमतौर पर एक पंक्ति में कई टेट्रिस (चार-पंक्ति संयोजन) इकट्ठा करने के लिए जानबूझकर गहरे कुओं का निर्माण करते हैं। लेकिन जैसा कि ऊपर उल्लेख किया गया है, यह एक जोखिम भरा खेल है, मुख्य लक्ष्य के विपरीत - अस्तित्व। इसके अलावा, कुओं की संख्या ढेर के "खुरदरापन" का एक संकेतक है। कुछ आंकड़ों या आंकड़ों के संयोजन को रखने पर एक निश्चित स्तर की असमानता फायदेमंद होती है। लेकिन उच्च खुरदरापन तंग पैकेजिंग को नुकसान पहुंचाता है।

स्तंभों में छेदों की कुल संख्या स्तंभों की कुल संख्या का लगभग आधा है। इन मापदंडों को एक आम संबंधित पैरामीटर में जोड़ा जा सकता है और ढह दिया जा सकता है, जिससे अधिक व्यापक और सबसे हानिकारक पैरामीटर प्राप्त होता है: संक्रमण की कुल संख्या।

सघन रूप से भरे क्षेत्रों में सभी दिशाओं में बहुत कम संख्या में संक्रमण होते हैं। इसलिए, कृत्रिम बुद्धि द्वारा संचालित मुख्य रणनीति, संक्षेप में निम्नानुसार वर्णित की जा सकती है: टुकड़ों को एक-दूसरे के जितना संभव हो उतना पैक करें।

अन्य विकल्प

यहाँ एआई के विकास के दौरान प्रयोग किए गए कुछ और मापदंडों की एक सूची दी गई है:

• ढेर की ऊँचाई : व्यस्त ब्लॉक खाली कोशिकाओं पर लटक सकते हैं, जिससे फलाव और छेद बन सकते हैं; हालाँकि, पूरी तरह से खाली लाइनों पर कब्जे वाले ब्लॉक को लॉक करना संभव नहीं है। इसलिए, हीप ऊंचाई पंक्तियों की संख्या है जिसमें कम से कम एक व्यस्त ब्लॉक होता है।
• कब्जे वाले स्तंभों की कुल संख्या : यह उन स्तंभों की संख्या है जिनमें कम से कम एक कब्जे वाला सेल होता है।
• कब्जे वाली कोशिकाओं की कुल संख्या : खेल के मैदान पर कब्जे वाली कोशिकाओं की संख्या।
• जुड़े हुए क्षेत्रों की कुल संख्या : लगातार जुड़े क्षेत्रों की संख्या की गणना करने के लिए यहां फिल एल्गोरिथ्म का उपयोग किया जाता है। कब्जे में "द्वीप" खोजने के अलावा, वह दोनों कुल्हाड़ियों के साथ छेद करने वाले छेदों का पता लगाता है।
• कॉलम ऊंचाई फैलाव : यह स्तंभ ऊंचाइयों में भिन्नता का एक सांख्यिकीय उपाय है। यह सतह खुरदरापन का सूचक है।
• कुल अनुकूलन मूल्य : अगले अज्ञात आंकड़े के लिए ढेर के अनुकूलन मूल्य की गणना करता है। यह उन तरीकों की कुल संख्या को गिनाता है जिसमें 7 प्रकार के आकार नए छेदों की उपस्थिति के बिना खेल मैदान में जोड़े जा सकते हैं। सटीक गिनती के लिए, बार-बार बीएफएस के उपयोग की आवश्यकता होगी। लेकिन अनुमानित गणना के लिए, खोज पेड़ को बहुत छोटा किया जा सकता है।
• अगले आंकड़े के लिए औसत रेटिंग : यह पैरामीटर अगले अज्ञात आंकड़े के लिए सभी संभावनाओं का विश्लेषण करके खोज को गहरा करता है। यह प्रत्येक प्रकार के आंकड़े के स्थान को अलग करने के लिए अन्य मापदंडों का उपयोग करता है, और फिर 7 रेटिंग के लिए औसत लौटाता है। आकृति के प्रत्येक प्लेसमेंट के लिए, बीएफएस की आवश्यकता होती है।
• एवरेज्ड सिम्युलेटेड गेम : पैरामीटर टेट्रिस में गेम की एक श्रृंखला का अनुकरण करता है, अपने स्वयं के छद्म यादृच्छिक संख्या जनरेटर का उपयोग करके टुकड़ों का चयन करता है और उनके साथ काम करने के लिए एआई का उपयोग करता है। प्रत्येक खेल के अंत में, खेल के क्षेत्र का मूल्यांकन अन्य मापदंडों का उपयोग करके किया जाता है। सभी बैचों का औसत मान लौटाया जाता है।

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

एक अन्य उपयोगी कारक ऑफसेट मूल्य है। उदाहरण के लिए, एक ढेर की पूरी तरह से सपाट सतह में 0. की स्तंभ ऊंचाइयों का फैलाव होता है, लेकिन एक पूरी तरह से सपाट सतह एस और जेड के साथ-साथ आकार के अन्य संयोजनों के अनुकूल नहीं होती है। इसलिए, स्थिरांक को घटाकर, विचरण को अधिकतम खुरदरेपन के आसपास केंद्रित किया जाना चाहिए।

समायोजित और पक्षपाती मापदंडों को कुछ हद तक उठाया जा सकता है ताकि भारित राशि की गणना करने से पहले वे लॉगरिदमिक या घातीय रूप से स्केल कर सकें। इन सभी संभावनाओं को अतिरिक्त भार के रूप में माना जा सकता है जो संभवतः PSO जैसी विधियों द्वारा अनुकूलित किया जा सकता है।

मापदंडों में से कई इस बात की समझ देते हैं कि ढेर अतिरिक्त टुकड़ों को कितनी अच्छी तरह से संभाल सकते हैं, उदाहरण के लिए, जो सतह की खुरदरापन से निपटते हैं, लेकिन "अनुकूलन की कुल राशि", "अगले आंकड़े की औसत रेटिंग" और "औसत सिम्युलेटेड गेम" जो बदले हुए खेल के क्षेत्र का मूल्यांकन करते हैं। उन आंकड़ों को सम्मिलित करना जो दो ज्ञात में शामिल नहीं हैं। बाद के आंकड़ों के अध्ययन में, श्रृंखला के तेजी से उन्मूलन के कारण, प्राप्त अतिरिक्त ज्ञान की मात्रा गहराई के साथ घट जाती है। इसका मतलब है कि पार्टी का लंबा अतीत पाठ्यक्रम इतना महत्वपूर्ण नहीं है, और दूर के भविष्य में पार्टी का पाठ्यक्रम भी बहुत महत्वपूर्ण नहीं है। वास्तव में, यदि आंकड़ों का एक छोटा क्रम बेतरतीब ढंग से गलत तरीके से सेट किया गया है, तो एआई प्रभावित पंक्तियों को साफ करने के लिए निम्नलिखित कुछ आंकड़ों का उपयोग करके, गेम को जल्दी से पुनर्स्थापित करता है। बाद के आंकड़ों के विश्लेषण के लिए इष्टतम मूल्य का निर्धारण करने के लिए और अधिक शोध की आवश्यकता है।

एक पैरामीटर की उपयोगिता का दूसरा पहलू कम्प्यूटेशनल लागत है। लागत में बहुत वृद्धि हुई है क्योंकि मूल्यांकन फ़ंक्शन को दो आंकड़ों के प्रत्येक संभावित प्लेसमेंट के लिए कहा जाता है। चूंकि एआई को वास्तविक समय में टेट्रिस खेलने में सक्षम होना चाहिए, बहुमूल्य जानकारी प्रदान करने वाले लागत कारकों का तेजी से चलने वाली अधिक अनुमानित तकनीकों के लिए आदान-प्रदान किया जा सकता है।

एआई प्रशिक्षण

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


चूंकि कई बैचों के पूरा होने से पहले एआई संस्करण को चलाने के लिए दिन लगते हैं और औसत की गणना करते हैं, इसलिए पीएसओ नियंत्रण मीट्रिक के रूप में औसत बैच अवधि का उपयोग करना पूरी तरह से अव्यावहारिक है। इसके बजाय, आप एस और जेड की आवृत्ति को बढ़ाकर नियंत्रित गति के साथ खेल की जटिलता को बढ़ा सकते हैं, जो समय के साथ केवल इस जोड़ी के आंकड़ों के वैकल्पिक निर्माण की ओर ले जाएगा।

मैंने इस शिक्षण पद्धति का उपयोग करने की कोशिश की, लेकिन पाया कि एस और जेड के साथ काम करने के लिए एआई को पढ़ाना वास्तव में समान रूप से वितरित यादृच्छिक आकृतियों के साथ सामना करने की क्षमता को परेशान करता है।

बी-टाइप गेम से प्रेरित एक वैकल्पिक विधि में, पीएसओ मीट्रिक पंक्ति सफाई की आवृत्ति को नियंत्रित करता है। खेल का मैदान यादृच्छिक कचरा ब्लॉकों का 10-रेखा आरेख है, और हर बार लाइन को साफ करने के बाद, ढेर की ऊंचाई को बहाल करते हुए, एक नई कचरा रेखा नीचे दिखाई देती है। चूंकि खेल के मैदान में 10 स्तंभों की चौड़ाई होती है, और प्रत्येक टेट्रीमिनो में 4 वर्ग होते हैं, औसतन, एआई को प्रत्येक 2.5 टेट्रीमिनो की एक पंक्ति को साफ करना चाहिए। और कचरे से छुटकारा पाने के लिए, उसे इसे और भी तेजी से करना होगा।

दुर्भाग्य से, इस तकनीक ने भी प्रदर्शन में सुधार नहीं किया। एक संभावित कारण यह है कि यादृच्छिक कचरा छेद वास्तव में उन तारों से मेल नहीं खाते हैं जो एआई वास्तविक खेल से संबंधित हैं। इसके अलावा, पंक्ति को साफ करना एक अल्पकालिक लक्ष्य है; लालची पंक्ति सफाई जरूरी नहीं कि लंबे समय तक जीवित रहे। समय-समय पर, बाद के आंकड़ों के कुछ संयोजनों को संसाधित करने के लिए पंक्तियों को नहीं छुआ जाना चाहिए।

कॉलिन फी ने अपने वेब पेज पर एक अलग दृष्टिकोण का सुझाव दिया। उन्होंने हिस्टोग्राम बनाए जो आकार के प्रतिशत को दर्शाते हैं जो प्रत्येक पंक्ति में परीक्षण के दौरान अवरुद्ध होते हैं। दिलचस्प है, सभी हिस्टोग्राम लगभग बनाए गए आंकड़ों की संख्या की परवाह किए बिना समान दिखते हैं। इसके आधार पर, उन्होंने सुझाव दिया कि आप किसी भी परीक्षण बैच के लिए फ़ंक्शन की अनुमानित छवि का उपयोग कर सकते हैं, जब निर्माण लाइन में किसी आंकड़े को अवरुद्ध करने की सांख्यिकीय अपेक्षा का मूल्यांकन किया जाता है, इस प्रकार वह समय प्राप्त होता है जिसके दौरान AI खेल के अंत तक खेलेंगे। मैंने इस संभावना का पता लगाने का फैसला किया।

नीचे कुल 2,039,900,000 टेट्रिमिनो युक्त परीक्षण बैचों का एक हीट मैप है। प्रत्येक कोशिका उस में बंद आकृतियों के प्रतिशत के आधार पर रंगीन होती है। दृश्य विपरीत को बढ़ाने के लिए, एक गैर-रेखीय पैलेट का चयन किया जाता है। कोशिकाओं के अधिकतम प्रतिशत को विभाजित करके सेल मानों को सामान्य करके मानचित्र बनाया गया था, और फिर 0.19 की शक्ति की घोषणा की (देखें "गामा सुधार" )।

रंग का प्रतिशत ■ 0.00000000 ■ 0.00000315 ■ 0.00024227 ■ 0.00307038 ■ 0.01860818 ■ 0.07527774 ■ 0.23582574 ■ 0.61928352 ■ 1.42923040 ■ 2.98867416 ■ 5.78182519

17 और 18 की पंक्तियों में गहरे नारंगी और लाल धारियों का मतलब है कि विशाल बहुमत के आंकड़े वहाँ समाप्त होते हैं। नीचे से हल्का हरा रंग आंकड़ों की ज्यामिति का एक परिणाम है: टेट्रीमिनो के 7 प्रकारों में से केवल 4 नीचे की रेखा पर दिखाई दे सकते हैं। निचले कोने काले होते हैं क्योंकि वहां जाना असंभव है।

प्रत्येक पंक्ति के साथ रंग लगभग समान है, और यह बताता है कि आकृतियों को समान रूप से समान रूप से वितरित किया गया है। विभिन्न प्रकार की आकृतियों के हिस्टोग्राम को देखकर थोड़ा अंतराल समझाया जा सकता है:

टी

जम्मू

जेड

हे

एस

एल

मैं

टी सबसे सार्वभौमिक प्रकार निकलता है: इसका हिस्टोग्राम अन्य सभी की तुलना में अधिक समान है। हिस्टोग्राम जे में विसंगतियाँ - दीवारों के प्रभाव का परिणाम; केवल Jr और Jl साइड कॉलम में हो सकते हैं, जो क्षतिपूर्ति करने के लिए AI का उपयोग कॉलम 1 और 9 को अधिक बार करता है। यही बात L पर लागू होती है। Histograms Z और S लगभग समान दिखते हैं, जो इस तथ्य के कारण असंतुलन पर जोर देते हैं कि Zv और Sv एक दूसरे के आदर्श दर्पण चित्र नहीं हैं। टाइप ओ 19 × 9 के खेल के मैदान तक सीमित है, और ऐसा लग रहा है कि एआई केंद्र की तुलना में पक्षों पर ओ का उपयोग करने की अधिक संभावना है। Tetrimino I को दाईं ओर स्थानांतरित कर दिया गया है, क्योंकि इसका प्रारंभिक बिंदु वहां स्थित है; इसलिए, स्तंभ 1 में ताला लगाना दुर्लभ है।

तालिका उन आंकड़ों का प्रतिशत दिखाती है जो प्रत्येक पंक्ति में अवरुद्ध हैं।

पंक्ति	का प्रतिशत
0	.००००००००००
1	.००००००००००
2	.००००००४९०२
3	.०००००२६४७२
4	.०००००६६१८०
5	.००००१७२५५७
6	0.००००५१२२८०
7	.०००१७५९४००
8	.०००६६८१२१०
9	.००२३१८७९०१
10	.००७७९२८८२०
11	.०२५९६७२०४३
12	.०८६६१८७०६८
13	.२९०१३१५७५१
14	.९७७१६६३८०७
15	३.३०००४०८३५३
16	१०.६९८९०५९२६८
17	२८.५६८७९७६३७१
18	५०.०३३५७०६१६२
19	६.००७७६७१४५४

यहाँ मूल्यों का एक ग्राफ है:


यदि लाइन 19 को ध्यान में नहीं रखा गया है, तो ग्राफ घातीय वृद्धि दर्शाता है।

निम्नलिखित आसन्न पंक्तियों में बंद आकृतियों की संख्या के अनुपात की एक सूची है।

स्ट्रिंग ए / स्ट्रिंग बी	अनुपात (%)
1/2	0.00
2/3	18.52
3/4	40.00
4/5	38.35
5/6	33.68
6/7	29.12
7/8	26.33
8/9	28.81
9/10	29.76
10/11	30.01
11/12	29.98
12/13	29.85
13/14	29.69
14/15	29.61
15/16	30.84
16/17	37.45
17/18	57.10
18/19	832.81

लाइनें 16–19खेल के मैदान के फर्श के साथ बातचीत करने वाले आंकड़ों को ध्यान में रखती हैं, इसलिए उन्हें त्याग दिया जा सकता है। पंक्तियों में, 0–5चयन सार्थक होने के लिए बहुत छोटा है। शेष अनुपात, जोड़े ६ / r-१४ / १५, लगभग समान हैं; उनका औसत मूल्य 29.24% है। इसका मतलब यह है कि ढेर के बढ़ने की संभावना लगभग एक ही है। यह तर्कसंगत है, क्योंकि टेट्रिस नियम ढेर के शीर्ष पर बातचीत को सीमित करता है जब इसे कसकर पैक किया जाता है।

निम्नलिखित ग्राफ 6–15 की रेखाओं में ₁₀ प्रतिशत के आंकड़ों का लॉग दिखाता है ।


यह 1 के करीब निर्धारण के गुणांक के साथ एक पूरी तरह से सीधी रेखा के करीब है । ऊपर दिखाए गए रेखीय प्रतिगमन से प्राप्त सूत्र हमें Y अक्ष के साथ प्रतिच्छेदन देता है, यह मानते हुए कि पंक्ति 0 में आकृतियों का प्रतिशत लगभग 10 ^.7.459 % है। इस मूल्य का विलोम हमें खेल के अंत तक 2,877,688,349 टेट्रीमिनो या 1,151,175,340 पंक्तियों की एक सांख्यिकीय उम्मीद देता है।

यह हमें समझाता है कि लॉग ₁₀प्रत्येक पंक्ति में आंकड़ों का प्रतिशत पंक्ति, तक रैखिक रहता है। हालांकि, जब ढेर लगभग खेल के मैदान की छत तक पहुंच जाता है, तो आंदोलन की स्वतंत्रता इस हद तक सीमित होती है कि इस संपत्ति का उल्लंघन होता है। इसके अलावा, लाइन 0 पर एक टुकड़ा अवरुद्ध करना जरूरी नहीं कि गेम खत्म हो जाए; यदि नए आंकड़े बनाने के लिए कोई जगह है तो भी आपको बचाया जा सकता है।

एआई की ताकत का आकलन करने का दूसरा तरीका खेल मैदान की पूरी सफाई के बीच बनाई गई आकृतियों की औसत संख्या को मापना है। पूरी सफाई सिर्फ 5 टेट्रिमिनोस के साथ प्राप्त की जा सकती है। उदाहरण के लिए, अन्य संभावनाओं के बीच, यह खेल मैदान के फर्श पर बिछाई गई पांच हे आकृतियों द्वारा प्राप्त किया जा सकता है। सामान्य तौर पर, चूंकि प्रत्येक टेट्रीमिनो में 4 वर्ग होते हैं और खेल मैदान की चौड़ाई 10 वर्ग होती है, पूर्ण सफाई के लिए बनाए गए आंकड़ों की संख्या 5 से अधिक होनी चाहिए। क्योंकि4 × 5 एन = 2 × 10 एन )।

मेरे एआई में 1,181 के पूरे क्षेत्र की सफाई के बीच औसत आकार का एक आकार है - एक काफी छोटी संख्या। चूंकि एक पूर्ण सफाई एक खेल को फिर से शुरू करने की तरह है, एक पूर्ण बैच को खेल पुनरारंभ की एक अत्यंत लंबी श्रृंखला के रूप में देखा जा सकता है, इसके बाद गेम को त्वरित अग्रिम किया जा सकता है। ऊपर वर्णित विकल्पों के अनुक्रम की तरह SZ, खेल के अंत तक जाने वाले पैथोलॉजिकल सीक्वेंस आमतौर पर बहुत कम होते हैं।

नीचे दिए गए हिस्टोग्राम संभावना (प्रतिशत में) को दर्शाता है कि एआई निर्दिष्ट आंकड़ों की संख्या के बाद क्षेत्र की पूरी समाशोधन प्राप्त करेगा।


उपरोक्त सूत्र में डिग्री क्रम में कमी की दर निर्धारित करता है और, संभवतः, एआई की ताकत। इस सूत्र के अनुसार, खाली खेल मैदान के साथ शुरू होने वाले 253 खेलों में से लगभग 0.4% या केवल 1 टेट्रिमिनोस के बाद एक पूर्ण सफाई के साथ समाप्त होता है।

फेय ने जो सुझाव दिया उसके विपरीत, रैखिक और घातीय सन्निकटन में स्थिरांक को बहुत बड़े नमूने के आकार की आवश्यकता होती है ताकि R ²1 से संपर्क किया, इसलिए यह पद्धति PSO के लिए लागू नहीं है। हालांकि, लंबे बैचों के साथ प्राप्त स्थिरांक का उपयोग सन्निकटन फ़ंक्शन को अनुकूलित करने के लिए किया जा सकता है जो छोटे बैचों के लिए निरंतर निरंतर मान बनाता है। एक प्रकार के विकास प्रतिक्रिया पाश में, अनुकूलित सन्निकटन फ़ंक्शन का उपयोग PSO में किया जा सकता है, जो AI को बेहतर बनाता है, जो बदले में नए स्थिरांक की गणना करने के लिए इस्तेमाल किया जा सकता है, जो सन्निकटन फ़ंक्शन के लिए संदर्भ मानदंड के रूप में कार्य करता है।

जावा संस्करण

कार्यक्रम के बारे में

लुआ से अपरिचित डेवलपर्स के लिए, मैंने स्रोत ज़िप फ़ाइल में जावा एआई पोर्ट जोड़ा । क्लोजर के आधार पर लुआ ऑब्जेक्ट्स की लगभग लाइन-बाय-लाइन अनुवाद कक्षाएं हैं ।

संकुल

कोड दो पैकेजों में विभाजित है:

• tetris.ai एआई कक्षाएं और इंटरफेस शामिल हैं।
• tetris.gui खेल के मैदान का एक ग्राफिक मॉडल बनाता है।

एआई कक्षाएं और इंटरफेस

उपयुक्त नाम के साथ एक वर्ग Tetriminosटेट्रीमिनो का वर्णन करता है। यह समान रूप से उपयोग किया जाता है enumऔर टेट्रीमिनो के सभी प्रकारों के लिए स्थिरांक होता है:

 public static final int NONE = -1; public static final int T = 0; public static final int J = 1; public static final int Z = 2; public static final int O = 3; public static final int S = 4; public static final int L = 5; public static final int I = 6; 

NONEमतलब बिना मूल्य वाला। इसका उपयोग खेल के मैदान की खाली कोशिकाओं के लिए किया जाता है। इसमें ओरिएंटेशन टेबल के दो मॉडल

भी Tetriminosशामिल हैं। PATTERNS- यह एक 4-आयामी पूर्णांक सरणी है (प्रकार × रोटेशन × वर्ग × निर्देशांक) जिसमें वर्गों के सापेक्ष निर्देशांक हैं; लाइनों को व्यवस्थित किया जाता है ताकि प्रत्येक प्रकार में आकार निर्माण अभिविन्यास पहले हो। ORIENTATIONSएक और मॉडल, वस्तुओं का एक 2-आयामी सरणी (टाइप × रोटेशन) है Orientation। प्रत्येक Orientationमें वस्तुओं की एक सरणी के रूप में वर्ग के निर्देशांक होते हैं Point। इसमें ऐसे फ़ील्ड भी हैं जो संबंधित अभिविन्यास के लिए अनुमत पदों की श्रेणी का वर्णन करते हैं।

 public class Orientation { public Point[] squares = new Point[4]; public int minX; public int maxX; public int maxY; ... } 

 public class Point { public int x; public int y; ... } 

टेट्रीमिनो रोटेशन (दोनों ओरिएंटेशन टेबल में दूसरा इंडेक्स) उन वस्तुओं में उपयोग किया जाता है Stateजो बीएफएस में हेरफेर करते हैं।

 public class State { public int x; public int y; public int rotation; public int visited; public State predecessor; public State next; ... } 

x, yऔर rotationएक साथ आंकड़े की स्थिति और अभिविन्यास का वर्णन करते हैं। चूंकि Tetrimino प्रकार निर्माण के क्षण से लेकर अवरुद्ध होने तक स्थिर रहता है, इसलिए इसके लिए एक क्षेत्र वैकल्पिक है।

जिस वर्ग Searcherमें BFS एल्गोरिथ्म होता है वह Stateनिर्मित होने पर सभी संभावित वस्तुओं का एक पूरा सेट बनाता है :

 private void createStates() { states = new State[AI.PLAYFIELD_HEIGHT][AI.PLAYFIELD_WIDTH][4]; for(int y = 0; y < AI.PLAYFIELD_HEIGHT; y++) { for(int x = 0; x < AI.PLAYFIELD_WIDTH; x++) { for(int rotation = 0; rotation < 4; rotation++) { states[y][x][rotation] = new State(x, y, rotation); } } } } 

यद्यपि जावा में एक समृद्ध संग्रह एपीआई है, लेकिन Searcherइसमें कतार का अपना कार्यान्वयन शामिल है। वर्ग वस्तुओं को एक लिंक्ड सूची में शामिल करने के लिए Queueउपयोग करता State.nextहै State। चूंकि सभी वस्तुओं Stateको पूर्वनिर्धारित किया जाता है, और प्रत्येक Stateको कतार में एक बार से अधिक नहीं जोड़ा जा सकता है, कतार जगह में काम कर सकती है, जो सामान्य कतार कार्यान्वयन में उपयोग किए जाने वाले अनावश्यक अस्थायी कंटेनर ऑब्जेक्ट्स की आवश्यकता को समाप्त करती है।

बीएफएस का "दिल" नीचे दिखाया गया तरीका है search।

 public boolean search(int[][] playfield, int tetriminoType, int id) { int maxRotation = Tetriminos.ORIENTATIONS[tetriminoType].length - 1; int mark = globalMark++; if (!addChild(playfield, tetriminoType, mark, null, 5, 0, 0)) { return false; } while(queue.isNotEmpty()) { State state = queue.dequeue(); if (maxRotation != 0) { addChild(playfield, tetriminoType, mark, state, state.x, state.y, state.rotation == 0 ? maxRotation : state.rotation - 1); if (maxRotation != 1) { addChild(playfield, tetriminoType, mark, state, state.x, state.y, state.rotation == maxRotation ? 0 : state.rotation + 1); } } addChild(playfield, tetriminoType, mark, state, state.x - 1, state.y, state.rotation); addChild(playfield, tetriminoType, mark, state, state.x + 1, state.y, state.rotation); if (!addChild(playfield, tetriminoType, mark, state, state.x, state.y + 1, state.rotation)) { lockTetrimino(playfield, tetriminoType, id, state); } } return true; } 

यह निर्मित टेट्रिमिनो की स्थिति के साथ एक कतार को जन्म देता है, और फिर क्रमिक रूप से कतार से हटाए गए राज्यों से बाल तत्वों को निकालता है, जब वे खेल के मैदान पर दिखाई देते हैं तो उन्हें कतार में वापस जोड़ते हैं।

एक searchगेम फ़ील्ड जिसमें व्याप्त और खाली कोशिकाओं का एक संयोजन होता है, निर्मित Tetrimino प्रकार और एक मनमाना पहचानकर्ता विधि को पारित किया जाता है । बीएफएस के निष्पादन के दौरान, एक श्रोता को तब बुलाया जाता है जब भी एक लॉक स्थिति का पता लगाया जाता है।

 public interface ISearchListener { public void handleResult(int[][] playfield, int tetriminoType, int id, State state); } 

श्रोता एक बदला हुआ खेल का मैदान प्राप्त करता है जिसमें एक टेट्रीमिनो होता है जो जगह में बंद होता है। बनाई गई Tetrimino का प्रकार और एक मनमाना पहचानकर्ता भी प्रेषित होता है। अंतिम पैरामीटर वह Stateहै जिसमें टेट्रीमिनो को अवरुद्ध किया जाता है। लिंक की श्रृंखला का पालन करके State.predecessor, आप Stateएक आकृति बनाने के लिए सभी तरह से बहाल कर सकते हैं ।

State.visitedके रूप में लागू किया जा सकता है boolean; हालांकि, इस मामले में, खोज करने से पहले, Stateरीसेट visitedकरने के लिए सभी वस्तुओं के माध्यम से सॉर्ट करना आवश्यक होगा false। इसके बजाय, मैंने एक काउंटर की तुलना में एक visitedमूल्य बनाया int, प्रत्येक कॉल के साथ वेतन वृद्धि।

विधिaddChildपूर्ववर्ती अवस्थाएँ। बाद की स्थिति मैदान के भीतर होनी चाहिए और खेल मैदान के 4 खाली कक्षों पर स्थित होनी चाहिए। इसके अलावा, बाद की स्थिति की परिकल्पना की जानी चाहिए State। स्थिति स्वीकार्य है, तो addChildरिटर्न true, बाद में राज्य जगह में डाल करने के लिए है, क्योंकि यह पहले से ही दौरा किया विफल रहा है, भले ही। यदि कोई आकृति बनाई जा सकती है यह निर्धारित करने के लिए

विधि searchरिटर्न addChildमान का उपयोग करती है । यदि आंकड़ा नहीं बनाया जा सकता है, तो ढेर शीर्ष पर पहुंच गया है और खोज अब नहीं की जा सकती है; इसलिए यह लौट आता है false।

वापसीaddChildएक और कदम नीचे जाने की संभावना के लिए महत्व का भी अध्ययन किया जा रहा है। यदि यह नहीं किया जा सकता है, तो वर्तमान स्थिति लॉक स्थिति है और कॉल शुरू होता है lockTetrimino। विधि lockTetriminoखेल के मैदान को बदल देती है, श्रोता को कॉल करती है, और फिर खेल मैदान को पुनर्स्थापित करता है।

सरणी की प्रत्येक पंक्ति playfieldमें 1 अतिरिक्त तत्व होता है, जो पंक्ति में व्याप्त कोशिकाओं की संख्या को संग्रहीत करता है। एक तत्व में वृद्धि विधि द्वारा किया जाता है lockTetriminoक्योंकि यह कोशिकाओं को व्यस्त के रूप में चिह्नित करता है।

जब श्रोता संशोधित खेल का मैदान प्राप्त करता है, तो वह कॉल करता हैPlayfieldUtil.clearRowsभरी हुई पंक्तियों को हटाने के लिए विधि सरणी के अतिरिक्त तत्व में मूल्य की जांच करके उन्हें पहचानती है। एक स्ट्रिंग को हटाने के लिए, कोड इस तथ्य का लाभ उठाता है कि जावा में, दो-आयामी सरणियों को अनिवार्य रूप से सरणियों का उपयोग किया जाता है; यह सिर्फ तार के लिंक को नीचे धकेलता है। PlayfieldUtilइसमें मुफ्त लाइनें शामिल हैं; वह उनमें से एक का लिंक डालकर सफाई की प्रक्रिया पूरी करता है। शिफ्ट करने से पहले, साफ़ की जाने वाली पंक्ति का सूचकांक एक अतिरिक्त पंक्ति तत्व में जमा हो जाता है। फिर लाइन का लिंक स्टैक पर धकेल दिया जाता है।

तब श्रोता पुकारता हैPlayfieldUtil.restoreRowsखेल के मैदान में किए गए परिवर्तनों को त्यागना। कदम रिवर्स ऑर्डर में रद्द कर दिए गए हैं। पहले हमें ऊपर से एक मुफ्त पंक्ति मिलती है। फिर, भरी हुई पंक्ति को स्टैक से पुनर्प्राप्त किया जाता है और अतिरिक्त तत्व से सूचकांक बहाल किया जाता है। इसका उपयोग लाइन संदर्भों को स्थानांतरित करने और हटाए गए रेखा के स्थान पर लौटने के लिए किया जाता है। अंत में, एक अतिरिक्त तत्व को बहाल किया जाता है, इसे खेल मैदान की चौड़ाई का मान सौंपा जाता है - भरी हुई पंक्ति में कब्जे वाली कोशिकाओं की संख्या।

के रूप में PlayfieldUtilअच्छी तरह से वहाँ एक तरीका है evaluatePlayfieldकि गणना करता है और राईट 4 मूल्यांकन पैरामीटर कंटेनर वर्ग नीचे दिखाया गया है।

 public class PlayfieldEvaluation { public int holes; public int columnTransitions; public int rowTransitions; public int wells; } 

वर्ग यह सब प्रबंधित करता है AI। इसमें Searcherनीचे दिखाए गए श्रोता द्वारा एक साथ दो ऑब्जेक्ट जुड़े हुए हैं।

 public void handleResult( int[][] playfield, int tetriminoType, int id, State state) { if (id == 0) { result0 = state; } Orientation orientation = Tetriminos.ORIENTATIONS[tetriminoType][state.rotation]; int rows = playfieldUtil.clearRows(playfield, state.y); int originalTotalRows = totalRows; int originalTotalDropHeight = totalDropHeight; totalRows += rows; totalDropHeight += orientation.maxY - state.y; int nextID = id + 1; if (nextID == tetriminoIndices.length) { playfieldUtil.evaluatePlayfield(playfield, e); double fitness = computeFitness(); if (fitness < bestFitness) { bestFitness = fitness; bestResult = result0; } } else { searchers[nextID].search(playfield, tetriminoIndices[nextID], nextID); } totalDropHeight = originalTotalDropHeight; totalRows = originalTotalRows; playfieldUtil.restoreRows(playfield, rows); } 

एक वर्ग AIकिसी भी संख्या में वस्तुओं को संभाल सकता है Searcher, लेकिन निंटेंडो टेट्रिस केवल एक आकार पहले से दिखाता है। वस्तुओं Searcherको एक सरणी में संग्रहीत किया जाता है, और ऊपर दिखाया गया कोड उनके सामान्य श्रोता के रूप में कार्य करता है। विधि को पारित यादृच्छिक पहचानकर्ता Searcher.searchवास्तव में सरणी का सूचकांक है, जो खोज की गहराई भी है। जब श्रोता को बुलाया जाता है, तो पहचानकर्ता कॉल को अगले Searcherश्रृंखला में निर्देशित करता है। यदि वह सरणी के अंत तक पहुँचता है, तो खेल के मैदान का मूल्यांकन करता है। और जब वह एक उच्च फिटनेस स्कोर के साथ खेल का मैदान पाता है, तो वह श्रृंखला में Stateपहले से अवरुद्ध एक को लिखता है Searcher।

AIएक विधि searchहै जिसमें खेल के मैदान और एक सरणी बनाई जाती है जिसमें बनाए गए प्रकार और अगले टेट्रीमिनो होते हैं। वह लौटता हैStateस्थिति और रोटेशन जिसमें पहले टेट्रीमिनो को अवरुद्ध किया जाना चाहिए। वह दूसरे टेट्रिमिनो पर ध्यान केंद्रित नहीं करता है; अगली बार जब इसे बुलाया जाता है, तो यह स्कोर की फिर से गणना करता है। यदि ढेर बहुत अधिक है और श्रृंखला Searcherदोनों टेट्रिमिनोस को रखने में विफल रहती है, तो यह AI.searchवापस आ जाएगी null।

 public State search(int[][] playfield, int[] tetriminoIndices) { this.tetriminoIndices = tetriminoIndices; bestResult = null; bestFitness = Double.MAX_VALUE; searchers[0].search(playfield, tetriminoIndices[0], 0); return bestResult; } 

ऐ चुनौती

चूंकि जावा संस्करण FCEUX से बंधा नहीं है, इसलिए इसे संभवतः अन्य परियोजनाओं के लिए उपयोग किया जा सकता है। जो लोग एआई को कहीं और एकीकृत करने में रुचि रखते हैं, उनके लिए यह खंड आपकी जरूरत की सभी चीजों का वर्णन करता है।

सबसे पहले, सभी प्रकार के टेट्रिमिनो धारण करने के लिए एक उदाहरण AI, उदाहरण PlayfieldUtilऔर सरणी बनाएं। इसके अलावा, कॉल PlayfieldUtil.createPlayfieldकरके खेल मैदान का एक उदाहरण बनाएं ; यह एक अतिरिक्त कॉलम के साथ दो-आयामी सरणी देता है, जिसकी हमने ऊपर जांच की थी। आपको शायद एक यादृच्छिक संख्या जनरेटर की भी आवश्यकता होगी।

 AI ai = new AI(); PlayfieldUtil playfieldUtil = new PlayfieldUtil(); int[] tetriminos = new int[AI.TETRIMINOS_SEARCHED]; int[][] playfield = playfieldUtil.createPlayfield(); Random random = new Random(); 

प्रारंभ में, खेल का मैदान खाली है, और सभी सेल प्रासंगिक हैं Tetriminos.NONE। यदि आप कोशिकाओं को प्रोग्रामेटिक रूप से भरते हैं, तो playfield[rowIndex][AI.PLAYFIELD_WIDTH]प्रत्येक पंक्ति में व्याप्त कोशिकाओं की संख्या लिखना न भूलें ।

प्रारंभ में बनाए गए आकार और अगले आकार के प्रकारों के साथ टेट्रीमिनो प्रकारों की सरणी भरें, जिन्हें आमतौर पर मैन्युअल रूप से चुना जाता है।

 tetriminos[0] = random.nextInt(7); tetriminos[1] = random.nextInt(7); 

फिर हम खेल के मैदान और विधि के प्रकार के सरणी को पास करते हैं AI.search। वह वापस आएगा Stateजिसमें आपको पहले टेट्रीमिनो को ब्लॉक करने की आवश्यकता है। अगर वह लौटता है null, तो खेल खत्म होना अपरिहार्य है।

 State state = ai.search(playfield, tetriminos); 

यदि आपको लॉकिंग के लिए एक आंकड़ा बनाने से एक रास्ता चाहिए, तो इसे Stateविधि को पास करें AI.buildStateList।

 State[] states = ai.buildStatesList(state); 

खेल मैदान को अपडेट करने के लिए, हम इसे PlayfieldUtil.lockTetriminoइसके प्रकार और ऑब्जेक्ट के साथ पास करेंगे State। यह विधि स्वचालित रूप से भरी हुई पंक्तियों को साफ करती है।

 playfieldUtil.lockTetrimino(playfield, tetriminos[0], state); 

दोबारा कॉल करने से पहले, AI.searchआपको बेतरतीब ढंग से अगले टेट्रीमिनो का चयन करना होगा।

 tetriminos[0] = tetriminos[1]; tetriminos[1] = random.nextInt(7); 

एक साथ, यह इस तरह दिखता है:

 AI ai = new AI(); PlayfieldUtil playfieldUtil = new PlayfieldUtil(); int[] tetriminos = new int[AI.TETRIMINOS_SEARCHED]; int[][] playfield = playfieldUtil.createPlayfield(); Random random = new Random(); tetriminos[0] = random.nextInt(7); tetriminos[1] = random.nextInt(7); while(true) { // ... print playfield ... State state = ai.search(playfield, tetriminos); if (state == null) { break; // game over } playfieldUtil.lockTetrimino(playfield, tetriminos[0], state); tetriminos[0] = tetriminos[1]; tetriminos[1] = random.nextInt(7); } 

पाठ के रूप में खेल के मैदान को प्रदर्शित करने के बजाय, आप यह प्रदर्शित करने के लिए अधिक दिलचस्प तरीके का उपयोग कर सकते हैं कि क्या हो रहा है ...

खेल मैदान प्रदर्शन

कक्षा TetrisFrameनिन्टेंडो टेट्रिस ग्राफिक्स की नकल करती है, जिसमें लेख के पिछले भाग में वर्णित व्यवहारिक विशेषताएं शामिल हैं।


इसे कार्रवाई में देखने के लिए, इसे चलाएं tetris.gui.Main। Lua संस्करण के साथ के रूप में, हम फ़ाइल की शुरुआत में निरंतर मूल्य को बदलकर खेल की गति को समायोजित कर सकते हैं।

 public static final boolean PLAY_FAST = true; 

TetrisFrameस्क्रीन में हेरफेर करने के लिए 4 तरीके हैं। विधि displayTetriminoनिर्दिष्ट निर्देशांक में सक्रिय टेट्रीमिनो प्रदान करती है। यह एक विलंब पैरामीटर प्राप्त करता है, जो कि एनीमेशन फ़्रेम की निर्दिष्ट संख्या को वापस करने से पहले प्रतीक्षा करने की विधि का कारण बनता है।

 public void displayTetrimino(int type, int rotation, int x, int y, int delay) 

विधि lockTetriminoजगह में आंकड़ा ताला लगाती है। पंक्ति काउंटर, अंक, स्तर और टेट्रिमिनो रंग तदनुसार अद्यतन किए जाते हैं, जब अपेक्षित अनुमेय मूल्यों से अधिक होने पर अपेक्षित जिज्ञासु व्यवहार का प्रदर्शन करते हैं। एक पैरामीटर के लिए एक animateमान असाइन trueकरना टेट्रिस प्राप्त करते समय पंक्ति सफाई एनिमेशन और स्क्रीन टिमटिमा शामिल है। एनीमेशन खत्म होने तक विधि अवरुद्ध है।

 public void lockTetrimino(int type, int rotation, int x, int y, boolean animate) 

updateStatisticsAndNext नए बनाए गए tetrimino के लिए सांख्यिकी काउंटर की वृद्धि करता है और अगले आंकड़े का प्रदर्शन अपडेट करता है।

 public void updateStatisticsAndNext(int activeTetrimino, int nextTetrimino) 

विधि dropTetriminoएक आकृति बनाती है और इसे "गुरुत्वाकर्षण" के प्रभाव में उतरने की अनुमति देती है, बिना इसे घुमाने या स्थानांतरित करने का कोई प्रयास किए बिना। Mainजब यह AI.searchवापस लौटता है तो इसे अंतिम दो आंकड़ों के लिए उपयोग करता है null। यदि पैरामीटर animateमायने रखता है true, तो अगर एक आंकड़ा बनाना असंभव है, तो खेल के अंत का पर्दा गिर जाएगा। अन्य सभी विधियों की तरह, यह विधि तब तक अवरुद्ध होती है जब तक कि एनीमेशन समाप्त नहीं हो जाता। यह trueतभी लौटता है जब यह व्यस्त खेल मैदान पर एक आंकड़ा बना सकता है।

 public boolean dropTetrimino(int type, boolean animate) 

इन 4 विधियों को वर्कफ़्लो द्वारा बुलाया जाना चाहिए, लेकिन TetrisFrameइवेंट डिस्पैच थ्रेड में ही बनाया जाना चाहिए। यह देखने के लिए कि यह कैसे किया जाता है, कक्षा देखें Main।

रुचि के लिए, वह Mainएक वर्ग का उपयोग करता है Randomizerजो निंटेंडो टेट्रिस से एक पक्षपाती छद्म यादृच्छिक संख्या जनरेटर का अनुकरण करता है ।

पैकेज tetris.gui.imagesमें डिस्प्ले से संबंधित फाइलें हैं। tiles.png- यह एक पैटर्न टेबल है जिसमें सभी टाइल ग्राफिक्स हैं। background.datटाइल के पहचानकर्ताओं को संग्रहीत करता है जो पृष्ठभूमि बनाते हैं; से डेटा निकाला गया $BF3F। और colors.datइसमें बाइट्स होते हैं जो 138 के स्तर से दिखाई देने वाले असामान्य वर्ग रंग उत्पन्न करते हैं। इसमें

ImageLoaderएनईएस पैलेट्स की एक तालिका होती है, और ImagePaneप्रदर्शित स्तर मानों का पूरा सेट संग्रहीत होता है।

अन्य परियोजनाएं

संभावित रूप से, कोड का उपयोग डेमो मोड के लिए लिखने के बजाय किया जा सकता है। वास्तव में, इस तरह के एक डेमो को हमेशा के लिए प्रदान किया जा सकता है, जिसका लाभ उठाकर एआई पूरे खेल के मैदान को साफ करने में सक्षम है। इसे प्राप्त करने के लिए, छद्म यादृच्छिक संख्या जनरेटर में, आपको बीज के रूप में कुछ मनमाने ढंग से स्थिर का उपयोग करने की आवश्यकता होती है, जो हमें एक नियतात्मक टेट्रिमिनो अनुक्रम देगा। पहले दो टेट्रिमिनो अनुक्रम दर्ज किए जाएंगे। जब एआई पूरे क्षेत्र की सफाई तक पहुंचता है, तो अगले दो टेट्रिमिनोज की तुलना अनुक्रम के पहले दो के साथ की जाएगी। यदि वे मेल खाते हैं (यह घटना हर 49 पूर्ण क्षेत्र की सफाई की उम्मीद है), तो छद्म यादृच्छिक संख्या जनरेटर को बीज के समान निरंतर पास किया जा सकता है, जो एक अनंत डेमो लूप बनाएगा। चक्र की अवधि इस तथ्य को छिपाने के लिए बहुत लंबी हो सकती है कि यह एक चक्र है। इसके अलावा,डेमो लूप में एक यादृच्छिक बिंदु पर शुरू हो सकता है, हर बार एक नया डेमो बना सकता है।

एआई का उपयोग करने की एक और संभावना "खिलाड़ी बनाम कंप्यूटर" मोड बनाना है। मल्टी-प्लेयर टेट्रिस में, एक ही समय में कई लाइनों को साफ करते समय, प्रतिद्वंद्वी के मैदान के निचले हिस्से में कचरा लाइनें दिखाई देती हैं, जिससे खेल का मैदान ऊपर उठता है। एआई को उसी कारण से मलबे से बचाने में सक्षम होना चाहिए ताकि वह बी-टाइप गेम खेल सके। हालांकि, जैसा कि पहले कहा गया है, AI रूढ़िवादी रूप से खेलता है, आमतौर पर एक समय में एक पंक्ति को साफ़ करने का प्रयास करता है। यही है, वह हमलों से खुद का बचाव करने में सक्षम होगा, लेकिन वह हमला करने में सक्षम नहीं है। अपने व्यवहार को बदलने में सक्षम होने के लिए, मैंने एक इंटरफेस बनाया IChildFilter।

 public interface IChildFilter { public boolean validate(int[][] playfield, int tetriminoType, int x, int y, int rotation); } 

AIएक वैकल्पिक कंस्ट्रक्टर है जिसे एक कार्यान्वयन मिलता है IChildFilter। यदि उपलब्ध है, तो IChildFilter.validateयह बाल राज्य की अनुमति के लिए एक अतिरिक्त चेक के रूप में कार्य करता है; यदि यह वापस आ जाता है false, तो बाल राज्य की कतार नहीं है।

WellFilterएक कार्यान्वयन हैIChildFilterचार पंक्तियों (टेट्रिस) को उठाने के उद्देश्य से। जीवित खिलाड़ियों की तरह, वह धीरे-धीरे खेल के मैदान के सबसे दाहिने कॉलम में एक कुआं बनाती है, जो नीचे से ऊपर तक लाइन से बढ़ती है। चूंकि यह लाइन द्वारा लाइन काम करता है, यह बच्चे के राज्यों को अस्वीकार करता है जो एक वर्ग को सबसे सही कॉलम में जोड़ता है। जब अच्छी तरह से कॉलम के अपवाद के साथ पूरी पंक्ति पूरी तरह से भरी हुई है, तो AI अगली पंक्ति में आगे बढ़ता है। जब इनमें से 4 या अधिक लाइनें तैयार होती हैं, तो यह "छड़ी" को कुएं में गिरने और टेट्रिस प्राप्त करने की अनुमति देता है। इसके अलावा, ढेर की ऊंचाई को ट्रैक किया जाता है; यदि यह बहुत बड़ा हो जाता है, तो यह WellFilterAI को प्रभावित करना बंद कर देता है।


ऑपरेशन में इसका परीक्षण करने के लिए, Mainनिम्नलिखित बदलाव करें:

 AI ai = new AI(new WellFilter()); 

WellFilterकाम करता है, लेकिन विशेष रूप से प्रभावी नहीं है। इसमें अवधारणा को प्रदर्शित करने के लिए डिज़ाइन किया गया एक सरल अनुमान है। टेट्रिस को अधिक बार प्राप्त करने के लिए, आपको अधिक परिष्कृत रणनीति का उपयोग करने की आवश्यकता है, शायद एक जिसे पीएसओ का उपयोग करके अनुकूलित किया जा सकता है।

इसके अलावा, आप पैटर्न उत्पन्न करने के लिए बाल अवस्था फ़िल्टरिंग का उपयोग कर सकते हैं। नीचे एक उदाहरण है कि वह क्या करने में सक्षम है PatternFilter।


PatternFilterयह कैसे काम करता है के समान नीचे से ऊपर तक रेखा द्वारा छवियां बनाता है WellFilter; हालांकि, सही कॉलम को संरक्षित करने के बजाय, यह PatternFilterकेवल उन बच्चों को बताता है जो एक विशेष पैटर्न के अनुरूप हैं।

निर्माणकर्ता PatternFilterको पैकेज में एक चित्र का नाम मिलता है tetris.gui.patterns, जिसे वह एक टेम्पलेट के रूप में उपयोग करता है। प्रत्येक 20 × 10 छवि में खेल के मैदान में कोशिकाओं के अनुरूप काले और सफेद पिक्सेल होते हैं।

 AI ai = new AI(new PatternFilter("tetriminos")); 

ऊपर दिखाई गई कोड की लाइन टेट्रीमिनो के सात प्रकार के सिल्हूट बनाती है।


एक बड़े टेट्रीमिनो टी के साथ एक और उदाहरण एक कोण पर घुमाया गया।


एक और उदाहरण। यदि आप बारीकी से देखते हैं, तो आप खेल का नाम देखेंगे।


जैसे WellFilter, यह PatternFilterअवधारणा के प्रमाण से ज्यादा कुछ नहीं है। वह जिन प्रक्रियाओं को संसाधित करता है, वे इस तथ्य के कारण खेल के मैदान के नीचे तक सीमित होते हैं कि उन्हें प्राप्त करने का प्रयास आमतौर पर खेल खत्म हो जाता है। हालांकि, यह आगे के अध्ययन के लायक एक दिलचस्प विचार है।

गेमपैड संस्करण

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

गुरुत्वाकर्षण को जोड़ने से खोज स्थान का विस्तार होता है, एआई को आकृतियों के हेरफेर के चालाक नियमों को ध्यान में रखने के लिए मजबूर किया जाता है। इन नियमों का विवरण लेख के पहले भाग में वर्णित है, और कोड के प्रत्यक्ष अध्ययन द्वारा पूरी तरह से सराहना की जा सकती है। यहाँ सबसे महत्वपूर्ण हैं:

• : , .
• «» .
• «» «» .
• .
• .
• .
• .
• , .
• A B .
• «» «» 6 16 . «» «» , .
• «» 3 .
• 96 . , — .

इन सभी नियमों को समायोजित करने के लिए, ऐतिहासिक जानकारी को खोज राज्यों में एम्बेड किया जाना चाहिए। उन्हें उन क्षेत्रों की आवश्यकता होती है जिसमें प्रत्येक बटन के लिए होल्डिंग फ्रेम की संख्या और अंतिम स्वचालित रिलीज के बाद फ्रेम की संख्या संग्रहीत की जाएगी। निर्देशांक सहित मूल्यों, में से प्रत्येक अद्वितीय सेट x, yऔर रोटेशन व्यक्तिगत और अद्वितीय राज्य की विशेषताएँ tetrimino। दुर्भाग्य से, संभावनाओं की संख्या इतनी विशाल है कि इस स्थान की पूरी खोज अव्यावहारिक है। गेमपैड के लिए AI संस्करण केवल इसके सबसेट की खोज करता है।

एआई Stateनिम्नलिखित क्षेत्रों के साथ एक वस्तु का उपयोग करता है :

 { x, y, rotation, Left, Right, Down, A, B, fallTimer, visited, predecessor } 

वैकल्पिक फ़्रेम में स्वचालित AI शिफ्ट का उपयोग करने के बजाय, शिफ्ट बटन को दबाएं और छोड़ें। इसलिए, उसे केवल तब निगरानी करने की आवश्यकता है, जब बटन दबाया जाता है, और न कि इसे कितने समय तक दबाया जाए। कोई स्वत: रोटेशन के बाद से, एक ही विचार बटन ए और बी इसलिए क्षेत्र पर लागू होता है Left, Right, Aऔर Bनिम्न में से एक मान युक्त लिस्टिंग के रूप में व्याख्या की जा सकती:

 { RELEASED, PRESSED } 

दूसरी ओर, नरम वंश के लिए, आपको शुरू में तीन फ्रेम के लिए "डाउन" बटन दबाए रखना होगा, जिसके लिए 4 के अस्तित्व की आवश्यकता होती है:

 { RELEASED, PRESSED_FOR_1_FRAME, PRESSED_FOR_2_FRAMES, PRESSED_FOR_3_FRAMES } 

Downवृद्धिशील मूल्य से बढ़ RELEASEDजाता है PRESSED_FOR_3_FRAMES, जिस पर एक नरम वंश होता है। उसके बाद, यह एक मूल्य प्राप्त कर सकता है RELEASEDया वापस लौट सकता है PRESSED_FOR_2_FRAMES, जिससे शुरुआती देरी के बाद हर दूसरे फ्रेम में एक नरम वंश हो सकता है। यह नहीं हो सकता RELEASEDसे PRESSED_FOR_1_FRAMEया PRESSED_FOR_2_FRAMES।

दरअसल, Lua कोड एक पूर्णांक स्थिरांक का उपयोग करता है, लेकिन सिद्धांत समान है।

इसी तरह, visitedऔर predecessor, fallTimerइसे प्राप्त जब सहायक कतार राज्य में लिख मूल्य असाइन किया गया है; यह fallTimerमूल राज्य के मूल्य से एक अधिक होगा। शर्त युक्तfallTimer, जो कि वंश गति के बराबर है, का तात्पर्य है कि इस फ्रेम में स्वचालित वंश होता है, और इस राज्य की अगली स्थिति fallTimer0. होगी।

प्रत्येक Searcherपूर्व 8-में सभी संभावित राज्यों ( 20 × 10 × 4 × 2 × 2 × 4 × 2 A × 2 B) से युक्त एक सरणी को परिभाषित करता है , और BFS को सरणी के लिए दिखाए गए विधि के समान निष्पादित किया जाता है । नीचे दिखाया गया छद्म कोड बताता है कि बाद के राज्यों को किस प्रकार के राज्यों से प्राप्त किया जाता है।

 Slide = (Left == PRESSED) or (Right == PRESSED) Rotate = (A == PRESSED) or (B == PRESSED) if Down == RELEASED or Down == PRESSED_FOR_3_FRAMES then if Down == RELEASED then nextDown = PRESSED_FOR_1_FRAME else nextDown = PRESSED_FOR_2_FRAMES end addChild(Down = nextDown) if not Rotate then addChild(A = PRESSED, Down = nextDown) addChild(B = PRESSED, Down = nextDown) end if Slide then addChild() if not Rotate then addChild(A = PRESSED) addChild(B = PRESSED) end else addChild(Left = PRESSED) addChild(Right = PRESSED) if not Rotate then addChild(Left = PRESSED, A = PRESSED) addChild(Left = PRESSED, B = PRESSED) addChild(Right = PRESSED, A = PRESSED) addChild(Right = PRESSED, B = PRESSED) end end else if Down == PRESSED_FOR_1_FRAME then nextDown = PRESSED_FOR_2_FRAMES else nextDown = PRESSED_FOR_3_FRAMES end addChild(Down = nextDown) if not Rotate then addChild(A = PRESSED, Down = nextDown) addChild(B = PRESSED, Down = nextDown) end end 

जैसा कि नीचे दिए गए छद्म कोड में दिखाया गया है, फ़ंक्शन addChildप्रत्येक फ्रेम में होने वाली घटनाओं के क्रम को ध्यान में रखता है (उदाहरण के लिए, पारी, रोटेशन और वंश)।

 nextFallTimer = fallTimer + 1 if Left == PRESSED and testPosition(x - 1, y, rotation) then x = x - 1 elseif Right == PRESSED and testPosition(x + 1, y, rotation) then x = x + 1 end if A == PRESSED and testPosition(x, y, nextClockwiseRotation) then rotation = nextClockwiseRotation elseif B == PRESSED and testPosition(x, y, nextCounterclockwiseRotation) then rotation = nextCounterclockwiseRotation end if Down == PRESSED_FOR_3_FRAMES or nextFallTimer >= dropSpeed then if testPosition(x, y + 1, rotation) then y = y + 1 nextFallTimer = 0 else lockTetrimino() return end end childState = states[y][x][rotation][Left][Right][Down][A][B] if not childState.visited then childState.visited = mark childState.predecessor = state childState.fallTimer = nextFallTimer queue.enqueue(childState) end 

पिछले संस्करण की तरह, यह AI.searchवस्तुओं की एक श्रृंखला लौटाता है State। लेकिन इस मामले में, प्रत्येक Stateमें कई बटन होते हैं जिन्हें प्रत्येक फ्रेम में दबाने की आवश्यकता होती है। फ़ील्ड्स x, yऔर rotationआकृतियों में हेरफेर करने के लिए उपयोग नहीं किया जाता है, लेकिन उनका उपयोग आकृतियों के सही आंदोलन को सत्यापित करने के लिए किया जा सकता है।

यद्यपि ऊपर वर्णित सीमाओं के कारण खोज स्थान काफी कम हो गया है, लेकिन खोज को पूरा करने में 1-3 सेकंड लगते हैं। यदि आप इसे चलाते हैं, तो आप प्रत्येक टेट्रीमिनो बनाने के बाद एक ठहराव देखेंगे। इसके अलावा, आंदोलनों बहुत अप्राकृतिक लगती हैं; आमतौर पर ताला लगाने से पहले एक मोड़ तुरंत बनाया जाता है। हालांकि, यह एआई लगभग उसी तरह से खेलता है जैसे कि अधिकतम गति पर भी गुरुत्वाकर्षण को अनदेखा करता है।

इसे जांचने के लिए, इसे स्रोतों के साथ ज़िप फ़ाइलlua/NintendoTetrisAIGamepadVersion.lua में स्थित चलाएं ।

गुरुत्वाकर्षण के लिए एक सरल तरीका यह है कि आंकड़े की गति को केवल मोड़कर, एक पारी के बाद सीमित किया जाए, और फिर नीचे की ओर उतर दिया जाए। विचार यह है कि यदि आप स्लाइडिंग और स्क्रॉलिंग से छुटकारा पा लेते हैं, तो आंकड़े की ऊर्ध्वाधर गति का एआई पर बहुत कम प्रभाव पड़ेगा; उसे केवल इतना करना है कि वह वांछित कॉलम में आंकड़ा पहुंचाए, और गुरुत्वाकर्षण बाकी काम करेगा। इस तकनीक का एक अन्य लाभ यह है कि खोज स्थान बहुत छोटा है, जो आपको गणना के लिए देरी के बिना, वास्तविक समय में खेलने की अनुमति देता है। हालांकि, इस दृष्टिकोण का दोष यह है कि स्लाइडिंग और स्क्रॉलिंग के बिना, AI बहुत बुरा खेलता है। हालांकि, Tetris ऐ, वास्तविक समय में खेलने में असमर्थ, व्यावहारिक रूप से बेकार है।

इसके अलावा

इससे पहले, मैंने एक प्लगइन लिखा था जो कि टेट्रिस में एक खिलाड़ी की प्रक्रिया करता था। हालाँकि, मेरी परियोजना में कुछ नुकसान थे:

1. बॉट ने गुरुत्वाकर्षण को बंद कर दिया, जिससे आप ग्लाइडर और स्क्रॉलिंग का प्रदर्शन कर सकते हैं, जो कि निनटेंडो टेट्रिस के बहुत न्यूनतम स्तर पर खिलाड़ी की क्षमताओं से अधिक है। वह कभी भी आंकड़े नीचे नहीं बढ़ाता, लेकिन आंकड़ों को कम करने का एकमात्र तरीका एक नियंत्रित नरम वंश है। यही है, वह एक सैद्धांतिक, आदर्शित दुनिया में खेलता है। कुंद करने के लिए, वह धोखा देता है।
2. . — , . Double, Triple Tetris, — , . 90. , , 29 - .
3. . . . , Tetris .

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

---

वीडियो

नीचे दिखाए गए सभी वीडियो में बॉट को निन्टेंडो टेट्रिस पॉइंट्स की अधिकतम संख्या 19 के स्तर से शुरू करें।

---

डाउनलोड

TetrisAI_2018-01-28.zip

फ़ाइल .zipमें है:

• src - सोर्स कोड ट्री
• TetrisAI.jar - संकलित बाइनरी फ़ाइल।
• lgpl-2.1.txt - मुफ्त सॉफ्टवेयर लाइसेंस।

---

लांच

आवश्यक शर्तें

• Nintaco एक NES / Famicom एमुलेटर है।
• Tetris (U) [!].nes - निनटेंडो टेट्रिस रॉम फ़ाइल।

प्लगइन लॉन्च

1. Nintaco लॉन्च करें और खोलें Tetris (U) [!].nes।
2. TetrisAI.jarडाउनलोड से निकालें .zip।
3. टूल चुनकर रन प्रोग्राम विंडो खोलें प्रोग्राम चलाएं ...
4. JAR Find JAR… .
5. Load JAR, .
6. Run.
7. , GAME TYPE MUSIC TYPE . D-pad ( ) A-TYPE . Start (Enter), .
8. A-TYPE D-pad ( ) LEVEL 9 . , A Start ( X Enter), 19, .

यह विचार करने योग्य है कि बॉट केवल स्तर 19 और इसके बाद के संस्करण के लिए डिज़ाइन किया गया है। निचले स्तरों पर, वह टुकड़ों को नियंत्रित करने में सक्षम नहीं होगा।

गति का संदर्भ

खेल तेजी से आगे बढ़े, इसके लिए मशीन का चयन करें गति | मैक्स।

---

विवरण

पठार

10 के स्तर के नीचे, प्रत्येक स्तर पर वंश गति पिछले एक की तुलना में थोड़ा अधिक है। लेकिन 10 के स्तर पर और ऊपर कई पठार हैं, जिस पर गति कई स्तरों तक स्थिर रहती है। यह ट्रिगर तंत्र के काम करने के तरीके का एक परिणाम है। गति को प्रति वंश फ्रेम की संख्या के रूप में प्रस्तुत किया जाता है, जो पूर्णांक मान है। यही है, उच्च स्तरों के लिए कई विकल्प नहीं बचे हैं: 10-12, 13-15, 16-18, 19–28 और 29+ 5, 4, 3, 2 और वंश के लिए 1 फ्रेम हैं।

इस बोट को केवल 1928 के पठार को ध्यान में रखते हुए विकसित किया गया था। यहां तक ​​कि फ्रेम में, वह गेमपैड "लेफ्ट", "राइट", ए, बी या कुछ भी पर क्लिक करता है। और विषम फ़्रेमों में, यह किसी भी बटन को दबाए बिना स्वचालित वंश की अनुमति देता है। ऐसा लगता है कि खेल रोटेशन के साथ मेल खाते क्षैतिज आंदोलन का अनुभव नहीं करता है; इसलिए, प्रत्येक बटन को स्वतंत्र रूप से भी फ़्रेम में दबाया जाता है।

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

खिलाड़ियों को सिंगल, डबल, ट्रिपल और टेट्रिस के लिए 40, 100, 300 और 1200 अंकों से पुरस्कृत किया जाता है। और अंक को स्तर संख्या 1 से गुणा किया जाता है। दूसरे शब्दों में, अधिकतम अंक प्राप्त करने के लिए, खिलाड़ी को उच्च स्तर पर यथासंभव लंबे समय तक खेलना, टेट्रिस की अधिकतम संख्या के लिए प्रयास करना चाहिए।

लेवल 19 वह उच्चतम है जिसे शुरुआती एक के रूप में चुना जा सकता है, जो बॉट को पठार पर सीधे 1928 में कूदने की अनुमति देता है। हालाँकि, मैंने पिछले भाग में बताए गए लेवल कैलकुलेशन मैकेनिज्म में एक बग के कारण, गेम में अपेक्षित 200 के बजाय 140 पंक्तियों को क्लियर करने के बाद गेम 20 लेवल पर चला जाएगा। इसके बाद, गेम हर 10 पंक्तियों में लेवल बदल देगा। हालांकि, 230 पंक्तियों तक पहुंचने के बाद, बॉट पठार से उठेगा और जल्दी से छोड़ देगा। यही है, उसे 230 पंक्तियों की सफाई से पहले जितना संभव हो उतना टेट्रिस डायल करना होगा।

नरम वंश

नरम वंश भी अंकों की संख्या बढ़ा सकता है। अंक प्राप्त करने के लिए, खेल मैदान पर ताला लगाने के लिए आकृति को धीरे से नीचे करना चाहिए। किसी भी अल्पकालिक नरम वंश जो किसी आंकड़े की स्थिति के रास्ते में होता है, जो स्कोर को प्रभावित नहीं करेगा। यदि वंश सफल होता है, तो खिलाड़ी को नरम वंश के दौरान पार की गई प्रत्येक पंक्ति के लिए एक अंक प्राप्त होगा। और परिणामी मूल्य को स्तर संख्या से गुणा नहीं किया जाता है, भले ही एक नरम वंश पंक्तियों को साफ़ करने की ओर जाता हो।

नरम वंश का समग्र स्कोर पर बहुत कम प्रभाव होता है। हालाँकि, यदि संभव हो, तो बॉट इन बिंदुओं को प्राप्त करने के लिए "डाउन" पर क्लिक करके आंकड़े के स्थान को पूरा करता है। दुर्लभ मामलों में, यह बहुत उच्च स्कोर और अधिकतम स्कोर से अधिक के बीच अंतर को औसत कर सकता है।

एआई एल्गोरिथम

आकार बनाते समय, बॉट वर्तमान और अगले आकृतियों के हर संभव स्थान की खोज करता है। अनुमेय प्लेसमेंट वह स्थिति है जिसमें आकृति या तो कब्जा की गई कोशिकाओं पर या खेल के मैदान के फर्श पर टिकी हुई है। आकृति के निर्माण के स्थान से, क्षैतिज स्थिति, घुमाव और अवरोह के अनुक्रम के माध्यम से इस स्थिति तक पहुंचा जा सकता है। बीएसएफ का उपयोग करके वैध स्थान और पथ अनुक्रम पाए जाते हैं।

खेल के मैदान पर एक टुकड़ा रखने के परिणाम हैं: 4 खाली कोशिकाओं पर कब्जा हो जाता है, और सभी भरे हुए पंक्तियों को साफ कर दिया जाता है, जिससे पंक्तियों को नीचे चला जाता है। वर्तमान आंकड़े के प्रत्येक स्वीकार्य प्लेसमेंट और इससे जुड़े परिणामों के लिए, बॉट परिणामों के संयोजन का मूल्यांकन करते हुए, अगले आंकड़े के प्रत्येक स्वीकार्य प्लेसमेंट की जांच करता है। ऐसी खोज श्रृंखला प्रस्तुत की गई है SearchChain।

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

मूल्यांकन समारोह

मूल्यांकन समारोह निम्नलिखित मापदंडों का एक भारित योग है:

• साफ की गई पंक्तियों की कुल संख्या दोनों tetriminos के जोड़ से साफ की गई पंक्तियों की संख्या है।
• – , . — , , .
• - – .
• – , -.
• – , . . .
• – . , 1. , , .
• – , . — , — .
• – . , (20).
• – . , 0.
• – , ( ) .
• : — , ( ) . . . .
• – . , 1 , 1, — 0.
• – .
• – .
• – .
• – . .
• – .

मशीन सीखने

मूल्यांकन समारोह के वजन का पता लगाने के लिए, हमने फुटनोट [1] में वर्णित कण झुंड अनुकूलन (पीएसओ) पद्धति के एक संस्करण का उपयोग किया। अच्छा अभिसरण व्यवहार प्राप्त करने के लिए, प्रस्तावित जड़ता और त्वरण गुणांक लागू होते हैं। और कण चरणों की अधिकतम आकार उनके वेग मूल्यों की सीमा से निर्धारित होती है।

प्रत्येक पुनरावृत्ति के दौरान, उपलब्ध कंप्यूटिंग संसाधनों का पूर्ण उपयोग करने के लिए समानांतर में कणों का मूल्यांकन किया गया था। इसके अलावा, अभिसरण का पता चलने के बाद (पुनरावृत्तियों की एक निश्चित संख्या के बाद कोई सुधार नहीं), पीएसओ को स्वचालित रूप से चयनित वजन के साथ फिर से चालू करने के लिए सेट किया गया था, जिसने हमें खोज स्थान को और अधिक देखने की अनुमति दी।

प्रत्येक कण स्थिति वेक्टर का मूल्यांकन 19-28 के स्तर के पठार पर 100 बैचों के पूरा होने का अनुकरण करके किया गया था। एक पूर्ण बैच में 230 पंक्तियों की सफाई शामिल है, लेकिन कई क्षेत्र के अतिप्रवाह के साथ समाप्त हो गए। बैच के अंकों को क्रमबद्ध किया गया था, और 100 बैचों में से 33 के औसत के रूप में कण स्कोर निर्धारित किए गए थे। आक्रामकता के आधार पर विचार करना था। ऊपरी तीसरे में कण केवल वांछित अनुक्रमों के लिए उपयोग किए जाते हैं, जो एक रूढ़िवादी खेल की आवश्यकता को सीमित करता है। नतीजतन, वे सामान्य गेम को कगार पर धकेल देते हैं, अगले "छड़ी" की प्रतीक्षा करते हैं।

पीएसओ से पहले 100 बैचों के लिए पैटर्न अनुक्रम उत्पन्न किए गए थे, और बार-बार समान अनुक्रमों का उपयोग किया गया था। खोज स्थान को ठीक करने के लिए यह आवश्यक था, ताकि समाधान विकल्पों की एक दूसरे के साथ तुलना की जा सके। वास्तविक PRNG निन्टेंडो टेट्रिस के तर्क का उपयोग करके अनुक्रम बनाए गए थे, जो एक दूसरे के बाद डुप्लिकेट की संभावना को कम करने के लिए डिज़ाइन किया गया है। लेकिन PRNG में भी कमजोरियां हैं (एक पिछले लेख से "टेट्रिमिनो चुनना" खंड देखें): यह समान रूप से आंकड़े का चयन नहीं करता है।

शुरुआती प्रयासों के परिणामस्वरूप बॉट्स बहुत आक्रामक तरीके से काम करने लगे। यदि वे 1928 के पठार से आगे निकल गए, तो वे आमतौर पर अधिकतम स्कोर पर पहुंच गए। लेकिन, दुर्भाग्य से, वे अक्सर बहुत जल्दी फील्ड ओवरफ्लो का नेतृत्व करते थे। इसके जवाब में, बॉट्स को "शांत" करने के लिए चार कदम उठाए गए:

1. : Tetris, . «» . . ; 230 . , Tetris . Single, Double Triple. ; .
2. . , , 7 . .
3. , , . , 7 .
4. , , . , . , .

बॉट्स को "शांत" करने के लिए इन सभी नियमों को लागू करने के बाद, पीएसओ पद्धति ने निम्नलिखित भार दिए:

पैरामीटर	भार
पंक्तियों की कुल संख्या साफ हो गई	.286127095297893900
कुल अवरुद्ध ऊंचाई	1.701233676909959200
अच्छी तरह से कोशिकाओं की कुल संख्या	.711304230768307700
कुल गहरे कुएँ	.910665415998680400
स्तंभों में छेदों की कुल संख्या	1.879338064244357000
कुल भारित स्तंभ छेद	2.168463848297177000
स्तंभों में छेद की गहराई की कुल संख्या	-.265587111961757270
न्यूनतम स्तंभ छेद गहराई	.289886584949610500
अधिकतम स्तंभ छेद गहराई	.362361055261181730
स्तंभों में संक्रमण की कुल संख्या	-.028668795795469625
कुल लाइन कूदता है	.874179981113233100
टोटल कॉलम हाइट्स	-.507409683144361900
ढेर की ऊँचाई	-2.148676202831281000
कॉलम हाइट स्कैटर	-1.187558540281141700
कब्जे वाली कोशिकाओं की कुल संख्या	-2.645656132241128000
कब्जे वाली कोशिकाओं की कुल भारित संख्या	.242043416268706620
स्तंभ ऊंचाई फैलाव	.287838126164431440

चूंकि चेन एक संयोजन के लिए प्रयास करता है जो मूल्यांकन फ़ंक्शन को कम करता है, सकारात्मक भार वाले मापदंडों को बोनस माना जा सकता है, और बाकी - जुर्माना। लेकिन वज़न आवश्यक रूप से संबंधित मापदंडों के महत्व को नहीं दर्शाता है; वे सामान्यीकृत नहीं हैं, इसलिए उनकी तुलना नहीं की जा सकती है।

ऐ ताकत

एआई की ताकत का आकलन करने के लिए, नकली खेलों के लगभग 1.7 मिलियन परिणाम (अंक में) 1928 के पठार पर एकत्र किए गए थे। स्कोर 29 या उच्च स्तर पर खेल को प्रतिबिंबित नहीं करता है, और नरम वंश से प्राप्त अंक को ध्यान में नहीं रखता है। हालाँकि, इसमें ओवरफ्लो के कारण समय से पहले पूरा होने वाले खेल शामिल हैं। निन्टेंडो टेट्रिस PRNG लॉजिक का उपयोग टेट्रिमिनो अनुक्रम उत्पन्न करने के लिए किया गया था।

इन परिणामों के बीच, सबसे बड़ा स्कोर 1,313,600 है। न्यूनतम 0. 0.

औसत 816,379 है, और यह छोटा प्रतीत होता है। लेकिन जैसा कि नीचे उल्लेख किया गया है, डेटा विकृत हैं, इसलिए 989,200 अंक का औसत स्कोर विशिष्ट मूल्य का बेहतर विचार देता है।

जैसा कि ऊपर कहा गया है, पीएसओ ने सबसे अच्छे तीसरे बैचों के औसत के आधार पर वजन को अनुकूलित किया। इस मामले में, सर्वश्रेष्ठ तीसरे का औसत स्कोर 1 108 860 है। वास्तव में, सबसे अच्छा 75% का औसत स्कोर 1,000,000 है।

बॉट में 47% की संभावना है कि सीमा सीमा 29 तक पहुंच सकती है। इसमें 900% अंक प्राप्त करने की संभावना 61,000 है। 29. नीचे दिया गया ग्राफ़ 29 के स्तर तक स्कोर करने की संभावनाओं को दर्शाता है।


ऐसा लगता है कि संभावना लगभग 900,000 अंकों तक रैखिक घट जाती है। फिर यह एक उल्टे सिग्मॉयड कर्व में चला जाता है।

नीचे दिए गए प्रत्येक बिंदु के लिए पार्टियों की संख्या के साथ एक स्मूथ हिस्टोग्राम है। इसका आकार ऊपर दिखाए गए ग्राफ के व्युत्पन्न द्वारा निर्धारित किया जाता है।


यदि आप उतार-चढ़ाव की उपेक्षा करते हैं, तो लगभग 900,000 तक यह समतल है, और फिर लगभग 1,050,000 अंकों के साथ केंद्र के साथ एक सामान्य वितरण में चला जाता है। उतार-चढ़ाव के कारण स्पष्ट नहीं हैं। ऐसा लगता है कि अंकों की संख्या 20,000 अंकों की वृद्धि में कूदना पसंद करती है। शायद यह ढेर निर्माण चक्र और टेट्रिस प्राप्त करने के कारण है।

RAM और ROM का आवंटन

सीपीयू मेमोरी में हेरफेर करने के लिए, बटन क्लिक संचारित करें और फ़्रेम रेंडरिंग इवेंट प्राप्त करें, प्लगइन Nintaco API का उपयोग करता है । Nintaco डिबगिंग टूल का उपयोग करके सभी मेमोरी पतों की खोज की गई थी, और डेटा क्रिस्टल ROMhacking.net विकी में जानकारी जोड़ी गई थी । स्रोत कोड में, वे इंटरफ़ेस में स्थिरांक की तरह दिखते हैं Addresses।

---

संदर्भ सामग्री

1. van den Bergh, F.; Engelbrecht, AP (2006)
   A study of particle swarm optimization particle trajectories
   In: Information Sciences 176 (2006) (pp. 937–971)
   Retrieved from http://researchspace.csir.co.za/dspace/bitstream/handle/10204/1155/van%20den%20bergh_2006_D.pdf