Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 25
Отличная статья, я недавно тоже делал свои русские шашки: https://medv.io/шашки/
Для начала можно попробовать хранить кешированные позиции в хешмапе, а не в листе. Это должно дать неплохой такой прирост производительности:)
Довольно странно брать эндшпили из базы партий. Гораздо эффективней построить свою версию таблиц Налимова, там в основе довольно простая идея.
У вас в правилах ошибка. В русских шашках нет обязанности бить большинство. Это правило из международных шашек (поле 10 на 10, "стоклетки"). Другое отличие стоклеток от русских - это правило боя через дамочное поле (в русских шашка становится дамкой и продолжает бой как дамка; в стоклетках бой продолжается как шашка если возможен). Если применить правила стоклеток на малую доску (8 на 8), то получатся бразильские шашки.
Есть еще такая тема, как эндшпильные базы. Для количества фигур меньше определенного можно расчитать все позиции. В Тундре (шашечная программа, я - один из авторов) полная сжатая 8-фигурка была около 5ГБ (это половина базы, которой достаточно программе для получения результата позиции мгновенно). Было развитие темы в сторону неполных эндшпильных баз, но перспективы этого направления ждут очередного исследователя. В вашей статье рассматривается дебютная библиотека, а не эндшпильная. В эндшпильных базах не хранится позиция, там строится индекс позиции, а в базе хранятся только значения В/Н/П (или количество ходов до выигрыша/проигрыша или перехода в следующий подкласс ЭБ).
PS. Еще кажется, что у вас алгоритм боя неправильно закодирован. Навскидку, он должен быть сложнее. Например, в позиции б.д. a1, ч.ш. b2 доступно 6 ходов (бой с a1 на c3, d4, e5, f6, g7, h8). Если добавить черную на f4, то должно быть 2 хода (a1:e5:g3; a1:e5:h2).
Спасибо за комментарий.
Насчет правил — у меня все так и есть. В начале статьи написано: "Если есть несколько вариантов боя — можно выбрать любой". И насчёт дамки -- если шашка превратилась в дамку, она у меня продолжает бить по правилам дамки. Об этом написано в третьей bullet-point после функции GetAllMoves()
Про эндпильные базы -- интересно. А что за программа такая, Тундра? Она открыта? Можно где-то посмотреть, как она работает?
Насчет алгоритма боя, я долго с этим промучился, к тому же я и сам не понимал, обязан ли игрок брать еще одну шашку, если может этого избежать. Но эту ошибку я исправил и сейчас действительно доступно в такой позиции только два взятия. Этой программой я играл с другими приложениями в плеймаркете, и везде правила и возможности ходов совпадали.
Насчет правил - когда я читал было написано про большинство. Вы исправили в статье или я ошибся?
Тундра - программа для игры и анализа шашечных позиций (и партий). Последняя версия 2.4.6, вышла в феврале 2006. Первая версия (не публичная) была - в 2002м. Последняя демо-версия была 2.4.5, в ней был таймер на 10 минут (после этого программа завершала работу). Демо играла хуже, чем проф. версия, которая продавалась до 2009-го примерно.
Найти демо-версию, вероятно, можно на торрентах, и скорее всего с отломанным таймером. Размер исполняемого файла - в районе 300кБ. Обычно вирусы весят больше, так что если размер сильно больше - остерегайтесь. Официальный сайт - в дауне последние несколько лет. Но интернет многое помнит :)
Я что-то не понял, как вы посчитали на 10 ходов вперед. На конкретном ходе у нас есть 22*22=484 варианта хода. Но из каждой из этих позиций погружаясь на новую глубину, мы получаем новую позицию, в которой в нас опять есть 484 варианта хода. Т.е. мы должны возводить в степень, а не умножать, не так ли?
Ничего не редактировал.
У меня была идея, дать компу играть самим с собой, но непонятно, что с этим делать дальше.
Вы предлагаете дать компу играть самому с собой, пока на доске нет дамок, и формировать таким образом базу дебютов. Но как компу понять, что дебют действительно хороший? То есть даже если позиция после 10-15 ходов равна по материалу, это не значит, что она равна действительно. Как компьютеру, разыграв партию, понять, что этот дебют действительно хороший и его стоит запомнить... Не совсем интуитивно понятно...
Я правильно понимаю, что сейчас выиграть у компьютера в шашки невозможно? В отличии от шахмат
Выиграть у компьютеры в шахматы — невозможно. После победы компьютера DeepBlue над Каспаровым в 1996 году, компьютеры развились настолько, что могут победить даже чемпиона мира, еще и с форой.
Английские шашки, как я написал, постигла ничейная смерть. Это значит, что были полностью рассчитаны варианты, гарантированно обеспечивающие игроку ничью, за какую сторону бы он не играл.
Насчет русских шашек -- не уверен. Как я и сказал, я не нашел каких-либо готовых программ.
ей нужно 10-15 секунд на КАЖДЫЙ ХОД
Для начала стоит поискать профайлером горячие места.
Но линейный поиск транспозиций через сравнение строк? Тем более в шашках только ходы дамок могут привести к повтору.
Возможно, требуется много памяти. Можно хранить положение всех белых шашек в виде одного числа, тогда на все состояние потребуется 3 числа (белые, черные, признак дамок) и байт хода.
При таком хранении большую часть ходов можно получить несколькими битовыми операциями.
@GlukKazanтут в шашки играют
А тут https://ru.wikipedia.org/wiki/Plus600_(шашечная_программа) наверное самая сильная программа по русским шашкам.
По большому счету, у вас самые большие оптимизации выполнены.
Основная цель оптимизации алгоритма перебора - это увеличение количества отсечений.
То есть лучше не делать работу по перебору позиций, если вся ветка будет впоследствии отсечена другим ходом.
Можно еще чуть дожать отсечения, если использовать NegaScout алгоритм (вариация альфа-беты, но симметричная).
Я еще пробовал MTD(f), но каких-то существенных улучшений от использования алгоритма не заметил.
Что у вас не хватает - это отсечения по границам. Например, в переборе на определенную глубину вы нашли, что позиция оценена как 200.
Если эта оценка между альфой и бетой, то вы сохраняете в хэш точную оценку позиции. Потом ее прочитаете - и используете, здесь все правильно.
Но если вы нашли оценку 200, когда ваша альфа 200, то у вас отсечение, а не оценка позиции. В будущем - иногда вы можете отсечь (если следующий перебор будет с более режущими условиями), а иногда - нет.
Вам тут в соседних комментариях указывают на то, что списком хранить хэш-таблицу не стоит, а стоит использовать что-то более оптимальное.
Также стоит обратить внимание на представление доски. Использование битовых масок, если на доске нет дамок, позволяет определить наличие возможности боя (бой обязателен) без перебора каждой шашки. Скорость генератора ходов на частоте процессора 2ГГц была около 10 млн генераций/сек. Это на одном ядре, конечно же.
Оценочная функция - это основное в шашечной программе (имхо), если все оптимизации сделаны. У вас ее уровень - слабый. Учитывание материальных факторов (стремление к материальному перевесу) - это база игры в шашки, но оценка позиции должна быть намного более комплексной. Здесь остро проявляется отличие шахмат от шашек: в шахматах фигуры разные, а в шашках - одинаковые. Это делает игру интереснее и сложнее в плане оценки позиции.
В подавляющем большинстве случаев дамки появляются либо только у одной из сторон, либо в эндшпилях (кол-во фигур менее 10). Если дамка появляется в середине партии, да еще и у каждой из играющих сторон, то такие позиции оценить крайне тяжело. Но таких партий очень мало.
Перспективные направления в шашечном программировании я бы назвал такие: миттельшпильные базы (хранение возможности выигрыша в позиции, которая не расчитана в ЭБ), нейронные сети по построению оценочной функции, и использование параллельных алгоритмов (альфа-бета очень плохо параллелится). Конкуренты (другие программы по игре в шашки) ведут расчет глубже за счет еще больших отсечений. Я не знаю как к этому относится, на тот момент когда это стало актуально, я уже отошел от программирования шашек.
В шашках ничейная смерть у турниров начала просматриваться довольно давно. С появлением компьютерных программ - проблема стала намного острее. В частности, игра по переписке почти умерла из-за этого.
В итоге - некоторые турниры проводятся с жеребьевкой 1-2 первых ходов, некоторые из модифицированной стартовой позиции (летающая шашка). Результатом в таких турнирах является результат микро-матча, когда игроки поочередно играют одну и ту же стартовую позицию сначала белыми, а затем черными. Вероятно, только блиц-турниры (5 мин на партию) из начальной позиции еще дают какие-то результаты.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Мой опыт разработки программы для игры в шашки с помощью алгоритма минимакс