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

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

на обложку

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

Шрифт:

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

540

Гомер. Одиссея // http://data.perseus.org/citations/urn:cts:greekLit:tlg0012.tlg002.perseus-grc1:1.80-1.124

541

Peck H. T. (1898). Harpers Dictionary of Classical Antiquities // http://www.perseus.tufts.edu/hopper/text?doc=Perseus:text:1999.04.0062:id=latrunculi-harpers

542

Сократ. Федр //http://psylib.org.ua/books/plato01/21fedr.htm

В Древнем Риме наследником этой

игры стала игра под названием 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.

543

Westerveld G. (2013). The History of Alquerque-12. Spain and France. Volume I. Lulu.com // https://books.google.ru/books?id=Bp0pBgAAQBAJ

544

Neto J. P. (2016). Latrunculi / The World of Abstract Games // https://www.di.fc.ul.pt/~jpn/gv/latrunculi.htm

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

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

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

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

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

545

Цит. по: Schaeffer J. (2013). One Jump Ahead: Challenging Human Supremacy in Checkers. Springer New York // https://books.google.ru/books?id=HKfqBwAAQBAJ

image l:href="#"/>

Рис. 59. Портрет Кристофера Стрейчи, отпечатанный при помощи компьютера,

хранящийся в Бодлианской библиотеке Оксфордского университета

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

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

546

Epstein R., Roberts G., Beber G. (2007). Parsing the Turing Test: Philosophical and Methodological Issues in the Quest for the Thinking Computer. Springer Netherlands // https://books.google.ru/books?id=aggUJL_5_oQC

Стрейчи был также одним из пионеров компьютерной музыки. В руководстве по программированию, полученному Стрейчи от Тьюринга, упоминается инструкция, позволяющая передавать импульсы на встроенный динамик компьютера. Тьюринг пишет, как, управляя паузами между импульсами, можно производить звуки разной высоты. Тьюринг рекомендует использовать эту инструкцию для оповещения оператора машины об определённых событиях [547] . Стрейчи сделал следующий шаг, научив машину исполнять несколько мелодий: британский гимн (God Save the King — дело было ещё при жизни Георга VI), Baa Baa Black Sheep и In the Mood. В 1951 г. мелодии были записаны вещательным подразделением Би-би-си. В 2016 г. исследователи из Университета Кентербери восстановили мастер-диск и загрузили записанные на него мелодии в облачный сервис Soundcloud [548] , [549] . Таким образом, мелодии, созданные Стрейчи, стали первой дошедшей до нас компьютерной музыкой. Если бы Стрейчи чуть поторопился, то, возможно, его компьютерная музыка стала бы и первым в мире образцом компьютерной музыки, но его опередил Джеффри Хилл, научивший чуть раньше австралийский

компьютер CSIR Mk1 воспроизводить «Марш полковника Боги» (Colonel Bogey March) [550] .

547

Turing A. M. (2000). Alan Turing’s Manual for the Ferranti Mk. I. Transcribed by Robert S. Thau // http://curation.cs.manchester.ac.uk/computer50/www.computer50.org/kgill/mark1/RobertTau/turing.pdf

548

Doornbusch P. (2017). MuSA 2017 Conference — Early Computer Music Experiments in Australia, England and the USA // https://www.researchgate.net/publication/319130809_MuSA_2017_Conference_-_Early_Computer_Music_Experiments_in_Australia_England_and_the_USA

549

https://soundcloud.com/musicandcomputerscience/ferranti-mark-1-computer-god-save-the-queen-baa-baa-black-sheep-in-the-mood/s-NKOm6

550

Doornbusch P. (2004). Computer Sound Synthesis in 1951: The Music of CSIRAC / Computer Music Journal, Vol. 28 // https://www.mitpressjournals.org/doi/10.1162/014892604322970616

Но, так или иначе, шашечная программа Стрейчи не просто научилась играть в шашки раньше программы Сэмюэла, но и исполняла в конце партии британский гимн [551] .

В сентябре 1966 г. текст программы Стрейчи, переписанной на изобретённом им высокоуровневом языке программирования CPL, был опубликован в специальном выпуске журнала Scientific American, посвящённом информации. В 2011 г. Питер Норвиг реализовал простой транслятор с языка CPL на Python и, устранив несколько опечаток, смог вернуть программу Стрейчи «к жизни» [552] .

551

Barron D. (2008). Pioneer Profiles — Christopher Strachey / RESURRECTION: The Bulletin of the Computer Conservation Society, Vol. 43 // http://www.cs.man.ac.uk/CCS/res/res43.htm

552

Peter Norvig (2012). Systems Analysis and Programming: Thoughts from the Attic / [email protected] // http://norvig.com/sciam/sciam.html

Если взглянуть на начальную позицию в английских шашках, легко заметить, что белые могут начать партию одним из семи возможных полуходов (полуход, по-английски ply, возможно сокращение от reply — ответ, — перемещение шашки одного из цветов, ход — два последовательных полухода за белых и за чёрных), на каждый из которых чёрные могут также ответить семью возможными ответными полуходами. Таким образом, в результате первого полухода на доске может возникнуть семь позиций, в результате двух последовательных полуходов — 49 позиций. Далее число возможных полуходов меняется, и после трёх полуходов на доске может возникнуть 302 позиции, но некоторые из них будут повторяться, поскольку возникнут в результате перестановок ходов, и уникальных позиций будет всего 216. Современные шашечные программы умеют учитывать подобные повторения, запоминая часть проанализированных позиций в оперативной памяти [553] , но в начале 1950-х оперативная память Ferranti Mark 1 позволяла хранить всего 512 чисел, по 20 бит каждое [554] , поэтому о таких изысках, как таблица перестановок, не приходилось и мечтать. С увеличением количества полуходов число их возможных цепочек растёт очень быстро: 5 полуходов — 7361 вариант (уникальных позиций — 2733), 6 полуходов — 36 768 вариантов (уникальных позиций — 9105), 7 полуходов — 179 740 вариантов (уникальных позиций — 28 123) и так далее. При 28 полуходах мы получим астрономическое число 16 377 718 018 836 900 735 вариантов [555] . Современному компьютеру, способному просматривать 10 млн вариантов в секунду, потребовалось бы на их рассмотрение почти 52 000 лет, а ведь речь идёт лишь о партиях не длиннее 14 ходов. Совершенно очевидно, что перебор необходимо каким-то образом ограничить. Программа Стрейчи способна просматривать дерево вариантов игры на фиксированное число полуходов. При этом, поскольку позиции в терминальных узлах дерева в ряде случаев ещё далеки от завершения игры, Стрейчи использовал вместо неизвестной точной оценки позиции приближённую, выбрав в качестве приближения разницу в числе своих шашек и шашек противника (дамка оценивалась в четыре шашки). Функцию, выполняющую такую приближённую оценку позиции, сегодня принято называть оценочной функцией [evaluation function]. Подчёркивая неточный, основанный на предположениях и догадках характер заложенного в них знания, подобные функции называют эвристическими (от др.-греч. ??????? — отыскиваю, открываю). Действительно, хотя позиции, в которых у одной из сторон есть преимущество в числе шашек, часто являются выигрышными для этой стороны, но из такого правила несложно найти множество исключений.

553

Schaeffer J. (2013). One Jump Ahead: Challenging Human Supremacy in Checkers. Springer New York // https://books.google.ru/books?id=HKfqBwAAQBAJ

554

Turing A. M. (2000). Alan Turing’s Manual for the Ferranti Mk. I. Transcribed by Robert S. Thau // http://curation.cs.manchester.ac.uk/computer50/www.computer50.org/kgill/mark1/RobertTau/turing.pdf

555

J. C. Bik A. (2012). Computing Deep Perft and Divide Numbers for Checkers. ICGA Journal, 35, 206–213 // https://doi.org/10.3233/ICG-2012-35403

Примечательно, что с математической точки зрения оценочная функция, выбранная Стрейчи, является полиномом: f = Mc – Mp + 4Kc – 4Kp, где Mc — число шашек машины, Mp — число шашек противника, Kc — число дамок машины, Kp — число дамок противника. Все позиции в шашках, согласно теореме Цермело, должны быть либо выигрышными, либо проигранными, либо ничейными при идеальной игре обеих сторон. В примере с крестиками-ноликами мы использовали для выигрышной позиции оценку «1», для ничейной — «0» и для проигрышной — «–1». Такая оценка очевидным образом связана с числом очков, которое игрок получит при соответствующем результате, s = (v + 1) / 2, где s — число очков, а v ? {–1, 0, 1} — оценка, которую мы использовали в крестиках-ноликах. Оценка со знаком позволяла нам легко получить значение оценки для противника, достаточно было просто поменять у оценки знак: vc = –vp, вместо того чтобы выполнять менее наглядную операцию вычитания оценки из единицы: sc = 1 – sp, но это в некоторой степени дело вкуса.