Логические игры

Вторая серия о многолетней борьбе Каспарова с армадой терминаторов. Первую статью из цикла читайте здесь.

Шахматные программы считали с каждым годом всё быстрее и всё адекватнее оценивали позиции, в том числе и не изобилующими тактическими ударами. Алгоритмы совершенствовались и боты достигли успехов, выигрывая не только в комбинационном, но и в позиционном ключе. Компьютерные игроки почти излечились от жадности и если люди жертвовали материал, то роботы, ради восстановления игрового баланса, троянских коней с легким сердцем отправляли обратно.

Участие компьютеров в человеческих соревнованиях вошло в моду. IT-компании охотно и щедро спонсировали мероприятия, с непременным условием – роботы играют на тех же правах, что и люди. Особенно интересен 1994 год, в которых произошли несколько знаковых событий, когда внезапно компьютеры начали регулярно наносить людям чувствительные поражения.

История о нашумевшем противостоянии Каспарова с детищем IBM уже затрагивалась на GeekTimes Хабре. Мой комментарий хоть и набрал приличное количество плюсов, содержит несколько существенных неточностей, которые я уже исправить, увы, не в силах. Дабы внести ясность и расставить все точки над ё, было решено написать более подробную статью про этот знаковый матч. Однако в творческом процессе выяснилось, что затронутая тема гораздо обширнее, многограннее и интереснее, и охватывает куда больший период времени. А посему статья про матч 1997 года органично трансформировалась в серию публикаций о незаурядных победах и поражениях 13-го чемпиона мира в борьбе с искусственным разумом на протяжении 15 лет.

         Если используешь их в битве, но победа долго не приходит, их оружие притупляется, а рвение — ослабевает. Если осаждаешь города, их силы истощаются. Если подвергаешь войско длительной войне, запасов государства не хватит.
…
         Поэтому я слышал об успехе быстрых военных походов, и не слышал об успехе затяжных. Ни одно государство не извлекло выгоды из длительной войны.

Сунь Цзы "Искусство войны"
 
В предыдущей статье, я рассказал о том как выполняется захват камней в го, но не упомянул об одном правиле. Правило это столь важное, что имеет собственное имя — Ко.

Тридцать спиц соединяются в одной ступице, [образуя колесо],
но употребление колеса зависит от пустоты между [спицами].
Из глины делают сосуды, но употребление сосудов зависит от пустоты.
Пробивают двери и окна, чтобы сделать дом,
но пользование домом зависит от пустоты в нем.
Вот почему полезность чего-либо имеющегося зависит от пустоты.

Лао Цзы "Дао дэ Цзин"
 

Камни в Го одинаковы и после установки на доску их нельзя двигать. Кажется, что это простая игра, но это не так. Простые правила ведут к невообразимому разнообразию тактических комбинаций. Проблематика «жизни и смерти» — хорошая тому иллюстрация.

На написание этого обзора натолкнул пост «Секрет древней игры го. Почему компьютер до сих пор не обыграл человека?», опубликованный 25 мая. В самом посте, и, тем более, в комментариях, было много сказано по поводу компьютерных шахмат вообще и матча Deep Blue — Каспаров (1997) в частности. Понятно, что сейчас, спустя уже без малого двадцать лет, мало кому интересны все подробности того матча: компьютеры развиваются с колоссальной скоростью, современные смартфоны легко дадут фору компьютерам того времени, да и возможно, сами шахматы несколько утратили популярность последнее время — по каким причинам — это уже тема отдельного разговора.

Впрочем, некоторые подробности, судя по всему, действительно неизвестны, а подробности эти таковы, что заголовки о “падении последнего интеллектуального бастиона” — не более, чем газетный прием, ибо случившийся по итогам матча, по сути, скандал, в силу своей шахматной специфичности вряд ли был бы интересен широкой публике. Нет, я, несмотря на то, что всегда являлся поклонником Гарри Кимовича Каспарова (исключительно в шахматном плане), не собираюсь его оправдывать за то поражение и пытаться доказать, что все было совсем не так, как сейчас общеизвестно. И уж тем более целью не является опровержение некоторых комментариев на шахматную тему к посту хабраюзера alizar. Единственная цель — рассказать некоторые подробности того, что именно произошло в Нью-Йорке в начале мая 1997 года, и почему результат этого противостояния, по мнению автора, на самом деле никому ничего не доказал.

Чемпион мира по шахматам, юный Магнус Карлсен сыграл с Биллом Гейтсом в суперблиц в эфире скандинавского телеканала NRK и поставил ему мат девятым ходом.

Многие знакомы с проектом Seti@home: мощнейшей инициативой по поиску следов внеземных цивилизаций в океане данных, получаемых с неба, с использованием мощностей миллионов компьютеров по всему земному шару («матрицы»).

Хотя инопланетян до сих пор не обнаружили, Seti@home вполне успешно демонстрирует потенциал крупномасштабных распределенных вычислений. Проекты типа BOINC распространили подобные инициативы в другие области: биологию, медицину и физику.

К сожалению, для шахмат пока нет лучших алгоритмов, чем перебор очень многих позиций. Правда, перебор порядком (и не одним) оптимизированный, но все же это большой перебор. Для поиска ответного хода строится дерево с исходным ходом в корне, ребрами — ходами-ответами и узлами — новыми позициями.



Как в элементарных алгоритмах выбирается следующий ход объяснить просто. На своем ходе вы выбираете такой ход (по вашему мнению), который принесет наибольшую пользу (максимизирует вашу выгоду), а противник на очередном своем ходе старается выбрать ход, который принесет ему больше всего пользы (максимизирует его выгоду и минимизирует вашу). Алгоритм с таким принципом называется минимакс. На каждом этапе вы присваиваете каждому узлу в дереве оценку позиции (об этом потом) и на своем ходе ее максимизируете, а на ходе противника — минимизируете. Алгоритм во время работы должен пройти по всем узлам дерева (то есть по всем возможный игровым позициям в игре), то есть совсем непригоден по времени.
Следующее его усовершенствование — альфа-бета отсечение (метод веток и границ).

Спустя более чем 25 лет после своего создания тетрис остаётся самой популярной мобильной игрой в истории. Гениальное российское изобретение продолжает покорять мир, а недавно количество мобильных загрузок тетриса превысило 100 млн (имеются в виду только платные загрузки, за которые были уплачены роялти правообладателям).

В настоящее время права на продажу самой успешной игры принадлежат корпорации Electronic Arts. Лицензию она получила у компании Blue Planet Software. Сегодня эти две фирмы планируют организовать в Монреале (Канада) торжественное мероприятие, посвящённое юбилею.

Фишка набора «Шахматы для Теслы» – то что играть надо настоящими вакуумными лампами. Дизайнер – Paul Fryer, год разработки – 2008, размеры доски – 17x48x50cm. Всего сделано семь комплектов, поэтому купить набор, к сожалению, почти невозможно.

Интереснейшую реализацию шахматной программы показали вчера на Хабре.
Почитав комментарии, я пришел к выводу, что принцип работы наиболее распространенных алгоритмов игры в шахматы, шашки и тому подобные известны не всем.

Вместе с тем задача создания программы, играющей во что-то, достаточно тривиальна, если имеются способы расчета некоторых величин и оценок, специфичных именно для этой игры.

Клик на картинку:

Знаете ли вы, что в Google Spreadsheets при одновременной работе нескольких человек над одним документом изменения синхронизируются так быстро, что можно вполне комфортно играть в крестики нолики через интернет?