التقيت بزميلي عميت بن بيست لأسأله عما يجري هناك في الجامعة
عميت هو طالب دكتوراه في قسم علوم الكمبيوتر في جامعة بن غوريون في النقب. وهو يقوم حاليًا بإعداد أطروحة الدكتوراه في مجموعة البروفيسور موشيه زيبر، حيث يبحث في استخدام البرمجة الجينية لتطوير اللاعبين في ألعاب الطاولة. وفي أوقات فراغه يكتب عميت على الموقع الإلكتروني لمنظمة المتشككين الإسرائيليين، ويلقي محاضرات هنا وهناك في موضوعات علمية شعبية.
أميت، فماذا تفعل هناك؟
تتناول مجموعتنا البحثية مجموعة متنوعة من المواضيع المتعلقة بالخوارزميات التطورية، وهو مجال في علوم الكمبيوتر ينتمي إلى الذكاء الاصطناعي. تعني الخوارزميات التطورية إنشاء محاكاة مجردة لعملية التطور عن طريق الانتقاء الطبيعي على جهاز كمبيوتر لإنتاج حلول أفضل للمشكلات. أنا أعمل في مجال فرعي يسمى البرمجة الجينية.
كيف تعمل البرمجة الجينية؟
الخطوة الأولى هي إنتاج مجموعة أولية من البرامج التي تحل مشكلة معينة، على سبيل المثال، كيفية لعب لعبة لوحية بشكل جيد. تتمثل استراتيجيتنا عادةً في تحسين عملية التطوير فقط لجزء من البرنامج الموجود داخل غلاف غير متغير. الجزء الذي يمر بعملية التطور هو ما يميز الأفراد بين السكان.
يمكنك ان تعطي مثالا؟
نعم، خذ على سبيل المثال لعبة الداما. جزء البرنامج الذي نقوم بتحسينه في التطور هو الجزء الذي يكتشف حالة اللوحة ويعيد الرقم. تصف "حالة اللوحة" حالة قانونية واحدة للعبة، وفي لعبة الداما سيتم تحديدها من خلال عدد القطع الموجودة على اللوحة ونوعها وموضعها، ومن هو التالي في الصف للعب. سيكون برنامج الصدفة بمثابة نوع من خوارزمية البحث.
كيف يحدد البرنامج اللاعب؟
من خلال تحديد استراتيجية لعبته. ويمكن لنفس اللاعب استخدام البرنامج للتحقق من الوضع الذي هو فيه حاليا، ومقارنته في مخيلته الحاسوبية بالمواقف الناتجة عن جميع التحركات القانونية الممكنة. يمكن لهذا اللاعب الآن اختيار الوضع الذي حصل على أفضل نتيجة. إذا أردنا لاعبًا أفضل، فيمكننا أن نطلب منه التحقق من عدة تحركات للأمام أيضًا. السعر هو وقت التشغيل، وينمو بشكل كبير.
هل يمكنك إعطاء مثال على الاختلافات في عدد السكان؟
نعم، على سبيل المثال، يمكن لبرنامج واحد في المجموعة أن يسجل حالة اللوحة من خلال الفرق بين عدد الأدوات لدى اللاعبين. فإذا زاد الفارق لصالحي فأنا راضٍ لأنني ربما أكلت أداة الخصم. يمكن لبرامج أخرى في المجتمع أن تحصل على منصب في مجلس الإدارة وفقًا لنفس المبدأ ولكنها تضيف شرطًا بأن الملك يستحق أكثر في العدد.
تم بناء هذه البرامج في بنية بيانات تسمى شجرة GP، وتتكون من عناصر مختلفة في شكل وحدات (انظر الشكل 2). نقوم بشكل عشوائي بإنشاء المجموعة الأولية لما لا يقل عن مائة برنامج أو شجرة باستخدام برنامج كتبناه لهذا الغرض.
كيف يمكنك تحديد هوية أفضل البرامج؟
وكما تقول العبارة المبتذلة في كرة القدم، الطاولة لا تكذب. لتحديد البرامج الناجحة (في لغة اللياقة البدنية) نعقد بطولة بين الأفراد من السكان. يحصل البرنامج على نقطة لكل فوز، ونصف نقطة للتعادل. كلما ارتفع ترتيب البرنامج في الجدول، زادت فرص اختياره للجيل القادم. على سبيل المثال، إذا كان عدد سكاننا 100 فرد، فسوف نختار 100 فرد لتكوين الجيل القادم. يمكن اختيار كل برنامج أكثر من مرة، وبالتالي سيتم اختيار البرامج التي تحتل مركزاً عالياً في الجدول عدداً كبيراً من المرات على حساب البرامج التي تحتل مركزاً منخفضاً. ومن بين البرامج المائة التي تم اختيارها في نهاية العملية، سننشئ الجيل القادم.
ماذا تقصد؟ كيف يتم إنتاج الجيل القادم؟
هناك إجراءان يتبعان عملية الاختيار ويهدفان إلى إحداث تغيير في عدد السكان. تسمى إحدى العمليات بالطفرة، حيث يتم اختيار شجرة فرعية بشكل عشوائي من الشجرة بأكملها التي تمثل اللاعب. يتم استبدال نفس الشجرة الفرعية بشجرة فرعية جديدة. مثال على الطفرة يمكن أن يكون استبدال الشجرة الفرعية x/11 من الشكل 2، إلى شجرة فرعية تعبر على سبيل المثال عن x-5 (انظر الشكل 3). نحن عادة نحدد احتمالية حدوث طفرة في الشجرة بحيث يتعرض حوالي عُشر الأشجار للطفرة.
العملية الثانية تسمى التقاطع وتحاكي التكاثر الجنسي. نختار شجرتين، وداخل كل شجرة يتم اختيار شجرة فرعية عشوائية. الآن نقوم بأحد الاحتمالين التاليين: التبديل بين الشجرتين الفرعيتين، أو تبديل الشجرة الفرعية بالشجرة التي كان أداؤها أقل جودة في الدورة في الشجرة الفرعية من الشجرة التي كان أداؤها أفضل.
بعد مرحلتي الطفرة والتقاطع، يتم الحصول على مجتمع يتكون من مائة فرد جديد، يسمى الجيل 1 (يسمى المجتمع الأولي الجيل 0). للحصول على جيل ثانٍ، سنكرر العملية: الدوري والاختيار والتكاثر (الطفرة والتهجين)، وهكذا حتى عدد محدد مسبقًا من الأجيال (انظر الشكل 2). يتم تحديد مستوى اللاعبين بشكل موضوعي من خلال اللعب ضد لاعب خارجي كتبناه بدون خوارزمية البرمجة الجينية. نهاية العملية هي البحث عن أفضل لاعب على مر الأجيال.
فماذا عن لعبة الداما؟
من أول الأشياء التي قمت بها بمساعدة البرمجة الجينية هو كتابة لاعب للعبة الداما العكسية، دون أن أكون خبيرًا كبيرًا في اللعبة. لقد تركت التطور يقوم بالعمل نيابة عني. لقد أوضحت لاحقًا أنه يمكن أيضًا استخدام هذه العملية في لعبة الداما العادية والألعاب الأخرى. لقد أتاحت لي البرمجة الجينية كتابة لاعبين ناجحين لمختلف الألعاب دون الحاجة إلى بذل الكثير من الجهد بالإضافة إلى ما استثمرته بالفعل.
يبدو رائعًا، هل هناك "لكن" في مكان ما؟
انظر، يجب أن يكون مفهومًا أننا محدودون للغاية في عدد التحركات الأمامية التي نسمح للاعبين بحسابها. بالنسبة لعدد كبير من النقلات لن نتمكن من إنهاء البطولات من عملية الاختيار في وقت معقول لأن وقت التشغيل يزداد كما ذكرنا بشكل كبير. يمكن أيضًا توضيح أنه إذا أنتجنا لاعبًا في عملية تطور حيث كان هناك فحص لعدد معين من التحركات الأمامية، فلن نتمكن من تحسين جودته بشكل ملحوظ بطريقة بسيطة عن طريق زيادة عدد التحركات الأمامية التي يتحقق منها. أي أن المنتج النهائي هو الأمثل للظروف التي تم إنشاؤه فيها.
אז מה עושים؟
تحاول أن تكون ذكية. لنفترض أنه في موقف معين على اللوحة، تؤدي كل خطوة إلى الأمام إلى عشرة احتمالات عمل. إذا قمنا بالتحقق من خمسة منها فقط لكل حركة، فيمكننا التحقق من المزيد من التحركات المقبلة. لاختيار أفضل خمسة احتمالات من بين العشرة، يمكننا الاستعانة باللاعب الذي يرى خطوة واحدة فقط للأمام. تسمى هذه العملية التقليم في اللغة المهنية. خلال البحث تمكنا من إظهار أنه بعد التقليم نكسب مرتين. أولاً، هؤلاء اللاعبون أفضل، وثانيًا، يمكن تحسينهم بشكل مباشر عن طريق تقليل التقليم، على سبيل المثال في المثال هنا لاختيار سبعة محتملين من أصل عشرة بدلاً من خمسة، دون مزيد من العملية التطورية.
كيف يمكنك تلخيص مزايا الطريقة؟
تتيح البرمجة الجينية إمكانية التعلم والتحسين في اللعبة، دون معرفة أي شيء عنها باستثناء الحركات الأساسية. الطريقة عامة ويمكن تكييفها بسهولة مع المشكلات المختلفة، ويمكنها أيضًا أن تنجح في حل المشكلات التي لا يكون فيها المنطق البشري ميزة.
----------------------
يسعدني أن ألتقي وأتحدث مع أي طالب بحث (ربما أنت؟) يرغب في المشاركة ويخبرني قليلاً عما يفعله (وكل ذلك مقابل محادثة ليست طويلة جدًا). يمكنك الاتصال بي من خلال نموذج الاتصال.
حان الوقت لتخبر الجميع بما تفعله، ربما سيفهمون هذه المرة أيضًا 🙂
يسعدني أن ألتقي وأتحدث مع أي طالب بحث (ربما أنت؟) يرغب في المشاركة ويخبرني قليلاً عما يفعله (وكل ذلك مقابل محادثة ليست طويلة جدًا). يمكنك التواصل معي عبر نموذج الاتصال بنا.
حان الوقت لإخبار الجميع بما تفعله، ربما سيفهمون هذه المرة أيضًا
تم نشر المقال على مدونة أورين شايع.إلى حد ثابت"
