بازی مصنوعی هوش مصنوعی: الگوریتم مینیماکس: 8 مرحله

2024 نویسنده: John Day | [email protected]. آخرین اصلاح شده: 2024-01-30 08:54

آیا تا به حال به این فکر کرده اید که رایانه هایی که در شطرنج یا چکرز با آنها بازی می کنید چگونه ساخته می شوند؟ خوب ، بیشتر از این دستورالعمل نگاه نکنید زیرا به شما نشان می دهد چگونه می توانید با استفاده از الگوریتم Minimax یک هوش مصنوعی ساده اما م effectiveثر (AI) بسازید! با استفاده از الگوریتم Minimax ، هوش مصنوعی به خوبی برنامه ریزی شده و برنامه ریزی شده (یا حداقل تقلید از یک روند فکر). در حال حاضر ، من فقط می توانم کد هوش مصنوعی را که ساخته ام به شما بدهم ، اما این سرگرم کننده نخواهد بود. من منطق انتخاب کامپیوتر را توضیح می دهم.

در این دستورالعمل ، من مراحل مربوط به نحوه ایجاد هوش مصنوعی برای اتللو (AKA Reversi) در پایتون را به شما آموزش می دهم. قبل از مقابله با این پروژه ، باید از نحوه برنامه نویسی در پایتون درک متوسطی داشته باشید. در اینجا چند وب سایت خوب وجود دارد که برای آماده سازی شما برای این دستورالعمل باید به آنها توجه کنید: w3schools یا learnpython. در پایان این دستورالعمل ، شما باید یک هوش مصنوعی داشته باشید که حرکات حساب شده ای انجام دهد و بتواند اکثر انسان ها را شکست دهد.

از آنجا که این دستورالعمل در درجه اول با نحوه ایجاد AI صحبت می کند ، من نحوه طراحی یک بازی در پایتون را توضیح نخواهم داد. در عوض ، من کد بازی را ارائه می کنم که در آن یک انسان می تواند در برابر یک انسان دیگر بازی کند و آن را تغییر دهد تا بتوانید یک بازی را انجام دهید که در آن یک انسان در برابر AI بازی می کند.

من نحوه ایجاد این هوش مصنوعی را از طریق یک برنامه تابستانی در Columbia SHAPE آموختم. من اوقات خوبی را در آنجا گذراندم ، بنابراین به وب سایت آنها نگاه کنید تا ببینید آیا به آن علاقه مند هستید یا خیر.

حالا که تدارکات را از سر راه برداشتیم ، بیایید برنامه نویسی را شروع کنیم!

(من چند نکته در تصاویر قرار دادم ، بنابراین حتماً آنها را ببینید)

تدارکات

این آسان است:

1) کامپیوتر با محیط پایتون مانند Spyder یا IDLE

2) فایل های بازی Othello را از GitHub من بارگیری کنید

3) مغز شما با صبر نصب شده است

مرحله 1: فایلهای لازم را بارگیری کنید

وقتی وارد GitHub من می شوید ، باید 5 فایل را ببینید. هر 5 را بارگیری کرده و همه آنها را در یک پوشه قرار دهید. قبل از اجرای بازی ، تمام فایل های موجود در محیط spyder را باز کنید.

در اینجا کارهایی که فایلها انجام می دهند به شرح زیر است:

1) othello_gui.py این فایل صفحه بازی را برای بازی بازیکنان ایجاد می کند (چه انسان و چه کامپیوتر)

2) othello_game.py این فایل بدون رایانه دو کامپیوتر را در برابر یکدیگر پخش می کند و فقط موقعیت و مکان حرکت را نشان می دهد

3) ai_template.py اینجاست که تمام کد خود را برای ایجاد هوش مصنوعی خود قرار می دهید

4) randy_ai.py این یک هوش مصنوعی از پیش ساخته است که حرکات خود را به طور تصادفی انتخاب می کند

5) othello_shared.py مجموعه ای از توابع از پیش ساخته شده را که می توانید برای ایجاد هوش مصنوعی خود مانند بررسی حرکات موجود ، نمره یا وضعیت هیئت مدیره استفاده کنید

6) سه فایل دیگر: Puma.py ، erika_5.py و nathan.py ، به ترتیب توسط من ، اریکا و ناتان از برنامه SHAPE ، این سه هوش مصنوعی متفاوت با کدهای منحصر به فرد است

مرحله 2: نحوه باز کردن و بازی Python Othello

پس از بازکردن همه پرونده ها ، در گوشه سمت چپ پایین صفحه ، عبارت "run othello_gui.py" را تایپ کرده و enter را در IPython Console بزنید. یا در ترمینال Mac ، "python othello_gui.py" را تایپ کنید (البته بعد از اینکه در پوشه مناسب قرار گرفتید). سپس یک صفحه باید روی صفحه شما ظاهر شود. این حالت حالت انسان در مقابل انسان است. نور دوم می شود و اول تاریک می شود. اگر گیج شده اید به ویدیوی من نگاه کنید. در بالا ، نمره هر کاشی رنگ وجود دارد. برای بازی ، روی یک مکان حرکت معتبر کلیک کنید تا کاشی در آنجا قرار گیرد و سپس رایانه را به حریف خود بدهید که همان کار را تکرار می کند.

اگر نحوه بازی Othello را نمی دانید ، این قوانین را از وب سایت ultra boards بخوانید:

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

تفاوت بازی اصلی با این بازی پایتون در این است که وقتی هیچ حرکت معتبری برای یک بازیکن باقی نماند ، بازی به پایان می رسد

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

مرحله 3: الگوریتم مینیماکس: ایجاد سناریوها

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

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

من این را یک الگوریتم عقب نشینی نامیدم ، زیرا ابتدا با ایجاد و ارزیابی همه حالات هیئت مدیره آینده با مقادیر مرتبط با آنها شروع می شود. این بدان معناست که الگوریتم تا زمانی که هر سناریویی از بازی انجام نشود ، بازی را به میزان لازم (انجام حرکات برای خود و حریف) انجام می دهد. برای پیگیری همه حالتهای صفحه (سناریوها) ، می توانیم درختی بکشیم (به تصاویر نگاه کنید). درخت موجود در تصویر بالا یک مثال ساده از بازی Connect 4 است. به هر پیکربندی تخته حالت تخته و محل آن را روی درخت گره می گویند. همه گره های پایین درخت حالت نهایی صفحه بعد از انجام همه حرکتها هستند. بدیهی است که برخی از حالتهای هیئت مدیره برای یک بازیکن بهتر از بازیکن دیگر است. بنابراین ، اکنون ما باید هوش مصنوعی را مجبور کنیم انتخاب کند که به کدام حالت هیئت مدیره می خواهد برسد.

مرحله 4: Minimax: ارزیابی تنظیمات هیئت مدیره

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

اکنون ما می توانیم مقادیر را به موقعیت های مربوط به هر هیئت مدیره ایالت اختصاص دهیم. وقتی موقعیتی توسط قطعه AI اشغال می شود ، بسته به موقعیت ، تعداد مشخصی امتیاز می دهید. به عنوان مثال ، یک صفحه هیئت مدیره که قطعه AI در گوشه قرار دارد ، می توانید 50 امتیاز پاداش بدهید ، اما اگر در نقطه نامطلوبی قرار داشت ، ممکن است مقدار قطعه 0. پس از در نظر گرفتن تمام مقادیر موقعیت ها ، شما به وضعیت هیئت مدیره یک مقدار اختصاص می دهید. به عنوان مثال ، اگر هوش مصنوعی یک قطعه در گوشه داشته باشد ، حالت برد می تواند نمره 50 داشته باشد در حالی که حالت دیگر برد با قطعه AI در وسط دارای نمره 10 است.

روش های زیادی برای انجام این کار وجود دارد ، و من سه روش اکتشافی مختلف برای ارزیابی قطعات تخته دارم. من شما را تشویق می کنم که نوع ابتکاری خود را بسازید. من سه هوش مصنوعی مختلف توسط سه سازنده مختلف در github خود بارگذاری کردم ، با سه روش اکتشافی مختلف: Puma.py ، erika5.py ، nathanh.py.

مرحله 5: الگوریتم Minimax: انتخاب بهترین حرکت

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

پس از ایجاد همه حالتهای برد و تعیین مقادیر به تخته ، الگوریتم شروع به مقایسه حالتهای برد می کند. در تصاویر ، من یک درخت ایجاد کردم تا نشان دهد چگونه الگوریتم حرکات خود را انتخاب می کند. هر شکاف در شاخه ها یک حرکت متفاوت است که AI یا حریف می تواند انجام دهد. در سمت چپ ردیف گره ها ، نوشتم که آیا پخش کننده حداکثر یا کوچک می شود. ردیف پایین همه حالتهای تخته با مقادیر آنها است. در داخل هر یک از آن گره ها یک عدد وجود دارد و این نمره هایی است که ما به هر یک از تخته ها اختصاص می دهیم: هرچه بیشتر باشند ، داشتن AI بهتر است.

تعاریف: گره والد - گره ای که در زیر آن ایجاد شده یا گره ایجاد می کند. منشاء گره های کودکان - گره هایی که از همان گره والد می آیند

گره های خالی نشان دهنده حرکت هوش مصنوعی برای رسیدن به بهترین حالت برد است. این کار با مقایسه فرزندان سمت چپ ترین گره شروع می شود: 10 ، -3 ، 5. از آنجا که بازیکن حداکثر می تواند حرکت کند ، حرکتی را انتخاب می کند که بیشترین امتیاز را به آن می دهد: 10. بنابراین ، ما آن را انتخاب و ذخیره می کنیم با نمره تخته حرکت کنید و آن را در گره والد بنویسید. اکنون که 10 در گره والد است ، نوبت به حداقل رساندن بازیکنان است. با این حال ، گره ای که ما 10 را با آن مقایسه می کنیم خالی است ، بنابراین ما باید قبل از انتخاب پخش کننده کوچک کننده ابتدا آن گره را ارزیابی کنیم. بنابراین ما به نوبه خود بازیکن حداکثر می رویم و فرزندان گره مجاور را مقایسه می کنیم: 8 ، -2. Maximizing 8 را انتخاب می کند و ما آن را در گره اصلی خالی می نویسیم. اکنون که الگوریتم پر کردن فضاهای خالی برای فرزندان یک گره در بالای آن را به پایان رسانده است ، بازیکن کوچک کننده می تواند آن کودکان - 10 و 8 را مقایسه کرده و 8 را انتخاب کند. الگوریتم سپس این روند را تکرار می کند تا کل درخت پر شود. در پایان این مثال ، ما نمره 8 را داریم. این بالاترین حالت هیئت مدیره است که هوش مصنوعی می تواند انجام دهد تا فرض کند که حریف بهینه بازی می کند. بنابراین هوش مصنوعی اولین حرکت را که منجر به حالت 8 تخته می شود ، انتخاب می کند و اگر حریف بهینه بازی کند ، هوش مصنوعی باید تمام حرکات را انجام دهد تا به حالت 8 برسد. (نکات تصاویر من را دنبال کنید)

می دانم که خیلی زیاد بود. اگر شما از آن دسته افرادی هستید که برای درک چیزی نیاز به صحبت با شما دارند ، در اینجا چند ویدئو وجود دارد که من آنها را تماشا کردم تا به من کمک کند ایده پشت این موضوع را درک کنم: 1 ، 2 ، 3.

مرحله 6: الگوریتم مینیماکس: شبه کد

بعد از اینکه منطق پشت الگوریتم مینیماکس را درک کردید ، به این شبه کد (توابع عمومی همه کدها) از ویکی پدیا نگاه کنید:

تابع minimax (گره ، عمق ، maximizingPlayer) است

اگر عمق = 0 یا گره یک گره پایانی است پس

مقدار اکتشافی گره را برمی گرداند

اگر maximizingPlayer پس

مقدار: = −∞

برای هر فرزند گره انجام دهید

مقدار: = حداکثر (مقدار ، مینیمکس (کودک ، عمق - 1 ، FALSE))

مقدار بازگشتی

else (* به حداقل رساندن پخش کننده *)

مقدار: = +∞

برای هر فرزند گره انجام دهید

مقدار: = دقیقه (مقدار ، حداقل (کودک ، عمق - 1 ، TRUE))

مقدار بازگشتی

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

این شبه کد فرآیندی را که در دو مرحله قبل توضیح دادم ، بازتولید می کند. حالا بیایید این کار را یک قدم جلوتر برداریم و این را در کد پایتون درست کنیم.

مرحله 7: ایجاد هوش مصنوعی خود با Ai_template.py

قبل از اینکه به کد هوش مصنوعی Minimax نگاهی بیندازید ، سعی کنید با فایل ai_template.py و کد شبه ای که در آخرین مرحله در مورد آن صحبت کردیم ، AI خود را بسازید. دو الگوی در قالب ai وجود دارد به نام: def minimax_min_node (تخته ، رنگ) و def minimax_max_node (تخته ، رنگ). به جای اینکه تابع minimax خود به خود به صورت بازگشتی فراخوانی شود ، ما دو تابع متفاوت داریم که یکدیگر را صدا می زنند. برای ایجاد روش ابتکاری برای ارزیابی حالات هیئت مدیره ، باید عملکرد خود را ایجاد کنید. توابع پیش ساخته ای در فایل othello_shared.py وجود دارد که می توانید از آنها برای ساخت هوش مصنوعی خود استفاده کنید.

هنگامی که هوش مصنوعی خود را دارید ، سعی کنید آن را در مقابل ، randy_ai.py اجرا کنید. برای اجرای دو راهرو در مقابل یکدیگر ، "python othello_gui.py (نام فایل ai را وارد کنید).py (نام فایل را وارد کنید).py" در ترمینال مک یا تایپ کنید "run othello_gui.py (نام فایل ai را وارد کنید).py (نام فایل را وارد کنید).py "و مطمئن شوید که در دایرکتوری مناسب قرار دارید. همچنین ، مراحل دقیق کار را به فیلم من نگاه کنید.

مرحله 8: زمان مبارزه با هوش مصنوعی است

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