Александр Гордон
Диалоги (июнь 2003 г.)
Программирование недетерминированных игр
3.06.03
(хр.00:50:09)
Участники:
Мельников Борис Феликсович – доктор физико-математических наук, профессор.
Радионов Алексей Николаевич – кандидат технических наук.
Борис Мельников: …И книжки, выходившие в основном в 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 года.
А.Г. Можно ещё чуть подробнее, что такое «центр тяжести» в данном случае, потому что я понял, но не до конца. Ещё раз можете объяснить, что такое принцип динамического подхода, присвоение веса и так далее?
А.Р. То, что мы для каждого исхода случайного события имеем какую-то числовую величину – это просто набор прогнозов на будущее. Нам этот набор не делает погоды, из него надо получить какую-то одну величину, одно значение, которое всю ветвь, которая следует за случайными событиями, оценивает приемлемой величиной, основываясь на которой мы сделаем решение – ходить нам так или предпочесть другой вариант. Так вот, на основе чего получается общая оценка этого набора прогнозов? Каждую точку, каждую величину, грубо говоря, можно представить шариком на стержне. Стержень у нас длиной от минус единицы до единицы, минус единица – это значит, что дела для нас очень плохо пойдут. Единица – что очень хорошо, мы победители. На этот стержень нанизаны шарики. Каждый на своём расстоянии от нулевой точки. Это расстояние соответствует значению прогноза.
Теперь мы подбираем массу этих шариков, а масса этих шариков подбирается согласно функции риска.
Б.М. Чем больше значение этой функции в данной точке, тем больше масса шарика.
А.Р. А потом этот стержень уравновешиваем и находим положение центра тяжести.
Б.М. Это, видимо, лучше объяснение, чем моё…
А.Г. Оно доступнее, да.
А.Р. Этот центр тяжести, его положение, мы считаем величиной, которая…