новой миниатюрной версии радиолампы[484]. Спустя два года Александр Дуглас создал OXO — реализацию крестиков-ноликов для компьютера EDSAC (Electronic Delay Storage Automatic Calculator) с графическим выводом на 6-дюймовую электронно-лучевую трубку. OXO стала, по всей видимости, первой игрой, разработанной для компьютера общего назначения[485].

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

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

В 1960 г. Дональд Мичи разработал программу, получившую название «Спичечнокоробочный обучающийся движок для крестиков-ноликов» (Matchbox Educable Noughts And Crosses Engine, MENACE; слово menace по-английски значит «угроза»). Эта программа была способна обучиться идеальной игре в крестики-нолики и для своего выполнения не требовала такого дефицитного ресурса, как компьютер. Вместо него Мичи использовал набор из трёх сотен спичечных коробков, каждый из которых соответствовал уникальному состоянию доски. Спичечные коробки были заполнены цветными бусинками, соответствующими отдельным ходам. Количество шариков каждого цвета указывало на «уверенность» в том, что соответствующий ход является наилучшим. В зависимости от результата каждой сыгранной партии производилось изменение количества бусинок в коробках, соответствующих возникшим в игре позициям, в результате чего программа постепенно всё более уверенно выбирала правильные ходы[486]. В статье Мичи, посвящённой MENACE, впервые был введён термин «обучение с подкреплением» [reinforcement learning][487].

Простота крестиков-ноликов сделала эту игру популярным модельным объектом на заре развития электронных вычислительных машин. В наши дни анализ этой игры удобен в педагогических целях: при помощи крестиков-ноликов удобно иллюстрировать многие положения классической теории игр, а создание программы, способной играть в эту игру, — неплохое упражнение для начинающих разработчиков систем искусственного интеллекта.

3.3 Играть на уровне бога: от Цермело до «Ломоносова» (первое отступление)

Двух операторов била нервная дрожь. Тысячелетия ожидания прошли не впустую.

— Он действительно существует? — выдохнул Хвуудт.

— Он действительно существует, — подтвердил Глубокомысленный.

— Главный Ответ? На Главный Вопрос Жизни, Вселенной, и Всего Такого?

— Да.

Обоих обучали и специально готовили к этому моменту, вся их жизнь была подготовкой к нему, они ещё при рождении были выбраны, чтобы стать свидетелями Ответа, и всё равно они не могли сдержать радостных восклицаний. Они хлопали друг друга по плечам, и веселились, как дети.

— И ты готов выдать его нам? — успокоившись, спросил Колнгкилл.

— Готов.

— Сейчас?

— Сейчас.

Оба оператора облизали сухие губы.

— Хотя я не думаю, — добавил компьютер, — что он вам понравится.

— Неважно! — сказал Хвуудт. — Мы должны знать его! Сейчас же!

— Сейчас? — переспросил Глубокомысленный.

— Да! Сейчас!

— Отлично, — сказал компьютер и снова погрузился в молчание. Хвуудт и Колнгкилл трепетали. Напряжение становилось невыносимым.

— Серьёзно, он вам не понравится, — заметил Глубокомысленный.

— Говори!

— Отлично, — сказал компьютер. — Ответ на Главный Вопрос…

— Ну…!

— Жизни, Вселенной, и Всего Такого…, — продолжал компьютер.

— Ну…!!!

— Это… — сказал Глубокомысленный и сделал многозначительную паузу.

— Ну…!!!!!!

— Сорок два, — сказал Глубокомысленный с неподражаемым спокойствием и величием.

Дуглас Адамс. Путеводитель хитч-хайкера по Галактике[488]

3.3.1 Основоположник теории игр Эрнст Цермело

Серьёзный разговор о теории игр обычно не обходится без упоминания немецкого математика Эрнста Цермело и его теоремы. Цермело в жизни сопутствовала научная удача: его именем названо сразу две теоремы, первая из них — одна из фундаментальных теорем теории множеств — называется также теоремой о полном упорядочении; вторая, доказанная в 1913 г., стала первой формальной теоремой теории игр.

В современной литературе по теории игр даются различные формулировки этой теоремы[489]. Некоторые авторы утверждают, что Цермело доказал, что шахматы являются детерминированной (т. е. лишённой элемента случайности) игрой, например: «В шахматах либо белые могут добиться форсированной победы, либо чёрные могут добиться форсированной победы, либо обе стороны могут форсировать ничью»[490], [491], [492].

Другие делают более общие утверждения, называя их теоремой Цермело, например: «В каждой конечной игре с полной информацией имеется строгое стратегическое равновесие Нэша, которое может быть найдено при помощи обратной индукции. Более того, если ни у одного из игроков нет одинаковых результатов в двух произвольных конечных узлах, то существует уникальное равновесие Нэша, которое может быть найдено таким образом»[493]. Равновесием Нэша называется ситуация, в которой ни один участник не может увеличить выигрыш, изменив свою стратегию, если другие участники своих стратегий не меняют. Авторов не смущает, что Джон Нэш родился спустя 15 лет после доказательства теоремы Цермело.

Некоторые вообще утверждают, что белые не могут проиграть: «…в конечной игре существует стратегия, следуя которой игрок, первым осуществляющий ход… может избежать поражения, но неизвестно, существует ли стратегия, следуя которой он может победить»[494].

Кроме того, многие авторы указывают, что методом доказательства, использованным Цермело, была обратная индукция, например: «Цермело использовал этот метод ещё в 1912 году для анализа шахмат. Он начинает с конца игры и затем движется к её началу. По этой причине данную технику иногда