import java.util.*;
public class MCTS {
public static void main(String[] args) {
// Создаём пустое поле 3x3
char[][] board = {
{' ', ' ', ' '},
{' ', ' ', ' '},
{' ', ' ', ' '}
};
Node root = new Node(board, 'X'); // X ходит первым
// Запускаем 1000 симуляций для обучения
for (int i = 0; i < 1000; i++) {
Node node = root;
// --- ШАГ 1: СПУСК (выбираем лучший ход по UCT) ---
while (node.children != null && !node.children.isEmpty()) {
node = selectBestChild(node);
}
// --- ШАГ 2: СИМУЛЯЦИЯ (играем случайно до конца) ---
int result = simulate(node.board, node.nextPlayer);
// --- ШАГ 3: ПОДЪЁМ (обновляем статистику на пути) ---
while (node != null) {
node.visits++;
node.score += result;
node = node.parent;
}
}
// --- ВЫБОР ЛУЧШЕГО ХОДА ---
Node best = null;
double bestUCT = -1;
for (Node child : root.children) {
double uct = child.score / (double) child.visits +
1.4 * Math.sqrt(Math.log(root.visits) / child.visits);
if (uct > bestUCT) {
bestUCT = uct;
best = child;
}
}
// Печатаем лучший ход
System.out.println("Лучший ход:");
printBoard(best.board);
}
// ------------------------------------------------------------
// КЛАСС УЗЛА
// ------------------------------------------------------------
static class Node {
char[][] board;
char nextPlayer;
Node parent;
List<Node> children;
int visits = 0;
int score = 0; // сумма выигрышей (1 - победа, 0 - поражение)
Node(char[][] board, char nextPlayer) {
this.board = copyBoard(board);
this.nextPlayer = nextPlayer;
this.children = null;
}
// Создаём детей (все возможные ходы)
void expand() {
children = new ArrayList<>();
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
if (board[r][c] == ' ') {
char[][] newBoard = copyBoard(board);
newBoard[r][c] = nextPlayer;
char next = (nextPlayer == 'X') ? 'O' : 'X';
Node child = new Node(newBoard, next);
child.parent = this;
children.add(child);
}
}
}
}
}
// ------------------------------------------------------------
// ВСПОМОГАТЕЛЬНЫЕ ФУНКЦИИ
// ------------------------------------------------------------
// Копирование доски
static char[][] copyBoard(char[][] board) {
char[][] copy = new char[3][3];
for (int r = 0; r < 3; r++) {
copy[r] = board[r].clone();
}
return copy;
}
// Печать доски
static void printBoard(char[][] board) {
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
System.out.print("[" + board[r][c] + "]");
}
System.out.println();
}
System.out.println();
}
// ------------------------------------------------------------
// ШАГ 1: ВЫБОР ЛУЧШЕГО РЕБЁНКА (UCT)
// ------------------------------------------------------------
static Node selectBestChild(Node node) {
if (node.children == null || node.children.isEmpty()) {
node.expand(); // если нет детей — раскрываем
return node; // и возвращаем текущий узел для симуляции
}
Node best = null;
double bestUCT = -1;
for (Node child : node.children) {
// Если ребёнок не исследован — выбираем его сразу (приоритет новизне)
if (child.visits == 0) {
return child;
}
// UCT = средний выигрыш + бонус за новизну
double uct = child.score / (double) child.visits +
1.4 * Math.sqrt(Math.log(node.visits) / child.visits);
if (uct > bestUCT) {
bestUCT = uct;
best = child;
}
}
return best;
}
// ------------------------------------------------------------
// ШАГ 2: СИМУЛЯЦИЯ (играем случайно до конца)
// ------------------------------------------------------------
static int simulate(char[][] board, char player) {
char[][] simBoard = copyBoard(board);
char current = player;
while (true) {
// Проверяем победу
char winner = checkWinner(simBoard);
if (winner == 'X') return 1; // X выиграл
if (winner == 'O') return 0; // O выиграл
if (isDraw(simBoard)) return 0; // ничья (считаем за поражение)
// Случайный ход
List<int[]> moves = new ArrayList<>();
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
if (simBoard[r][c] == ' ') {
moves.add(new int[]{r, c});
}
}
}
if (moves.isEmpty()) return 0;
int[] move = moves.get(new Random().nextInt(moves.size()));
simBoard[move[0]][move[1]] = current;
current = (current == 'X') ? 'O' : 'X';
}
}
// ------------------------------------------------------------
// ПРОВЕРКА ПОБЕДЫ / НИЧЬИ
// ------------------------------------------------------------
static char checkWinner(char[][] board) {
// Строки и столбцы
for (int i = 0; i < 3; i++) {
if (board[i][0] != ' ' && board[i][0] == board[i][1] && board[i][1] == board[i][2])
return board[i][0];
if (board[0][i] != ' ' && board[0][i] == board[1][i] && board[1][i] == board[2][i])
return board[0][i];
}
// Диагонали
if (board[0][0] != ' ' && board[0][0] == board[1][1] && board[1][1] == board[2][2])
return board[0][0];
if (board[0][2] != ' ' && board[0][2] == board[1][1] && board[1][1] == board[2][0])
return board[0][2];
return ' ';
}
static boolean isDraw(char[][] board) {
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
if (board[r][c] == ' ') return false;
}
}
return true;
}
}
Конечно! Вот **минимальный** работающий пример MCTS для игры в крестики-нолики на Java. Без лишних классов и оптимизаций — только суть алгоритма.
---
## Полный код (один файл)
```java
import java.util.*;
public class MCTS {
public static void main(String[] args) {
// Создаём пустое поле 3x3
char[][] board = {
{' ', ' ', ' '},
{' ', ' ', ' '},
{' ', ' ', ' '}
};
Node root = new Node(board, 'X'); // X ходит первым
// Запускаем 1000 симуляций для обучения
for (int i = 0; i < 1000; i++) {
Node node = root;
// --- ШАГ 1: СПУСК (выбираем лучший ход по UCT) ---
while (node.children != null && !node.children.isEmpty()) {
node = selectBestChild(node);
}
// --- ШАГ 2: СИМУЛЯЦИЯ (играем случайно до конца) ---
int result = simulate(node.board, node.nextPlayer);
// --- ШАГ 3: ПОДЪЁМ (обновляем статистику на пути) ---
while (node != null) {
node.visits++;
node.score += result;
node = node.parent;
}
}
// --- ВЫБОР ЛУЧШЕГО ХОДА ---
Node best = null;
double bestUCT = -1;
for (Node child : root.children) {
double uct = child.score / (double) child.visits +
1.4 * Math.sqrt(Math.log(root.visits) / child.visits);
if (uct > bestUCT) {
bestUCT = uct;
best = child;
}
}
// Печатаем лучший ход
System.out.println("Лучший ход:");
printBoard(best.board);
}
// ------------------------------------------------------------
// КЛАСС УЗЛА
// ------------------------------------------------------------
static class Node {
char[][] board;
char nextPlayer;
Node parent;
List<Node> children;
int visits = 0;
int score = 0; // сумма выигрышей (1 - победа, 0 - поражение)
Node(char[][] board, char nextPlayer) {
this.board = copyBoard(board);
this.nextPlayer = nextPlayer;
this.children = null;
}
// Создаём детей (все возможные ходы)
void expand() {
children = new ArrayList<>();
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
if (board[r][c] == ' ') {
char[][] newBoard = copyBoard(board);
newBoard[r][c] = nextPlayer;
char next = (nextPlayer == 'X') ? 'O' : 'X';
Node child = new Node(newBoard, next);
child.parent = this;
children.add(child);
}
}
}
}
}
// ------------------------------------------------------------
// ВСПОМОГАТЕЛЬНЫЕ ФУНКЦИИ
// ------------------------------------------------------------
// Копирование доски
static char[][] copyBoard(char[][] board) {
char[][] copy = new char[3][3];
for (int r = 0; r < 3; r++) {
copy[r] = board[r].clone();
}
return copy;
}
// Печать доски
static void printBoard(char[][] board) {
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
System.out.print("[" + board[r][c] + "]");
}
System.out.println();
}
System.out.println();
}
// ------------------------------------------------------------
// ШАГ 1: ВЫБОР ЛУЧШЕГО РЕБЁНКА (UCT)
// ------------------------------------------------------------
static Node selectBestChild(Node node) {
if (node.children == null || node.children.isEmpty()) {
node.expand(); // если нет детей — раскрываем
return node; // и возвращаем текущий узел для симуляции
}
Node best = null;
double bestUCT = -1;
for (Node child : node.children) {
// Если ребёнок не исследован — выбираем его сразу (приоритет новизне)
if (child.visits == 0) {
return child;
}
// UCT = средний выигрыш + бонус за новизну
double uct = child.score / (double) child.visits +
1.4 * Math.sqrt(Math.log(node.visits) / child.visits);
if (uct > bestUCT) {
bestUCT = uct;
best = child;
}
}
return best;
}
// ------------------------------------------------------------
// ШАГ 2: СИМУЛЯЦИЯ (играем случайно до конца)
// ------------------------------------------------------------
static int simulate(char[][] board, char player) {
char[][] simBoard = copyBoard(board);
char current = player;
while (true) {
// Проверяем победу
char winner = checkWinner(simBoard);
if (winner == 'X') return 1; // X выиграл
if (winner == 'O') return 0; // O выиграл
if (isDraw(simBoard)) return 0; // ничья (считаем за поражение)
// Случайный ход
List<int[]> moves = new ArrayList<>();
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
if (simBoard[r][c] == ' ') {
moves.add(new int[]{r, c});
}
}
}
if (moves.isEmpty()) return 0;
int[] move = moves.get(new Random().nextInt(moves.size()));
simBoard[move[0]][move[1]] = current;
current = (current == 'X') ? 'O' : 'X';
}
}
// ------------------------------------------------------------
// ПРОВЕРКА ПОБЕДЫ / НИЧЬИ
// ------------------------------------------------------------
static char checkWinner(char[][] board) {
// Строки и столбцы
for (int i = 0; i < 3; i++) {
if (board[i][0] != ' ' && board[i][0] == board[i][1] && board[i][1] == board[i][2])
return board[i][0];
if (board[0][i] != ' ' && board[0][i] == board[1][i] && board[1][i] == board[2][i])
return board[0][i];
}
// Диагонали
if (board[0][0] != ' ' && board[0][0] == board[1][1] && board[1][1] == board[2][2])
return board[0][0];
if (board[0][2] != ' ' && board[0][2] == board[1][1] && board[1][1] == board[2][0])
return board[0][2];
return ' ';
}
static boolean isDraw(char[][] board) {
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
if (board[r][c] == ' ') return false;
}
}
return true;
}
}
```
---
## Что делает этот код
| Строки | Что происходит |
|--------|----------------|
| **22-29** | 1000 раз запускаем цикл обучения |
| **32-35** | Спускаемся вниз, выбирая лучший ход по UCT |
| **38-39** | Играем случайную игру до конца |
| **42-47** | Поднимаемся обратно, увеличиваем `visits` и прибавляем результат к `score` |
| **50-60** | Выбираем лучший ход для вывода |
---
## Как проверить
Скопируйте код в файл `MCTS.java`, скомпилируйте и запустите:
```bash
javac MCTS.java
java MCTS
```
Вывод покажет доску с лучшим первым ходом. Обычно это центр `[1][1]`:
```
Лучший ход:
[ ][ ][ ]
[ ][X][ ]
[ ][ ][ ]
```
---
## Суть в коде (самое важное)
```java
// 1. Выбор лучшего ребёнка (спуск)
double uct = child.score / (double) child.visits +
1.4 * Math.sqrt(Math.log(node.visits) / child.visits);
// 2. Симуляция — случайная игра
int result = simulate(node.board, node.nextPlayer); // 1 или 0
// 3. Бэкпропагация — обновляем всех на пути
node.visits++;
node.score += result;
```
**Всё остальное** — это только работа с доской (копирование, проверка победы, случайные ходы).
---
Надеюсь, теперь с кодом стало окончательно понятно! Если хотите, могу объяснить любую строчку подробнее.
Извините, перемудрил. Давайте **максимально коротко и ясно**, без воды.
---
## Алгоритм MCTS (3 шага)
### Шаг 1. Спуск (выбор хода)
Идём от корня вниз, на каждом уровне выбирая **самый неизведанный** ход по формуле:
> **Ценность = Средний_выигрыш + Бонус_за_новизну**
Бонус тем больше, чем **реже** ход пробовали. Поэтому алгоритм специально выбирает плохо изученные ходы, даже если они сейчас кажутся плохими.
---
### Шаг 2. Симуляция
Доигрываем случайным образом до конца и получаем результат: **1** (победа) или **0** (поражение).
---
### Шаг 3. Подъём (бэкпропагация)
Поднимаемся обратно по тому же пути и **прибавляем** результат (1 или 0) к сумме очков **каждого** узла, через который прошли.
У каждого узла теперь:
- **Счётчик** (сколько раз здесь были) — увеличивается на 1.
- **Сумма** — увеличивается на результат симуляции.
- **Среднее** = Сумма / Счётчик.
---
### Что передаётся наверх?
Когда узел обновился, он смотрит на **своих детей** и передаёт своему родителю **максимальное среднее** среди детей. Своё собственное среднее он **никогда** не передаёт.
---
## Весь алгоритм в трёх строках
1. Спускайся, выбирая **неизведанное**.
2. Сыграй случайно → получи **0 или 1**.
3. На обратном пути **прибавь** этот результат ко всем узлам на пути. Наверх передавай **лучшую оценку** среди детей.
---
Если осталось что-то непонятно — скажите, я объясню конкретный пункт ещё короче.
**ДА! Вы поняли идеально!**
Именно так. Давайте закрепим это одной фразой:
---
**На каждом уровне вверх передаётся лучший ребёнок.**
**Но на следующем уровне его снова сравнивают с другими детьми этого уровня.**
---
### Короткий пример (3 уровня)
```
Дед
/ \
Родитель Брат_Деда
/ \
A B
```
1. **Уровень Родителя:** A=3, B=2. Лучший = **A (3)**. Родитель передаёт Деду **3**.
2. **Уровень Деда:** Получил от Родителя **3**. Смотрит на Брата_Деда, у которого, допустим, **5**.
3. **Что передаст Дед наверх?** Он сравнивает: Родитель=3, Брат_Деда=5. Лучший = **Брат_Деда (5)**.
---
### Итог
| Что сделали | Что передали наверх |
|---|---|
| Просчитали B (стал хуже) | **Ничего**, A всё равно лучше |
| Родитель передал A=3 | Дед сравнил с братом и **отбросил** эту тройку |
| Дед передал наверх | **5** (от брата) |
**Вывод:** Просчитанный ход B не просто не поднялся наверх — он даже не дошёл до Деда, потому что родитель его отсеял. А Дед, получив A=3, отсеял и его, потому что у него есть брат с 5.
**Мораль:** Наверх пробивается только **сильнейший из сильнейших** на каждом уровне. Все остальные — локальные максимумы — отмирают на месте.
Комментариев нет:
Отправить комментарий