Tic Tac Toe على Arduino مع AI (خوارزمية Minimax): 3 خطوات

2024 مؤلف: John Day | [email protected]. آخر تعديل: 2024-01-30 07:41

في Instructable ، سأوضح لك كيفية إنشاء لعبة Tic Tac Toe باستخدام ذكاء اصطناعي باستخدام Arduino. يمكنك إما اللعب ضد Arduino أو مشاهدة Arduino يلعب ضد نفسه.

أنا أستخدم خوارزمية تسمى "خوارزمية minimax" ، والتي يمكن استخدامها ليس فقط لبناء ذكاء اصطناعي لـ Tic Tac Toe ، ولكن أيضًا لمجموعة متنوعة من الألعاب الأخرى مثل Four in a Row أو لعبة الداما أو حتى لعبة الشطرنج. ألعاب مثل الشطرنج معقدة للغاية وتتطلب إصدارات أكثر دقة من الخوارزمية. بالنسبة إلى لعبة Tic Tac Toe الخاصة بنا ، يمكننا استخدام أبسط نسخة من الخوارزمية ، والتي مع ذلك مثيرة للإعجاب. في الواقع ، الذكاء الاصطناعي جيد جدًا لدرجة أنه من المستحيل التغلب على Arduino!

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

الخطوة 1: البناء واللعب

لبناء لعبة Tic Tac Toe ، ستحتاج إلى المكونات التالية:

• اردوينو أونو
• 9 WS2812 RGB LEDs
• 9 أزرار ضغط
• بعض الكابلات الأسلاك والطائر

اربط المكونات كما هو موضح في رسم فريتزينج. ثم قم بتحميل الكود على Arduino الخاص بك.

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

يمكنك مشاهدة Arduino "think" من خلال فتح Serial Monitor. لكل خطوة محتملة ، تحسب الخوارزمية تصنيفًا يشير إلى ما إذا كانت هذه الخطوة ستؤدي إلى فوز (قيمة 10) أو خسارة (قيمة -10) لـ Arduino أو التعادل (القيمة 0).

يمكنك أيضًا مشاهدة Arduino وهو يلعب ضد نفسه بإلغاء التعليق على السطر "#define DEMO_MODE" في بداية الرسم التخطيطي. إذا قمت بتحميل الرسم المعدل ، فإن Arduino يقوم بالخطوة الأولى بشكل عشوائي ثم يستخدم خوارزمية minimax لتحديد أفضل حركة لكل لاعب في كل دور.

لاحظ أنه لا يمكنك الفوز على Arduino. ستنتهي كل مباراة بالتعادل أو تخسر ، إذا ارتكبت خطأ. هذا لأن الخوارزمية تختار دائمًا أفضل حركة ممكنة. كما تعلم ، فإن لعبة Tic Tac Toe ستنتهي دائمًا بالتعادل إذا لم يرتكب اللاعبان أي خطأ. في الوضع التجريبي ، تنتهي كل لعبة بالتعادل لأنه ، كما نعلم جميعًا ، لا ترتكب أجهزة الكمبيوتر أخطاء ؛-)

الخطوة 2: خوارزمية Minimax

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

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

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

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

الخطوة 3: استكشاف الأخطاء وإصلاحها والخطوات الأخرى

إذا ضغطت على زر وأضاء مؤشر LED مختلف عن ذلك المقابل للزر ، فمن المحتمل أن تكون قد اختلطت الأسلاك على المسامير A0-A2 أو 4-6 ، أو أنك قمت بتوصيل مصابيح LED بترتيب خاطئ.

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

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

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