Диалоги (июнь 2003 г.)   ::   Гордон Александр

Если те же самые методы применить к общему бэкгеммону, то есть добавить этот кубик, то выиграем и у всех оставшихся, мы просто ещё не успели это сделать.

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

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

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

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

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

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

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

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

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

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

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

Б.М. Да.

А.Р. Здесь некоторые нюансы всё же есть – как раз с этими статическими оценками. Глядя на позицию, например, можно сказать, что вот в этой позиции мы гарантированно выиграем столько-то и столько-то.