استفاده از هوش مصنوعی برای حل بازی 2048 (کد جاوا)

• آوریل 7، 2014
• واسیلیس ورینیوتس
• . 6 نظر

تا به حال اکثر شما آن را شنیده یا بازی کرده اید بازی 2048 توسط گابریل سیرولی این یک بازی رومیزی ساده اما بسیار اعتیادآور است که از شما می‌خواهد تعداد سلول‌ها را ترکیب کنید تا به عدد 2048 برسید. همانطور که انتظار می‌رفت، با پر شدن سلول‌های بیشتر با مقادیر بالا، دشواری بازی افزایش می‌یابد. من شخصاً با وجود اینکه زمان زیادی را صرف بازی کردم، هرگز نتوانستم به 2048 برسم. بنابراین کار طبیعی این است که سعی کنیم یک حل کننده هوش مصنوعی در JAVA توسعه دهیم تا بازی 2048 را شکست دهم. 🙂

در این مقاله به طور خلاصه به رویکرد خود برای ساخت حل‌کننده هوش مصنوعی بازی 2048 می‌پردازم، اکتشافی‌هایی که استفاده کردم را شرح می‌دهم و کد کاملی را که به زبان JAVA نوشته شده است ارائه می‌دهم. این کد تحت مجوز GPL v3 منبع باز است و می توانید آن را از اینجا دانلود کنید گیتهاب.

در حال توسعه بازی 2048 در جاوا

بازی اصلی با جاوا اسکریپت نوشته شده است، بنابراین مجبور شدم آن را در جاوا از ابتدا بازنویسی کنم. ایده اصلی بازی این است که شما یک شبکه 4×4 با مقادیر Integer دارید که همه آنها توان های 2 هستند. سلول های صفر در نظر گرفته شده خالی در نظر گرفته می شوند. در هر مرحله از بازی می توانید مقادیر را به 4 جهت بالا، پایین، راست یا چپ حرکت دهید. وقتی حرکتی را انجام می‌دهید، همه مقادیر شبکه به سمت آن جهت حرکت می‌کنند و زمانی که به مرزهای شبکه می‌رسند یا زمانی که به سلول دیگری با مقدار غیر صفر می‌رسند متوقف می‌شوند. اگر سلول قبلی دارای یک مقدار باشد، دو سلول در یک سلول با مقدار دو برابر ادغام می شوند. در پایان هر حرکت یک مقدار تصادفی در تابلو در یکی از خانه های خالی اضافه می شود و مقدار آن یا 2 با احتمال 0.9 یا 4 با احتمال 0.1 است. بازی زمانی به پایان می رسد که بازیکن موفق به ایجاد سلولی با ارزش 2048 (برد) یا زمانی که هیچ حرکت دیگری برای انجام (بازنده) وجود ندارد، به پایان می رسد.

در اجرای اصلی بازی، الگوریتم حرکت-ادغام کمی پیچیده است زیرا تمام جهات را در نظر می گیرد. اگر جهتی را که می‌توانیم قطعات را با هم ترکیب کنیم و تخته را مطابق با آن برای انجام حرکت بچرخانیم، می‌توان یک ساده‌سازی خوب از الگوریتم انجام داد. موریتز ون در شی اخیراً مقاله ای در مورد آن نوشته است که به نظر من ارزش بررسی دارد.

تمام کلاس ها با نظرات Javadoc مستند شده اند. در زیر توضیح سطح بالایی از معماری پیاده سازی ارائه می دهیم:

1. کلاس هیئت مدیره

کلاس تخته حاوی کد اصلی بازی است که وظیفه جابجایی مهره ها، محاسبه امتیاز، اعتبارسنجی در صورت پایان بازی و غیره را بر عهده دارد.

2. ActionStatus و Direction Enum

ActionStatus و Direction دو عدد ضروری هستند که نتیجه حرکت و جهت آن را بر این اساس ذخیره می کنند.

3. کلاس ConsoleGame

ConsoleGame کلاس اصلی است که به ما امکان می دهد بازی را انجام دهیم و دقت حل کننده AI را آزمایش کنیم.

4. کلاس AIsolver

AIsolver کلاس اولیه ماژول هوش مصنوعی است که مسئول ارزیابی بهترین حرکت بعدی با توجه به یک برد خاص است.

تکنیک های هوش مصنوعی: هرس Minimax در مقابل آلفا بتا

چندین رویکرد برای حل خودکار این بازی منتشر شده است. قابل توجه ترین آن است که توسط مت اورلان. برای حل این مشکل دو روش مختلف را امتحان کردم، با استفاده از الگوریتم Minimax و استفاده از هرس آلفا بتا.

الگوریتم Minimax

La مینیماکس یک الگوریتم بازگشتی است که می تواند برای حل بازی های دو نفره مجموع صفر استفاده شود. در هر حالت از بازی، ما یک مقدار را مرتبط می کنیم. الگوریتم Minimax در فضای حالت‌های بازی ممکن جستجو می‌کند و درختی را ایجاد می‌کند که تا رسیدن به عمق از پیش تعریف‌شده خاصی گسترش می‌یابد. پس از رسیدن به آن حالات برگ، مقادیر آنها برای تخمین گره های میانی استفاده می شود.

ایده جالب این الگوریتم این است که هر سطح نشان دهنده نوبت یکی از دو بازیکن است. برای برنده شدن، هر بازیکن باید حرکتی را انتخاب کند که حداکثر بازده حریف را به حداقل برساند. در اینجا یک ارائه ویدیویی زیبا از الگوریتم مینیمکس وجود دارد:

[محتوای جاسازی شده]

در زیر می توانید شبه کد الگوریتم Minimax را مشاهده کنید:

تابع مینیمکس (گره، عمق، حداکثر کردن پخش کننده)
    if عمق = 0 or گره یک گره پایانی است
        برگشت مقدار اکتشافی گره
    if maximizingPlayer bestValue := -∞
        برای هر فرزند نود val := minimax(کودک، عمق - 1، FALSE)) bestValue := max(bestValue، val);
        برگشت بهترین ارزش
    دیگر
        bestValue := +∞
        برای هر فرزند گره val := minimax(child, depth - 1, TRUE)) bestValue := min(bestValue, val);
        برگشت بهترین ارزش
(* فراخوان اولیه برای به حداکثر رساندن پخش کننده *)
حداقل (منشا، عمق، TRUE)

هرس آلفا بتا

La الگوریتم هرس آلفا بتا یک بسط حداقلی است که تعداد گره هایی را که باید ارزیابی/بسط دهیم به شدت کاهش می دهد. برای رسیدن به این هدف، الگوریتم دو مقدار آلفا و بتا را تخمین می زند. اگر در یک گره معین بتا کمتر از آلفا باشد، بقیه زیردرخت ها را می توان هرس کرد. در اینجا یک نمایش ویدیویی زیبا از الگوریتم الفبا آورده شده است:

[محتوای جاسازی شده]

در زیر می توانید شبه کد الگوریتم هرس آلفا بتا را مشاهده کنید:

تابع الفبا (گره، عمق، α، β، حداکثر کردن پخش کننده)
    if عمق = 0 or گره یک گره پایانی است
        برگشت مقدار اکتشافی گره
    if به حداکثر رساندن پخش کننده
        برای هر فرزند گره α := max(α، الفبا (کودک، عمق - 1، α، β، نادرست))
            if β ≤ α
                شکستن (* قطع β *)
        برگشت α
    دیگر
        برای هر فرزند گره β := دقیقه (β، الفبا (کودک، عمق - 1، α، β، درست))
            if β ≤ α
                شکستن (* α برش *)
        برگشت β
(* تماس اولیه *)
الفبا (منشا، عمق، -∞، +∞، TRUE)

چگونه از هوش مصنوعی برای حل بازی 2048 استفاده می شود؟

برای استفاده از الگوریتم های فوق ابتدا باید دو بازیکن را شناسایی کنیم. اولین بازیکن شخصی است که بازی را انجام می دهد. بازیکن دوم رایانه ای است که به طور تصادفی مقادیر را در سلول های تخته درج می کند. بدیهی است که اولین بازیکن سعی می کند امتیاز خود را به حداکثر برساند و به ادغام 2048 دست یابد. از طرف دیگر رایانه در بازی اصلی به طور خاص برنامه ریزی نشده است تا کاربر را با انتخاب بدترین حرکت ممکن مسدود کند، بلکه به طور تصادفی مقادیری را در سلول های خالی درج می کند.

پس چرا از تکنیک‌های هوش مصنوعی استفاده می‌کنیم که بازی‌های حاصل جمع صفر را حل می‌کنند و به طور خاص فرض می‌کنند که هر دو بازیکن بهترین حرکت ممکن را برای خود انتخاب می‌کنند؟ پاسخ ساده است؛ علیرغم اینکه این تنها اولین بازیکنی است که سعی می کند امتیاز خود را به حداکثر برساند، انتخاب های رایانه می تواند جلوی پیشرفت را بگیرد و کاربر را از تکمیل بازی باز دارد. با مدل‌سازی رفتار رایانه به‌عنوان یک پخش‌کننده غیرتصادفی ارثولوژیک، اطمینان حاصل می‌کنیم که انتخاب ما مستقل از آنچه رایانه پخش می‌کند، ثابت خواهد بود.

دومین بخش مهم، اختصاص مقادیر به حالت های بازی است. این مشکل نسبتاً ساده است زیرا خود بازی به ما امتیاز می دهد. متأسفانه تلاش برای به حداکثر رساندن امتیاز به تنهایی رویکرد خوبی نیست. یکی از دلایل این امر این است که موقعیت مقادیر و تعداد سلول های خالی با ارزش برای بردن بازی بسیار مهم است. به عنوان مثال، اگر مقادیر بزرگ را در سلول های راه دور پراکنده کنیم، ترکیب آنها برای ما واقعا دشوار خواهد بود. علاوه بر این، اگر سلول خالی در دسترس نداشته باشیم، هر لحظه خطر از دست دادن بازی را داریم.

به همه دلایل بالا، چندین اکتشافی پیشنهاد شده است مانند Monoticity، صافی و کاشی های رایگان تخته. ایده اصلی این است که از امتیاز به تنهایی برای ارزیابی هر حالت بازی استفاده نکنید، بلکه در عوض یک امتیاز ترکیبی اکتشافی ایجاد کنید که شامل امتیازات فوق‌الذکر می‌شود.

در نهایت باید توجه داشته باشیم که با وجود اینکه من پیاده‌سازی الگوریتم Minimax را توسعه داده‌ام، تعداد زیاد حالت‌های ممکن، الگوریتم را بسیار کند می‌کند و بنابراین هرس کردن ضروری است. در نتیجه در اجرای JAVA از گسترش الگوریتم هرس آلفا بتا استفاده می کنم. علاوه بر این، بر خلاف سایر پیاده‌سازی‌ها، من با استفاده از قوانین دلخواه، انتخاب‌های رایانه را به‌طور تهاجمی انجام نمی‌دهم، اما در عوض همه آنها را در نظر می‌گیرم تا بهترین حرکت ممکن بازیکن را پیدا کنم.

توسعه یک تابع امتیاز اکتشافی

برای اینکه بازی را شکست دهم، چندین عملکرد اکتشافی مختلف را امتحان کردم. موردی که به نظر من مفیدتر بود موارد زیر است:

private static int heuristicScore(int actualScore, int numberOfEmptyCells, int clusteringScore) {
     int score = (int) (actualScore+Math.log(actualScore)*numberOfEmptyCells -clusteringScore);
     return Math.max(score, Math.min(actualScore, 1));
}

تابع فوق امتیاز واقعی تابلو، تعداد سلول‌ها/کاشی‌های خالی و معیاری به نام نمره خوشه‌بندی را ترکیب می‌کند که بعداً به آن خواهیم پرداخت. بیایید هر جزء را با جزئیات بیشتری ببینیم:

1. امتیاز واقعی: به دلایل واضح، وقتی ارزش یک تابلو را محاسبه می کنیم، باید امتیاز آن را در نظر بگیریم. تابلوهایی که امتیازات بالاتری دارند معمولاً در مقایسه با تابلوهایی با امتیازات پایین تر ترجیح داده می شوند.
2. تعداد سلول های خالی: همانطور که قبلاً اشاره کردیم، نگه داشتن چند سلول خالی برای اطمینان از عدم شکست بازی در حرکات بعدی مهم است. حالت‌های تخته‌ای با سلول‌های خالی بیشتر معمولاً در مقایسه با سایر موارد با سلول‌های کمتر ترجیح داده می‌شوند. یک سوال مطرح می شود که چگونه آن سلول های خالی را ارزش گذاری می کنیم؟ در حل من آنها را با لگاریتم نمره واقعی وزن می کنم. این تأثیر زیر را دارد: هر چه امتیاز کمتر باشد، تعداد سلول‌های خالی از اهمیت کمتری برخوردار است (این به این دلیل است که در ابتدای بازی ترکیب سلول‌ها نسبتاً آسان است). هر چه امتیاز بالاتر باشد، اطمینان از داشتن سلول های خالی در بازی اهمیت بیشتری دارد (این به این دلیل است که در پایان بازی به دلیل عدم وجود سلول های خالی احتمال شکست بیشتر است.
3. امتیاز خوشه بندی: ما از امتیاز خوشه‌بندی استفاده می‌کنیم که میزان پراکندگی مقادیر تابلوی ما را اندازه می‌گیرد. وقتی سلول‌هایی با مقادیر مشابه نزدیک هستند، ترکیب آن‌ها آسان‌تر است، به این معنی که از دست دادن بازی سخت‌تر است. در این حالت امتیاز خوشه بندی ارزش کمی دارد. اگر مقادیر تخته پراکنده باشد، این امتیاز مقدار بسیار بزرگی می گیرد. این امتیاز از دو امتیاز قبلی کم می شود و مانند یک پنالتی عمل می کند که ترجیح می دهد تخته های خوشه ای را تضمین کند.

در خط آخر تابع، از غیرمنفی بودن امتیاز اطمینان حاصل می کنیم. اگر امتیاز تابلو مثبت باشد، امتیاز باید کاملاً مثبت باشد و فقط زمانی که تابلوی امتیاز صفر باشد صفر باشد. توابع max و min طوری ساخته شده اند که این اثر را بدست آوریم.

در نهایت باید توجه داشته باشیم که وقتی بازیکن به حالت پایانی بازی می رسد و هیچ حرکت دیگری مجاز نیست، از امتیاز فوق برای تخمین ارزش حالت استفاده نمی کنیم. اگر بازی برنده شود، بالاترین عدد صحیح ممکن را به آن اختصاص می دهیم، در حالی که اگر بازی شکست می خورد، کمترین مقدار غیر منفی (0 یا 1 با منطق مشابه در پاراگراف قبل) را اختصاص می دهیم.

اطلاعات بیشتر در مورد امتیاز خوشه بندی

همانطور که قبلاً گفتیم امتیاز خوشه بندی میزان پراکندگی مقادیر تابلو را اندازه می گیرد و مانند یک پنالتی عمل می کند. من این امتیاز را به گونه‌ای ساخته‌ام که نکات/قوانینی از کاربرانی که بر بازی «تسلط دارند» در آن گنجانده شود. اولین قانون پیشنهادی این است که سعی کنید سلول های دارای مقادیر مشابه را نزدیک نگه دارید تا راحت تر آنها را ترکیب کنید. قانون دوم این است که سلول های با ارزش بالا باید نزدیک به یکدیگر باشند و در وسط تخته ظاهر نشوند، بلکه در کناره ها یا گوشه ها ظاهر شوند.

بیایید ببینیم امتیاز خوشه بندی چگونه تخمین زده می شود. برای هر سلول از تابلو مجموع تفاوت های مطلق از همسایگان آن (به استثنای سلول های خالی) را تخمین می زنیم و اختلاف میانگین را می گیریم. دلیل اینکه ما میانگین ها را می گیریم این است که از شمارش بیش از یک بار اثر دو سلول همسایه خودداری کنیم. نمره کل خوشه بندی مجموع تمام آن میانگین هاست.

امتیاز خوشه بندی دارای ویژگی های زیر است:

1. هنگامی که مقادیر تابلو پراکنده می شوند، ارزش بالایی پیدا می کند و زمانی که سلول هایی با مقادیر مشابه به یکدیگر نزدیک باشند، ارزش پایینی پیدا می کند.
2. این اثر دو سلول همسایه را سنگین نمی کند.
3. سلول های حاشیه یا گوشه همسایه های کمتری دارند و در نتیجه امتیازات کمتری دارند. در نتیجه هنگامی که مقادیر بالا در نزدیکی حاشیه ها یا گوشه ها قرار می گیرند امتیازات کمتری دارند و در نتیجه جریمه کمتر می شود.

دقت الگوریتم

همانطور که انتظار می رود دقت (معروف به درصد بازی هایی که برنده شده اند) الگوریتم به شدت به عمق جستجویی که استفاده می کنیم بستگی دارد. هر چه عمق جستجو بیشتر باشد، دقت بالاتر و زمان بیشتری برای اجرا نیاز دارد. در تست های من، جستجو با عمق 3 کمتر از 0.05 ثانیه طول می کشد اما 20٪ شانس برنده شدن را می دهد، عمق 5 حدود 1 ثانیه طول می کشد اما 40٪ شانس برنده شدن را می دهد و در نهایت عمق 7 27-28 ثانیه طول می کشد. حدود 70-80 درصد شانس برنده شدن را می دهد.

توسعه های آینده

برای کسانی از شما که علاقه مند به بهبود کد هستند در اینجا مواردی وجود دارد که می توانید به آنها توجه کنید:

1. بهبود سرعت: بهبود سرعت الگوریتم به شما این امکان را می دهد که از عمق بیشتری استفاده کنید و در نتیجه دقت بهتری کسب کنید.
2. ایجاد گرافیک: دلیل خوبی وجود دارد که چرا اجرای گابریل سیرولی تا این حد معروف شد. به نظر خوب است! من حوصله توسعه رابط کاربری گرافیکی را نداشتم، بلکه نتایج را روی کنسول چاپ می‌کنم که پیگیری و اجرای بازی را سخت‌تر می‌کند. ایجاد یک رابط کاربری گرافیکی خوب ضروری است.
3. کوک اکتشافی: همانطور که قبلاً اشاره کردم، چندین کاربر اکتشافی های مختلفی را پیشنهاد کرده اند. می توان نحوه محاسبه امتیازات، وزن ها و ویژگی های تخته را که در نظر گرفته می شود آزمایش کرد. رویکرد من برای اندازه‌گیری امتیاز خوشه‌ای قرار است پیشنهادهای دیگری مانند یکنواختی و همواری را با هم ترکیب کند، اما هنوز جای پیشرفت وجود دارد.
4. تنظیم عمق: همچنین می توانید سعی کنید عمق جستجو را بسته به وضعیت بازی تنظیم یا تنظیم کنید. همچنین می توانید از جست و جوی عمیق عمقی تکراری الگوریتمی که به بهبود الگوریتم هرس آلفا-بتا معروف است.

فراموش نکنید که کد جاوا را از اینجا دانلود کنید گیتهاب و آزمایش کنید. امیدوارم از این پست لذت برده باشید! اگر این کار را کردید، لطفا چند لحظه وقت بگذارید و مقاله را در فیس بوک و توییتر به اشتراک بگذارید. 🙂