آموزش هوش مصنوعی با پایتون - بازی

بازی‌ها با استفاده از یک راهبرد انجام می‌شوند. هر بازیکن یا تیم پیش از شروع بازی، راهبردی را در نظر می‌گیرد و باید با توجه به وضعیت فعلی بازی، آن را تغییر دهد یا راهبرد جدیدی تدوین کند.

الگوریتم‌های جستجو

در بازی‌های رایانه‌ای نیز باید از همان راهبردی که در بالا توضیح داده شد استفاده کنید. توجه داشته باشید که الگوریتم‌های جستجو وظیفه تعیین راهبرد را در بازی‌های رایانه‌ای بر عهده دارند.

نحوه عملکرد

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

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

جستجوی ترکیبی

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

برای رفع این مشکل، می‌توانیم از جستجوی ترکیبی استفاده کنیم که با بهره‌گیری از روش ابتکاری، فضای جستجو را بررسی می‌کند و با حذف حرکت‌های احتمالیِ نادرست، اندازه آن را کاهش می‌دهد. در نتیجه، این الگوریتم‌ها می‌توانند در مصرف منابع صرفه‌جویی کنند. در ادامه، برخی از الگوریتم‌هایی را بررسی می‌کنیم که برای جستجو در فضا و صرفه‌جویی در منابع از روش‌های ابتکاری استفاده می‌کنند:

الگوریتم مینیمکس

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

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

هرس آلفا-بتا

یکی از مشکلات اصلی الگوریتم مینیمکس این است که ممکن است بخش‌هایی از درخت را بررسی کند که ارتباطی با مسئله ندارند و این امر باعث هدررفتن منابع می‌شود. بنابراین، باید راهبردی وجود داشته باشد که مشخص کند کدام بخش از درخت مرتبط و کدام بخش نامرتبط است تا بخش‌های نامرتبط بررسی نشوند. هرس آلفا-بتا یکی از این راهبردهاست.

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

الگوریتم نگامکس

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

ساخت ربات برای انجام بازی‌ها

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

pip install easyAI

ساخت ربات برای بازی «آخرین سکه باقی‌مانده»

در این بازی، تعدادی سکه در یک توده قرار دارند. هر بازیکن باید تعدادی سکه از آن توده بردارد. هدف بازی این است که از برداشتن آخرین سکه توده خودداری کنید. ما از کلاس LastCoinStanding استفاده خواهیم کرد که از کلاس TwoPlayersGame در کتابخانه easyAI به ارث برده شده است. کد زیر، کد پایتون این بازی را نشان می‌دهد:

بسته‌های موردنیاز را مطابق زیر وارد کنید:

from easyAI import TwoPlayersGame, id_solve, Human_Player, AI_Player
from easyAI.AI import TT

اکنون، برای مدیریت تمام عملیات بازی، کلاس خود را از کلاس TwoPlayerGame به ارث ببرید:

class LastCoin_game(TwoPlayersGame):
   def __init__(self, players):

اکنون بازیکنان و بازیکنی را که قرار است بازی را شروع کند، تعریف کنید.

self.players = players
self.nplayer = 1

اکنون تعداد سکه‌های بازی را تعریف کنید. در اینجا برای بازی از ۱۵ سکه استفاده می‌کنیم.

self.num_coins = 15

حداکثر تعداد سکه‌هایی را که یک بازیکن می‌تواند در هر حرکت بردارد، تعریف کنید.

self.max_coins = 4

اکنون باید چند مورد دیگر را مطابق کد زیر تعریف کنیم. حرکت‌های ممکن را مشخص کنید.

def possible_moves(self):
   return [str(a) for a in range(1, self.max_coins + 1)]

نحوه برداشتن سکه‌ها را تعریف کنید.

def make_move(self, move):
   self.num_coins -= int(move)

مشخص کنید چه کسی آخرین سکه را برداشته است.

def win_game(self):
   return self.num_coins

زمان پایان بازی را تعریف کنید؛ یعنی زمانی که یکی از بازیکنان برنده می‌شود.

def is_over(self):
   return self.win()

نحوه محاسبه امتیاز را تعریف کنید.

def score(self):
   return 100 if self.win_game() else 0

تعداد سکه‌های باقی‌مانده در توده را مشخص کنید.

def show(self):
   print(self.num_coins, 'coins left in the pile')
if __name__ == "__main__":
   tt = TT()
   LastCoin_game.ttentry = lambda self: self.num_coins

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

r, d, m = id_solve(LastCoin_game,
   range(2, 20), win_score=100, tt=tt)
print(r, d, m)

تعیین کنید چه کسی بازی را شروع خواهد کرد.

game = LastCoin_game([AI_Player(tt), Human_Player()])
game.play()

خروجی زیر و نمونه‌ای ساده از اجرای این بازی را مشاهده خواهید کرد:

d:2, a:0, m:1
d:3, a:0, m:1
d:4, a:0, m:1
d:5, a:0, m:1
d:6, a:100, m:4
1 6 4
15 coins left in the pile
Move #1: player 1 plays 4 :
11 coins left in the pile
Player 2 what do you play ? 2
Move #2: player 2 plays 2 :
9 coins left in the pile
Move #3: player 1 plays 3 :
6 coins left in the pile
Player 2 what do you play ? 1
Move #4: player 2 plays 1 :
5 coins left in the pile
Move #5: player 1 plays 4 :
1 coins left in the pile
Player 2 what do you play ? 1
Move #6: player 2 plays 1 :
0 coins left in the pile

ساخت ربات برای بازی دوز

بازی دوز بسیار شناخته‌شده است و یکی از محبوب‌ترین بازی‌ها به شمار می‌رود. بیایید با استفاده از کتابخانه easyAI در پایتون، این بازی را ایجاد کنیم. کد زیر، کد پایتون این بازی است:

بسته‌ها را مطابق زیر وارد کنید:

from easyAI import TwoPlayersGame, AI_Player, Negamax
from easyAI.Player import Human_Player

برای مدیریت تمام عملیات بازی، کلاس خود را از کلاس TwoPlayerGame به ارث ببرید:

class TicTacToe_game(TwoPlayersGame):
   def __init__(self, players):

اکنون بازیکنان و بازیکنی را که قرار است بازی را شروع کند، تعریف کنید:

self.players = players
self.nplayer = 1

نوع صفحه بازی را تعریف کنید:

self.board = [0] * 9

اکنون باید موارد زیر را تعریف کنیم:

حرکت‌های ممکن را مشخص کنید.

def possible_moves(self):
   return [x + 1 for x, y in enumerate(self.board) if y == 0]

حرکت بازیکن را تعریف کنید:

def make_move(self, move):
   self.board[int(move) - 1] = self.nplayer

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

def umake_move(self, move):
   self.board[int(move) - 1] = 0

شرط باخت را تعریف کنید؛ یعنی زمانی که حریف سه مهره را در یک ردیف قرار می‌دهد.

def condition_for_lose(self):
   possible_combinations = [[1,2,3], [4,5,6], [7,8,9],
      [1,4,7], [2,5,8], [3,6,9], [1,5,9], [3,5,7]]
   return any([all([(self.board[z-1] == self.nopponent)
      for z in combination]) for combination in possible_combinations])

شرط پایان بازی را بررسی کنید.

def is_over(self):
   return (self.possible_moves() == []) or self.condition_for_lose()

موقعیت فعلی بازیکنان در بازی را نمایش دهید.

def show(self):
   print('\n'+'\n'.join([' '.join([['.', 'O', 'X'][self.board[3*j + i]]
      for i in range(3)]) for j in range(3)]))

امتیازها را محاسبه کنید.

def scoring(self):
   return -100 if self.condition_for_lose() else 0

متد اصلی را برای تعریف الگوریتم و شروع بازی مشخص کنید:

if __name__ == "__main__":
   algo = Negamax(7)
   TicTacToe_game([Human_Player(), AI_Player(algo)]).play()

خروجی زیر و نمونه‌ای ساده از اجرای این بازی را مشاهده می‌کنید:

. . .
. . .
. . .
Player 1 what do you play ? 1
Move #1: player 1 plays 1 :
O . .
. . .
. . .
Move #2: player 2 plays 5 :
O . .
. X .
121
. . .
Player 1 what do you play ? 3
Move #3: player 1 plays 3 :
O . O
. X .
. . .
Move #4: player 2 plays 2 :
O X O
. X .
. . .
Player 1 what do you play ? 4
Move #5: player 1 plays 4 :
O X O
O X .
. . .
Move #6: player 2 plays 8 :
O X O
O X .
. X .