समस्या
मिनिमैक्स वह तरीका है जिससे गेम खेलने वाले प्रोग्राम चाल चुनते हैं: मान लें कि दोनों खिलाड़ी पूरी तरह सही खेलते हैं, हर ख़त्म हुए गेम को स्कोर दें, और स्कोर को गेम ट्री में ऊपर ले जाएँ। जिस खिलाड़ी की बारी है, वह अपने लिए सबसे ऊँचे स्कोर वाला चाइल्ड चुनता है।
बोर्ड 9 अक्षरों की स्ट्रिंग है जो पंक्ति दर पंक्ति पढ़ी जाती है (इंडेक्स 0-8), जिसमें "X", "O" या ख़ाली सेल के लिए "." होता है। X हमेशा पहले चलता है, इसलिए जब दोनों के निशान बराबर हों तो X की बारी है, नहीं तो O की।
ख़त्म हुए गेम को उस खिलाड़ी की नज़र से स्कोर दें जिसकी बारी है: जीत पर +1, ड्रॉ पर 0, हार पर -1। वह ख़ाली सेल लौटाएँ जिसकी चाल का मिनिमैक्स स्कोर सबसे अच्छा हो; अगर कई बराबर अच्छे हों, तो सबसे छोटा इंडेक्स लौटाएँ।
best_move(board) लागू करें।
इनपुट
board: एक मान्य स्थिति जिसमें अभी तक कोई नहीं जीता और कम से कम एक सेल ख़ाली है।
आउटपुट
सबसे अच्छी चाल का इंडेक्स (0-8) लौटाएँ।
सीमाएँ
board में ठीक 9 अक्षर हैं, हर अक्षर X, O या . है
यह स्थिति असली गेम में आ सकती है, कोई नहीं जीता और कम से कम एक सेल ख़ाली है
उदाहरण
इनपुट:
board = "XX.OO...."
अपेक्षित आउटपुट:
expected = 2इनपुट:
std::string board = "XX.OO....";
अपेक्षित आउटपुट:
long long expected = 2;इनपुट:
string board = "XX.OO....";
अपेक्षित आउटपुट:
long expected = 2;व्याख्या
X और O दोनों के दो-दो निशान हैं, इसलिए X की बारी है। 2 पर खेलने से ऊपर की पंक्ति पूरी होती है और तुरंत जीत मिलती है (+1)।
इनपुट:
board = "X..OO...X"
अपेक्षित आउटपुट:
expected = 5इनपुट:
std::string board = "X..OO...X";
अपेक्षित आउटपुट:
long long expected = 5;इनपुट:
string board = "X..OO...X";
अपेक्षित आउटपुट:
long expected = 5;व्याख्या
X की बारी है। O बीच की पंक्ति को 5 पर पूरा करने की धमकी दे रहा है। कोई भी दूसरी चाल O को जिताती है (-1), जबकि 5 पर रोकने से ड्रॉ (0) होता है, इसलिए उत्तर 5 है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
X और O की counts से तय करें कि किसकी turn है, फिर हर legal move को recursively evaluate करें.
संकेत 2
Terminal boards को current player के perspective से score करें, और उस move को चुनें जो value को maximize करे.
संकेत 3
अगर multiple moves tie हों, तो earliest empty cell index रखें, और आगे के moves consider करने से पहले wins detect हों यह सुनिश्चित करें.
अपेक्षित जटिलता
समय O(9!), अतिरिक्त स्थान O(9)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।