Comments 16
Спасибо за статью, подкинули интересные мысли. Надо будет на досуге почитать внимательнее. Кстати, не думали организовать auto-play между ботами? Сильно экономит время и силы в процессе отладки ботов (не надо каждый раз играть самому).
Спасибо, может еще поэкспериментирую. Auto-play я использовал в тестах, чтобы сравнить наскоро пару настроек (с отсечением с сортировкой и без). Плюс в принципе удобный тест — может ли игра закончить партию, не скатится ли в стояние на месте — повторяющиеся ходы.
Если бы у меня была нейросеть или что-то иное, самообучаемое, я бы подкинул ей материала, заставив играть саму с собой.
Сейчас одна партия для пары ботов занимает секунд 10. Была мысль оптимизировать поправочные коэффициенты в эвристической функции за счет auto-play. Но перебрать надо несколько тысяч вариантов, минимум.
Если бы у меня была нейросеть или что-то иное, самообучаемое, я бы подкинул ей материала, заставив играть саму с собой.
Сейчас одна партия для пары ботов занимает секунд 10. Была мысль оптимизировать поправочные коэффициенты в эвристической функции за счет auto-play. Но перебрать надо несколько тысяч вариантов, минимум.
UFO just landed and posted this here
Спасибо, приятно было разобраться. Плюс один проект на потенциальное участие :)
Кстати, помимо Фейта и Лесли есть ещё одна оценка, на мой взгляд, наиболее адекватная. Просто надо из оценки текущего игрока отнять оценки всех его противников. Как-то так.
Иначе говоря, вы предлагаете вариант А, а сейчас реализован вариант В:
Можно и так попробовать, кто знает. Но ведь, как я предполагал ранее, остается проблема: в погоне за «относительным» результатом AI может перехитрить самого себя?
Можно и так попробовать, кто знает. Но ведь, как я предполагал ранее, остается проблема: в погоне за «относительным» результатом AI может перехитрить самого себя?
Именно так. Мне думается, Фейт опять сам себя перехитрил. Оценка (A) зависит и от оценки собственной позиции и от оценок всех противников (что и требуется) и при наличии лучшей собственной оценки будет выбирать её. Пытаюсь сейчас, кстати, применить новые идеи к этой игре (в релизе пока другой бот), но не слишком успешно. Не удаётся просматривать глубоко и широко. По быстродействию, нормально пока удаётся работать со следующим вектором отсева [20, 3, 3, 3], что при простейших эвристиках и оценках совершенно несерьёзно (фигуры лезут под бой, в том числе и короли). Попробую улучшить эвристики, введя штрафы за бой фигур. В любом случае, спасибо. Дело сдвинулось с мёртвой точки.
А, кстати, зачем в B минимум? максимум же? (но A всё равно лучше).
Можно поменять знак и получится max(Pk — Pi)
То есть, ваша программа строит дерево из 4х ходов? Или вы только матрицу привели для 4-х ходов, а смотрит алгоритм «глубже»?
Да, 20 ходов — это как раз столько же, сколько в шахматном дебюте (в миттельшпиле вроде побольше). Много, конечно, но поддается решению. Судя по шахматам.
Вопрос, сколько вершин дерева обрабатывает ваша программа за приемлемое время. Если существенно меньше 100 000 / сек, значит можно предположить, что программа остро нуждается в оптимизации.
Если порядок ± такой же, значит, вероятно, проблема в эвристике — как и у меня в Зайце.
Удачи с вашей реализацией.
Да, 20 ходов — это как раз столько же, сколько в шахматном дебюте (в миттельшпиле вроде побольше). Много, конечно, но поддается решению. Судя по шахматам.
Вопрос, сколько вершин дерева обрабатывает ваша программа за приемлемое время. Если существенно меньше 100 000 / сек, значит можно предположить, что программа остро нуждается в оптимизации.
Если порядок ± такой же, значит, вероятно, проблема в эвристике — как и у меня в Зайце.
Удачи с вашей реализацией.
Там не всё просто с оптимизацией. Движок универсальный, что даёт свои издержки. Да, сейчас смотрел на 4 хода (но тут 4 игрока и это по одному на каждого). Пробовал другие вектора тоже [0, 10, 5, 5, 1, 1, 1, 1] например, но 0 для первого игрока тоже чревато, в середине игры начинают идти непредсказуемые задержки. Улучшение эвристики должно помочь, я уже экспериментировал с этим на других играх. В принципе, при хорошей эвристике даже без минимакса играет вполне вменяемо. В общем надо продолжать экспериментировать.
Банальнейшая ошибка в эвристике была (в результате которой ходы вообще не сортировались). Поправил, вменяемость в игре сразу появилась. Ограничил просмотр на нижнем уровне 3 секундами и использую вектор [0, 5, 5, 5]. Успевает просмотреть порядка 20 ходов верхнего уровня и около 1500 листовых позиций. На остальных векторах (для этой игры) показатели хуже. Буду дальше улучшать эвристику, но игра выглядит уже неплохо.
Если у вашей программы чемпионские амбиции, то, наверное, придется как-то оптимизировать движок (генератор ходов), чтобы просматривать в 10… 100 раз больше листовых позиций…
У неё нет чемпионских амбиций. Это скорее универсальный движок охватывающий большое количество относительно простых игр. Мысли по его оптимизации есть (скорее в 10 чем в 100), но они довольно глобальные и сейчас я этим заниматься не готов. Кроме того, нет уверенности, в том что это сильно поможет (у Jocly похожие проблемы с AI, а универсальностью там сроду не заморачивались). Для чемпионских движков нужна многопоточность и оптимизации связанные со спецификой игры. Это немножко не то чем я занимаюсь.
Sign up to leave a comment.
AI в игре Hase und Igel: minimax на троих