Здравствуй, сообщество CodeForces!
Пишу я задание для получения зачёта по проге и сталкиваюсь со следующей проблемой. В общем, имеется игра Реверси. Имеются несколько типов ботов, из них:
жадный: ходит самым максимальным из доступных ходов (greedy)
перебор minmax дерева игры глубиной до N (aiN)
то же, что и выше, но написанное с ab-отсечением. (aiN_ab)
Имеется проблема:
Счёт за 300 игр:
ai4 vs. greedy — 287:8 и это, я считаю, нормально
ai4_ab vs. greedy — 250:47 и это не очень нормально.
Насколько я понимаю, аб-отсечения должны давать такой же результат, но быстрее. Собственно имеется вопрос: это не так или я делаю что-то не так? Исходники-примеры я брал отсюда, отсюда, отсюда и ещё с некоторых других источников (мой код). Результат везде одинаковый. Может у кого-то есть реальный пример какой-то игры, а не просто сатья-мануал? Ну или какие-то комментарии по этому поводу, буду очень признателен.
А можете показать код ai4? Да, если ab-отсечения дают худший результат, то они неправильно написаны. Но игра — не лучшая область для исследований, потому что даже если всё написано правильно, ab и перебор могут найти разные лучшие решения, которые приведут к разным результатам. Лучше взять какую-нибудь задачу на перебор и попробовать сдать её при помощи ab.
да, вот весь код ai.
Точнее, неполный перебор игры — не самая лучшая идея для сравнений. Но всё равно странно. Есть, например, вот такая задача, которая сдаётся ab-отсечениями и лютым загоном в TL.
Ты не правильную ссылку даешь. У них там явно нет тестов, которые Burunduk1 доделал этой осенью. Впрочем, давать ссылку с доделаными тестами я не умею.
Что какие новые тесты ? Хочу сдать задачу с новыми тестами!
Новые тесты есть в универовском контесте нашем за 1 семестр. Я не знаю как туда кому-то попадать. Можно написать сереже, думаю прислать тебе тесты не проблема.
Да ладно не лютым)) Просто там ab надо писать с запоминанием... ну и сервер должен быть не тормозным... Хотя там ещё надо битхаки делать, но я верю, что это было из-за медленного сервера...
Правильное αβ-отсечение, должно давать тот же результат, что и раньше, но быстрее, что позволяет увеличить глубину перебора. Увеличение глубины перебора должно улучшать результат в среднем, но на отдельных играх приводит к непредсказуемым результатам. Впрочем, иногда перебор большего количества ходов одной четности работает хуже чем меньшего числа ходов другой четности. Тут еще от функции оценки многое зависит.
Как программы ведут себя при одинаковой глубине просчета? Если нет рандома, должны вести себя полностью одинаково. Иначе баг, и его несложно будет отследить.
Не правда. αβ-отсечение имеет полное моральное право найти другой ответ с такой же функцией оценки.
Верно.
Тогда можно попробовать на время поиска бага полностью изменить функцию оценки, лишь бы два состояния не имели одинаковой стоимости.
А как оно может найти другой ответ, если мы не меняем глубину поиска, все перебираем в таком же порядке и обновляем ответ только если он строго лучше?
Видимо если брать в каком-то смысле лексикорафичеки минимальный ответ, то никак..
Рандом в решении есть.
Если убрать рандом у ai и ai_ab, но оставить у greedy, то забавно получается: ai_ab в среднем лучше играет с greedy, ai как играл, так и играет. Ходят ai и ai_ab одинакого. Мистика.
Прошу прощения, что не стану копаться в коде — это несколько утомительно. Так, навскидку. Непонятно, как вообще использовать отсечение в игровых программах с оценочной функцией. Большинство оценочных функций в игровых программах немонотонны. Допустим лучшее найденной решение имеет качество +100 после 10 хода. Я на пятом ходу получил позицию с качеством -100. О чем это говорит? Да ни о чем, если только за 5 ходов в принципе невозможно перейти от позиции с оценкой -100 к +100, что вряд ли.
Опиши вкратце функцию оценки словами.
самая банальная оценка: фишка в углу весит X, у стенки — Y, обычная — Z. когда писался пост это были числа (4,3,2). Свои фишкисо знаком "+", врага со знаком "-"
Подозреваю, что дело вот в чем. Функция оценки неверна и действует во вред. В реверси рулит тот игрок, у которого больше ходов. У него больше свобода действий, он может вынуждать противника делать плохие ходы. А ходов больше, как ни странно, у того, у кого меньше фишек. В начале-середине игры следует минимизировать количество своих фишек, особенно дающих ходы противнику. И лишь в самом конце, загнав оппонента в плохое положение, набирать количество. Твоя программа честно следует функции оценки и оказывается в худшей ситуации. Погугли основы стратегии реверси и измени функцию. А углы надо оценивать на дофига, тут ты прав)
Ты бы свою прогу выложил) Я-то в реверси не шарю, но автору поста, наверное, будет интересно
А еще исследование(читать гугление) которое мы проводили на сборах, когда делали такую задачу, показало, что не все стены одинаково полезны. Например своя фишка во 2 или 7 клетке в ряду это скорее плохо чем хорошо. В интернете не сложно найти веса клеток найденные профессионалами.
Так чем все закончилось?
да впринципе процесс ещё идёт... но лагов в альфабета не нашёл. Поэтому на этот "баг" я забил. Единственное, убрал рандом при равенстве ответа, но добавил рандомный обход доски при поиске, на результат почти не влияет. А ещё, я с весами в оценщике продешевил, поставил (32,8,1) теперь средний счёт 300:0, хрен его обыграешь. Понятно, что это не предел, поэтому буду писать ГА с особями, у каждой своя табличка коэффициентов :)
а так ещё хороший дискасс нашёл