جلسهی 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 سطح سختی را انتخاب میکنی.
مثالهای این جلسه
- مثال تابع در پایتون: def winner(board):
- مثال تابع در پایتون: def winner(board): — یک حرکت جلوتر فکر کن
- مثال تابع در پایتون: def winner(board): — یک حرکت جلوتر فکر کن 2
چالشها
- Who Won? (آسان)
- Win or Block? (آسان)
- Win If You Can (متوسط)
- Block If You Must (متوسط)
- Minimax and Its Count (سخت)
- Show the Computer's Thinking (سخت)
بیشتر بخوان
← جلسهی 14: راه را پیدا کن جلسهی 16: پروژه: دوز شکستناپذیر →