بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 38: بازی و جست‌وجو Games and Search

هوش بدون یادگیری: کامپیوتر دوز (tic-tac-toe) را با نگاه کردن به همه‌ی آینده‌های ممکن می‌بَرد. الگوریتم مینی‌ماکس.

در این جلسه یاد می‌گیری

درس

تا اینجا هوش مصنوعی یعنی «یادگیری از داده». ولی نوع دیگری هم هست که اصلاً داده نمی‌خواهد: جست‌وجو. برنامه‌ی شطرنج دیپ‌بلو که در ۱۹۹۷ قهرمان جهان را برد، یاد نگرفته بود؛ فقط میلیون‌ها حرکت آینده را بررسی می‌کرد. امروز همین را برای دوز می‌سازیم، که به اندازه‌ی کافی کوچک است تا همه‌ی آینده‌ها را ببینیم.

صفحه: یک لیست ۹تایی، خانه‌های ۰ تا ۸، هر خانه "X"، "O" یا " " (خالی). هشت خط برنده داریم: سه سطر، سه ستون، دو قطر. برنده کسی است که هر سه خانه‌ی یک خط را دارد.

LINES = [(0, 1, 2), (3, 4, 5), (6, 7, 8),
         (0, 3, 6), (1, 4, 7), (2, 5, 8),
         (0, 4, 8), (2, 4, 6)]

def winner(board):
    for a, b, c in LINES:
        if board[a] != " " and board[a] == board[b] == board[c]:
            return board[a]
    return None

board = ["X", "O", "X",
         " ", "X", "O",
         "O", " ", "X"]
print(winner(board))   # X

حرکت‌های مجاز: شماره‌ی خانه‌های خالی. نوبت را هم باید بدانیم: اگر تعداد X و O برابر است نوبت X است، وگرنه O. بازی وقتی تمام است که برنده داشته باشیم یا هیچ خانه‌ی خالی نمانده باشد (مساوی).

def moves(board):
    return [i for i in range(9) if board[i] == " "]

def turn(board):
    return "X" if board.count("X") == board.count("O") else "O"

print(moves(board))   # [3, 7]
print(turn(board))    # O

ایده‌ی مینی‌ماکس: به هر پایان بازی یک امتیاز بده: برد X = +۱، برد O = −۱، مساوی = ۰. X می‌خواهد امتیاز را بیشینه کند، O می‌خواهد کمینه کند. برای هر حرکت ممکن، فرض کن آن را انجام دادی و بپرس: «بهترین نتیجه‌ای که از اینجا به بعد می‌گیرم چیست، اگر حریف هم بهترین بازی را بکند؟» این سؤال خودش همان سؤال اصلی است، فقط یک حرکت جلوتر. پس تابع خودش را صدا می‌زند: بازگشت (recursion).

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

def minimax(board):
    w = winner(board)
    if w == "X":
        return 1
    if w == "O":
        return -1
    if not moves(board):
        return 0
    scores = []
    for m in moves(board):
        new_board = board[:]
        new_board[m] = turn(board)
        scores.append(minimax(new_board))
    if turn(board) == "X":
        return max(scores)
    return min(scores)

بهترین حرکت: برای هر حرکت ممکن امتیاز مینی‌ماکس را حساب کن و حرکتی را بردار که برای بازیکن فعلی بهترین است. این بازیکن هیچ‌وقت نمی‌بازد! دوز با مینی‌ماکس همیشه حداقل مساوی می‌کند. برای شطرنج این کار ناممکن است (آینده‌ها بیشتر از اتم‌های جهان‌اند)، برای همین برنامه‌های شطرنج مینی‌ماکس را با «حدس ارزش صفحه» ترکیب می‌کنند، و برنامه‌های مدرن آن حدس را با شبکه‌ی عصبی یاد می‌گیرند. جست‌وجو + یادگیری = آلفاگو.

def best_move(board):
    player = turn(board)
    best = None
    best_score = None
    for m in moves(board):
        new_board = board[:]
        new_board[m] = player
        score = minimax(new_board)
        if best is None or (player == "X" and score > best_score) or (player == "O" and score < best_score):
            best, best_score = m, score
    return best

اشتباه رایج: کپی نکردن صفحه (new_board = board به جای board[:])؛ آن‌وقت همه‌ی شاخه‌ها روی یک لیست می‌نویسند و همه‌چیز خراب می‌شود. اشتباه دوم: فراموش کردن حالت مساوی؛ بازگشت هیچ‌وقت تمام نمی‌شود و خطای RecursionError می‌گیری. مینی‌ماکس از صفحه‌ی خالی چند صد هزار صفحه را می‌بیند و یکی دو ثانیه طول می‌کشد؛ در تمرین‌ها از وسط بازی شروع می‌کنیم.

مثال‌های این جلسه

چالش‌ها

  1. Find the Winner (آسان)
  2. Moves and Turn (آسان)
  3. Score a Finished Game (متوسط)
  4. One Move Ahead (متوسط)
  5. Minimax (سخت)
  6. Best Move (سخت)

بیشتر بخوان

← جلسه‌ی 37: پیشنهادگر جلسه‌ی 39: مدل‌های بزرگ: پشت صحنه →