अल्फा-बीटा स्थानांतरण

Question

मेरे पास अल्फा-बीटा छंटनी का मूल कार्यान्वयन है लेकिन मुझे नहीं पता कि चाल आदेश में सुधार कैसे किया जाए। मैंने पढ़ा है कि इसे एक उथली खोज, पुनरावृत्ति गहराई या संक्रमण तालिका में सबसे अच्छा बनाने के साथ किया जा सकता है।

कोई सुझाव है कि इस एल्गोरिदम में इन सुधारों में से किसी एक को कैसे कार्यान्वित किया जाए?

public double alphaBetaPruning(Board board, int depth, double alpha, double beta, int player) { 
    if (depth == 0) { 
     return board.evaluateBoard(); 
    } 

    Collection<Move> children = board.generatePossibleMoves(player); 
    if (player == 0) { 
     for (Move move : children) { 
      Board tempBoard = new Board(board); 
      tempBoard.makeMove(move); 
      int nextPlayer = next(player); 
      double result = alphaBetaPruning(tempBoard, depth - 1, alpha,beta,nextPlayer); 
      if ((result > alpha)) { 
       alpha = result; 
       if (depth == this.origDepth) { 
        this.bestMove = move; 
       } 
      } 
      if (alpha >= beta) { 
       break; 
      } 
     } 
     return alpha; 
    } else { 
     for (Move move : children) { 
      Board tempBoard = new Board(board); 
      tempBoard.makeMove(move); 
      int nextPlayer = next(player); 
      double result = alphaBetaPruning(tempBoard, depth - 1, alpha,beta,nextPlayer); 
      if ((result < beta)) { 
       beta = result; 
       if (depth == this.origDepth) { 
        this.bestMove = move; 
       } 
      } 
      if (beta <= alpha) { 
       break; 
      } 
     } 
     return beta; 
    } 
} 

public int next(int player) { 
    if (player == 0) { 
     return 4; 
    } else { 
     return 0; 
    } 
} 

Answer 1

• नोड उथले खोज के साथ पुन: क्रम तुच्छ है: रिकर्सिवली उन्हें की जाँच से पहले राज्य के प्रत्येक बच्चे के लिए अनुमानी मूल्य की गणना। फिर, इन राज्यों के मानों को क्रमबद्ध करें [अधिकतम vertex के लिए अवरोही, और न्यूनतम vertex के लिए आरोही], और क्रमबद्ध रूप से क्रमबद्ध सूची पर एल्गोरिदम का आह्वान करें। विचार यह है कि - यदि उथले गहराई पर कोई राज्य अच्छा है, तो यह पर भी अच्छा होने की संभावना है और यदि यह सत्य है - तो आपको और अधिक प्रजनन मिलेगा।

  छंटाई [दोनों if और else खंड में] इस से पहले किया जाना चाहिए

  for (Move move : children) {

• चाल भंडारण भी तुच्छ है - कई राज्यों में दो बार गणना कर रहे हैं, जब आप किसी भी राज्य की गणना समाप्त , इसे की गहराई के साथ गणना करें! यह असंभव है!] HashMap में। सबसे पहले आप करते हैं जब आप एक कशेरुक पर गणना शुरू करते हैं - यह जांच कर लें कि यह पहले से ही गणना की गई है - और यदि यह है, तो कैश किए गए मान को वापस कर दिया गया है। के पीछे विचार यह है कि कई राज्य विभिन्न पथों से पहुंच योग्य हैं, इसलिए यह तरीका - आप अनावश्यक गणना को समाप्त कर सकते हैं।

  परिवर्तन विधि की पहली पंक्ति [if (cache.contains((new State(board,depth,player)) return cache.get(new State(board,depth,player)) जैसे कुछ] में किया जाना चाहिए [मुझे लालित्य और दक्षता की कमी के लिए क्षमा करें - बस यहां एक विचार समझाएं]।
  आपको प्रत्येक return कथन से पहले cache.put(...) भी जोड़ना चाहिए।

Answer 2

सबसे पहले किसी को अल्फा-बीटा प्रुनिंग एल्गोरिदम में चलने के आदेश के पीछे तर्क को समझना होगा। अल्फा-बीटा एक ही परिणाम को मिनीमैक्स के रूप में उत्पन्न करता है लेकिन कई मामलों में यह तेजी से कर सकता है क्योंकि यह अप्रासंगिक शाखाओं के माध्यम से नहीं खोजता है।

यह हमेशा तेज़ नहीं होता है, क्योंकि यह छेड़छाड़ की गारंटी नहीं देता है, अगर वास्तव में खराब स्थिति में यह बिल्कुल नहीं छूटेगा और बिल्कुल उसी पेड़ को मिनीमैक्स के रूप में खोजेगा और ए/बी मूल्यों की किताब के कारण धीमा हो जाएगा- ध्यान में रखते हुए। सबसे अच्छे मामले में (अधिकतम छंटनी) यह एक ही समय में एक पेड़ को 2 बार गहरी खोज करने की अनुमति देता है। एक यादृच्छिक पेड़ के लिए यह एक ही समय के लिए 4/3 गुना गहराई से खोज सकता है।

ले जाएँ आदेश तरीके के एक जोड़े में लागू किया जा सकता:

1. आप एक डोमेन विशेषज्ञ जो आप क्या चलता रहता है बेहतर हैं के सुझाव देता है। उदाहरण के लिए एक पॉन के शतरंज पदोन्नति में, कम मूल्य वाले टुकड़े वाले उच्च मूल्य वाले टुकड़ों को कैप्चर करना औसत अच्छी चाल पर है। चेकर्स में एक चाल में अधिक चेकर्स को मारना बेहतर होता है, फिर कम चेकर और रानी बनाने के लिए बेहतर होता है।तो
2. से पहले आपकी चाल पीढ़ी की फ़ंक्शन बेहतर चाल वापस लौटाती है, आपको यह समझ में आता है कि गहराई के 1 स्तर (आपकी उथली खोज/पुनरावृत्ति गहराई) पर स्थिति का मूल्यांकन करने से कितना अच्छा कदम है। आपने गहराई एन -1 पर मूल्यांकन की गणना की, चाल को क्रमबद्ध किया और फिर गहराई एन पर मूल्यांकन किया।

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