अल्फा-बीटा ट्रांसपोजिशन टेबल के साथ आश्चर्यजनक,

Question

गहराई से गहराई से मैं अल्फा-बीटा न्यूनतम-अधिकतम आश्चर्यजनक तालिकाओं के साथ बढ़ाया जा रहा है। इस एल्गोरिथ्म के लिए

http://people.csail.mit.edu/plaat/mtdf.html#abmem

function AlphaBetaWithMemory(n : node_type; alpha , beta , d : integer) : integer; 
    if retrieve(n) == OK then /* Transposition table lookup */ 
     if n.lowerbound >= beta then return n.lowerbound; 
     if n.upperbound <= alpha then return n.upperbound; 
     alpha := max(alpha, n.lowerbound); 
     beta := min(beta, n.upperbound); 
    if d == 0 then g := evaluate(n); /* leaf node */ 
    else if n == MAXNODE then 
     g := -INFINITY; a := alpha; /* save original alpha value */ 
     c := firstchild(n); 
     while (g < beta) and (c != NOCHILD) do 
      g := max(g, AlphaBetaWithMemory(c, a, beta, d - 1)); 
      a := max(a, g); 
      c := nextbrother(c); 
    else /* n is a MINNODE */ 
     g := +INFINITY; b := beta; /* save original beta value */ 
     c := firstchild(n); 
     while (g > alpha) and (c != NOCHILD) do 
      g := min(g, AlphaBetaWithMemory(c, alpha, b, d - 1)); 
      b := min(b, g); 
      c := nextbrother(c); 

    if g <= alpha then 
     n.upperbound := g; 
     store n.upperbound; 
    if g > alpha and g < beta then 
     n.lowerbound := g; 
     n.upperbound := g; 
     store n.lowerbound, n.upperbound; 
    if g >= beta then 
     n.lowerbound := g; 
     store n.lowerbound; 
return g; 

तीन सवाल:

1. मैं belive कि मैं (पत्ता स्तर तक = दूरी) गहराई संग्रहीत करना चाहिए प्रत्येक बचाया स्थानांतरण के साथ मैं संदर्भ के रूप में इस स्यूडोकोड का उपयोग तालिका प्रविष्टि और केवल प्रवेश प्रविष्टि जब प्रविष्टि.depth> = currentDepth (= प्रविष्टि पत्तियों के स्तर से अधिक या बराबर होती है)। यह उपरोक्त छद्म कोड में नहीं दिखाया गया है और वहां पर चर्चा नहीं की गई है, मैं यह सुनिश्चित करना चाहता था कि मैं इसे सही ढंग से समझूं।

2. मैं प्रत्येक स्थिति के लिए इसे स्थानांतरित करने के लिए सबसे अच्छा स्थान स्टोर करना चाहता हूं और खोज स्टॉप के बाद सबसे अच्छा कदम निकालना चाहता हूं। शुद्ध न्यूनतम-अधिकतम में यह स्पष्ट है कि कौन सी चाल सबसे अच्छी है, लेकिन अल्फा-बीटा कटऑफ के साथ फिर से चलने पर कौन सी चाल सबसे अच्छी है? क्या मैं मान सकता हूं कि दी गई स्थिति के लिए सबसे अच्छा कदम सबसे अच्छा कदम है जब लूप समाप्त होता है (कट ऑफ या बिना)?

3. पुनरावर्तक गहन योजना में इस एल्गोरिदम को निष्पादित करते समय - क्या मुझे प्रत्येक गहराई में वृद्धि से पहले पारदर्शिता तालिका को साफ़ करना चाहिए? मुझे नहीं लगता, मैं चाहता हूं कि आप पिछले पुनरावृत्ति से संग्रहित स्थिति का उपयोग करें, लेकिन मुझे यकीन नहीं है कि जानकारी गहरी खोजों के लिए पर्याप्त है (यह तालिका प्रविष्टि गहराई की जांच करते समय होना चाहिए)?

Answer 1

1. आप सही हैं। entry.depth प्लस की संख्या को स्टोर करता है, पारदर्शिता तालिका प्रविष्टि में जानकारी आधारित होती है। तो आप केवल उन जानकारी का उपयोग कर सकते हैं जब entry.depth >= remaining_depth।

   तर्क यह है कि हम "सामान्य" खोज से कमजोर परिणाम का उपयोग नहीं करना चाहते हैं।

   entry.depth == remaining_depth 
   

   यह कुछ search instabilities से बचा जाता है:

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

2. स्टोर करने के लिए हमेशा एक बेहतरीन कदम नहीं है।

   जब खोज कम हो जाती है, तो "सर्वश्रेष्ठ कदम" नहीं होता है। एकमात्र चीज जो हम जानते हैं वह यह है कि alpha से बड़ा स्कोर बनाने के लिए कोई कदम पर्याप्त नहीं है। अनुमान लगाने का कोई तरीका नहीं है कि कौन सा कदम सबसे अच्छा है।

   तो आपको केवल निम्न सीमाओं (बीटा-कटऑफ यानी एक अस्वीकार स्थान) और सटीक स्कोर (पीवी नोड) के लिए हैश तालिका में एक चाल को स्टोर करना चाहिए।

3. नहीं, आपको नहीं करना चाहिए। पुनरावृत्ति गहराई के साथ एक ही स्थिति बार-बार पहुंच जाती है और पारदर्शिता तालिका खोज को तेज कर सकती है।

   आपको चाल के बीच पारदर्शिता तालिका को साफ़ करना चाहिए (या बेहतर, अतिरिक्त entry.age फ़ील्ड का उपयोग करें)।