-
-
c00l0ne, ещё хотел уточнить. А выход какой из этого вашегопоискацикла?
Пока что я встретил только по времени. То есть, сколько времени дали, до такой "глубины" поиск и добирается. А если дать бесконечное время? Поиск обойдёт полное дерево и даст абсолютно точный результат? -
БиллиУбили, пиши в телегу , я же не буду тут рецепт счастья для китайских лудоманов выкладывать, обсудим
Telegram:
@coulant
Посл раз отвечу: выход измеряется оценкой погрешности...
Чем дольше тем лучше (с)Цитата (БиллиУбили @ 25.5.2020)
Поиск обойдёт полное дерево и даст абсолютно точный результат?
Это не верно, обойдет да, но основные ресурсы будут потрачены на топовые ветки по ев -
Грамотный человек писалclass Node {
Node *parent;
std::list<Node> childList;
Node getParent() {
return *parent;
};
} ;
class Tree {
Node root;
};
Хотя странно, что компилятор не ругается. Ведь пока класс Node не обьявлен, разве могут быть данные-члены его собственного типа? -
БиллиУбили, это ссылка на родительский обьект
-
редкая рука доберётся до
середины Днепра+бесконечности...double uctValue(int totalVisit, double nodeScore, int nodeVisit) {
if (nodeVisit == 0) {
return 100000; //////////////
}
return (nodeScore / (double) nodeVisit) + 1.41 * sqrt( log(totalVisit) / (double) nodeVisit);
};
ЗЫ Думал спросить, почему UCT, а не UCB. Оказалось, что Upper Confidence bounds applied to Trees -
БиллиУбили, ну ты сделал что нибудь в правильном направлении?
-
c00l0ne, сделал конечно. Нашёл исходник на Java, переписал. Проект скомпилировался, но вылетает с ошибкой. Точнее говоря, там рассматривается игра "крестики-нолики" и уж слишком там запутано: для каждого "хода" хранится доска(поставленные на неё крестики/нолики), на неё (доску) нанизаны состояния(включая текущего игрока), и вот это всё запихнули в узел(туда счётчик посещений и кол-во побед\поражений). В итоге вызывается функция "найти лучший ход".
В результате дерево у меня пока не растёт. Работаем...
ЗЫ Что крайне удивительно, несмотря на то, что количество потомков ограничено(а ведь мы мало куда можем поставить крестик/нолик) везде вставляют счётчик миллисекунд...для каждого уровня обсчёта дерева МК. -
Проблема в том, что код на С++ выполнен в виде консольного приложения
GCC его "скушал"(что удивительно), но найти среду разработки я пока не могу. Если кто подскажет, буду благодарен
ЗЫ Там первая же строчка #include <bits/stdc++.h> уже не всем нравится -
Вроде бы флаг -std=c++11 помог. Отбой по поиску IDE )
-
БиллиУбили, ну и старье, приду покопаюсь
Кинь ссылку откуда качал -
Цитата
https://gist.github.com/ztl8702/4dd133c7d8627ffd2751720c91181449
глянул сорцы
мдя
пустая трата времени
тебе сюда лучше пойти:
https://github.com/rfrerebe/MCTS
или сюда
https://github.com/dmacthedestroyer/mcts
по второй ссылке предпочтительней, стиль программирования и алгоритм - то как оно должно быть, много ООПа )
но по первой ссылке больше интегер и мультипоточный ... производительней
разбирайся давай, да самым интересным пора тебе уже заняться и самым сложным )
описать node structure :D -
О-хо-хо...я говорил, что это трёхмерные(3Х3) крестики-нолики?
Но это даже лучше, т.к. доказывает, игра может быть любой.
Попробуем разобраться в логике программы(на примере ОДНОмерных крестиков-ноликов).
Имеем:
Доска - изначально пустое поле, по ходу игры поочерёдно заполняется крестиками\ноликами
Состояние - доска с уже сделанными ходами + исход игры. Может быть победа крестиков, победа ноликов, ничья и "в процессе"
Узел - Состояние + потомки Состоянияний. Потомки опеределяются, как все ходы, которые может сделать текущий игрок из текущего Состояния. Также включает в себя Счётчик посещений и кол-во набранных очков(скажем, 1 за победу и -1 за поражение)
Собственно говоря, [i]Дерево[/i](состояний?). Строится из начального Состояния(начало) игры на определённое кол-во ходов(полуходов).
Теперь сам метод МонтеКарло. Выполняем следующие шаги:
1. Строим дерево Состояний на 1 ход вперёд и каждому узлу присваиваем Счётчик посещений = 0 и очки +999999
2. В новом Состоянии(после 1 хода), мы по прежнему не знаем исход игры(партии)
3. Выбираем рандомного потомка из корня и продолжаем рандомными(!) ходами до определения исхода партии. Предположим, выиграли Крестики. Тогда записываем в новое состояние +1 очко и +1 счётчик посещений.
4. Повторяем пункт 3 для всех новых состояний на 1 ход(грубо говоря, завершаем обход дерева на 1 уровень). При этом в корне у нас будет сумма очков, которые дали все потомки.
5. Теперь, при полном переборе, мы должны были бы идти из каждого Состояния на 1 ход во все продолжения на 2 хода(путём возможного хода). Однако, мы выбираем узел с максимальным(!) USB и начинаем спускаться по нему. Спускаемся также, как и раньше, переходим на 1 ход вперёд(из этого, выбранного Состояния) и
6. повторяем процедуру. То есть, в Состоянии после 2 ух ходов мы снова проверяем игру на завершение, а если такого нет - рандомными(!) ходами двигаемся до завершения партии. Отличие в том, что счётчик посещения и набранные очки мы обновляем по всем узлам до самого корня(начала партии). Ну и что, спросите вы?
7. А то, что в какой-то момент узел, который раньше был максимальным в п.5, станет вторым. В этот самый момент мы, естественно, должны переключится на узел, ставший максимальным и спускаться вниз уже по его потомкам.
8. Выход из практически бесконечно цикла обхода дерева по истечении времени(например, 1 минута)
Грубо говоря, в начале партии мы имеет 2 продолжения:
_| |_ _| |_
_ | Х|_ _ | |Х_
| | | | и второй вариант волею рандома при первом проходе дерева набрал +1 очко, а первый - 0.5, то мере более тщательного обхода его(второго варианта) продолжений(по прежнему рандомных) его очки будут падать, и в конце-концов станут меньше 0.5, что позволит нам переключится на исследование продолжений первого варианта и там очки уже будут расти(0.5 -> 0.6 и т.д.)
Это вкратце)
Моменты, которые мне не понятны:
1. Если игроки ход за ходом меняются, то почему мы ищем лучший ход только за одного? Как-то ускользает то момент, на основании чего ходы делает оппонент в пределах уровней полного обхода дерева(3 хода, далее рандом)
2. Правильно ли я понял, что ходы с точностью до перестановки в один узел не соединяются? Ну, то есть "крестик в верхний левый угол, нолик в центр, крестик в нижний правый угол" существует отдельно от "крестик в нижний правый угол, нолик в центр, крестик в верхний левый".
Надеюсь, Кулончик пояснит. -
-
Цитата (БиллиУбили @ 30.5.2020)
Моменты, которые мне не понятны:
Вопросы снимается, если вспомнить, что мы находимся в пространстве Состояний(а не ходов). А ведь Состояние включает ситуацию на доске, которая, в ,свою очередь, уже включает сделанные ходы.
Да, неважно, как ты шёл - важно, куда ты пришёл -
Цитата
Чёт ничего не вдохновило, у второго ООП и не пахло...
а ты точно знаешь запах оопа )
лан короче не буду тролить , что не понятно конкретно формулируй вопросы ... там код обширный и тебе нужен MCTS.V1 для того чтобы разобраться как оно работает -
вкратце вот весь код мткс
вот поставил крестик в серединку , оно две ветки отработало:
нолик в левый верхний угол и нолик в правый верхний угол -
а работает как в любой работе написано по MCTS
первое заходим в ноду с макс ев если действия все уже есть в дереве :
если есть действия которые ни разу не проходили то расширяем :
симулируем до конца
и бэкпропогандируем, посещая ноды в обратном порядке
пс вот тебе музыкальная пауза -
1 человек читает эту тему (1 гость):
Зачем регистрироваться на GipsyTeam?
- Вы сможете оставлять комментарии, оценивать посты, участвовать в дискуссиях и повышать свой уровень игры.
- Если вы предпочитаете четырехцветную колоду и хотите отключить анимацию аватаров, эти возможности будут в настройках профиля.
- Вам станут доступны закладки, бекинг и другие удобные инструменты сайта.
- На каждой странице будет видно, где появились новые посты и комментарии.
- Если вы зарегистрированы в покер-румах через GipsyTeam, вы получите статистику рейка, бонусные очки для покупок в магазине, эксклюзивные акции и расширенную поддержку.
Ну скачи