هوش مصنوعی بازی سالیتر
گیت هاب این پروژه در این لینک موجود است!
پیاده سازی توسط : محمدامین مرتضایی محمدصنایع عباسی
چگونه میتوان هوش مصنوعی برای بازی دشوار سالیتر طراحی نمود؟
۱. مقدمه
در تمام بازی های موجود در جهان هستی آن چیزی که اهمیت اساسی و مهم دارد وجود و بدست آوردن پیروزی می باشد اما در همین حین ممکن است این بازی ها شامل بازی چند انسان باشد و یا بازی انسان با شانس باشد در سری بازی های کارتی که مورد بررسی ماست این امکان به قسمت دوم برمیگردد و دسته ای از بازی ها می باشد که چند انسان درگیر بازی نمیباشند و تنها رقابتی که قرار است اتفاق بیفتد رقابت میان انسان و شانس خودش می باشد.
در تمام سالهایی که بازی کامپیوتری از این دست در حال ساخت بوده اند آن چیزی که دغدغه طراحان بوده است تولید بازی هایی بوده است که سخت تر بتوان آنها را برد و بر شانس ترسیمی طراح فائق آمد. پس در تمامی این سالها طراحان در پی سخت تر کردن شانس بازی ها بوده اند و به شکلی میتوان گفت همواره در پی افزایش چالش ها در حین بازی بوده اند.
اما بازی ای که ما برای هوشمند کردن آن انتخاب کردیم یکی از سخت ترین آنهاست.
این یکی از سخت ترین بازی های کارتی می باشد که وجود دارد و به شکل تئوریکال و حداکثری و با در نظر گرفتن بهترین شرایط تنها شانس 79 درصدی برای این بازی ترسیم شده است که البته بسیار آرمانی میباشد زیرا این شانس برای انسان اصلا و ابدا متصور نیست و تنها میتوان انتظار داشت که گاهی اوقات پیروزی حاصل شود اما دلیل این مسئله این است که این بازی خارج از خوب بازی کردن انسان و یا هر عاملی نیازمند شانس آوردن در حین بازی نیز می باشد و این بسیار مهمتر از بازی صحیح می باشد و نکته بعدی این است که تا حدود زیادی میتوان گفت که حتی یک حرکت اشتباه ممکن است به معنای شکست حتمی عامل بازی کننده باشد و خب این بسیار این بازی را سخت و دشوار میکند و حتی پیروزی برای انسان میتواند بسیار موفقیت بزرگی باشد و عامل هوش مصنوعی ما نیز از این قاعده مستسنی نخواهد بود.
به طور کلی این بازی که به سالیتر معروف می باشد شامل چندین دسته و نوع می باشد و آن چیزی که مورد بررسی ماست بازی سالیتر کلوندایک (Solitaire Klondike) میباشد.
این بازی شامل 52 کارت می باشد و هر کدام از این کارتها معنا و مفهوم خاص خودشان را دارند که به دورنگ قرمز و مشکی تقسیم می شوند و قواعد خاصی را باید برای این بازی رعایت کرد.
بازی شامل سه قسمت میباشد که از هر قسمت با توجه به قاعده خاص خویش می توان استفاده کرد.
قسمت اول قسمت پایین بازی می باشد که کارتها در آن قرار می گیرند و بیشترین میزان کارت در ابتدای بازی را در خود جای داده است.
قسمت دوم قسمت بالا سمت چپ می باشد که شامل پشته و ذخیره ای از کارتها می باشد که باید از آنها در طول بازی و زمانیکه حرکتی نداریم استفاده کنیم.
قسمت سوم قسمت بالا سمت راست می باشد که در ابتدای بازی کاملا خالی می باشد و در آینده باید آنرا پر کرد و درانتهای بازی آنجا پر خواهد بود و بقیه جاها خالی از کارتها خواهد شد.
قواعد قسمت اول بازی
کادر سفید نشانگر قسمت اول بازی می باشد. کارتها باید به شکل نزولی چیده شوند و ما به این ترتیب شماره 1 اطلاق میکنیم و به این شکل می باشد که باید مثلا عدد 3 بر روی 4 قرار بگیرد.
در این قسمت باید کارتها یکی در میان به رنگهای مختلف قرار بگیرند تا به آنها بتوان حرکت مجاز گفت.
اگر به بن بستی خوردیم و نتوانستیم حرکتی بکنیم باید از کارتهای قسمت دوم استفاده کنیم.
در نهایت با توجه به هدف بازی باید کارتها را در قسمت سوم قرار دهیم و به این شکل روند پیروزی را طی کنیم.
قواعد قسمت دوم بازی
کادر سفید نشانگر قسمت دوم بازی می باشد. این قسمت در حقیقت مخزن کارتهایی است در ادامه بازی به آنها نیازمندیم.
از این قسمت برای دیدن کارتها میتوان استفاده کرد و با دیدن آنها می توان در مواقع بن بست بازی کارت جدیدی به قسمت اول و یا قسمت سوم اضافه کرد.
قواعد قسمت سوم بازی
کادر سفید نشانگر قسمت سوم بازی می باشد. در حقیقت مهمترین قسمت بازی می باشد که برنده شدن ما در گرو این قسمت می باشد.
روش قرار گیری کارت در این قسمت دقیقا برعکس قرار گیری در قسمت اول میباشد و به همین دلیل ما شماره -1 را به آن اطلاق میکنیم.
برای برنده شدن باید کارتهای هم رنگ از هرنوع را در قسمت های چهارگانه قرار داد.
بازی سالیتر چگونه امتیازگیری میشود؟
این بازی در حقیقت و به شکل کلاسیک شامل امتیازی بندی نیست و فقط و تنها اولویت بازی پیروزی می باشد اما در بعضی افزونه هایی که بعدا برای این بازی افزوده شده است به بعضی قسمت های مختلف و همچنین بعضی از حرکات امتیازهای متفاوت تلقی شده است که ما مورد بررسی انها را قرار نداده ایم و در بازی ما تنها اولویت پیروزی می باشد.
برای بردن چه باید کرد؟
باید از استراتژی های برد بهره برد که در ادامه به آنها اشاره خواهیم کرد.
۲. مقاله های مرتبط
در این زمینه مقاله مرتبط زیادی وجود ندارد اما می توان به دو مقاله که ما در طول فرآیند حل این مسئله از آنها استفاده کردیم اشاره کرد.
مقاله اول مقاله ای از سایت معتبر مدیوم بود که در آن درباره توضیح اینکه بازی های کارتی چگونه در کامپیوتر بازی میشوند و انواع آنها که در مقدمه به آنها اشاره شد را معرفی کرده بود که در لینک توضیحات من باب سالیتر و بازی هایی از این دست قابل دسترسی می باشد.
مقاله بعدی که از آن استفاده کردیم مقاله سایت ویکی پدیا بود که درباره این بازی توضیحات لازم را داده بود.
و در نهایت مقاله اصلی که استراتژی برد ما نیز بود مقاله ای چگونه میتوان در بازی سالیتر موفق بود!؟ بود که ما تلاش کردیم تا جایی که میشود به این استراتژی ها کد را نزدیک کنیم.
۳. چالش ها و پیروزی بر چالشها!
سخت ترین قسمت زندگی چالش های آن است و شیرین ترین قسمت آن پیروزی بر آنها!
ما در این پروژه به دلیل اینکه راه متفاوتی نسبت به پروژه دیگران در پیش گرفته بودیم بسیار کار سختی را در پیش داشتیم و این مسئله بشدت مارا اذیت کرد اما مسئله اصلی این بود که بر آنها فائق آمدیم.
انتخاب راه متفاوت و انتخاب پروژه ای که بر اساس اکسپکتی مکس پیش میرفت باعث شد که در تکاپو بیفتیم و کد زیادی بزنیم گرچه میشد که با انتخاب ماشین لرنینگ و مطالبی از این دست راه خودمان را هموار تر کنیم اما مطلب سخت تر را انتخاب کردیم و سمت این مسئله رفتیم و تا حدود زیادی موفق به انجام یک پروژه خوب و درست و حسابی شدیم! و از این بابت خوشحالیم!
در ابتدا باید اشاره کنیم که کدی که به عنوان کد اصلی بازی هوش مصنوعی را بر روی آن سوار کردیم کدی بود که مشکلاتی اساسی داشت که با توجه به نیاز چندین جا به کد بازی دست زدیم و تغییرات لازم را اعمال کردیم تا بتوانیم بازی را به شکل صحیح داشته باشیم و این چالش اول ما بود یعنی تصحیح کد اصلی بازی! که قطعا قرار نبود در پروژه هوش مصنوعی به این مسائل بخوریم که متاسفانه این اتفاق افتاد البته شایان به ذکر است که این مسئله به این برمیگردد که کدی که نیاز بود از آن به عنوان بازی اصلی استفاده کنیم در اینترنت باید پیدا میکردیم و بعد از جست جوهای ما تنها کدی به زبان پایتون بود و میتوانستیم از آن استفاده کنیم و ران میشد همین کد موجود می باشد که البته با توجه به مطلبی که در بالا اشاره شد ما آنرا تصحیح نیز کردیم و از آن استفاده کردیم.
چالش بعدی که در این بین موجود بود این بود که ما باید به کد بازی مسلط میشدیم که بتوانیم از آن استفاده کنیم و هوش مصنوعی را روی آن پیاده سازی کنیم و خب این پروسه زمان بری بود که با درایت اعضای گروه بسیار کوتاه تر شد و توانستیم به سرعت هرچه تمام تر بر این مشکل نیز فائق آییم و در مدت کوتاهی بر کد بازی به شکل کامل مسلط شدیم و توانستیم بدون استفاده از نشانگر کارتها را حرکت بدهیم.
چالش بعدی نوع طراحی خانه های بازی بود که بشدت ما را گیج و البته عصبی کرد که باعث شد حرکت کارتها در خانه های مختلف و بالاخص از قسمت اول به قسمت سوم را برای ما مشکل کند که این طراحی و معماری بد کد باعث این اتفاق شده بود و بسیار لحظات سختی بود که باعث شده بود زمان زیادی از ما تلف این مسئله شود.
مسئله بعدی این بود که حالا هوش مصنوعی این بازی را به چه شکلی پیاده سازی کنیم که در همین حین به دلایلی از الگوریتم اکسپکتی مکس استفاده کردیم و این الگوریتم راهگشای راه ما در راه این پروژه شد.
چرا از اکسپکتی مکس استفاده کردیم؟
این الگوریتم کاملا مناسب سوالات و مسائلی از این دست می باشد به دلیل اینکه تعداد حالات زیادی در کار نیست و قرار نیست اتفاقات عجیبی بیفتد و با بهره جستن از این الگوریتم که به شکل بازگشتی در کد اجرا شده است توانستیم این مسئله را به خوبی حل کنیم.
چالش مهمی که در این بین به آن برخورد کردیم این بود که این بازی به شکل برد و باختی طراحی شده بود گرچه روند امتیاز گیری هایی در بعضی جاها برای آن در نظر گرفته شده بود ولی اصل ماجرا این بود که در این بازی یا برنده باید میشدیم و یا بازنده پس ارزیابی این اتفاق بسیار مشکل بود که در آنچه در آینده می توان به این پروژه اضافه کرد به این مسئله نیز اشاره خواهیم کرد ولی در حال حاضر تنها چیزی که میتوان برای ارزیابی بهره جست تغییر متغیر های تابع پیشبر بود که این اتفاق افتاده و در نمونه آزمایشات و نتایج می توانید آنها را مشاهده کنیم ولی در کل این تابع ارزیابی تابع خیلی خوبی نیست و حتی اگر فرض کنیم که تابع خوبی هم باشد بازهم بدرد آزمایشاتی که در تعداد بار پایین اتفاق می افتد نمیخورد و باید تعداد بار زیادی تست شود تا بتوان به نتیجه قابل قبول و قابل ذکری در آن برسیم پس نوشتن تابع ارزیابی بسیار مشکل بود.
و اما چالش آخر و مهترین چالش پیاده سازی و استفاده از استراتژی های بردی بود که به همت اعضای گروه از اینترنت پیدا شده بود.که این استراتژی ها در قالب کد بخش تابع پیشبر ارائه شد و کد آن به شکل روبرو می باشد.
def evaluation_function(valid_move_set, level, deck):
if level == 0:
point = float("-inf")
face_ups = []
for pile in deck.piles:
for card in pile.cards:
if card.face_up:
face_ups.append(card)
counter = 0
index = 0
for possibility in valid_move_set:
temp_point = 0
if possibility[3].rank == '2' and possibility[4].rank == 'ace':
temp_point += 2500 # RULE NO.1
if possibility[3].rank == '2' and possibility[4].rank == '3':
temp_point += 1000 # RULE NO.1
if len(possibility[0].cards) > 1:
temp_point += 10 * len(possibility[0].cards) / 3 # @TODO RULE NO.2&NO.3
face_down_counter = 0
for card in possibility[1].cards:
if card.face_up:
if card.suit == possibility[3].suit:
temp_point += 300 # RULE NO.4
else:
face_down_counter += 1
if len(possibility[0].cards) == 1:
for card in face_ups:
if card.rank == 'king':
temp_point += 100 # RULE NO.5
face_down_counter = 0
for card in possibility[0].cards:
if card.face_up:
if card.rank == 'king':
temp_point += face_down_counter * 5 # RULE NO.6
else:
face_down_counter += 1
if possibility[1].pile_type == 'foundation':
# Next card protection
rank_index = 0
for i in deck.ranks:
if i == possibility[3].rank:
break
rank_index += 1
rank_index -= 1
for card in face_ups:
if card.rank == rank_index and card.color != possibility[3].color:
temp_point += 500 # RULE NO.7
if possibility[3].rank == "5" or possibility[3].rank == "6" or possibility[3].rank == "7" or \
possibility[3].rank == "8":
temp_point -= 100
for card in possibility[1].cards:
if card.suit == possibility[3].suit:
temp_point += 300 # RULE NO.8 face_up_pile_counter += 1
if temp_point > point:
point = temp_point
index = counter
counter += 1 point -= move_counter * 500000
else:
face_ups = []
for pile in deck.piles:
for card in pile.cards:
if card.face_up:
face_ups.append(card)
temp_deck = deck
for possibility in valid_move_set:
temp_piles = []
temp_pile = []
temp_point = 0
for pile in deck.piles:
if pile == possibility[0]:
temp_pile = pile.cards[:len(pile.cards) - 1] #@TODO Check later
if pile != possibility[0]:
temp_piles.append(pile)
# for card in pile.cards:
# face_ups.append(card)
# for pile in deck.piles:
# valid_move_set_ = valid_moves(deck) # @TODO handle leveling
if temp_point > point:
point = temp_point
index = counter
counter += 1
return valid_move_set[index], point
۴. استراتژی های برد
در پیاده سازی هوش مصنوعی این بازی از این استراتژی استفاده کردیم.
۱- همیشه آس و شاه را حرکت بده
۲-همیشه و در همه ی شرایط حرکتی را انجام بده که کارت رو به پشتی را آزاد کند
۳-در صورت وجود انتخاب های متعدد, کارتی را حرکت بده که دسته‌ی رو به پایین بیشتری را آزاد کند
۴-تنها وقتی کارت از ستونی به ستون دیگر جابجا بکن که یک کارت را آزاد کند یا ستون را روان تر کند.
۵-یک جایگاه را تنها وقتی خالی کن که یک شاه بلافاصله آماده ی آمدن به آن باشد
۶-شاهی را حرکت بده که بر روی بزرگترین دسته تاثیر بگذارد مگر این که حرکت شاه دیگری منجر به آزاد شدن کارت دیگری شود
۷-تنها وقتی دسته ی آس را کامل کن که:
مانع از حفاظت کارت بعدی نشود
کمک به آزاد شدن کارت بکند
فضا برای قرار گرفتن آنی شاه آماده شود
۸- ۵، ۶، ۷ و ۸ را حرکت نده مگر وقتی که:به روانتر شدن یک ستون کمک کند
اجازه به آزاد شدن آنی یک کارت کند
جای خود را به یک کارت همرنگ خود بدهد که منجر به آزاد شدن کارت رو به پشتی گردد
هیچ حرکت دیگری نداشته باشیم(عموما نشانه ی خوبی نیست)
۹-وقتی که به نقطه ای رسیدیم که همه ی کارت ها در جایگاهی قرار گرفته اند و نمیتوانیم حرکت بهتری انجام دهیم سعی کنیم کارت ها را در جایگاه آس مربوط به خود قرار دهیم
ستون روان:
به این معنا که در هر دسته ی کارتی که در جایگاه پایین داریم صرفا دو نوع متفاوت(بر حسب رنگ) داشته باشیم.
حفاظت از کارت بعدی:
در صورتی کارت به دسته ی آس ها میرود که کارت های با ارزش پایین تر و رنگ مخالف آن قبلا دیده شده باشند.**
۵. آینده
برای این برنامه آینده خوبی متصور هستیم و میتوانیم با استفاده از الگوریتم هایی که به تعداد بار زیادی این کد را اجرا کنند میتوان به نتایجی در قبال اینکه چقد تابع پیشبر ما خوب عمل میکرد رسید و این تنها کاری است که در این پروژه انجام نشده اما هوش مصنوعی به شکل کامل پیاده سازی شده و بازی اجرا می شود و با زدن دکمه هوش مصنوعی میتوان دید که به خوبی عملکرد خود را نشان میدهد.