import math
import random
import copy
# Игровое поле 8x8. 0 - пусто, 1 - игрок 1 (белые), 2 - игрок 2 (черные)
# Дома для игроков:
# Дом 1 (цель для 2): левый верхний угол (0,0) - (2,2)
# Дом 2 (цель для 1): правый нижний угол (5,5) - (7,7)
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 = []
def uct_select_child(self, exploration_weight=1.414):
# Формула UCB1
s = sorted(self.children, key=lambda c: c.wins / c.visits + exploration_weight * math.sqrt(2 * math.log(self.visits) / c.visits))
return s[-1]
def add_child(self, m, s):
n = MCTSNode(s, parent=self, move=m)
self.untried_moves.remove(m)
self.children.append(n)
return n
# Базовые функции для логики игры
def is_terminal_state(state):
# Условие победы: игрок занял все 9 клеток противоположного дома
pass
def get_possible_moves(state, player):
# Возвращает список возможных ходов для шашек игрока (простые и через прыжки)
pass
def execute_move(state, move):
# Возвращает новое состояние поля после хода
pass
def rollout(state, current_player):
# Симуляция: случайные ходы до конца игры
while not is_terminal_state(state):
moves = get_possible_moves(state, current_player)
if not moves:
break
move = random.choice(moves)
state = execute_move(state, move)
current_player = 3 - current_player # смена игрока
# Возвращает награду
return 1 if is_terminal_state(state) and current_player != 1 else 0
def mcts(root_state, iterations=1000):
root_node = MCTSNode(root_state)
for _ in range(iterations):
node = root_node
state = copy.deepcopy(root_state)
# 1. Selection
while not node.untried_moves and node.children:
node = node.uct_select_child()
state = execute_move(state, node.move)
# 2. Expansion
if node.untried_moves:
m = random.choice(node.untried_moves)
state = execute_move(state, m)
node = node.add_child(m, state)
# 3. Simulation
reward = rollout(state, 2)
# 4. Backpropagation
while node is not None:
node.visits += 1
node.wins += reward
node = node.parent
# Возвращает лучший ход на основе наибольшего количества визитов
return max(root_node.children, key=lambda c: c.visits).move
/////////
Да, конечно. Ниже представлена рабочая реализация настольной игры «Уголки» (Halma) на уменьшенном поле 4×4 с искусственным интеллектом на базе алгоритма MCTS (Monte Carlo Tree Search) на языке Python.
Для наглядности и высокой скорости работы ИИ в коде используется классическое поле 4×4 и по 3 шашки у каждого игрока (для поля 8×8 структура остается абсолютно той же, но требуется кратно больше итераций MCTS).
Реализация игры «Уголки» с MCTS ИИ
import math
import random
import copy
# Константы игроков
EMPTY = 0
PLAYER_1 = 1 # Стартует в левом верхнем углу (0,0), цель — правый нижний
PLAYER_2 = 2 # Стартует в правом нижнем углу (3,3), цель — левый верхний
BOARD_SIZE = 4
# Начальные дома и целевые позиции (для поля 4x4 по 3 шашки)
P1_HOME = {(0, 0), (0, 1), (1, 0)}
P2_HOME = {(3, 3), (3, 2), (2, 3)}
class HalmaState:
def __init__(self, board=None, turn=PLAYER_1):
self.size = BOARD_SIZE
self.turn = turn
if board is not None:
self.board = board
else:
self.board = [[EMPTY] * self.size for _ in range(self.size)]
# Расстановка стартовых позиций
for r, c in P1_HOME: self.board[r][c] = PLAYER_1
for r, c in P2_HOME: self.board[r][c] = PLAYER_2
def get_current_player(self):
return self.turn
def is_terminal(self):
return self.get_winner() is not None
def get_winner(self):
# Проверяем занял ли Игрок 1 дом Игрока 2
if all(self.board[r][c] == PLAYER_1 for r, c in P2_HOME):
return PLAYER_1
# Проверяем занял ли Игрок 2 дом Игрока 1
if all(self.board[r][c] == PLAYER_2 for r, c in P1_HOME):
return PLAYER_2
return None
def get_legal_moves(self):
moves = []
player = self.turn
for r in range(self.size):
for c in range(self.size):
if self.board[r][c] == player:
# Находим одиночные шаги и прыжки
moves.extend(self._get_piece_moves(r, c))
return moves
def _get_piece_moves(self, r, c):
piece_moves = []
directions = [(-1,0), (1,0), (0,-1), (0,1)] # вверх, вниз, влево, вправо
# 1. Простые шаги в соседние клетки
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < self.size and 0 <= nc < self.size:
if self.board[nr][nc] == EMPTY:
piece_moves.append(((r, c), (nr, nc)))
# 2. Прыжки через фигуры (включая серии прыжков)
visited_jumps = set()
self._get_jumps(r, c, r, c, directions, visited_jumps, piece_moves)
return piece_moves
def _get_jumps(self, start_r, start_c, curr_r, curr_c, directions, visited, moves):
for dr, dc in directions:
mid_r, mid_c = curr_r + dr, curr_c + dc
end_r, end_c = curr_r + 2 * dr, curr_c + 2 * dc
if 0 <= end_r < self.size and 0 <= end_c < self.size:
if self.board[mid_r][mid_c] != EMPTY and self.board[end_r][end_c] == EMPTY:
if (end_r, end_c) not in visited and (end_r, end_c) != (start_r, start_c):
visited.add((end_r, end_c))
moves.append(((start_r, start_c), (end_r, end_c)))
# Рекурсивно ищем продолжение прыжка
self._get_jumps(start_r, start_c, end_r, end_c, directions, visited, moves)
def make_move(self, move):
(from_r, from_c), (to_r, to_c) = move
new_board = copy.deepcopy(self.board)
new_board[to_r][to_c] = new_board[from_r][from_c]
new_board[from_r][from_c] = EMPTY
next_turn = PLAYER_2 if self.turn == PLAYER_1 else PLAYER_1
return HalmaState(new_board, next_turn)
class MCTSNode:
def __init__(self, state, parent=None, move=None):
self.state = state
self.parent = parent
self.move = move
self.children = []
self.visits = 0
self.wins = 0.0
self.untried_moves = state.get_legal_moves()
def ucb1(self, exploration_constant=1.41):
if self.visits == 0:
return float('inf')
return (self.wins / self.visits) + exploration_constant * math.sqrt(math.log(self.parent.visits) / self.visits)
def is_fully_expanded(self):
return len(self.untried_moves) == 0
def best_child(self, exploration_constant=1.41):
return max(self.children, key=lambda node: node.ucb1(exploration_constant))
def mcts_search(root_state, iter_count=500):
root_node = MCTSNode(state=root_state)
for _ in range(iter_count):
node = root_node
state = copy.deepcopy(root_state)
# 1. Selection (Выбор)
while node.is_fully_expanded() and node.children:
node = node.best_child()
state = state.make_move(node.move)
# 2. Expansion (Расширение)
if node.untried_moves:
move = node.untried_moves.pop(random.randint(0, len(node.untried_moves) - 1))
state = state.make_move(move)
child_node = MCTSNode(state=state, parent=node, move=move)
node.children.append(child_node)
node = child_node
# 3. Simulation / Rollout (Симуляция)
# Ограничим глубину симуляции, чтобы избежать бесконечных циклов при случайных ходах
max_simulation_steps = 60
step = 0
while not state.is_terminal() and step < max_simulation_steps:
legal_moves = state.get_legal_moves()
if not legal_moves:
break
# Эвристика для симуляции: отдавать легкое предпочтение ходам, приближающим к цели
state = state.make_move(random.choice(legal_moves))
step += 1
# 4. Backpropagation (Обратное распространение)
winner = state.get_winner()
# Если ничья или лимит ходов, рассчитываем по дистанции до "дома"
while node is not None:
node.visits += 1
if winner is not None:
# Если победитель — игрок, сделавший этот ход
if node.parent and node.parent.state.get_current_player() == winner:
node.wins += 1.0
elif node.parent and node.parent.state.get_current_player() != winner:
node.wins -= 1.0
node = node.parent
# Возвращаем ход, который привел к наиболее посещаемому узлу
best = max(root_node.children, key=lambda node: node.visits)
return best.move
def print_board(state):
symbols = {EMPTY: '.', PLAYER_1: 'X', PLAYER_2: 'O'}
print(" 0 1 2 3")
for r in range(BOARD_SIZE):
row_str = " ".join([symbols[state.board[r][c]] for r in range(BOARD_SIZE) for c in [r]][0]) # dummy
row_str = " ".join([symbols[state.board[r][c]] for c in range(BOARD_SIZE)])
print(f"{r} {row_str}")
print()
# --- ДЕМОНСТРАЦИЯ ИГРЫ ---
if __name__ == "__main__":
game_state = HalmaState()
print("--- СТАРТ ИГРЫ УГОЛКИ ---")
print_board(game_state)
# Симулируем 10 ходов ИИ против самого себя
for turn_num in range(1, 11):
if game_state.is_terminal():
break
current_player = game_state.get_current_player()
print(f"Ход {turn_num}. Очередь Игрока {'1 (X)' if current_player == PLAYER_1 else '2 (O)'}...")
# Запуск MCTS поиска
best_move = mcts_search(game_state, iter_count=400)
print(f"Выбран ход: {best_move[0]} -> {best_move[1]}")
game_state = game_state.make_move(best_move)
print_board(game_state)
winner = game_state.get_winner()
if winner:
print(f"Победил Игрок {winner}!")
else:
print("Игра завершена по лимиту ходов демонстрации.")
Как устроен этот алгоритм:
- HalmaState: Хранит игровое поле, вычисляет доступные ходы. Функция
_get_jumps рекурсивно ищет длинные серии прыжков (через одну фигуру на пустую клетку) — это ключевая тактика «Уголков». [1] - Класс MCTSNode: Представляет собой узел дерева поиска. Содержит статистику побед/посещений и формулу UCB1 для баланса между исследованием редких веток (Exploration) и углублением в лучшие ветки (Exploitation). [2]
- Функция
mcts_search: Главный цикл ИИ. Проводит заданное число случайных партий (iter_count) из текущего состояния до конца игры, а затем выбирает статистически самый надежный первый ход. [2]
Если вы хотите развернуть код на поле 8×8, вам потребуется изменить значение BOARD_SIZE = 8 и заполнить массивы P1_HOME и P2_HOME координатами угловых квадратов 3×3 или 4×3, а также увеличить iter_count до 2000-5000 для более умной игры.
Хотите ли вы добавить в этот код интерфейс ввода для человека, чтобы играть против компьютера, или вам необходимо настроить правила для полноценного поля 8×8?
Комментариев нет:
Отправить комментарий