बोर्ड गेम "गो" एनपी पूरा है?

Question

बहुत सारे शतरंज एआई के आस-पास हैं, और स्पष्ट रूप से कुछ दुनिया के कुछ महानतम खिलाड़ियों को हरा करने के लिए पर्याप्त हैं।

मैंने सुना है कि बोर्ड गेम Go के लिए सफल एआई लिखने के लिए कई प्रयास किए गए हैं, लेकिन अब तक औसत शौकिया स्तर से परे कुछ भी नहीं माना गया है।

क्या यह हो सकता है कि गो में किसी भी समय पर इष्टतम कदम की गणितीय गणना की कार्य एक एनपी-पूर्ण समस्या है?

Answer 1

शतरंज और गो EXPTIME complete दोनों हैं। आईआईआरसी, गो में अधिक संभावित चाल हैं, इसलिए मुझे लगता है कि यह शतरंज की तुलना में उस जटिलता वर्ग का एक उच्च बहुमत है। विकिपीडिया में गो की जटिलता पर good article है।

Answer 2

यहां तक ​​कि अगर जाओ P में केवल है यह अभी भी O(n^m) तरह खराब कुछ जहां n स्थानों की संख्या है और m कुछ (बड़े) निश्चित संख्या है हो सकता है। यहां तक ​​कि P में भी गणना करने के लिए कुछ उचित नहीं है।

Answer 3

न तो शतरंज या गो एआई एक कदम पर निर्णय लेने से पहले सभी संभावनाओं का पूरी तरह से मूल्यांकन करते हैं।

शतरंज एआई खोज स्थान को कम करने के लिए विभिन्न हेरिस्टिक का उपयोग करते हैं, और यह मापने के लिए कि बोर्ड पर दी गई स्थिति को 'अच्छा' कैसे किया जाता है। यह संभावित बोर्ड पदों का मूल्यांकन करके 14-15 आगे बढ़ने और एक अच्छी स्थिति की ओर बढ़ने वाला पथ चुनकर पुनरावर्ती किया जा सकता है।

बोर्ड की स्थिति को मापने के तरीके में थोड़ा 'जादू' है, ताकि शीर्ष स्तर पर एआई आसानी से मूव ए> मूव बी जा सके, इसलिए चलो ए ले जाएं। लेकिन चूंकि सीमित संख्या में टुकड़े हैं और उनके पास मात्रात्मक मूल्य है 'पर्याप्त पर्याप्त' एल्गोरिदम लागू किया जा सकता है।

लेकिन यह प्रोग्राम में गो में दो संभावित बोर्ड स्थितियों का मूल्यांकन करने और ए> बी गणना करने के लिए बहुत कठिन हो गया है। उस महत्वपूर्ण टुकड़े के बिना बाकी एआई काम करने के लिए थोड़ा मुश्किल है।