كيفية جعل لعبة Tic Tac Toe الخاصة بك لا تقبل المنافسة باستخدام خوارزمية minimax

لقد كافحت لساعات أثناء التمرير عبر البرامج التعليمية ومشاهدة مقاطع الفيديو وضرب رأسي على المكتب في محاولة لبناء لعبة Tic Tac Toe لا تقبل المنافسة مع ذكاء اصطناعي موثوق. لذا إذا كنت تقوم برحلة مماثلة ، أود أن أقدم لكم خوارزمية Minimax.

مثل لاعب الشطرنج المحترف ، ترى هذه الخوارزمية خطوات قليلة للأمام وتضع نفسها في مكان خصمها. يستمر في اللعب إلى الأمام حتى يصل إلى ترتيب طرفي للوحة ( الحالة النهائية ) مما يؤدي إلى التعادل أو الفوز أو الخسارة. بمجرد الوصول إلى حالة نهائية ، سيخصص الذكاء الاصطناعي درجة إيجابية عشوائية (+10) للفوز ، أو درجة سلبية (-10) للخسارة ، أو درجة محايدة (0) للتعادل.

في الوقت نفسه ، تقوم الخوارزمية بتقييم الحركات التي تؤدي إلى حالة طرفية بناءً على دور اللاعبين. سيختار الحركة بأقصى درجة عندما يحين دور الذكاء الاصطناعي ويختار الحركة بأقل درجة عندما يحين دور اللاعب البشري. باستخدام هذه الإستراتيجية ، يتجنب Minimax الخسارة أمام اللاعب البشري.

جربها بنفسك في اللعبة التالية ويفضل باستخدام متصفح Chrom.

يمكن تعريف خوارزمية Minimax بشكل أفضل على أنها دالة تكرارية تقوم بالأشياء التالية:

  1. إرجاع قيمة إذا تم العثور على حالة طرفية (+10 ، 0 ، -10)
  2. تصفح الأماكن المتاحة على السبورة
  3. استدعاء وظيفة minimax في كل مكان متاح (العودية)
  4. تقييم إرجاع القيم من استدعاءات الوظائف
  5. وإرجاع أفضل قيمة

إذا كنت جديدًا على مفهوم العودية ، فإنني أوصي بمشاهدة هذا الفيديو من CS50 من Harvard.

لفهم عملية التفكير الخاصة بـ Minimax تمامًا ، دعنا ننفذها في التعليمات البرمجية ونراها أثناء العمل في القسمين التاليين.

مينيماكس في كود

في هذا البرنامج التعليمي ، ستعمل على وضع شبه نهائي للعبة كما هو موضح في الشكل 2 أدناه. نظرًا لأن minimax يقيِّم كل حالة للعبة (مئات الآلاف) ، فإن حالة شبه النهاية تسمح لك بمتابعة مكالمات minimax المتكررة بسهولة (9).

بالنسبة للشكل التالي ، افترض أن الذكاء الاصطناعي هو X واللاعب البشري هو O.

للعمل مع لوحة Ti Tac Toe بشكل أسهل ، يجب أن تحددها كمصفوفة تحتوي على 9 عناصر. كل عنصر سيكون له فهرسه كقيمة. سيكون هذا مفيدًا لاحقًا. نظرًا لأن اللوحة أعلاه مليئة بالفعل ببعض حركات X و Y ، فلنقم بتعريف اللوحة بحركات X و Y الموجودة بالفعل ( لوحة OrigBoard ).

var origBoard = ["O",1,"X","X",4,"X",6,"O","O"];

ثم أعلن عن متغيري aiPlayer و huPlayer واضبطهما على "X" و "O" على التوالي .

بالإضافة إلى ذلك ، تحتاج إلى وظيفة تبحث عن التوليفات الفائزة وتعود صحيحًا إذا وجدت واحدة ، ووظيفة تسرد فهارس الأماكن المتاحة في اللوحة.

/* the original board O | | X --------- X | | X --------- | O | O */ var origBoard = [“O”,1 ,”X”,”X”,4 ,”X”, 6 ,”O”,”O”]; // human var huPlayer = “O”; // ai var aiPlayer = “X”; // returns list of the indexes of empty spots on the board function emptyIndexies(board){ return board.filter(s => s != "O" && s != "X"); } // winning combinations using the board indexies function winning(board, player){ if ( (board[0] == player && board[1] == player && board[2] == player) || (board[3] == player && board[4] == player && board[5] == player) || (board[6] == player && board[7] == player && board[8] == player) || (board[0] == player && board[3] == player && board[6] == player) || (board[1] == player && board[4] == player && board[7] == player) || (board[2] == player && board[5] == player && board[8] == player) || (board[0] == player && board[4] == player && board[8] == player) || (board[2] == player && board[4] == player && board[6] == player) ) { return true; } else { return false; } }

الآن دعنا نتعمق في الأجزاء الجيدة من خلال تحديد وظيفة Minimax مع وسيطتين newBoard و player . بعد ذلك ، تحتاج إلى العثور على فهارس الأماكن المتاحة في اللوحة وتعيينها على متغير يسمى availSpots .

// the main minimax function function minimax(newBoard, player){ //available spots var availSpots = emptyIndexies(newBoard);

تحتاج أيضًا إلى التحقق من الحالات الطرفية وإرجاع القيمة وفقًا لذلك. إذا ربح O ، يجب أن تعود -10 ، إذا فاز X ، يجب أن تعود +10. بالإضافة إلى ذلك ، إذا كان طول مصفوفة النقاط المتاحة يساوي صفرًا ، فهذا يعني أنه لا توجد مساحة أخرى للعب ، وقد أدت اللعبة إلى التعادل ، ويجب عليك إرجاع صفر.

 // checks for the terminal states such as win, lose, and tie //and returning a value accordingly if (winning(newBoard, huPlayer)){ return {score:-10}; } else if (winning(newBoard, aiPlayer)){ return {score:10}; } else if (availSpots.length === 0){ return {score:0}; }

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

بعد ذلك ، قم بتعيين رقم الفهرس للبقعة الفارغة التي تم تخزينها كرقم في لوحة OrigBoard إلى خاصية الفهرس الخاصة بكائن النقل . وفي وقت لاحق، تعيين بقعة فارغة على newboard إلى اللاعب الحالي واستدعاء مينيماكس وظيفة مع لاعب آخر وغيرت حديثا newboard . بعد ذلك ، يجب عليك تخزين الكائن الناتج عن استدعاء دالة minimax الذي يتضمن خاصية نقاط إلى خاصية النتيجة لكائن النقل .

إذا لم تعثر وظيفة minimax على حالة طرفية ، فإنها تستمر في الانتقال بشكل متكرر إلى مستوى أعمق في اللعبة. يحدث هذا التكرار حتى يصل إلى حالة نهائية ويعيد النتيجة بمستوى واحد لأعلى.

وأخيرا، مينيماكس يعيد newBoard إلى ما كانت عليه من قبل، ويدفع الخطوة الكائن إلى تحركات مجموعة.

// an array to collect all the objects var moves = []; // loop through available spots for (var i = 0; i < availSpots.length; i++){ //create an object for each and store the index of that spot var move = {}; move.index = newBoard[availSpots[i]]; // set the empty spot to the current player newBoard[availSpots[i]] = player; /*collect the score resulted from calling minimax on the opponent of the current player*/ if (player == aiPlayer){ var result = minimax(newBoard, huPlayer); move.score = result.score; } else{ var result = minimax(newBoard, aiPlayer); move.score = result.score; } // reset the spot to empty newBoard[availSpots[i]] = move.index; // push the object to the array moves.push(move); }

بعد ذلك ، تحتاج خوارزمية minimax إلى تقييم أفضل حركة في مجموعة التحركات . يجب أن تختار التحرك وفقا لأعلى درجة عندما تلعب منظمة العفو الدولية و التحرك مع أقل عدد من النقاط عندما يلعب البشرية. لذلك، إذا كان لاعب هو aiPlayer ، فإنه يحدد متغير يسمى شهرية لعدد والحلقات منخفضة للغاية من خلال تحركات مجموعة، إذا تحرك له أعلى درجة من شهرية ، ومخازن الخوارزمية التي تحرك . في حالة وجود حركات بنفس الدرجة ، سيتم تخزين الحركة الأولى فقط.

تحدث نفس عملية التقييم عندما يكون اللاعب هو huPlayer ، ولكن هذه المرة سيتم تعيين bestScore على رقم مرتفع ويبحث Minimax عن حركة بأقل درجة للتخزين.

في النهاية ، يقوم Minimax بإرجاع الكائن المخزن في bestMove .

// if it is the computer's turn loop over the moves and choose the move with the highest score var bestMove; if(player === aiPlayer){ var bestScore = -10000; for(var i = 0; i  bestScore){ bestScore = moves[i].score; bestMove = i; } } }else{ // else loop over the moves and choose the move with the lowest score var bestScore = 10000; for(var i = 0; i < moves.length; i++){ if(moves[i].score < bestScore){ bestScore = moves[i].score; bestMove = i; } } } // return the chosen move (object) from the moves array return moves[bestMove]; }
هذا كل شيء لوظيفة minimax. :) يمكنك العثور على الخوارزمية أعلاه على github و codepen. العب بألواح مختلفة وتحقق من النتائج في وحدة التحكم.

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

Minimax في العمل

باستخدام الشكل التالي ، دعنا نتبع استدعاءات وظائف الخوارزمية ( FC ) واحدًا تلو الآخر.

ملاحظة: في الشكل 3 ، تمثل الأرقام الكبيرة كل استدعاء دالة وتشير المستويات إلى عدد الخطوات التي تسبق اللعبة التي تلعبها الخوارزمية.

1. يتم تغذية OrigBoard و aiPlayer للخوارزمية. تقوم الخوارزمية بعمل قائمة بثلاث نقاط فارغة تجدها ، وتتحقق من الحالات الطرفية ، وتتكرر عبر كل بقعة فارغة بدءًا من النقطة الأولى. بعد ذلك ، يقوم بتغيير اللوحة الجديدة عن طريق وضع aiPlayer في أول بقعة فارغة.بعد ذلك،تستدعي نفسها بـ newBoard و huPlayer وتنتظر FC لإرجاع قيمة.

2. بينما لا يزال أول FC قيد التشغيل ، يبدأ الثاني بعمل قائمة من النقطتين الفارغتين اللتين يعثر عليهما ، والتحقق من الحالات الطرفية ، والحلقات عبر النقطة الفارغة بدءًا من الأولى. بعد ذلك ، يغير اللوحة الجديدة عن طريق وضع huPlayer في أول بقعة فارغة.بعد ذلكتستدعي نفسها بـ newBoard و aiPlayer وتنتظر FC لإرجاع قيمة.

3. أخيرًا ، تقوم الخوارزمية بإعداد قائمة بالمناطق الفارغة ، وتجد فوزًا للاعب البشري بعد التحقق من الحالات النهائية. لذلك ، تقوم بإرجاع كائن بخاصية درجة وقيمة -10.

نظرًا لأن FC الثانية أدرجت نقطتين فارغتين ، قام Minimax بتغيير اللوحة الجديدة عن طريق وضع huPlayer في المكان الفارغ الثاني. بعد ذلك ، تستدعي نفسها باللوحة الجديدة و aiPlayer .

4. تقوم الخوارزمية بعمل قائمة بالمناطق الفارغة ، وتجد فوزًا للاعب البشري بعد التحقق من الحالات النهائية. لذلك ، تقوم بإرجاع كائن بخاصية درجة وقيمة -10.

في FC الثاني ، تجمع الخوارزمية القيم القادمة من المستويات الأدنى (3 و 4 FC). نظرًا لأن دور huPlayer أدى إلى القيمتين ، فإن الخوارزمية تختار أدنى القيمتين. نظرًا لأن كلا القيمتين متشابهتين ، فإنه يختار القيمة الأولى ويعيدها إلى أول FC. في هذه المرحلة ، قام فريق FC الأول بتقييم درجة تحريك aiPlayer في أول بقعة فارغة. بعد ذلك ، يقوم بتغيير اللوحة الجديدة بوضع aiPlayer في المكان الفارغ الثاني. بعد ذلك ، تستدعي نفسها باللوحة الجديدة و huPlayer .

5. في المركز الخامس ، تقوم الخوارزمية بعمل قائمة بالمناطق الفارغة ، وتجد فوزًا للاعب البشري بعد التحقق من الحالات النهائية. لذلك ، تقوم بإرجاع كائن بخاصية درجة وقيمة +10.

بعد ذلك ، يتحرك أول FC عن طريق تغيير اللوحة الجديدة ووضع aiPlayer في المكان الفارغ الثالث. بعد ذلك ، تستدعي نفسها باللوحة الجديدة و huPlayer .

6. يبدأ المركز السادس بعمل قائمة من نقطتين فارغتين يعثر عليهما ، ويتحقق من الحالات النهائية ، ويتنقل عبر النقطتين الفارغتين بدءًا من الأولى. بعد ذلك ، يغير اللوحة الجديدة عن طريق وضع huPlayer في أول بقعة فارغة.بعد ذلك،it calls itself with newBoard and the aiPlayer and waits for the FC to return a score.

7. Now the algorithm is two level deep into the recursion. It makes a list of the one empty spot it finds, checks for terminal states, and changes the newBoard by placing the aiPlayer in the empty spot.After that,it calls itself with newBoard and the huPlayer and waits for the FC to return a score so it can evaluate it.

8. On the 8th FC,تقوم الخوارزمية بعمل قائمة فارغة من النقاط الفارغة ، وتجد فوزًا لـ aiPlayer بعد التحقق من الحالات الطرفية. لذلك ، تقوم بإرجاع كائن بخاصية نقاط وقيمة +10 مستوى واحد لأعلى (7 FC).

تلقى المركز السابع قيمة إيجابية واحدة فقط من المستويات الأدنى (8 FC). نظرًا لأن دور aiPlayer أدى إلى تلك القيمة ، فإن الخوارزمية تحتاج إلى إرجاع أعلى قيمة تلقتها من المستويات الأدنى. لذلك ، تُرجع قيمتها الموجبة الوحيدة (+10) مستوى واحد لأعلى (السادس FC). منذ أن أدرج الاتحاد السادس مكانين فارغين ، قام Minimax بتغيير اللوحة الجديدة بوضع huPlayer في المكان الفارغ الثاني. ثم يتصل باللوحة الجديدة و aiPlayer .

9. Next, the algorithm makes a list of the empty spots, and finds a win for the aiPlayer after checking for terminal states. Therefore, it returns an object with score properties and value of +10.

في هذه المرحلة ، يتعين على فريق 6 FC الاختيار بين النتيجة (+10) التي تم إرسالها من FC 7 (تم إرجاعها في الأصل من 8 FC) والنتيجة (-10) التي تم إرجاعها من FC 9. نظرًا لأن دور huPlayer أدى إلى هاتين القيمتين المرتجعتين ، فإن الخوارزمية تعثر على الحد الأدنى من النقاط (-10) وتعيده لأعلى ككائن يحتوي على خصائص النقاط والفهرس. أخيرًا ، تم تقييم جميع الفروع الثلاثة للـ FC الأول (-10 ، +10 ، -10). ولكن نظرًا لأن دور aiPlayer أدى إلى هذه القيم ، فإن الخوارزمية تُرجع كائنًا يحتوي على أعلى درجة (+10) وفهرسها (4).

في السيناريو أعلاه ، استنتج Minimax أن تحريك X إلى منتصف اللوحة يؤدي إلى أفضل نتيجة. :)

النهاية!

الآن يجب أن تكون قادرًا على فهم المنطق وراء خوارزمية Minimax. باستخدام هذا المنطق ، حاول تنفيذ خوارزمية Minimax بنفسك أو ابحث عن العينة أعلاهgithub أو codepen وتحسينه.

شكرا للقراءة! إذا أحببت هذه القصة ، فلا تنس مشاركتها على وسائل التواصل الاجتماعي.

شكر خاص لتوبا يلماز وريك ماكجافين وجويد أسكيروف لمراجعة هذا المقال.