Реверси

 Да, алгоритм MCTS (Monte Carlo Tree Search / Поиск по дереву Монте-Карло) идеально подходит для Реверси, так как игра обладает огромным числом вариантов ходов. Этот алгоритм не требует сложной математической оценки позиции — он буквально симулирует тысячи случайных партий до конца из текущего положения и выбирает лучший путь.

Ниже представлен полный, рабочий код Реверси с ИИ на базе MCTS, полностью интегрированный в графическое окно tkinter (из прошлого ответа).

ИИ думает прямо во время вашего хода — вы можете настроить количество симуляций (переменная simulations), чтобы сделать его умнее или быстрее.

import tkinter as tk
from tkinter import messagebox
import copy
import random
import math

class ReversiBoard:
    """Класс логики игры, отделенный от интерфейса для нужд MCTS"""
    def __init__(self, size=8):
        self.size = size
        self.board = [[0] * size for _ in range(size)]
        self.board[3][3], self.board[4][4] = 2, 2
        self.board[3][4], self.board[4][3] = 1, 1
        self.current_player = 1

    def get_flipped_disks(self, row, col, player):
        if self.board[row][col] != 0:
            return []
        opponent = 2 if player == 1 else 1
        directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
        flipped = []
        for dr, dc in directions:
            r, c = row + dr, col + dc
            temp = []
            while 0 <= r < self.size and 0 <= c < self.size and self.board[r][c] == opponent:
                temp.append((r, c))
                r += dr
                c += dc
            if 0 <= r < self.size and 0 <= c < self.size and self.board[r][c] == player:
                flipped.extend(temp)
        return flipped

    def get_valid_moves(self, player):
        moves = []
        for r in range(self.size):
            for c in range(self.size):
                if self.get_flipped_disks(r, c, player):
                    moves.append((r, c))
        return moves

    def make_move(self, row, col):
        flipped = self.get_flipped_disks(row, col, self.current_player)
        if not flipped:
            return False
        self.board[row][col] = self.current_player
        for r, c in flipped:
            self.board[r][c] = self.current_player
        
        # Смена игрока с проверкой доступных ходов
        next_player = 2 if self.current_player == 1 else 1
        if self.get_valid_moves(next_player):
            self.current_player = next_player
        elif not self.get_valid_moves(self.current_player):
            self.current_player = 0 # Игра окончена
        return True

    def is_game_over(self):
        return self.current_player == 0

    def get_winner(self):
        b = sum(row.count(1) for row in self.board)
        w = sum(row.count(2) for row in self.board)
        if b > w: return 1
        if w > b: return 2
        return 0 # Ничья

# ==================== РЕАЛИЗАЦИЯ MCTS ====================

class MCTSNode:
    def __init__(self, state: ReversiBoard, parent=None, move=None):
        self.state = state
        self.parent = parent
        self.move = move
        self.children = []
        self.visits = 0
        self.wins = 0
        self.untried_moves = state.get_valid_moves(state.current_player)

    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 select_child(self):
        return max(self.children, key=lambda c: c.ucb1())

    def expand(self):
        move = self.untried_moves.pop()
        next_state = copy.deepcopy(self.state)
        next_state.make_move(*move)
        child_node = MCTSNode(next_state, parent=self, move=move)
        self.children.append(child_node)
        return child_node

    def update(self, result):
        self.visits += 1
        # Результат оценивается относительно игрока, который СДЕЛАЛ ход, приведший в этот узел
        if self.parent:
            player_who_moved = self.parent.state.current_player
            if result == player_who_moved:
                self.wins += 1
            elif result == 0:
                self.wins += 0.5  # Ничья

def mcts_search(root_state, simulations=300):
    """Главный цикл MCTS: Выбор -> Расширение -> Симуляция -> Обратное распространение"""
    root = MCTSNode(copy.deepcopy(root_state))
    
    for _ in range(simulations):
        node = root
        
        # 1. Selection (Выбор)
        while not node.untried_moves and node.children:
            node = node.select_child()
            
        # 2. Expansion (Расширение)
        if node.untried_moves and not node.state.is_game_over():
            node = node.expand()
            
        # 3. Simulation (Симуляция / Rollout)
        sim_state = copy.deepcopy(node.state)
        while not sim_state.is_game_over():
            possible_moves = sim_state.get_valid_moves(sim_state.current_player)
            if possible_moves:
                sim_state.make_move(*random.choice(possible_moves))
            else:
                break
        
        # 4. Backpropagation (Обратное распространение)
        game_result = sim_state.get_winner()
        while node is not None:
            node.update(game_result)
            node = node.parent
            
    # Выбираем ход с наибольшим количеством посещений (самый надежный)
    best_child = max(root.children, key=lambda c: c.visits)
    return best_child.move

# ==================== ГРАФИЧЕСКИЙ ИНТЕРФЕЙС ====================

class ReversiGUI:
    def __init__(self, root):
        self.root = root
        self.root.title("Реверси с ИИ (MCTS)")
        
        self.game = ReversiBoard()
        self.cell_size = 60
        self.ai_player = 2  # 1 - Черные (Игрок), 2 - Белые (MCTS Компьютер)
        
        self.canvas = tk.Canvas(root, width=8*self.cell_size, height=8*self.cell_size, bg="#006633")
        self.canvas.pack()
        self.canvas.bind("<Button-1>", self.handle_click)
        
        self.draw_board()

    def draw_board(self):
        self.canvas.delete("all")
        # Сетка
        for i in range(9):
            coord = i * self.cell_size
            self.canvas.create_line(coord, 0, coord, 8*self.cell_size, fill="#004d26")
            self.canvas.create_line(0, coord, 8*self.cell_size, coord, fill="#004d26")
        
        # Фишки
        for r in range(8):
            for c in range(8):
                val = self.game.board[r][c]
                if val != 0:
                    color = "black" if val == 1 else "white"
                    x0, y0 = c * self.cell_size + 5, r * self.cell_size + 5
                    x1, y1 = (c + 1) * self.cell_size - 5, (r + 1) * self.cell_size - 5
                    self.canvas.create_oval(x0, y0, x1, y1, fill=color, outline="gray")

    def handle_click(self, event):
        if self.game.current_player != 1 or self.game.is_game_over():
            return # Ход компьютера или игра завершена
            
        col = event.x // self.cell_size
        row = event.y // self.cell_size
        
        if self.game.make_move(row, col):
            self.draw_board()
            if self.game.is_game_over():
                self.check_winner()
            elif self.game.current_player == self.ai_player:
                self.root.after(100, self.make_ai_move)

    def make_ai_move(self):
        if self.game.is_game_over():
            return
            
        # Запуск MCTS поиска (300 симуляций для баланса скорости и ума)
        best_move = mcts_search(self.game, simulations=300)
        
        if best_move:
            self.game.make_move(*best_move)
            self.draw_board()
            
        if self.game.is_game_over():
            self.check_winner()
        elif self.game.current_player == 1:
            return # Ход возвращается игроку
        else:
            # Если у игрока нет ходов, ИИ ходит снова
            self.root.after(100, self.make_ai_move)

    def check_winner(self):
        b = sum(row.count(1) for row in self.game.board)
        w = sum(row.count(2) for row in self.game.board)
        if b > w:
            res = f"Вы победили! ({b}:{w})"
        elif w > b:
            res = f"Победил ИИ! ({w}:{b})"
        else:
            res = f"Ничья! ({b}:{w})"
        messagebox.showinfo("Игра окончена", res)

if __name__ == "__main__":
    root = tk.Tk()
    gui = ReversiGUI(root)
    root.mainloop()

Как устроен этот MCTS:

1. Selection (Выбор): Используя формулу UCB1, алгоритм спускается по уже известному дереву ходов, балансируя между исследованием новых путей (Exploration) и выбором заведомо выигрышных (Exploitation). [1]
2. Expansion (Расширение): Дойдя до края изученной зоны, алгоритм создает новый узел для еще не опробованного хода.
3. Simulation (Симуляция): Из нового узла игра "доигрывается" до самого конца случайными ходами за обе стороны.
4. Backpropagation (Обратная связь): Результат этой случайной игры (победа/проигрыш) поднимается вверх по дереву, обновляя статистику каждого узла. [1]

Хотите ли вы увеличить сложность (например, добавить веса для угловых клеток в фазу симуляции) или нужно помочь с оптимизацией скорости кода?

[1] https://github.com