सबसे अच्छा लौटें tictactoe

Question

के लिए मिनीमैक्स एल्गोरिदम में सबसे अच्छा लौटें मैंने आर्टिफिशियल इंटेलिजेंस पर रसेल नॉर्विग की पुस्तक में दिए गए टिक-टैक-टो के लिए मिनीमैक्स एल्गोरिदम को कोड करने का प्रयास किया है। इसमें सब कुछ था सिवाय इसके कि उपयोगकर्ता को सबसे अच्छा लौटने का तरीका। मैं सबसे अच्छा लौटने के लिए कड़ी मेहनत कर रहा हूं, लेकिन यह तय नहीं कर सकता कि सबसे अच्छा कब चुनना है। मदद करो, कोई भी?

moveT MiniMax(stateT state) 
{ 
    moveT bestMove; 

    max_move(state,bestMove); 

    return bestMove; 

} 

int max_move(stateT state,int & bestMove) 
{ 
    int v = -10000; 
    if(GameIsOver(state)) 
    { 
     return EvaluateStaticPosition(state); 

    } 

    vector<moveT> moveList; 
    GenerateMoveList(state, moveList); 
    int nMoves = moveList.size(); 

    for(int i = 0 ; i < nMoves ; i++) 
    { 
     moveT move = moveList[i]; 
     MakeMove(state, move); 

     int curValue = min_move(state,bestMove); 

      if(curValue > v) 
      { 
       v = curValue; 
       bestMove = move; 
      } 
     RetractMove(state, move); 

    } 

    return v; 

} 

int min_move(stateT state, int &bestMove) 
{ 
    int v = 10000; 
    if(GameIsOver(state)) 
    { 
     return EvaluateStaticPosition(state); 

    } 
    vector<moveT> moveList; 
    GenerateMoveList(state, moveList); 

    int nMoves = moveList.size(); 

    for(int i = 0 ; i < nMoves; i++) 
    { 
     moveT move = moveList[i]; 
     MakeMove(state, move); 

     int curValue = max_move(state,depth+1,bestMove); 

      if(curValue < v) 
      { 
       curValue = v; 
      } 
     RetractMove(state, move); 

    } 
    return v; 
} 

पीएस .: मिनमैक्स मूल्य खोजने के लिए अन्य छद्म कोड हैं। हालांकि, वे केवल टिक-टैक-टो पर केंद्रित हैं, मैं इसे अन्य खेलों में विस्तारित करने की कोशिश कर रहा हूं। धन्यवाद।

अद्यतन: पूरे कोड यहां पाया जा सकता: http://ideone.com/XPswCl

Answer 1

मिनीमैक्स के सबसे सरल संस्करण में, पहला खिलाड़ी अपने स्कोर को अधिकतम करना चाहता है, और दूसरा खिलाड़ी पहले खिलाड़ी के स्कोर को कम करना चाहता है। चूंकि पहले और दूसरे खिलाड़ी केवल पहले खिलाड़ी के स्कोर के बारे में परवाह करते हैं, EvaluateStaticPosition को यह मानना ​​चाहिए कि बोर्ड के पहले खिलाड़ी के लिए कितना अच्छा है। यह किसकी बारी है प्रासंगिक नहीं है।

int EvaluateStaticPosition(stateT state) 
{ 
     if(CheckForWin(state, FIRST_PLAYER)) 
     { 
       return WINNING_POSITION; 
     } 
     if(CheckForWin(state, Opponent(FIRST_PLAYER))) 
     { 
       return LOSING_POSITION; 
     } 
     return NEUTRAL_POSITION; 
} 

अब, जब आप पहले खिलाड़ी के लिए सबसे अच्छा कदम चाहते हैं, तो MaxMove पर कॉल करें। जब आप दूसरे खिलाड़ी के लिए सबसे अच्छा कदम चाहते हैं, तो मिनमोव को कॉल करें।

moveT MiniMax(stateT state) 
{ 
    moveT bestMove; 
    int i = 0; 
    if (state.whoseTurn == FIRST_PLAYER){ 
     i = MaxMove(state, bestMove); 
    } 
    else{ 
     i = MinMove(state,bestMove); 
    } 
    cout<<"i is "<<i<<endl; 
    return bestMove; 
} 

अंत में, आप MinMove और MaxMove के अंदर कुछ समस्याएं हैं। जब आप किसी एक में curRating असाइन करते हैं, तो आपको bestMove में MaxMove या MinMove पर दूसरे तर्क के रूप में पास नहीं करना चाहिए। इसके बाद प्रतिद्वंद्वी केbestMove में सबसे अच्छा स्थानांतरित होगा, जो समझ में नहीं आता है। इसके बजाय, opponentsBestMove ऑब्जेक्ट घोषित करें और दूसरी तर्क के रूप में पास करें। (आप वास्तव में ऑब्जेक्ट का उपयोग नहीं करेंगे या इसके बाद भी इसके मूल्य को देख नहीं पाएंगे, लेकिन यह ठीक है)। उस परिवर्तन के साथ, आप कभी भी bestMove पर MinMove के भीतर कुछ भी असाइन नहीं करते हैं, इसलिए आपको if(curRating < v) ब्लॉक के अंदर ऐसा करना चाहिए।

int MaxMove(stateT state, moveT &bestMove) 
{ 
     if(GameIsOver(state)) 
     { 
      return EvaluateStaticPosition(state); 
     } 
     vector<moveT> moveList; 
     GenerateMoveList(state, moveList); 
     int nMoves = moveList.size(); 
     int v = -1000; 
     for(int i = 0 ;i<nMoves; i++) 
     { 
       moveT move = moveList[i]; 
       MakeMove(state, move); 
       moveT opponentsBestMove; 
       int curRating = MinMove(state, opponentsBestMove); 
       if (curRating > v) 
       { 
         v = curRating; 
         bestMove = move; 
       } 
       RetractMove(state, move); 
     } 
     return v; 

} 
int MinMove(stateT state, moveT &bestMove) 
{ 
     if(GameIsOver(state)) 
     { 
       return EvaluateStaticPosition(state); 
     } 
     vector<moveT>moveList; 
     GenerateMoveList(state, moveList); 
     int nMoves = moveList.size(); 
     int v = 1000; 
     for(int i = 0 ; i<nMoves; i++) 
     { 
       moveT move = moveList[i]; 
       MakeMove(state , move); 
       moveT opponentsBestMove; 
       int curRating = MaxMove(state,opponentsBestMove); 
       if(curRating < v) 
       { 
         v = curRating; 
         bestMove = move; 
       } 
       RetractMove(state, move); 
     } 
     return v; 
} 

इस बिंदु पर आपको एक अजेय एआई होना चाहिए!

The final position looks like this: 

O | O | X 
---+---+--- 
X | X | O 
---+---+--- 
O | X | X 

Cat's game. 

---

एक वैकल्पिक पद्धति तथ्य टिक टीएसी को पैर की अंगुली एक शून्य राशि खेल है कि का लाभ लेता है। दूसरे शब्दों में, खेल के अंत में, खिलाड़ियों के स्कोर शून्य के बराबर होगा। दो खिलाड़ी गेम के लिए, इसका मतलब है कि एक खिलाड़ी का स्कोर हमेशा दूसरे खिलाड़ी का नकारात्मक होगा। यह हमारे लिए सुविधाजनक है, क्योंकि दूसरे खिलाड़ी के स्कोर को कम करने के बाद से किसी के अपने स्कोर को अधिकतम करने के समान होता है। तो एक खिलाड़ी के बजाय अपने स्कोर को अधिकतम करने और दूसरे खिलाड़ी के स्कोर को कम करने वाले एक खिलाड़ी के बजाय, हम दोनों खिलाड़ी अपने स्कोर को अधिकतम करने का प्रयास कर सकते हैं।

EvaluateStaticPosition अपने मूल रूप में वापस बदलें, ताकि यह वर्तमान प्लेयर के लिए बोर्ड राज्य कितना अच्छा है, इस पर आधारित स्कोर प्रदान करता है।

int EvaluateStaticPosition(stateT state) 
{ 
     if(CheckForWin(state, state.whoseTurn)) 
     { 
       return WINNING_POSITION; 
     } 
     if(CheckForWin(state, Opponent(state.whoseTurn))) 
     { 
       return LOSING_POSITION; 
     } 
     return NEUTRAL_POSITION; 
} 

MinMove हटाएं, क्योंकि हम केवल अधिकतम करने की परवाह करते हैं। MaxMove पुनर्लेखन करें ताकि यह उस कदम को चुन सके जो प्रतिद्वंद्वी को सबसे खराब संभव स्कोर देता है। सबसे अच्छे कदम के लिए स्कोर दूसरे खिलाड़ी के सबसे खराब स्कोर का नकारात्मक है।

int MaxMove(stateT state, moveT &bestMove) 
{ 
     if(GameIsOver(state)) 
     { 
       return EvaluateStaticPosition(state); 
     } 
     vector<moveT> moveList; 
     GenerateMoveList(state, moveList); 
     int nMoves = moveList.size(); 
     int v = -1000; 
     for(int i = 0 ;i<nMoves; i++) 
     { 
       moveT move = moveList[i]; 
       MakeMove(state, move); 
       moveT opponentsBestMove; 
       int curRating = -MaxMove(state, opponentsBestMove); 
       if (curRating > v) 
       { 
         v = curRating; 
         bestMove = move; 
       } 
       RetractMove(state, move); 
     } 
     return v; 

} 

MaxMove के बाद से दोनों खिलाड़ियों के लिए प्रयोग किया जाता है, हम अब MiniMax समारोह में खिलाड़ियों के बीच भेद करने के लिए की जरूरत है।

moveT MiniMax(stateT state) 
{ 
    moveT bestMove; 
    int i = 0; 
    i = MaxMove(state, bestMove); 
    cout<<"i is "<<i<<endl; 
    return bestMove; 
} 

Answer 2

खैर, यह MiniMax सही ढंग से, यह तुम्हारे लिए चुनता है सिर्फ एक प्रारंभिक अवस्था और गहराई से कॉल करने की तरह दिखता है। (जब तक कि राज्य के अनुसार पहला खिलाड़ी दूसरा खिलाड़ी नहीं है, तो आपको मिनीमैक्स में min_move को कॉल करना चाहिए।)

संपादित करें: हाँ, मैंने कुछ अनदेखा किया, सबसे अच्छा वर्तमान में अधिक समझ में नहीं आता है।

for(int i = 0 ; i < nMoves ; i++) 
{ 
    moveT move = moveList[i]; 
    MakeMove(state, move); 

    int new_value = min_move(state, depth+1); 
    if(new_value > v) 
    { 
     v=new_value; 
    } 
    RetractMove(state, move); 

} 

है कि आप आप के बारे में सोच सकते हैं क्या bestMove का मतलब है के बाद: max_move भीतर कार्यक्रम में आप इस तरह पाश बदलते हैं? मेरा विचार यह है कि आप टिक-टैक-टो के लिए चाल की "सर्वश्रेष्ठ संभव" श्रृंखला में से एक को खोजने में रुचि रखते हैं। इसके लिए आपको एक वेक्टर की आवश्यकता है या stack भी बेहतर है। लेकिन इसका मतलब है कि पिछले पैरामीटर के रूप में std::stack<int>* best_moves है।

स्टैक कार्यान्वयन के लिए, min_move में आप अगली चालें वापस करते हैं और यदि उनका मान सबसे अच्छा है, तो आप best_moves स्टैक के शीर्ष पर अपने move को दबाएंगे। निश्चित रूप से खेल के अंत में आप खाली ढेर वापस कर देते हैं। इसे ठीक से खींचने के लिए ओओपी दृष्टिकोण लेता है, जब मैं कुछ समय लेता हूं तो मैं इसे करूँगा।

मेरा सुझाव है तो आप सभी की जरूरत केवल सबसे अच्छा अगली चाल है, तो आप इस तरह की कुछ struct को min_move और max_moe की वापसी प्रकार परिवर्तित:

struct Value_move{ 
    int value; 
    moveT best_move; 
}; 

फिर max_move के नए कार्यान्वयन की तरह दिखता है निम्नलिखित:

const int MOVE_INVALID = -12345; 
const int MOVE_NOTHING = -12346; 

Value_move max_move(stateT state, int depth) 
{ 
    Value_move best; 
    best.value = -10000; best.best_move = MOVE_INVALID; 

    if(GameIsOver(state)) 
    { 
     best.value = EvaluateStaticPosition(state); 
     best.best_move = MOVE_NOTHING; 
     return best; 
    } 

    vector<moveT> moveList; 
    GenerateMoveList(state, moveList); 
    int nMoves = moveList.size(); 

    for(int i = 0 ; i < nMoves ; i++) 
    { 
     moveT move = moveList[i]; 
     MakeMove(state, move); 
     Value_move curr = min_move(state, depth+1); 
     if(curr.value > best.value) 
     { 
      best.value = curr.value; 
      best.best_move = move; 
     } 
     RetractMove(state, move); 

    } 

    return v; 

} 

आपको मिनीमैक्स फ़ंक्शन में लौटाई गई संरचना में सबसे अच्छा_मोव फ़ील्ड लेने की आवश्यकता है।

रिमर्क:
आपको स्वीकार करना होगा हालांकि यह कई पहलुओं में एक सी ++ प्रोग्राम जैसा नहीं बल्कि एक सी प्रोग्राम है। अन्यथा, CapitalCamelCase में सभी फ़ंक्शंस क्लास विधियां होनी चाहिए, आपको मूल्यों के बजाय (कॉन्स) रेफरी द्वारा राज्यों को पास करना चाहिए - लेकिन यह पूरा कोड केवल तभी समझ में आता है जब स्थिति वास्तव में टाइपपीफ के पीछे एक सूचक है।

Answer 3

आपका कोड सही मान पाता है लेकिन फिर उसी संदर्भ को पारित करके इसे ओवरराइट करता है।

int curValue = min_move(state,bestMove); 

हो जाना चाहिए

moveT nextMove; // No need to actually do anything with this value 
int curValue = min_move(state,nextMove); 

आप भी अपनी min_move समारोह में परिवर्तन की ही तरह बनाने की जरूरत है।

एनबी: min_move में आपका कोड max_move पर फ़ंक्शन के लिए परिभाषित किए गए अधिक तर्कों के साथ कॉल करता है।