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

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

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

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

جربه بنفسك في اللعبة التالية.

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

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

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

لفهم عملية التفكير في Minimax تمامًا ، دعنا ننفذها في الشفرة ونراها في القسمين التاليين.

الحد الأدنى في القانون

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

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

الشكل 2 عينة من حالة اللعبة

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

var origBoard = ["O"، 1، "X"، "X"، 4، "X"، 6، "O"، "O"]؛

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

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

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

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

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

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

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

أخيرًا ، يعيد Minimax تعيين newBoard إلى ما كان عليه من قبل ويدفع كائن النقل إلى صفيف التحركات.

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

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

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

هذا هو الحال بالنسبة لوظيفة minimax. :) يمكنك العثور على الخوارزمية أعلاه على جيثب و codepen. العب مع لوحات مختلفة وتحقق من النتائج في وحدة التحكم.

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

الحد الأدنى في العمل

باستخدام الشكل التالي ، دعونا نتبع مكالمات دالة الخوارزمية (FC) واحدة تلو الأخرى.

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

الشكل 3 الشكل 3. Minimax وظيفة الدعوة عن طريق استدعاء وظيفة

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

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

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

نظرًا لأن أف سي الثانية أدرجت نقطتين فارغتين ، فإن Minimax يغير newBoard من خلال وضع huPlayer في النقطة الفارغة الثانية. ثم ، يطلق على نفسه مع لوحة جديدة و aiPlayer.

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

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

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

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

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

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

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

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

9. بعد ذلك ، تقوم الخوارزمية بإعداد قائمة بالبقع الفارغة ، وتجد فوزًا لـ aiPlayer بعد التحقق من حالات الجهاز الطرفي. لذلك ، تقوم بإرجاع كائن بخصائص النقاط وقيمة +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 وقم بتحسينها.

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

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