О-хо-хо...я говорил, что это трёхмерные(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. Правильно ли я понял, что ходы с точностью до перестановки в один узел не соединяются? Ну, то есть "крестик в верхний левый угол, нолик в центр, крестик в нижний правый угол" существует отдельно от "крестик в нижний правый угол, нолик в центр, крестик в верхний левый".
Надеюсь, Кулончик пояснит.
Ну скачи