لغة وصف اللعبة

الموسوعة الحرة

لغة وصف الألعاب (GDL) هي لغة برمجة منطقية متخصصة صممها مايكل جينسيريث . يهدف تطوير GDL إلى تمكين تطوير وكلاء ذكاء اصطناعي قادرين على لعب الألعاب بشكل عام . وهي جزء من مشروع لعب الألعاب العام في جامعة ستانفورد . تُعد GDL أداةً للتعبير عن تعقيدات قواعد اللعبة وديناميكياتها بشكل مفهوم لأنظمة الذكاء الاصطناعي ، وذلك من خلال الجمع بين البنى المنطقية والمبادئ التصريحية .

عمليًا، يُستخدم GDL غالبًا في مسابقات الألعاب العامة والأبحاث. في هذه السياقات، يُستخدم GDL لتحديد قواعد الألعاب التي يُتوقع من وكلاء الذكاء الاصطناعي لعبها. يستغل مطورو وباحثو الذكاء الاصطناعي GDL لإنشاء خوارزميات قادرة على فهم الألعاب والتفاعل معها بناءً على قواعدها. يتيح استخدام GDL تطوير وكلاء ذكاء اصطناعي يتمتعون بقدرة عالية على التكيف، وقادرين على المنافسة في سيناريوهات متنوعة.

الغرض من برنامج رخصة التدريس التدريجي

أشار جينسيريث، في مقالٍ نُشر في مجلة نيو ساينتست ، إلى أنه على الرغم من قدرة ديب بلو على لعب الشطرنج بمستوى أستاذ كبير ، إلا أنه عاجزٌ تمامًا عن لعب الداما لأنه لاعبٌ متخصصٌ في ألعابٍ محددة. [ 1 ] يمكن وصف كلٍّ من الشطرنج والداما باستخدام لغة وصف الألعاب العامة (GDL). وهذا يُتيح بناء لاعبين عامين قادرين على لعب كلتا اللعبتين، وأي لعبةٍ أخرى يُمكن وصفها باستخدام GDL.

مواصفة

بناء الجملة

لغة GDL هي صيغة معدلة من لغة Datalog ، وبنيتها متشابهة إلى حد كبير. وعادةً ما تُكتب باستخدام صيغة البادئة . تبدأ المتغيرات بـ ?. [ 2 ]

الكلمات المفتاحية

فيما يلي قائمة بالكلمات الرئيسية في لغة GDL، بالإضافة إلى وصف موجز لوظائفها:

distinct
يُستخدم هذا المسند لاشتراط أن يكون المصطلحان مختلفين نحويًا.
does
يعني الشرط أن اللاعب (أو الدور ) يقوم بالتحرك في حالة اللعبة الحالية .(does?r?m)?r?m
goal
يتم استخدام المسند لتحديد قيمة الهدف (عادةً ما يكون عددًا طبيعيًا بين 0 و 100) للدور في الحالة الحالية.(goal?r?n)?n?r
init
يشير هذا المسند إلى حقيقة تتعلق بحالة اللعبة الأولية.
legal
يعني هذا الشرط أن هذا تحرك مسموح به للدور في الوضع الحالي.(legal?r?m)?m?r
next
يشير هذا المسند إلى حقيقة تتعلق بحالة اللعبة التالية.
role
يُستخدم هذا الشرط لإضافة اسم اللاعب.
terminal
هذا الشرط يعني أن الحالة الحالية هي حالة نهاية اللعبة.
true
يشير هذا المسند إلى حقيقة تتعلق بحالة اللعبة الحالية.

قواعد

يوفر وصف اللعبة في GDL قواعد كاملة تحدد لاعبي اللعبة، والحالة الأولية، والتحركات الصالحة، وكيفية تحديث حالة اللعبة، وكيفية انتهاء اللعبة، وكيفية تحديد الفائز.

اللاعبون

الحقائق التي تحدد الأدوار في اللعبة. على سبيل المثال، يمكن للعبة إكس-أو التي يلعبها لاعبان أن تحدد اللاعبين في دوري تطوير الألعاب (GDL) من خلال (role xplayer)و (role oplayer).

الحالة الابتدائية

قواعد تتضمن جميع الحقائق المتعلقة بحالة اللعبة الأولية. يصف المثال التالي لوحة لعبة إكس-أو فارغة مكونة من ثلاثة صفوف وثلاثة أعمدة، حيث يقوم اللاعب س بالخطوة الأولى:

( تهيئة ( الخلية 1 فارغة 1 )) ... ( تهيئة ( الخلية 3 فارغة 3 )) ( تهيئة ( التحكم في مشغل إكس بلاير ))

قواعد تصف كل حركة يمكن للاعب القيام بها، بناءً على ظروف اللعبة الحالية. يمكن للاعب في لعبة إكس-أو وضع علامة على خانة إذا كانت فارغة، وكان دوره في اللعب. في لغة GDL:

( <= ( قانوني ؟ لاعب ( علامة ؟ م ؟ ن )) ( صحيح ( خلية ؟ م ؟ ن فارغة )) ( صحيح ( تحكم ؟ لاعب )))

تحديث حالة اللعبة

قواعد تصف جميع الحقائق المتعلقة بالحالة التالية بالنسبة للحالة الحالية والتحركات التي قام بها اللاعبون. على سبيل المثال:

( <= ( next ( cell ?m ?n x )) ( does xplayer ( mark ?m ?n ))) ( <= ( next ( cell ?m ?n o )) ( does oplayer ( mark ?m ?n )))

إنهاء الخدمة

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

( ≤ الطرفية ( السطر س )) ( ≤ الطرفية ( السطر ع )) ( ≤ الطرفية غير مفتوحة اللوحة )

أهداف الحالة

القيم التي تحدد اللاعب الفائز في نهاية المطاف. مثال على ذلك:

( ≤ ( الهدف x اللاعب 100 ) ( السطر x )) ( ≤ ( الهدف oplayer 0 ) ( السطر x ))

الإضافات

GDL-II

يمكن للغة وصف الألعاب المحدودة ذات عدد اللاعبين غير محدد. مع ذلك، لا يمكنها وصف الألعاب التي تتضمن عنصرًا من الصدفة (مثل رمي النرد ) أو الألعاب التي يمتلك فيها اللاعبون معلومات غير كاملة عن حالة اللعبة الحالية (كما هو الحال في العديد من ألعاب الورق ، حيث لا تكون أوراق الخصوم مرئية). يُوسّع امتدادٌ للغة وصف الألعاب، يُعرف باسم لغة وصف الألعاب ذات المعلومات غير الكاملة ( GDL-II )، اللغةَ باستخدام كلمتين مفتاحيتين، seesوهما و random، اللتان تسمحان بوصف عناصر الصدفة والمعلومات غير الكاملة. [ 3 ] تعني العبارة أن اللاعب يُدرك دوره في حالة اللعبة التالية. أما الثابت فيشير إلى لاعب مُحدد مسبقًا يختار تحركاته عشوائيًا.(sees?r?p)?r?prandom

فيما يلي مثال من وصف GDL-II للعبة الورق تكساس هولدم :

( <= ( يرى ؟اللاعب ؟ البطاقة ) ( يقوم بتوزيع عشوائي ( توزيع_الوجه_للأسفل ؟ اللاعب ؟البطاقة ))) ( < = ( يرى ؟الدور ؟ الدور ) ( يقوم بتوزيع عشوائي ( توزيع_النهر ؟البطاقة )))

GDL-III

كما ابتكر مايكل ثيلشر امتدادًا آخر، وهو GDL-III ، وهو GDL عام مع معلومات غير كاملة واستبطان ، يدعم تحديد الألعاب المعرفية - تلك التي تتميز بقواعد تعتمد على معرفة اللاعبين. [ 4 ]

طرق أخرى لتمثيل اللعبة

في نظرية الألعاب الكلاسيكية ، يمكن صياغة الألعاب في صيغتين: الصيغة الموسعة والصيغة العادية . أما في نظرية الألعاب التعاونية ، فتُمثل الألعاب باستخدام الدوال المميزة. تسمح بعض الفئات الفرعية للألعاب بتمثيلات خاصة بأحجام أصغر، تُعرف أيضًا بالألعاب المختصرة . مع مرور الوقت، طُوّرت صيغ ولغات أخرى لتمثيل أنواع الألعاب المختلفة، ويعود ذلك جزئيًا إلى احتياجات البحث متعدد التخصصات . [ 5 ] تتضمن بعض هذه التمثيلات البديلة جوانب متعلقة بالزمن.

اسمسنةتمت صياغتها رسميًا معنوع اللعبةالجانب الزمني
لعبة الازدحام [ 6 ]1973الوظائفمجموعة فرعية من ألعاب اللاعبين المتعددين ، تحركات متزامنةلا
الشكل التسلسلي [ 7 ]1994المصفوفاتألعاب ثنائية اللاعبين ذات معلومات غير كاملةلا
الألعاب المحددة بوقت [ 8 ] [ 9 ]1994الوظائفألعاب ثنائية اللاعبيننعم
حفل [ 10 ]1997منطقألعاب معلومات غير كاملة لـ n لاعبلا
الألعاب الرسومية [ 11 ] [ 12 ]2001الرسوم البيانية ، الدوالألعاب متعددة اللاعبين، تحركات متزامنةلا
ألعاب التأثير المحلي [ 13 ]2003الوظائفمجموعة فرعية من ألعاب اللاعبين المتعددين ، تحركات متزامنةلا
شبكات لعبة بيتري [ 14 ]2006شبكات بتريألعاب حتمية متعددة اللاعبين، تحركات متزامنةلا
الألعاب المستمرة [ 15 ]2007الوظائفمجموعة فرعية من ألعاب اللاعبين الاثنين ذات المعلومات غير الكاملةنعم
التفاعلات الاستراتيجية لشبكة بيتري [ 16 ] [ 17 ]2008شبكات بتريألعاب معلومات غير كاملة لـ n لاعبنعم
ألعاب الرسوم البيانية الحركية [ 18 ]2012الرسوم البيانية، الدوالألعاب متعددة اللاعبين، تحركات متزامنةلا

التطبيقات

تصف ورقة بحثية صدرت عام 2016 "خوارزمية متعددة المستويات تقوم بتجميع وصف عام للعبة في GDL إلى مُستدل مُحسَّن بلغة منخفضة المستوى ". [ 19 ]

استخدمت ورقة بحثية نُشرت عام 2017 لغة GDL لنمذجة عملية الوساطة لحل نزاع بين طرفين، وقدمت خوارزمية تستخدم المعلومات المتاحة للقيام بذلك بكفاءة. [ 20 ]

انظر أيضاً

مراجع

  1. ↑ بيفر، سيليست (29 يوليو 2006). "إنتاج أفضل روبوتات لعب الألعاب - تقنية - 29 يوليو 2006 - نيو ساينتست تك" . مؤرشف من الأصل في 11 أغسطس 2007.
  2. ↑ لوف، ن؛ جينسيريث، م؛ هينريش، ت (2006). "لعب الألعاب بشكل عام: مواصفات لغة وصف الألعاب. تقرير فني LG-2006-01" (ملف PDF) . جامعة ستانفورد . جامعة ستانفورد، ستانفورد. مؤرشف من الأصل (ملف PDF) في 24 فبراير 2021. تم الاطلاع عليه في 1 يوليو 2019 .
  3. ↑ ثيلشر، م (2010). فوكس، م؛ بول، د (محرران). "لغة وصف عامة للألعاب ذات المعلومات غير الكاملة" . وقائع المؤتمر الرابع والعشرين للجمعية الأمريكية للذكاء الاصطناعي، AAAI 2010. أتلانتا: مطبعة الجمعية الأمريكية للذكاء الاصطناعي . تم الاطلاع عليه في 1 يوليو 2019 .
  4. ↑ ثيلشر، مايكل (2017). "GDL-III: لغة وصفية للعب الألعاب العامة المعرفية" (ملف PDF) . وقائع المؤتمر الدولي المشترك السادس والعشرين حول الذكاء الاصطناعي . IJCAI. ISBN 978-0-9992411-0-3تم الاطلاع عليه بتاريخ 1 يوليو 2019 .
  5. ↑ تاجيو، رستم (3 مايو 2011). "إذا كانت هناك حاجة إلى أكثر من مجرد النمذجة التحليلية للتنبؤ بالتفاعل الاستراتيجي للوكلاء الحقيقيين". arXiv : 1105.0558 [ cs.GT ].
  6. ↑ روزنتال، روبرت و. (ديسمبر 1973). "فئة من الألعاب التي تمتلك توازنات ناش ذات استراتيجية خالصة". المجلة الدولية لنظرية الألعاب . 2 (1): 65-67 . doi : 10.1007/BF01737559 . S2CID 121904640 . 
  7. ↑ كولر، دافني ؛ ميغيدو، نمرود ؛ فون ستينجل، برنارد (1994). "خوارزميات سريعة لإيجاد استراتيجيات عشوائية في أشجار الألعاب". وقائع الندوة السنوية السادسة والعشرين لجمعية ACM حول نظرية الحوسبة - STOC '94 . الصفحات 750-759 . doi : 10.1145/195058.195451 . ISBN  0-89791-663-8. S2CID 1893272 . 
  8. ↑ ألور، راجيف؛ ديل، ديفيد ل. (أبريل 1994). "نظرية الأوتوماتا الموقوتة" . علوم الحاسوب النظرية . 126 (2): 183-235 . doi : 10.1016/0304-3975(94)90010-8 .
  9. ↑ توملين، سي جيه؛ ليغيروس، جيه؛ شانكار ساستري، إس. (يوليو 2000). "نهج نظرية الألعاب لتصميم المتحكمات للأنظمة الهجينة". وقائع معهد مهندسي الكهرباء والإلكترونيات . 88 (7): 949-970 . رمز Bibcode : 2000IEEEP..88..949T . CiteSeerX 10.1.1.129.8347 . doi : 10.1109/5.871303 . S2CID 1844682 .  
  10. ↑ كولر، دافني؛ فايفر، آفي (1997). "التمثيلات والحلول لمسائل نظرية الألعاب" (ملف PDF) . الذكاء الاصطناعي . 94 ( 1-2 ): 167-215 . doi : 10.1016/S0004-3702(97)00023-4 .
  11. ↑ مايكل، مايكل كيرنز؛ ليتمان، مايكل ل. (2001). "النماذج الرسومية لنظرية الألعاب". في UAI : 253-260 . CiteSeerX 10.1.1.22.5705 . 
  12. ↑ كيرنز، مايكل؛ ليتمان، مايكل ل.؛ سينغ، ساتيندر (7 مارس 2011). "النماذج البيانية لنظرية الألعاب". arXiv : 1301.2281 [ cs.GT ].
  13. ↑ ليتون-براون، كيفن؛ تينينهولتز، موشيه (2003). "ألعاب التأثير المحلي" . IJCAI'03: وقائع المؤتمر الدولي المشترك الثامن عشر حول الذكاء الاصطناعي : 772-777 .
  14. ↑ كليمبنر، خوليو (2006). "نمذجة ألعاب أقصر مسار باستخدام شبكات بيتري: نظرية قائمة على ليابونوف" . المجلة الدولية للرياضيات التطبيقية وعلوم الحاسوب . 16 (3): 387-397 . ISSN 1641-876X . 
  15. ↑ سانيكوف، يولي (سبتمبر 2007). "ألعاب ذات أفعال غير قابلة للملاحظة بشكل كامل في زمن مستمر" (ملف PDF) . Econometrica . 75 (5): 1285–1329 . doi : 10.1111/j.1468-0262.2007.00795.x .
  16. ↑ تاجيو، رستم (ديسمبر 2008). "ألعاب بتري متعددة العوامل". المؤتمر الدولي لعام 2008 حول الذكاء الحسابي لنمذجة التحكم والأتمتة . الصفحات 130-135 . doi : 10.1109/CIMCA.2008.15 . ISBN  978-0-7695-3514-2. S2CID 16679934 . 
  17. ↑ تاجيو، رستم (2009). "حول نماذج شبكات بتري متعددة العوامل لحساب الألعاب المحدودة الموسعة". تحديات جديدة في الذكاء الجماعي الحسابي . دراسات في الذكاء الحسابي. المجلد 244. سبرينغر. الصفحات 243-254 . doi : 10.1007/978-3-642-03958-4_21 . ISBN   978-3-642-03957-7.
  18. ↑ بهات، نافين؛ ليتون-براون، كيفن (11 يوليو 2012). "حساب توازنات ناش لألعاب الرسم البياني للحركة". arXiv : 1207.4128 [ cs.GT ].
  19. ↑ كوالسكي، جاكوب؛ شيكولا، ماريك (2013). " بناء مُجمِّع لغة وصف الألعاب" . مؤتمر الذكاء الاصطناعي 2013: التطورات في الذكاء الاصطناعي: المؤتمر الأسترالي الآسيوي المشترك السادس والعشرون، دنيدن، نيوزيلندا، 1-6 ديسمبر 2013. وقائع المؤتمر . الصفحات 234-245 . تاريخ الاطلاع: 1 يوليو 2019 . 
  20. ^ دي جونج ، ديف. تريسكاك، توماس؛ سييرا، كارليس. سيموف، سمعان؛ لوبيز دي مانتاراس، رامون (2017). “استخدام لغة وصف اللعبة لحل النزاعات عن طريق الوساطة”. الذكاء الاصطناعي والمجتمع . 2017 (4). سبرينغر: 767–784 . دوى : 10.1007/s00146-017-0790-8 . S2CID 22738517 .