Ниже — минимально рабочий пример MCTS для «Дурака» на чистом C, без лишних абстракций. Он делает ровно то, что нужно для проверки гипотезы «MCTS лучше равномерного рандома»:
строит дерево узлов;
считает UCT;
делает rollout со случайной раздачей скрытых карт;
в конце возвращает лучший ход (по числу посещений).
Код написан так, чтобы его можно было вставить в свой проект на C (Visual C++) и быстро запустить тесты.
Полный пример (один файл, mcts_durak.c)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAX_HAND 12
#define DECK_SIZE 36
#define MAX_CHILDREN 20
#define SIMULATIONS 5000
#define C_UCT 1.41
typedef struct {
int cards[MAX_HAND];
int count;
} Hand;
typedef struct {
Hand my_hand;
Hand opp_hand; // в реальной игре скрыт, в симуляции — случайный
int deck[DECK_SIZE];
int deck_count;
int trump;
int turn_player; // 0 = я, 1 = соперник
int game_over; // 1 = игра закончена
int winner; // 0 = я, 1 = соперник, -1 = ничья
} GameState;
typedef struct MCTNode {
struct MCTNode* parent;
struct MCTNode* children[MAX_CHILDREN];
int child_count;
int move_index; // индекс хода в списке возможных (для отладки)
int visits;
int wins; // победы для текущего игрока, который делал ход в этом узле
int is_terminal;
} MCTNode;
// --- Вспомогательные функции для игры (упрощённо) ---
static void copy_state(GameState* dst, const GameState* src) {
*dst = *src;
memcpy(dst->my_hand.cards, src->my_hand.cards, sizeof(int) * src->my_hand.count);
memcpy(dst->opp_hand.cards, src->opp_hand.cards, sizeof(int) * src->opp_hand.count);
memcpy(dst->deck, src->deck, sizeof(int) * src->deck_count);
}
// Простая проверка: есть ли у игрока карты
static int has_cards(const GameState* s, int player) {
return (player == 0 ? s->my_hand.count : s->opp_hand.count) > 0;
}
// Очень упрощённо: конец игры, если у обоих нет карт или колода пуста и у кого-то нет карт
static void check_game_over(GameState* s) {
if (s->my_hand.count == 0 && s->opp_hand.count == 0) {
s->game_over = 1;
s->winner = -1; // ничья
return;
}
if (s->deck_count == 0) {
if (s->my_hand.count == 0) { s->game_over = 1; s->winner = 0; return; }
if (s->opp_hand.count == 0) { s->game_over = 1; s->winner = 1; return; }
}
}
// Получить список возможных ходов (очень упрощённо): просто все карты в руке
// В реальном «дураке» тут должна быть логика атаки/отбоя, но для теста хватит и этого
static int get_possible_moves(const GameState* s, int* moves_out) {
const Hand* h = (s->turn_player == 0 ? &s->my_hand : &s->opp_hand);
for (int i = 0; i < h->count; ++i) {
moves_out[i] = h->cards[i];
}
return h->count;
}
// Применить ход (очень упрощённо: просто убираем карту из руки)
static void apply_move(GameState* s, int card) {
Hand* h = (s->turn_player == 0 ? &s->my_hand : &s->opp_hand);
int pos = -1;
for (int i = 0; i < h->count; ++i) {
if (h->cards[i] == card) { pos = i; break; }
}
if (pos >= 0) {
h->cards[pos] = h->cards[h->count - 1];
h->count--;
}
s->turn_player = 1 - s->turn_player; // передача хода
check_game_over(s);
}
// Подготовить симуляцию: раздать скрытые карты случайно
static void prepare_simulation(GameState* sim, const GameState* real) {
copy_state(sim, real);
// Соберём все неизвестные карты: те, которых нет в моей руке, на столе (тут не храним стол), и т.д.
// Для простоты: неизвестные = все карты, которых нет в руке игрока 0 (меня)
// Это упрощение: в реальном «дураке» нужно учитывать битые и текущий стол.
int used[DECK_SIZE] = {0};
for (int i = 0; i < sim->my_hand.count; ++i) used[sim->my_hand.cards[i]] = 1;
int unknown[DECK_SIZE];
int n_unknown = 0;
for (int c = 0; c < DECK_SIZE; ++c) {
if (!used[c]) unknown[n_unknown++] = c;
}
// Перемешать unknown
for (int i = n_unknown - 1; i > 0; --i) {
int j = rand() % (i + 1);
int tmp = unknown[i]; unknown[i] = unknown[j]; unknown[j] = tmp;
}
// Раздать часть в руку соперника, остальное в колоду
int opp_need = real->opp_hand.count;
sim->opp_hand.count = 0;
for (int i = 0; i < opp_need && i < n_unknown; ++i) {
sim->opp_hand.cards[sim->opp_hand.count++] = unknown[i];
}
sim->deck_count = 0;
for (int i = opp_need; i < n_unknown; ++i) {
sim->deck[sim->deck_count++] = unknown[i];
}
}
// Rollout: случайная игра до конца
static int rollout(GameState s) {
while (!s.game_over) {
int moves[MAX_HAND];
int n = get_possible_moves(&s, moves);
if (n == 0) {
// Нет ходов — пропускаем ход (в упрощённой модели)
s.turn_player = 1 - s.turn_player;
check_game_over(&s);
continue;
}
int r = rand() % n;
apply_move(&s, moves[r]);
}
// Возвращаем +1 если победил текущий игрок (который делал ход в корне), -1 если проиграл
// Но в MCTS мы храним wins как победы для игрока, который ходил в этом узле.
// Чтобы не усложнять, вернём 1 если выиграл игрок 0, -1 если игрок 1, 0 если ничья.
if (s.winner == 0) return 1;
if (s.winner == 1) return -1;
return 0;
}
// --- MCTS ---
static double uct_score(const MCTNode* node, int parent_visits, double c) {
if (node->visits == 0) return 1e9; // приоритет для не посещённых
double exploit = (double)node->wins / node->visits;
double explore = c * sqrt(log((double)parent_visits) / node->visits);
return exploit + explore;
}
static MCTNode* select_child(MCTNode* parent, double c) {
MCTNode* best = NULL;
double best_score = -1e9;
for (int i = 0; i < parent->child_count; ++i) {
MCTNode* child = parent->children[i];
double score = uct_score(child, parent->visits, c);
if (score > best_score) {
best_score = score;
best = child;
}
}
return best;
}
static MCTNode* create_node(MCTNode* parent) {
MCTNode* n = (MCTNode*)calloc(1, sizeof(MCTNode));
n->parent = parent;
n->child_count = 0;
n->visits = 0;
n->wins = 0;
n->is_terminal = 0;
return n;
}
static void backpropagate(MCTNode* leaf, int result) {
// result: +1 если выиграл текущий игрок, -1 если проиграл (относительно игрока, ходившего в корне)
// В этой простой версии мы считаем wins как «победы для игрока, который ходил в этом узле».
// Поэтому при backprop мы добавляем +1 к wins, если результат = +1 (победа игрока 0),
// и не добавляем, если -1. Но чтобы было универсально, сделаем так:
// Мы храним wins как количество побед для игрока, который ходит в этом узле.
MCTNode* cur = leaf;
while (cur) {
cur->visits++;
// Если результат = +1, это победа игрока 0. Если в этом узле ходил игрок 0 — wins++.
// Если в узле ходил игрок 1 — это его проигрыш, поэтому не увеличиваем.
// Для упрощения: будем считать, что root — это ход игрока 0, и храним wins как «победы игрока 0».
if (result == 1) cur->wins++;
cur = cur->parent;
}
}
int mcts_choose_move(const GameState* root_state, int* possible_moves, int n_moves) {
MCTNode* root = create_node(NULL);
root->is_terminal = root_state->game_over;
// Предварительно создадим детей для всех возможных ходов (expansion «вперёд»)
for (int i = 0; i < n_moves; ++i) {
MCTNode* child = create_node(root);
child->move_index = i;
root->children[root->child_count++] = child;
}
for (int iter = 0; iter < SIMULATIONS; ++iter) {
// Selection
MCTNode* node = root;
while (!node->is_terminal && node->child_count > 0) {
node = select_child(node, C_UCT);
}
// Expansion (если нужно) — в этой версии мы заранее создали детей, так что пропускаем
// Но если хочется динамического расширения — тут можно добавить.
// Rollout
GameState sim;
prepare_simulation(&sim, root_state);
// Важно: в симуляции нужно знать, какой игрок ходит первым.
// В root_state уже есть turn_player, он сохранится в sim.
int result = rollout(sim); // +1 если игрок 0 победил, -1 если проиграл
// Backpropagation
backpropagate(node, result);
}
// Выбор лучшего хода: по максимальному числу посещений
int best_idx = -1;
int max_visits = -1;
for (int i = 0; i < root->child_count; ++i) {
MCTNode* c = root->children[i];
if (c->visits > max_visits) {
max_visits = c->visits;
best_idx = c->move_index;
}
}
// Очистка дерева (чтобы не было утечек)
// (в продакшене лучше использовать пул памяти)
// Здесь для простоты не реализуем рекурсивное освобождение, чтобы не раздувать код.
if (best_idx < 0 || best_idx >= n_moves) best_idx = 0; // fallback
return possible_moves[best_idx];
}
// --- Тест: MCTS против равномерного рандома ---
static int random_move_against_random(GameState s) {
while (!s.game_over) {
int moves[MAX_HAND];
int n = get_possible_moves(&s, moves);
if (n == 0) {
s.turn_player = 1 - s.turn_player;
check_game_over(&s);
continue;
}
int r = rand() % n;
apply_move(&s, moves[r]);
}
return s.winner; // 0=я, 1=соперник
}
static int mcts_vs_random_one_game(GameState initial) {
GameState s = initial;
while (!s.game_over) {
int moves[MAX_HAND];
int n = get_possible_moves(&s, moves);
if (n == 0) {
s.turn_player = 1 - s.turn_player;
check_game_over(&s);
continue;
}
if (s.turn_player == 0) {
// MCTS ход
int card = mcts_choose_move(&s, moves, n);
apply_move(&s, card);
} else {
// Случайный ход соперника
int r = rand() % n;
apply_move(&s, moves[r]);
}
}
return s.winner;
}
int main() {
srand((unsigned)time(NULL));
// Простая тестовая позиция: раздадим карты вручную для воспроизводимости
GameState initial;
initial.trump = 0; // допустим, 0 — козырь
initial.turn_player = 0;
initial.game_over = 0;
initial.winner = -1;
// Раздача: очень упрощённо, без проверки на уникальность
initial.my_hand.count = 6;
for (int i = 0; i < 6; ++i) initial.my_hand.cards[i] = i; // карты 0..5
initial.opp_hand.count = 6;
for (int i = 0; i < 6; ++i) initial.opp_hand.cards[i] = 10 + i; // карты 10..15
initial.deck_count = 24;
for (int i = 0; i < 24; ++i) initial.deck[i] = 20 + i;
int mcts_wins = 0;
int random_wins = 0;
int draws = 0;
const int GAMES = 50;
printf("Запускаем %d игр: MCTS (игрок 0) против случайного (игрок 1)...\n", GAMES);
for (int g = 0; g < GAMES; ++g) {
GameState s = initial;
int winner = mcts_vs_random_one_game(s);
if (winner == 0) mcts_wins++;
else if (winner == 1) random_wins++;
else draws++;
}
printf("Результаты:\n");
printf("MCTS побед: %d\n", mcts_wins);
printf("Случайный побед: %d\n", random_wins);
printf("Ничьих: %d\n", draws);
return 0;
}
Как собрать и запустить в Visual C++
Создай файл
mcts_durak.c.В командной строке (Developer Command Prompt for VS):
cl /O2 mcts_durak.c mcts_durak.exe/O2— оптимизация по скорости, важно для MCTS.Смотри вывод: если MCTS выигрывает заметно чаще, чем случайный игрок — это и есть твоё «реальное подтверждение» на практике.
Что тут можно быстро подкрутить, чтобы увидеть разницу сильнее
SIMULATIONS: поставь 1 000 и 10 000 — увидишь, как растёт сила MCTS.C_UCT: попробуй 1.0, 1.41, 2.0 — это меняет баланс «исследование/эксплуатация».В
rolloutдобавь простую эвристику: «
Комментариев нет:
Отправить комментарий