تحديدِ الخياراتِ المُثلى لاتِّخاذِها في الألعاب

استمع على ساوندكلاود 🎧

يُطلَقُ مفهومُ اللّعبِ على نشاطٍ يتطلّب من اللّاعبِ القيام به، ويقومُ به لتفريغِ طاقةٍ زائدةٍ أو للتّسليةِ والمرحِ، وبعضُ أنواع اللّعب تتضمّنُ اللّعبَ مع الخصومِ والمنافسةَ حيث يسعى كلُّ طرفٍ لَنيلِ مصالحهِ للفوزِ على الخصمِ.

إنّ الألعابَ الّتي سنتحدّثُ عنها اليوم هي ذاتُ طبيعةٍ خاصةٍ: تُدعى بالألعابِ المحدَّدةِ أو الألعابِ ذاتِ المجموعِ الصّفريِّ. هذه الألعابُ تتميّزُ بأنَّ فوزَ أحدِ اللّاعبَين يعني حتماً خسارةَ الآخَر.

لطالما شكّلتِ الألعابُ مجالاً هاماً و ممتعاً للباحثينَ في مجال الذّكاء الصُّنعيّ، وذلك لأنّها عادةً صعبةُ الحلِّ!

فلنأخذ على سبيلِ المثالِ لعبة XO: تتألّفُ اللّعبةُ من لاعبَين وحقلٍ مُقسَّمٍ إلى ٩ مربعاتٍ. يُمَثَّل أحد اللّاعبَين بالحرف X بينما يُمَثَّلُ اللّاعبُ الآخَرُ بالحرفِ O وهدفُ كلٍّ من اللّاعبَين هو الفوزُ عن طريق وضعِ ثلاثةِ أحرفٍ متتابعةٍ إمّا عن طريق مَلءِ سطرٍ أو عمودٍ أو قَطرٍ من الأقطارِ كما في الشّكلِ التّالي حيث ينتصر اللّاعب O:

نلاحظُ خاصَتين للعبة XO: الأولى هي أنّ اللُّعبة تُلعَبُ بالأدوار المتتالية فكلُّ لاعبٍ له دورٌ يقومُ باختيارِ ما يجبُ أن يحدث ثمَّ يأتي دورُ اللاَّعب الآخَر وهكذا، الخاصّةُ الأخرى هُنا هي أنَّهُ في هذه اللُّعبة لا يمكنُ أن يكونَ هناك منتصران معاً.

هذه اللُّعبة هي مثالٌ بسيطٌ عن مجموعةٍ منَ الألعابِ الّتي تتمتّعُ بهذه الخواص، بعض الأمثلة عن ألعابٍ مُشابهةٍ هي:

الشّطرنج، لعبة غو، تنافُس شَرِكَتين على بيع منتجٍ معيّنٍ، أغلبُ ألعاب الحاسوب الاستراتيجية إلخ....

هذه الألعاب من الممكن للحاسوب أن يلعبَها ويُتقنَها أيضاً لأنَّ لديه إمكانيّةَ أن يبني شجرةً في الذّاكرةِ تُعبّرُ عن كل الاحتمالاتِ المُمكنةِ لما يمكنُ أن يلعبَه بكلِّ دورٍ وكلِّ الرُّدودِ الّتي منَ الممكنِ لخصمِه أن يقومَ بها. ما على الحاسوب إلّا أن يبني هذه الشّجرة إن كانت لديه الإمكانيّاتُ (كالذّاكِرةِ الكافيةِ والسُّرعة) لوضعِ جميع الاحتمالاتِ فإنَّ بإمكانِه ضمانُ الفوزِ في بعضِ الأحيان.

دعونا نرى مِثالاً عن شجرةٍ تُمثِّلُ للحاسوبِ لُعبةَ XO:

في هذا المثال يلعب الحاسوب دور X وهذا شكل اللّعبة عند لحظةِ محاولةِ الحاسوب تقريرَ ما يجبُ أن يلعبه هو، وتُدعى الخوارزميّةُ الّتي استخدمها بـ MinMax، فهو في كلِّ خطوةٍ يحاول أن تكونَ القيمةُ الّتي يحصل عليها أعلى ما يمكن والقيمةُ الّتي يحصل عليها الخصم أقلّ ما يُمكن. يُمثّلُ هذا مبدأ (تعليم الآلة)، أحدُ أهمِّ تطبيقاتِ الذّكاء الصُّنعيّ.

فلنأخذ المثال الهامُ الآخَر وهو لُعبةُ الشّطرنج: تتألّف اللُّعبة من اللّاعبين، والحركات والتّنقلات الّتي يقومُ بها اللّاعبون، والنّتيجة (أي النّموذج الرّياضيّ الّذي يُحدّد ما هي نتيجة التّنقلات)، واختبار النّهاية (والّذي يُصبح صحيحاً عند انتهاء اللّعبة، فإنّ الحالات الّتي تنتهي عندها اللّعبة تُدعى بالحالات الانتهائيّة)، وتابع الأداءِ أو الهدف (وهو الّذي يُحدّد القيمةَ النّهائيّة الّتي يملكها لاعبٌ معيّنٌ عند انتهاءِ اللّعبة، في لُعبةِ الشّطرنج مثلاً، فإنّ القيم المُمكنة هي ربحٌ أو خسارةٌ أو تعادلٌ).

كما وَرَدَ في المقالِ السّابقِ من السّلسلة، فإنّه يمكن للحالةِ البدئيّة للُّعبة والتّنقلات والنّتائج أن تُعرِّف شجرةَ اللُّعبة، وهي شجرةٌ تكون فيها النّقاط هي حالاتُ اللُّعبة والخطوطُ الواصلةُ بينها هي التّنقلاتُ والحركاتُ الّتي تحدث في اللُّعبة.

إذاً يمكننا استخدام خورازميّة MinMax لاختبار احتمالات اللُّعبة ومعرفةِ الطّريقِ الأفضلِ لنسلُكَهُ، لكنّ المشكلةَ تكْمنُ في العددِ الكبيرِ للحالاتِ الّتي يتوجّبُ على الخوارزميّة أن تتفحّصها والّذي يزداد بشكلٍ كبيرٍ مع ازديادِ عُمْقِ الشّجرةِ الّتي تُمثِّلُ حالاتِ اللُّعبة والّتنقلات فيها، فهل يمكنُ تخفيضَ هذا العدد؟

اتضح أنَّه يمكن تقليلُ عددِ الحالاتِ الّتي على الخوارزميّة تفحُّصَها عن طريقِ تجاوزِ بعضِ الحالات الّتي لن تؤثِّرَ على القرار النّهائيّ.

كيف يمكن تحقيق ذلك؟

تكمُنُ الحيلةُ في تجنُّبِ توليدِ كاملِ الشّجرةِ عبر تجاوزِ بعض الحالاتِ أو حتّى بعضِ تفرُّعات الشّجرةِ الّتي لَيسَ لها تأثيرٌ على الحلِّ. لننظر في المثال التّالي:

إذا وصلنا عبر تطبيق خوارزميّة MinMax إلى التّالي:

سوف نلاحظ أنّه بالرّغمِ من عَدَمِ معرِفَةِ قيمَةِ كلٍّ من x وَ y فإنّنا تمكنَّا من معرفةِ الحلِّ وذلكَ لأنَّ المقارنة في السّطر الثّاني كانت بين 3 وَ 2 والرّقم الأصغرِ بين 2 وَ x وَ y وَالّذي لن يكونَ أكبرُ من 2، فالعدد الأكبرُ سيكون 3 بغضِّ النَّظرِ عن قيمةِ x وَ y. هذه العمليّةُ تُدعى بتشذيب الحل Pruning وتُسمّى التّقنيّةُ المُعتمدةُ Alpha - Beta Pruning. أمّا Alpha (α) فهي أفضلُ قيمة (أعلى قيمة) حصلنا عليها لغايةِ اللّحظةِ لدى كلِّ نقطةِ اختيارٍ على طول المسار لـ Max، وأمّا Beta (β) فهي أفضلُ قيمة (أصغر قيمة) حصلنا عليها لغايةِ اللّحظة لدى كلِّ نقطةِ اختيارٍ على طولِ المسارِ لـ Min. و هكذا يتمُّ باستمرارٍ تحديثُ قيمتي α وَ β و يتمُّ تجاوزُ باقي الخيارات والتّفرعات لدى نقطةٍ معيّنةٍ في الشّجرةِ عندما تُصبحُ قيمةَ النُّقطةِ الحاليّةِ أسوأ من قيمة α بالنّسبة لـ Max أو أسوأ من قيمة β بالنّسبة لـ Min.

يوضّح الشّكل التّالي فكرةَ الخوارزميّة بشكلٍ مُبَسّطٍ:

إن كانت m أفضل من n بالنّسبة للّاعب الأوّل، فإنّنا لن نصل إلى n أبداً أثناء اللّعبة.

بالرّغم من فعاليّة الخوارزميّات السّابقة، تواجِهُنا في الحياةِ الواقعيّةِ العديدُ من الأحداثِ غيرِ المتوقّعةِ الّتي تضعنا في مواقف لم نحسب لها حساباً. تحدث هذه المواقف في الألعاب الّتي تتضمّن عاملاً عشوائيّاً، كَرَمي الزّهر وتُدعى بالألعاب العشوائيّة.

من الأمثلَةِ على هذه الألعابِ لُعبةُ طاولةِ الزّهرِ الّتي تعتمد على المهارة وعلى الصُّدفةِ (الحظ) كذلك. فعندما يرمي اللّاعبُ الأوّلُ الزّهرَ ويتمكّنُ من معرفة حركاتِه المُمكنَةِ فإنَّه لن يكونَ قادراً على معرفة الرّقم الّذي سيحصلُ عليه اللّاعبُ الثّاني وبالتّالي لن يكونَ قادراً على معرفةِ الحركاتِ المُمكنَةِ لهذا اللّاعب. في هذه الحالة لا يُمكنُ بناءُ شجرةِ البحثِ للُّعبةِ كما قمنا ببنائها في لُعبةِ XO، إذ أنّها سوف تتضمّنُ نقاطاً للصُّدفَةِ (الحظ) بالإضافة إلى نقاط Min و Max و هذه النّقاط سوف تتضمّن كافةَ احتمالاتِ الزّهر الّتي يمكن أن يحصل عليها اللّاعب، و بالتّالي بدلاً من قيم minimax سوف نحصلُ على قيمٍ متوقّعةٍ هي Expected minimax الّتي تتضمّنُ عامِلَ نتيجةِ الزّهرِ الّتي سيحصلُ عليها اللّاعب.

بعد هذه الجولةِ في خوارزميّاتِ الذّكاء الصُّنعيّ للألعاب، هل أصبح فوز الإنسان على الآلة مُستحيلاً؟ حسناً لنراجع أحداثَ التّاريخِ لمعرفةِ ماذا حصل: لقد تمكّنَ الحاسوبُ Deep Blue من هزيمةِ بطلِ العالمِ في الشّطرنجِ غاري كاسباروف، ورُبَّما لن تستغرِبَ عندما تعلَمُ أنَّ هذا الحاسوبُ كانَ قادراً على تحرّي 30 بليون موقع في كلِّ حركةٍ، أي الوصول إلى عُمْقِ 14 عقدة في شجرة البحث. لقد تقاعد Deep Blue الآن وظهرت حواسيبَ أكثرَ قوةً منه لكنَّ الإنجازَ الّذي بَهرَنا به منذ فترةٍ كانَ تفوّق الحاسوب في لُعبةٍ مُختلفةٍ عن الشّطرنجِ وهي لُعبة Go الشّهيرة في آسيا والّتي يُميّزَها عدمُ القدرةِ على الفوز فيها عبرَ خوارزميّةِ البحثِ عن أفضلِ خطوةٍ مُمكنةٍ بسببِ العدد الهائلِ من الاحتمالات المُمكنةِ.

نُنهي في هذا المقالِ النّبذةَ المُختصَرةَ الّتي قدّمناها حول هذا القسم من خوارزميّاتِ الذّكاء الصُّنعيّ المُتعلّق بالألعاب، وسنتابعُ في المقالِ القادمِ الحديثَ حول جزءٍ شيّقٍ من الذّكاء الصُّنعيّ وهو المنطق.

-----------------------------------------------------------------

للفائدة بإمكانكم أيضاً الاطّلاع على المقال التالي:

الذكاء الصنعي يتقن لعبة صينية تعود إلى 2500 سنة! هنا

----------------------------------------------------------------

المصادر:

Russell، S. and Norvig، P. Artificial Intelligence A Modern Approach 3rd Edition

www.cs.cornell.edu/courses/cs4700/2011fa/lectures/06_adversarialsearch.pdf

هنا