Шашечная задача
Развитие компьютерной техники уже привело нас к тому, что компьютерные программы играют в шашки не хуже людей. Хотя до профессионального уровня игры в шашки программам еще далеко, не стоит забывать о том, что еще совсем недавно программы заметно отставали от человеческого мастерства. Это говорит о прогрессе не только в наращивании мощности и повышении быстродействия компьютеров, а касается и качества шашечных программ, их алгоритмов.
Целью данной статьи автор считает реализацию нового подхода к решению так называемой шашечной задачи. В идеале, шашечная программа должна знать, что последует за каждым из возможных вариантов, куда он ее приведет. А вот какое решение принять, какой вариант выбрать - это, скорее, задача автора программы.
Существует несколько основных алгоритмов, на которых базируются все шашечные программы. Некоторые из них широко известны, некоторые держатся авторами в тайне, некоторые трудно реализуемы, поэтому редко применяются. Есть еще и вспомогательные алгоритмы, такие как генератор эндшпильных баз и генератор базы дебютов. Эти алгоритмы используются один раз, сохраняя результаты своей работы, которыми программа пользуется в ходе игры.
Новизна авторского подхода заключается в объединении всех алгоритмов для получения базы данных всех возможных позиций при игре в шашки. Приглашаются все желающие принять участие в обсуждении и, возможно, реализации проекта. Следует заметить, что речь идет не только о программистах и шашистах. В проекте есть место и для распределенных вычислений, где помочь сможет любой желающий, имеющий компьютер.
Проект.
Идея пришла в голову после генерации 7-фигурной эндшпильной базы. Размышляя над генерацией 8-фигурной базы, я пришел к выводу, что она не нужна. Не то, чтобы совсем не нужна, конечно нужна, но в другом виде. В самом деле, часто ли вы встречали позиции в игре, где 5 дамок играют против 3? А 4 против 4? Вот и я таких позиций не видел. А при существующем алгоритме генерации базы, такие соотношения сил генерируются в первую очередь, далее (после 4 дамок против 4 дамок) генерируются 3 дамки и шашка против 4 дамок. Тоже редкий случай, не так ли? А вот 4 шашки на 4 шашки - другое дело; наверное, 80% (если не больше) всех партий проходит через это соотношение. Таким образом, сгенерировав 4 шашки против 4 шашек, и еще несколько других соотношений, можно сказать, что 8-фигурная база создана. Пусть не полностью, но все-таки какие-то результаты будут. Продолжаем мысль. К сведению: позиций 8 шашек против 8 шашек всего чуть меньше 724 миллиардов. Имея на 7-фигурной базе коэффициент сжатия 1 к 20, то есть в 1 байте хранится 20 позиций, можно легко посчитать, сколько будет занимать "полноценная" 16-фигурка (около 37 Гбайт). Не такие уж и страшные цифры. Я говорю "полноценная", так как считаю, что если у одной из сторон есть дамка в соотношении 8 на 8, то результат партии известен на 99.99%, или же эта дамка идет в размен в обозримом будущем.
Продолжение следует...
Шевченко Антон
E-mail: sanc0der@mail.ru
|
