Алгоритм поиска по дереву Монте-Карло (MCTS) — это метод, который помогает компьютеру находить лучший ход в играх (например, в шахматах или Го), не перебирая миллиарды вариантов, а симулируя случайные партии.
Простыми словами: вместо того чтобы думать как идеальный математик, алгоритм думает как человек — он «прокручивает» в голове разные варианты до конца игры и смотрит, какой ход чаще приводит к победе.
Четыре шага алгоритма (Как это работает)
Каждый ход MCTS состоит из четырех быстрых шагов, которые повторяются тысячи раз за секунду:
[ Выбор ] ---> [ Расширение ] ---> [ Симуляция ] ---> [ Обратное распространение ]
- Выбор (Selection)
Алгоритм спускается по уже известному ему дереву ходов от текущей позиции. Он выбирает те ходы, которые раньше приносили победу. Но иногда он специально выбирает неизученные ходы, чтобы проверить — вдруг они лучше. - Расширение (Expansion)
Когда алгоритм доходит до края изученных ходов (где он еще не знает, что будет дальше), он добавляет в свою память один или несколько новых возможных ходов. - Симуляция / Розыгрыш (Simulation)
Из этой новой точки компьютер начинает играть сам с собой абсолютно случайно и очень быстро до самого конца партии (пока кто-то не выиграет или не проиграет). - Обратное распространение (Backpropagation)
Компьютер смотрит на результат случайной игры (например, «Победа»). Он возвращается в самое начало и ставит «плюсик» всем ходам, которые привели к этой победе.
Простая аналогия: Выбор ресторана
Представьте, что вы приехали в новый город и хотите каждый день ходить в лучшее кафе, но у вас есть всего 10 дней:
- Первые дни (Разведка): Вы каждый день ходите в случайные новые места. Одно вам очень понравилось, другое — ужасно.
- Середина отпуска (Баланс): Вы хотите пойти в то место, где уже было вкусно (эксплуатация успеха). Но краем уха вы слышали, что за углом есть еще одно кафе. Вы рискуете и идете туда (исследование).
- Итог: К концу отпуска на основе своего опыта (симуляций) вы точно знаете, какое кафе принесло вам больше всего удовольствия, и ходите только туда.
Почему MCTS — это круто?
- Ему не нужен эксперт: Алгоритму не нужно объяснять правила стратегии. Достаточно просто сказать: «вот так можно ходить, а вот это — победа». Он сам поймет, какие ходы ведут к выигрышу через тысячи случайных симуляций.
- Экономия времени: Он не тратит силы на просчет заведомо глупых ходов. Если ход один раз привел к мгновенному проигрышу, алгоритм почти не будет тратить время на его глубокий анализ.
Именно этот алгоритм в сочетании с нейросетями лежит в основе AlphaGo — программы, которая впервые в истории победила чемпиона мира по игре в Го.
Если вы хотите запрограммировать этот алгоритм, я могу показать простой пример кода или подробнее разобрать формулу UCB1, по которой компьютер решает, исследовать новый ход или выбирать старый. Что из этого вам интересно?
Вот минимальный и понятный пример реализации алгоритма MCTS для игры в Крестики-Нолики на языке Python.
Для простоты код разбит на три логические части: игровое поле, сам узел дерева MCTS и цикл симуляции.
1. Игровой движок (Крестики-Нолики)
Этот класс отвечает за правила игры: хранит доску, делает ходы и проверяет, есть ли победитель.
import math
import random
class TicTacToe:
def __init__(self):
self.board = [' '] * 9 # Доска из 9 клеток (индексы 0-8)
self.current_player = 'X' # Первыми ходят Крестики
def get_legal_moves(self):
"""Возвращает список индексов пустых клеток."""
return [i for i, spot in enumerate(self.board) if spot == ' ']
def make_move(self, move):
"""Делает ход и передает управление другому игроку."""
self.board[move] = self.current_player
self.current_player = 'O' if self.current_player == 'X' else 'X'
def check_winner(self):
"""Возвращает (Игра окончена?, Кто победил)."""
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] # Диагонали
]
for line in lines:
if self.board[line[0]] == self.board[line[1]] == self.board[line[2]] != ' ':
return True, self.board[line[0]] # Есть победитель
if ' ' not in self.board:
return True, 'Tie' # Ничья
return False, None # Игра продолжается
def clone(self):
"""Создает копию игры для симуляций в уме."""
new_state = TicTacToe()
new_state.board = list(self.board)
new_state.current_player = self.current_player
return new_state
2. Узел дерева поиска (MCTS Node)
Каждый узел хранит состояние доски, количество своих посещений, побед и список ещё не проверенных ходов. Тут же применяется математическая формула UCT (Upper Confidence Bound), чтобы выбирать самый перспективный ход.
class MCTSNode:
def __init__(self, state, parent=None, move=None):
self.state = state # Состояние игры в этом узле
self.parent = parent # Родительский узел
self.move = move # Ход, который привел в этот узел
self.children = [] # Список дочерних узлов
self.wins = 0 # Очки побед
self.visits = 0 # Количество посещений узла
self.untried_moves = state.get_legal_moves() # Ходы, которые мы еще не пробовали отсюда
def uct_select_child(self):
"""Выбирает лучший дочерний узел по формуле UCB1."""
# Формула балансирует между эксплуатацией успеха (wins/visits) и исследованием редких ходов
return max(
self.children,
key=lambda c: (c.wins / c.visits) + math.sqrt(2 * math.log(self.visits) / c.visits)
)
def update(self, winner):
"""Обновляет статистику узла после завершения симуляции."""
self.visits += 1
# Определяем, кто сделал ход, приведший в этот узел
# Если сейчас ходить X, значит этот узел был создан ходом игрока O
who_moved = 'O' if self.state.current_player == 'X' else 'X'
if winner == who_moved:
self.wins += 1 # Победа игрока, совершившего ход
elif winner == 'Tie':
self.wins += 0.5 # За ничью даем пол-очка
3. Главный алгоритм MCTS
Функция берет текущее положение на доске и запускает itermax кругов симуляций (например, 1000 раз), чтобы найти идеальный ход.
def mcts_find_best_move(root_state, itermax=1000):
root_node = MCTSNode(state=root_state)
for _ in range(itermax):
node = root_node
state = root_state.clone()
# 1. ВЫБОР (Selection)
# Спускаемся по дереву, пока у узлов нет неисследованных ходов и есть дети
while not node.untried_moves and node.children:
node = node.uct_select_child()
state.make_move(node.move)
# 2. РАСШИРЕНИЕ (Expansion)
# Если нашли узел, где есть неисследованные ходы, создаем для одного из них новый узел
if node.untried_moves:
move = random.choice(node.untried_moves)
node.untried_moves.remove(move)
state.make_move(move)
child_node = MCTSNode(state=state, parent=node, move=move)
node.children.append(child_node)
node = child_node
# 3. СИМУЛЯЦИЯ (Simulation / Розыгрыш)
# Быстро и случайно доигрываем партию до конца в виртуальной копии доски
game_over, winner = state.check_winner()
while not game_over:
possible_moves = state.get_legal_moves()
state.make_move(random.choice(possible_moves))
game_over, winner = state.check_winner()
# 4. ОБРАТНОЕ РАСПРОСТРАНЕНИЕ (Backpropagation)
# Поднимаемся обратно к корню дерева и обновляем статистику каждого узла
while node is not None:
node.update(winner)
node = node.parent
# В итоге лучшим ходом считается тот, узел которого посещали чаще всего
best_child = max(root_node.children, key=lambda c: c.visits)
return best_child.move
Как это запустить и проверить?
Давайте создадим игровую ситуацию. Например, Крестики (X) заняли центр поля, а Нолики (O) ответили в левый верхний угол. Попросим MCTS найти лучший ответный ход для Крестиков:
# Создаем игру
game = TicTacToe()
# Симулируем начало партии
game.make_move(4) # X ходит в центр (индекс 4)
game.make_move(0) # O ходит в левый верхний угол (индекс 0)
# Просим MCTS подумать (сделать 2000 симуляций «в голове»)
best_move = mcts_find_best_move(game, itermax=2000)
print(f"Робот считает, что лучший следующий ход для X — это клетка №: {best_move}")
Как алгоритм рассуждает во время работы кода?
- Он берет текущую доску и видит 7 пустых клеток.
- Пробует сходить в клетку №1. После этого запускает случайный «доигрыш» 50 раз подряд. Замечает, что Крестики выиграли 30 раз.
- Пробует сходить в другую клетку. Случайный доигрыш показывает, что Крестики там чаще проигрывают.
- С помощью формулы UCT алгоритм начинает копать глубже именно в ту клетку, где побед было больше, проверяя ответы Ноликов.
- Спустя 2000 симуляций он выдает ход, который статистически чаще всего приводил к победе Х.
Хотите, добавим к этому коду простой текстовый интерфейс, чтобы вы могли прямо в консоли сыграть против этого алгоритма и проверить, насколько тяжело у него выиграть?
Вот готовый скрипт, который объединяет весь предыдущий код и добавляет текстовый интерфейс. Вы можете скопировать его целиком, запустить в любом Python-файле и сыграть против искусственного интеллекта.
Вы будете играть за Ноликов (O), а алгоритм MCTS — за Крестиков (X). Он будет делать первый ход.
import math
import random
# =====================================================================
# 1. ИГРОВОЙ ДВИЖОК
# =====================================================================
class TicTacToe:
def __init__(self):
self.board = [' '] * 9 # Доска из 9 клеток
self.current_player = 'X' # X ходит первым
def get_legal_moves(self):
return [i for i, spot in enumerate(self.board) if spot == ' ']
def make_move(self, move):
self.board[move] = self.current_player
self.current_player = 'O' if self.current_player == 'X' else 'X'
def check_winner(self):
lines = [, [3, 4, 5], [6, 7, 8], # Горизонтали, [1, 4, 7], [2, 5, 8], # Вертикали, [2, 4, 6] # Диагонали
]
for line in lines:
if self.board[line[0]] == self.board[line[1]] == self.board[line[2]] != ' ':
return True, self.board[line[0]]
if ' ' not in self.board:
return True, 'Tie'
return False, None
def clone(self):
new_state = TicTacToe()
new_state.board = list(self.board)
new_state.current_player = self.current_player
return new_state
def print_board(self):
"""Красивый вывод доски в консоль с номерами подсказок."""
print("\n")
for i in range(3):
# Выводим игровое поле
board_line = f" {self.board[i*3]} | {self.board[i*3+1]} | {self.board[i*3+2]} "
# Выводим подсказку с номерами кнопок для игрока
hint_line = f" [ Номера клеток: {i*3} {i*3+1} {i*3+2} ]"
print(board_line + hint_line)
if i < 2:
print("---+---+---")
print("\n")
# =====================================================================
# 2. УЗЕЛ ДЕРЕВА MCTS
# =====================================================================
class MCTSNode:
def __init__(self, state, parent=None, move=None):
self.state = state
self.parent = parent
self.move = move
self.children = []
self.wins = 0
self.visits = 0
self.untried_moves = state.get_legal_moves()
def uct_select_child(self):
return max(
self.children,
key=lambda c: (c.wins / c.visits) + math.sqrt(2 * math.log(self.visits) / c.visits)
)
def update(self, winner):
self.visits += 1
who_moved = 'O' if self.state.current_player == 'X' else 'X'
if winner == who_moved:
self.wins += 1
elif winner == 'Tie':
self.wins += 0.5
# =====================================================================
# 3. АЛГОРИТМ ПОИСКА
# =====================================================================
def mcts_find_best_move(root_state, itermax=3000):
root_node = MCTSNode(state=root_state)
for _ in range(itermax):
node = root_node
state = root_state.clone()
# 1. Выбор
while not node.untried_moves and node.children:
node = node.uct_select_child()
state.make_move(node.move)
# 2. Расширение
if node.untried_moves:
move = random.choice(node.untried_moves)
node.untried_moves.remove(move)
state.make_move(move)
child_node = MCTSNode(state=state, parent=node, move=move)
node.children.append(child_node)
node = child_node
# 3. Симуляция
game_over, winner = state.check_winner()
while not game_over:
possible_moves = state.get_legal_moves()
state.make_move(random.choice(possible_moves))
game_over, winner = state.check_winner()
# 4. Обратное распространение
while node is not None:
node.update(winner)
node = node.parent
best_child = max(root_node.children, key=lambda c: c.visits)
return best_child.move
# =====================================================================
# 4. ИГРОВОЙ ЦИКЛ
# =====================================================================
def play_game():
print("Добро пожаловать в игру против MCTS ИИ!")
print("Вы играете за 'O' (Нолики). Компьютер играет за 'X' (Крестики) и ходит первым.")
game = TicTacToe()
while True:
game.print_board()
game_over, winner = game.check_winner()
if game_over:
if winner == 'Tie':
print("Ничья! Хорошая игра.")
else:
print(f"Игра окончена! Победитель: {winner}")
break
if game.current_player == 'X':
print("ИИ думает (симулирует 3000 партий в уме)...")
# Настройки itermax=3000 хватает, чтобы ИИ вообще не ошибался в крестиках-ноликах
move = mcts_find_best_move(game, itermax=3000)
game.make_move(move)
print(f"ИИ сделал ход в клетку {move}")
else:
# Ход человека
legal_moves = game.get_legal_moves()
while True:
try:
move = int(input(f"Ваш ход (выберите свободный номер {legal_moves}): "))
if move in legal_moves:
break
else:
print("Эта клетка уже занята или её не существует!")
except ValueError:
print("Пожалуйста, введите число от 0 до 8.")
game.make_move(move)
if __name__ == "__main__":
play_game()
Как проверить силу алгоритма?
Особенность MCTS в том, что при 3000 симуляций на каждый ход в такой простой игре как крестики-нолики, алгоритм за пару секунд просчитает абсолютно все цепочки событий до конца. Выиграть у него станет физически невозможно. Максимум, чего получится добиться идеальной игрой — это свести партию к ничьей.
Если вы хотите сделать ИИ «глупее» и дать себе шанс на победу, измените параметр количества симуляций в строке:
move = mcts_find_best_move(game, itermax=20) # Сделайте 15-20 вместо 3000
Тогда алгоритм начнет совершать человеческие ошибки, так как его «интуиция» на основе случайных симуляций не успеет полностью собраться.
Если вам будет интересно, мы можем обсудить, как именно изменить этот код, чтобы превратить его в другую текстовую игру (например, Ним или Камень-Ножницы-Бумага), или разобрать какую-то конкретную строчку в логике дерева поиска. Что скажете?
Вот готовый скрипт, который объединяет весь предыдущий код и добавляет текстовый интерфейс. Вы можете скопировать его целиком, запустить в любом Python-файле и сыграть против искусственного интеллекта.
Вы будете играть за Ноликов (O), а алгоритм MCTS — за Крестиков (X). Он будет делать первый ход.
import math
import random
# =====================================================================
# 1. ИГРОВОЙ ДВИЖОК
# =====================================================================
class TicTacToe:
def __init__(self):
self.board = [' '] * 9 # Доска из 9 клеток
self.current_player = 'X' # X ходит первым
def get_legal_moves(self):
return [i for i, spot in enumerate(self.board) if spot == ' ']
def make_move(self, move):
self.board[move] = self.current_player
self.current_player = 'O' if self.current_player == 'X' else 'X'
def check_winner(self):
lines = [, [3, 4, 5], [6, 7, 8], # Горизонтали, [1, 4, 7], [2, 5, 8], # Вертикали, [2, 4, 6] # Диагонали
]
for line in lines:
if self.board[line[0]] == self.board[line[1]] == self.board[line[2]] != ' ':
return True, self.board[line[0]]
if ' ' not in self.board:
return True, 'Tie'
return False, None
def clone(self):
new_state = TicTacToe()
new_state.board = list(self.board)
new_state.current_player = self.current_player
return new_state
def print_board(self):
"""Красивый вывод доски в консоль с номерами подсказок."""
print("\n")
for i in range(3):
# Выводим игровое поле
board_line = f" {self.board[i*3]} | {self.board[i*3+1]} | {self.board[i*3+2]} "
# Выводим подсказку с номерами кнопок для игрока
hint_line = f" [ Номера клеток: {i*3} {i*3+1} {i*3+2} ]"
print(board_line + hint_line)
if i < 2:
print("---+---+---")
print("\n")
# =====================================================================
# 2. УЗЕЛ ДЕРЕВА MCTS
# =====================================================================
class MCTSNode:
def __init__(self, state, parent=None, move=None):
self.state = state
self.parent = parent
self.move = move
self.children = []
self.wins = 0
self.visits = 0
self.untried_moves = state.get_legal_moves()
def uct_select_child(self):
return max(
self.children,
key=lambda c: (c.wins / c.visits) + math.sqrt(2 * math.log(self.visits) / c.visits)
)
def update(self, winner):
self.visits += 1
who_moved = 'O' if self.state.current_player == 'X' else 'X'
if winner == who_moved:
self.wins += 1
elif winner == 'Tie':
self.wins += 0.5
# =====================================================================
# 3. АЛГОРИТМ ПОИСКА
# =====================================================================
def mcts_find_best_move(root_state, itermax=3000):
root_node = MCTSNode(state=root_state)
for _ in range(itermax):
node = root_node
state = root_state.clone()
# 1. Выбор
while not node.untried_moves and node.children:
node = node.uct_select_child()
state.make_move(node.move)
# 2. Расширение
if node.untried_moves:
move = random.choice(node.untried_moves)
node.untried_moves.remove(move)
state.make_move(move)
child_node = MCTSNode(state=state, parent=node, move=move)
node.children.append(child_node)
node = child_node
# 3. Симуляция
game_over, winner = state.check_winner()
while not game_over:
possible_moves = state.get_legal_moves()
state.make_move(random.choice(possible_moves))
game_over, winner = state.check_winner()
# 4. Обратное распространение
while node is not None:
node.update(winner)
node = node.parent
best_child = max(root_node.children, key=lambda c: c.visits)
return best_child.move
# =====================================================================
# 4. ИГРОВОЙ ЦИКЛ
# =====================================================================
def play_game():
print("Добро пожаловать в игру против MCTS ИИ!")
print("Вы играете за 'O' (Нолики). Компьютер играет за 'X' (Крестики) и ходит первым.")
game = TicTacToe()
while True:
game.print_board()
game_over, winner = game.check_winner()
if game_over:
if winner == 'Tie':
print("Ничья! Хорошая игра.")
else:
print(f"Игра окончена! Победитель: {winner}")
break
if game.current_player == 'X':
print("ИИ думает (симулирует 3000 партий в уме)...")
# Настройки itermax=3000 хватает, чтобы ИИ вообще не ошибался в крестиках-ноликах
move = mcts_find_best_move(game, itermax=3000)
game.make_move(move)
print(f"ИИ сделал ход в клетку {move}")
else:
# Ход человека
legal_moves = game.get_legal_moves()
while True:
try:
move = int(input(f"Ваш ход (выберите свободный номер {legal_moves}): "))
if move in legal_moves:
break
else:
print("Эта клетка уже занята или её не существует!")
except ValueError:
print("Пожалуйста, введите число от 0 до 8.")
game.make_move(move)
if __name__ == "__main__":
play_game()
Как проверить силу алгоритма?
Особенность MCTS в том, что при 3000 симуляций на каждый ход в такой простой игре как крестики-нолики, алгоритм за пару секунд просчитает абсолютно все цепочки событий до конца. Выиграть у него станет физически невозможно. Максимум, чего получится добиться идеальной игрой — это свести партию к ничьей.
Если вы хотите сделать ИИ «глупее» и дать себе шанс на победу, измените параметр количества симуляций в строке:
move = mcts_find_best_move(game, itermax=20) # Сделайте 15-20 вместо 3000
Тогда алгоритм начнет совершать человеческие ошибки, так как его «интуиция» на основе случайных симуляций не успеет полностью собраться.
Если вам будет интересно, мы можем обсудить, как именно изменить этот код, чтобы превратить его в другую текстовую игру (например, Ним или Камень-Ножницы-Бумага), или разобрать какую-то конкретную строчку в логике дерева поиска. Что скажете?
Вот готовый скрипт, который объединяет весь предыдущий код и добавляет текстовый интерфейс. Вы можете скопировать его целиком, запустить в любом Python-файле и сыграть против искусственного интеллекта.
Вы будете играть за Ноликов (O), а алгоритм MCTS — за Крестиков (X). Он будет делать первый ход.
import math
import random
# =====================================================================
# 1. ИГРОВОЙ ДВИЖОК
# =====================================================================
class TicTacToe:
def __init__(self):
self.board = [' '] * 9 # Доска из 9 клеток
self.current_player = 'X' # X ходит первым
def get_legal_moves(self):
return [i for i, spot in enumerate(self.board) if spot == ' ']
def make_move(self, move):
self.board[move] = self.current_player
self.current_player = 'O' if self.current_player == 'X' else 'X'
def check_winner(self):
lines = [, [3, 4, 5], [6, 7, 8], # Горизонтали, [1, 4, 7], [2, 5, 8], # Вертикали, [2, 4, 6] # Диагонали
]
for line in lines:
if self.board[line[0]] == self.board[line[1]] == self.board[line[2]] != ' ':
return True, self.board[line[0]]
if ' ' not in self.board:
return True, 'Tie'
return False, None
def clone(self):
new_state = TicTacToe()
new_state.board = list(self.board)
new_state.current_player = self.current_player
return new_state
def print_board(self):
"""Красивый вывод доски в консоль с номерами подсказок."""
print("\n")
for i in range(3):
# Выводим игровое поле
board_line = f" {self.board[i*3]} | {self.board[i*3+1]} | {self.board[i*3+2]} "
# Выводим подсказку с номерами кнопок для игрока
hint_line = f" [ Номера клеток: {i*3} {i*3+1} {i*3+2} ]"
print(board_line + hint_line)
if i < 2:
print("---+---+---")
print("\n")
# =====================================================================
# 2. УЗЕЛ ДЕРЕВА MCTS
# =====================================================================
class MCTSNode:
def __init__(self, state, parent=None, move=None):
self.state = state
self.parent = parent
self.move = move
self.children = []
self.wins = 0
self.visits = 0
self.untried_moves = state.get_legal_moves()
def uct_select_child(self):
return max(
self.children,
key=lambda c: (c.wins / c.visits) + math.sqrt(2 * math.log(self.visits) / c.visits)
)
def update(self, winner):
self.visits += 1
who_moved = 'O' if self.state.current_player == 'X' else 'X'
if winner == who_moved:
self.wins += 1
elif winner == 'Tie':
self.wins += 0.5
# =====================================================================
# 3. АЛГОРИТМ ПОИСКА
# =====================================================================
def mcts_find_best_move(root_state, itermax=3000):
root_node = MCTSNode(state=root_state)
for _ in range(itermax):
node = root_node
state = root_state.clone()
# 1. Выбор
while not node.untried_moves and node.children:
node = node.uct_select_child()
state.make_move(node.move)
# 2. Расширение
if node.untried_moves:
move = random.choice(node.untried_moves)
node.untried_moves.remove(move)
state.make_move(move)
child_node = MCTSNode(state=state, parent=node, move=move)
node.children.append(child_node)
node = child_node
# 3. Симуляция
game_over, winner = state.check_winner()
while not game_over:
possible_moves = state.get_legal_moves()
state.make_move(random.choice(possible_moves))
game_over, winner = state.check_winner()
# 4. Обратное распространение
while node is not None:
node.update(winner)
node = node.parent
best_child = max(root_node.children, key=lambda c: c.visits)
return best_child.move
# =====================================================================
# 4. ИГРОВОЙ ЦИКЛ
# =====================================================================
def play_game():
print("Добро пожаловать в игру против MCTS ИИ!")
print("Вы играете за 'O' (Нолики). Компьютер играет за 'X' (Крестики) и ходит первым.")
game = TicTacToe()
while True:
game.print_board()
game_over, winner = game.check_winner()
if game_over:
if winner == 'Tie':
print("Ничья! Хорошая игра.")
else:
print(f"Игра окончена! Победитель: {winner}")
break
if game.current_player == 'X':
print("ИИ думает (симулирует 3000 партий в уме)...")
# Настройки itermax=3000 хватает, чтобы ИИ вообще не ошибался в крестиках-ноликах
move = mcts_find_best_move(game, itermax=3000)
game.make_move(move)
print(f"ИИ сделал ход в клетку {move}")
else:
# Ход человека
legal_moves = game.get_legal_moves()
while True:
try:
move = int(input(f"Ваш ход (выберите свободный номер {legal_moves}): "))
if move in legal_moves:
break
else:
print("Эта клетка уже занята или её не существует!")
except ValueError:
print("Пожалуйста, введите число от 0 до 8.")
game.make_move(move)
if __name__ == "__main__":
play_game()
Как проверить силу алгоритма?
Особенность MCTS в том, что при 3000 симуляций на каждый ход в такой простой игре как крестики-нолики, алгоритм за пару секунд просчитает абсолютно все цепочки событий до конца. Выиграть у него станет физически невозможно. Максимум, чего получится добиться идеальной игрой — это свести партию к ничьей.
Если вы хотите сделать ИИ «глупее» и дать себе шанс на победу, измените параметр количества симуляций в строке:
move = mcts_find_best_move(game, itermax=20) # Сделайте 15-20 вместо 3000
Тогда алгоритм начнет совершать человеческие ошибки, так как его «интуиция» на основе случайных симуляций не успеет полностью собраться.
Если вам будет интересно, мы можем обсудить, как именно изменить этот код, чтобы превратить его в другую текстовую игру (например, Ним или Камень-Ножницы-Бумага), или разобрать какую-то конкретную строчку в логике дерева поиска. Что скажете?
Вот готовый рабочий прототип упрощенного «Дурака» с открытыми картами, подключенный к нашему алгоритму MCTS.
Чтобы код оставался простым и понятным, мы взяли правила «один на один» в эндшпиле (когда колода кончилась):
- Атакующий ходит одной картой.
- Защищающийся должен её побить (картой той же масти выше рангом или козырем).
- Если защищающийся отбился — карты уходят в отбой, и он становится атакующим. Если не отбился — он забирает карту себе, а ход остается у первого игрока.
- Игра идет, пока у кого-то не закончатся карты.
Вы можете скопировать этот код целиком и запустить:
import math
import random
# Определим достоинства карт для простоты сравнения (числа от 6 до 14)
# 11 = Валет, 12 = Дама, 13 = Король, 14 = Туз
# Масти: 'H' (Черви), 'D' (Бубны), 'C' (Крести), 'S' (Пики)
TRUMP = 'H' # Пусть Черви всегда будут козырем в этой партии
# =====================================================================
# 1. ИГРОВОЙ ДВИЖОК (Упрощенный Открытый Дурак)
# =====================================================================
class DurakOpen:
def __init__(self, hand_ai, hand_player):
self.hands = {
'AI': list(hand_ai), # Карты робота
'PLAYER': list(hand_player) # Карты человека
}
self.current_player = 'AI' # Кто сейчас принимает решение
self.phase = 'ATTACK' # Текущая фаза: 'ATTACK' или 'DEFEND'
self.table_card = None # Карта, которую нужно побить (если фаза DEFEND)
def is_stronger(self, card1, card2):
"""Проверяет, бьет ли card1 (справа) карту card2 (слева)."""
r1, m1 = card1
r2, m2 = card2
if m1 == m2:
return r1 > r2
return m1 == TRUMP # Если масти разные, то card1 бьет, только если она козырь
def get_legal_moves(self):
"""Возвращает список доступных ходов для текущего игрока."""
hand = self.hands[self.current_player]
if self.phase == 'ATTACK':
# В фазе атаки можно ходить любой картой из руки
return hand
elif self.phase == 'DEFEND':
# В фазе защиты можно либо побить картой, либо взять (обозначим ход как 'TAKE')
legal = [card for card in hand if self.is_stronger(card, self.table_card)]
legal.append('TAKE')
return legal
def make_move(self, move):
"""Применяет ход и меняет состояние игры."""
opponent = 'PLAYER' if self.current_player == 'AI' else 'AI'
if self.phase == 'ATTACK':
self.hands[self.current_player].remove(move)
self.table_card = move
self.phase = 'DEFEND'
self.current_player = opponent # Защищаться должен соперник
elif self.phase == 'DEFEND':
if move == 'TAKE':
# Игрок забирает карту со стола
self.hands[self.current_player].append(self.table_card)
self.table_card = None
self.phase = 'ATTACK'
self.current_player = opponent # Атакует снова соперник
else:
# Игрок успешно отбился картой `move`
self.hands[self.current_player].remove(move)
self.table_card = None
self.phase = 'ATTACK'
# Отбился -> теперь сам атакует (current_player не меняется, он стал атакующим)
def check_winner(self):
"""Определяет, кончилась ли игра."""
# Тот, у кого первого кончились карты, победил (в Дураке проигрывает тот, кто остался с картами)
if not self.hands['AI'] and self.hands['PLAYER']:
return True, 'AI'
if not self.hands['PLAYER'] and self.hands['AI']:
return True, 'PLAYER'
if not self.hands['AI'] and not self.hands['PLAYER']:
return True, 'Tie' # На случай редкой ничьей
return False, None
def clone(self):
new_game = DurakOpen([], [])
new_game.hands['AI'] = list(self.hands['AI'])
new_game.hands['PLAYER'] = list(self.hands['PLAYER'])
new_game.current_player = self.current_player
new_game.phase = self.phase
new_game.table_card = self.table_card
return new_game
def card_to_str(self, card):
if card == 'TAKE': return 'ВЗЯТЬ'
if card is None: return 'Пусто'
ranks = {11: 'В', 12: 'Д', 13: 'К', 14: 'Т'}
suits = {'H': '♥ (К)', 'D': '♦', 'C': '♣', 'S': '♠'}
r, m = card
return f"{ranks.get(r, r)}{suits[m]}"
def print_state(self):
print(f"--- Козырь партии: ♥ ---")
print(f"Карты ИИ: {[self.card_to_str(c) for c in self.hands['AI']]}")
print(f"Ваши карты: {[self.card_to_str(c) for c in self.hands['PLAYER']]}")
if self.table_card:
print(f"На столе лежит: {self.card_to_str(self.table_card)}")
print(f"Сейчас ход игрока: {self.current_player} (Фаза: {self.phase})")
print("-" * 30)
# =====================================================================
# 2. УЗЕЛ ДЕРЕВА MCTS (Абсолютно такой же, как для крестиков-ноликов)
# =====================================================================
class MCTSNode:
def __init__(self, state, parent=None, move=None):
self.state = state
self.parent = parent
self.move = move
self.children = []
self.wins = 0
self.visits = 0
self.untried_moves = state.get_legal_moves()
def uct_select_child(self):
return max(
self.children,
key=lambda c: (c.wins / c.visits) + math.sqrt(2 * math.log(self.visits) / c.visits)
)
def update(self, winner):
self.visits += 1
# Кто сделал ход, приведший сюда?
# Если сейчас принимает решение AI, значит этот узел создал PLAYER своим ходом
who_moved = 'PLAYER' if self.state.current_player == 'AI' else 'AI'
if winner == who_moved:
self.wins += 1
elif winner == 'Tie':
self.wins += 0.5
# =====================================================================
# 3. АЛГОРИТМ ПОИСКА (Тоже без изменений)
# =====================================================================
def mcts_find_best_move(root_state, itermax=2000):
root_node = MCTSNode(state=root_state)
for _ in range(itermax):
node = root_node
state = root_state.clone()
# 1. Выбор
while not node.untried_moves and node.children:
node = node.uct_select_child()
state.make_move(node.move)
# 2. Расширение
if node.untried_moves:
move = random.choice(node.untried_moves)
node.untried_moves.remove(move)
state.make_move(move)
child_node = MCTSNode(state=state, parent=node, move=move)
node.children.append(child_node)
node = child_node
# 3. Симуляция (Случайный быстрый доигрыш)
game_over, winner = state.check_winner()
while not game_over:
possible_moves = state.get_legal_moves()
state.make_move(random.choice(possible_moves))
game_over, winner = state.check_winner()
# 4. Обратное распространение
while node is not None:
node.update(winner)
node = node.parent
best_child = max(root_node.children, key=lambda c: c.visits)
return best_child.move
# =====================================================================
# 4. ЗАПУСК ИГРЫ
# =====================================================================
if __name__ == "__main__":
# Зададим интересную стартовую позицию в эндшпиле
# Формат карт: (ранг, масть)
# Козырь — H (Черви)
ai_cards = [(14, 'D'), (6, 'H'), (10, 'S')] # Туз Бубен, 6 Червей (Козырь), 10 Пик
player_cards = [(13, 'D'), (11, 'H'), (14, 'S')] # Король Бубен, Валет Червей (Козырь), Туз Пик
game = DurakOpen(ai_cards, player_cards)
while True:
game.print_state()
game_over, winner = game.check_winner()
if game_over:
print(f"Игра окончена! Победил: {winner}")
break
if game.current_player == 'AI':
print("ИИ просчитывает комбинации открытых карт...")
move = mcts_find_best_move(game, itermax=2000)
print(f"ИИ делает ход: {game.card_to_str(move)}")
game.make_move(move)
else:
# Ход человека
legal_moves = game.get_legal_moves()
print("Варианты ваших ходов:")
for idx, m in enumerate(legal_moves):
print(f" [{idx}] -> {game.card_to_str(m)}")
while True:
try:
choice = int(input("Введите номер вашего хода: "))
if 0 <= choice < len(legal_moves):
move = legal_moves[choice]
break
print("Неверный номер!")
except ValueError:
print("Введите число.")
game.make_move(move)
Как проверить "ум" ИИ в этом примере?
В коде ИИ разыгрывает сложную ситуацию:
- У него на руках есть Туз Бубен (14D), слабенький козырь 6 Червей (6H) и 10 Пик (10S).
- У вас на руках есть козырь посильнее — Валет Червей (11H), Король Бубен (13D) и Туз Пик (14S).
Если ИИ сглупит и пойдет с Туза Бубен, вы легко заберете инициативу. Но благодаря MCTS алгоритм сделает 2000 быстрых случайных розыгрышей «в уме» и поймет, что единственный путь к победе — пожертвовать маленьким козырем или заставить вас выкинуть Туза Пик. Он найдет лучшую математическую цепочку ходов, даже не зная теории игры в Дурака.
Хотите изменить карты на руках или обсудить, как алгоритм обрабатывает фазу защиты, когда вы пытаетесь его завалить?
Да, конечно! Для этого достаточно немного изменить логику вводы карты игроком в самом конце скрипта. Мы добавим в класс DurakOpen два небольших метода для красивого текстового ввода (например, 10S для 10 пик или TH для козырного туза), чтобы вам не пришлось искать индексы в списках.
Вот обновленный и полностью готовый код, где вы вводите карту прямо текстом с консоли (например: 6H, 10S, TD или TAKE):
import math
import random
# Козырь партии — Черви (H)
TRUMP = 'H'
# Словари для удобного текстового ввода и вывода
RANK_MAP = {'6': 6, '7': 7, '8': 8, '9': 9, '10': 10, 'J': 11, 'Q': 12, 'K': 13, 'A': 14, 'V': 11, 'D': 12, 'T': 14}
SUIT_MAP = {'H': 'H', 'D': 'D', 'C': 'C', 'S': 'S', 'Х': 'H', 'Б': 'D', 'К': 'C', 'П': 'S'} # Поддержка рус/англ
# =====================================================================
# 1. ИГРОВОЙ ДВИЖОК
# =====================================================================
class DurakOpen:
def __init__(self, hand_ai, hand_player):
self.hands = {'AI': list(hand_ai), 'PLAYER': list(hand_player)}
self.current_player = 'AI'
self.phase = 'ATTACK'
self.table_card = None
def is_stronger(self, card1, card2):
r1, m1 = card1
r2, m2 = card2
if m1 == m2: return r1 > r2
return m1 == TRUMP
def get_legal_moves(self):
hand = self.hands[self.current_player]
if self.phase == 'ATTACK':
return hand
elif self.phase == 'DEFEND':
legal = [card for card in hand if self.is_stronger(card, self.table_card)]
legal.append('TAKE')
return legal
def make_move(self, move):
opponent = 'PLAYER' if self.current_player == 'AI' else 'AI'
if self.phase == 'ATTACK':
self.hands[self.current_player].remove(move)
self.table_card = move
self.phase = 'DEFEND'
self.current_player = opponent
elif self.phase == 'DEFEND':
if move == 'TAKE':
self.hands[self.current_player].append(self.table_card)
self.table_card = None
self.phase = 'ATTACK'
self.current_player = opponent
else:
self.hands[self.current_player].remove(move)
self.table_card = None
self.phase = 'ATTACK'
def check_winner(self):
if not self.hands['AI'] and self.hands['PLAYER']: return True, 'AI'
if not self.hands['PLAYER'] and self.hands['AI']: return True, 'PLAYER'
if not self.hands['AI'] and not self.hands['PLAYER']: return True, 'Tie'
return False, None
def clone(self):
new_game = DurakOpen([], [])
new_game.hands['AI'] = list(self.hands['AI'])
new_game.hands['PLAYER'] = list(self.hands['PLAYER'])
new_game.current_player = self.current_player
new_game.phase = self.phase
new_game.table_card = self.table_card
return new_game
def card_to_str(self, card):
if card == 'TAKE': return 'ВЗЯТЬ'
if card is None: return 'Пусто'
ranks = {11: 'J', 12: 'Q', 13: 'K', 14: 'A'}
suits = {'H': '♥', 'D': '♦', 'C': '♣', 'S': '♠'}
r, m = card
return f"{ranks.get(r, r)}{suits[m]}"
def print_state(self):
print(f"\n===== КОЗЫРЬ: ЧЕРВИ (♥) =====")
print(f"Карты ИИ: {[self.card_to_str(c) for c in self.hands['AI']]}")
print(f"Ваши карты: {[self.card_to_str(c) for c in self.hands['PLAYER']]}")
if self.table_card:
print(f"На столе: {self.card_to_str(self.table_card)}")
print(f"Чей ход: {self.current_player} ({self.phase})")
print("=============================")
def parse_input_card(self, user_str):
"""Переводит текст игрока вроде '10S' или 'AH' в формат карты (10, 'S')."""
user_str = user_str.strip().upper()
if user_str in ['ВЗЯТЬ', 'TAKE', 'ПАС', 'PAS']:
return 'TAKE'
# Разделяем ранг и масть (например, '10' и 'S' или 'A' и 'H')
if user_str.startswith('10'):
rank_str, suit_str = '10', user_str[2:]
elif len(user_str) >= 2:
rank_str, suit_str = user_str[0], user_str[1:]
else:
return None
rank = RANK_MAP.get(rank_str)
suit = SUIT_MAP.get(suit_str)
if rank and suit:
return (rank, suit)
return None
# =====================================================================
# 2. УЗЕЛ ДЕРЕВА MCTS
# =====================================================================
class MCTSNode:
def __init__(self, state, parent=None, move=None):
self.state = state
self.parent = parent
self.move = move
self.children = []
self.wins = 0
self.visits = 0
self.untried_moves = state.get_legal_moves()
def uct_select_child(self):
return max(self.children, key=lambda c: (c.wins / c.visits) + math.sqrt(2 * math.log(self.visits) / c.visits))
def update(self, winner):
self.visits += 1
who_moved = 'PLAYER' if self.state.current_player == 'AI' else 'AI'
if winner == who_moved:
self.wins += 1
elif winner == 'Tie':
self.wins += 0.5
# =====================================================================
# 3. АЛГОРИТМ ПОИСКА
# =====================================================================
def mcts_find_best_move(root_state, itermax=3000):
root_node = MCTSNode(state=root_state)
for _ in range(itermax):
node = root_node
state = root_state.clone()
while not node.untried_moves and node.children:
node = node.uct_select_child()
state.make_move(node.move)
if node.untried_moves:
move = random.choice(node.untried_moves)
node.untried_moves.remove(move)
state.make_move(move)
child_node = MCTSNode(state=state, parent=node, move=move)
node.children.append(child_node)
node = child_node
game_over, winner = state.check_winner()
while not game_over:
possible_moves = state.get_legal_moves()
state.make_move(random.choice(possible_moves))
game_over, winner = state.check_winner()
while node is not None:
node.update(winner)
node = node.parent
best_child = max(root_node.children, key=lambda c: c.visits)
return best_child.move
# =====================================================================
# 4. ЗАПУСК ИГРЫ С КОНСОЛИ
# =====================================================================
if __name__ == "__main__":
# Стартовые карты (Формат: ранг, масть)
# H=Черви, D=Бубны, C=Крести, S=Пики
ai_cards = [(14, 'D'), (6, 'H'), (10, 'S')] # Туз♦, 6♥ (Козырь), 10♠
player_cards = [(13, 'D'), (11, 'H'), (14, 'S')] # Король♦, Валет♥ (Козырь), Туз♠
game = DurakOpen(ai_cards, player_cards)
print("Шпаргалка по мастям для ввода: H - Черви, D - Бубны, C - Крести, S - Пики")
print("Шпаргалка по рангам: 6, 7, 8, 9, 10, J (Валет), Q (Дама), K (Король), A (Туз)")
print("Примеры ввода: '10S' — это 10 Пик, 'AH' — это Туз Червей, 'TAKE' — забрать карты.")
while True:
game.print_state()
game_over, winner = game.check_winner()
if game_over:
if winner == 'AI':
print("Игра окончена! Робот MCTS выиграл (у него раньше кончились карты).")
elif winner == 'PLAYER':
print("Поздравляем! Вы победили робота!")
else:
print("Ничья!")
break
if game.current_player == 'AI':
print("ИИ думает...")
move = mcts_find_best_move(game, itermax=4000)
print(f"ИИ сделал ход: {game.card_to_str(move)}")
game.make_move(move)
else:
legal_moves = game.get_legal_moves()
print(f"Доступные вам ходы: {[game.card_to_str(m) for m in legal_moves]}")
while True:
user_input = input("Введите вашу карту (например, 10S или TAKE): ")
parsed_card = game.parse_input_card(user_input)
if parsed_card in legal_moves:
game.make_move(parsed_card)
break
else:
print("❌ Ошибка: Такой ход невозможен или вы ввели некорректное имя карты. Попробуйте еще раз.")
Как играть:
Запустите код и вводите комбинации букв и цифр английским текстом (регистр не важен):
- Если вам нужно походить или отбиться Тузом Пик, пишите:
AS (A = Ace/Туз, S = Spades/Пики). - Если нужно скинуть 10 Пик:
10S. - Если карт для защиты нет и нужно взять карту со стола, пишите:
TAKE (или pas).
Если вы хотите изменить стартовый набор карт ИИ или игрока на другие, просто поменяйте кортежи в строках ai_cards = [...] и player_cards = [...] в самом низу файла.
Хотите расширить этот прототип, чтобы в нем была колода, из которой добираются карты, или логика игры вас полностью устраивает?
Да, конечно! Добавить колоду, из которой игроки будут автоматически добирать карты после каждого раунда (как в настоящем «Дураке»), вполне можно.
Для этого в игровой движок нам нужно добавить список deck (колоду) и функцию draw_cards(), которая проверяет, у кого на руках меньше 6 карт, и выдает новые сверху колоды.
Вот обновленная версия кода. Теперь в начале игры создается полная случайная колода, игрокам раздается по 6 карт, одна карта объявляется козырем, а ИИ просчитывает ходы на основе того, что колода лежит «в открытую»:
import math
import random
# Словари для текстового ввода и вывода
RANK_MAP = {'6': 6, '7': 7, '8': 8, '9': 9, '10': 10, 'J': 11, 'Q': 12, 'K': 13, 'A': 14}
SUIT_MAP = {'H': 'H', 'D': 'D', 'C': 'C', 'S': 'S'}
# =====================================================================
# 1. ИГРОВОЙ ДВИЖОК С КОЛОДОЙ
# =====================================================================
class DurakFullOpen:
def __init__(self):
# Создаем колоду из 36 карт (ранги от 6 до 14, 4 масти)
suits = ['H', 'D', 'C', 'S']
self.deck = [(r, s) for r in range(6, 15) for s in suits]
random.shuffle(self.deck)
# Определяем козырь (последняя карта в колоде)
self.trump_card = self.deck[-1]
self.trump_suit = self.trump_card[1]
# Раздаем по 6 карт
self.hands = {
'AI': [self.deck.pop(0) for _ in range(6)],
'PLAYER': [self.deck.pop(0) for _ in range(6)]
}
self.current_player = 'AI' # ИИ начинает для примера
self.phase = 'ATTACK'
self.table_card = None
def is_stronger(self, card1, card2):
"""Бьет ли card1 карту card2."""
r1, m1 = card1
r2, m2 = card2
if m1 == m2: return r1 > r2
return m1 == self.trump_suit
def get_legal_moves(self):
hand = self.hands[self.current_player]
if self.phase == 'ATTACK':
return hand
elif self.phase == 'DEFEND':
legal = [card for card in hand if self.is_stronger(card, self.table_card)]
legal.append('TAKE')
return legal
def draw_cards(self):
"""Игроки добирают карты из колоды до 6 штук после раунда."""
# Первым берет тот, кто атаковал (по правилам Дурака)
attacker = 'AI' if self.phase == 'ATTACK' else 'PLAYER'
defender = 'PLAYER' if attacker == 'AI' else 'AI'
for player in [attacker, defender]:
while len(self.hands[player]) < 6 and self.deck:
self.hands[player].append(self.deck.pop(0))
def make_move(self, move):
opponent = 'PLAYER' if self.current_player == 'AI' else 'AI'
if self.phase == 'ATTACK':
self.hands[self.current_player].remove(move)
self.table_card = move
self.phase = 'DEFEND'
self.current_player = opponent
elif self.phase == 'DEFEND':
if move == 'TAKE':
# Защищающийся забирает карту, добора из колоды нет, ход переходит атакующему
self.hands[self.current_player].append(self.table_card)
self.table_card = None
self.phase = 'ATTACK'
self.current_player = opponent
else:
# Успешно отбился, карты уходят в отбой, добор из колоды
self.hands[self.current_player].remove(move)
self.table_card = None
self.draw_cards() # Добор карт
self.phase = 'ATTACK'
# Отбился — значит теперь сам атакует (current_player остается прежним)
def check_winner(self):
"""Игра завершается, когда колода пуста и у кого-то кончились карты."""
if not self.deck:
if not self.hands['AI'] and self.hands['PLAYER']: return True, 'AI'
if not self.hands['PLAYER'] and self.hands['AI']: return True, 'PLAYER'
if not self.hands['AI'] and not self.hands['PLAYER']: return True, 'Tie'
return False, None
def clone(self):
"""Создает точную копию игры для симуляций в MCTS."""
new_game = DurakFullOpen()
new_game.deck = list(self.deck)
new_game.trump_card = self.trump_card
new_game.trump_suit = self.trump_suit
new_game.hands['AI'] = list(self.hands['AI'])
new_game.hands['PLAYER'] = list(self.hands['PLAYER'])
new_game.current_player = self.current_player
new_game.phase = self.phase
new_game.table_card = self.table_card
return new_game
def card_to_str(self, card):
if card == 'TAKE': return 'ВЗЯТЬ'
if card is None: return 'Пусто'
ranks = {11: 'J', 12: 'Q', 13: 'K', 14: 'A'}
suits = {'H': '♥', 'D': '♦', 'C': '♣', 'S': '♠'}
r, m = card
return f"{ranks.get(r, r)}{suits[m]}"
def print_state(self):
suits_symbols = {'H': '♥', 'D': '♦', 'C': '♣', 'S': '♠'}
print(f"\n======================================")
print(f"КОЗЫРЬ: {suits_symbols[self.trump_suit]} (Карта: {self.card_to_str(self.trump_card)})")
print(f"Осталось карт в колоде: {len(self.deck)}")
print(f"Карты ИИ: {[self.card_to_str(c) for c in self.hands['AI']]}")
print(f"Ваши карты: {[self.card_to_str(c) for c in self.hands['PLAYER']]}")
if self.table_card:
print(f"На столе: {self.card_to_str(self.table_card)}")
print(f"Чей ход: {self.current_player} ({self.phase})")
print(f"======================================")
def parse_input_card(self, user_str):
user_str = user_str.strip().upper()
if user_str in ['ВЗЯТЬ', 'TAKE', 'ПАС', 'PAS']: return 'TAKE'
if user_str.startswith('10'):
rank_str, suit_str = '10', user_str[2:]
elif len(user_str) >= 2:
rank_str, suit_str = user_str, user_str[1:]
else:
return None
rank = RANK_MAP.get(rank_str)
suit = SUIT_MAP.get(suit_str)
if rank and suit: return (rank, suit)
return None
# =====================================================================
# 2. УЗЕЛ ДЕРЕВА MCTS
# =====================================================================
class MCTSNode:
def __init__(self, state, parent=None, move=None):
self.state = state
self.parent = parent
self.move = move
self.children = []
self.wins = 0
self.visits = 0
self.untried_moves = state.get_legal_moves()
def uct_select_child(self):
return max(self.children, key=lambda c: (c.wins / c.visits) + math.sqrt(2 * math.log(self.visits) / c.visits))
def update(self, winner):
self.visits += 1
who_moved = 'PLAYER' if self.state.current_player == 'AI' else 'AI'
if winner == who_moved:
self.wins += 1
elif winner == 'Tie':
self.wins += 0.5
# =====================================================================
# 3. АЛГОРИТМ ПОИСКА
# =====================================================================
def mcts_find_best_move(root_state, itermax=1500):
root_node = MCTSNode(state=root_state)
for _ in range(itermax):
node = root_node
state = root_state.clone()
while not node.untried_moves and node.children:
node = node.uct_select_child()
state.make_move(node.move)
if node.untried_moves:
move = random.choice(node.untried_moves)
node.untried_moves.remove(move)
state.make_move(move)
child_node = MCTSNode(state=state, parent=node, move=move)
node.children.append(child_node)
node = child_node
game_over, winner = state.check_winner()
while not game_over:
possible_moves = state.get_legal_moves()
state.make_move(random.choice(possible_moves))
game_over, winner = state.check_winner()
while node is not None:
node.update(winner)
node = node.parent
best_child = max(root_node.children, key=lambda c: c.visits)
return best_child.move
# =====================================================================
# 4. ГЛАВНЫЙ ИГРОВОЙ ЦИКЛ
# =====================================================================
if __name__ == "__main__":
game = DurakFullOpen()
print("Игра началась! Колода перемешана, карты розданы.")
print("Ввод карт английскими буквами: 6H (6 Черви), JS (Валет Пик), 10C (10 Крести), AD (Туз Бубен).")
print("Команда чтобы забрать карту со стола: TAKE\n")
while True:
game.print_state()
game_over, winner = game.check_winner()
if game_over:
if winner == 'AI':
print("🏆 Робот MCTS победил!")
elif winner == 'PLAYER':
print("🎉 Вы победили робота MCTS!")
else:
print("🤝 Ничья!")
break
if game.current_player == 'AI':
# Снизили itermax до 1500, чтобы ИИ думал быстрее, так как дерево ходов стало больше из-за колоды
print("ИИ анализирует открытую колоду и ваши карты...")
move = mcts_find_best_move(game, itermax=1500)
print(f"ИИ делает ход: {game.card_to_str(move)}")
game.make_move(move)
else:
legal_moves = game.get_legal_moves()
print(f"Доступные вам ходы: {[game.card_to_str(m) for m in legal_moves]}")
while True:
user_input = input("Ваш ход: ")
parsed_card = game.parse_input_card(user_input)
if parsed_card in legal_moves:
game.make_move(parsed_card)
break
else:
print("❌ Неверный ход или опечатка. Попробуйте еще раз.")
Что изменилось математически:
Теперь, когда ИИ запускает 1500 симуляций «в уме», он видит не только ваши карты, но и точный порядок карт в колоде. Он может заглянуть вперед на 5-10 ходов и понять: «Если я сейчас подброшу эту даму, человек отобьется королем, и в следующем раунде из колоды мне придет козырной туз. Значит, надо ходить именно так!»
Если вы захотите сделать игру полностью честной (чтобы ИИ не знал порядок карт в колоде и ваши карты до того, как вы их сыграете), то нам как раз понадобится упомянутый метод детерминизации (IS-MCTS).
Хотите, чтобы мы пошли дальше и скрыли колоду от ИИ, или пока хотите просто протестировать и сыграть в эту версию?
Чтобы ограничить симуляцию по глубине и не давать алгоритму доигрывать партию до самого конца, нам нужно изменить только один блок — Шаг №3 (Симуляция) в функции поиска mcts_find_best_move.
Мы введем два изменения:
- Максимальное число ходов (
max_depth) — симуляция остановится, например, через 6 ходов, даже если игра не завершена. - Функция оценки позиции (
evaluate_state) — если лимит ходов исчерпан, ИИ просто посчитает, у кого на руках ситуация лучше. Тот, у кого карт меньше (и они ценнее), получит виртуальную «победу».
Вот как теперь будет выглядеть обновленная функция поиска MCTS. Вы можете просто заменить этот блок в своем коде:
def evaluate_state(state):
"""
Эвристическая оценка: считает, кто ближе к победе, если игра прервана.
Возвращает 1.0 (победа ИИ), 0.0 (победа Человека) или 0.5 (ничья).
"""
ai_cards_count = len(state.hands['AI'])
player_cards_count = len(state.hands['PLAYER'])
# В Дураке цель — избавиться от карт. У кого карт меньше, тот и ведет.
if ai_cards_count < player_cards_count:
return 1.0 # Считаем, что ИИ побеждает
elif player_cards_count < ai_cards_count:
return 0.0 # Считаем, что Человек побеждает
else:
# Если карт поровну, можно оценить их силу (например, посчитать козыри)
ai_trumps = sum(1 for r, m in state.hands['AI'] if m == state.trump_suit)
player_trumps = sum(1 for r, m in state.hands['PLAYER'] if m == state.trump_suit)
if ai_trumps > player_trumps: return 1.0
if player_trumps > ai_trumps: return 0.0
return 0.5 # Абсолютно равная позиция
def mcts_find_best_move(root_state, itermax=1500, max_depth=8):
root_node = MCTSNode(state=root_state)
for _ in range(itermax):
node = root_node
state = root_state.clone()
# 1. Выбор
while not node.untried_moves and node.children:
node = node.uct_select_child()
state.make_move(node.move)
# 2. Расширение
if node.untried_moves:
move = random.choice(node.untried_moves)
node.untried_moves.remove(move)
state.make_move(move)
child_node = MCTSNode(state=state, parent=node, move=move)
node.children.append(child_node)
node = child_node
# 3. МОДИФИЦИРОВАННАЯ СИМУЛЯЦИЯ (С ограничением глубины)
game_over, winner = state.check_winner()
depth = 0
# Симулируем, пока игра не кончится ИЛИ пока не упремся в лимит ходов (max_depth)
while not game_over and depth < max_depth:
possible_moves = state.get_legal_moves()
state.make_move(random.choice(possible_moves))
game_over, winner = state.check_winner()
depth += 1
# Если игра была прервана лимитом ходов, оцениваем "на глаз"
if not game_over:
score = evaluate_state(state)
# Переводим числовую оценку в текстовое имя победителя для совместимости с node.update
if score == 1.0: winner = 'AI'
elif score == 0.0: winner = 'PLAYER'
else: winner = 'Tie'
# 4. Обратное распространение
while node is not None:
node.update(winner)
node = node.parent
best_child = max(root_node.children, key=lambda c: c.visits)
return best_child.move
Что это дало алгоритму?
- Скорость работы выросла в разы: Ему больше не нужно делать по 20–30 случайных ходов, чтобы дойти до конца колоды. Он делает строго 8 ходов вперед и мгновенно возвращает результат. Теперь вы можете смело поднимать
itermax до 5000+, и ИИ будет «думать» за доли секунды. - Ходы стали более осмысленными: Случайные игроки в симуляции больше не успевают натворить глупостей в глубоком эндшпиле. Алгоритм оценивает краткосрочную перспективу — выгодно ли сделать конкретно этот размен прямо сейчас.
Если вы захотите перенести этот алгоритм на еще более сложную игру вроде шахмат, вам достаточно будет лишь усложнить функцию evaluate_state (например, оценивать позицию по стандартной стоимости фигур: ферзь — 9 очков, ладья — 5 и т.д.).
Остались ли у вас вопросы по какому-то конкретному шагу алгоритма Монте-Карло, или вы хотите обсудить другие стратегии, которые можно к нему подключить?
Вот полный, собранный воедино скрипт игры «Дурак в открытую с колодой». В эту версию уже встроен измененный шаг симуляции с ограничением по глубине (max_depth=8) и функция «умной» оценки позиции (evaluate_state), которая считает карты и козыри.
Вы можете скопировать этот код целиком, запустить его в одном Python-файле и сразу начать играть.
import math
import random
# Настройки рангов и мастей для ввода/вывода
RANK_MAP = {'6': 6, '7': 7, '8': 8, '9': 9, '10': 10, 'J': 11, 'Q': 12, 'K': 13, 'A': 14}
SUIT_MAP = {'H': 'H', 'D': 'D', 'C': 'C', 'S': 'S'}
# =====================================================================
# 1. ИГРОВОЙ ДВИЖОК С КОЛОДОЙ
# =====================================================================
class DurakFullOpen:
def __init__(self):
# Создаем колоду из 36 карт (ранги от 6 до 14, 4 масти)
suits = ['H', 'D', 'C', 'S']
self.deck = [(r, s) for r in range(6, 15) for s in suits]
random.shuffle(self.deck)
# Определяем козырь (последняя карта в колоде)
self.trump_card = self.deck[-1]
self.trump_suit = self.trump_card[1]
# Раздаем по 6 карт
self.hands = {
'AI': [self.deck.pop(0) for _ in range(6)],
'PLAYER': [self.deck.pop(0) for _ in range(6)]
}
self.current_player = 'AI' # ИИ начинает первым для примера
self.phase = 'ATTACK'
self.table_card = None
def is_stronger(self, card1, card2):
"""Бьет ли card1 карту card2."""
r1, m1 = card1
r2, m2 = card2
if m1 == m2: return r1 > r2
return m1 == self.trump_suit
def get_legal_moves(self):
hand = self.hands[self.current_player]
if self.phase == 'ATTACK':
return hand
elif self.phase == 'DEFEND':
legal = [card for card in hand if self.is_stronger(card, self.table_card)]
legal.append('TAKE')
return legal
def draw_cards(self):
"""Игроки добирают карты из колоды до 6 штук после раунда."""
attacker = 'AI' if self.phase == 'ATTACK' else 'PLAYER'
defender = 'PLAYER' if attacker == 'AI' else 'AI'
for player in [attacker, defender]:
while len(self.hands[player]) < 6 and self.deck:
self.hands[player].append(self.deck.pop(0))
def make_move(self, move):
opponent = 'PLAYER' if self.current_player == 'AI' else 'AI'
if self.phase == 'ATTACK':
self.hands[self.current_player].remove(move)
self.table_card = move
self.phase = 'DEFEND'
self.current_player = opponent
elif self.phase == 'DEFEND':
if move == 'TAKE':
# Защищающийся забирает карту, добора из колоды нет, ход переходит атакующему
self.hands[self.current_player].append(self.table_card)
self.table_card = None
self.phase = 'ATTACK'
self.current_player = opponent
else:
# Успешно отбился, карты уходят в отбой, добор из колоды
self.hands[self.current_player].remove(move)
self.table_card = None
self.draw_cards()
self.phase = 'ATTACK'
def check_winner(self):
"""Игра завершается, когда колода пуста и у кого-то кончились карты."""
if not self.deck:
if not self.hands['AI'] and self.hands['PLAYER']: return True, 'AI'
if not self.hands['PLAYER'] and self.hands['AI']: return True, 'PLAYER'
if not self.hands['AI'] and not self.hands['PLAYER']: return True, 'Tie'
return False, None
def clone(self):
"""Создает точную копию игры для симуляций в MCTS."""
new_game = DurakFullOpen()
new_game.deck = list(self.deck)
new_game.trump_card = self.trump_card
new_game.trump_suit = self.trump_suit
new_game.hands['AI'] = list(self.hands['AI'])
new_game.hands['PLAYER'] = list(self.hands['PLAYER'])
new_game.current_player = self.current_player
new_game.phase = self.phase
new_game.table_card = self.table_card
return new_game
def card_to_str(self, card):
if card == 'TAKE': return 'ВЗЯТЬ'
if card is None: return 'Пусто'
ranks = {11: 'J', 12: 'Q', 13: 'K', 14: 'A'}
suits = {'H': '♥', 'D': '♦', 'C': '♣', 'S': '♠'}
r, m = card
return f"{ranks.get(r, r)}{suits[m]}"
def print_state(self):
suits_symbols = {'H': '♥', 'D': '♦', 'C': '♣', 'S': '♠'}
print(f"\n======================================")
print(f"КОЗЫРЬ: {suits_symbols[self.trump_suit]} (Карта: {self.card_to_str(self.trump_card)})")
print(f"Осталось карт в колоде: {len(self.deck)}")
print(f"Карты ИИ: {[self.card_to_str(c) for c in self.hands['AI']]}")
print(f"Ваши карты: {[self.card_to_str(c) for c in self.hands['PLAYER']]}")
if self.table_card:
print(f"На столе: {self.card_to_str(self.table_card)}")
print(f"Чей ход: {self.current_player} ({self.phase})")
print(f"======================================")
def parse_input_card(self, user_str):
user_str = user_str.strip().upper()
if user_str in ['ВЗЯТЬ', 'TAKE', 'ПАС', 'PAS']: return 'TAKE'
if user_str.startswith('10'):
rank_str, suit_str = '10', user_str[2:]
elif len(user_str) >= 2:
rank_str, suit_str = user_str[0], user_str[1:]
else:
return None
rank = RANK_MAP.get(rank_str)
suit = SUIT_MAP.get(suit_str)
if rank and suit: return (rank, suit)
return None
# =====================================================================
# 2. УЗЕЛ ДЕРЕВА MCTS
# =====================================================================
class MCTSNode:
def __init__(self, state, parent=None, move=None):
self.state = state
self.parent = parent
self.move = move
self.children = []
self.wins = 0
self.visits = 0
self.untried_moves = state.get_legal_moves()
def uct_select_child(self):
return max(self.children, key=lambda c: (c.wins / c.visits) + math.sqrt(2 * math.log(self.visits) / c.visits))
def update(self, winner):
self.visits += 1
who_moved = 'PLAYER' if self.state.current_player == 'AI' else 'AI'
if winner == who_moved:
self.wins += 1
elif winner == 'Tie':
self.wins += 0.5
# =====================================================================
# 3. АЛГОРИТМ ПОИСКА С ОГРАНИЧЕНИЕМ ГЛУБИНЫ И ОЦЕНКОЙ ПОЗИЦИИ
# =====================================================================
def evaluate_state(state):
"""Эвристическая оценка: считает, кто ближе к победе при прерывании симуляции."""
ai_cards_count = len(state.hands['AI'])
player_cards_count = len(state.hands['PLAYER'])
# Чем меньше карт на руках — тем лучше позиция
if ai_cards_count < player_cards_count:
return 1.0 # Победа ИИ
elif player_cards_count < ai_cards_count:
return 0.0 # Победа Человека
else:
# Если карт поровну, оцениваем по количеству козырей
ai_trumps = sum(1 for r, m in state.hands['AI'] if m == state.trump_suit)
player_trumps = sum(1 for r, m in state.hands['PLAYER'] if m == state.trump_suit)
if ai_trumps > player_trumps: return 1.0
if player_trumps > ai_trumps: return 0.0
return 0.5 # Равная ситуация
def mcts_find_best_move(root_state, itermax=2000, max_depth=8):
root_node = MCTSNode(state=root_state)
for _ in range(itermax):
node = root_node
state = root_state.clone()
# 1. Выбор
while not node.untried_moves and node.children:
node = node.uct_select_child()
state.make_move(node.move)
# 2. Расширение
if node.untried_moves:
move = random.choice(node.untried_moves)
node.untried_moves.remove(move)
state.make_move(move)
child_node = MCTSNode(state=state, parent=node, move=move)
node.children.append(child_node)
node = child_node
# 3. Симуляция с лимитом шагов (Глубиной)
game_over, winner = state.check_winner()
depth = 0
while not game_over and depth < max_depth:
possible_moves = state.get_legal_moves()
state.make_move(random.choice(possible_moves))
game_over, winner = state.check_winner()
depth += 1
# Если прервали симуляцию по глубине — оцениваем позицию эвристически
if not game_over:
score = evaluate_state(state)
if score == 1.0: winner = 'AI'
elif score == 0.0: winner = 'PLAYER'
else: winner = 'Tie'
# 4. Обратное распространение
while node is not None:
node.update(winner)
node = node.parent
best_child = max(root_node.children, key=lambda c: c.visits)
return best_child.move
# =====================================================================
# 4. ГЛАВНЫЙ ИГРОВОЙ ЦИКЛ
# =====================================================================
if __name__ == "__main__":
game = DurakFullOpen()
print("Игра началась! Колода перемешана, карты розданы.")
print("Ввод карт английскими буквами: 6H (6 Черви), JS (Валет Пик), 10C (10 Крести), AD (Туз Бубен).")
print("Команда чтобы забрать карту со стола: TAKE\n")
while True:
game.print_state()
game_over, winner = game.check_winner()
if game_over:
if winner == 'AI': print("🏆 Робот MCTS победил!")
elif winner == 'PLAYER': print("🎉 Вы победили робота MCTS!")
else: print("🤝 Ничья!")
break
if game.current_player == 'AI':
# Благодаря ограничению max_depth мы можем спокойно поднять itermax до 3000-4000
print("ИИ анализирует ситуацию на 8 ходов вперед...")
move = mcts_find_best_move(game, itermax=3000, max_depth=8)
print(f"ИИ делает ход: {game.card_to_str(move)}")
game.make_move(move)
else:
legal_moves = game.get_legal_moves()
print(f"Доступные вам ходы: {[game.card_to_str(m) for m in legal_moves]}")
while True:
user_input = input("Ваш ход: ")
parsed_card = game.parse_input_card(user_input)
if parsed_card in legal_moves:
game.make_move(parsed_card)
break
else:
print("❌ Неверный ход или опечатка. Попробуйте еще раз.")
Если вы хотите провести эксперимент, попробуйте изменить параметр глубины в строке поиска:
* Поставьте `max_depth=2` — ИИ станет играть очень близоруко и прямолинейно (будет видеть только следующий размен).
* Поставьте `max_depth=15` — ИИ начнет заглядывать далеко вперед, но время его размышлений немного увеличится.
Насколько сильно, по вашему мнению, **ограничение по глубине** изменило сложность игры против ИИ? Будет интересно узнать ваши впечатления после теста!
Комментариев нет:
Отправить комментарий