Комментарии 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-15 секунд на КАЖДЫЙ ХОД (что дает глубину анализа 9-10 ходов вперед)
Это на i386 16МГц? У вас 12 шашек, а значит 22 ходов максимум, 22 ответов на ход и 10 ходов в глубину - итого 22*22*10=4840 возможных ходов (утрирую, так как взятие двух шашек приводит к двум ходам, но!!! взятая шашка не будет потом ходить в ответ, плюс у вас пока много фигур на доске и нет развития, то и ходов у вас не так и много, например для первого хода у вас всего 4 варианта начала партии, плюс - вы можете запустить сразу 1000 партий на ночь, сохранять в базу все ходы, как базу дебютов, а потом просто пользоваться базой с заведомо известным весом хода, и ходы у вас будут просто мгновенные. Этим кстати шашки выгодно отличаются от шахмат, можно все варианты ходов записать и считать не придется совсем - никогда, я бы наверное на этом и заморочился, формально игровое поле 8*4, то есть 3^32 состояний на поле, но даже с вашими оптимизациями львиная доля состояний вообще никогда не попадёт в базу, они либо невозможны, либо имеют заведомо низкий вес).
Наверное сложность будет выше с дамками и чем их больше - тем сложнее, но во всяком случае пока ни одна шашка не дошла до дамки вариантов ходов будет не так и много, можно пока сосредоточиться на них и сформировать базу дебютов без дамок. Подозреваю что 95% людей-игроков сольются еще до этого.
Для С#, который очень быстрый если им правильно пользоваться, это (15 секунд на ход) очень медленно. Я код не читал, у меня проблемы с чтением чужого кода, но в комментариях написали, что вы пользуетесь списками, это плохой вариант, C# для любого нового объекта создает копию . Ну и зачем вам Unity если есть чистый C#, а рисовать можно на канвасе формы, хоть битмапы, хоть по пикселам.
Я что-то не понял, как вы посчитали на 10 ходов вперед. На конкретном ходе у нас есть 22*22=484 варианта хода. Но из каждой из этих позиций погружаясь на новую глубину, мы получаем новую позицию, в которой в нас опять есть 484 варианта хода. Т.е. мы должны возводить в степень, а не умножать, не так ли?
На конкретном ходе у нас есть 22*22=484 варианта хода. Но из каждой из этих позиций погружаясь на новую глубину, мы получаем новую позицию, в которой в нас опять есть 484 варианта хода. Т.е. мы должны возводить в степень, а не умножать, не так ли?
Да. Но вы пропустили слово "утрирую" и текст в скобках, который в 10 раз больше чем этот расчёт. Фишка как раз в том, что 12 шашек у вас никогда одновременно ходить не смогут, а значит у вас, если вы например скормите центр врагу, будет 5-7 ходов, но через 10 ходов у вас будет еще меньше ходов, поэтому у вас, опять же, не будет стабильно 5^10 ходов. Думаю если исключить ходы с дамками, то партия будет приходить за <100 ходов, причем при формировании базы дебютов каждая последующая партия будет в явном виде производить расчёт всё меньшего и меньшего числа ходов и в конечном итоге все ходы будут в базе (повторюсь - без дамок).
<занудство ON>
учитывая шашки справа и слева я уменьшил число ходов с 24 (12*2) до 22, но это неправильно, так как из 12 шашек шесть штук не будут иметь позиции для второго хода, поэтому будет 6*2+6=18. Но в процессе игры конечно не всегда будет сохраняться константное значение шашек с одним полем для хода и с двумя. Так что моё уточнение всё же это занудство.
<занудство OFF>
Ничего не редактировал.
У меня была идея, дать компу играть самим с собой, но непонятно, что с этим делать дальше.
Вы предлагаете дать компу играть самому с собой, пока на доске нет дамок, и формировать таким образом базу дебютов. Но как компу понять, что дебют действительно хороший? То есть даже если позиция после 10-15 ходов равна по материалу, это не значит, что она равна действительно. Как компьютеру, разыграв партию, понять, что этот дебют действительно хороший и его стоит запомнить... Не совсем интуитивно понятно...
Во-первых вы, как я понял, считаете вес того или иного хода или состояния, что мешает это продолжать делать?
Во-вторых, цель - просчитать все дебюты до первой дамки (я дамку специально выделяю, так как там, из-за большей подвижности фигуры количество ходов становится очень большим)
В-третьих, узнать (эмпирически) - сколько существует состояний доски с появлением первой дамки. Интуитивно я не могу утверждать даже порядок. И если таких состояний например 30, то сколько бы вы ходов не делали до этого у вас все равно всё будет приходить к этим 30 состояниям.
В-четвертых, сложность и интерес будут представлять только эндшпили от момента появления первой дамки. Всё что до этого вообще не нужно рассматривать. Вот вычислительно эндшпили и будут представлять сложность, возможно поэтому в программе Plus есть ограничение на базу эндшпилей от 8 фигур, так как на это были потрачены ресурсы.
В-пятых, будет определенное число партий, которые будут завершаться победой до появления дамки. Можно посчитать пока только их, это уже позволит быстро отыгрывать часть дебютов и доводить их до победы.
Для хранения состояния доски достаточно 8 байт (доска 4х8, 2 бита на состояние: пусто, белая, черная, это DWORD, это же хеш), мне кажется сами ходы совсем не важны, достаточно выстроить последовательность состояния доски - двунаправленное дерево. В C# это Dictionary по DWORD (uint кажется для 8 байт). Смотрите словарь, если нет совпадения, то применяете ваше решение как в этой статье, если есть совпадение, то вам отдается список хешей следующих возможных состояний.
В общем это мои размышления, не претендую на истину.
Я правильно понимаю, что сейчас выиграть у компьютера в шашки невозможно? В отличии от шахмат
Выиграть у компьютеры в шахматы — невозможно. После победы компьютера DeepBlue над Каспаровым в 1996 году, компьютеры развились настолько, что могут победить даже чемпиона мира, еще и с форой.
Английские шашки, как я написал, постигла ничейная смерть. Это значит, что были полностью рассчитаны варианты, гарантированно обеспечивающие игроку ничью, за какую сторону бы он не играл.
Насчет русских шашек -- не уверен. Как я и сказал, я не нашел каких-либо готовых программ.
ей нужно 10-15 секунд на КАЖДЫЙ ХОД
Для начала стоит поискать профайлером горячие места.
Но линейный поиск транспозиций через сравнение строк? Тем более в шашках только ходы дамок могут привести к повтору.
Возможно, требуется много памяти. Можно хранить положение всех белых шашек в виде одного числа, тогда на все состояние потребуется 3 числа (белые, черные, признак дамок) и байт хода.
При таком хранении большую часть ходов можно получить несколькими битовыми операциями.
@GlukKazanтут в шашки играют
А тут https://ru.wikipedia.org/wiki/Plus600_(шашечная_программа) наверное самая сильная программа по русским шашкам.
По большому счету, у вас самые большие оптимизации выполнены.
Основная цель оптимизации алгоритма перебора - это увеличение количества отсечений.
То есть лучше не делать работу по перебору позиций, если вся ветка будет впоследствии отсечена другим ходом.
Можно еще чуть дожать отсечения, если использовать NegaScout алгоритм (вариация альфа-беты, но симметричная).
Я еще пробовал MTD(f), но каких-то существенных улучшений от использования алгоритма не заметил.
Что у вас не хватает - это отсечения по границам. Например, в переборе на определенную глубину вы нашли, что позиция оценена как 200.
Если эта оценка между альфой и бетой, то вы сохраняете в хэш точную оценку позиции. Потом ее прочитаете - и используете, здесь все правильно.
Но если вы нашли оценку 200, когда ваша альфа 200, то у вас отсечение, а не оценка позиции. В будущем - иногда вы можете отсечь (если следующий перебор будет с более режущими условиями), а иногда - нет.
Вам тут в соседних комментариях указывают на то, что списком хранить хэш-таблицу не стоит, а стоит использовать что-то более оптимальное.
Также стоит обратить внимание на представление доски. Использование битовых масок, если на доске нет дамок, позволяет определить наличие возможности боя (бой обязателен) без перебора каждой шашки. Скорость генератора ходов на частоте процессора 2ГГц была около 10 млн генераций/сек. Это на одном ядре, конечно же.
Оценочная функция - это основное в шашечной программе (имхо), если все оптимизации сделаны. У вас ее уровень - слабый. Учитывание материальных факторов (стремление к материальному перевесу) - это база игры в шашки, но оценка позиции должна быть намного более комплексной. Здесь остро проявляется отличие шахмат от шашек: в шахматах фигуры разные, а в шашках - одинаковые. Это делает игру интереснее и сложнее в плане оценки позиции.
В подавляющем большинстве случаев дамки появляются либо только у одной из сторон, либо в эндшпилях (кол-во фигур менее 10). Если дамка появляется в середине партии, да еще и у каждой из играющих сторон, то такие позиции оценить крайне тяжело. Но таких партий очень мало.
Перспективные направления в шашечном программировании я бы назвал такие: миттельшпильные базы (хранение возможности выигрыша в позиции, которая не расчитана в ЭБ), нейронные сети по построению оценочной функции, и использование параллельных алгоритмов (альфа-бета очень плохо параллелится). Конкуренты (другие программы по игре в шашки) ведут расчет глубже за счет еще больших отсечений. Я не знаю как к этому относится, на тот момент когда это стало актуально, я уже отошел от программирования шашек.
В шашках ничейная смерть у турниров начала просматриваться довольно давно. С появлением компьютерных программ - проблема стала намного острее. В частности, игра по переписке почти умерла из-за этого.
В итоге - некоторые турниры проводятся с жеребьевкой 1-2 первых ходов, некоторые из модифицированной стартовой позиции (летающая шашка). Результатом в таких турнирах является результат микро-матча, когда игроки поочередно играют одну и ту же стартовую позицию сначала белыми, а затем черными. Вероятно, только блиц-турниры (5 мин на партию) из начальной позиции еще дают какие-то результаты.
Мой опыт разработки программы для игры в шашки с помощью алгоритма минимакс