Чтение онлайн

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

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

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

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

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

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

Многочисленные упоминания игр, напоминающих шашки, встречаются у древнегреческих авторов. В гомеровской «Одиссее» женихи Пенелопы играют в «пессои» (??????) — вариант шашек, по преданию изобретённый Паламедом (?????????) [540] . В других античных источниках эта игра (или подобные ей) упоминается под названиями «пять линий» (????? ???????), «полеис» (??????) и «псефои» (?????). В качестве обобщающего названия различных видов игры в шашки древние греки использовали термин «петейя» (???????) [541] . Платон в диалоге «Федр» указывает на древнеегипетское происхождение шашек и говорит, что их изобретение приписывается богу Тевту (по всей видимости, Тоту) [542] .

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

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

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

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

Я узнал о работе Стрейчи из статьи, которую он представил в Торонто в сентябре 1952 года. Поскольку его программа в то время уже была опубликована, я должен признать своё поражение. Только в 1954 году, с появлением IBM 704, моя программа смогла продемонстрировать интересную игру. Мой вклад заключался в добавлении «обучения» в программу, и я считаю, что могу претендовать на приоритет в этом вопросе [545] .

Первая версия программы Стрейчи для прототипа британского компьютера ACE (Automatic Computing Engine) была завершена в феврале 1951 г., однако объёма оперативной памяти машины оказалось недостаточно для полноценной работы программы.

Когда Стрейчи услышал о машине Manchester Mark 1, обладавшей значительно большим объёмом памяти, он попросил у бывшего сокурсника по Кингс-колледжу Кембриджа Алана Тьюринга руководство по программированию этой машины и к октябрю 1951 г. перевёл свою программу в машинный код для Manchester Mark 1 (коммерческая версия этой машины получила название Ferranti Mark 1) — иногда эту машину называют MADM (Manchester Automatic Digital Machine, Манчестерская автоматическая цифровая машина) или даже MADAM. Летом 1952 г. программа могла «сыграть полноценную партию в шашки на разумной скорости» [546] .