जावा मिनिमैक्स अल्फा-बीटा प्रुनिंग रिकर्सन रिटर्न

Question

मैं जावा में चेकर्स गेम के लिए अल्फा-बीटा छंटनी के साथ मिनीमैक्स को कार्यान्वित करने की कोशिश कर रहा हूं। मेरा मिनीमैक्स एल्गोरिदम पूरी तरह से काम करता है। मेरा कोड अल्फा-बीटा कोड के साथ जगह पर चलता है। दुर्भाग्यवश, जब मैं मानक मिनीमैक्स एल्गोरिदम बनाम 1000 गेम खेलता हूं, तो अल्फा-बीटा एल्गोरिदम हमेशा 50 गेमों के पीछे आता है।

चूंकि अल्फा-बीटा छंटनी चाल की गुणवत्ता को कम नहीं करनी चाहिए, बस उन्हें प्राप्त करने में लगने वाला समय, कुछ गलत होना चाहिए। हालांकि, मैंने पेन और पेपर निकाला है और अनुमानित पत्ते नोड मानों को खींचा है और यह अनुमान लगाने के लिए मेरे एल्गोरिदम का उपयोग किया है कि यह सही सर्वोत्तम चाल की गणना करेगा या नहीं, और कोई तर्क त्रुटियां नहीं दिखाई देती हैं। मैंने इस वीडियो से पेड़ का उपयोग किया: Alpha-Beta Pruning मेरे एल्गोरिदम का पता लगाने के लिए। यह तर्कसंगत रूप से सभी विकल्पों को बनाना चाहिए, और इसलिए एक कार्यान्वयन कार्यान्वयन होना चाहिए।

मैंने कोड में प्रिंट स्टेटमेंट भी लगाए हैं (उन्हें अव्यवस्था को कम करने के लिए हटा दिया गया है), और मूल्यों को सही तरीके से वापस किया जा रहा है और ऐसा लगता है कि छंटनी होती है। मेरे सर्वोत्तम प्रयासों के बावजूद मैं यह पता लगाने में असमर्थ हूं कि तर्क त्रुटि कहां है। यह लागू करने में मेरा तीसरा अलग प्रयास है और उनमें से सभी को एक ही समस्या है।

मैं यहां पूरा कोड पोस्ट नहीं कर सकता, यह बहुत लंबा है, इसलिए मैंने त्रुटि के लिए प्रासंगिक विधियों को शामिल किया है। मैं निश्चित नहीं हूं, लेकिन मुझे संदेह है कि समस्या गैर-पुनरावर्ती चाल() विधि में हो सकती है, हालांकि मुझे इसमें एक तार्किक त्रुटि नहीं मिल रही है, इसलिए मैं बस इसके आसपास घूम रहा हूं, शायद चीजें बनाना एक कविता या कारण के बिना बेहतर से बदतर।

क्या लूप में रिकर्सिव कॉल से एकाधिक पूर्णांक मानों को पुनर्प्राप्त करने के लिए कोई चाल है? यह मेरे मिनीमैक्स और negamax कार्यान्वयन दोनों के साथ ठीक काम करता है, लेकिन अल्फा-बीटा छंटनी कुछ अजीब परिणाम उत्पन्न करने लगता है।

@Override 
public GameState move(GameState state) 
{ 
    int alpha = -INFINITY; 
    int beta = INFINITY; 
    int bestScore = -Integer.MAX_VALUE; 
    GameTreeNode gameTreeRoot = new GameTreeNode(state); 
    GameState bestMove = null; 
    for(GameTreeNode child: gameTreeRoot.getChildren()) 
    { 
     if(bestMove == null) 
     { 
      bestMove = child.getState(); 
     } 
     alpha = Math.max(alpha, miniMax(child, plyDepth - 1, alpha, beta)); 
     if(alpha > bestScore) 
     { 
      bestMove = child.getState(); 
      bestScore = alpha; 
     } 
    } 
    return bestMove; 
} 

private int miniMax(GameTreeNode currentNode, int depth, int alpha, int beta) 
{ 
    if(depth <= 0 || terminalNode(currentNode.getState())) 
    { 
     return getHeuristic(currentNode.getState()); 
    } 
    if(currentNode.getState().getCurrentPlayer().equals(selfColor)) 
    { 
     for(GameTreeNode child: currentNode.getChildren()) 
     { 
      alpha = Math.max(alpha, miniMax(child, depth - 1, alpha, beta)); 

      if(alpha >= beta) 
      { 
       return beta; 
      } 
     } 
     return alpha; 
    } 
    else 
    { 
     for(GameTreeNode child: currentNode.getChildren()) 
     { 
      beta = Math.min(beta, miniMax(child, depth - 1, alpha, beta)); 

      if(alpha >= beta) 
      { 
       return alpha; 
      } 
     } 
     return beta; 
    } 
} 
//Checks to see if the node is terminal 
private boolean terminalNode(GameState state) 
{ 
if(state.getStatus().equals(win) || state.getStatus().equals(lose) || state.getStatus().equals(draw)) 
    { 
     return true; 
    } 
    else 
    { 
     return false; 
    } 
} 

Answer 1

मैं तुम्हें कहा था कि आप समस्या का पता चला देखा लेकिन नहीं करनी चाहिए अल्पमहिष्ठ अल्फा बीटा छंटाई हो

if it is MAX's turn to move 
    for child in children 
    result = alphaBetaMinimax(child, alpha, beta) 
    if result > alpha 
     alpha = result 
     if node is root 
      bestMove = operator of child 
    if alpha >= beta 
     return alpha 
    return alpha 

if it is MIN's turn to move 
    for child in children 
    result = alphaBetaMinimax(child, alpha, beta) 
    if result < beta 
     beta = result 
     if node is root 
      bestMove = operator of child 
    if beta <= alpha 
     return beta 
    return beta 

आप ने लिखा है:

if alpha >= beta 
    return beta 
return alpha 

Answer 2

सिर्फ उत्तर देने के लिए अपने प्रश्न

क्या एकाधिक पूर्णांक v को पुनर्प्राप्त करने के लिए कोई चाल है रिकर्सिव से अलर्ट लूप में कॉल करता है?

हाँ, जावा में आपको किसी ऑब्जेक्ट को रिकर्सिव फ़ंक्शन कॉल में पास करने की आवश्यकता होगी, फिर उस ऑब्जेक्ट की सामग्री को संशोधित करें। फ़ंक्शन रिटर्न के बाद आप संशोधित मानों तक पहुंच पाएंगे।

ईजी।

class ToBeReturned { 
    int returnValue1; 
    int returnValue2; 
    int returnValue3; 
} 

Answer 3

जासूसों को आश्चर्यजनक परिणामों के लिए आपको किसी प्रकार के चाल आदेश को लागू करना चाहिए। शतरंज में यह आमतौर पर कैप्चर या चेक होता है। उन तरह की चालें मूल्यांकन को सबसे अधिक बदलती हैं और इसलिए उन्हें आश्चर्यजनक पर बहुत अधिक प्रभाव पड़ता है। चेकर्स में यह औपचारिक पत्थरों को ले जा सकता है या 8 वें रैंक पर आत्म पत्थरों को बढ़ावा दे सकता है (खेद है कि इस्तेमाल की जाने वाली शर्तों को नहीं जानते)।

Answer 4

16 मार्च, 2013 को, पूछा sage88:

वहाँ पाश के लिए एक में पुनरावर्ती कॉल से कई पूर्णांक मूल्यों उबरने के लिए एक चाल है? यह मेरे मिनीमैक्स और negamax कार्यान्वयन दोनों के साथ ठीक काम करता है, लेकिन अल्फा-बीटा छंटनी कुछ अजीब परिणाम उत्पन्न करने लगता है।

अल्फा बीटा प्रुनिंग में, ब्याज का एकमात्र आउटपुट मूल्य नोड का स्कोर है: एक न्यूनतम नोड में बीटा का अंतिम मान अपने माता-पिता अधिकतम नोड के अल्फा मान के लिए माना जाता है; इसी तरह, अधिकतम नोड में अल्फा का अंतिम मान अपने माता-पिता न्यूनतम नोड के बीटा मान के लिए माना जाता है। इसलिए:

आपके प्रश्न का उत्तर एल्गोरिदम स्वयं है, क्योंकि यह सबसे प्रासंगिक चाल है।

यह कहा गया है कि आपके कार्यान्वयन में दो त्रुटियां हैं: 1) एड्रियन ब्लैकबर्न ने मूल रूप से बताया कि यह गलत रूप से एक मिनी नोड से अल्फा लौटा रहा है और इसके विपरीत, इसकी सटीकता को कम करना; 2) यह वर्तमान नोड के मूल्य में माता-पिता अल्फा या बीटा पर समय से पहले छंटनी के अवसरों को छोड़ रहा है। इस संस्करण में वापसी मान ठीक करता है और अधिकतम छंटाई: एक मजेदार और दिलचस्प सवाल :)

अधिक मज़ा के लिए योगदान करने के लिए

private int miniMax(GameTreeNode currentNode, int depth, int alpha, int beta) { 
    if (depth <= 0 || terminalNode(currentNode.getState())) { 
     return getHeuristic(currentNode.getState()); 
    } 
    if (currentNode.getState().getCurrentPlayer().equals(selfColor)) { 
     int currentAlpha = -INFINITY; 
     for (GameTreeNode child : currentNode.getChildren()) { 
      currentAlpha = Math.max(currentAlpha, miniMax(child, depth - 1, alpha, beta)); 
      alpha = Math.max(alpha, currentAlpha); 
      if (alpha >= beta) { 
       return alpha; 
      } 
     } 
     return currentAlpha; 
    } 
    int currentBeta = INFINITY; 
    for (GameTreeNode child : currentNode.getChildren()) { 
     currentBeta = Math.min(currentBeta, miniMax(child, depth - 1, alpha, beta)); 
     beta = Math.min(beta, currentBeta); 
     if (beta <= alpha) { 
      return beta; 
     } 
    } 
    return currentBeta; 
} 

धन्यवाद, यहाँ move() विधि का एक स्पष्टीकरण, एक निरर्थक को हटाने है Math.max() करने के लिए कॉल:

@Override 
public GameState move(GameState state) { 
    GameState bestMove = null; 
    int bestScore = -INFINITY; 
    GameTreeNode gameTreeRoot = new GameTreeNode(state); 
    for (GameTreeNode child : gameTreeRoot.getChildren()) { 
     int alpha = miniMax(child, plyDepth - 1, bestScore, INFINITY); 
     if (alpha > bestScore || bestMove == null) { 
      bestMove = child.getState(); 
      bestScore = alpha; 
     } 
    } 
    return bestMove; 
} 

अंत में (यहां तक ​​कि अधिक मज़ा), केवल एक सुझाव, एक विधि का नाम बदलने terminalNode() की मंशा स्पष्ट करने के लिए, हालांकि मैं GameState इसलिए यह कोई पैरामीटर के साथ कहा जा सकता है में इस कदम होगा:

private boolean isTerminal(GameState state) { 
    //return Is.any(state.getStatus(), win, lose, draw); 
    return state.getStatus().equals(win) 
     || state.getStatus().equals(lose) 
     || state.getStatus().equals(draw); 
} 

Answer 5

आप पहले से ही अपनी समस्या तय कर चुके हैं, लेकिन आप जिस समस्या का सामना करना पड़ा वह काफी आम है। इसलिए जब भी आप एआई एजेंट के लिए एल्गोरिदम का हिस्सा बनाते हैं, तो आपको इसे ठीक से जांचना होगा। तो एक बार आपका मिनीमैक्स एल्गोरिदम सही है, तो आप केवल कई यादृच्छिक पेड़ उत्पन्न कर सकते हैं और जांच सकते हैं कि परिणाम समान हैं या नहीं। अजगर में उदाहरण के लिए आप इस तरह से यह कर सकते हैं:

class Node(): 
    def __init__(self, data, children): 
     self.data = data 
     self.children = children 

def generateTree(depth, branching): 
    total = branching**depth 
    values = [randint(-100, 100) for _ in xrange(total)] 
    level = [Node(values[i], []) for i in xrange(total)] 

    for _ in xrange(depth): 
     total /= branching 
     level = [Node(None, level[i * branching: (i+1) * branching]) for i in xrange(total)] 

    return level[0], values 

अब आप कई यादृच्छिक पेड़ के साथ एक पेड़ पैदा करते हैं और परिणामों की तुलना कर सकते हैं।

tree, values = generateTree(depth, branching) 
print negamax(tree, depth, 1) == alpha_beta_negamax(tree, depth, float('-inf'), float('inf'), 1) 

---

कि अल्पमहिष्ठ और अल्फा-बीटा वापसी बस सबसे अच्छा मूल्य मत भूलना, जबकि क्या आप एक असली खेल में रुचि रखते हैं एक चाल है। उन्हें इस तरह से संशोधित करने के लिए सीधा है कि वे एक कदम वापस कर सकते हैं, लेकिन यह तय करने के लिए डेवलपर पर निर्भर है कि कदम कैसे लौटाया जाता है। ऐसा इसलिए है क्योंकि कई चालें हो सकती हैं जो सर्वोत्तम समाधान की ओर ले जाती हैं (आप पहले को वापस कर सकते हैं, आखिरी एक या सबसे आम बात सभी चालों को ढूंढना और यादृच्छिक एक वापस करना है)।

आपके मामले में समस्या लौटाए गए मूल्यों की यादृच्छिकता के साथ थी, इसलिए परीक्षण के दौरान यादृच्छिकता को ठीक करने के लिए अच्छा दृष्टिकोण है।