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

الگوریتم 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~=0.26

Python-chess کتابخانه‌ای است که از آن برای ایجاد محیط بازی استفاده می‌شود؛ محیط بازی، محیطی است که عامل با آن تعامل برقرار می‌کند.

pip install livelossplot==0.3.4

در زمان آموزش عامل، برای ترسیم روند پیشرفت آن از livelossplot استفاده می‌کنیم.

!wget https://www.dropbox.com/sh/75gzfgu7qo94pvh/AACk_w5M94GTwwhSItCqsemoa/Stockfish%205/stockfish-5-linux.zip?dl=0

کد زیر stockfish-5، که عامل باید در مقابل آن بازی کند، را  دانلود می‌کند. شما می‌توانید همان مرحله (رقیب) stockfish را هم بازی کنید اما به عقیده من stockfish-5  بهتر است.

!unzip stockfish-5-linux.zip?dl=0
!chmod +x /content/stockfish-5-linux/Linux/stockfish_14053109_x64

این دو فرمان را به صورت جداگانه اجرا کنید، چرا که در این صورت می‌توانید به آسانی به الگوریتم stockfish دسترسی پیدا کنید.

گام دوم – بیان مسئله

پیش از ایجاد عامل 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' : [1,0,0,0,0,0,0,0,0,0,0,0,0],
        'P' : [0,0,0,0,0,0,1,0,0,0,0,0,0],
        'n' : [0,1,0,0,0,0,0,0,0,0,0,0,0],
        'N' : [0,0,0,0,0,0,0,1,0,0,0,0,0],
        'b' : [0,0,1,0,0,0,0,0,0,0,0,0,0],
        'B' : [0,0,0,0,0,0,0,0,1,0,0,0,0],
        'r' : [0,0,0,1,0,0,0,0,0,0,0,0,0],
        'R' : [0,0,0,0,0,0,0,0,0,1,0,0,0],
        'q' : [0,0,0,0,1,0,0,0,0,0,0,0,0],
        'Q' : [0,0,0,0,0,0,0,0,0,0,1,0,0],
        'k' : [0,0,0,0,0,1,0,0,0,0,0,0,0],
        'K' : [0,0,0,0,0,0,0,0,0,0,0,1,0],
        '.' : [0,0,0,0,0,0,0,0,0,0,0,0,1],
    }
def make_matrix(board): 
        pgn = board.epd()
        foo = []  
        pieces = pgn.split(" ", 1)[0]
        rows = pieces.split("/")
        for row in rows:
            foo2 = []  
            for thing in row:
                if thing.isdigit():
                    for i in range(0, 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[0].type()

به منظور ایجاد محیط باید کاری کنیم که مدل به آسانی بتواند محیط را بخواند. برای انجام این پروژه من از کدگذاری one-hot استفاده کردم تا هر یک از مهره‌‌ها را به صورت آرایه‌ای نشان بدهم که به روش one-hot کدگذاری شده‌ و 13 مقدار دارد. با توجه به اینکه ابعاد تخته شطرنج 8 در 8 است، هر یک از ورودی‌ها به شکل (8،8،13) هستند.

شبکه یک تنسور دیگر را خروجی می‌دهد و ما از آن برای انتخاب کردن حرکت بعدی استفاده می‌کنیم. اندازه تنسور خروجی 64×64 خواهد بود. اِلمان موجود در این تنسور به ما نشان می‌دهد کدام مهره را از کدام خانه شطرنج (64 × 64 خانه) باید برداریم و در خانه دیگر (64 × 64) بگذاریم. برای ساده‌تر کردن بازی فرض را بر آن می‌گذاریم زمانی که یکی از مهره‌ها (به آخر صفحه شطرنج می‌رسد) و قرار است ارتقاء پیدا کند، به مهره وزیر ارتقا پیدا می‌کند. البته توجه داشته باشید با توجه به وضعیت تخته شطرنج تمامی حرکت‌ها مجاز نیستند اما ما در طول فرایند آموزش مدل فقط حرکت‌های مجاز را مد نظر قرار می‌دهیم.

توابع مقابل می‌توانند حالت مذکور را پیاده‌سازی کنند. البته ما تابعی را اجرا می‌کنیم که شاخص المانی را پیدا کند که حرکت  در ماتریس 64 × 64 نشان می‌دهد.

def move_to_index_tensor(move):
  
    index_tensor = torch.LongTensor([0])

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 * 64 + 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 == 5:

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=64*64):
        super(Network, self).__init__()
        self.conv1 = nn.Conv2d(8, 64, 2)
        self.batch_norm1 = nn.BatchNorm2d(64)
        self.conv2 = nn.Conv2d(64, 128, 2)
        self.batch_norm2 = nn.BatchNorm2d(128)
        self.conv3 = nn.Conv2d(128, 256, 2)
        self.batch_norm3 = nn.BatchNorm2d(256)
        self.fc1 = nn.Linear(256, 512)
        self.fc2 = nn.Linear(512, 1024)
        self.fc3 = nn.Linear(1024, number_of_actions)

def forward(self, x):
        x = F.max_pool2d(F.relu(self.conv1(x.reshape(1,8,8,13))),
(2,2))
        x = self.batch_norm1(x)
        x = F.max_pool2d(F.relu(self.conv2(x)),(1,2))
        x = self.batch_norm2(x)
        x = F.relu(self.conv3(x))
        x = x.view(-1, 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()[1:] 
        num_features = 1
        for s in size:
            num_features *= s
        return num_features

return x

net = Network(number_of_actions=64*64)

dummy_input = torch.zeros(1,8,8,13)
output = net(board_tensor.float())
output.shape

برای این برنامه از PyTorch استفاده خواهم کرد. چراکه ویژگی‌های آن فرایند پیاده‌سازی یادگیری تقویتی عمیق را تسهیل می‌کنند. این ویژگی‌ها شامل نمونه‌برداری رده‌ای Categorical sampling حرکت‌ها می‌شود که بعداً آن را اجرا خواهیم کرد.

def discount_rewards(collected_moves, gamma=0.99):
    
    running_reward = 0.0
for index, collected_move in enumerate(reversed(collected_moves)):
        
        reward = collected_move[1]
        running_reward = running_reward * gamma + reward
        collected_move[1] = running_reward
def normalize_rewards(collected_moves):
    
    normalized_rewards = np.asarray(list(map(lambda x: x[1], 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[1] = normalized_rewards[index]

برای اینکه مطمئن شویم پاداش‌ها به درستی محاسبه شده‌اند از این دو تابع استفاده می‌کنیم و در نتیجه  گرادیان شبکه policy سریع‌تر همگرا می‌شود.

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

گام چهارم – اجرای برنامه

from torch.distributions import Categorical
import random
import chess
import chess.engine

def get_games_data(policy_net, episodes=1):
  
    all_moves = []
    
    lost_count = 0
    draw_count = 0
    win_count = 0
    
    
    game_lengths_sum = 0.0
    
    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 = 1
        move_counter = 0.0
        
        while not board.is_game_over():

if board_sign == 1:

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, 0.0])

else:
                
                result = engine.play(board, 
chess.engine.Limit(depth=10, nodes=10))
                board.push(result.move)

board_sign = board_sign * -1
            move_counter = move_counter + 1

if board.is_checkmate():
          
          if board_sign == 1:
            
            reward = -1.0
            lost_count = lost_count + 1
          else:
            
            reward = 1.0
            win_count = win_count + 1
        
        if not board.is_checkmate():
          
          reward = 0.1
          draw_count = draw_count + 1

game_lengths_sum = game_lengths_sum + move_counter
        
        collected_moves[-1][1] = 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=1)

این تابع تمامی مؤلفه‌هایی که در مرحله قبلی به آن‌ها اشاره کردیم را شامل می‌شود و به صورت همزمان آن‌ها را اجرا می‌کند. این تابع را یک بار فراخون می‌کنیم تا از عملکرد صحیح آن مطمئن شویم.

گام پنجم – آموزش شبکه Policy

import torch
import torch.optim as optim

net = Network(number_of_actions=64*64)

optimizer = optim.Adam(net.parameters(), lr=0.01)

from livelossplot import PlotLosses

liveloss = PlotLosses()

بهینه‌ساز و liveloss مقداردهی می‌شوند و از این طریق این بخش برای تابع آموزش آماده می‌شود؛ liveloss روند پیشرفت عامل را نشان می‌دهد.

while True:
    
    collected_moves, stats = get_games_data(policy_net=net, 
episodes=100)
    
    logs = [collected_move[0] for collected_move in 
collected_moves]
    rewards = [collected_move[1] 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()

این تابع آموزش یادگیری تقویتی عمیق را آغاز می‌کند. شما می‌توانید تعداد اپیزودها در هر مرحله و هم‌چنین معماری شبکه را تعیین کنید تا نتایج آموزش را ارتقا دهید.