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

Разгадывать кроссворды — не такая простая задача для компьютера, потому что задачи формулируются расплывчато. С другой стороны, тезаурус упрощает задачу. Пример Deep Blue показывает, что программы ИИ могут участвовать в викторинах и обыгрывать людей. Почему не сделать то же самое с кроссвордами?

Американский разработчик Мэтью Гинсберг (Matthew Ginsberg) создал программу под названием Dr Fill, которая справляется с кроссвордами гораздо лучше, чем абсолютное большинство людей, пишет New Scientist.

Игра Color Lines aka «Шарики» в особом представлении, вероятно, не нуждается: компьютер заваливает доску 9*9 шариками разных цветов, человек может перемещать их по свободным клеткам, выстраивая в ряды. Ряды от 5 и более шариков одного цвета самоуничтожаются; если это произошло после хода человека, ему начисляются очки и даётся ещё один ход; если в процессе наброса от компьютера, то очки самоуничтожаются вместе с шариками.

Игра имеет большое число клонов, от входящих в поставку Gnome и KDE до реализаций на JavaScript в 30 строк. Тем не менее, большинство реализаций не учитывает одну интересную особенность, присутствующую в оригинальной DOS-игре, и заметно влияющую на геймплей.

Опытные игроки (в компетентности которых не позволяли сомневаться их рекорды, намного большие, чем у меня) уверяли, что компьютер выбирает места для новых шариков вовсе не случайно, а так, чтобы «ломать» горизонтальные и вертикальные ряды и, как следствие, рекомендовали концентрироваться на выстраивании диагональных рядов. Понятно, что естественная реализация выбора места «взять случайное поле из свободных» безразлична к направлению рядов. Что же под капотом у DOS-реализации?

Дао рождает одно, одно рождает два,
два рождают три, а три — все вещи…

             Лао Цзы «Дао дэ Цзин»

Пусть расцветают сто цветов,
пусть соперничают сто школ.

                          Цинь Шихуанди
 
Правила Го просты, но простота заканчивается там, где начинается подсчёт очков. Есть множество действительно сложных ситуаций, логично вытекающих из очень простых правил. Я хочу рассказать о причинах, по которым не существует единой методики подсчёта очков в Го. О причинах, благодаря которым существует множество различных редакций правил этой игры.

Создатель легендарной скульптуры-загадки раскрыл ещё 5 букв зашифрованного сообщения

Главный офис Центрального разведывательного управления США расположен в Лэнгли, штат Виргиния, в 13 километрах от столицы государства. В конце 80-х при постройке нового здания образовалось пустое место, в которое решили поставить какую-нибудь инсталляцию. В 1988 году выбор пал на Джеймса Санборна.

Санборн мало что знал о шифровании данных, поэтому ему пришлось неплохо подготовиться. Помогал в этом Эд Шейдт, который как раз ушёл с поста главы криптографического центра Лэнгли. Нужно было оставить способ разгадки, а также не выдать текущие секреты ЦРУ. Поэтому Шейдт научил художника не современной криптографии, а техникам шифрования периода от конца XIX века до Второй мировой войны, методам, которые требуют наличия лишь ручки и бумаги. В отличие от них сегодняшние алгоритмы сильно опираются на вычислительные машины.

Продолжаю серию материалов о противостоянии Гарри Каспарова с компьютерами, начатую valemak. Его статьи, открывающие тему, можно почитать здесь и здесь.

Несмотря на то, что к середине 90-х шахматные программы для ПК стали непростыми соперниками для гроссмейстеров, приблизиться к уровню чемпиона мира им всё ещё не удавалось. Их шахматная сила на классических контролях времени, колебалась в районе 2300 – 2400 пунктов рейтинга, что по-прежнему было ниже уровня гроссмейстеров (от 2500), и уж тем более, ниже уровня игры Каспарова (2800). В будущем многие специалисты ожидали улучшения качества игры шахматных машин, но что же можно было сделать прямо сейчас?

Несмотря на свои небольшие детали в виде рисунков, сближающих игру с легендарным комиксом юмора для гиков xkcd, SineRider была создана не Рэнделом Манро, а Кристофером Уокером. Работы над проектом ведутся как минимум с лета этого года.

Своему созданию игра обязана часами, потраченными автором на построение графиков функций на графическом калькуляторе TI-86. SineRider написана на движке Unity, что позволяет запускать её на Windows, Linux и OS X, а также играть в неё прямо в браузере с установленными плагином Unity.

Правила предельно просты: каждый из уровней является математической задачкой, которую нужно решить заданием функции с нужным графиком. Функция задаётся от x и от переменной t, которая является временем после запуска.

Целью является съезжание на санях по уклону её графика, что потребует наличия отличного знания форм функций или выработает его в процессе игры. Два человечка на санях подчиняются базовым законам физики.

При этом нужно обойти все обозначенные области. Некоторые области нужно обходить в определённом порядке. В некоторых областях нужно стоять определённое количество секунд. Некоторые области могут двигаться.

Хороший способ провести пятничный вечер — поиграть в новую головоломку 0h h1.

Смысл простой: нужно заполнить всё игровое пространство квадратиками красного и синего цветов. При этом запрещено размещать в ряд три квадрата одного цвета.



Красный квадрат создаётся одинарным щелчком, синий — двойным щелчком.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

Толчком к написанию статьи послужила статья habrahabr.ru/blogs/algorithm/105450 автора lightcaster, который занимается (похоже это интересное хобби) тем, что интересно моей команде в проекте foxyevents.de (не сочтите за рекламу) с предложением вступить к нам в команду разработчиков. Т.к. на Хабре нет способа написать этому человеку «извне», приходится написать свою собственную интересную (надеюсь) статью.

В классических шахматах при всех их несомненных достоинствах существует один «недостаток», о котором знают (либо догадываются) даже начинающие шахматисты: игрок, имеющий белые фигуры, ходит первым, что даёт ему «преимущество» над соперником. Данное «преимущество» не является особо значительным при игре двух любителей, но становится существеннее, когда за шахматную доску садятся более опытные игроки.

Предполагая, что из базовой позиции в шахматах заведомо выигрышной стратегии (как для белых, так и для чёрных фигур) не существует, под «преимуществом» белых я подразумеваю несколько большее количество «благоприятных» вариантов развития событий для игрока, совершающего первый ход, при достаточно хорошем уровне сбалансированности шахмат, как таковых. И в целом, при «безошибочной» игре двух шахматных игроков (или игре Бога с самим собой), неминуемым результатом шахматной партии должна стать ничья. Более того, ничейная зона в шахматах является самой широкой среди распространённых настольных логических игр. Так что «преимущество» белых является относительным, и проявляется, в основном, статистически в шахматных турнирах различного уровня в виде большего числа партий, выигранных белыми, нежели партий, выигранных чёрными.

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

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

Выяснять что лучше: Mac или PC дизайнер Adam Frederick предлагает не на форумах, на за шахматной доской. Соответствующую случаю доску он уже нарисовал. Правда, сдается мне, что форма подставки указывает на то, что художник был не совсем беспристрастен.

via coroflot.com