مقدمة في الـ Adversarial Search في الذكاء الإصطناعي

في هذا المقال، نعلم الكمبيوتر كيف يلعب X/O باستخدام الـ Min-max Algorithm

Mohammad Al-Aliمنذ 5 سنوات

بسم الله الرحمن الرحيم

هل تساءلت يوماً كيف يمكن للكمبيوتر أن يلعب الألعاب (الشطرنج، X/O، Go وغيرها) بذكاء؟ لطالما كان هذا السؤال يحيرني مع بداياتي في البرمجة. في هذا المقال سوف نتعرف على كيفية لعب الكمبيوتر للألعاب باستخدام إحدى خوارزميات الذكاء الإصطناعي (Min-max) ونقوم بتطبيق مثال عملي ببناء لعبة X/O يصعب هزيمتها!

ما هو الـ Adversarial Search؟

هي طريقة بحث لإيجاد أفضل حركة في لعبة مكونة من لاعبين. وتستخدم هذه الطريقة في الألعاب التي يكون فيها تقدم اللاعب على الآخر قابل للقياس، ويكون فوز اللاعب هو خسارة للآخر وبذلك يكون المجموع 0 (zero-sum). تستخدم هذه الطريقة عادة مع الألعاب التي فيها لوح (Board Games) كالـ X/O والشطرنج وغيرها. وتشتهر خوارزمية Min-max في هذا المجال وهناك تحسين لها باسم Alpha-Beta Pruning.

لنبدأ بتعريف بعض المصطلحات المستخدمة في هذه الخوارزمية، لننتقل بعدها لفهم كيفية عمل الخوارزمية:

Initial State:

وهي حالة اللعبة (state) في البداية وقبل بدأ تنفيذ الخوارزمية.

Successor Function:

وهي الدالة المسؤولة عن توليد الحركات المتاحة (Legal Moves) في وضعية معينة (state) من اللعبة.

Terminal Test:

وهو اختبار يبين ما إذا كانت اللعبة وصلت للنهاية بفوز أحد اللاعبين أو التعادل..

Evaluation Function:

وهي دالة تعطي قيمة رقمية هي تقييم يحدد اللاعب المتقدم في وضعية معينة (state) من اللعبة.

في تطبيقنا للخوارزمية، المشكلات الأساسية التي يجب علينا حلها هي:

تحديد طريقة لتمثيل اللعبة (اللوح).
توليد الحركات المتاحة (Legal Moves)
تقييم وضعية معينة وتحديد اللاعب المتقدم ومقدار التقدم.

كيف تعمل الخوارزمية؟

تقوم الخوارزمية على مبدأين:

عندما أريد (الكمبيوتر) أن ألعب، سأحاول أن أختار حركة تزيد من تقييمي وفرصة فوزي.
عندما يريد أن يلعب خصمي، سيحاول اختيار حركة (حركته) تقلل من تقييمي وأدائي.

ومن هنا جاءت التسمية Min-max:

Min: الخصم يحاول تقليل أدائي.
Max: أنا (الكمبيوتر) أحاول أن أرفع من تقييمي.

لكي تختار الحركة، تقوم الخوارزمية بتجربة جميع الحركات المتاحة (باستخدام الـ Successor Function)، وفي كل حركة تجرب الحركات المتاحة التي تليها وهكذا إلى أن نصل إلى عمق معين (Depth) نحدده نحن. بعد أن نصل لهذا العمق نقيم حالة اللعبة (باستخدام الـ Evaluation Function). الحركة الأفضل هي الحركة التي قادت إلى حالة اللعبة التي لها تقييم أعلى.

لتسهيل الموضوع، بمكننا تمثيل العملية بـ Tree تسمى Game Tree، بحيث:

Nodes: تمثل حالات (أوضاع) اللعبة
Edges: تمثل الحركات الحركات المتاحة والتي تنقلنا من حالة (وضعية اللعبة) إلى حالة أخرى.
ستكون الـ Root node هي حالة اللعبة الإبتدائية (initial state) والمطلوب اختيار الحركة عندها، وبالتالي ستكون الحركة التي سيتحركها الكمبيوتر(لذلك سنختار القيمة التي تعطينا أفضل تقييم، لذلك تسمى هذه الـ node بـ Max node)، وبذلك سيكون الـ level الذي يلي الـ root يمثل الحركة التي سيلعبها الخصم (ولذلك سنفترض أن الخصم سيختار اللعبة الأفضل له والتي ستعطينا أسوء تقييم بالنسبة للكمبيوتر لذلك تسمى الـ nodes في هذا الـ level بـ Min node).. وهكذا تتبادل الأدوار بين حركة للكمبيوتر (Max node) وحركة للخصم (Min node) إلى أن نصل إلى العمق المطلوب أو تنتهي اللعبة.
ستكون الـ Leaves أو الـ Terminal Nodes هي الـ nodes التي سنقيم حالة اللعبة عندها.

سنحاول التوضيح أكثر بالصور، لنأخذ الشجرة التالية من وسط لعبة X/O:

في هذه اللعبة، يلعب الكمبيوتر بدور X، والآن دور الكمبيوتر في اللعب وعليه اختيار الحركة التالية. كما قلنا، يمثل الـ Root الحالة الحالية للعبة والتي نريد اختيار الحركة التالية عندها، لذلك سنجرب كل الحركات المتاحة لنختار الحركة التي تعطينا أفضل قيمة، وفي كل حركة من هذه الحركات سنجرب الحركات المتاحة التي تليها ونفترض أن الخصم سيختار الحركة الأفضل له والتي ستكون الحركة التي تعطينا أقل قيمة بالنسبة لنا وهكذا..

في الصورة، توضح التسميات على اليسار (Max, Min) عند كل مستوى (Level) ذلك، فالـ Root الذي سيختار الحركة التي تعطينا أفضل (Max) تقييم، لذلك التسمية عند المستوى الأول (Root) هي Max، والتسمية في المستوى الثاني -حيث دور الخصم الذي سيحاول اختيار الحركة التي تعطينا أقل (Min) تقييم (بالنسبة لنا)- هي Min. وهكذا تتبادل الأدوار إلى أن نصل إلى الـ Depth المطلوب أو أن تنتهي اللعبة.

عندما نصل إلى leaf -لنأخذ العقدة رقم 4 كمثال-، نقوم بتقييم وضع اللعبة ولأننا فزنا سنعطيها تقييم بـ مالانهاية، ولأن العقدة 3 هي Max ستختار القيمة الأعلى (والوحيدة) القادمة من العقدة 4.

لنأخذ العقدة 2 كمثال آخر، لأنها Min node ستختار القيمة الأقل بين 3 و 5، ولكن لا فرق بينهما لأن كلاهما لهما قيمة بـ ما لانهاية والتي تعبر عن فوزنا، (يعني أنه لا مفر للخصم من الخسارة).

أما بالنسبة للعقدة 7 -ولأنها Min node- ستختار القيمة الأقل بين 8 و 9، والتي هي 8 بقيمة سالب ما لانهاية والتي تعبر عن خسارتنا وفوز الخصم.

العقدة 11، ستختار القيمة الأقل بين 12 و 13 وهي 12 لأنها أيضا سالب مالا نهاية.

نأتي الآن للـ Root Node والتي عندها سنختار الحركة التي سنقوم بها، لدينا الآن 3 خيارات وهي مالانهاية (من العقدة 2)، وسالب ما لانهاية من العقدتين 7 و 11. ولأننا كما قلنا الـ Root Node هي Max Node، ستختار القيمة الأعلى (ما لانهاية) والقادمة من العقدة 2.

بعد كل هذا، استنتجنا أن الحركة الأفضل لنا هي وضع الـ X في المنتصف كما في العقدة 2.

والآن بعد أن فهمنا كيف تعمل الخوارزمية، لنلقي نظرة على الـ Pseducode ونفهمه:

تستقبل الخوارزمية كمدخلات: الحالة الحالية للعبة (ممثلة بالـ node) والـ depth المطلوب. يقوم المتغير maximizingPlayer بتحديد إذا ما كانت الـ Node الحالية هي Max Node أم Min Node.

في السطر 2، نقوم بالتأكد إذا ما وصلنا للـ Depth المطلوب أو إذا كانت اللعبة قد انتهت بفوز أحد اللاعبين أو التعادل، إذا كان كذلك سنقوم بإرجاع تقييم الـ node (باستخدام الـ Evaluation Function كما ذكرنا).

تبدأ جزئية الكود الخاصة بالـ Max node عند السطر 4، حيث سنمر على جميع الحركات المتاحة لنا إنطلاقاً من الـ node الحالية، وفي كل حركة نستدعي الدالة نفسها مع تغيير قيمة الـ maximizingPlayer إلى FALSE لأن الدور التالي سيكون للخصم (Min Node). وتقليل قيمة الـ Depth بـ 1. بعد أن نقوم بالمرور على جميع الحركات، نختار الحركة التي تعطينا أفضل تقييم.

وبالمثل، الكود الخاص بالـ Min node، نمر على جميع الحركات المتاحة لنا إنطلاقاً من الـ node الحالية، وفي كل حركة نستدعي الدالة نفسها مع تغيير قيمة الـ maximizingPlayer إلى TRUE لأن الدور التالي سيكون للكمبيوتر (Max Node). وتقليل قيمة الـ Depth بـ 1. بعد أن نقوم بالمرور على جميع الحركات، سنفترض أن الخصم سيلعب أفضل حركة له ويختار الحركة التي تعطينا أقل تقييم.

مثال تطبيقي، لعبة X/O:

سنقوم الآن بتطبيق ما تعلمناه على لعبة X/O وسنقوم بكتابتها بلغة جافا، سنقوم بتمثيل اللعبة كمصفوفة ثنائية الأبعاد من نوع char. وسنستخدم طريقتين لتحديد المربعات، إما بـ index خاص لكل بعد من البعدين أو برقم من 1 إلى 9 لنسهل عملية الإختيار للمستخدم.

ولكي نسهل عملية المرور على جميع الخطوط العمودية والأفقية والأقطار، بدلاً من فعلها يدوياً، سنقوم بتمثيلها في arrays.

سنمثل كل خط بـ 4 أرقام: بداية الخط في البعد الأول والبعد الثاني و مقدار الزيادة في البعد الأول والثاني.

int[] iStart = {0, 1, 2, 0, 0, 0, 0, 0};
int[] jStart = {0, 0, 0, 0, 1, 2, 0, 2};

int[] iIncrement = {0, 0, 0, 1, 1, 1, 1, -1};
int[] jIncrement = {1, 1, 1, 0, 0, 0, 1, -1};

فالخط الأول في الصورة (رقم 0) سيُمَثّل في العنصر الأول من المصفوفات الأربعة. فيبدأ الخط الأول عند الـ index 0 من البعد الأول والثاني board[0][0] ونقوم بزيادة البعد الثاني فقط بـ 1 لثلاث مرات فنحصل على الـ :

board[0][0] , board[0][1] and board[0][2]

والتي تمثل فعلياً الخط 0 المرسوم في الصورة.

Successor Function:

الحركات المتاحة في اللعبة ستكون ببساطة المربعات الفارغة التي يمكننا وضع X/O فيها.

List<Integer> availableMoves(char[][] board) {
        List<Integer> availableSquares = new ArrayList<>();

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == ' ')
                    availableSquares.add(i * 3 + j);
            }
        }

        return availableSquares;
}

في الكود السابق، استخدمنا تمثيل المربعات برقم واحد (من 0 إلى 8) لتبسيط عملية تخزين الحركات.

Evaluation Function:

لحسن حظنا، فإن لعبة X/O لعبة بسيطة ولا تحتاج إلى طرق كثيرة ومعقدة لتقييم حالة اللعبة، يجدر بنا هنا أن نذكر أن ألعاب معقدة كالشطرنج تستخدم الكثير من الـ features لتقييم وضعية اللوح، فمثلاً حاسوب Deep Blue من IBM والذي تغلب في عام 1996 على Garry Kasparov، بطل العالم للشطرنج في الوقت ذاك، استخدم 8000 feature لتقييم اللوح، مثل عدد وأنواع القطع المتقية وأماكنها، أمان الملك، تركيب البيادق (Pawns Structure) وغيرها الكثير..

في لعبة الـ X/O ستكون الـ Evaluation Function بسيطة، وترتكز على عدد الفرص المتاحة لنا للفوز ومدى قربها منه. لنفترض أن الكمبيوتر يلعب بـ X، ستكون الحسابات كالتالي:

+10 لكل مربعين في خط واحد محجوزين بـ X والمربع الآخر هو فارغ.
+1 لكل مربع في خط واحد محجوز بـ X والمربعين الآخرين فارغين.

ولا ننسى أن نأخذ بعين الإعتبار حركات اللاعب الآخر:

-10 لكل مربعين في خط واحد محجوزين بـ O والمربع الآخر هو فارغ.
-1 لكل مربع في خط واحد محجوز بـ O والمربعين الآخرين فارغين.

الكود التالي يقوم بالعملية:

int evaluate(char[][] board, char player) {
    int value = 0;

    /*
     * For each line of the eight lines
     * */
    for (int line = 0; line < iStart.length; line++) {

        int i = iStart[line];
        int j = jStart[line];


        /*
         * Number of squares in the line for each player
         * */
        int playersSquare = 0;
        int opponentSquare = 0;

        int emptySquares = 0;

        int k = 0;
        do {
            char currentSquare = board[i][j];

            if (currentSquare != ' ') {
                if (currentSquare == player)
                    playersSquare++;
                else
                    opponentSquare++;
            } else
                emptySquares++;

            i += iIncrement[line];
            j += jIncrement[line];

            k++;
        } while (k < 3);

        if (playersSquare == 2 && emptySquares == 1)
            value += 10;
        else if (playersSquare == 1 && emptySquares == 2)
            value += 1;

        if (opponentSquare == 2 && emptySquares == 1)
            value -= 10;
        else if (opponentSquare == 1 && emptySquares == 2)
            value -= 1;
    }

    return value;
}

والآن دور الخوارزمية:

قمنا بتقسيم الخوارزمية إلى 3 دوال لتبسيط العملية.

int minMax(char[][] board, int depth, char player) {
    double bestMoveValue = Double.NEGATIVE_INFINITY;
    int bestMove = 0;

    for (int move : availableMoves(board)) {
        /*
         * Avoid modifying the board because it is needed for the other moves
         * */
        char[][] copyBoard = copyBoard(board);
        copyBoard[move / 3][move % 3] = player;

        double moveValue = min(copyBoard, depth - 1, player);
        if (moveValue > bestMoveValue) {
            bestMoveValue = moveValue;
            bestMove = move;
        }

    }

    return bestMove;
}

الدالة السابقة هي الدالة الرئيسية والتي سننطلق لتطبيق الخوارزمية منها، ولأننا نريد اختيار الحركة وإرجاعها وليس فقط إرجاع التقييم الناتج عنها كما تقوم الدوال التالية.

الدالة تمر على جميع الحركات، وتعطي الدور للخصم بمناداة دالة الـ min -ليختار الحركة الأفضل له-، وتعيد الحركة التي أعطتنا أفضل قيمة.

double min(char[][] board, int depth, char player) {

    char winner = getWinnerIfThere(board);
    if (winner != ' ') {
        if (winner == player) {
            return Double.POSITIVE_INFINITY;
        } else {
            return Double.NEGATIVE_INFINITY;
        }
    }

    if (isDraw(board))
        return 0;

    if (depth == 0) {
        return evaluate(board, player);
    }

    char opponent = player == 'X' ? 'O' : 'X';

    double bestMoveValue = Double.POSITIVE_INFINITY;

    for (int move : availableMoves(board)) {
        char[][] copyBoard = copyBoard(board);
        copyBoard[move / 3][move % 3] = opponent;

        double moveValue = max(copyBoard, depth - 1, player);

        if (moveValue < bestMoveValue) {
            bestMoveValue = moveValue;
        }
    }

    return bestMoveValue;

}

هذه دالة الـ min والمسؤولة عن الـ Min Node، سنتأكد في البداية من الوصول لشرط يوقفنا عن الإستمرار بتجربة الحركات، سنتأكد في البداية إذا ما كنا وصلنا لنهاية اللعبة، فإذا كان الكمبيوتر هو الفائز، سنرجع ما لانهاية، أما إذا كان الخصم هو الفائز فسنرجع سالب ما لانهاية. وفي حالة التعادل، سنرجع صفر. شرط آخر للتوقف هو الوصول للـ Depth المحدد، فإذا وصلنا له سنرجع التقييم للوضع الحالي.

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

double max(char[][] board, int depth, char player) {
    char winner = getWinnerIfThere(board);
    if (winner != ' ') {
        if (winner == player) {
            return Double.POSITIVE_INFINITY;
        } else {
            return Double.NEGATIVE_INFINITY;
        }
    }

    if (isDraw(board))
        return 0;
    if (depth == 0) {
        return evaluate(board, player);
    }


    double bestMoveValue = Double.NEGATIVE_INFINITY;

    for (int move : availableMoves(board)) {
        char[][] copyBoard = copyBoard(board);
        copyBoard[move / 3][move % 3] = player;

        double moveValue = min(copyBoard, depth - 1, player);
        if (moveValue > bestMoveValue) {
            bestMoveValue = moveValue;
        }

    }

    return bestMoveValue;
}

الدالة السابقة هي دالة الـ Max Node وتقوم بعمل مماثل لما تقوم به الـ min.

الشفرة المصدرية للعبة كاملة موجود هنا، استمتع باللعب مع برنامجك وحاول أن تهزمه إن استطعت!

مبروك! لقد قمت ببرمجة لعبة X/O ذكية وصعبة الهزيمة. بإمكاننا التحكم بصعوبة اللعبة عن طريق تحديد الـ Depth. فكلما زاد الـ Depth كلما زادت الصعوبة والعكس صحيح. في لعبة الـ X/O تعتبر الحركات المتاحة قليلة (تسمى بالـ Branching Factor في تمثيل الـ Game Tree) لذلك يمكننا وضع الـ Depth بـ 9 لكي نضمن الوصول لنهاية اللعبة دائماً بذلك ستكون الـ Complexity للخوارزمية هي O(9!) (مضروب الـ 9)، ولن نلاحظ أي بطئ في لعب الكمبيوتر، بعكس الألعاب المعقدة التي يكون فيها عدد الحركات كبير كالشطرنج. لذلك يوجد تحسين للخوارزمية يقوم بتجاهل حساب الـ nodes غير اللازمة، وتسمى هذه الخوارزمية بـ Alpha-Beta Pruning.

كلمات دليلية: ai games min-max

إعجاب

أعجبني

7872

مشاهدات

تلقائي