green_fr (green_fr) wrote,
green_fr
green_fr

Шашки

В Pour la science рассказали о "конце шашек" - игру (здесь и далее имеются в виду "английские шашки" (Jeu de dames anglaises), т.е. шашки 8*8, назад бить нельзя) окончательно просчитали и вывели оптимальный алгоритм, следуя которому невозможно проиграть ни за белых, ни за чёрных.

Само по себе это уже впечатляет.

Я в школе прочитал книжку (Мартин Гарднер?) про "самообучающийся автомат из спичечных коробков и пуговиц", который "учился" играть в крестики-нолики методом естественного отбора. Каждый спичечный коробок соответствует возможному положению в игре, каждая пуговица внутри - одному из возможных в этом положении ходу. Для хода машины нужно потрясти коробок и вытащить наугад одну пуговицу.
Ход, после которого машина проиграла, объявляется пораженческим, и соответствующая пуговица удаляется из коробка. Пустой коробок объявляется пораженческим, и ходы, ответ на которые приводят к пораженческим положениям тоже объявляются пораженческими.
Рано или поздно в коробках останутся только оптимальные ходы, следуя которым проиграть невозможно.

Прочитав эту книжку, я тут же "собрал" машину и обучил её.
Когда в поле досягаемости появились компьютеры, я не стал браться за шахматы (в книге явно проговаривалась невозможность такого алгоритма, там количество вариантов получалось едва не соизмеримое с количеством атомов Вселенной :-)), а вот шашки показались вполне реальными. Я не смог вот так с пол-пинка прикинуть количество возможных вариантов, но программу написал и запустил. Не помню, не хватило ей памяти, или мне терпения, но, судя по статье, шансов у меня было немного: вариантов в шашках 1080, что соизмеримо если не со Вселенной, то с суммарным (на сегодняшний день) объёмом компьютерной памяти на планете.

Больше всего меня в статье поразил Marion Tinsley - чемпион мира по шашкам с 1950 года. Программу Chinook, в конечном итоге просчитавшую всю игру, начали писать именно с целью выиграть у мэтра, не проигравшего к тому времени ни одной партии (это по версии журнала - wikipedia утверждает, что 7 партий он всё-таки проиграл).
В 1992 году мэтр сделал первую версию программы, проиграв, впрочем, ей две партии в ходе турнира.
Следующая версия программы вышла в 1994 году, но турнир пришлось прервать из-за болезни Tinsley, который вскорости умер.

Тут сразу две красоты.
Первая: каким же надо быть монстром, чтобы 45 лет оставаться непобедимым (да ещё и с таким отрывом - ни одной проигранной партии). Шумахеру есть (было) к чему стремиться.
Вторая: представляю, что сказали про себя авторы программы, узнав, что она никогда не сможет сразиться и победить того, для кого её писали. Выход у них оставался только один: найти оптимальный алгоритм и математически доказать, что даже Tinsley не мог бы у него выиграть. Чем они и занялись.

Как я понял, невозможность (пускай и временную) полного перебора они разрулили следующим образом: вместо того, чтобы строить полное дерево возможных вариантов, они сначала просчитали все возможные варианты, когда на доске остаётся 10 и менее шашек, а потом просчитывали дерево только до этого уровня, используя уже известные оценки. Это упрощённо, а детали на 6 страницах.
Tags: pour la science
Subscribe

  • Отравление Навального

    Все уже видели фильм? Если вдруг нет — крайне рекомендую. Дальше будут спойлеры :-) Помимо очевидного (надо быть хорошим, а плохим быть —…

  • Le Monde: covid, корона Мадагаскара

    Подписался несколько месяцев назад на еженедельный дайджест и не могу нарадоваться. Читать ежедневную газету я не могу (времени нет) и не хочу (мне…

  • Invalides : Comme en 40

    Сходил на  выставку про 1940 год в Инвалидах. Достаточно мрачная, как заметил igparis, выставка, но я не увидел там излишнего нагнетания…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 17 comments

  • Отравление Навального

    Все уже видели фильм? Если вдруг нет — крайне рекомендую. Дальше будут спойлеры :-) Помимо очевидного (надо быть хорошим, а плохим быть —…

  • Le Monde: covid, корона Мадагаскара

    Подписался несколько месяцев назад на еженедельный дайджест и не могу нарадоваться. Читать ежедневную газету я не могу (времени нет) и не хочу (мне…

  • Invalides : Comme en 40

    Сходил на  выставку про 1940 год в Инвалидах. Достаточно мрачная, как заметил igparis, выставка, но я не увидел там излишнего нагнетания…