بازی کردن عمومی

بازی کردن عمومی (GGP) طراحی برنامه‌های هوش مصنوعی است تا بتوان بیش از یک بازی را با موفقیت انجام داد.[۱][۲][۳] برای بسیاری از بازی‌ها مانند شطرنج، کامپیوترها برنامه‌ریزی شده‌اند تا این بازی‌ها را با استفاده از یک الگوریتم طراحی شده خاص انجام دهند، که نمی‌تواند به بازی‌های دیگر این برنامه تعمیم پیدا کند. به عنوان مثال، یک برنامه رایانه ای که شطرنج بازی می‌کند نمی‌تواند بازی چکرز را انجام دهد. بازی عمومی به عنوان یک نقطه عطف ضروری در مسیر هوش جامع مصنوعی محسوب می‌شود.

بازی ویدیویی کردن عمومی (GVGP) یکی دیگر از کاربردهای GGP است که با توجه به هدف بازی‌های ویدیویی تنظیم می‌شود. در بازی سازی عمومی قوانین بازی باید توسط چند بازیکن تکرار شود مانند TD-Gammon[۴] یا به صورت دستی این قوانین در یک زبان خاص و از پیش تعریف شده برای بازیکنان ارسال شود[۵][۶]

درواقع GGP از سال ۲۰۱۳ به دنبال رویکرد یادگیری تقویت عمیق هست مانند توسعه برنامه ای که بر اساس یادگیری عمیق بتواند بازی آتاری ۲۶۰۰ را یاد بگیرد[۷][۸][۹][۱۰] و توسط این یادگیری بتواند بازی‌های سیستم سرگرمی نینتندو که در نسل‌های بعد ارایه می‌شود را انجام دهد[۱۱][۱۲][۱۳]

اولین کاربرد تجاری فناوری بازی عمومی، Zillions of Games در سال ۱۹۹۸ بود. بازی عمومی نیز برای نمایندگان تجارت در مدیریت زنجیره تأمین و پس از آن در مذاکره‌ها قیمت در حراج‌های آنلاین از سال ۲۰۰۳ به بعد پیشنهاد شد.[۱۴][۱۵][۱۶]

تاریخ

ویرایش

در سال ۱۹۹۲، بارنی پل مفهوم Meta-Game Playing را تعریف کرد و سیستم "MetaGame" را توسعه داد. این اولین برنامه ای بود که به‌طور خودکار قوانین بازی‌های شطرنج مانند را تولید می‌کند و یکی از اولین برنامه‌هایی است که از تولید بازی‌های خودکار استفاده می‌کند. سپس بارنی پل سیستم Metagamer را توسعه داد.[۱۷] این سیستم با توجه به تعریف قوانین بازی به زبانی خاص به نام Game Description Language، بدون هیچ گونه تعامل انسانی پس از تولید بازی‌ها، توانست تعدادی از بازی‌های شطرنج مانند را انجام دهد.[۱۸]

در سال ۱۹۹۸، سیستم تجاری Zillions of Games توسط جف مالت و مارک لفلر ساخته شد. این سیستم برای تعریف قوانین بازی از زبانی مانند LISP استفاده می‌کرد. Zillions of Games عملکرد ارزیابی را به‌طور خودکار از قوانین بازی بر اساس تحرک، ساختار صفحه و اهداف بازی به دست می‌آورد. همچنین الگوریتم‌ها را در سیستم‌های شطرنج رایانه ای به کار می‌برد: هرس آلفا بتا با ترتیب حرکت، جداول جابجایی و غیره.[۱۹] این بسته در سال ۲۰۰۷ با افزودن پلاگین Axiom، یک موتور متا بازی جایگزین که یک زبان برنامه‌نویسی کاملاً مبتنی بر Forth را در خود دارد، تمدید شد.

در سال ۱۹۹۸، z-Tree توسط Urs Fischbacher ساخته شد.[۲۰] z-Tree اولین و پر استنادترین ابزار نرم‌افزاری برای اقتصاد تجربی است. z-Tree امکان تعریف قوانین بازی در زبان z-Tree را برای آزمایش‌ها تئوری بازی با افراد انسانی فراهم می‌کند. همچنین امکان تعریف بازیکنان رایانه ای را نیز فراهم می‌کند، که در یک بازی با موضوع‌های انسانی شرکت می‌کنند.[۲۱]

در سال ۲۰۰۵، بازی عمومی پروژه استنفورد تأسیس شد.[۳]

در سال ۲۰۱۲، توسعه PyVGDL آغاز شد.[۲۲]

پیاده‌سازی‌های GGP

ویرایش

پروژه استنفورد

ویرایش

General Game Playing پروژه ای از گروه منطق استنفورد دانشگاه استنفورد، کالیفرنیا است که هدف آن ایجاد بستری برای بازی عمومی است. این شناخته شده‌ترین تلاش برای استانداردسازی GGP AI است و به‌طور کلی به عنوان استاندارد سیستم‌های GGP دیده می‌شود. این بازی‌ها با مجموعه قوانینی که در زبان توضیح بازی ارائه می‌شوند، تعریف می‌شوند. برای انجام بازی‌ها، بازیکنان با یک سرور میزبان بازی ارتباط برقرار می‌کنند[۲۳][۲۴] که از نظر قانونی بودن حرکت را کنترل می‌کند و بازیکنان را از تغییرهای وضعیت مطلع می‌کند.

از سال ۲۰۰۵، سالانه مسابقه‌های بازی عمومی در کنفرانس AAAI برگزار می‌شود. این مسابقه با ضبط عملکرد آنها در هر بازی، توانایی‌های AI رقیب را برای انجام انواع بازی‌های مختلف قضاوت می‌کند. در مرحله اول مسابقه، داوطلبان با توجه به توانایی انجام حرکت‌های قانونی، دستیابی به برتری و بازی‌های سریعتر قضاوت می‌شوند. در مرحله بعدی، هوش مصنوعی در بازی‌های پیچیده‌ای که به‌طور فزاینده ای پیچیده‌ هستند، در برابر یکدیگر قرار می‌گیرند. هوش مصنوعی که در این مرحله بیشترین موفقیت را به دست می‌آورد در این مسابقه برنده می‌شود و تا سال ۲۰۱۳ سازنده آن یک جایزه ۱۰ هزار دلاری می‌گرفت.[۱۷] تاکنون، برنامه‌های زیر پیروز بودند:[۲۵]

رویکردهای دیگر

ویرایش

سیستم‌های بازی عمومی دیگری نیز وجود دارند که از زبانهای خاص خود برای تعریف قوانین بازی استفاده می‌کنند. سایر نرم‌افزارهای عمومی بازی شامل:

  • سیستمی به نام AiAi توسط Stephen Tavener (توسعه دهنده قبلی Zillions)[۲۹] که به سال ۲۰۱۵ برمی گردد و از اواخر سال ۲۰۱۷ فعالانه توسعه می‌یابد.[۳۰][۳۱]
  • سیستمی به نام PolyGamo Player توسط David M. Bennett در سپتامبر ۲۰۱۷ بر اساس موتور بازی یونیتی منتشر شد.[۳۲]

پیاده‌سازی‌های GVGP

ویرایش

به‌طور بالقوه می‌توان از GVGP برای ایجاد هوش مصنوعی بازی‌های ویدیویی و همچنین «آزمایش محیط‌های بازی، از جمله مواردی که به‌طور خودکار با استفاده از تولید محتوای مرحله ای ایجاد می‌شوند و یافتن نقاط ضعف احتمالی در بازی که یک بازیکن انسانی می‌تواند سوءاستفاده کند ،» استفاده کرد.[۶] از GVGP همچنین برای تولید قوانین بازی و تخمین کیفیت بازی بر اساس پروفایل‌های عملکرد الگوریتم نسبی (RAPP) استفاده شده‌است که تفاوت مهارت را که یک هوش مصنوعی خوب و هوش مصنوعی انجام می‌دهد مقایسه می‌کند.[۳۳]

مسابقه هوش مصنوعی General Video Game (GVGAI بایگانی‌شده در ۳ مه ۲۰۱۵ توسط Wayback Machine) از سال ۲۰۱۴ برگزار می‌شود. در این مسابقه، به جای بازی‌های رومیزی که در مسابقه GGP استفاده می‌شود، از بازی‌های ویدئویی دو بعدی مشابه (و بعضاً مبتنی بر) دوره‌های بازی و کنسول مربوط به دوران دهه ۸۰ استفاده می‌شود. این یک روش برای محققان و شرکت کنندگان ارائه داده‌است تا بهترین الگوریتم‌های بازی عمومی ویدیویی خود را آزمایش و مقایسه کنند. این مسابقه دارای یک چارچوب نرم‌افزاری مرتبط با تعداد زیادی بازی است که به زبان توضیح‌های بازی ویدیویی (VGDL) نوشته شده‌است، که نباید با GDL اشتباه گرفته شود و یک زبان برنامه‌نویسی با استفاده از معانی و دستورهای ساده است که به راحتی تجزیه می‌شود. یک مثال برای VGDL PyVGDL است که در سال ۲۰۱۳ ساخته شده‌است.[۵][۲۲] بازی‌های مورد استفاده در GVGP، در حال حاضر، غالباً بازی‌های دو بعدی هستند، زیرا ساده‌ترین آنها برای تعیین کمیت است.[۳۴] برای ساده‌سازی فرایند هوش مصنوعی که می‌تواند بازی‌های ویدیویی را تفسیر کند، بازی‌ها بصورت دستی در VGDL نوشته می‌شوند. VGDL می‌تواند برای توصیف یک بازی و تولید رویه سطوح، با استفاده از Answer Set Programming (ASP) و یک الگوریتم تکاملی (EA) استفاده شود. سپس می‌توان از GVGP برای بررسی اعتبار سطوح رویه ای و همچنین دشواری یا کیفیت سطوح بر اساس عملکرد یک عامل استفاده کرد.[۳۵]

الگوریتم‌ها

ویرایش

از آنجا که GGP AI باید برای انجام چندین بازی طراحی شده باشد، طراحی آن نمی‌تواند به الگوریتم‌های ایجاد شده برای یک بازی خاص تکیه کند. در عوض، هوش مصنوعی باید با استفاده از الگوریتم‌هایی طراحی شود که روش‌های آنها را می‌توان در طیف گسترده‌ای از بازی‌ها به کار برد. هوش مصنوعی همچنین باید یک روند مداوم باشد، که بتواند به جای خروجی حالت‌های قبلی، با وضعیت فعلی خود سازگار شود. به همین دلیل، تکنیک‌های حلقه باز اغلب بیشترین تأثیر را دارند.[۳۶]

یک روش محبوب برای توسعه GGP AI الگوریتم جستجوی درخت مونت کارلو (MCTS) است.[۳۷] برای استفاده بهتر از بازی‌های خاص و همچنین سازگاری آن با بازی‌های ویدئویی، تغییرهای MCTS که اغلب همراه با روش UCT استفاده می‌شود (بهینه‌سازی که برای درختان اعمال می‌شود) ارائه شده‌است.[۳۸][۳۹][۴۰] یکی دیگر از تغییرهای الگوریتم‌های جستجوی درخت استفاده شده، جستجوی مستقیم پهنای مستقیم (BFS) است که در آن یک گره فرزند به حالت فعلی برای هر اقدام موجود ایجاد می‌شود و از هر فرزند که طبق بالاترین پاداش متوسط بازدید می‌شود حرکت می‌کند، تا زمانی که بازی تمام شود یا اجرا شود خارج از زمان[۴۱] در هر روش جستجوی درخت، هوش مصنوعی اقدام‌های بالقوه را شبیه‌سازی می‌کند و هر کدام را براساس میانگین بالاترین پاداش هر مسیر، از نظر امتیازهای کسب شده، رتبه‌بندی می‌کند.

فرضیه‌ها

ویرایش

به منظور تعامل با بازی‌های مختلف، الگوریتم‌ها باید با این فرض که همه ویژگی‌های مشترک بازی‌ها دارند عمل کنند. در کتاب نیمه واقعی: بازی‌های ویدئویی بین دنیای واقعی و دنیای خیالی، Jesper Juul تعریف زیر را از بازی‌ها ارائه می‌دهد: بازی‌ها براساس قوانین تعریف می‌شوند، دارای نتایج متغیر هستند و سپس نتایج مختلف ارزش‌های مختلف ایجاد می‌کنند و تلاش بازیکن بر نتایج تأثیر می‌گذارد. بازیکن و نتیجه بازی به هم وابسته هستند و نتیجه بازی قابل بحث هست.[۴۲] با استفاده از این فرضیه‌ها، می‌توان هوش مصنوعی بازی را با کمی سازی ورودی بازیکن، نتایج بازی و نحوه اعمال قوانین مختلف و استفاده از الگوریتم‌ها برای محاسبه مطلوب‌ترین مسیر ایجاد کرد.[۳۴]

منابع

ویرایش
  1. Pell, Barney (1992). L. Allis (ed.). "Metagame: a new challenge for games and learning" [Heuristic programming in artificial intelligence 3–the third computerolympiad] (PDF). Ellis-Horwood. Archived from the original (PDF) on 17 February 2020. Retrieved 24 November 2020. {{cite journal}}: Cite journal requires |journal= (help); Missing |editor1= (help)
  2. Pell, Barney (1996). "A Strategic Metagame Player for General Chess-Like Games". Computational Intelligence (به انگلیسی). 12 (1): 177–198. doi:10.1111/j.1467-8640.1996.tb00258.x. ISSN 1467-8640.
  3. ۳٫۰ ۳٫۱ Genesereth, Michael; Love, Nathaniel; Pell, Barney (15 June 2005). "General Game Playing: Overview of the AAAI Competition". AI Magazine (به انگلیسی). 26 (2): 62. doi:10.1609/aimag.v26i2.1813. ISSN 2371-9621.
  4. Mnih, Volodymyr; Kavukcuoglu, Koray; Silver, David; Graves, Alex; Antonoglou, Ioannis; Wierstra, Daan; Riedmiller, Martin (2013). "Playing Atari with Deep Reinforcement Learning" (PDF). Neural Information Processing Systems Workshop 2013. Retrieved 25 April 2015.
  5. ۵٫۰ ۵٫۱ Schaul, Tom (August 2013). "A video game description language for model-based or interactive learning". 2013 IEEE Conference on Computational Intelligence in Games (CIG): 1–8. CiteSeerX 10.1.1.360.2263. doi:10.1109/CIG.2013.6633610. ISBN 978-1-4673-5311-3.
  6. ۶٫۰ ۶٫۱ Levine, John; Congdon, Clare Bates; Ebner, Marc; Kendall, Graham; Lucas, Simon M.; Miikkulainen, Risto; Schaul, Tom; Thompson, Tommy (2013). "General Video Game Playing". Artificial and Computational Intelligence in Games. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. 6: 77–83. Retrieved 25 April 2015.
  7. Bowling, M.; Veness, J.; Naddaf, Y.; Bellemare, M. G. (2013-06-14). "The Arcade Learning Environment: An Evaluation Platform for General Agents". Journal of Artificial Intelligence Research (به انگلیسی). 47: 253–279. arXiv:1207.4708. doi:10.1613/jair.3912. ISSN 1076-9757.
  8. Mnih, Volodymyr; Kavukcuoglu, Koray; Silver, David; Rusu, Andrei A.; Veness, Joel; Hassabis, Demis; Bellemare, Marc G.; Graves, Alex; Riedmiller, Martin (26 February 2015). "Human-level control through deep reinforcement learning". Nature. 518 (7540): 529–533. Bibcode:2015Natur.518..529M. doi:10.1038/nature14236. PMID 25719670.
  9. Korjus, Kristjan; Kuzovkin, Ilya; Tampuu, Ardi; Pungas, Taivo (2014). "Replicating the Paper "Playing Atari with Deep Reinforcement Learning"" (PDF). University of Tartu. Retrieved 25 April 2015.
  10. Guo, Xiaoxiao; Singh, Satinder; Lee, Honglak; Lewis, Richard L.; Wang, Xiaoshi (2014). "Deep Learning for Real-Time Atari Game Play Using Offline Monte-Carlo Tree Search Planning" (PDF). NIPS Proceedingsβ. Conference on Neural Information Processing Systems. Retrieved 25 April 2015.
  11. Murphy, Tom (2013). "The First Level of Super Mario Bros. is Easy with Lexicographic Orderings and Time Travel … after that it gets a little tricky." (PDF). SIGBOVIK. Retrieved 25 April 2015.
  12. Murphy, Tom. "learnfun & playfun: A general technique for automating NES games". Retrieved 25 April 2015.
  13. Teller, Swizec (October 28, 2013). "Week 2: Level 1 of Super Mario Bros. is easy with lexicographic orderings and". A geek with a hat. Archived from the original on 30 April 2015. Retrieved 25 April 2015.
  14. McMillen, Colin (2003). "Toward the Development of an Intelligent Agent for the Supply Chain Management Game of the 2003 Trading Agent Competition" [2003 Trading Agent Competition]. Master's Thesis. Minneapolis, MN: University of Minnesota. {{cite journal}}: Cite journal requires |journal= (help)
  15. "AGAPE - An Auction LanGuage for GenerAl Auction PlayErs". AGAPE (به فرانسوی). Retrieved 5 March 2020.
  16. Michael, Friedrich; Ignatov, Dmitry (2019). "General Game Playing B-to-B Price Negotiations" (PDF). CEUR Workshop Proceedings. Vol-2479: 89–99. Retrieved 5 March 2020. {{cite journal}}: |volume= has extra text (help)
  17. ۱۷٫۰ ۱۷٫۱ Barney Pell's research on computer game playing بایگانی‌شده در ۲۰۰۷-۰۸-۱۲ توسط Wayback Machine.
  18. "Metagame and General Game Playing". Metagame and General Game Playing. Retrieved 27 March 2016.
  19. Available: Universal Game Engine email to comp.ai.games by Jeff Mallett, 10-Dec-1998.
  20. "UZH - z-Tree - Zurich Toolbox for Readymade Economic Experiments". www.ztree.uzh.ch (به انگلیسی). Retrieved 17 February 2020.
  21. Beckenkamp, Martin; Hennig‐Schmidt, Heike; Maier-Rigaud, Frank P. (1 March 2007). "Cooperation in Symmetric and Asymmetric Prisoner's Dilemma Games" (به انگلیسی). Social Science Research Network. SSRN 968942. {{cite journal}}: Cite journal requires |journal= (help)
  22. ۲۲٫۰ ۲۲٫۱ Schaul, Tom (7 February 2020). "schaul/py-vgdl".
  23. GGP Server, platform for competition of general game playing systems.
  24. Dresden GGP Server بایگانی‌شده در ۷ آوریل ۲۰۱۳ توسط Wayback Machine, platform for competition of general game playing systems with automatic scheduling of matches.
  25. "General Game Playing". www.general-game-playing.de.
  26. Information about Fluxplayer, the winner of the 2nd International General Game Playing competition.
  27. Information about CADIAPlayer, more information about the winner of the 3rd, 4th, and 8th International General Game Playing competitions.
  28. Sancho is GGP Champion 2014!, winner of the 2014 International General Game Playing competition.
  29. "Zillions of Games - Who Are We?". www.zillions-of-games.com. Retrieved 2017-11-16.
  30. "AiAi Home Page – Stephen Tavener". mrraow.com (به انگلیسی). Retrieved 2017-11-16.
  31. "Ai Ai announcement thread". BoardGameGeek. Retrieved 2017-11-16.
  32. "The PolyGamo Player Project | Programming Languages and General Players for Abstract Games and Puzzles". www.polyomino.com (به انگلیسی). Retrieved 2017-11-16.
  33. Nielsen, Thorbjørn S.; Barros, Gabriella A. B.; Togelius, Julian; Nelson, Mark J. "Towards generating arcade game rules with VGDL" (PDF).
  34. ۳۴٫۰ ۳۴٫۱ Levine, John; Congdon, Clare Bates; Ebner, Marc; Kendall, Graham; Lucas, Simon M.; Miikkulainen Risto, Schaul; Tom, Thompson; Tommy. "General Video Game Playing" (PDF).
  35. Neufeld, Xenija; Mostaghim, Sanaz; Perez-Liebana, Diego. "Procedural Level Generation with Answer Set Programming for General Video Game Playing" (PDF).
  36. "Recent Advances in General Game Playing" (به انگلیسی). Hindawi Publishing Corporation. 2015. doi:10.1155/2015/986262.
  37. "Monte-Carlo Tree Search for General Game Playing". ResearchGate. Retrieved 2016-04-01.
  38. Finnsson, Hilmar (2012). "Generalized Monte-Carlo Tree Search Extensions for General Game Playing". Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. Archived from the original on 15 اكتبر 2013. {{cite journal}}: Check date values in: |archive-date= (help)
  39. Frydenberg, Frederik; Anderson, Kasper R.; Risi, Sebastian; Togelius, Julian. "Investigating MCTS Modifications in General Video Game Playing" (PDF).
  40. M. Swiechowski; J. Mandziuk; Y. S. Ong, "Specialization of a UCT-based General Game Playing Program to Single-Player Games," in IEEE Transactions on Computational Intelligence and AI in Games, vol.PP, no.99, pp.1-1 doi:10.1109/TCIAIG.2015.2391232
  41. Perez, Diego; Dieskau, Jens; Hünermund, Martin. "Open Loop Search for General Video Game Playing" (PDF).
  42. Jesper Juul. Half-Real: Video Games Between Real Rules and Fictional Worlds. MIT Press, 2005.