Sunday, July 17, 2016

Дмитрий Бачило: Трудный путь Apple к Mac OS X



Для повторения старого материала:

История Mac 128k


История NeXT

Гордон - Диалони: Программирование недетерминированных игр (03.06.2003)

Форматирование не сохранено.



Участники:

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

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

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

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

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


- Здесь я должен сделать несколько замечаний.

1. В ноябре-декабре 2006 года чемпион мира Владимир Крамник играл с программой Deep Fritz. Матч закончился выигрышем машины со счётом 2-4.
Если после поражения Каспарова в 1997 г. у некоторых ещё были сомнения в силе компьютера, то после этого матча стала всем понятно, что компьютер играет лучше чемпиона мира по шахматам среди людей.

2. [12 марта 2016 г.] Не осталось игр с открытой информацией, в которых компьютер не мог бы обыграть человека
После этого не осталось игр с открытой информацией, в которых компьютер не мог бы обыграть человека.


- Несколько цитат из стенограммы.


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

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

- Следующая цитата:
...Каким образом проводится самообучение?..

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

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


Далее, будет приведено продолжение стенограммы, а затем материалы к подготовке к программе.


Ниже есть продолжение.

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

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

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

Б.М. Да, конечно. Давайте тоже об этом расскажу. Я незаслуженно поздно познакомился с нардами. В шахматах я уже был достаточно большим специалистом для своего возраста, а про нарды узнал из публикации в «Науке и жизни» – мне было где-то 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 году. И если победите, то приходите рассказать о том, как это было.

Б.М. Спасибо!
http://ralimurad.narod.ru/lib/gordon/gameprog/index.html

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

Рассмотрим некоторые эвристики, применяемые при программировании игр — естественно, речь идет об интеллектуальных играх, а не о значительно более популярных в настоящее время динамических играх, рассчитанных, в первую очередь, на быстроту реакции пользователя, и лишь во вторую (или даже в последнюю) — на его интеллект. Эвристики — это специальные методы, используемые в процессе открытия нового. Второе значение термина «эвристика» — наука, изучающая продуктивное творческое мышление.

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

По мнению Б. Ф. Мельникова, в литературе, посвященной искусственному интеллекту вообще и программированию интеллектуальных игр в частности, шахматам (и «аналогичным’ простым играм) уделено слишком большое внимание. Более того, о шахматах утвердилось мнение как о самой интеллектуальной игре, когда-либо изобретенной человеком. Математики проводят аналогии между мышлением шахматиста и математика, экономисты говорят о помощи шахматного мышления для работы „на рынке ценных бумаг“, психологи — о его помощи в разных жизненных ситуациях... Однако Б. Ф. Мельников придерживается особого мнения. Он считает, что человечество сделало ошибку, назвав именно шахматы самой интеллектуальной игрой. Ученый считает такой игрой Backgammon, почти не отличающийся от известной в России (и других странах бывшего СССР) игры „короткие нарды“. При игре в Backgammon человек занимается не только прямым пересчетом, но и — в значительно большей степени, чем при игре в шахматы — качественной оценкой позиции; за последнюю же, по-видимому, „отвечает“ правое полушарие мозга — следовательно, оба полушария в этом случае „задействованы“ полностью.

Все-таки шахматы не случайно так часто упоминаются. При программировании огромного количества интеллектуальных игр используются те же самые модели, что и в шахматах. Среди таких игр можно назвать реверси, калах, оуа, рэндзю, разные (национальные) версии шашек. Стоит еще упомянуть различные игры, рассматривавшиеся М. Гарднером — в заметках, публиковавшихся в течение нескольких десятилетий в журнале „Scientific American“, а также в его книгах, некоторые из которых переведены и на русский язык. Большинство указанных игр — детерминированные; таковых в упомянутых книгах несколько десятков, тогда как недетерминированных — существенно меньше. Отметим, однако, что не во всех детерминированных играх можно использовать „шахматные“ модели, эти модели неприменимы при игре в го (эту игру часто неудачно называют японскими шашками).

В различных национальных версиях шашек, для получения очень сильных программ часто достаточно использовать те же самые модели, что и в шахматах, но в значительно более простом виде. Например, программы разных версий 64-клеточных шашек обыграли действующих чемпионов мира в 60-х годах, что на 30 и более лет раньше, чем в шахматах. Кроме того, многие из методов дискретной оптимизации в задачах программирования недетерминированных интеллектуальных игр, которые будут описаны ниже, могут быть применены и в „обычных“, детерминированных играх. Кроме того, эти же методы применяются автором и в других задачах искусственного интеллекта.

Карточные игры — причем все — в советское время были отнесены к „азартным“; при этом многие из них (в первую очередь такие недетерминированные игры как преферанс и бридж) совершенно несправедливо. К сожалению, это отношение перешло и на отечественные работы, связанные с программированием игр.

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

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

Будем исходить из предположения автора, что сам „канонический“ метод минимакса читателю известен. В недетерминированных играх чередуются: конкретная реализация некоторого случайного события, ход одной из сторон, снова реализация случайного события, ход другой стороны. Количество всевозможных исходов случайного события должно быть конечным (иначе придется применять другие модели). В результате в дереве игры появляются уровни, заключенные между уровнями очередности ходов соперников. Эти новые уровни отражают те моменты игры, в которые реализуется исход случайного события. Обобщение метода минимакса работает именно с таким деревом.

Итак, считаем, что мы умеем строить статическую оценку позиции. Временным удалением недетерминированности получаются предварительные оценки позиций дерева игры. Для этого мы сначала предполагаем, что уже реализовался конкретный исход случайного события, и вычисляем динамическую оценку для данной позиции так же, как и в „обычном“ методе минимакса. Затем вычисляем динамическую оценку позиции для следующего исхода случайного события, и так далее для всех исходов.

Окончательная динамическая оценка позиции определяется на основе всех детерминированных оценок, полученных для всех возможных значений случайного события. Полученные значения детерминированных (обычно — статических) оценок специальным образом усредняются — это и есть окончательная динамическая оценка. С физической точки зрения такое усреднение дает положение центра тяжести одномерной системы тел с массами, определяемыми специально подобранной функцией (функцией риска). Координаты тел системы — значения соответствующей детерминированной оценки, которая определяется только детерминированными факторами игры, как, например, в обычном минимаксе. Например, пусть a1,..., ak — значения детерминированных оценок, а f — некоторая функция риска. Тогда значение динамической оценки вычисляется по следующей формуле:



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

Автоматическая смена стратегии. Отметим, что описанные далее приемы и алгоритмы могут быть реализованы, например, с помощью нейросетей. Однако в данном случае используемые здесь алгоритмы позволяют обходиться и без них, существенно упрощая работу практического программирования. Материал этого пункта не связан с автоматическим изменением набора правил, применяемых при выборе очередного хода, — работа над этой темой является задачей обозримого будущего. Однако название раздела не является преувеличением: изменение специальных коэффициентов — не являющихся коэффициентами статической оценки позиции — действительно приводит к изменению стратегии игры программы.

Перед описанием таких алгоритмов рассмотрим немного подробнее, почему обобщение метода минимакса для недетерминированных игр действительно стоит формулировать именно так, как это сделано в разделе „Динамическая оценка позиции“. Покажем, что это обобщение следует из реального мышления игрока, проявляющегося далеко не только в какой-либо недетерминированной игре, но и, по большому счету, в иных различных жизненных ситуациях. Действительно, человек чаще всего не самые удачные реализации случайных факторов (в backgammon’e это варианты бросков кубиков противника) должен считать более вероятными, чем хорошие для него: надо быть хоть немного, да пессимистом. То есть усреднение, кратко описанное выше, необходимо делать с весами тем меньшими, чем более „хорошим для нас“ является будущее показание кубиков противника (повторим: так надо делать не всегда, но чаще всего).

Возникает вопрос: насколько надо уменьшать веса для „хороших для нас“ показаний кубиков противника? Если заранее задать функцию риска и употреблять ее независимо от каких-либо иных обстоятельств с простейшей функцией статической оценки позиции, то даже в этом случае результаты получаются довольно хорошими. Автором при этом были рассмотрены различные убывающие функции риска. Простейшее интуитивное объяснение того, что обычно функция риска должна быть убывающей, можно рассматривать как выход из следующего небольшого статистического исследования Гарднера: человек за возможность сыграть в простейшую игру, заключающуюся в подбрасывании монеты и получении 10 долл. в случае выпадения орла, в среднем готов заплатить 3–4 долл. (но не 5).

Итак, для получения более сильной программы необходимо проводить смену стратегий в процессе игры. Один из путей улучшения простейшей динамической оценки позиции заключается в следующем. Мы можем заранее прикинуть оценку позиции (т. е. как примерно мы „стоим“ — на выигрыш или совсем наоборот); далее: если мы выигрываем или „проигрываем совсем мало“ — то надо быть пессимистами, и примерный вид функции риска описан выше (убывающая); если „проигрываем больше“ — то функция риска близка к константе; если же „проигрываем сильно“ — то, наоборот, функция риска является возрастающей: ведь в этом случае необходимо быть сверхоптимистами и надеяться почти на чудо (а что делать?).

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

Далее, функции, приведенные выше, удобно описывать с помощью трех параметров — например, параметров, являющихся значениями функции риска в точках 0, 0,5 и 1 — при этом сама функция риска строится с помощью квадратичной интерполяции. Для дальнейшего удобно обозначать эти три функции — как функции от статической (или простейшей динамической) оценки S — записью fs(0), fs(0,5), fs(1).

Данные параметры можно выбрать таким образом, чтобы интерполирующие функции для нескольких значений S оказались близкими к выбранным выше. Первый и третий параметры fs(0) и fs(1), характеризуют изменение функции риска (при росте S) от возрастающей к убывающей. А второй параметр, fs(0,5), характеризует изменение выпуклости функции риска при росте S. Последние три функции также можно считать зависящими от параметров.

Основные эвристики процесса самообучения игровых программ. „Турнирные“ алгоритмы самообучения». Самообучение можно рассматривать как повторяющиеся игры программы с самой собой, при этом два играющих варианта одной и той же программы используют немного отличающиеся друг от друга множества коэффициентов (последние применяются просто для статической оценки позиции). Таким образом, «силу программы» можно рассматривать как функцию многих переменных. Однако — какую именно функцию? Этот вопрос в литературе (как в статьях, так и на интернетовских страницах) практически не отражен; предполагается, что если одна программа (точнее — один набор коэффициентов) выиграла у другой (другого), то и значение такой функции на первом наборе коэффициентов больше.

Однако даже при этом предположении оптимизировать подобную функцию силы программы крайне сложно, так как она имеет большое количество локальных максимумов; кроме того, по-видимому, даже в некоторой локальной области невозможно исследовать подобную функцию на выпуклость. Еще большие проблемы, связанные с самим определением такой функции силы, вызывают «нетранзитивные наборы коэффициентов». Хотя, заметим, самые простые методы поиска экстремума (автор в практическом программировании часто пользуется модификацией градиентного метода с неявным вычислением частных производных) дают неплохие практические результаты — несмотря на описанные здесь и далее проблемы, связанные с определением функции силы.

При подобном самообучении все авторы считают очевидным тот факт, что результатом самообучения должен быть набор коэффициентов, на котором у программы значение функции силы (кратко охарактеризованной выше) максимально возможное. Однако — почему более важна именно такая программа, «объективно более сильная»? Разве не опровергают эту мысль многочисленные примеры нетранзитивных игр? Интересно заметить, что и в реальной жизни, в самых разных игровых видах спорта, встречались и встречаются ситуации, когда в соревновании в итоге побеждает далеко не сильнейший (но общему признанию) участник. Конечно, частая причина этого — несовершенство системы проведения соревнований; кстати, статистическое исследование систем (как уже существующих, так и потенциально возможных), сравнение их по различным критериям — тема отдельного небольшого исследования. Однако часто в реальной жизни встречаются и другие причины. Например, А. Алехин в международных шахматных соревнованиях 30-х годов постоянно проигрывал Л. Асталошу, шахматисту практически неизвестному и ничем иным не прославившемуся.

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

Немного упрощая ситуацию, можно сказать, что для выбора одной игровой программы из нескольких мы должны провести турнир между ними. (И, также упрощенно, определить силу программы как случайную величину, реализация которой — результат выступления этой программы в турнире.) Но по какой именно системе, по каким именно правилам следует проводить турнир? Как понятно из вышеизложенного, даже в турнире по круговой системе (не говоря уже о совсем необъективной олимпийской) может показать более хорошие результаты программа, которая иногда применяет не самые сильные ходы. То есть даже в детерминированных играх возможен выбор из двух ходов, один из которых более сильный, зато другой — с риском, «ловушкой? Тем более это верно для недетерминированных игр, где риск может быть строго определен. Риск может быть определен при условии, что единственная цель — выиграть одну партию в короткие нарды (backgammon). Однако даже в последней игре существуют ситуации, когда эта цель не является самой важной в данный момент (хотя этот факт и может показаться довольно странным для шахматиста, специалиста но шахматному программированию и т. п.). Например, такая ситуация иногда возникает при проведении матча с использованием удваивающего куба (cube) — а ведь именно таким образом обычно проходят официальные соревнования по backgammon’y.

Автор при практическом программировании самообучения применял разные системы. По понятным причинам, олимпийская система плоха; поэтому нередко применялись круговая система (когда каждая программа встречается с каждой, и победитель определяется по общему числу побед).

Но и круговая система не является оптимальной, она имеет, по крайней мере, следующие четыре недостатка.

1. Временные ограничения: необходимо провести очень большое число партий (матчей).

2. В очень большом проценте партий встречаются один из сильнейших участников с одним из слабейших — так что даже в случае недетерминированных игр исход часто предрешен заранее.

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

4. Несмотря на сказанные выше слова, что итоговая (искомая) программа должна показать свое превосходство не против какой-либо одной программы-соперницы, а против нескольких, с более сильными программами желательно играть чаще.

И чем изобретать некоторый критерий, преодолевающий эти недостатки (например, усредняя результаты встреч с некоторыми весами, — этот критерий в чем-то аналогичен функции риска), — лучше воспользоваться уже имеющимся готовым рецептом, так называемой швейцарской системой проведения турнира.

Основные положения швейцарской системы кратко опишем и в данном обзоре. В классическом варианте этой системы обычно предполагается, что число участников N довольно велико, а число туров (т. е. партий, проводимых каждым участником) значительно меньше числа N-1, нужного для проведения круговой системы, и лишь немногим (обычно примерно в 2 раза) превышает число [log2N]+1, нужное для проведения олимпийской системы. В каждом туре составляются пары из участников, имеющих равное (или примерно равное) число очков; при этом повтора пар не допускается. Из приведенного краткого описания швейцарской системы видно, что при этом преодолеваются три из четырех ранее описанных недостатков круговой системы. И действительно, многолетняя практика применения швейцарской системы в шахматных соревнованиях показывает ее «живучесть» (поскольку шахматисты-практики дают о ней, в основном, положительные отзывы). Однако один недостаток остается (большое число партий, не влияющих на итоговый результат процесса), поэтому Б. Ф. Мельников при практическом программировании самообучения чаще всего применял модификации швейцарской системы.

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

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

Другие алгоритмы самообучения и связанные задачи. При организации самообучения программ автором применялся следующий алгоритм для локальной сети ЭВМ. Набор коэффициентов, «лидирующий» в турнире, имеет б́ольший приоритет (б́ольшую вероятность) для назначения его на следующую партию (матч); это назначение выполняется головным компьютером для проведения на каком-либо ином компьютере сети. Может быть, математик позаимствовал подобный приём у шахматной программы «Deep Thought», обыгравшей Г. Каспарова (однако там он применялся для организации взаимодействия процессов, выборе более перспективного из них — да и всех своих «тайн» авторы той программы ещё не открыли). По-видимому, эта тема ещё ждёт дальнейшего развития, схожие алгоритмы (самообучения в локальной сети) могут применяться и в других задачах дискретной оптимизации, не связанных с задачами игрового программирования.

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

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

Заключение. Самое интересное между «да» и «нет». Основным результатом работы Б. Ф. Мельникова по данной теме является программа игры в backgammon (короткие нарды), обыгрывающая как всех известных автору игроков-практиков, так и все программы, найденные в Интернете и других источниках. По его мнению, backgammon — не только самая интеллектуальная игра, но и более, чем шахматы, интересен для создания игровых программ. К этому необходимы сразу несколько замечаний. Название «backgammon» лучше записывать латинскими буквами, так как применяющаяся иногда русская интерпретация этого названия — бэкгэммон — «смотрится» ещё хуже. Небольшие отличия backgammon’а от коротких нард всё же есть, поэтому ниже название «нарды» здесь не употребляется. С точки зрения программирования можно было бы выбрать любую из двух моделей — автор выбрал более распространённый backgammon, имеющий, кстати, международную федерацию, наподобие шахматной. И, по-видимому, отечественным любителям нард ст́оит перейти на международный стандарт. Короткие нарды ни в коем случае не надо путать с длинными, которые вряд ли стоит считать интеллектуальной игрой. Последние — просто «передвигание фишек» в соответствие с показаниями двух кубиков, и в этой игре в партии более-менее опытных игроков практически всегда в итоге побеждает тот, чьи показания в сумме оказались больше. Б. Ф. Мельников действительно считает backgammon более интеллектуальной игрой, чем шахматы. Однако «квасным патриотом» backgammon’а его, по-видимому, назвать нельзя: он имеет не только «математические регалии», но и — не намного меньшие — именно шахматные. Вообще, среднее число возможных ходов в backgammon’е, (после того, как уже стало известно конкретное показание кубиков), по-видимому, примерно равно среднему числу возможных ходов в шахматах (т. е. примерно 25–40 вариантов). Более того, несложно привести пример, когда число возможных ходов в позиции backgammon’а превышает максимальное возможное число ходов в шахматной позиции, равное 109.

Прослеживается большая аналогия между парой шахматы / backgammon с одной стороны, и парой классическая / нечёткая логика — с другой. Приведём по этому поводу мысль из книги математика и философа Барта Коско (Bart Kosko) «Fuzzy Thinking» («Нечёткое мышление») — она цитируется по одному из многочисленных пересказов этой книги, имеющихся в Интернете. Коско считает, что два тысячелетия назад человечество сделало роковую ошибку, заложив в фундамент науки не «зыбкую поэтику ранних восточных философий», а «выхолощенную двоичную логику Аристотеля». И с тех пор классическая «чёрно-белая» бинарная логика всё более отдаляется от реального многоцветного мира, где нет ничего абсолютного, а всё самое интересное «происходит в туманной области между „да“ и „нет“».

Методы, применявшиеся при создании программы и самообучении игровых программ, могут найти применение (и уже находят) во многих других задачах дискретной оптимизации и искусственного интеллекта. Среди этих задач и очень часто встречающаяся задача о подборе наилучших параметров при имитационном моделировании стохастических процессов. Один из примеров — задача теории биологических популяций (без статистики старения). В последнем случае прослеживается очень большая аналогия с недетерминированными играми. Действительно, при одних и тех же входных параметрах возможны различные варианты изменения параметров популяции в зависимости от времени — в этом и проявляется недетерминизм. Однако параметры имитационного моделирования, несмотря на недетерминизм, должны быть подобраны статистически наилучшим образом.

Рассмотренный подход имеет аналогии в других задачах, например: при моделировании экономических процессов, краткосрочном прогнозировании микро- и макроэкономических параметров, в теории принятия решений с использованием алгоритмов нечеткой классификации ситуаций и др.

Библиография

Адельсон-Вельский Г.М., Арлазаров В. Л., Донской М. В. Программирование игр. М., 1978

Ботвинник М. М. Алгоритм игры в шахматы. М, 1968

Гарднер М. Математические досуги. М., 1995

Клемент Р. Генетические алгоритмы: почему они работают? когда их применять?//Компьютерра. 1999. № 11

Лернер А. Я. Начала кибернетики. М., 1967

Мельников Б. Ф., Мосеев А. В. Недетерминированные игры и экономика/Математические методы и компьютеры в экономике: Сборник материалов конференции. Пенза, 1999

Мельников Б. Ф., Радионов А. Н. О выборе стратегии в недетерминированных антагонистических играх//Программирование: Изв. РАН. 1998. № 5

Мельников Б. Ф. Эвристики в программировании недетерминированных игр//Програмирование: Изв. РАН. 2001. № 5

Мельников Б. Ф., Романов Н. В. Ещё раз об эвристиках для задачи коммивояжёра//Теоретические проблемы информатики и ее приложений. Саратов, 2001. Вып. 4

Нейман Дж. фон. Теория игр и экономическое поведение. М., 1970

Цермело Э. О. Применении теории множеств к теории шахматной игры/Матричные игры. М., 1961

Шеннон К. Э. Играющие машины/Работы по кибернетике и теории информации. М., 1956

Berliner H. Computer backgammon//Scientific Am. 1980. № 243

Zbigniew M., Michalewicz S. Genetic algorithm + Data stucture = Evolution programs. Berlin; Heidelberg, 1992

Melnikov B. A new algorithm of the state-minimization for the nondeterministic finite automata//The Korean Journal of Computational and Applied Mathematics. 1999. V. 6. № 2

Melnikov B. Once more about the state-minimization of the nondeterministic finite automata//The Korean Journal of Computational and Applied Mathematics. 2000. V. 7. № 3

Тема № 263

Эфир 03.06.2003

Хронометраж 50:09
http://gordon0030.narod.ru/archive/12035/index.html