Охота на электроовец. Большая книга искусственного интеллекта - Марков Сергей Николаевич

5. Аналогично путь не может заканчиваться и на краях поля, поскольку края игрового поля считаются граничащими со сплошной стеной из шестиугольников с соответствующими стороне отметками (X или 0).

6. Таким образом, путь может закончиться только в другом углу.

7. Согласно построению пути, с одной его стороны будет непрерывная цепочка из шестиугольников с отметкой X, а с другой — цепочка из шестиугольников с отметкой 0.

8. Из предыдущего следует, что путь не может закончиться в углу, противоположном начальному, потому что в нём метки X и 0 находятся на иных сторонах пути, чем в исходном углу. Таким образом, путь может соединять только смежные углы (принадлежащие одной стороне).

9. Поскольку путь соединяет смежные углы, сторона игрового поля между этими углами (скажем, сторона X) отрезана от остальной части игрового поля непрерывной цепью противоположных отметок (в данном случае 0). Эта неразрывная цепь обязательно соединяет две другие стороны, прилегающие к углам.

10. Таким образом, на полностью заполненном поле для игры в гекс должен быть победитель.

Итак, геометрия гекса не позволяет ни одному из игроков рассчитывать на ничью, следовательно, при идеальной игре сторон у гекса должен быть победитель [537]. В своём отчёте 1952 г. Нэш приводит любопытное соображение: «В гексе, — пишет он, — наличие лишней фишки на игровом поле никогда не может быть недостатком. Это в корне отличается от ситуации в шахматах или го, в которых наличие фигуры или камня на определённом участке доски может быть помехой». Из этого Нэш делает вывод, что у игрока, ходящего вторым, не может быть выигрышной стратегии и что, следовательно, при идеальной игре обеих сторон игра является выигранной для первого игрока. Однако Нэш отмечает, что, по всей видимости, у первого игрока нет простой стратегии победы [538]. И действительно, до сих пор придумать какое-либо простое правило для первого игрока, позволяющее ему выигрывать в гекс с гарантией, не удалось. В настоящее время найдено слабое решение для игры в гекс лишь на поле 9 × 9, хотя благодаря доказательству Нэша мы знаем, что игра является теоретически выигранной первым игроком для любого размера поля. Таким образом, для гекса с произвольным размером поля мы обладаем ультраслабым решением.

Иногда ультраслабым образом не может быть установлена точная теоретическая игровая оценка стартовой позиции, но может быть установлено её ограничение сверху или снизу. Например, в некоторых играх вторая сторона может повторять ходы противника, что гарантирует ей ничью. Для таких игр можно сказать, что их стартовая позиция точно не является выигрышной для первой стороны. Этот логический трюк называют обычно «воровством стратегии».

3.3.6 Решения разных игр

Для многих более простых игр слабые (а иногда даже сильные) решения обнаружились без привлечения машин. Например, для игры «магараджа» (или «магараджа и сипаи»), где чёрные имеют набор обычных шахматных фигур, а белые — единственную фигуру «магараджа», способную ходить и как ферзь, и как конь, было доказано, что при правильной игре чёрным гарантирована победа. Ещё до появления компьютеров люди смогли решить и ним, и крестики-нолики, однако последние достижения в области решения игр людям без помощи машин были бы явно не под силу. Например, 29 апреля 2007 г. команда исследователей из Университета Альберты (Канада) под руководством Джонатана Шеффера смогла достичь слабого решения для английских шашек, по правилам которых шашки не бьют назад, а дамки могут ходить лишь на соседние по диагонали поля, но в любую сторону.

Английские шашки — самая большая из игр, решённых до настоящего времени. Размер её поискового пространства (т. е. количество легальных позиций) — примерно 5 × 10²⁰. Для того чтобы найти решение, в течение 18 лет сеть персональных компьютеров (в разное время от 50 до 200) произвела 10¹⁴ вычислений.

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

Последней решённой игрой на данный момент стала пентаго. В отличие от шахмат и го поисковое пространство этой игры небольшое, что позволяет современному компьютеру играть идеально: с учётом всех возможных симметрий количество возможных позиций в пентаго составляет 3 009 081 623 421 558. В течение нескольких часов суперкомпьютер Edison семейства Cray, находящийся в Национальном научно-вычислительном центре энергетических исследований (NERSC), используя для вычислений целых 98 304 потока, нашёл сильное решение игры.

3.4 Шашки

Шашки — одна из самых древних настольных игр, известная человечеству с незапамятных времён. Археологические находки в Уре, одном из древнейших шумерских городов-государств древнего Южного Междуречья (Месопотамии), подтверждают существование ранней формы этой игры уже в III тысячелетии до н. э. [539] Аналог этой игры существовал и у древних египтян: найдены папирусы с изображением играющих людей, а также сами комплекты для игры.

Многочисленные упоминания игр, напоминающих шашки, встречаются у древнегреческих авторов. В гомеровской «Одиссее» женихи Пенелопы играют в «пессои» (πεσσοί) — вариант шашек, по преданию изобретённый Паламедом (Παλαμήδης) [540]. В других античных источниках эта игра (или подобные ей) упоминается под названиями «пять линий» (πέντε γραμμαί), «полеис» (πόλεις) и «псефои» (ψῆφοι). В качестве обобщающего названия различных видов игры в шашки древние греки использовали термин «петейя» (πεττεία) [541]. Платон в диалоге «Федр» указывает на древнеегипетское происхождение шашек и говорит, что их изобретение приписывается богу Тевту (по всей видимости, Тоту) [542].

В Древнем Риме наследником этой игры стала игра под названием ludus latrunculorum, latrunculi или попросту latrones. Её название образовано от слова latro, которое обозначает разбойника или солдата-наёмника. Арабский вариант шашек с доской размером 5 × 5 клеток назывался «киркат» (القرقات). В Испании эту игру стали называть «алькерк» (alquerque), под этим названием она известна и поныне [543]. Правила многих древних игр шашечного типа не сохранились до наших дней, а если и известны, то обычно существенно отличаются от современных шашек. Да и сами эти игры часто существовали в нескольких вариантах. Например, в латрункули, по всей видимости, могли играть на досках размером 7 × 8, 8 × 8, 9 × 10, 8 × 11 и даже 8 × 12 (по крайней мере, археологи обнаруживали поля для игры таких размеров) [544]. Даже сегодня существуют русские, английские, испанские, итальянские, португальские, чешские, французские, турецкие, армянские шашки — и ещё множество других вариантов этой игры. В некоторых современных разновидностях шашек используются доски размером 8 × 8, 10 × 10 и даже 10 × 8.