Branching Factor & नोड गणना
एक गेम ट्री एक प्रारंभिक स्थिति से संभावित चालों के प्रत्येक क्रम को मॉडल करता है। प्रत्येक नोड एक बोर्ड स्थिति का प्रतिनिधित्व करता है। प्रत्येक किनारा एक कानूनी चाल का प्रतिनिधित्व करता है। पेड़ की संरचना निर्धारित करती है कि खोज व्यावहारिक रहती है या नहीं।
मुख्य पैरामीटर
Branching factor b: एक सामान्य स्थिति पर उपलब्ध कानूनी चालों की संख्या।
Depth d: खोज में आगे की plies (आधी-चालें) की संख्या।
Depth d पर नोड गणना: b^d
सभी गहराई पर कुल नोड: 1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)
बड़े b और d के लिए, कुल ≈ b^d (पत्ती स्तर द्वारा प्रभुत्व)।
4×4×4 Tic-Tac-Toe
पूरा गेम ट्री: b ≈ 64 (कानूनी वर्ग), d = 64 (कुल चालें)। पूर्ण नोड गणना ≈ 64^64 ≈ 10^115। दृश्यमान ब्रह्मांड में लगभग 10^80 परमाणु हैं। बल-प्रयोग खोज भौतिक रूप से असंभव है।
ट्री आकार की गणना
शतरंज अधिक यथार्थवादी संख्या प्रदान करती है। औसत branching factor b ≈ 35। एक 6-ply खोज (प्रत्येक पक्ष 3 चालें) को लगभग 35^6 नोड की आवश्यकता है।
Alpha-Beta Pruning: घातांक को कम करना
Alpha-beta pruning ऐसे उप-वृक्षों को समाप्त करता है जो minimax परिणाम को प्रभावित नहीं कर सकते। मुख्य अंतर्दृष्टि: यदि आप पहले से जानते हैं कि एक शाखा मान V देती है, तो आप किसी भी भाई शाखा को छंट सकते हैं जिसका मान सिद्ध रूप से V से नीचे गिरता है (अधिकतमकरण खिलाड़ी के लिए) या V से ऊपर (न्यूनतमकरण खिलाड़ी के लिए)।
सर्वोत्तम-केस ज्यामिति
इष्टतम चाल क्रमानुदेश (सर्वश्रेष्ठ चालें पहले खोजी गईं) के तहत, alpha-beta प्रभावी branching factor को b से √b तक कम करता है। खोज गहराई समान नोड बजट के लिए प्रभावी रूप से दोगुनी हो जाती है:
पूर्ण खोज: b^d नोड
Alpha-beta सर्वोत्तम केस: b^(d/2) नोड
उदाहरण: b=35, d=6। पूर्ण: 35^6 ≈ 1.84 × 10^9। Alpha-beta: 35^3 = 42,875। कमी कारक: ~43,000।
व्यवहार में, चाल क्रमानुदेश अपूर्ण है। विशिष्ट कमी: b^(d×0.75) — समकक्ष branching factor ≈ b^0.75।
केंद्र-कोने द्वैत
हैमिंग 4×4×4 घन में एक ज्यामितीय द्वैत नोट करते हैं: 8 कोने स्थितियों को 8 केंद्र स्थितियों (आंतरिक 2×2×2 घन) में भेजने वाला एक व्युत्क्रम मौजूद है & इसके विपरीत, सभी 76 जीतने वाली पंक्तियों को संरक्षित करते हुए।
एक स्थिति के माध्यम से जीतने वाली पंक्तियों की गणना
4×4×4 घन में, स्थितियाँ इस बात में भिन्न होती हैं कि कितनी जीतने वाली पंक्तियाँ उनके माध्यम से गुजरती हैं:
कोने की स्थितियाँ: प्रत्येक 7 पंक्तियाँ (4 चेहरे के विकर्ण, 2 किनारे की पंक्तियाँ, 1 अंतरिक्ष विकर्ण)
किनारे-केंद्र स्थितियाँ: प्रत्येक 4 पंक्तियाँ
चेहरे-केंद्र स्थितियाँ: प्रत्येक 6 पंक्तियाँ
शरीर-केंद्र स्थितियाँ (आंतरिक 2×2×2): प्रत्येक 7 पंक्तियाँ
द्वैत कोनों (7 पंक्तियाँ) को शरीर-केंद्रों (7 पंक्तियाँ) से मानचित्र करता है। दोनों सेट 'गर्म स्थान' बनाते हैं।
गर्म स्थान ज्यामितीय रूप से क्यों महत्वपूर्ण हैं
एक खिलाड़ी जो अधिक उच्च-पंक्ति-गणना स्थितियों को नियंत्रित करता है, अधिक संभावित जीतने वाली पंक्तियों को नियंत्रित करता है। यह एक सीधी ज्यामितीय तर्क है: पंक्ति कवरेज अधिकतमकरण किसी भी खोज के बिना चाल चयन को निर्देशित करता है।
मूल्यांकन कार्य
प्रत्येक गेम-खेलने वाले प्रोग्राम को एक मूल्यांकन कार्य की आवश्यकता होती है: बोर्ड स्थितियों को संख्यात्मक मानों के लिए मानचित्र करने वाला एक कार्य (सकारात्मक = अधिकतमकरण खिलाड़ी के लिए अच्छा, नकारात्मक = न्यूनतमकरण खिलाड़ी के लिए अच्छा)। मूल्यांकन कार्य खोज ट्री के पत्तियों पर सीमा शर्त प्रदान करता है।
रैखिक मूल्यांकन कार्य
एक रैखिक मूल्यांकन कार्य स्थिति की प्रत्येक विशेषता को एक भार w_i निर्दिष्ट करता है f_i:
E(स्थिति) = w_1 × f_1 + w_2 × f_2 + ... + w_n × f_n
4×4×4 tic-tac-toe के लिए: विशेषताएँ नियंत्रित खुली पंक्तियाँ, उच्च-पंक्ति-गणना वर्गों में स्थितियाँ, खतरों में forks शामिल हो सकती हैं। शतरंज के लिए: सामग्री गणना, केंद्र नियंत्रण, राजा सुरक्षा, pawn संरचना।
यह विशेषता अंतरिक्ष में एक रैखिक कार्य है — ℝ^n में एक hyperplane। समान विशेषता मान वाली दो स्थितियाँ समान मूल्यांकन प्राप्त करती हैं अन्य सभी अंतरों की परवाह किए बिना। मूल्यांकन कार्य की ज्यामिति निर्धारित करती है कि प्रोग्राम क्या 'देखता' है।
Samuel का checker प्रोग्राम भार वेक्टर w को समायोजित करके रैखिक मूल्यांकन कार्यों के स्थान में gradient descent सुधार करता है।
ज्यामिति & औपचारिकरण की सीमा
गेम ट्री में एक स्वच्छ ज्यामितीय संरचना होती है: depth d पर घातांकीय वृद्धि, alpha-beta द्वारा b^(d/2) में पुनरावर्तनीय, उच्च-मान स्थितियों तक सीमित करके आगे पुनरावर्तनीय (गर्म स्थान प्रभावी b को कम करते हैं)। मूल्यांकन कार्य विशेषता अंतरिक्ष में एक hyperplane को परिभाषित करता है।
यह सब स्वच्छ, सटीक, औपचारिक रूप से पूर्ण है। यह गेम-खेलने की समस्या के केंद्र का वर्णन करता है — क्षेत्र जहाँ गणितीय संरचना स्पष्ट मार्गदर्शन प्रदान करती है।
सीमा — नियम-अनुप्रयोग से अन्वेषण में कब स्विच करें, स्थितिगत लाभ को सामरिक अवसर के लिए कब व्यापार करें, मूल्यांकन कार्य से परे उभरते हुए पैटर्न को कैसे पहचानें — इस औपचारिकरण का प्रतिरोध करता है। हैमिंग का निहित ज्ञान उस सीमा पर रहता है।
ज्यामिति आपको यह गणना करने देता है कि आप कितनी खोज का जोखिम उठा सकते हैं। यह आपको नहीं बताता कि क्या देखना है।