AI. Понятие игры как таковой

серьезного. Ибо серьезность стремится исключить игру, игра же с легкостью включает в себя серьезность».
Йохан Хёзинга. Homo Ludens (1938)
Йохан Хёйзинга (1872—1945) — нидерландский философ, историк, исследователь культуры, профессор Гронингенского (1905—1915) и Лейденского (1915—1940) университетов.
Человек играющий (лат. Homo Ludens) — трактат, опубликованный Хёйзингой в 1938 году. Сочинение посвящено всеобъемлющей сущности феномена игры и универсальному значению её в человеческой цивилизации.

было проиграно всего 6. В разное время операторами «автомата» были И. Альгайер, У. Льюис, А. Александр и другие сильные шахматисты.

и инженером Леонардо Торресом-и-Кеведо.

Норберт Винер и версия El Ajedrecista 1920 года на Парижском конгрессе по кибернетике (1951).

Ним, разработанную под руководством Эдварда Улера Кондона. Математическая теория игры была разработана американским математиком Чарльзом Боутоном ещё в 1901—1902 гг.

«Ниматрон» (1940)

Набор для игры в Ним

Более распространённый набор для игры в Ним

первых видеоигр. Компьютер мог играть идеальные игры против человека.

Поле для игры в «Terni Lapilli»

Ранний вариант игры был распространён в Древнем Риме примерно с I в. до н.э.

важный вклад в квантовую физику, квантовую логику, функциональный анализ, теорию множеств, информатику, экономику и другие отрасли науки.

Оскар Моргенштерн (1902—1977) — американский экономист немецкого происхождения, совместно с Джоном фон Нейманом создал математический фундамент теории игр и её применения к проблемам экономики.

в любой позиции игры.

Слабое решение (weak solution)
Идеальный ход есть только в случае, если с самого начала игры совершались идеальные ходы.

Ультра-слабое решение (ultra-weak solution)
Определение исхода игры при идеальной игре сторон. Сами ходы при этом не просчитываются.

в играх было дано в работе Р. Беллмана «О применении динамического программирования и нахождению оптимальной стратегии при игре в шахматы и в шашки» (1965).
В 1970 году Томас Штрохлейн (нем. Thomas Ströhlein) защитил докторскую диссертацию в которой анализировались такие окончание как KQK, KRK, KPK, KQKR, KRKB, и KRKN.

Ричард Эрнст Беллман (1920—1984) — американский математик, создатель метода динамического программирования.

Томас Штрохлейн (р. 1941) — немецкий математик, исследователь в области теории игр, профессор Мюнхенского технического университета.

Фигур Позиций (NULP)
2 462
3 368,079
4 125,246,598
5 25,912,594,054
6 3,787,154,440,416
7 423,836,835,667,331

за свой вклад в создание языка программирования C, операционной системы UNIX и одной из первых систем эндшпильных таблиц с Деннисом Ритчи в Bell Labs (1972).

В 2012 году были рассчитаны 7-фигурные таблицы для ситуаций распределения фигур четыре против трех и пять против двух. Авторы таблиц — В. Махнычев и В. Захаров, сотрудники ВМК МГУ. Таблицы названы таблицами Ломоносова, так как рассчитывались на суперкомпьютерах МГУ «Ломоносов» и IBM Blue Gene/P.

хода

Мат в 549 ходов

Правило 50 ходов — правило шахматной игры, согласно которому игрок, имеющий очередь хода, имеет право потребовать ничью, если на протяжении последних 50 ходов каждого игрока ни одна фигура не была взята и ни одна пешка не сделала хода.
В начале XX века А. Троицкий доказал, что в некоторых эндшпилях выигрыш достигается более, чем за 50 ходов. В связи с этим ФИДЕ в 1928 году установило правило 50 ходов с исключениями.
В 1982 году правило было конкретизировано. Число ходов увеличивалось до 100 для трёх видов окончаний.
В 1989 году правило вновь изменилось благодаря анализам, проведённым программой Кена Томпсона. Число 50 заменили на 75 (вместо 100), но уже для шести видов окончаний. Между тем компьютерный анализ эндшпиля продолжался, в результате было открыто много эндшпилей, нарушающих правило 50 ходов. В 1992 году было принято решение отменить все исключения из правила 50 ходов.
На 2014 год, рекордный вариант — 517 ходов без взятий при наилучшей игре для окончания «ферзь и конь против ладьи, слона и коня» — был найден в 2008 году.

(ИТЭФ) в 1961 году, стала одной из первых полнофункциональных шахматных программ, написанных в СССР (ещё одна шахматная программа примерно в это же время была создана в Математическом институте им. Стеклова АН СССР под руководством М. Р. Шура-Бура).
Разработка шахматной программы ИТЭФ для машины М-20 началась в 1960 году. Созданием программы занимались В. Арлазаров, Г. Адельсон-Вельский, А. Усков под общим руководством А.С. Кронрода. В 1967 году в матче из четырех партий программа ИТЭФ обыграла шахматную программу Стэнфордского университета со счётом 3—1. По оценкам профессиональных шахматистов, игравших с программой, она играла в силу третьего разряда.
В начале 1970-х годов на основе исходных текстов программы ИТЭФ началось создание новой шахматной программы, получившей название «Каисса».

Михаил Романович Шура-Бура (1918—2008) — советский и российский учёный, внёсший существенный вклад в становление и развитие программирования в СССР.

Фрагмент листинга шахматной программы ИТЭФ для ЭВМ М-20.

Института проблем управления АН СССР Георгием Адельсон-Вельским, Владимиром Арлазаровым, и Михаилом Донским. Непосредственно над программой работали А.  Битман, А. Бараев, А.  Усков, А. Леман, М.  Розенфельд. На 1-м Чемпионате мира по шахматам среди компьютерных программ в августе 1974 года в Стокгольме «Каисса» выиграла все четыре партии и стала первым чемпионом мира среди шахматных программ.

под руководством Д. Шеффера (известного как ведущего разработчика шашечной программы «Чинук» — чемпиона мира по английским шашкам) смогла достичь «слабого» решения этой игры. Английские шашки — самая большая из игр, решённых до настоящего времени. Размер её поискового пространства 5×1020. Для того, чтобы найти решение, в течение 18 лет сеть персональных компьютеров (в разное время от 50 до 200) произвела 1014 вычислений.

Джонатан Шеффер

мира по английским шашкам в 1955—1958 и 1975—1991 гг. Тинсли ни разу в жизни не проигрывал матч за первенство мира и за 45-летнюю карьеру проиграл всего семь партий. В 1990 году «Чинук» занял второе место в чемпионате США. Неофициальный матч на первенство мира состоялся в августе 1992 г. Победу со счётом 4—2 (при 33 ничьих) одержал Тинсли. В одной из игр «Чинук» совершил ошибку на 10 ходу. Тинсли отметил: «Ты будешь сожалеть об этом». «Чинук» сдался 26 ходов спустя. Позднейший анализ показал, что Тинсли выбрал единственную ведущую к победе стратегию, и что победа была отделена от момента принятия решения на 64 хода.

TECH DRAMA

участие в нём по состоянию здоровья после 6 игр (все — ничьи). Через неделю у Тинсли был диагностирован рак поджелудочной железы и через семь месяцев он скончался.
В 1995 году «Чинук» выиграл у Дона Лафферти матч на первенство мира со счётом 1—0 (при 31 ничьей). С тех пор первенство перешло к машинам.

HUMAN DRAMA

Дон Лафферти (1933—1998)

Команда разработчиков «Чинук»

Книга Д. Шеффера

с 10 по 17 февраля 1996 года. Окончательный счёт матча — 4 : 2 в пользу Каспарова. Второй матч проходил в Нью-Йорке с 3 по 11 мая 1997 года и состоял из 6 партий. Окончательный счёт матча — 3½ : 2½ в пользу Deep Blue.

Гарри Каспаров против Deep Blue (1997).

Pocket Fritz 4 на турнире  Copa Mercosur (2009).

шахматная программа занимается «тупым» перебором вариантов, и что своими успехами программы обязаны созданию более быстрых компьютеров.
В среднестатистической шахматной позиции возможно 35 ходов, следовательно для полного перебора вариантов на 1 полуход в потребуется просмотреть 35 позиций, на 2 — 1225 и т.д. (см. таблицу выше). «Каисса» была способна просматривать 200 позиций в секунду. В 1999 году программа Shredder на персональном компьютере могла просматривать примерно 20 000 позиций в секунду. Нынешний лидер рейтингов, программа Stockfish, на современном ноутбуке — около 1 млн позиций. В 1998 году суперкомпьютер Deep Blue мог позволить себе 300 млн позиций в секунду. Но даже он, используя полный перебор, должен был бы потратить около 356 лет чтобы найти решение к задаче, изображённой на диаграмме (мат в 6 ходов). Однако любая сильная современная программа находит решение на настольном компьютере менее чем за секунду. При игре на аналогичном оборудовании разница в рейтинге между чемпионом 2008 года и чемпионом 2015 года — около 300 пунктов Эло.

партий, вычисленное в 1950 году американским математиком Клодом Шенноном. Составляет приблизительно 10118. Для сравнения — количество атомов в наблюдаемой Вселенной составляет по разным оценкам от 4×1079 до 1081, то есть в 1040 раз меньше числа Шеннона.

— го-игрок китайского происхождения, гражданин Франции, трёхкратный чемпион Европы по го.

Логотип программы «AlphaGo».

Ходы 1—99 4-й партии матча с Фань Хуэем.

В течение многих лет игра в го была одним из крепких орешков для ИИ. В силу больших размеров поискового пространства и сложности позиционной оценки классические переборные алгоритмы были неспособны обеспечить программам уровень игры сопоставимый с сильными игроками-людьми.
Прорыв осуществила компания Google DeepMind (британская компания, занимающаяся искусственным интеллектом; основана в 2010 году в Лондоне под названием DeepMind Technologies, а в 2014 году приобретена Google), создавшая программу AlphaGo.
2016 год был ознаменован победой AlphaGo над сильнейшими игроками-людьми.

2.0

Графики обучения AlphaZero

чемпионате по DOTA 2 «The International 2017» компания Илона Маска Open AI презентует своего бота.
Презентация проходила в прямом эфире, против бота играл один из самых известных игроков на Dota 2-сцене, Даниил Ишутин (Dendi), который проиграл два матча из двух возможных.
Перед Даниилом с ботом играли и другие профессиональные игроки, по непроверенным данным обыграть бота, удалось всего несколько раз.
Нужно отметить, что во время игры с ботом для игроков были установлены некоторые ограничения: было запрещено покупать несколько предметов, а также использовать внутриигровые бонусы*.
* Автор выражает признательность Егору Мурашову за помощь в подготовке материала

Игровая карта

Игра против бота

Твит Маска

и смогли одержать несколько побед над командами любителей и полупрофессиональных игроков. На чемпионате The International 2018 OpenAI Five сыграли два матча против профессиональных команд (бразильской paiN Gaming, входящей в двадцатку сильнейших в мире, а также против команды Big God, состоящей из прославленных китайских игроков). Первый матч продолжался 51 минуту. Сначала боты казались дезориентированными, но к середине игры смогли превзойти людей по количеству убийств и собранного золота. Впрочем, победу всё же одержали люди: в ходе последней битвы профессионалы смогли разрушить базу противника. Игроки из Big God смогли управиться с противником за 45 минут.
Хотя боты и проиграли оба матча, представители OpenAI заявили об успехе предприятия, поскольку игра с одними из лучших игроков в Dota 2 позволит исследователям проанализировать и скорректировать алгоритмы системы на будущее.
Следующая публичная демонстрация игры OpenAI Five состоялась в апреле 2019 года, когда команда ботов выиграла серию игр «лучший из трёх» против чемпионов The International 2018, европейской команды OG, в Сан-Франциско. Игры транслировались в прямом эфире. В том же месяце было организовано четырёхдневное онлайн-мероприятие, в ходе которого все желающие могли попытать счастья в игре против ботов. В итоге из 42 729 игр, боты выиграли 38 654 (чуть более 90%).

игрок в StarCraft Сон Бён-гу (Song Byung-gu) сразился с четырьмя различными ботами и одержал убедительную победу со счётом 4-0. Один из ботов, «CherryPi», был разработан корпорацией Facebook. Другие боты созданы компаниями из Австралии, Норвегии и Кореи.
В университете Sejong С 2010 проходят соревнования по StarCraft с участием людей и машин. Мероприятие поддерживают различные организации (как коммерческого толка, так и научно-исследовательские и общественные), в частности, Institute of Electrical and Electronics Engineers (IEEE).
В августе 2017 года DeepMind и Blizzard Entertainment анонсировали инструменты по разработке ИИ, совместимые со StarCraft II.

Игра против бота

матчей, состоявшихся 19 декабря, AlphaStar решительно победил со счётом 5:0 Гжегожа «MaNa» Коминча (Grzegorz Komincz) из команды Team Liquid, одного из сильнейших профессиональных игроков StarCraft в мире. До этого AlphaStar в знаменательном матче обыграл товарища MaNa по команде Дарио «TLO» Вюнша (Dario Wünsch). Условия были такие же, как и в обычных профессиональных матчах, игроки соревновались на ладдере (competitive ladder map) и без каких-либо ограничений игры.