جلسهی 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 میگیری. مینیماکس از صفحهی خالی چند صد هزار صفحه را میبیند و یکی دو ثانیه طول میکشد؛ در تمرینها از وسط بازی شروع میکنیم.
مثالهای این جلسه
- مثال تابع (هوش مصنوعی با پایتون): def winner(board):
- مثال تابع (هوش مصنوعی با پایتون): def moves(board):
- مثال تابع (هوش مصنوعی با پایتون): def minimax(board):
- مثال تابع (هوش مصنوعی با پایتون): def best_move(board):
چالشها
- Find the Winner (آسان)
- Moves and Turn (آسان)
- Score a Finished Game (متوسط)
- One Move Ahead (متوسط)
- Minimax (سخت)
- Best Move (سخت)