مشروع: لعبة إكس-أو

الفكرة: أنت X والحاسوب O. يقرأ البرنامج حركاتك من الإدخال (رقم خانة من 1 إلى 9 في كل سطر)، والحاسوب يبحث في كل الاحتمالات (minimax) فلا يخسر.

البرنامج

في هذا التشغيل كُتبت الحركات مسبقاً في الإدخال، ومنها «س» وخانات مشغولة لترى رسائل التحقق:

اكس_او.م

# تطبيق تعليمي: لعبة إكس-أو في الطرفية، اللاعب ضد الحاسوب (بحث minimax كامل)
# يقرأ حركات اللاعب من الإدخال (رقم الخانة 1–9 في كل سطر)

تعداد خانة:
    فارغة
    انا
    حاسوب

هيكل لوح:
    خانات مصفوفة[خانة, 9]

ثابت خطوط_الفوز = "012345678036147258048246"

داله رمز_خانة(خ خانة, رقم عدد) نص:
    حالات خ:
        حاله خانة.فارغة:
            ارجع نص(رقم)
        حاله خانة.انا:
            ارجع "X"
        حاله خانة.حاسوب:
            ارجع "O"

داله ارسم(ل لوح) فراغ:
    لكل ص في مدى(0, 3):
        اطبع(" ", رمز_خانة(ل.خانات[3 * ص], 3 * ص + 1), " | ", رمز_خانة(ل.خانات[3 * ص + 1], 3 * ص + 2), " | ", رمز_خانة(ل.خانات[3 * ص + 2], 3 * ص + 3))
        اذا ص < 2:
            اطبع("---+---+---")

داله رقم_في(ن نص, موضع عدد) عدد:
    ارجع عدد(جزء(ن, موضع, موضع + 1)) والا 0

داله الفائز(ل لوح) خانة:
    لكل خط في مدى(0, 8):
        ا = رقم_في(خطوط_الفوز, 3 * خط)
        ب = رقم_في(خطوط_الفوز, 3 * خط + 1)
        ج = رقم_في(خطوط_الفوز, 3 * خط + 2)
        اذا ل.خانات[ا] != خانة.فارغة و ل.خانات[ا] == ل.خانات[ب] و ل.خانات[ب] == ل.خانات[ج]:
            ارجع ل.خانات[ا]
    ارجع خانة.فارغة

داله ممتلئ(ل لوح) منطقي:
    لكل خ في ل.خانات:
        اذا خ == خانة.فارغة:
            ارجع خطاء
    ارجع صواب

عقد_مفحوصة = 0

داله قيمة(ل لوح, دور خانة, عمق عدد) عدد:
    عام عقد_مفحوصة
    عقد_مفحوصة += 1
    ف = الفائز(ل)
    اذا ف == خانة.حاسوب:
        ارجع 10 - عمق
    اذا ف == خانة.انا:
        ارجع عمق - 10
    اذا ممتلئ(ل):
        ارجع 0
    افضل = 100
    اذا دور == خانة.حاسوب:
        افضل = -100
    لكل ع في مدى(0, 9):
        اذا ل.خانات[ع] != خانة.فارغة:
            تجاوز
        ل.خانات[ع] = دور                 # الهيكل بالقيمة: نسخة لا تمس لوح المستدعي
        اذا دور == خانة.حاسوب:
            ق = قيمة(ل, خانة.انا, عمق + 1)
            اذا ق > افضل:
                افضل = ق
        غير ذلك:
            ق = قيمة(ل, خانة.حاسوب, عمق + 1)
            اذا ق < افضل:
                افضل = ق
        ل.خانات[ع] = خانة.فارغة
    ارجع افضل

داله حركة_الحاسوب(ل لوح) عدد:
    افضل = -100
    موضع = -1
    لكل ع في مدى(0, 9):
        اذا ل.خانات[ع] == خانة.فارغة:
            ل.خانات[ع] = خانة.حاسوب
            ق = قيمة(ل, خانة.انا, 1)
            ل.خانات[ع] = خانة.فارغة
            اذا ق > افضل:
                افضل = ق
                موضع = ع
    ارجع موضع

داله اقرأ_حركة(ل لوح) عدد:
    طالما !انتهى_الدخل():
        سطر = قص_الفراغات(اقرأ("حركتك (1-9): "))
        ر = عدد(سطر) والا خ:
            اطبع("«", سطر, "» ليس رقماً")
            تجاوز
        اذا ر < 1 او ر > 9:
            اطبع("الخانة بين 1 و9")
            تجاوز
        اذا ل.خانات[ر - 1] != خانة.فارغة:
            اطبع("الخانة مشغولة")
            تجاوز
        ارجع ر - 1
    ارجع -1

ل = لوح([خانة.فارغة, خانة.فارغة, خانة.فارغة, خانة.فارغة, خانة.فارغة, خانة.فارغة, خانة.فارغة, خانة.فارغة, خانة.فارغة])
اطبع("أنت X والحاسوب O")
طالما الفائز(ل) == خانة.فارغة و !ممتلئ(ل):
    ارسم(ل)
    م = اقرأ_حركة(ل)
    اذا م < 0:
        اطبع("انتهى الإدخال")
        توقف
    ل.خانات[م] = خانة.انا
    اذا الفائز(ل) != خانة.فارغة او ممتلئ(ل):
        توقف
    ح = حركة_الحاسوب(ل)
    اطبع("الحاسوب يلعب ", ح + 1)
    ل.خانات[ح] = خانة.حاسوب
ارسم(ل)
حالات الفائز(ل):
    حاله خانة.انا:
        اطبع("فزت!")
    حاله خانة.حاسوب:
        اطبع("فاز الحاسوب")
    حاله خانة.فارغة:
        اطبع("تعادل")
اطبع("عقد مفحوصة: ", عقد_مفحوصة)

مخرجات مسجّلة من المجمّعmeem اكس_او.م · meem 0.10.0+b01b55f

الإدخال

5س153489

أنت X والحاسوب O 1 | 2 | 3---+---+--- 4 | 5 | 6---+---+--- 7 | 8 | 9حركتك (1-9): الحاسوب يلعب 1 O | 2 | 3---+---+--- 4 | X | 6---+---+--- 7 | 8 | 9حركتك (1-9): «س» ليس رقماًحركتك (1-9): الخانة مشغولةحركتك (1-9): الخانة مشغولةحركتك (1-9): الحاسوب يلعب 7 O | 2 | X---+---+--- 4 | X | 6---+---+--- O | 8 | 9حركتك (1-9): الحاسوب يلعب 6 O | 2 | X---+---+--- X | X | O---+---+--- O | 8 | 9حركتك (1-9): الحاسوب يلعب 2 O | O | X---+---+--- X | X | O---+---+--- O | X | 9حركتك (1-9):  O | O | X---+---+--- X | X | O---+---+--- O | X | Xتعادلعقد مفحوصة: 56490

بُني أيضاً بـ meem build عند بناء الموقع: ملف ساكن حجمه 47.2 ك.ب، شُغّل وحده وطابق مخرجه المخرج أعلاه.

خطوة خطوة

1. التعداد خانة: فارغة أو أنا أو حاسوب. وحالات على التعداد تُفحص عند الترجمة: نسيان حالة خطأ.
2. اللوح هيكل بمصفوفة ثابتة: مصفوفة[خانة, 9]. والهيكل يُمرَّر بالقيمة، فكل استدعاء لـ قيمة يعمل على نسخته.
3. minimax: قيمة تجرّب كل خانة فارغة وتستدعي نفسها للاعب الآخر، وتفضّل الفوز الأقرب (10 - عمق).
4. الإدخال: اقرأ_حركة تقرأ حتى ينتهي الإدخال (انتهى_الدخل())، وعدد(سطر) والا خ: ترفض ما ليس رقماً، وتتحقق من المدى ومن أن الخانة فارغة.

ما كان صعباً

• نسخ خفية في الدالة الساخنة (في 0.9.1): رقم_في تكتب عدد(جزء(ن, موضع, موضع + 1)). في 0.9.1 كان عدد() على العرض يحجز نسخة لا تُعاد في كل نداء، وminimax يناديها عشرات الآلاف من المرات، فأبقى هذا السطر وحده في التقرير 1.1 مليون كتلة (20 م.ب) حتى الخروج، وكشفها --debug-mem بالسطر. في 0.10.0 أُزيلت هذه النسخ: البرنامج نفسه بـ --debug-mem لا يذكر هذا السطر في تقريره.
• الحل الالتفافي (غير مشغَّل هنا): أن تُحسب خطوط الفوز أعداداً مرة واحدة في قائمة، بدل تحويل الأحرف في كل نداء.

ما تعلّمناه

• التعداد مع حالات المكتملة يجعل منطق اللعبة واضحاً ومفحوصاً.
• الهيكل بالقيمة يغني عن التراجع اليدوي في بحث كهذا.
• عُدّت 56490 عقدة في هذه اللعبة، والزمن في التقرير 0.24 ث مبنياً.