Tic Tac Toe در آردوینو با هوش مصنوعی (الگوریتم مینیماکس): 3 مرحله

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

در این دستورالعمل من قصد دارم به شما نشان دهم که چگونه می توانید یک بازی Tic Tac Toe با AI با استفاده از Arduino بسازید. شما می توانید در برابر آردوینو بازی کنید یا بازی آردوینو را در برابر خود تماشا کنید.

من از الگوریتمی به نام "minimax algorithm" استفاده می کنم ، که می تواند نه تنها برای ایجاد هوش مصنوعی برای Tic Tac Toe ، بلکه برای انواع بازی های دیگر مانند Four in a Row ، چکرز یا حتی شطرنج نیز استفاده شود. بازی هایی مانند شطرنج بسیار پیچیده هستند و به نسخه های بسیار دقیق تری از الگوریتم نیاز دارند. برای بازی Tic Tac Toe ، می توانیم از ساده ترین نسخه الگوریتم استفاده کنیم ، که با این وجود بسیار چشمگیر است. در واقع ، هوش مصنوعی آنقدر خوب است که شکست دادن آردوینو غیرممکن است!

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

مرحله 1: بسازید و بازی کنید

برای ساخت بازی Tic Tac Toe به اجزای زیر نیاز دارید:

• یک آردوینو اونو
• 9 LED WS2812 RGB
• 9 دکمه فشاری
• تعدادی کابل سیم و بلوز

قطعات را همانطور که در طرح Fritzing نشان داده شده است ، سیم بندی کنید. سپس کد را در Arduino خود بارگذاری کنید.

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

با باز کردن Serial Monitor می توانید آردوینو را "فکر کنید" تماشا کنید. برای هر حرکت ممکن ، الگوریتم رتبه ای را محاسبه می کند که نشان می دهد آیا این حرکت منجر به برد (مقدار 10) یا باخت (مقدار -10) برای آردوینو یا تساوی (مقدار 0) می شود.

همچنین می توانید بازی Arduino را در مقابل خود با اظهارنظر درباره خط "#تعریف DEMO_MODE" در ابتدای طرح مشاهده کنید. اگر طرح اصلاح شده را بارگذاری کنید ، Arduino اولین حرکت را به صورت تصادفی انجام می دهد و سپس از الگوریتم minimax برای تعیین بهترین حرکت برای هر بازیکن در هر نوبت استفاده می کند.

توجه داشته باشید که نمی توانید در مقابل آردوینو پیروز شوید. در صورت اشتباه ، هر بازی یا با تساوی به پایان می رسد یا می بازید. این به این دلیل است که الگوریتم همیشه بهترین حرکت ممکن را انتخاب می کند. همانطور که ممکن است بدانید ، بازی تیک تاک در صورت اشتباه نکردن هر دو بازیکن همیشه با تساوی به پایان می رسد. در حالت آزمایشی ، هر بازی با تساوی به پایان می رسد زیرا همانطور که همه می دانیم کامپیوترها هرگز اشتباه نمی کنند ؛-)

مرحله 2: الگوریتم Minimax

الگوریتم شامل دو جزء است: یک تابع ارزیابی و یک استراتژی جستجو. تابع ارزیابی یک تابع است که مقدار عددی را به موقعیت های تخته اختصاص می دهد. اگر موقعیت یک موقعیت نهایی است (یعنی موقعیتی که یا بازیکن آبی یا قرمز برنده شده یا هیچ بازیکنی برنده نشده است) ، عملکرد ارزیابی بسیار ساده است: فرض کنید آردوینو آبی بازی می کند و بازیکن انسانی قرمز بازی می کند به اگر موقعیت یک موقعیت برنده برای رنگ آبی باشد ، تابع مقدار 10 را به آن موقعیت اختصاص می دهد. اگر این یک موقعیت برنده برای رنگ قرمز باشد ، تابع مقدار -10 را به موقعیت اختصاص می دهد. و اگر موقعیت قرعه کشی باشد ، تابع مقدار 0 را به آن اختصاص می دهد.

وقتی نوبت به آردوینو می رسد ، می خواهد حرکتی را انتخاب کند که ارزش تابع ارزیابی را به حداکثر برساند ، زیرا حداکثر کردن ارزش به این معنی است که برد را بر تساوی (10 بیشتر از 0) ترجیح می دهد و تساوی را بر باخت ترجیح می دهد (0 بزرگتر از -10 است). با استدلال مشابه ، حریف می خواهد به گونه ای بازی کند که ارزش عملکرد ارزیابی را به حداقل برساند.

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

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

مرحله 3: عیب یابی و مراحل بیشتر

اگر یک دکمه را فشار دهید و یک LED متفاوت از آنچه مربوط به دکمه است روشن کنید ، احتمالاً سیم های پین A0-A2 یا 4-6 را با هم مخلوط کرده اید یا LED ها را به ترتیب اشتباه وصل کرده اید.

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

گسترش احتمالی این پروژه استفاده از الگوریتم برای ایجاد هوش مصنوعی برای 4x4 یا حتی 5x5 Tic Tac Toe است. با این حال ، توجه داشته باشید که تعداد موقعیت هایی که الگوریتم برای بررسی نیاز دارد به سرعت رشد می کند. شما باید روش هایی را برای هوشمندسازی عملکرد ارزیابی با تعیین مقادیر در موقعیت هایی که نهایی نیستند ، بر اساس احتمال خوب یا بد بودن موقعیت برای بازیکن مورد نظر ، بیابید. همچنین اگر به نظر برسد که حرکت نسبت به حرکات جایگزین ارزش کاوش کمتری دارد ، می توانید با متوقف کردن زودهنگام جستجو ، جستجوی خود را هوشمندتر کنید.

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