и что, следовательно, при идеальной игре обеих сторон игра является выигранной для первого игрока. Однако Нэш отмечает, что, по всей видимости, у первого игрока нет простой стратегии победы[538]. И действительно, до сих пор придумать какое-либо простое правило для первого игрока, позволяющее ему выигрывать в гекс с гарантией, не удалось. В настоящее время найдено слабое решение для игры в гекс лишь на поле 9 × 9, хотя благодаря доказательству Нэша мы знаем, что игра является теоретически выигранной первым игроком для любого размера поля. Таким образом, для гекса с произвольным размером поля мы обладаем ультраслабым решением.

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

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

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

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

Исследователям удалось найти решения для весьма внушительного списка игр, в который, в частности, входят «четыре в ряд», фанорона, вари (оваре), калах, шахматные поддавки (белые выигрывают, начиная игру ходом пешки на поле 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.

Мы будем говорить в этой главе и далее об английских шашках, известных также под названием «чекерс» [checkers], поскольку история создания программ именно для этой игры наиболее насыщена событиями. Привычные всему миру правила этой игры окончательно оформились, по всей видимости, только на излёте Средневековья. Главное отличие: в привычных нам русских шашках дамка может ходить и бить по диагонали на любое число полей, а дамка в «чекерсе» ходит только на одно поле (вперёд или назад) и бьёт только через одно поле (вперёд или назад).

3.4.1 Начало. Шашечная программа Кристофера Стрейчи

Создание первой компьютерной программы для игры в шашки часто приписывают Артуру Сэмюэлу. Однако в действительности приоритет в этой области принадлежит, по-видимому, другому программисту — Кристоферу Стрейчи, что признавал и сам Сэмюэл. Вот что он писал по этому поводу:

Стрейчи действительно заинтересовался шашками довольно рано, хотя, возможно, не в 1947 году, когда я начал работать над своей программой в Университете Иллинойса. Тем не менее Чарльз Бэббидж <…> ещё раньше предлагал использовать свою «аналитическую машину» для игры в шашки и шахматы, так что Бэббидж в любом случае опередил нас обоих. Моя первая программа для игры в шашки для компьютера Illiac Иллинойсского университета так и не была ни разу запущена, потому что Illiac существовал только на бумаге, когда я покинул этот университет, чтобы перейти на работу в IBM в 1949 году. Только в 1952 году моя