Диалоги (июнь 2003 г.)

А.Г. Для тех, кто знаком с правилами игры в короткие нарды, скажите, пожалуйста, в двух словах, чем отличается бэкгеммон от коротких нард.

Б.М. Самое главное отличие – то, что в бэкгеммоне добавляется ещё один кубик, удваивающий куб. Doubling dice, даблинг дайс, по-моему, называется. Его смысл вот какой. Кубик сначала лежит на единичке и в любой момент игры любой из участников может перевернуть его на двойку. И другой – либо сразу сдаётся, либо любой будущий исход игры удваивается. При этом тот, кто удваивает, уже не является хозяином кубика. Если в самом начале кубик является общим, то удвоенный кубик лежит на стороне того, который согласился – не того, который предложил удваивать, а того, который согласился. И далее можно учетверять и так далее.

И сначала, когда я впервые познакомился с этим правилом (это было 5 лет назад, когда Интернет стал широко доступен), то первая моя реакция была резко отрицательная, я даже тогда такие примеры приводил: играет, например, «Спартак» с «Динамо» (Киев), выбегает тренер Романцев и ставит на футбольное поле огромный куб с двойкой. И киевляне либо соглашаются, либо убегают с поля. Но потом я постепенно понял, что эта аналогия всё-таки плоховата, и даже не выдерживает никакой критики. Это нововведение очень сильно, в хорошем смысле, усложняет игру, то есть разные тонкости, разные нюансы даёт. Вот это основное отличие.

Но давайте ещё скажем, чтобы закончить эту минитему, про отличие нард об бэкгеммона. Я переписываюсь с разными именно нардистами, в том числе добивавшимися успеха в международных соревнованиях. И у меня возникло такое впечатление, что в последнее время ситуация в тех же программах, выставленных в Интернете, немножко другая, чем была года 3-4 назад. Там в основном выставляются программы, где хорошо развита игра на деньги. Ну, и соответственно, сайты, на которых играли умнейшие люди мира (я нисколько не шучу, таким образом действительно можно определять интеллект) – эти сайты постепенно закрываются, и появляются сайты, на которых можно в нарды поиграть, в бэкгеммон поиграть за деньги. Там тоже есть этот удваивающий куб, то есть это игры, похожие на бэкгеммон, а не на нарды…

А.Г. Всё-таки, возвращаясь к вашей программе, откуда у вас уверенность в том, что она может стать чемпионом?

Б.М. Да, эту мысль надо точнее развить. Мы в нашем советском варианте обыграли всё, что у нас было. Более того, я высылал всем желающим и продолжаю высылать демонстрационную версию, которая играется так называемым «Джели-фиш» (это широко известная программа, даже в Интернете среди нардистов обсуждается, типа «как я играл в „Джели-фиш“). И мы его обыграли, и ещё парочку программ обыграли. То есть мы берём стабильно больше 55 % очков. Если те же самые методы применить к общему бэкгеммону, то есть добавить этот кубик, то выиграем и у всех оставшихся, мы просто ещё не успели это сделать.

А.Г. Так. Теперь – что же это за методы?

Б.М. Да. Но начнём с другого конца: на чём построены абсолютно все остальные бэкгеммоновские программы, за редчайшим исключением, за исключением, может быть, самых первых программ? Там был такой Берлинер… Может быть, вы про Берлинера расскажете?

Алексей Радионов: В любых программах фигурирует такая вещь, как оценка позиции, некоторые оценочные функции. Что это такое? В конце партии уже чётко видно, кто победил, кто проиграл – по доске мы можем сказать: да, действительно, такое-то количество очков выиграл один игрок, другой, соответственно, другое. Это видно в самом конце игры. А как оценить позицию, когда мы ещё до конца игры не добрались? Здесь, как правило, программа моделирует ходы противников с той целью, чтобы одна сторона стремилась свой выигрыш увеличить, а другая сторона стремилась уменьшить выигрыш противника. Вот, собственно, метод минимакса, минимизации и максимизации идёт отсюда.

Б.М. Но это стандартное. Это ещё пока не имеет отношения к недетерминизму.

А.Р. Да. Вот на подсчёте таких чередований минимума и максимума получается оценка позиций, которые уже не конечны, где ещё не ясно, кто и что выиграл, позиций на некоторых промежуточных уровнях, где-то в середине игры. Таким образом программа может оценить своё положение и принять тот ход, который либо гарантирует ей выигрыш, либо гарантирует какой-то минимальный проигрыш, то есть не ухудшает ситуацию.

В недетерминированных же играх появляется ещё тот фактор, что мы не знаем точно, как сложится игра в дальнейшем, то есть на игру влияют некоторые не от нас зависящие причины. Это либо показания кубиков (когда мы не можем предсказать, что выпадет заранее), либо какие-то другие случайные факторы. В нашем случае этих случайных факторов, именно показаний кубиков, – конечное количество вариантов, несколько комбинаций. Мы просматриваем каждую комбинацию и смотрим, как будет развиваться игра, если у нас выпали такие-то очки или другие очки, для каждой комбинации это…

А.Г. Но это увеличивает количество вариантов в прогрессии…

А.Р. Да, там появляются дополнительные…

Б.М. И не только увеличивают количество вариантов, кроме того, непонятно, какими алгоритмами здесь пользоваться, и к этим алгоритмам существуют (я снова на Берлинера клоню) разные подходы.

Первый подход – это просто случайное моделирование нескольких ветвей позиции, более точно – нити развития игры. Всё-таки русской терминологии нету, поэтому приходится вспоминать и одновременно переводить. Это один вариант программы. Но это всё было давно, это самые первые нардовские программы, датированные примерно 80-ми, может быть, 90-м годом, но не позже. А после этого все программы – абсолютно все, я не знаю ни одного исключения среди хороших программ, кроме нашей, – написаны на так называемой нейросетевой технологии. То есть там вообще, если немножко упрощать ситуацию, фактически и нет никакого метода минимакса. А вся оценка позиции сводится к статической. Ещё раз повторю, что я немножко ситуацию упрощаю, но в целом говорю правильно.

А.Г. То есть в каждый конкретный момент позиция оценивается как единственно возможная сейчас?

Б.М. Да.

А.Р. Здесь некоторые нюансы всё же есть – как раз с этими статическими оценками. Глядя на позицию, например, можно сказать, что вот в этой позиции мы гарантированно выиграем столько-то и столько-то. Остался вопрос: как получить эту точную оценку, чтобы она была как можно более адекватна? Но построение оценочной функции с нейросетевым подходом заключается в том, что нейропрограмма, основанная на нейросети, производит огромное количество партий сама с собой, то есть происходит самообучение, настройка нейросети с той целью, чтобы значение оценки для тех позиций, которые выдаёт нейросеть, было как можно более адекватно. А мера адекватности здесь уже – это количество выигрышей.

Б.М. Сейчас я перебью опять. Этот подход и в шахматах осуществляется, хотя я не знаю, насколько успешно он применяются в Deep Thought или в более совершённых, более новых версиях этого Deep'а (я даже не выучил название последнего Deep'а). Deep Thought – это который обыграл Каспарова, а в следующих я даже не знаю, используют это или не используют. Я просто знаю, что в шахматах такой подход тоже есть.

А.Р. Собственно, всё нацелено на получение точной оценки некоторой позиции. И у нас в работе такая же цель преследуется, просто делается это несколько другими методами.

Опять же, если вернуться к нейросетевым методам, программа обучает нейросеть, исследователь это видит по специальным характеристикам, по некоторым графикам, по частоте поражений и побед. И когда считается, что нейросеть уже достаточно обучена, программе достаточно перебрать возможные количества случайных исходов, может быть, на один уровень заглянуть вниз и предусмотреть, как может пойти противник, и, предполагая, что оценка позиции якобы точная, программа уже делает ход. Вот, собственно, та программа, о которой Борис Феликсович уже говорил, «Джели-фиш», при достаточно небольшом количестве нейронов считается одной из самых сильных.