👔 🚑 👻 खेल के उदाहरण पर मिनीमैक्स एल्गोरिथ्म "लीजिए 4 (कनेक्ट 4)" 👩🏿‍🤝‍👨🏾 🤦🏽 😦

गेम "4 लीजिए" के उदाहरण पर मिनिमैक्स एल्गोरिथ्म का कार्यान्वयन एक बहुत ही रोमांचक गतिविधि है और इसके संबंध में, इस शौक को किसी और को बताने की इच्छा थी, जो मैंने किया। खेल इस पते पर उपलब्ध है।

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

खेल के नियम ऐसे हैं कि आप बोर्ड पर किसी भी स्थान पर एक टुकड़ा स्थापित नहीं कर सकते हैं, लेकिन केवल तल पर, और टुकड़े (किसी भी) के कब्जे वाले क्षेत्र के ऊपर स्थित तल को भी नीचे माना जाता है। बोर्ड एक आयामी सरणी के रूप में प्रस्तुत किया

TicTac field[NSIZE_I*NSIZE_J];

संरचनाएं स्वयं ऐसी हो सकती हैं

 typedef enum {Tic, Tac, EMPTY} TicTac;

, खेल के लिए आपको कई प्रक्रियाओं की आवश्यकता होगी (अपेक्षाकृत), कोड सत्यापन प्रक्रिया के रूप में कार्यान्वित किया जाता है

 int validstep(const TicTac *field, int step){ return ((field[step]==EMPTY)&&((step + NSIZE_J >= NSIZE_I*NSIZE_J)||((step + NSIZE_J < NSIZE_I*NSIZE_J)&&(field[step + NSIZE_J] != EMPTY))));}

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

 int c4getrait(const TicTac *field, TicTac Me){ int i, j, k, score=0, maxscore=-1; /* X X X */ for(i=0; i<NSIZE_I; i++){ score=0; for(j=0; j<NSIZE_J; j++){ //printf( "i=%d; j=%d\n", i, j ); if(field[i*NSIZE_J + j] == Me) score++; else { maxscore = (score > maxscore)?score:maxscore; score = 0; if(maxscore == WIN) return maxscore; } } maxscore = (score > maxscore)?score:maxscore; } /* XXX */ for(j=0; j<NSIZE_J; j++){ score=0; for(i=0; i<NSIZE_I; i++){ if(field[i*NSIZE_J + j] == Me) score++; else { maxscore = (score > maxscore)?score:maxscore; score = 0; if(maxscore == WIN) return maxscore; } } maxscore = (score > maxscore)?score:maxscore; } /*main up diag XXX XX X */ for(k=0; k<NSIZE_J; k++){ score=0; for(i=0, j=NSIZE_J-k-1; i<NSIZE_I&&j>=0; i++, j--){ //printf( "i=%d; j=%d\n", i, j ); if(field[i*NSIZE_J + j] == Me) score++; else { maxscore = (score > maxscore)?score:maxscore; score = 0; if(maxscore == WIN) return maxscore; } } //printf( "\n" ); maxscore = (score > maxscore)?score:maxscore; }...

।

बेशक, कार्यक्रम में सबसे महत्वपूर्ण और जटिल प्रक्रिया मिनिमैक्स एल्गोरिथम ही है। एल्गोरिथ्म का सार इष्टतम चाल को खोजने के लिए है, इसके अलावा, स्कोर को किसी के प्रतिद्वंद्वी की चाल के अनुमानों के एक सेट के रूप में विकसित किया गया है। प्रक्रिया पुनरावर्ती है। प्रत्येक चरण में, हम अपने पाठ्यक्रम का आकलन करते हैं और दुश्मन के सर्वोत्तम पाठ्यक्रम का आकलन करते हैं। उदाहरण के लिए: हम 2 बिंदुओं पर अपनी चाल का मूल्यांकन करते हैं, 10 बिंदुओं पर प्रतिद्वंद्वी के जवाब, कुल = 2 - 10 = -8 - यह हमारी चाल का अनुमान है, फिर से विकल्प के पेड़ के नीचे अपना रास्ता बनाते हुए, हम गहराई N की स्थिति का मूल्यांकन करते हैं। हालांकि, यह पर्याप्त है सरल, लेकिन सभी विकल्पों की गणना करते हुए, और एक खाली क्षेत्र के लिए उनके तथ्यात्मक 42, व्यक्तिगत कंप्यूटर पर कार्य असंभव है (केवल सुपर कंप्यूटर पर दिखाई देता है)। सभी तरह की गणना करने में असमर्थता आपको स्थिति-गणना की स्थिति के उपयोग के लिए बाध्य करती है। मैं न्यूनतम प्रक्रिया देगा:

 Step game(TicTac *field, int deep, WHO it, TicTac t){ int i=0; float rait, koeff = 1 - Koeff[it]*deep; Step s, r; s.step = -1; s.rait = -1000.; if(deep > DEEPMAX){ s.rait = 0.; return s; } for(i=0; i<NSIZE_I*NSIZE_J; i++){ if( validstep(field, i) ){ field[i] = t; rait = c4getrait(field, t); if(rait >= WIN){ field[i] = EMPTY; s.rait = 10.*koeff; s.step = i; return s; } else if(!isstep(field)){ rait = 0.; } else { r = game(field, deep+1, it, (t==Tic)?Tac:Tic); rait-=r.rait; } if(rait > s.rait){ s.rait = rait; s.step = i; } field[i] = EMPTY; } } s.rait = s.rait*koeff; return s; }

प्रक्रिया चक्र में सभी पदों की गणना करती है

 for(i=0; i<NSIZE_I*NSIZE_J; i++){...

अगली चाल बनाओ

 field[i] = t;

एक अनुमान के लिए देख रहे हैं

 rait = c4getrait(field, t);

अगर हम जीत गए

 if(rait >= WIN){

, तो यह गहराई से देखने के लिए कोई मतलब नहीं है - नहीं, पुनरावृत्ति बंद हो जाती है, अगर कोई चाल नहीं बची है (ड्रा) - वापसी 0 (संभवतः इष्टतम नहीं), अन्यथा

 r = game(field, deep+1, it, (t==Tic)?Tac:Tic); rait-=r.rait;

हम अपने कदम के लिए दुश्मन की प्रतिक्रिया का मूल्यांकन करते हैं और रेटिंग की गणना करते हैं, फिर अधिकतम रेटिंग का चयन करें और स्थिति वापस करें

 if(rait > s.rait){ s.rait = rait; s.step = i; } field[i] = EMPTY;

परिणाम वापस करें

 s.rait = s.rait*koeff; return s;

।

एक सही मूल्यांकन के लिए, आपको गुणांक दर्ज करना होगा (सिद्धांत विशुद्ध रूप से मेरा है :)। यह इस तथ्य से जुड़ा है कि विभिन्न गहराई पर जीतना एक असमान अवधारणा है (और सामान्य रूप से एक आकलन), क्योंकि मूल्य अधिक है, खोज की गहराई कम है। स्पष्टीकरण: उदाहरण के लिए, चाल A के दौरान, आपको गहराई 5 पर नुकसान मिलता है, और चाल B के दौरान, गहराई 2 पर। यह स्पष्ट है कि 2 पहले 5 :) की तुलना में होगा, और इसलिए, इस स्थिति में, आपके लिए 5 अधिक स्थानांतरित करने योग्य है, यह लागू नहीं होगा। केवल जीत / हार, लेकिन यह भी केवल एक स्थिति का अनुमान है। इस संबंध में, सिद्धांत के अनुसार गुणांक बनाने के लिए आवश्यक है, गहरा, कम महत्व हम कदम से जुड़ते हैं। लेकिन, यहाँ कठिनाइयाँ बस शुरू हो जाती हैं :) यह आवश्यक है कि एल्गोरिथ्म सही ढंग से पदों को मापता है, विरोधाभास के बावजूद - गहराई से सोचता है, लेकिन रेटिंग को अधिक से अधिक समझना, गहराई जितनी अधिक होगी। जाहिर है, यहां कठोर गणित संभव है, लेकिन मेरे पास कोई विशेष प्रशिक्षण नहीं है। लेकिन यह संभव है और इतना स्पष्ट है: एक चक्र में गुणांक में क्रमिक परिवर्तन और लॉग में लिखने के साथ कार्यक्रमों के बीच खेल का संचालन करने के लिए। फिर, लॉग का उपयोग करके, आप सबसे अच्छे विकल्प पा सकते हैं और गुणांक लिख सकते हैं। खोज की गहराई 6 के लिए - मुझे 0.2 मिली। इसलिए, इस चरण के दौरान, मैं देख रहा हूं, हालांकि, इस प्रक्रिया में, एक और सुधार है कि विकल्पों की संख्या के आधार पर गहराई में भिन्नता है, यह स्पष्ट है कि इस खेल में विकल्पों की संख्या व्याप्त क्षेत्रों के अनुपात में घट जाती है ... अब एल्गोरिथ्म आसानी से औसत खिलाड़ी को बेहतर बनाता है: ) ऊपर दिए गए लिंक पर प्रोग्राम के साथ, यह हार जाता है अगर यह दूसरा हो जाता है, पहला - अधिकतम कठिनाई पर खींचता है। कार्यक्रम को डिबगिंग और ट्यूनिंग के साथ 2 दिनों के लिए लिखा गया था। आपका ध्यान देने के लिए धन्यवाद।

खेल के उदाहरण पर मिनीमैक्स एल्गोरिथ्म "लीजिए 4 (कनेक्ट 4)"

More articles: