Охота на электроовец. Большая книга искусственного интеллекта

Марков Сергей Николаевич

В настоящее время существует два альтернативных набора эндшпильных таблиц для всех семифигурных окончаний (Lomonosov и Syzygy), база данных семифигурных эндшпилей в формате Syzygy занимает 17 терабайт дискового пространства.

Для восьмифигурных окончаний по состоянию на сентябрь 2023 г. просчитаны позиции без пешек и с блокирующими друг друга пешками разных цветов [531] ^, [532] .

531

Bourzutschky M., Kryukov K. (2022). All about chess endgames study // https://www.arves.org/arves/index.php/en/endgamestudies/theory/endgame-tablebases-check-a-7-men-position?id=1509

532

Bourzutschky M., Kryukov K. (2022). All about chess endgames study // https://www.arves.org/arves/index.php/en/endgamestudies/theory/endgame-tablebases-check-a-7-men-position?id=1533

3.3.4

Виды решений: сильное, слабое, ультраслабое

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

Первый — сильное решение [strong solution]. При наличии сильного решения мы знаем (либо можем установить, затратив разумное количество ресурсов) теоретическую игровую оценку [game-theoretic value] для любой допустимой позиции игры. Под теоретической игровой оценкой обычно понимают результат игры при идеальных действиях всех игроков (для игр с элементами случайности аналогом теоретической игровой оценки будет математическое ожидание результата игры при идеальных действиях игроков, но мы сейчас не будем погружаться в анализ игр с неполной или несовершенной информацией). Зная теоретическую игровую оценку для каждой из позиций игры, игрок в любой позиции может выбирать идеальные ходы, играя тем самым «на уровне бога».

Слабое решение [weak solution], в отличие от сильного, предполагает лишь наличие стратегии (либо возможность её получить при затрате разумного количества ресурсов), позволяющей каждому из игроков, начавших игру со стартовой позиции игры, достичь результата, не уступающего теоретической игровой оценке. Поясним отличие слабого решения на примере крестиков-ноликов. Обладая слабым решением, мы знаем, какой ход нужно сделать в стартовой позиции игры. В ответ на все ответные ходы соперника мы в свою очередь знаем наши наилучшие ответы и так далее. Однако, если мы в какой-либо позиции совершим ход, отличный от того, который рекомендует нам имеющееся решение, мы окажемся в позиции, для которой у нас уже не будет информации о лучшем ходе. Если стратегия, содержащаяся в слабом решении, говорит нам ставить крестик в левый верхний угол поля, а мы вопреки этой рекомендации поставили его, например, на клетку ниже, мы необязательно проиграем партию или упустим возможный выигрыш, но мы попадём в позицию, точная оценка которой неизвестна. Таким образом, наличие слабого решения позволяет нам играть «на уровне бога» лишь в некотором подмножестве валидных позиций игры, включающем начальную игровую позицию.

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

Рис. 55. Слабое решение для игры крестики-нолики

Благодаря тому, что слабое решение для крестиков-ноликов содержит гораздо меньше позиций, чем в принципе может возникнуть в игре, его удалось изобразить на одной книжной странице. Можете сфотографировать его на камеру телефона и затем использовать в качестве шпаргалки: если будете точно следовать его рекомендациям, то никогда не проиграете в крестики-нолики, а при ошибке противника никогда не упустите победу.

Также существует понятие ультраслабого решения [ultra-weak solution], подразумевающего, что был определён результат при идеальной игре обеих сторон, однако сама последовательность ходов не определена.

Рис. 56. Типы решений

3.3.5 Гекс — игра без ничьих

Забавно, что эту игру придумали независимо друг от друга сразу два человека — Пит Хейн в Дании в 1942 г. и Джон Нэш в США в 1948 г. Пит Хейн не менее знаменит среди датчан, чем Джон Нэш среди специалистов по теории игр. Будучи прямым потомком Пита Хейна — старшего, голландского моряка и народного героя XVII в., Пит Хейн — младший приобрёл известность благодаря созданию коротких стихотворных афоризмов, которые он называл «груками» (gruk). Груки были способом, позволявшим Хейну во время фашистской оккупации Дании обходить цензуру и доносить свои мысли до других датчан в иносказательной форме.

Отец кибернетики Норберт

Винер был большим почитателем литературного таланта Хейна и так отзывался о его творчестве: «Пит Хейн — мастер эпиграммы. Его следует читать по меньшей мере на двух уровнях — внешнем и более глубоком. И в том и в другом случае они вызывают во мне восхищение. Какое богатство значительных мыслей заключено в них!» Многие строки Хейна стали крылатыми словами и поговорками. Хейн был не только талантливым литератором, но и художником, инженером и изобретателем. Когда Пит Хейн работал в Институте теоретической физики Университета Копенгагена, то именно его Нильс Бор избрал в качестве партнёра по «интеллектуальному пинг-понгу» [533] ^, [534] . Помимо других научных проблем, Хейн размышлял над знаменитой топологической проблемой четырёх красок (теорема, которая утверждает, что всякую расположенную на сфере карту можно раскрасить не более чем четырьмя разными красками так, чтобы любые две области с общим участком границы были раскрашены в разные цвета), и ему пришла в голову идея новой игры. Хейн рассказал о ней в одной из своих лекций, и через некоторое время её правила опубликовала газета Politiken. Игра быстро стала весьма популярной в Дании — гекс тогда называли «многоугольники» и играли в него на бумаге. Со временем в продаже появились специальные блокноты для игры с напечатанными в них изображениями игровых полей. Задачи по гексу регулярно появлялись в газете Politiken, которая назначала премии за лучшие решения. В 1950-е гг. доски для игры в гекс начала выпускать фирма Parker Brothers, тогда же игра и получила своё современное название — гекс.

533

Hicks J. (1966). Close-up / Piet Hein bestrides art and science / LIFE, Oct. 14 // https://books.google.ru/books?id=lFYEAAAAMBAJ&pg=PA64

534

Варденга Г. Л. (1997). П. Хэйн. Груки / Вопросы истории естествознания и техники. № 3 // http://vivovoco.ibmh.msk.su/VV/PAPERS/BONMOTS/GROOKS/HEIN.HTM

Поле для игры в гекс состоит из шестиугольных ячеек. Оно может быть любого размера или формы, но обычно используют поле в форме ромба размером n x n, обычно 11 x 11, 14 x 14 или 19 x 19. Нэш считал наилучшим размером 14 x 14.

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

Две противоположные стороны поля окрашены в красный и синий цвета и называются красной и синей сторонами соответственно. Ячейки в углах поля являются общими. Чтобы выиграть, игрок должен выстроить цепочку из своих фишек, соединив ею стороны своего цвета, то есть красные стремятся построить цепь из красных фишек между двумя красными сторонами доски, а синие — цепь из синих фишек, соединяющую синие стороны [535] .

535

Toft H. (2019). Hex, Inside and Out: The Full Story. CRC Press // https://doi.org/10.1201/9780429031960

Рис. 57. Пример игры в гекс

В отношении гекса авторы статьи в русской «Википедии» утверждают следующее: «Нетрудно заметить, что игра никогда не кончается вничью». Это утверждение напоминает мне анекдот про Лившица и Ландау, в котором первый заливает чаем сорок страниц доказательства, а второй советует заменить эти сорок страниц словами «очевидно, что…».

Джон Нэш был первым, кто указал (примерно в 1949 г.), что гекс не может закончиться ничьей. Это утверждение в разговорной речи иногда называют теоремой гекса. В наши дни известно, что теорема гекса эквивалентна теореме Брауэра о неподвижной точке. Рассуждения Нэша, однако, не были опубликованы в научной прессе, они содержатся во внутреннем техническом отчёте RAND Corporation, подготовленном в 1952 г. Дословно Нэш пишет в нём следующее: «Природа игры такова, что если всё игровое поле заполнено фишками, то либо белые совершили соединение, либо чёрные сделали это (Нэш использовал эти два цвета для фишек играющих сторон. — С. М.). Соединение и блокирование противника являются эквивалентными действиями» [536] . Формальное доказательство было опубликовано Дэвидом Гейлом в 1979 г., то есть более чем через тридцать лет после изобретения игры. На самом деле оно совершенно нетривиальное и содержит десять шагов рассуждения:

536

Nash J. (1952). Rand Corp. technical report D-1164: Some Games and Machines for Playing Them // https://www.rand.org/content/dam/rand/pubs/documents/2015/D1164.pdf