جنون، راه گریز از رنج

مردم همیشه می‌گویند که انسان‌‌های مجنون رنج می‌کشند. اما من فکر می‌کنم دیوانگی یک راه گریز است. اگر چیزها به اندازه کافی خوب نباشند، می‌توانید چیزهای بهتر را تصور کنید – جان فوربز نش

ما همواره در جستجو هستیم. در جستجوی جواب. جواب به سوال‌هایی که حتی خودمان بنیادش را نمی‌دانیم. اما فعل یافتن امری اجتناب‌ناپذیر است. حداقل برای انسانِ زنده… از دیدگاه زیست‌شناسی تکاملی از قدیم تا به امروز عموماً تمایل ما به پیدا کردن بهینه‌ترین جواب بوده‌است.

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

یک دزدی دوستانه

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

1. جفتتان ساکت بمانید: هردو ۱سال زندان.
2. دوستتان شما را لو دهد: او آزاد می‌شود و ۳سال زندان برای شما.
3. شما دوستتان را لو دهید: آزاد خواهید شد و ۳سال زندان برای دوستتان.
4. جفتتان خیانت کنید: هردو ۲سال زندان.

توجه داشته‌ باشید که شما و دوستتان هیچ اطلاعی از تصمیم دیگری ندارید و قرار است در دو اتاق جداگانه و مجزا تصمیم بگیرید. در این شرایط چه استراتژی را برمی‌گزینید؟

این همان معمای معروف زندانی‌ها یا Prisoner’s Dilemma است که از مثال‌های ساده مورد بحث نظریه بازی می‌باشد.

استراتژی غالب (Dominant Strategy)

با کمی بررسی به این نتیجه می‌رسیم که استراتژی غالب به همه‌ی استراتژی‌ها، استراتژی چهارم ینی سکوت هردو زندانی است. برای انتخاب استراتژی غالب کافی است از یک سطر یا ستون شروع کنیم و سعی کنیم سطر/ستونی که توسط سطر/ستون مجاورش مغلوب می‌شود (مقدار عددی کمتری دارد) را حذف کنیم. در اینجا فرض کنید سطر پایین را انتخاب می‌کنیم. برای زندانی A، میزان سال زندان در هردو ستون از ردیف بالا کمتر است (صفر کمتر از یک و دو کمتر از سه). پس این سطر یک سطر مغلوب است.

حالا ستون دوم را انتخاب می‌کنیم. برای زندانی B، ستون سمت راست نسبت به ستون سمت چپ مقادیر کمتری (صفر کمتر از یک) دارد و لذا حذف می‌شود.

در نهایت استراتژی باقیمانده، استراتژی غالب است. این بدان معنی است که سود هردو زندانی در انتخاب این استراتژی می‌باشد.

تعادل نش (Nash Equilibrium)

تعادل نش به احترام ریاضی‌دان بزرگ جان فوربز نش نام‌گذاری شد. یکی از معروف‌ترین راه‌های پیداکردن جواب بهینه در بازی‌های غیرتعاملی است. جان نش در سال ۱۹۹۴ به پاس فعالیت‌هایش در حوزه الگوریتم‌های مرتبط با نظریه بازی، برنده نوبل اقتصاد شد.

برای آشنایی بیشتر با تعادل نش. فرض کنید در مثال زندانی‌ها. شما و دوستتان از انتخاب یک‌دیگر باخبر باشید. در این صورت کدام استراتژی‌را انتخاب می‌کنید؟ اگر شما بدانید که قرار است دوستتان به شما خیانت کند. آیا شما سکوت می‌کنید تا ۳سال به زندان بی‌افتید؟ طبیعاً خیر. اگر بدانید دوستتان سکوت کرده‌است و اوهم از انتخاب شما آگاه باشد، کدام استراتژی را انتخاب می‌کنید؟

تعریف تعادل نش در بیان ساده این است: استراتژی‌هایی که عملکرد هر عامل (بازیکن) بهترین عملکرد (پاسخ) نسبت به عوامل دیگر باشد.

در معمای زندانی، تنها استراتژی که تعادل نش در آن برقرار است استراتژی ۴ می‌باشد. یعنی زمانی که هردو خیانت کنید! عجیب است نه؟ اما اگر کمی تأمل کنید منطقی بنظر می‌رسد. با وجود اینکه این انتخاب، بهترین حالت قابل اتفاق نیست، اما با توجه به اینکه هردو بازیکن از انتخاب هم آگاه هستند، همیشه تعادلی در این وضعیت رخ می‌دهد. توضیح این‌که چگونه می‌توانیم این تعادل را پیدا کنیم توسط جناب نش ارائه شد و مطالعه بیشتر آن را حتماً به شما پیشنهاد می‌کنم.

گریز از رنج

فرض کنید که قرار است با زندگی‌تان دوز یا همان Tic-Tac-Toe بازی کنید. یا شاید هم با فرشته‌ی مرگ، شطرنج! (درود بر نکته‌گیران!). زندگی سعی دارد تا بر شما رنج بی‌افزاید و شما برای گریز از آن، سعی در مجنون شدن و مجنون ماندن دارید. این یک طناب دو طرفه‌است. هرچقدر زندگی آن را به سمت خود بکشد، شما رنجورتر و هرچقدر شما آن را به سمت خود بکشید، مجنون‌تر!

بیاید به این فلسفه کمی رنگ و بوی عمل بدهیم. فرض کنید جدال ما با زندگی به سادگی بازی‌کردن همان دوز 3×3 است. و جدال ما بر سر همان طناب ثابتی است که هرچقدر بیشتر به سمت ما کشیده شود، روی بیشتری از خوشبتخی را خواهیم دید. درواقع عایدی ثابت است و ما با زندگی سر آن می‌جنگیم. رنجی که ما از خود کاهش می‌دهیم، دستی‌ست که از زندگی بر ما کوتاه می‌شود. و تاثیری که زندگی بر ما می‌گذارد، رنجی‌ست که بر ما افزوده می‌شود یا خوشبتخی‌ست که از ما کاسته می‌شود. این همان بازی مجموع-صفر (Zero-Sum Game) است.

بازی مجموع-صفر (Zero-Sum Game)

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

بیاید روی مسئله جدیدمان تمرکز کنیم. فرض کنید بازی دوز در این مرحله است و نوبت بازیکن X:

با کمی دقت می‌فهمیم که کافی‌ست با انتخاب خانه ۲ بازی را به نفع خود تمام کنیم. چطور به این راه‌حل رسیدید؟ قبول دارید که در ذهن خود تمامی حالت‌های ممکن را بررسی کردید؟ حتی حالتی که باعث باخت شما می‌شود؟

بیاید مثل یک کامپیوتر به این موضوع نگاه کنیم. در هر مرحله باید تمامی انتخاب‌های موجود را بررسی کنیم و نتیجه‌ آن‌هارا بسنجیم. طبیعی است که پس از سنجش امتیاز همه مراحل، آنی را انتخاب کنیم که بیشترین امتیاز مثبت (یا کمترین امتیاز منفی) را دارد. فرض کنید در صورت پیروز شدن در این مسابقه +۱ امتیاز و در صورت شکست، -۱ امتیاز دریافت می‌کنیم. مشخص است که انتخاب خانه ۲ باعث می‌شود یک امتیاز مثبت دریافت کنیم. اما آیا می‌شود با یک نگاه در مورد خانه‌های ۱ و ۳ نظر داد؟

وقتی ما (یعنی بازیکن X) خانه ۱ را انتخاب کنیم. هنوز نمی‌توانیم در خصوص دریافت امتیاز مثبت یا منفی نظر دهیم. زیرا که هنوز بازی برقرار است. پس چطور بین ۳ یا ۲ انتخاب کنیم؟ حدس می‌زنیم! بله درست است. باید راهی پیدا کنیم که بتوانیم بهترین خانه را در وضعیت فعلی حدس بزنیم. برای این‌کار اول از همه باید بتوانیم به ازای هر حرکتی که قرار است انجام دهیم، حرکات متقابل حریف را نیز بررسی کنیم. فرضاً اگر در اینجا خانه ۱ انتخاب شود. حریف می‌تواند خانه ۲ یا ۳را انتخاب کند. در اینجا ما باید هردوی این حالات را بررسی کنیم. حال اگر حریف ما خانه ۲ را انتخاب کند. ما راهی جز خانه ۳ نداریم و بازی در حالت برابر پایان می‌یابد.

همانطور که دیدید ما توانستیم قبل از انجام حرکت، عاقبت تمامی حرکات در مقابل حریفمان (که فرض کردیم عاقل‌ترین است) را بررسی کنیم. وقتی عاقبت هر حرکت را بدانیم. خیلی راحت می‌توانیم بهترین آن‌ها را انتخاب کنیم و بازی‌را به نفع خود جلو ببریم.

طراحی بازی

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

import os
from colorama import Fore, init

init(autoreset=True)

def clear_screen():
    os.system('cls' if os.name == 'nt' else 'clear')

def print_board(board):
    clear_screen()
    print("Sufferance Escape\n")
    print(" ", Fore.RED + "Life" + Fore.RESET + " VS. " + Fore.GREEN + "Human" + Fore.RESET + "\n")
    print("    1 | 2 | 3 ")
    print("   -----------")
    print(f"  1 {format_cell(board[0])} | {format_cell(board[1])} | {format_cell(board[2])} ")
    print("   -----------")
    print(f"  2 {format_cell(board[3])} | {format_cell(board[4])} | {format_cell(board[5])} ")
    print("   -----------")
    print(f"  3 {format_cell(board[6])} | {format_cell(board[7])} | {format_cell(board[8])} ")
    print("\n   " + get_progress_bar(board) + " ")

def format_cell(cell):
    if cell == 'L':
        return Fore.RED + cell
    elif cell == 'H':
        return Fore.GREEN + cell
    else:
        return cell

def check_win(board, player):
    winning_combinations = [
        [0, 1, 2], [3, 4, 5], [6, 7, 8],  # Rows
        [0, 3, 6], [1, 4, 7], [2, 5, 8],  # Columns
        [0, 4, 8], [2, 4, 6]            # Diagonals
    ]
    
    for combo in winning_combinations:
        if all(board[i] == player for i in combo):
            return True
    return False

def is_board_full(board):
    return all(cell != ' ' for cell in board)

def get_progress_bar(board):
    num_x = board.count('L')
    num_o = board.count('H')
    empty_bar = '#' * 9

    if num_o + num_x == 0:
        return f"[{empty_bar}]"

    x_bar = Fore.RED + '#' * (9 - num_o)
    o_bar = Fore.GREEN + ('#' * num_o) + Fore.RESET

    return f"[{x_bar}{o_bar}]"

def main():
    board = [' '] * 9
    current_player = 'L'
    
    while True:
        print_board(board)
        
        if is_board_full(board):
            print("\nIt's a draw!")
            break
        
        move = input(f"\nPlayer {current_player}, enter your move (row column): ")
        try:
            row, col = map(int, move.split())
            index = (row - 1) * 3 + (col - 1)
            
            if board[index] == ' ':
                board[index] = current_player
                if check_win(board, current_player):
                    print_board(board)
                    print(Fore.YELLOW + f"\nPlayer {current_player} wins!")
                    break
                current_player = 'L' if current_player == 'H' else 'H'
            else:
                print("Invalid move. That cell is already taken.")
        except (ValueError, IndexError):
            print("Invalid input. Please enter row and column (e.g., 2 3).")

if __name__ == "__main__":
    main()

این کد از دو بخش اصلی main و check_win تشکیل شده‌است و باقی موارد برای نمایش صفحه بازی و زیباسازی آن است. در این کد یک لیست اولیه به نام board داریم که ۹ عنصر خالی دارد (صفحه ۳در۳).

برای جایگذاری در خانه فرضاً (۱،۲) کافی‌است مشخصه سطری‌را تبدیل به ضریبی از ۳ کنیم. همچنین از میزان سطر و ستون یک واحد کم می‌کنیم چون شمارنده لیست در پایتون از صفر شروع می‌شود. همچنین در یک لیست داخل تابع check_win، تمامی حالاتی که در آن‌ها برد رخ می‌دهد را ذخیره می‌کنیم تا پیاده‌سازی راحت‌تری داشته باشیم. حال کافی است تمام شرایط برد را برای بازیکن مورد نظر بررسی کنیم.

برای انتقال بهتر فلسفه‌ای که به‌دنبال پیاده‌سازی آن هستیم، یک progress bar کوچک هم پایین صفحه بازی نمایش می‌دهیم که نسبت بین خانه‌های اشغال شده توسط دو بازیکن (زندگی و انسان) را نمایش می‌دهد. نتیجه را ببینید:

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

درختِ بازی

پیش‌تر راجع‌به وضعیتی که در آن نمی‌توانیم سریعاً وضعیت برد (خاتمه) را ببینیم صحبت کردیم. اگر ما گزینه ۱ را انتخاب کنیم. نتیجه بازی کاملاً به این بستگی دارد که حریف گزینه ۲ یا ۳ را انتخاب کند. پس برای پیش‌بینی بهترین وضعیت. کافی‌است تمام ترکیبات ممکن از حرکات خودمان و حریفمان را بررسی کنیم و هرکدام که سریع‌تر مارا به وضعیت برد می‌رساند را انتخاب کنیم.

مثال طناب‌کشی بین انسان و زندگی را به‌خاطر دارید. شما می‌خواهید سهمتان از طناب را بیشتر کنید (Maximizer) و زندگی می‌خواهد سهم شمارا از طناب کمتر کند (Minimizer). یا در توصیفی دیگر؛ شما می‌خواهید در هر مرحله بیشترین امتیاز مثبت را نسبت به زندگی دریافت کنید. و زندگی می‌خواهد در هر مرحله کمترین امتیاز منفی را نسبت به شما کسب کند.

این همان الگوریتم درختی مرسوم یعنی MiniMax است. ینی تقابل بین عامل Maximizer و عامل Minimizer. ایمن و مطمئن (؟). یا به اصطلاح انگلیسی: Playing it safe. به این اسلاید که از ارائه لکچر هوش مصنوعی از دانشگاه برکلی آورده‌ام دقت کنید.

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

در مثال درختی بالا، مثلث رو به‌پایین یعنی Minimizer، رو به‌بالا Maximizer و مستعطیل نیز وضعیت خاتمه یا Terminal است. اعداد قرمز همان مقداری هستند که نود Min/Max از بین فرزندان خود انتخاب کرده‌است.

ما با این روش امتیاز MiniMax تک‌تک حرکات ممکن را حساب می‌کنیم و آن حرکتی که بیشترین امتیاز را داشت انتخاب می‌کنیم.

تابعی که امتیاز مرحله خاتمه را محاسبه می‌کند را تابع حدس یا Hueristic می‌نامند. این توابع می‌توانند در برخی پروژه‌های بزرگتر بسیار ارزشمند باشند. مثلا طراحی بازی شطرنج، نقشه‌یابی و…

هوشمند کردن زندگی

بیاید تا الگوریتمی که هم‌اکنون یاد گرفتیم را در قالب کد پیاده‌سازی کنیم. شبه‌کد این الگوریتم به‌این صورت است:

function minimax(node, depth, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, minimax(child, depth − 1, FALSE))
        return value
    else (* minimizing player *)
        value := +∞
        for each child of node do
            value := min(value, minimax(child, depth − 1, TRUE))
        return value

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

اما این کد در پروژه ما:

def get_possible_moves(board):
    return [i for i in range(len(board)) if board[i] == ' ']

def minimax(board, player, isMaximizer):
    # Heuristic
    other_player = 'L' if player == 'H' else 'H'
    if check_win(board, player):
        return 1
    if check_win(board, other_player):
        return -1
    if is_board_full(board):
        return 0

    # Maximizer
    if isMaximizer:
        value = float("-inf")
        for i in get_possible_moves(board):
            board[i] = player # Apply move
            value = max(value, minimax(board, other_player, False)) # Maximum value of minimizers
            board[i] = ' ' # Undo move
        return value

    # Minimizer
    value = float("inf")
    for i in get_possible_moves(board):
        board[i] = player # Apply move
        value = min(value, minimax(board, other_player, True)) # Minimizer value of maximizers
        board[i] = ' ' # Undo move
    return value

در بخش heuristic شروط خاتمه را بررسی می‌کنیم. اگر بازیکن فعلی (که همیشه Maximizer) است برده باشد، مثبت یک و اگر بازیکن مقابل برده باشد، منفی یک. و در صورت مساوی هم مقدار صفر برگردانده می‌شود. اگر شروط خاتمه برقرا نبود، وضعیت مینیمایز یا ماکسیمایزر را بررسی می‌کنیم. طبق توضیحات قبلی، ماکسیمایزر باید ماکسیمم امتیازهای مربوط به فرزندان مینیمایزرش را انتخاب کند. دقت کنید که امتیاز مینیمایزر باید برای بازیکن حریف محاسبه شود و نه بازیکن فعلی. و برعکس همین فرایند هم برای مینیمایز صادق است.

def get_best_move(board, player):
    best_value = float("-inf")
    best_move = None

    for i in get_possible_moves(board):
        board[i] = player # Apply move
        value = minimax(board, player, True)
        board[i] = ' ' # Undo move

    if value > best_value:
        best_value = value
        best_move = i

    return best_move

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

def main():
    ...
    current_player = 'H' # Human plays first
    ...
    try:
       if current_player == 'H':
          move = input(f"\nPlayer {current_player}, enter your move (row column): ")
          row, col = map(int, move.split())
          index = (row - 1) * 3 + (col - 1)
    else:
          index = get_best_move(board, current_player)
    ...

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

نتیجه کار را ببینیم:

تفکر بیشتر

می‌خواهم چند سرنخ به شما بدهم تا درباره این مباحث بیشتر فکر کنید. شاید هم در پست‌های بعد بیشتر راجع‌به این موضوعات بنویسم.

• آیا تعادل نش در این بازی برقرار می‌شود؟
• بنظر می‌رسد از بدو شروع نتیجه بازی مشخص است. نظر شما چیست؟
• اگر هم انسان و هم زندگی هوشمند باشند چه اتفاقی می‌افتد؟
• فرض کنیم زندگی می‌خواهد اولین حرکت را انجام دهد. چه جایگشتی از حالات ممکن وجود دارد؟
• یک بازی بزرگ‌تر در نظر بگیرید. مثل شطرنج. آیا می‌توانیم درختی به بزرگی تمام حالات صفحه شطرنج ایجاد کنیم؟
• چطوری این درخت را هرس کنیم؟ (راهنمایی: Alpha-Beta Pruning)

ریپوی گیت‌هاب: https://github.com/shahriarshm/sufferance-escape