На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Программирование игрового бота общего назначения
    Буэнос диас, амигос!

    Вопрос просто ради "самообразования". В последнее время время мы видим то тут, то там, что "программа" обыгрывает человека то в шахматы, то в го ... Вот, собственно, это и заинтересовало.

    Простой вариант - тупо полный перебор. Как применение - игра в "крестики-нолики". Вариантов там достаточно ограниченное количество, решение можно свести к полному перебору. Но, когда берем, шахматы, а тем паче, ту же игру го - количество развитий игры стремиться к необозримо большому числу вариантов. Такое количество вариантов современному компьютеру рассчитать в реальном масштабе времени просто не реально.

    Но! ... Программы все-таки выигрывают...

    Собственно вопросы:

    1) Каким образом программируются стратегии выигрыша?
    2) Есть ли какие-то общие методики программирования игровых стратегий, безотносительно игры и правил?
      на шахматном сайте (личез, где я поигрываю иногда) их главный проггер пишет шахматных ботов!
      самый совершенный этот: БОТ ЛИИЛА!
      вроде код у них открытый, хотя хз
      Гроссов этот бот крошит в пух и прах!
        FasterHarder, спасибо за линк ... но вопросы остались открытыми.
        Меня не алгоритмы интересуют, а методология
          Цитата JoeUser @
          1) Каким образом программируются стратегии выигрыша?

          Никаким - стратегии выводятся самим ботом в виде набора весов нейросети :D Вообще, боты вроде alpha zero или leela, способные самообучаться без человека, работают относительно несложно (если не углубляться в нюансы, конечно). Есть некая нейронка, она для позиции выдаёт список "разумных" ходов (применительно к го, например - матрицу 19*19, которая, грубо говоря, интерпретируется как вероятность сходить в то поле) и вероятность выигрыша. Далее, имея эту нейронку, мы запускаем Монте-Карло, в котором ищем ноду, дающую максимальную вероятность выигрыша с т.з. этой нашей нейронки. Ну а когда игра закончилась - сдвигаем веса нейросети так, чтобы она данную игру предсказывала правильней, а так же правильней оценивала разумность ходов (выигрышная сторона делала более разумные ходы, проигравшая - менее).
          Можешь глянуть реализацию бота для го, работающего как раз по вышеописанному алгоритму и обучающегося исключительно на партиях самим с собой - leela zero. Играет этот бот на данный момент хуже, чем топовые профи, но большинство игроков ему не могут противопоставить ничего - проверено лично :crazy:

          Цитата JoeUser @
          2) Есть ли какие-то общие методики программирования игровых стратегий, безотносительно игры и правил?

          Ну для настольных игр, где передвигаются фишки, видимо, такую стратегию сделали. Для карточных игр, стратежек или какого-нибудь The Talos Principle, видимо, что-то другое надо - алгоритмы для настольных игр подходят не очень в этом случае.

          Цитата FasterHarder @
          на шахматном сайте (личез, где я поигрываю иногда) их главный проггер пишет шахматных ботов!
          самый совершенный этот: БОТ ЛИИЛА!

          leela? Она разве не проигрывает топовым ботам вроде Стокфиша?
            Цитата JoeUser @
            Такое количество вариантов современному компьютеру рассчитать в реальном масштабе времени просто не реально.

            По этому поводу вспоминается журнал GoWord для того что-бы установить какое начало игры приводит к выигрышной стратегии простой китайский клуб сыграл один миллион партий. 8-)

            Цитата JoeUser @
            Есть ли какие-то общие методики программирования игровых стратегий, безотносительно игры и правил?

            Для первичного обучения используют кластеры/суперкомпьютеры. Так что там бот в паролели играет кучу игр сам с собой. Во-вторых команд код пишут команды. Как бы команда соревнуется одним игроком пусть и лучшим профи в мире, но всё равно это не честно. :tong:


            Шутки шутками. А теперь серьёзно.
            Обучение с подкреплением. Если выиграл то стратегия верная. Если проиграл стратегия не верная.
            Самое важно это три вещи определить цену игры, делай самый большой ход и не теряй темпа. Есть ещё немало важных правил: к примеру известных как 10 правил Го. Они универсальны и их можно принимать и к другим играм.

            Цитата JoeUser @
            Есть ли какие-то общие методики программирования игровых стратегий, безотносительно игры и правил?

            Как тебе сказать и да и нет. Вот к примеру есть такое правило "разделяй и властвуй". А есть его брат блезнец "в единстве мы сила". Их вполне можно закодировать безотносительно. Но все равно под каждую игру придётся писать свою метрику.

            Вся теория обучения построена как безотносительная. Но с другой стороны эти алгоритмы точно не работают по одиночке и даже есть самомнения что будут работать в системе.
            В одних играх работают одни стратегии в других другие.

            К ответу а как же полный перебор? Полный перебор можно свернуть в короткое правило. Сейчас популярны рекурсивные нейронные сети. У них очень хорошо получается играть в Го и читать тексты. :jokingly:

            Сами по себе такие сети плохо поддаются обучению по методу обратному распространению ошибки. Поэтому их обучают через структурные методы. К структурным относятся генетические алгоритмы (ГА). По мимо ГА есть такая вещь как автокодировщик и стековые алгоритмы.

            Тут стратегия простая основана она на сжатие информации. Чем меньше нейронов тет лучше НС. Из сети пробуют удалять нейроны или связи так что-бы количество информации сохранялось на выходе.

            Большинство из этого уже закодировано в фреймворках таких как TenserFlow.

            Ещё про структурные методы. Структурные методы хороши, но теория разработана недоконца. Поэтому в большинстве задач выигрывают вероятностные деревья классификаций. Если их удаться совместить, то должен получится довольно сильный общий метод.
            0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
            0 пользователей:


            Рейтинг@Mail.ru
            [ Script execution time: 0,0292 ]   [ 15 queries used ]   [ Generated: 28.03.24, 08:45 GMT ]