الدروس ولعبة التعلّم

الذكاء الاصطناعي في الألعاب: minimax وما بعده

Teach a Raspberry Pi to play: perfect tic-tac-toe with minimax, then a Connect Four opponent built on alpha-beta, evaluation, a clock and random games.

الدورة

الذكاء الاصطناعي في الألعاب: minimax وما بعده هو دورة برمجة متقدمة من سبعة دروس، جميعها بلغة Python على لوحة Raspberry Pi 4. تُرسم اللوحات كنص على الشاشة التسلسلية وتُكتب النقلات يدويًا، ويتم التحقق من كل خطوة بما يطبعه الـ Pi أو أي مصباح يضيئه.

  1. شجرة اللعبة: لعبة إكس-أو كقائمة من 9 مربعات، والتحقق من الفائز من جدول خطوط، واستدعاء ذاتي يعدّ كل مباراة ممكنة من موضع معيّن (3,468 مباراة بعد نقلتين).
  2. Minimax: إعطاء درجة للموضع بافتراض أن اللاعبَين مثاليان، واختيار أفضل نقلة، وتفضيل الانتصار السريع، وحل اللعبة كاملة بمذكرة تحفظ كل المواضع الـ 5,478. ثم العب ضد الـ Pi، واحرص على التعادل في أحسن الأحوال.
  3. Alpha-beta: احسب العمل أولًا ثم قلّصه. بعد نقلتين، يصبح عدد المواضع 7,332 موضعًا ثم 871، ثم 768 مع ترتيب يبدأ من المركز، وتُحل اللعبة كاملة في 7,865 موضعًا دون مذكرة.
  4. Evaluation: Connect Four, a four-in-a-row check from the last move, and a score built from the 69 windows of four. A one-move player trusts it and misses a block, which is the case for searching deeper.
  5. العمق مقابل الزمن: alpha-beta كنموذج negamax مع حد للعمق، وجدول بالعقد والملي ثانية لكل عمق، والتعميق التكراري ضمن ميزانية زمنية، وبحث من 3 نقلات يعثر على نصر حتمي.
  6. بحث Monte Carlo: جولات عشوائية، واختيار النقلات بأسلوب Monte Carlo المسطّح، والضجيج مقابل حجم العينة، وقاعدة UCB1، وهي القاعدة داخل بحث شجرة Monte Carlo.
  7. Boss: an unbeatable Connect Four.

الخاتمة

The boss lesson is a Connect Four game against the Pi on the Serial Monitor. You are X and type a column; the Pi answers with an alpha-beta search, first at a fixed depth of 4 and then with iterative deepening on a time budget, printing how deep it looked. The gallery's traffic light module shows the game: green for your move, amber while the Pi thinks, red when it wins.

Connect Four is solved: the first player wins with perfect play. The course says so, and explains what a truly perfect engine would add (a transposition table, better ordering, a sharper evaluation and an opening book). For nearly everyone who sits down to play, the Pi is unbeatable.

على الـ Pi

يذكر سطر الكتالوج لهذه الدورة لوحة ESP32 مع شاشة لمس. لكنها تعمل على الـ Pi بدلًا من ذلك، فالمحركات بأسلوب Python بسيط يمكنك قراءته وتعديله، واللوحة نصية.

يشغّل الـ Pi نظام MicroPython 1.29 وليس CPython، ويظهر ذلك هنا:

  • time.monotonic() يتبع ساعة المحاكاة، التي تفرض على كل دورة من دورات Python التكلفة الصغيرة نفسها. لذلك تكون أزمنة البحث والعمق الذي تسمح به الساعة متطابقة في كل تشغيل وعلى كل حاسوب.
  • random هو مولّد MicroPython نفسه. مع random.seed(2026) تتكرر الجولات بدقة تامة، لكن الأرقام تختلف عن أرقام CPython.
  • لا يحتفظ الـ dict بترتيب مفاتيحه، لذا تُطبع النتائج واحدًا واحدًا بدلًا من طباعة الـ dict كاملًا.
  • البحث أبطأ منه على حاسوب مكتبي، لذا تُبقي الدروس كل بحث في حدود بضعة آلاف من المواضع. ارفع العمق أو الميزانية بنفسك لتراه ينمو.