با استفاده از یادگیری تقویتی عمیق یک الگوریتم شطرنج طراحی کنید
الگوریتم AlphaZero توانست بدون هیچ آموزش قبلی و فقط در عرض چند ساعت رقیبان خود را در بازیهای Go، شطرنج و Shogi شکست دهد. چه عواملی به موفقیت این الگوریتم کمک کردند؟ برای ساخت این الگوریتم شطرنج از یادگیری تقویتی عمیق استفاده شد.
یادگیری تقویتی عمیق
یادگیری تقویتی عمیق به مجموعهای از الگوریتمها گفته میشود که در آن برای تکمیل q-tableها از یادگیری عمیق استفاده میشود؛ این الگوریتمها در بازیهایی به کمک ما میآیند که q-table به اندازهای پیچیده هستند که نمیتوان آنها را با الگوریتمهای brute force پر کرد.
شبکه مورد استفاده در این متد، شبکه Q عمیق نامیده میشود و ورودی آن وضعیت بازی است و برای هر یک از حرکتها، مقادیر q را خروجی میدهد.
برنامه با استفاده از این مقادیر q، جدولها را تکمیل میکند و به کمک دیگر مؤلفههای یادگیری q همچون الگوریتمهای حریصانه اپسیلون Epsilon-greedy و تنزیل پاداش (reward discounting) بازی میکند.
در گام بعدی، شبکه q با استفاده از نتایج بازیها آموزش میبیند؛ این شبکه برای اینکه وزنهای شبکه های عصبی تا حد ممکن به مقادیر حقیقی q نزدیک شوند، به آهستگی آنها را تغییر میدهد.
کد
توجه داشته باشید که من این کد را در نوتبوک Google Colab نوشتم (من شبکه، تکنیک کدگذاری و حریفی که عامل باید مقابل آن بازی کند را بازنویسی کردم)؛ به بیان دیگر برای اینکه کد عمل کند باید بخشی از آن را به جای IDE در terminal بگذارید.
گام اول – دانلود پیش نیازهای نرمافزاری
۱ |
pip install python-chess~=۰.۲۶ |
۱ |
pip install livelossplot==۰.۳.۴ |
۱ |
!wget https://www.dropbox.com/sh/۷۵gzfgu7qo94pvh/AACk_w5M94GTwwhSItCqsemoa/Stockfish%۲۰۵/stockfish-۵-linux.zip?dl=۰ |
۱ ۲ |
!unzip stockfish-۵-linux.zip?dl=۰ !chmod +x /content/stockfish-۵-linux/Linux/stockfish_14053109_x64 |
گام دوم – بیان مسئله
پیش از ایجاد عامل Deep RL، باید محیط را ایجاد کنیم.
۱ ۲ ۳ ۴ ۵ ۶ ۷ |
import chess import chess.pgn import chess.engine import torch import numpy as np board = chess.Board() board |
کد فوق تخته شطرنج را ایجاد میکند و به شما این اجازه را میدهد که آن را ببینید. برای اینکه مطمئن شویم تمامی بخشها به خوبی عمل میکند این قسمت را انجام میدهیم.
۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸ ۹ ۱۰ ۱۱ ۱۲ ۱۳ ۱۴ ۱۵ ۱۶ ۱۷ ۱۸ ۱۹ ۲۰ ۲۱ ۲۲ ۲۳ ۲۴ ۲۵ ۲۶ ۲۷ ۲۸ ۲۹ ۳۰ ۳۱ ۳۲ ۳۳ ۳۴ ۳۵ ۳۶ ۳۷ ۳۸ ۳۹ ۴۰ ۴۱ ۴۲ ۴۳ ۴۴ ۴۵ |
# A function that converts the board into matrix representation def board_to_tensor(board): chess_dict = { 'p' : [۱,۰,۰,۰,۰,۰,۰,۰,۰,۰,۰,۰,۰], 'P' : [۰,۰,۰,۰,۰,۰,۱,۰,۰,۰,۰,۰,۰], 'n' : [۰,۱,۰,۰,۰,۰,۰,۰,۰,۰,۰,۰,۰], 'N' : [۰,۰,۰,۰,۰,۰,۰,۱,۰,۰,۰,۰,۰], 'b' : [۰,۰,۱,۰,۰,۰,۰,۰,۰,۰,۰,۰,۰], 'B' : [۰,۰,۰,۰,۰,۰,۰,۰,۱,۰,۰,۰,۰], 'r' : [۰,۰,۰,۱,۰,۰,۰,۰,۰,۰,۰,۰,۰], 'R' : [۰,۰,۰,۰,۰,۰,۰,۰,۰,۱,۰,۰,۰], 'q' : [۰,۰,۰,۰,۱,۰,۰,۰,۰,۰,۰,۰,۰], 'Q' : [۰,۰,۰,۰,۰,۰,۰,۰,۰,۰,۱,۰,۰], 'k' : [۰,۰,۰,۰,۰,۱,۰,۰,۰,۰,۰,۰,۰], 'K' : [۰,۰,۰,۰,۰,۰,۰,۰,۰,۰,۰,۱,۰], '.' : [۰,۰,۰,۰,۰,۰,۰,۰,۰,۰,۰,۰,۱], } def make_matrix(board): pgn = board.epd() foo = [] pieces = pgn.split(" ", ۱)[۰] rows = pieces.split("/") for row in rows: foo2 = [] for thing in row: if thing.isdigit(): for i in range(۰, int(thing)): foo2.append('.') else: foo2.append(thing) foo.append(foo2) return foo def translate(matrix,chess_dict): rows = [] for row in matrix: terms = [] for term in row: terms.append(chess_dict[term]) rows.append(terms) return rows board_tensor = torch.Tensor(translate(make_matrix(board),chess_dict)) return board_tensor.float() board_tensor = board_to_tensor(board) board_tensor[۰].type() |
به منظور ایجاد محیط باید کاری کنیم که مدل به آسانی بتواند محیط را بخواند. برای انجام این پروژه من از کدگذاری one-hot استفاده کردم تا هر یک از مهرهها را به صورت آرایهای نشان بدهم که به روش one-hot کدگذاری شده و ۱۳ مقدار دارد. با توجه به اینکه ابعاد تخته شطرنج ۸ در ۸ است، هر یک از ورودیها به شکل (۸،۸،۱۳) هستند.
شبکه یک تنسور دیگر را خروجی میدهد و ما از آن برای انتخاب کردن حرکت بعدی استفاده میکنیم. اندازه تنسور خروجی ۶۴×۶۴ خواهد بود. اِلمان موجود در این تنسور به ما نشان میدهد کدام مهره را از کدام خانه شطرنج (۶۴ × ۶۴ خانه) باید برداریم و در خانه دیگر (۶۴ × ۶۴) بگذاریم. برای سادهتر کردن بازی فرض را بر آن میگذاریم زمانی که یکی از مهرهها (به آخر صفحه شطرنج میرسد) و قرار است ارتقاء پیدا کند، به مهره وزیر ارتقا پیدا میکند. البته توجه داشته باشید با توجه به وضعیت تخته شطرنج تمامی حرکتها مجاز نیستند اما ما در طول فرایند آموزش مدل فقط حرکتهای مجاز را مد نظر قرار میدهیم.
توابع مقابل میتوانند حالت مذکور را پیادهسازی کنند. البته ما تابعی را اجرا میکنیم که شاخص المانی را پیدا کند که حرکت در ماتریس ۶۴ × ۶۴ نشان میدهد.
۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸ ۹ ۱۰ ۱۱ ۱۲ ۱۳ ۱۴ ۱۵ ۱۶ ۱۷ ۱۸ ۱۹ ۲۰ ۲۱ ۲۲ ۲۳ ۲۴ ۲۵ ۲۶ ۲۷ ۲۸ ۲۹ ۳۰ ۳۱ ۳۲ ۳۳ ۳۴ ۳۵ ۳۶ ۳۷ ۳۸ ۳۹ |
def move_to_index_tensor(move): index_tensor = torch.LongTensor([۰]) square_to_pick_figure = move.from_square #square_to_pick_figure_row = int(square_to_pick_figure / 8) #square_to_pick_figure_col = int(square_to_pick_figure % 8) square_to_put_figure = move.to_square #square_to_put_figure_row = int(square_to_put_figure / 8) #square_to_put_figure_col = int(square_to_put_figure % 8) index = square_to_pick_figure * ۶۴ + square_to_put_figure index_tensor = torch.LongTensor([index]) return index_tensor def filter_legal_moves(legal_moves): filtered_legal_moves = [] for legal_move in legal_moves: if legal_move.promotion is not None: if legal_move.promotion == ۵: filtered_legal_moves.append(legal_move) continue filtered_legal_moves.append(legal_move) return filtered_legal_moves def legal_moves_to_index_tensors(legal_moves): legal_moves_index_tensors = [move_to_index_tensor(legal_move) for legal_move in legal_moves] return legal_moves_index_tensors |
گام سوم – ساخت شبکه عصبی
۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸ ۹ ۱۰ ۱۱ ۱۲ ۱۳ ۱۴ ۱۵ ۱۶ ۱۷ ۱۸ ۱۹ ۲۰ ۲۱ ۲۲ ۲۳ ۲۴ ۲۵ ۲۶ ۲۷ ۲۸ ۲۹ ۳۰ ۳۱ ۳۲ ۳۳ ۳۴ ۳۵ ۳۶ ۳۷ ۳۸ ۳۹ ۴۰ ۴۱ ۴۲ ۴۳ ۴۴ |
import torch.nn as nn from torch.nn import functional as F class Network(nn.Module): def __init__(self,number_of_actions=۶۴*۶۴): super(Network, self).__init__() self.conv1 = nn.Conv2d(۸, ۶۴, ۲) self.batch_norm1 = nn.BatchNorm2d(۶۴) self.conv2 = nn.Conv2d(۶۴, ۱۲۸, ۲) self.batch_norm2 = nn.BatchNorm2d(۱۲۸) self.conv3 = nn.Conv2d(۱۲۸, ۲۵۶, ۲) self.batch_norm3 = nn.BatchNorm2d(۲۵۶) self.fc1 = nn.Linear(۲۵۶, ۵۱۲) self.fc2 = nn.Linear(۵۱۲, ۱۰۲۴) self.fc3 = nn.Linear(۱۰۲۴, number_of_actions) def forward(self, x): x = F.max_pool2d(F.relu(self.conv1(x.reshape(۱,۸,۸,۱۳))), (۲,۲)) x = self.batch_norm1(x) x = F.max_pool2d(F.relu(self.conv2(x)),(۱,۲)) x = self.batch_norm2(x) x = F.relu(self.conv3(x)) x = x.view(-۱, self.num_flat_features(x)) x = F.relu(self.fc1(x)) x = F.relu(self.fc2(x)) logits = self.fc3(x) return logits def num_flat_features(self, x): size = x.size()[۱:] num_features = ۱ for s in size: num_features *= s return num_features return x net = Network(number_of_actions=۶۴*۶۴) dummy_input = torch.zeros(۱,۸,۸,۱۳) output = net(board_tensor.float()) output.shape |
برای این برنامه از PyTorch استفاده خواهم کرد. چراکه ویژگیهای آن فرایند پیادهسازی یادگیری تقویتی عمیق را تسهیل میکنند. این ویژگیها شامل نمونهبرداری ردهای Categorical sampling حرکتها میشود که بعداً آن را اجرا خواهیم کرد.
۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸ ۹ ۱۰ ۱۱ ۱۲ ۱۳ ۱۴ ۱۵ ۱۶ ۱۷ ۱۸ ۱۹ |
def discount_rewards(collected_moves, gamma=۰.۹۹): running_reward = ۰.۰ for index, collected_move in enumerate(reversed(collected_moves)): reward = collected_move[۱] running_reward = running_reward * gamma + reward collected_move[۱] = running_reward def normalize_rewards(collected_moves): normalized_rewards = np.asarray(list(map(lambda x: x[۱], collected_moves)), dtype=np.float) normalized_rewards -= np.mean(normalized_rewards) normalized_rewards /= np.std(normalized_rewards) for index, collected_move in enumerate(collected_moves): collected_move[۱] = normalized_rewards[index] |
برای اینکه مطمئن شویم پاداشها به درستی محاسبه شدهاند از این دو تابع استفاده میکنیم و در نتیجه گرادیان شبکه policy سریعتر همگرا میشود.
فرمول گرادیان شبکه policy بدین شکل است:
گام چهارم – اجرای برنامه
۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸ ۹ ۱۰ ۱۱ ۱۲ ۱۳ ۱۴ ۱۵ ۱۶ ۱۷ ۱۸ ۱۹ ۲۰ ۲۱ ۲۲ ۲۳ ۲۴ ۲۵ ۲۶ ۲۷ ۲۸ ۲۹ ۳۰ ۳۱ ۳۲ ۳۳ ۳۴ ۳۵ ۳۶ ۳۷ ۳۸ ۳۹ ۴۰ ۴۱ ۴۲ ۴۳ ۴۴ ۴۵ ۴۶ ۴۷ ۴۸ ۴۹ ۵۰ ۵۱ ۵۲ ۵۳ ۵۴ ۵۵ ۵۶ ۵۷ ۵۸ ۵۹ ۶۰ ۶۱ ۶۲ ۶۳ ۶۴ ۶۵ ۶۶ ۶۷ ۶۸ ۶۹ ۷۰ ۷۱ ۷۲ ۷۳ ۷۴ ۷۵ ۷۶ ۷۷ ۷۸ ۷۹ ۸۰ ۸۱ ۸۲ ۸۳ ۸۴ ۸۵ ۸۶ ۸۷ ۸۸ ۸۹ ۹۰ ۹۱ ۹۲ ۹۳ ۹۴ ۹۵ ۹۶ ۹۷ ۹۸ ۹۹ ۱۰۰ ۱۰۱ ۱۰۲ ۱۰۳ ۱۰۴ ۱۰۵ |
from torch.distributions import Categorical import random import chess import chess.engine def get_games_data(policy_net, episodes=۱): all_moves = [] lost_count = ۰ draw_count = ۰ win_count = ۰ game_lengths_sum = ۰.۰ for episode in range(episodes): engine = chess.engine.SimpleEngine.popen_uci("/content/stockfish-5-linux/Linux/stockfish_14053109_x64") engine.configure({"Clear Hash": True}) board = chess.Board() collected_moves = [] board_sign = ۱ move_counter = ۰.۰ while not board.is_game_over(): if board_sign == ۱: board_tensor = board_to_tensor(board) logits = policy_net(board_tensor) current_legal_moves = filter_legal_moves(list(board.legal_moves)) legal_moves_index_tensors = legal_moves_to_index_tensors(current_legal_moves) legal_moves_logits = logits[:, legal_moves_index_tensors] categorical_sampler = Categorical(logits=(legal_moves_logits)) sampled_action = categorical_sampler.sample() sampled_action_move_object = current_legal_moves[sampled_action] log_prob = categorical_sampler.log_prob(sampled_action) board.push(sampled_action_move_object) collected_moves.append([log_prob, ۰.۰]) else: result = engine.play(board, chess.engine.Limit(depth=۱۰, nodes=۱۰)) board.push(result.move) board_sign = board_sign * -۱ move_counter = move_counter + ۱ if board.is_checkmate(): if board_sign == ۱: reward = -۱.۰ lost_count = lost_count + ۱ else: reward = ۱.۰ win_count = win_count + ۱ if not board.is_checkmate(): reward = ۰.۱ draw_count = draw_count + ۱ game_lengths_sum = game_lengths_sum + move_counter collected_moves[-۱][۱] = reward discount_rewards(collected_moves) all_moves.extend(collected_moves) engine.quit() average_game_length = game_lengths_sum / episodes stats = { "lost": lost_count, "draw": draw_count, "win": win_count, "average game length": average_game_length } normalize_rewards(all_moves) return all_moves, stats collected_moves, stats = get_games_data(policy_net=net, episodes=۱) |
گام پنجم – آموزش شبکه Policy
۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸ ۹ ۱۰ |
import torch import torch.optim as optim net = Network(number_of_actions=۶۴*۶۴) optimizer = optim.Adam(net.parameters(), lr=۰.۰۱) from livelossplot import PlotLosses liveloss = PlotLosses() |
۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸ ۹ ۱۰ ۱۱ ۱۲ ۱۳ ۱۴ ۱۵ ۱۶ ۱۷ ۱۸ ۱۹ ۲۰ ۲۱ ۲۲ ۲۳ ۲۴ ۲۵ |
while True: collected_moves, stats = get_games_data(policy_net=net, episodes=۱۰۰) logs = [collected_move[۰] for collected_move in collected_moves] rewards = [collected_move[۱] for collected_move in collected_moves] logs_tensor = torch.cat(logs) rewards_tensor = torch.FloatTensor(rewards) optimizer.zero_grad() policy_loss = -logs_tensor * rewards_tensor policy_loss = policy_loss.sum() policy_loss.backward() optimizer.step() liveloss.update(stats) liveloss.draw() |