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

جلسه‌ی 15: یک حرکت جلوتر فکر کن Thinking Ahead

کامپیوتر دوز چطور فکر می‌کند: اول «اگر می‌توانی ببری، ببر؛ اگر باید، ببند»، بعد مینی‌ماکس: «من بهترین را می‌خواهم، حریف بدترین را برای من».

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

درس

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

صفحه یک لیست ۹تایی است، خانه‌های 0 تا 8 سطر به سطر، هر خانه "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))

یک حرکت جلوتر، مثل فوتبال: اگر جلوی دروازه‌ی خالی هستی، شوت بزن (ببر اگر می‌توانی). اگر حریف دارد گل می‌زند، جلویش را بگیر (ببند اگر باید). کامپیوتر این را با «امتحان و پس گرفتن» می‌فهمد: مهره را در هر خانه‌ی خالی می‌گذارد، نگاه می‌کند برنده شد یا نه، و دوباره خالی‌اش می‌کند.

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

def winning_move(board, p):
    for i in range(9):
        if board[i] == " ":
            board[i] = p
            w = winner(board)
            board[i] = " "
            if w == p:
                return i
    return None

board = ["O", "O", " ",
         "X", "X", " ",
         " ", " ", " "]
print("O wins at", winning_move(board, "O"))
print("X wins at", winning_move(board, "X"))

مینی‌ماکس چند حرکت جلوتر را می‌بیند: «اگر من این‌جا بزنم، حریف بهترین جوابش را می‌دهد، بعد من…». قانونش یک جمله است: من بهترین را می‌خواهم، حریف بدترین را برای من. برد O = 1، مساوی = 0، باخت = -1. نوبت O بزرگ‌ترین (max) را برمی‌دارد، نوبت X کوچک‌ترین (min) را. تابع minimax خودش را صدا می‌زند، مثل دو آینه روبه‌روی هم؛ وقتی بازی تمام شود، می‌ایستد.

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

def minimax(board, turn):
    w = winner(board)
    if w == "O":
        return 1
    if w == "X":
        return -1
    if " " not in board:
        return 0
    scores = []
    for i in range(9):
        if board[i] == " ":
            board[i] = turn
            if turn == "O":
                scores.append(minimax(board, "X"))
            else:
                scores.append(minimax(board, "O"))
            board[i] = " "
    if turn == "O":
        return max(scores)
    return min(scores)

board = ["X", "O", "X",
         " ", "O", " ",
         " ", " ", "X"]
print("score for O:", minimax(board, "O"))

بازی بدون کامپیوتر: یک دوز نیمه‌تمام (سه خانه‌ی خالی) روی تخته بکشید. کلاس دو گروه می‌شود و هر گروه برای وضعیتی که گروه دیگر کشیده، درخت بازی می‌کشد: همه‌ی حرکت‌های بعدی شاخه می‌شوند تا آخر بازی. ته هر شاخه برد، مساوی یا باخت را بنویسید، بعد از پایین بالا بیایید: در ردیف O بهترین، در ردیف X بدترین را انتخاب کنید.

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

در پروژه: جلسه‌ی بعد همه‌ی این‌ها روی صفحه‌ی بازی با موس کنار هم می‌نشینند: کلیک تو X می‌گذارد، کامپیوتر اول تصادفی، بعد «یک حرکت جلوتر» و آخر با مینی‌ماکس جواب می‌دهد، و تو با کلیدهای 1، 2، 3 سطح سختی را انتخاب می‌کنی.

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

چالش‌ها

  1. Who Won? (آسان)
  2. Win or Block? (آسان)
  3. Win If You Can (متوسط)
  4. Block If You Must (متوسط)
  5. Minimax and Its Count (سخت)
  6. Show the Computer's Thinking (سخت)

بیشتر بخوان

← جلسه‌ی 14: راه را پیدا کن جلسه‌ی 16: پروژه: دوز شکست‌ناپذیر →