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

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

Однако некоторые неточности в отношении древнеримской версии игры всё-таки проникли в популярную литературу. Во-первых, Овидий нигде не приводит названия игры. Название Terni Lapilli — условное и используется для обозначения игры сегодня лишь потому, что Овидий упоминает три камешка (фишки). Из-за того что у Овидия не говорится о названии игры, её часто называют просто — «игра Овидия» [474] . Во-вторых, Овидий говорит о поле для игры tabella, а не использует термин tabula lusoria, который вообще применялся обычно к столикам для азартных игр [475] . Ну и, наконец, вишенка на торте — современная реконструкция игры основана в большей мере на современных правилах похожих игр, потому что единственное, что мы знаем из Овидия: в игре следовало выстроить три фишки в ряд [476] .

474

Berlekamp E. R., Conway J. H., Guy R. K. (1983). Winning ways for your mathematical plays: Games in particular. Acad. Pr // https://books.google.ru/books?id=1PfuAAAAMAAJ

475

Lanciani R. (1892). Gambling and Cheating in Ancient Rome / The North American Review, Volume 155 // https://archive.org/details/jstor-25102412/page/n1

476

Heimann F., Schadler U. (2014). The loop within circular three men’s morris / Game Studies, Vol. 8, pp. 51–61 // https://www.researchgate.net/publication/312118169_The_loop_within_circular_three_men's_morris

Сегодня

игру, правила которой аналогичны «реконструированным правилам» Terni Lapilli, называют «трёхфишечной мельницей» [Three men’s morris], при этом в стандартную мельницу играют девятью фишками на доске из 24 полей. Только в английском у «мельницы» как минимум десять названий: nine-man morris, mill, mills, the mill game, merels, merrills, merelles, marelles, morelles и ninepenny marl.

Мюррей приводит ещё одну разновидность игры на поле 3 x 3 — в ней, после того как все фишки выставлены на доску, ходы осуществляются необязательно на соседние клетки, вместо этого фишка может быть перемещена на любую свободную клетку. Мюррей называет такой вариант игры «девять дырок» [nine holes] [477] . В Гане распространена игра под названием «ачи» (achi), она похожа на «трёхфишечную мельницу», но у каждого игрока не три фишки, а четыре [478] .

477

Murray H. J. R. (2015). A History of Chess. Skyhorse Publishing // https://books.google.ru/books?id=dNSBCgAAQBAJ

478

Bell R. C. (2012). Board and Table Games from Many Civilizations. Dover Publications // https://books.google.ru/books?id=2vvBAgAAQBAJ

Но вернёмся к обычным крестикам-ноликам. В 1799 г. игра в крестики-нолики упоминается в белом стихе английского поэта «Озёрной школы» Уильяма Вордсворта, впрочем без указания названия игры:

Каких только не знали вы забот И не чурались их! Однако ж были У вас и праздники, и торжества, И радости простые: вечерами, Собравшись у каминного огня, Как часто мы над грифельной доской Склонялись низко друг напротив друга И крестики чертили и нули В баталиях упорных — впрочем, вряд ли Их удостою описанья здесь [479] ^, [480] .

479

^* Пер. Татьяны Стамовой.

480

Стамова Т., Халтрин-Халтурина Е. (2011). Уильям Вордсворт. Прелюдия, или Становление сознания поэта. Фрагменты поэмы / Перевод Татьяны Стамовой. Вступление Елены Халтрин-Халтуриной / Иностранная литература. № 3 // http://magazines.russ.ru/inostran/2011/3/vo9.html

Первая печатная ссылка на английское название игры — noughts and crosses (nought — альтернативное слово для обозначения нуля) — появилась в 1858 г. в выпуске журнала «Записки и запросы». В статье, подписанной «A. De Morgan», обсуждается возможность исчисления шахматной игры. Автор вспоминает игру, в которую играли его однокашники и которую одни называли noughts and crosses, а другие — tit-tat-toe (это были слова победителя в игре, подобно словам «шах и мат» в шахматах) [481] . Несложно догадаться, что подпись «A. De Morgan» принадлежит уже упоминавшемуся нами шотландскому математику и логику Огастесу де Моргану, благодаря жене которого, Софии Элизабет де Морган, мы знаем подробности одного из первых визитов Ады Лавлейс к Чарльзу Бэббиджу.

481

Notes and Queries, 2nd Series Volume VI 152, Nov. 27 1858 // https://archive.org/details/notesqueries2621unse/page/434

Считается, что первая печатная ссылка на игру с названием, похожим на современное американское tic-tac-toe, — tick-tack-toe — появилась в 1884 г., но тогда это слово обозначало игру, в которую играют на грифельной доске и которая состоит из попыток с закрытыми глазами попасть карандашом

по одному из множества чисел, при этом число, на которое попал карандаш, становится числом очков в игре. Не исключено, что название tic-tac-toe происходит от названия старинной версии нардов — tick-tack. Считается также, что американское переименование noughts and crosses в tic-tac-toe произошло уже в XX в. [482] , однако, по-моему, tic-tac-toe — это простое фонетическое искажение упомянутого де Морганом tit-tat-toe.

482

Wikipedia contributors. (2020, November 6). Tic-tac-toe. In Wikipedia, The Free Encyclopedia. Retrieved 02:40, November 12, 2020, from https://en.wikipedia.org/wiki/Tic-tac-toe

Де Морган не был единственным мыслителем своего времени, задумавшимся над проблемой исчисления настольных игр. Автобиография Чарльза Бэббиджа, вышедшая в 1864 г., проливает свет на подробности проекта по строительству машины, способной играть в крестики-нолики.

Первоначально Бэббидж занимался задачей с философской точки зрения, исследуя вопрос, можно ли построить машину, способную играть в шахматы, шашки или крестики-нолики (Бэббидж использовал термин tit-tat-to). Сделав вывод о том, что это возможно, Бэббидж разработал алгоритм перебора всех возможных вариантов, с помощью которого машина могла бы выбирать наилучшие ходы. Кроме того, он пришёл к выводу, что его аналитическая машина вполне способна выполнять все необходимые для этого действия: «Весь вопрос о создании автомата, способного играть в любую игру, зависит от способности машины представлять все мириады комбинаций, связанных с ней. Допустив по сто ходов каждой из сторон в самой длинной партии в шахматы, я обнаружил, что число возможных комбинаций в аналитической машине во много раз превосходит все необходимые требования».

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

Записи Бэббиджа об автомате для игры в крестики-нолики датируются с 25 сентября 1844 г. по 24 октября 1868 г., причём большая часть работы над механизмами системы и алгоритмами принятия решений была завершена к концу 1848 г. Алгоритм поиска выигрышных ходов был полностью завершён к октябрю 1860 г. [483] Однако реальная машина, способная играть в крестики-нолики, появилась лишь спустя почти сто лет — в 1950 г. Джозеф Кейтс создал для Канадской национальной выставки в Торонто «Берти Мозг» (Bertie the Brain) — машину четырёхметровой высоты, имевшую несколько уровней сложности и призванную продемонстрировать возможности аддитрона (additron) — новой миниатюрной версии радиолампы [484] . Спустя два года Александр Дуглас создал OXO — реализацию крестиков-ноликов для компьютера EDSAC (Electronic Delay Storage Automatic Calculator) с графическим выводом на 6-дюймовую электронно-лучевую трубку. OXO стала, по всей видимости, первой игрой, разработанной для компьютера общего назначения [485] .

483

Monnens D. (2013). “I commenced an examination of a game called 'tit-tat-to'”: Charles Babbage and the “First” Computer Game / DiGRA Conference 2013 // http://www.digra.org/wp-content/uploads/digital-library/paper_436.pdf

484

Bateman C. (2014). Meet Bertie the Brain, the world’s first arcade game, built in Toronto / Spacing Toronto, August 13 // http://spacing.ca/toronto/2014/08/13/meet-bertie-brain-worlds-first-arcade-game-built-toronto/

485

Wolf M. J. P. (2012). Encyclopedia of Video Games: The Culture, Technology, and Art of Gaming. Greenwood Publishing Group // https://books.google.ru/books?id=deBFx7QAwsQC

С вычислительной точки зрения крестики-нолики представляют собой довольно простую задачу. Несложно прикинуть количество возможных позиций в игре: каждое из полей доски, состоящей из девяти клеток, может быть пустым либо содержать крестик или нолик. Таким образом, у нас есть девять полей, для каждого из которых существует три возможных состояния, следовательно, общее число позиций составляет 3⁹ = 19 683. Однако данное число включает в себя множество невозможных позиций, например позицию с пятью крестиками и без единого нолика. Более точный подсчёт позволяет сократить это число до 5478, а с учётом идентичности всех возможных поворотов и отражений остаётся лишь 765 действительно различных позиций.

Простая оценка верхней границы количества различных партий даёт нам 9! = 362 880 (первый ход можно сделать на одну из девяти свободных клеток, второй — на одну из оставшихся восьми и т. д.). Это число включает в себя некорректные игры, в которых ходы продолжались уже после победы одной из сторон. За вычетом таких ситуаций игр остаётся 255 168, а удаляя отражения и повороты, получаем всего 26 830 возможных партий. Даже для ранних ламповых компьютеров полный перебор такого количества вариантов не представлял большой сложности, то есть машина могла рассмотреть в любой позиции все возможные варианты продолжения игры и выбрать ход, который обеспечивает наилучший для машины результат даже при идеальной игре противника.