وظيفة C++ الحد الأدنى

Question

لقد بحثت في Google وStackoverflow عن هذا السؤال، لكني ما زلت لا أفهم كيف تعمل وظيفة minimax.

لقد وجدت أن إدخال ويكيبيديا يحتوي على نسخة الكود الكاذب للوظيفة:

function integer minimax(node, depth)
    if node is a terminal node or depth <= 0:
        return the heuristic value of node
    α = -∞
    for child in node:                       # evaluation is identical for both players 
        α = max(α, -minimax(child, depth-1))
    return α

العديد من وظائف minimax الأخرى التي وجدتها مع Google هي في الأساس نفس الشيء؛أحاول تنفيذ ذلك في C++، وهذا ما توصلت إليه حتى الآن:

double miniMax(Board eval, int iterations)
{
    //I evaluate the board from both players' point of view and subtract the difference
    if(iterations == 0)
        return boardEval(eval, playerNumber) - boardEval(eval, opponentSide());

    /*Here, playerTurn tells the findPossibleMoves function whose turn it is;
    I mean, how do you generate a list of possible moves if you don't even know
    whose turn it's supposed to be? But the problem is, I don't see where I can
    get playerTurn from, as there are only 2 parameters in all the examples of
    minimax I've seen*/
    vector<int> moves = eval.findPossibleMoves(playerTurn);

    //I'm assuming -∞ in the wikipedia article means a very low number?
    int result = -999999999;

    //Now I run this loop to evaluate each possible move
    /*Also, the Lua example in the wiki article has
      alpha = node.player==1 and math.max(alpha,score) or math.min(alpha,score)
      Is alpha a boolean there?!*/
    for(int i = 0; i * 2 < moves.size(); i++)
    {
        //I make a copy of the board...
        Board temp = eval;

        /*and make the next possible move... once again playerTurn crops up, and I
        don't know where I can get that variable from*/
        temp.putPiece(moves[i * 2], moves[i * 2 + 1], playerTurn);

        /*So do I create a function max that returns the bigger of two doubles?*/
        result = max(result, -miniMax(temp, iterations - 1));
    }

    return result;
    /*So now I've returned the maximum score from all possible moves within a certain
    # of moves; so how do I know which move to make? I have the score; how do I know
    which sequence of moves that score belongs to?*/
}

كما ترون، أنا في حيرة من أمري بشأن وظيفة الحد الأدنى هذه.من فضلك على الأقل أعطني بعض التلميحات لمساعدتي في هذا الأمر.

شكرًا!:)

Answer 1

تلك العينة من ويكيبيديا تفعل negamax مع تشذيب ألفا/بيتا.

قد يتم مساعدتك من خلال تسمية التسمية بشكل مستقيم:

• الأساس هو الحد الأدنى ، وسيشمل التنفيذ الحرفي طريقتين يتناوبون (عودية متبادلة) ، 1 لكل جانب.

• يحول المبرمجون الكسولون هذا إلى negamax ، طريقة واحدة مع وضع استراتيجي - المشغل أو العامل.

• يتتبع تقليم Alpha/Beta نافذة من أفضل التحركات (على أعماق متعددة) للكشف عن الفروع الميتة.

لك playerTurn يستخدم لتحديد من هو بدوره. في Negamax ، يمكنك استخلاص هذا من العمق (التكرارات) كونه غريبًا أو حتى. ولكن سيكون من الأسهل استخدام 2 معلمتين (mycolor ، ألوان أخرى) وتبديلها في كل مستوى.

Answer 2

يجب أن تتذكر وظيفة Minimax () أفضل خطوة وجدت حتى الآن. لذا بدلاً من هذا الرمز:

  /*So do I create a function max that returns the bigger of two doubles?*/
  result = max(result, -miniMax(temp, iterations - 1));

يجب أن تفعل شيئًا كهذا:

  /*So do I create a function max that returns the bigger of two doubles?*/
  double score = -miniMax(temp, iterations - 1);
  if (score > result)
  {
     result = score;
     bestMove = i;
  }

بالطبع ، تحتاج إلى متغير "BestMove" وطريقة لإرجاع أفضل خطوة موجودة إلى المتصل.

Answer 3

أضف ال playerTurn متغير كحجة miniMax, ، و اتصل miniMax الذي تحرك اللاعب الحالي في البداية ومتكررة.

ايضا، opponentSide يجب أن تكون وظيفة playerTurn.

Answer 4

المكان الجيد للبدء بالبحث عن شجرة اللعبة هو ويكي برمجة الشطرنج.بالنسبة لسؤالك حول النقل:أعتقد أنه من الأكثر شيوعًا أن يكون لديك وظيفتان كحد أقصى.الفرق بين الدالتين الأقصىتين هو أن إحداهما تُرجع النتيجة فقط والأخرى تُرجع النتيجة وأفضل حركة.سيكون أمر الاتصال المتكرر كما يلي:

maxWithBestMoveReturn(...) --> min(...) --> max(...) --> min(...)

هناك بعض الأبحاث الجيدة التي تحتوي على كود زائف لخوارزمية Alpha Beta:

• تا مارسلاند - الشطرنج الكمبيوتر والبحث
• J Schaeffer - الألعاب التي تلعبها أجهزة الكمبيوتر (والأشخاص).

بالنسبة لسؤالك في التعليق: و math.max(alpha,score) أو math.min(alpha,score) هل ألفا منطقية هناك؟!

لا يوجد ألفا عبارة عن نافذة مرتبطة بخوارزمية ألفا بيتا.يتم تحديث قيمة ألفا بقيمة جديدة.نظرًا لأنه يتم تبديل ألفا وبيتا مع الاستدعاء العودي لوظيفة negamax، يشير متغير ألفا إلى متغير بيتا في الاستدعاء العودي التالي.

ملاحظة واحدة لمتغير playerTurn:لا تحتاج خوارزمية minimax أو alpha-beta إلى هذه المعلومات.لذا أود أن أقدم المعلومات - من هو التالي - إلى هيكل مجلس الإدارة.تحصل الوظيفتان findPossibleMoves وboardEval على جميع المعلومات التي تحتاجها من هيكل اللوحة.

ملاحظة واحدة لحالة الاستراحة العودية:إذا فهمت الكود الخاص بك بشكل صحيح، فلن يكون لديك سوى الكود الذي به iterations == o.أعتقد أن هذا يعني أن الخوارزمية وصلت إلى العمق المطلوب.ولكن ماذا لو لم تكن هناك تحركات محتملة قبل أن تصل الخوارزمية إلى هذا العمق.ربما عليك أن تكتب التالي:

vector<int> moves = findPossibleMoves(...);
if (!moves.size())
    return boardEval(...);

Answer 5

في الرمز الكاذب الخاص بك ، يجب أن يحتوي متغير العقدة على جميع المعلومات حول موضع اللوحة الحالي (أو أي شيء آخر). ستتضمن هذه المعلومات من هو دوره هو التحرك.