ما مسألة البحث؟
يمكن صياغة كثير من مسائل الذكاء الاصطناعي بوصفها بحثًا في فضاء الحالات: فالمواقف الممكنة حالات، والأفعال التي تنقل بينها مؤثّرات، والمطلوب إيجاد سلسلة من المؤثّرات تقود من حالة البداية إلى حالة الهدف. وينطبق ذلك على إيجاد الطرق والألغاز وتخطيط مسارات الروبوتات وألعاب كالشطرنج. وتعود فكرة حلّ الآلة للمشكلات «بذكاء» إلى النقاشات حول اختبار تورينغ وتعريف الذكاء الاصطناعي.
البحث غير المستنير
- البحث بالعرض أولًا (BFS): يوسّع الحالات الأقرب إلى البداية أولًا. ويجد أقصر مسار حين تتساوى تكلفة الخطوات، لكنه يستهلك ذاكرة كبيرة.
- البحث بالعمق أولًا (DFS): يتتبع فرعًا واحدًا حتى نهايته قبل التراجع. ويستهلك ذاكرة قليلة، لكنه لا يضمن أقصر مسار وقد يضيع في الفضاءات اللانهائية.
- البحث بالتكلفة الموحّدة / خوارزمية ديكسترا: يوسّع الحالة ذات أدنى تكلفة حتى الآن g(n). وقد بيّن ديكسترا (1959) أنها تجد أقصر المسارات حين تكون التكاليف غير سالبة.
خوارزمية A*
نُشرت خوارزمية A* عام 1968 على يد بيتر هارت ونيلز نيلسون وبرترام رافائيل في معهد ستانفورد للأبحاث، انطلاقًا من تخطيط المسارات للروبوت «شيكي». وهي توسّع الحالات بحسب ترتيب دالة التقييم
f(n) = g(n) + h(n)
- g(n): التكلفة الفعلية من البداية إلى n.
- h(n): تقدير استدلالي للتكلفة المتبقية من n إلى الهدف، كالمسافة المستقيمة على الخريطة أو مسافة مانهاتن على الشبكة.
- المقبولية: إذا لم تبالغ h(n) قط في تقدير التكلفة المتبقية الحقيقية، فإن A* مضمونة لإيجاد مسار أمثل.
- الاتساق: إذا لم تنخفض h بأكثر من تكلفة الخطوة بين حالتين متجاورتين، فلا حاجة إلى إعادة توسيع أي حالة، فتتحسن الكفاءة.
- حين تكون h(n)=0 تؤول A* إلى خوارزمية ديكسترا؛ وكلما كان الاستدلال أدق قلّ عدد الحالات الموسَّعة.
البحث في الألعاب: الميني ماكس
في الألعاب الثنائية يسعى الخصم أيضًا إلى الفوز. وتقيّم خوارزمية الميني ماكس أوراق شجرة اللعبة (أو المواقف عند عمق محدد)، ثم ترفع القيمة العظمى في أدوار اللاعب (MAX) والقيمة الصغرى في أدوار الخصم (MIN) لاختيار أفضل نقلة. وأساسها النظري مبرهنة الميني ماكس لفون نويمان (1928)، وقد اقترح بحث كلود شانون عام 1950 استعمالها مع دالة تقييم لتمكين الحواسيب من لعب الشطرنج.
تقليم ألفا-بيتا
لأن الميني ماكس يفحص الشجرة كلها، تتضخم تكلفته مع العمق. ويتتبع تقليم ألفا-بيتا أفضل القيم المكتشفة حتى الآن (α: الحد الأدنى المضمون لـMAX؛ β: الحد الأقصى المضمون لـMIN) ويتخطى الفروع التي لا يمكن أن تؤثر في النتيجة. وهو يعطي الإجابة نفسها التي يعطيها الميني ماكس بجهد أقل بكثير؛ وقد بيّن كنوث ومور (1975) أنه مع الترتيب الأمثل للنقلات ينخفض عدد العقد المفحوصة إلى ما يقارب الجذر التربيعي.
الحدود والتطورات اللاحقة
- يحدّ الانفجار التوافقي من فاعلية الميني ماكس في الألعاب الضخمة جدًا كلعبة غو، مما قاد إلى بحث شجرة مونت كارلو المقترن بالتقييم بالشبكات العصبية.
- تحتفظ A* بحدود البحث كاملةً في الذاكرة، ولذلك تُستعمل في المسائل الكبيرة صيغ موفّرة للذاكرة مثل IDA*.
- تصميم استدلالات ودوال تقييم جيدة أمر صعب في ذاته ويتطلب معرفة بالمجال.
المراجع
- von Neumann, J. (1928). Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100, 295–320.
- Shannon, C. E. (1950). Programming a computer for playing chess. Philosophical Magazine, 41(314), 256–275.
- Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271.
- Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.
- Knuth, D. E., & Moore, R. W. (1975). An analysis of alpha-beta pruning. Artificial Intelligence, 6(4), 293–326.