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

Программирование недетерминированных игр

Участники:

Мельников Борис Феликсович – доктор физико-математических наук, профессор.

Радионов Алексей Николаевич – кандидат технических наук.

Борис Мельников: …И книжки, выходившие в основном в 70-е годы, по программированию игр, прежде всего, посвящались шахматам. Эти книжки в основном писались коллективом авторов с Адельсон-Вельским во главе. И в чём-то альтернативно писал книжки один из чемпионов мира по шахматам Ботвинник. На основе идей Ботвинника так и не была создана программа, «Пионер» так и не заработал, в общем-то, – не то что в полную силу не заработал, а вообще не заработал. А «Каисса» Адельсона-Вельского была чемпионом мира среди шахматных компьютерных программ, по-моему, в 73-м году или в 74-м, а через три года заняла второе место.

И ещё в этих книжках были упомянуты немножко и другие игры. Но, действительно, только немного. Может быть и зря, потому что первые успехи в программировании детерминированных игр были во второй половине 60-х годов, если мне не изменяет память, в районе 67-го года, может быть немножко раньше, когда в разных национальных версиях шашек хорошая программа обыгрывала чемпиона мира. Ну, или, может быть, чемпиона своей страны по этим играм. В шахматах такое случилось только в 97-м или в 98-м, когда «Deep Thought» обыграла Каспарова, действующего чемпиона мира, и с тех пор, в общем-то, этот случай больше не повторялся. А именно – недавно с Крамником программа сыграла вничью. Причём, даже злые языки говорили, что Крамник немножко сплоховал в конце, даже чуть ли не сознательно. Но всё-таки речь не об этом.

Итак, возвращаясь к недетерминированным играм. Здесь хочется обязательно сказать, что в этих книжках, в очень хороших книжках, изданных в советское время, в 70-х, в начале 80-х годов, там про недетерминированные игры не было сказано вообще ни одного слова. А это и карточные игры, в том числе и интеллектуальные карточные игры – бридж, преферанс (прежде всего преферанс, который я считаю даже более интеллектуальным, чем бридж). И про то, чем мы занимаемся - я, наконец, перехожу к нардам - в этих книжках не было совсем. То есть, считалось, что эти игры азартные, в них играть запрещали. Я даже помню такие полуанекдотические случаи, когда за игру в карты из комсомола могли выгнать, из общежития выселить. Даже и к нардам были подобные притязания.

Александр Гордон: Конечно, кубики кидают…

Б.М. Нарды действительно воспринималась как азартная игра. Что, конечно, не правильно. Потому что для хорошей игры в нарды тоже нужно обладать интеллектом.

А.Г. Вы сейчас говорите о так называемых коротких нардах?

Б.М. Да, конечно. Давайте тоже об этом расскажу. Я незаслуженно поздно познакомился с нардами. В шахматах я уже был достаточно большим специалистом для своего возраста, а про нарды узнал из публикации в «Науке и жизни» – мне было где-то 14 лет. Там была публикация про нарды, в середине 80-х годов. И были две распространённые в России версии нард – длинные и короткие. И я достаточно быстро, хоть достаточно был молод, понял, что так называемые «длинные» нарды – это игра не очень интеллектуальная. То есть, просто игра на перетаскивание фишек в зависимости от показания кубика. Интеллект иногда надо было применять, но, по моим расчётам, в длинных нардах, чтобы из новичка получить человека, который играет наравне с чемпионом, может быть трех минут мало, как в крестиках и ноликах на доске три на три, но дня – достаточно. Чего, конечно, нельзя сказать о коротких нардах. И, тем более, о расширении этой игры, международной версии «бэкгеммон», в которой добавлено ещё несколько правил, несколько усложнений, которые эту игру делают гораздо более интересной.

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

Недавно мне попалась книжка Гика, недавно изданная, про разные игры, в которой проводится мысль, с которой совершенно не могу согласиться. Там говорится о том, что сильные игроки в бэкгеммон, в нарды, делают практически одинаковые ходы в сложных позициях, когда знают позицию, знают показания кубиков. Ну и поэтому в партиях сильных игроков побеждает тот, кому лучше придут кубики. Конечно, это так. Лучше придут кубики – это очень важно, гораздо важнее, чем в шахматах, где кубиков нет. Но, однако, те же самые сильные шахматисты в схожих позициях делают разные ходы, в этом проявляется стиль шахматиста. И нардисты, игроки в бэкгеммон, тоже делают разные ходы – тоже в зависимости от стиля. И недаром на сайтах в Интернете выставляются партии лучших игроков в мире и, в частности, их партии с компьютерами.

Но перехожу, наверное, к самому основному, то есть связанному с темой передачи. Наша группа среди прочего делает и программы по игре в бэкгеммон. Лучше даже пока сказать – в наши отечественные «короткие нарды». По материалам этих программ были статьи в журнале «Программирование».

Нужно сразу оговориться, чтобы эта тема не показалась слишком лёгкой, слишком ненужной – совершенно те же приёмы применяются нами и в нескольких задачах дискретной оптимизации. В гораздо более серьёзных задачах. Наверное, слово «серьёзные» я употребляю в кавычках, потому что самым серьёзным я считаю программирование нард. Именно там, в основном, и должен проявиться человеческий интеллект. Это гораздо более серьёзная задача, но я назову и другие задачи, которые на слуху у математиков.

Это так называемая «задача коммивояжёра». У нас есть несколько подходов к этой задаче дискретной оптимизации. Казалось бы, всё сделано, есть эвристические алгоритмы минимизации дизъюнктивных нормальных форм. Однако известные алгоритмы реально работают только для маленьких размерностей. И я ещё не всё вспомнил, но по этим темам у меня работали в разное время 3-4 дипломника-аспиранта. Вот минимизация конечных автоматов – по этому поводу у меня постоянно защищаются дипломные работы, сейчас две диссертации на выходе. А здесь применяются те же самые эвристические алгоритмы, что и в программировании игр.

Так что, основная, конечно, тема – это программирование игр, и я вернусь к программированию нард. В Интернете можно найти разные программы, играющие в бэкгеммон. И, в частности, в них во всех можно устанавливать уровень, лучше сказать не «уровень игры», а «вариант игры», который совпадает с русской версией, с более упрощённой, это короткие нарды. Но вот, к сожалению, у нас пока программы играют только в нашу отечественную версию и, причём, после публикации в журнале «Программирование» двухлетней давности, больших успехов с этого времени практически не случилось. Мы не поучаствовали в чемпионате мира по программированию летом 2002 года (хотя собираемся поучаствовать в следующем чемпионате 2004 года). Не поучаствовали по той причине, что просто не хватает времени – с совершенно теми же самыми идеями – довести программу до уровня бэкгеммон. То есть, до уровня международного стандарта, несколько более усложнённого. Но я, здесь сидя, обещаю, что в 2004 году я это сделаю. То есть, мы всех должны победить.

Почему у меня такая уверенность? Потому что всё-таки наш русский, российский (может быть, не очень хорошо говорить «русский», потому что в разных кавказских республиках бывшего Советского Союза короткие нарды распространены больше, чем в России, поэтому лучше сказать «советский» вариант игры), потому что советский вариант игры – это более простой вариант.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Б.М. Да.

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

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

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

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

Б.М. Её, правда, обыграла «Б-Г-блиц», новая программа, с которой мы хотим потягаться в следующем, 2004-м году и, в общем, уверенность есть, что в грязь лицом не ударим.

А.Г. А в чём принципиальная разница построения? Вы тоже используете систему нейросети?

Б.М. Так вот как раз и нет. Мы используем свой подход, этот подход можно, если совсем кратко, охарактеризовать таким образом. То есть почему, например, меня перестали интересовать шахматы, хотя в юности я добивался каких-то успехов? То есть я развёрнуто отвечаю на ваш вопрос. Окончательно я их забросил к 25 годам, потому что достиг своего потолка, потому что больше чем кандидатом в мастера мне было не стать. Почему? Потому что у меня гораздо хуже, чем у моих сверстников, которые стали кандидатами в мастера не в 25, скажем, а в 17 лет, работает левое «пересчетное» полушарие. Я в пересчёте вариантов совершенно слаб, несмотря на то, что до поры до времени играл с ними совершенно на равных. Это я осознал к годам к 25-ти.

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

И что-то подобное я и ввожу в свои программы. Где можно, я это пытаюсь программировать, алгоритмизировать, но не всегда это получается. То есть иногда именно в программах что-то совершенно невозможно объяснить. Именно в программах, именно в написанных текстах программы, опять же выражаясь полушутя, работает правое полушарие. Здесь что-то работает, программа работает, программа выдаёт хорошие результаты, и не только в программировании игр, но и в задачах дискретной оптимизации.

А.Г. А как, вы не знаете?

Б.М. А почему – не знаю.

А.Г. То есть вы программируете работу правого полушария правым полушарием и в результате получается хорошая программа.

Б.М. Да, да, да, так иногда оно и есть. Но кое-что всё-таки можно объяснить. И как раз это объяснение и есть предмет нескольких статей, которые мы с соавторами написали, и не только про программирование игр, но и про разные другие задачи дискретной оптимизации.

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

А.Г. Но это, извините, уже искусство.

Б.М. Может быть. Так игра в шахматы, в нарды тоже многими сравнивается с искусством.

Но сейчас, может быть, стоит перейти к тому, что алгоритмизуется работой правого полушария, и что нашло отражение в программах и для игры в нарды, и в других задачах дискретной оптимизации – это динамическая оценка позиции, даже лучше сказать, применение динамически генерируемых функций риска. Может быть, об этом вы расскажете подробнее?

А.Р. Про статические оценки я коротко уже говорил. В недетерминированных играх, благодаря этой недетерминированности, мы не знаем точно, что у нас получится, и мы перебираем всевозможные случайные исходы. Выпали у нас показания кубиков такие-то, мы получаем такой-то прогноз, следующий – следующий прогноз. Итак, мы для каждого исхода случайного события имеем какую-то коллекцию прогнозов, каких-то построенных статических оценок.

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

Б.М. Сейчас я опять перебью на секунду. Набор прогнозов можно рассматривать как вектор аргумента функций. Это не совсем правильное название, и математики могут за него поругать, но это близко к истине.

А.Р. Тем более там размерность нефиксированная получается.

Это специальное усреднение основывается на весовой функции, которая у нас называется «функция риска» и которая также подбирается специальным образом. А подбирается она так. Если у нас дела идут в гору…

Б.М. Давайте я снова вас перебью. Итак, есть у нас набор значений статической оценки позиции. И вот эти наборы значений как-то распределены, условно говоря, на отрезке от минус единицы до единицы. То есть, минус единица – самый плохой результат, единица – самый хороший, это результат, зависящий от выпадения кубиков. Ну, опять же, если снова говорить про бэкгеммон, про нарды, тут можно сказать, что у нас либо 21 вариант, если показания кубиков 5,6 и 6,5 считать одинаковыми, либо говорить, что 36 вариантов, если их считать разными, но это дело не меняет.

Главное, что некоторое количество вариантов тут распределено. И действительно, у нас могут быть и очень хорошие, и очень плохие показания кубиков. То есть в реальных партиях, в реальных оценках позиции распределение этого вектора – от минус до плюс единицы. Как усреднять? Алексей говорил, что можно среднеарифметически, но лучше не так, лучше усреднять с помощью, как он тоже начал говорить, функции риска. Что это такое. На отрезке от минус до плюс единица проводится какая-то функция, и наши аргументы получают временные значения, равные высоте столбиков ординат этой функции в нужных абсциссах. Я не очень красиво выразился, может, вы меня поправите?

А.Р. Каждому прогнозу, каждой оценке как бы приписывается свой вес.

Б.М. Равный значению этой функции риска. А абсцисса там, где она и находится.

А.Р. Потом эта система взвешивается, ищется центр тяжести.

Б.М. Центр тяжести – вот она главная оценка! То есть, то, чего мы не нашли ни в каких других программах.

Во-первых, мы применили эту оценку в задачах дискретной оптимизации. В общем-то, может быть, это отдельный разговор, причём здесь задача дискретной оптимизации. Причём, например, здесь так называемая «задача коммивояжёра», когда там никакого недеретминизма нет. Есть – причём те же самые алгоритмы применяются. И там получаются достаточно хорошие результаты.

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

А.Г. В казино не хотите в рулетку играть с этим подходом?

Б.М. Нет, но один из результатов этого подхода – предсказание курса валют, которые мы безуспешно всё пытаемся куда-нибудь пристроить. Но этих программ-предсказателей немереное количество.

А.Г. Насколько аккуратны ваши действия?

Б.М. Предсказать какой-то катаклизм вроде нашего кризиса 98-го года, видимо, никому не удавалось и не удастся, а доказать, что наша программа лучше, на каком-то более простом примере нам пока не удаётся. Но, в общем-то, это тоже не ставится как цель. Получить отсюда прибыль, коммерческий эффект, это второе, третье дело. Пока не получается. Получится – хорошо. Не получится – не страшно. Я всё-таки вижу основную цель в том, чтобы этот подход ввести в программирование игр, в другие задачи. Победить – дай Бог – на следующем чемпионате мира, 2004 года.

А.Г. Можно ещё чуть подробнее, что такое «центр тяжести» в данном случае, потому что я понял, но не до конца. Ещё раз можете объяснить, что такое принцип динамического подхода, присвоение веса и так далее?

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

Теперь мы подбираем массу этих шариков, а масса этих шариков подбирается согласно функции риска.

Б.М. Чем больше значение этой функции в данной точке, тем больше масса шарика.

А.Р. А потом этот стержень уравновешиваем и находим положение центра тяжести.

Б.М. Это, видимо, лучше объяснение, чем моё…

А.Г. Оно доступнее, да.

А.Р. Этот центр тяжести, его положение, мы считаем величиной, которая…

А.Г. Оптимальной величиной, которая позволяет сделать…

А.Р. Не сказать, чтобы оптимальной, это просто характерная величина, которая более-менее описывает куст с этими случайными событиями. И мы её принимаем в качестве оценки.

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

А.Г. То есть вы определяли себя игроком хуже, чем ваш партнёр?

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

И уже на этом мы подбирали разные виды этих функций риска. Уже здесь мы почти вплотную приблизились к «Джели-фишу». Если мы сейчас у него выигрываем (ещё раз повторяю, на нашем российском варианте нард) где-то 55 процентов, может, чуть побольше, тогда мы проигрывали столько же. Но это уже было хорошо. Выигрываем на убывающих функциях риска. Убывающих – это означает, что мы хоть немного, да пессимисты.

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

А.Г. Речь идёт о стратегии игры?

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

Если же мы заведомо проигрываем, функция риска сильно возрастает. Если же мы выигрываем очень сильно, то мы должны быть сверхпессимистами и очень плохие прогнозы предполагать с гораздо большими вероятностями. И функция риска будет становиться функцией сверхпессимиста. И в зависимости от такого предварительного подсчёта, предварительной генерации, мы и строим динамическую функцию риска.

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

А.Г. Это то, что у игрока называется интуицией во время игры.

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

Казалось бы, что это очень долгие вычисления, но нет – по сравнению со всем остальным объёмом вычисления, связанного с получением статических оценок позиции, с организацией перебора и так далее. Это неоднократное применение функции риска, динамическая функция риска, фактически совершенно не занимает времени, то есть там какие-то доли процента – даже, кажется, мы и не считали, какие именно доли процента. Даёт ли этот третий шаг большой выигрыш по сравнению только со вторым? Я затрудняюсь сказать, но раз без каких бы то ни было усилий мы можем получить какое-то преимущество, то, наверное, даёт.

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

А.Г. Вы сами у своей программы выигрываете?

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

И всё-таки я азарту поддаюсь. Например, если я два хода назад стоял хорошо, на выигрыш, но что-то случилось, плохо кубики упали, и я начал стоять плохо. Я просто по инерции продолжаю у себя в мозгу применять пессимистическую функцию риска, оценивая позицию, чего, конечно, делать не надо. Программа же быстрее переключается и быстрее понимает, что всё не так хорошо происходит, как есть на самом деле, и программа переключается, например, от пессимистической к оптимистической функции риска, переключается гораздо быстрее чем я.

А.Р. Тут, наверное, стоит ещё заметить, что программа, в которой реализованы эти алгоритмы, но в которой не подобраны числовые коэффициенты (когда переключаться на какую стратегию, как, собственно, статично оценивать позицию, хорошая она или плохая), эта программа не является рабочей. Чтобы она заработала, необходимо её обучить. Обучение программы происходит, когда она играет сама с собой, тогда происходит, собственно, подгонка параметров таким образом, чтобы максимально улучшить качество игры, максимально повысить вероятность выигрыша.

Но здесь возникает уже другой вопрос – каким образом её учить? Если в играх сама с собой, то, наверное, это будет немного необъективно, так как в данном случае отношения не транзитивны: если программа выиграла у другой программы, а другая у третьей, то не обязательно, что первая выиграет у третьей. И выбор системы обучения – тоже очень интересная проблема. И, собственно, если её грамотно решить, то можно действительно надеяться на то, что получится продукт, который в 2004 году станет играть на должном уровне.

А.Г. То есть эту проблему вы ещё не решили?

Б.М. Решаем… всё-таки можно даже сказать, что решили. Здесь мы касаемся темы, о которой ещё сегодня не говорили. Это не нейросети, их мы очень мало применяем здесь. А это так называемые генетические алгоритмы. В научной литературе им посвящено гораздо меньше публикаций, чем нейросетям. Мне кажется – незаслуженно. Потому что и то, и другое – это альтернативный подход к эвристическому программированию. Чистые математики объясняют это так, что нейросети – это математически объяснимо, может быть математически доказано, а генетические алгоритмы – якобы нет. И приводят ссылки на работу Колмогорова-Арнольда, работу 50-х годов – но мне кажется, что для практического программирования эта работа представляет весьма малый интерес. И то, и другое, это разные альтернативы, разные подходы к эвристическому программированию. Наша «функция риска» – это тоже подход. Просто надо всё применять в разумных примерах, в разумных количествах.

Вот здесь возникает именно задача самообучения набора коэффициентов, среди которых, кроме всего прочего, коэффициенты самообучения функций риска, не только коэффициенты для оценки позиций, но и коэффициенты функций риска. Мне, по крайней мере, неизвестно хороших публикаций (чуть ли вообще никаких) про самообучение этих наборов коэффициентов. Есть, либо есть стандартный подход генетических алгоритмов, в котором тоже много не совсем правильного, либо просто, как в упомянутых книжках Вельского с компанией, сказано: «Было произведено самообучение». Было, хорошо было произведено, раз программа хорошая, раз, отставая в 70-х годах от американцев по технике, на той же самой технике «Каисса», победила. Значит, было хорошо самообучение произведено, но как оно было произведено, никакой теории по этому поводу не было.

А.Г. Получается, что в вашем случае, при ваших алгоритмах решения, самообучение важнее, чем в случае программ, которые строятся на нейросетях. Или я ошибаюсь?

А.Р. В нейросетях как раз всё построено на самообучении…

Б.М. Но там своё самообучение…

А.Р. Нейросеть нужно настроить, чтобы она играла. Это производится за счёт самообучения, иначе это просто будет…

А.Г. Я неправильно задал вопрос. Что вам важнее – выбрать метод обучения программы или… Грубо говоря, у вас ребёнок непослушный, непредсказуемый…

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

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

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

Что ещё можно? Ещё только начаты работы в том направлении, чтобы программа пыталась, пока противник думает, начать думать за противника и старалась подобрать к противнику свои критерии работы. То есть пыталась представить саму себя на месте противника, и если у неё это получается, она на месте этого виртуального противника подставляет саму себя со своими коэффициентами. Вот это была бы очень интересная тема. Но она, как я уже сказал, только начата, и сказать, насколько она реально применяется в программах, я вам пока не могу.

А.Г. Ну что ж, мне осталось вам пожелать удачи в 2004 году. И если победите, то приходите рассказать о том, как это было.

Б.М. Спасибо!