Решение настольных игр

,

в

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

Простейшие игры имеют математическое решение. Для более сложных игр используются компьютерные программы. Грубый просчет – все возможные позиции просчитываются до окончательного результата. Очевидно, что, имея такую базу, компьютер будет непобедим. Для некоторых игр количество таких позиций превышает физические возможности хранения результатов. Следующий шаг – уменьшение количества позиций для расчета: нелегальные позиции исключаются, само собой, сразу (например, в шахматах – короли на соседних клетках, при этом позиции, с однопольными слонами исключать нельзя – они могут появиться в результате превращений пешек, и т.д.). Отбрасываются также позиции с заведомо известным результатом, например, с большим материальным перевесом. Этот момент является спорным, поскольку такой перевес далеко не всегда гарантирует победу. Правильная оценка позволяет уменьшить количество перебираемых вариантов.

Большой шаг вперед – использования опыта «белковых» игроков. Дебютные и эндшпильные базы, наработанные за многие годы, дополняются собственными расчетами. И, конечно, в программе закладываются элементы стратегии, формализация которой – задача нетривиальная, для решения которой привлекаются «белковые» игроки.

Решение интеллектуальных игр может быть разного уровня:

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

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

Что будет, если игра будет полностью просчитана? Будет она забыта или останется популярной? Или будут вводиться новые правила, влияющие на результат просчета?

Просчитанные игры

Крестики-нолики 3*3 и 4*4

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

Шашки «чекерс» 8*8

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

Частично просчитанные игры

Отелло-реверси

На досках 4*4 и 6*6 второй игрок форсированно выигрывает. На стандартной доске 8*8 решение пока не получено, но наиболее вероятен ничейный исход партии. Стратегии игры хорошо разработаны и легко формализуются. Компьютерные программы достигли высокого уровня, в 1997 году Logistello «всухую» обыграла чемпиона мира со счетом 6:0.

Шахматы

Компьютерные программы достигли уровня топовых игроков. Тем не менее, полностью игра не просчитана – слишком разветвленное дерево игры, слишком много возможных позиций. Преимущество первого хода не доказано, хотя общепринятая тенденция – играть белыми на выигрыш, черными – на ничью. Ничейная зона – широкая, эндшпильная теория просчитана: до 6-фигурных эндшпилей полностью, 7-фигурные – частично. Дебютная база, наработанная «белковыми» игроками, также активно используется и дополняется.

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

Международные шашки 10*10

В этом варианте шашек решение пока не получено, число возможных вариантов достаточно велико – этой игре компьютерная смерть в ближайшем будущем не грозит. Просчитаны эндшпили: от 2 до 7 шашек – полностью, 8-шашечные – частично, используются дебютные базы, наработанные людьми. Уровень программ довольно высокий, но не сравнимый с лучшими игроками – это объясняется, видимо, низкой популярностью шашек в целом.

Непросчитанные игры

Рэндзю

При игре в крестики-нолики на бесконечном поле до построения ряда из 5 камней – гомоку – начинающий игру имеет преимущество. Основная стратегия для выигрыша – построение вилок, защищающаяся сторона должна блокировать цепочки из трех камней. В рэндзю введены ограничения для снятия форсированности выигрыша: запрет черным строить вилки 3*3 и 4*4 и ряд из 6 и более камней, вилки кратностью более двух, для белых запретов нет. Игрок может пасовать – пропускать ход, если пасуют оба – объявляется ничья. Ограничения привели к усложнению игры, появились новые тактические тонкости, однако и этого оказалось недостаточно: на крупных турнирах применяют дебютный регламент, принятый Международной федерацией рэндзю. Изменения в правилах вводились не на основании компьютерного анализа, а эмпирически – на основе статистики турниров профессионалов. Программ, играющих на уровне топовых игроков, в рэндзю пока нет. Основная сложность – формализация стратегии, в этом рэндзю схожа с го.

Коннект6

Коннект6 – модификация игры гомоку: начиная со второго хода игроки выкладывают по два камня вместо одного, побеждает выставивший шесть или более камней в ряд. Игра возникла совсем недавно —  в 2003 году. Размер дерева игры превышает шахматный, в игре нет преимущества первого хода, сложность анализа не позволяет пока ее просчитать.

Для варианта коннект4 получено сильное решение, слабое решение существует для досок с суммой измерений не выше 15.

Сёги

По сравнению с европейскими шахматами, в сёги:

  • размеры доски больше – 9*9;
  • фигур больше – 42;
  • видов фигур -6, с учетом превращений – 14;
  • есть десантирование – сбитые фигуры возвращаются на доску.

В сёги очень редки ничьи – не более трех процентов. Статистика игр профессионалов показывает, что в сёги нет преимущества первого хода. Количество позиций значительно превышает таковое в шахматах (10 в 220 степени против 10 в 120), при этом процент легальных позиций значительно выше.

Материальный перевес в сёги не является ключевым, размены не упрощают игру, а обостряют ее, поскольку мобильность сбитых фигур возрастает благодаря десантированию. Оценка стоимости материала не имеет смысла – она меняется в процессе игры. Это так же увеличивает количество легальных позиций, которые в обычных шахматах можно было бы отбросить на основании подавляющего материального перевеса. В сёги появляется понятие «формы» защитных построений. Вместо двух рокировок в обычных шахматах в сёги разработана целая теория крепостей, включающая около полусотни вариантов. Форма в сеги – это статический фактор, на котором основываются стратегические оценки и принятие решений.

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

Го: ничья – это гармония

Для го на доске 4*4 существует сильное решение, для доски 5*5 есть слабое решение для всех начальных ходов. Игра на доске 19*19 на данный момент не просчитана, и, видимо, в обозримом будущем ей это не грозит. Компьютеры играют лишь на любительском уровне.

В го есть коми – компенсация за право первого хода, по логике, его наличие гарантирует ничейный исход при идеальной игре сторон. Дробное коми, применяемое в турнирах, гарантирует отсутствие ничейного результата. Эта величина определена эмпирически на основе опыта профессионалов. Использование целочисленного коми позволяет играть вничью, но количество ничейных исходов все равно очень мало. Дебютная база не имеет смысла, от ее наличия практически ничего не зависит. Количество возможных позиций таково, что просчитать их перебором на данный момент физически невозможно. Стратегию игры го очень трудно формализовать, игра иррациональна. Правильная оценка позиции сложна, требует высокого уровня игры.

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

Что будет, если го просчитают полностью?

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

Ничейная смерть и «решение» не приводят к гибели игры

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

Для решения проблемы прослеживаются некоторые тенденции:

Спортивный результат – это не единственная цель интеллектуальных игр. Сама по себе ничья при игре равных по силе игроков – вполне естественна. Логика и гибкость ума, гармония, красивые комбинации, искусная стратегия… Даже если в результате – ничья, игра приносит удовольствие игрокам, в том числе и от общения. Творческая составляющая компьютерам пока недоступна.

Даже полностью решенные игры продолжают существовать и находят своих поклонников. Кто в детстве не играл в крестики-нолики? Такие игры – этапы в развитии, развивающие логику и готовящие к более сложным играм.

 

Елена Кудрявцева, специально для GAMBITER.RU, август 2009




Комментарии

Добавить комментарий