بناء لعبة إكس أو (Tic Tac Toe) لا تُقهر: دليلك الشامل لخوارزمية المينيماكس (Minimax)

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

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

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

فهم خوارزمية المينيماكس (Minimax): كيف تعمل؟

يمكن تعريف خوارزمية المينيماكس (Minimax) على أفضل وجه بأنها دالة تكرارية (recursive function) تؤدي المهام التالية:

• تُعيد قيمة محددة إذا تم العثور على حالة نهائية (terminal state) للعبة (+10 للفوز، 0 للتعادل، -10 للخسارة).
• تستكشف جميع الأماكن المتاحة على لوحة اللعبة.
• تستدعي دالة المينيماكس (minimax function) نفسها لكل مكان متاح (مبدأ التكرارية).
• تُقيّم القيم المعادة من استدعاءات الدالة وتُعيد أفضل قيمة ممكنة.

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

تطبيق خوارزمية المينيماكس (Minimax) برمجياً

في هذا الجزء من الشرح، سنعمل على حالة شبه نهائية من اللعبة، كما هو موضح في الشكل أدناه. نظرًا لأن خوارزمية المينيماكس (Minimax) تُقيّم كل حالة محتملة للعبة (مئات الآلاف من الحالات)، فإن البدء بحالة شبه نهائية يُسهّل تتبع الاستدعاءات التكرارية (recursive calls) للخوارزمية. في الشكل التالي، افترض أن الذكاء الاصطناعي (AI) يمثله الرمز X، واللاعب البشري يمثله الرمز O.

الشكل 2: مثال على حالة لوحة اللعبة

تهيئة لوحة اللعبة والمتغيرات الأساسية

لتسهيل التعامل مع لوحة لعبة إكس أو (Tic Tac Toe)، يجب تعريفها كمصفوفة (array) تحتوي على 9 عناصر. سيحتوي كل عنصر على فهرسه كقيمة، وهو ما سيكون مفيدًا لاحقًا. نظرًا لأن اللوحة الموضحة أعلاه تحتوي بالفعل على بعض حركات X و O، دعنا نُعرّف اللوحة مع هذه الحركات الأولية في متغير يُسمى origBoard.

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

بعد ذلك، نُعلن عن متغيرين aiPlayer و huPlayer ونُعيّن لهما القيمتين "X" و "O" على التوالي. بالإضافة إلى ذلك، نحتاج إلى دالة تبحث عن التوليفات الفائزة وتُعيد true إذا وجدتها، ودالة أخرى تُدرج فهارس الأماكن المتاحة على اللوحة.

/* لوحة اللعبة الأصلية
O |   | X
--------- 
X |   | X
--------- 
  | O | O
*/
var origBoard = ["O", 1 ,"X","X", 4 ,"X", 6 ,"O","O"];

// اللاعب البشري
var huPlayer = "O";
// الذكاء الاصطناعي
var aiPlayer = "X";

// تُعيد قائمة بفهارس الأماكن الفارغة على اللوحة
function emptyIndexies(board) {
    return board.filter(s => s != "O" && s != "X");
}

// تتحقق من التوليفات الفائزة باستخدام فهارس اللوحة
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) الأساسية

الآن، دعنا نتعمق في الجزء الأهم بتعريف دالة المينيماكس (minimax) التي تأخذ وسيطين: newBoard (اللوحة الحالية) و player (اللاعب الحالي). أولاً، نحتاج إلى إيجاد فهارس الأماكن المتاحة على اللوحة وتخزينها في متغير يُسمى availSpots.

// دالة المينيماكس الرئيسية
function minimax(newBoard, player) {
    // الأماكن المتاحة
    var availSpots = emptyIndexies(newBoard);

يجب أيضًا التحقق من الحالات النهائية للعبة وإعادة قيمة مناسبة بناءً عليها. إذا فاز اللاعب O (البشري)، يجب أن تُعيد الدالة كائنًا بقيمة score: -10. إذا فاز اللاعب X (الذكاء الاصطناعي)، يجب أن تُعيد كائنًا بقيمة score: +10. بالإضافة إلى ذلك، إذا كان طول مصفوفة availSpots صفرًا، فهذا يعني عدم وجود أماكن إضافية للعب، وقد انتهت اللعبة بالتعادل، وفي هذه الحالة يجب أن تُعيد الدالة كائنًا بقيمة score: 0.

    // تتحقق من الحالات النهائية مثل الفوز والخسارة والتعادل
    // وتُعيد قيمة بناءً عليها
    if (winning(newBoard, huPlayer)) {
        return { score: -10 };
    } else if (winning(newBoard, aiPlayer)) {
        return { score: 10 };
    } else if (availSpots.length === 0) {
        return { score: 0 };
    }

بعد ذلك، نحتاج إلى جمع النقاط من كل مكان فارغ لتقييمها لاحقًا. لذلك، نُنشئ مصفوفة تُسمى moves ونقوم بالتكرار عبر الأماكن الفارغة، مع جمع فهرس كل حركة وقيمتها (score) في كائن يُسمى move. ثم نُعيّن رقم فهرس المكان الفارغ الذي تم تخزينه كرقم في origBoard إلى خاصية index في كائن move. لاحقًا، نُعيّن المكان الفارغ على newBoard للاعب الحالي ونستدعي دالة المينيماكس (minimax) مع اللاعب الآخر واللوحة الجديدة المُعدّلة (هنا تكمن التكرارية). بعد ذلك، يجب تخزين الكائن الناتج عن استدعاء دالة المينيماكس (minimax) والذي يتضمن خاصية score إلى خاصية score في كائن move. إذا لم تجد دالة المينيماكس (minimax) حالة نهائية، فإنها تستمر في التعمق تكراريًا مستوى تلو الآخر في اللعبة. يحدث هذا التكرار حتى تصل إلى حالة نهائية وتُعيد قيمة (score) إلى المستوى الأعلى. أخيرًا، تُعيد المينيماكس (Minimax) ضبط newBoard إلى ما كانت عليه قبل التعديل وتدفع كائن move إلى مصفوفة moves.

    // مصفوفة لجمع جميع الكائنات
    var moves = [];

    // التكرار عبر الأماكن المتاحة
    for (var i = 0; i < availSpots.length; i++) {
        // إنشاء كائن لكل مكان وتخزين فهرس ذلك المكان
        var move = {};
        move.index = newBoard[availSpots[i]];

        // تعيين المكان الفارغ للاعب الحالي
        newBoard[availSpots[i]] = player;

        /* جمع القيمة الناتجة عن استدعاء المينيماكس على خصم اللاعب الحالي */
        if (player == aiPlayer) {
            var result = minimax(newBoard, huPlayer);
            move.score = result.score;
        } else {
            var result = minimax(newBoard, aiPlayer);
            move.score = result.score;
        }

        // إعادة ضبط المكان ليصبح فارغًا
        newBoard[availSpots[i]] = move.index;

        // دفع الكائن إلى المصفوفة
        moves.push(move);
    }

بعد جمع جميع الحركات المحتملة وقيمها، تحتاج خوارزمية المينيماكس (Minimax) إلى تقييم أفضل حركة في مصفوفة moves. يجب أن تختار الحركة ذات القيمة الأعلى عندما يكون دور الذكاء الاصطناعي (AI)، والحركة ذات القيمة الأقل عندما يكون دور اللاعب البشري. لذلك، إذا كان اللاعب الحالي هو aiPlayer، فإنها تُعيّن متغيرًا يُسمى bestScore إلى قيمة منخفضة جدًا (مثل -10000) وتتكرر عبر مصفوفة moves. إذا كانت قيمة حركة ما أعلى من bestScore، فإن الخوارزمية تُخزّن تلك الحركة. في حال وجود حركات ذات قيم متساوية، سيتم تخزين الأولى فقط. تحدث عملية التقييم نفسها عندما يكون اللاعب هو huPlayer، ولكن هذه المرة سيتم تعيين bestScore إلى قيمة عالية (مثل 10000) وتبحث المينيماكس (Minimax) عن الحركة ذات القيمة الأقل لتخزينها. في النهاية، تُعيد المينيماكس (Minimax) الكائن المُخزّن في bestMove.

    // إذا كان دور الكمبيوتر، تكرار على الحركات واختيار الحركة ذات القيمة الأعلى
    var bestMove;
    if (player === aiPlayer) {
        var bestScore = -10000;
        for (var i = 0; i < moves.length; i++) {
            if (moves[i].score > bestScore) {
                bestScore = moves[i].score;
                bestMove = i;
            }
        }
    } else {
        // وإلا، تكرار على الحركات واختيار الحركة ذات القيمة الأقل
        var bestScore = 10000;
        for (var i = 0; i < moves.length; i++) {
            if (moves[i].score < bestScore) {
                bestScore = moves[i].score;
                bestMove = i;
            }
        }
    }
    // تُعيد الحركة المختارة (كائن) من مصفوفة الحركات
    return moves[bestMove];
}

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

خوارزمية المينيماكس (Minimax) في العمل: تتبع مسار القرار

باستخدام الشكل التالي، دعنا نتبع استدعاءات الدالة (Function Calls - FC) للخوارزمية واحدًا تلو الآخر. ملاحظة: في الشكل 3، تمثل الأرقام الكبيرة كل استدعاء دالة، وتشير المستويات إلى عدد الخطوات التي تستبقها الخوارزمية في اللعبة.

الشكل 3: استدعاءات دالة المينيماكس (Minimax) خطوة بخطوة

1. يتم تغذية الخوارزمية باللوحة الأصلية (origBoard) واللاعب الذكاء الاصطناعي (aiPlayer). تُنشئ الخوارزمية قائمة بالأماكن الثلاثة الفارغة التي تجدها، وتتحقق من الحالات النهائية، ثم تتكرر عبر كل مكان فارغ بدءًا من الأول. بعد ذلك، تُغيّر اللوحة الجديدة (newBoard) بوضع لاعب الذكاء الاصطناعي (aiPlayer) في أول مكان فارغ. ثم تستدعي نفسها مع newBoard واللاعب البشري (huPlayer) وتنتظر من استدعاء الدالة (FC) إعادة قيمة.
2. بينما لا يزال استدعاء الدالة الأول قيد التشغيل، يبدأ الاستدعاء الثاني بإنشاء قائمة بالمكانين الفارغين اللذين يجدهما، ويتحقق من الحالات النهائية، ثم يتكرر عبر المكان الفارغ بدءًا من الأول. بعد ذلك، يُغيّر اللوحة الجديدة (newBoard) بوضع اللاعب البشري (huPlayer) في أول مكان فارغ. ثم يستدعي نفسه مع newBoard واللاعب الذكاء الاصطناعي (aiPlayer) وينتظر من استدعاء الدالة (FC) إعادة قيمة.
3. أخيرًا، تُنشئ الخوارزمية قائمة بالأماكن الفارغة، وتجد فوزًا للاعب البشري بعد التحقق من الحالات النهائية. لذلك، تُعيد كائنًا بخاصية score وقيمة -10. نظرًا لأن استدعاء الدالة الثاني أدرج مكانين فارغين، تُغيّر المينيماكس (Minimax) اللوحة الجديدة (newBoard) بوضع اللاعب البشري (huPlayer) في المكان الفارغ الثاني. ثم تستدعي نفسها مع اللوحة الجديدة واللاعب الذكاء الاصطناعي (aiPlayer).
4. تُنشئ الخوارزمية قائمة بالأماكن الفارغة، وتجد فوزًا للاعب البشري بعد التحقق من الحالات النهائية. لذلك، تُعيد كائنًا بخاصية score وقيمة -10. في استدعاء الدالة الثاني، تجمع الخوارزمية القيم القادمة من المستويات الأدنى (استدعاءات الدالة الثالث والرابع). نظرًا لأن دور اللاعب البشري (huPlayer) أدى إلى القيمتين، تختار الخوارزمية القيمة الأدنى من القيمتين. وبما أن كلتا القيمتين متماثلتان، فإنها تختار الأولى وتُعيدها إلى استدعاء الدالة الأول. عند هذه النقطة، يكون استدعاء الدالة الأول قد قيّم قيمة نقل اللاعب الذكاء الاصطناعي (aiPlayer) إلى أول مكان فارغ. بعد ذلك، تُغيّر اللوحة الجديدة (newBoard) بوضع اللاعب الذكاء الاصطناعي (aiPlayer) في المكان الفارغ الثاني. ثم تستدعي نفسها مع newBoard واللاعب البشري (huPlayer).
5. في استدعاء الدالة الخامس، تُنشئ الخوارزمية قائمة بالأماكن الفارغة، وتجد فوزًا للاعب البشري بعد التحقق من الحالات النهائية. لذلك، تُعيد كائنًا بخاصية score وقيمة +10. بعد ذلك، ينتقل استدعاء الدالة الأول بتغيير اللوحة الجديدة (newBoard) ووضع اللاعب الذكاء الاصطناعي (aiPlayer) في المكان الفارغ الثالث. ثم يستدعي نفسه مع اللوحة الجديدة واللاعب البشري (huPlayer).
6. يبدأ استدعاء الدالة السادس بإنشاء قائمة بالمكانين الفارغين اللذين يجدهما، ويتحقق من الحالات النهائية، ثم يتكرر عبر المكانين الفارغين بدءًا من الأول. بعد ذلك، يُغيّر اللوحة الجديدة (newBoard) بوضع اللاعب البشري (huPlayer) في أول مكان فارغ. ثم يستدعي نفسه مع newBoard واللاعب الذكاء الاصطناعي (aiPlayer) وينتظر من استدعاء الدالة (FC) إعادة قيمة.
7. الآن، تتعمق الخوارزمية بمستويين في التكرارية. تُنشئ قائمة بالمكان الفارغ الوحيد الذي تجده، وتتحقق من الحالات النهائية، وتُغيّر اللوحة الجديدة (newBoard) بوضع اللاعب الذكاء الاصطناعي (aiPlayer) في المكان الفارغ. بعد ذلك، تستدعي نفسها مع newBoard واللاعب البشري (huPlayer) وتنتظر من استدعاء الدالة (FC) إعادة قيمة لتقييمها.
8. في استدعاء الدالة الثامن، تُنشئ الخوارزمية قائمة فارغة من الأماكن الفارغة، وتجد فوزًا للاعب الذكاء الاصطناعي (aiPlayer) بعد التحقق من الحالات النهائية. لذلك، تُعيد كائنًا بخاصية score وقيمة +10 إلى المستوى الأعلى (استدعاء الدالة السابع). تلقى استدعاء الدالة السابع قيمة إيجابية واحدة فقط من المستويات الأدنى (استدعاء الدالة الثامن). نظرًا لأن دور اللاعب الذكاء الاصطناعي (aiPlayer) أدى إلى تلك القيمة، تحتاج الخوارزمية إلى إعادة أعلى قيمة تلقتها من المستويات الأدنى. لذلك، تُعيد قيمتها الإيجابية الوحيدة (+10) إلى المستوى الأعلى (استدعاء الدالة السادس). نظرًا لأن استدعاء الدالة السادس أدرج مكانين فارغين، تُغيّر المينيماكس (Minimax) اللوحة الجديدة (newBoard) بوضع اللاعب البشري (huPlayer) في المكان الفارغ الثاني. ثم تستدعي نفسها مع اللوحة الجديدة واللاعب الذكاء الاصطناعي (aiPlayer).
9. بعد ذلك، تُنشئ الخوارزمية قائمة بالأماكن الفارغة، وتجد فوزًا للاعب الذكاء الاصطناعي (aiPlayer) بعد التحقق من الحالات النهائية. لذلك، تُعيد كائنًا بخصائص score وقيمة +10. عند هذه النقطة، يتعين على استدعاء الدالة السادس الاختيار بين القيمة (+10) التي تم إرسالها من استدعاء الدالة السابع (والتي عادت في الأصل من استدعاء الدالة الثامن) والقيمة (-10) التي عادت من استدعاء الدالة التاسع. نظرًا لأن دور اللاعب البشري (huPlayer) أدى إلى هاتين القيمتين المعادتين، تجد الخوارزمية أدنى قيمة (-10) وتُعيدها إلى الأعلى ككائن يحتوي على خصائص score و index.

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

الخلاصة التقنية

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