Виртуальный шашечный клуб
ТАВЛЕИ >> Другие шашки >> НАША ИСТОРИЯ >>
С.Старцев. "Plus600": Этапы большого пути Может быть, кого-то удивит выбор раздела,
в котором мы публикуем этот материал (почему не "Компьютерные шашки"?). Но это
объясняется просто.
Во-первых, это уже действительно - ИСТОРИЯ. И, во-вторых, - безусловно, НАША!
( прим. вебмастера ).
Компьютерная программа по русским шашкам PLUS600:
Этапы большого пути :)
История создания программы "Plus600" насчитывает уже более двух десятилетий.
Началось все летом 1981 года, когда тогда еще весьма молодой
Григорий Ветрогон , хорошо разбирающийся в шашках (кмс) и ощутимо слабее разбирающийся
в программировании, поспорил со своим коллегой по
учебе в МГУ Сергеем Старцевым (вашим покорным слугой). Арбитром выступал
Сергей Педько .
Предмет спора был таков: необходимо было за две недели написать программу, которая
правильно бы осуществляла хода и взятия по правилам
русских шашек. Кто знает отличия взятий в русских шашках, тот поймет сложность
проблемы в том далеком году. Напомню, до персоналок
оставалось еще несколько лет, а программы тогда приходилось набивать на перфокартах.
А если вспомнить первую ЭВМ для этой программы -
легендарную БЭСМ-4М , то картина станет совсем ясной.
Поскольку мы только что окончили 5-й курс, впереди был только диплом и, следовательно
(да простит меня мой научный руководитель), много
свободного времени - как личного, так и машинного.
Следующие две недели были для меня и, с тех пор консультирующего меня Сергея
Педько, достаточно напряженными. Хотел бы я посмотреть в глаза
тому, кто придумал такие правила для взятий?! Этого человека оправдывает только
одно - он вряд ли предполагал, что этот алгоритм нужно
будет программировать.
Но, как бы там ни было, через две недели пари было выиграно - программа делала
ходы по правилам русских шашек. Тут бы и остановиться, но
любопытство оказалось сильнее. И мы легко перешли к решению следующей задачи
- научить программу ИГРАТЬ (перешли-то легко, а вот решаем эту
задачу до сих пор).
В том же 1981 году на БЭСМ-4М удалось получить программу, играющую в русские
шашки. С высоты сегодняшних достижений параметры той программы
смотрятся весьма скромными - глубина расчета 2-4 полухода, но главной цели мы
достигли - программа ИГРАЛА! И, видимо, это была первая
программа для русских шашек (поправьте, если я не прав - другой информации у
меня нет).
В 1982 году программа была переписана для ЭВМ СМ-4 . Тут уже стал возможен нормальный
интерфейс взаимодействия с человеком, да и глубину
расчета удалось увеличить. Этот год мы приняли как год рождения нашей программы.
До 1985 года программа продолжала потихоньку
совершенствоваться, а ее авторы - лучше разбираться в теории перебора. Однако,
поскольку в 1982 году мы закончили астрономическое отделение
физфака МГУ и разъехались кто куда - Григорий Ветрогон в Подмосковье, а Сергей
Педько в Харьков, особо серьезных теоретических новинок
разработать не удалось (напомню, что электронной почты тогда не было!).
В период с 1985 по 1989 год программа пережила еще один "редизайн" и прописалась
на EC-1060 . Считать программа стала намного дальше, но
особого сопротивления человеку еще оказывать не могла.
С 1989 года программа живет на персоналках. Однако развитие ее, до 1998 года,
шло "от случая к случаю" и особыми успехами в игре с людьми
она похвастать не могла. Однако у любителей (себя я отношу именно к ним) программа
стала стабильно выигрывать.
Среди реализованных идей того времени имеет смысл отметить только "античеловеческий"
алгоритм и оценочную функцию. Программа при наличии
почти равноценных ходов, выбирала не все время один и тот же ход, что не позволяло
человеку нащупать слабинку программы и спокойно ею
пользоваться. Что касается оценочной функции , то это - "сердце" нашей программы:
можем только сказать, что ее основа осталось до сих пор
той же самой.
В 1998 году было принято решение заняться подготовкой коммерческой версии программы.
Требовалась какая-то изюминка, отличающая программу от
других. В голове у меня давно витала идея о том, как было бы хорошо научить
программу совершенствоваться во время игры. Однако реализация
идеи оказалось весьма непростым делом. Но, в конце концов, эту проблему удалось
решить. И в этом же году программа получила алгоритм
самообучения , оставшийся в ней и до настоящего времени.
Теперь, попав однажды в проигрышную ситуацию, программа при следующей игре учтет
эту информацию и, скорее всего, выберет другой ход.
Алгоритм очень напоминает действия человека в подобных ситуациях. Разумеется,
этот алгоритм также эффективен и не только для случаев
проигрыша программы, но и для ситуаций с ее выигрышем - в следующий раз программа
увидит победу еще раньше (или если программа будет играть
другим цветом - то раньше сможет уйти от поражения).
Реализация этого алгоритма весьма проста - результаты расчета текущего хода пишутся
в базу данных и используются в дальнейших расчетах.
Сложности и хитрости, как всегда, в деталях - их мы раскрывать не будем.
Однако реализация алгоритма самообучения открыла перед нами еще одну возможность,
которую мы с успехом используем уже четыре года. Это некий
аналог "распределенных" вычислений или "коллективного разума" (мне этот термин
нравится больше). Поскольку результаты работы программы
сохраняются у всех пользователей, то мы решили создать у себя Центр Знаний.
Его задача - принимать информацию от всех копий программ,
суммировать ее и возвращать эту обобщенную информацию обратно. Таким образом,
все зарегистрированные версии программы работают на одно дело
- усиливают свою игру.
Подготовка коммерческой версии программы заставила вычистить много "узких" мест
в программе. К тому же, тиражирование программы принесло нам
неоценимую помощь - это советы, замечания и идеи наших пользователей. Поверьте,
большая часть ныне существующих функций программы сделана
по их идеям.
В 2001-м году программа приняла участие в компьютерном чемпионате России. Итог
- пятое место из шести. Однако, более важен другой итог -
были определены направления развития программы. И что более важно, после этого
чемпионата были восстановлены наши связи с Григорием
Ветрогоном, в лице которого мы опять получили профессионального консультанта.
Были определены следующие задачи:
увеличение глубины расчета за счет оптимизации механизма перебора;
активное наполнение библиотеки дебютов;
активизация расчетов баз окончаний;
создание режимов автоматического анализа партий и позиций.
В 2002-м году программа приняла участие в очередном компьютерном чемпионате России.
Выступление было уже гораздо более весомым - третье
место из шести, но заставило признать, что первую задачу в полной мере реализовать
не удалось. Однако выводы были сделаны правильные и к
следующему чемпионату мы подошли во всеоружии. Итак, что же представляли собой
"плюсы" "Plus600" на начало 2003 года:
удобство работы с программой;
наличие большого числа функций, необходимых шашисту в его работе;
алгоритм самообучения;
оригинальная оценочная функция;
самая большая библиотека дебютов;
автоматический анализа партий (включая "поточный" анализ) и позиций;
фоновый режим расчета за счет времени противника;
эффективный механизм перебора;
наличие 7-ми фигурной базы окончаний.
Эти "плюсы" не смогли не сказаться на результате - теперь программа носит гордое
звание чемпиона России среди компьютерных программ 2003
года . Не обошла нас своим вниманием и пресса, интересующихся отсылаем к 9-му
номеру популярного журнала "GAME.EXE" за 2003 год.
Хотелось бы отметить основную цель, которую мы преследуем, создавая и развивая
нашу программу. Это не достижение максимального результата
при игре с другими программами или людьми, не максимальная глубина перебора
или 100% эффективность использования процессора или оперативной
памяти. Нет! Это -
создание эффективного и удобного помощника для человека, играющего в шашки .
Для любителя - это просто соперник для приятного времяпрепровождения.
Для профессионала - необходимый помощник для анализа партий и позиций, и, при
необходимости, весьма серьезный противник. Не будем
обольщаться, до гроссмейстерского уровня программе еще далеко, но мастеру спорта
программа оказывает вполне достойное сопротивление.
К настоящему моменту программа обзавелась еще радом важных преимуществ, это:
8-ми фигурная база окончаний;
сетевая игра.
Теперь основное направление наших усилий на ближайшее время - это выверка и расширение
дебютной базы . Тут очень много задумок и идей,
надеемся, их реализация поможет избежать излишней "ничейно-ориентированности"
программы.
Сергей СТАРЦЕВ,
автор программы PLUS600
г.Москва, ноябрь, 2003 г.
Выпуск листа #15
Членов клуба: 9 человек
Модератор Аргунов Артём:
argunov20***@r*****.ru
Архив Листа - http://subscribe.ru/archive/sport.others.checkers
