Подразделы категории "Гордон": Программирование недетерминированных игр
Расшифровка передачиБорис Мельников. …И книжки, выходившие в основном в 70-е годы, по программированию игр, прежде всего, посвящались шахматам. Эти книжки в основном писались коллективом авторов с Адель- сон-Вельским во главе. И в чём-то альтернативно пи- сал книжки один из чемпионов мира по шахматам Бот- винник. На основе идей Ботвинника так и не была со- здана программа, «Пионер» так и не заработал, в об- щем-то, – не то что в полную силу не заработал, а во- обще не заработал. А «Каисса» Адельсона-Вельского была чемпионом мира среди шахматных компьютер- ных программ, по-моему, в 73-м году или в 74-м, а че- рез три года заняла второе место. И ещё в этих книжках были упомянуты немножко и другие игры. Но, действительно, только немного. Мо- жет быть и зря, потому что первые успехи в програм- мировании детерминированных игр были во второй по- ловине 60-х годов, если мне не изменяет память, в районе 67-го года, может быть немножко раньше, ко- гда в разных национальных версиях шашек хорошая программа обыгрывала чемпиона мира. Ну, или, может быть, чемпиона своей страны по этим играм. В шах- матах такое случилось только в 97-м или в 98-м, ко- гда «Deep Thought» обыграла Каспарова, действующе- го чемпиона мира, и с тех пор, в общем-то, этот случай больше не повторялся. А именно – недавно с Крамни- ком программа сыграла вничью. Причём, даже злые языки говорили, что Крамник немножко сплоховал в конце, даже чуть ли не сознательно. Но всё-таки речь не об этом. Итак, возвращаясь к недетерминированным играм. Здесь хочется обязательно сказать, что в этих книжках, в очень хороших книжках, изданных в советское время, в 70-х, в начале 80-х годов, там про недетерминиро- ванные игры не было сказано вообще ни одного слова. А это и карточные игры, в том числе и интеллектуаль- ные карточные игры – бридж, преферанс (прежде все- го преферанс, который я считаю даже более интеллек- туальным, чем бридж). И про то, чем мы занимаемся – я, наконец, перехожу к нардам – в этих книжках не было совсем. То есть, считалось, что эти игры азарт- ные, в них играть запрещали. Я даже помню такие по- луанекдотические случаи, когда за игру в карты из ком- сомола могли выгнать, из общежития выселить. Даже и к нардам были подобные притязания. Александр Гордон: Конечно, кубики кидают… Борис Мельников. Нарды действительно воспринималась как азартная игра. Что, конечно, не правильно. Потому что для хорошей игры в нарды тоже нужно обладать ин- теллектом. Александр Гордон. Вы сейчас говорите о так называемых коротких нардах? Борис Мельников. Да, конечно. Давайте тоже об этом расскажу. Я незаслуженно поздно познакомился с нардами. В шах- матах я уже был достаточно большим специалистом для своего возраста, а про нарды узнал из публикации в «Науке и жизни» – мне было где-то 14 лет. Там была публикация про нарды, в середине 80-х годов. И были две распространённые в России версии нард – длин- ные и короткие. И я достаточно быстро, хоть достаточ- но был молод, понял, что так называемые «длинные» нарды – это игра не очень интеллектуальная. То есть, просто игра на перетаскивание фишек в зависимости от показания кубика. Интеллект иногда надо было при- менять, но, по моим расчётам, в длинных нардах, что- бы из новичка получить человека, который играет на- равне с чемпионом, может быть трех минут мало, как в крестиках и ноликах на доске три на три, но дня – до- статочно. Чего, конечно, нельзя сказать о коротких нар- дах. И, тем более, о расширении этой игры, междуна- родной версии «бэкгеммон», в которой добавлено ещё несколько правил, несколько усложнений, которые эту игру делают гораздо более интересной. Главное – это как выпадают кубики. Мы должны сде- лать свой ход, не зная, как кубики выпадут. Однако, не- смотря на это, мы можем играть так, что играем лучше чем новичок, лучше чем человек, который поиграл ме- сяц-другой. Ну и, в конце концов, становимся достаточ- но сильным игроком – точно так же, как и в шахматах. Недавно мне попалась книжка Гика, недавно издан- ная, про разные игры, в которой проводится мысль, с которой совершенно не могу согласиться. Там говорит- ся о том, что сильные игроки в бэкгеммон, в нарды, де- лают практически одинаковые ходы в сложных пози- циях, когда знают позицию, знают показания кубиков. Ну и поэтому в партиях сильных игроков побеждает тот, кому лучше придут кубики. Конечно, это так. Луч- ше придут кубики – это очень важно, гораздо важнее, чем в шахматах, где кубиков нет. Но, однако, те же са- мые сильные шахматисты в схожих позициях делают разные ходы, в этом проявляется стиль шахматиста. И нардисты, игроки в бэкгеммон, тоже делают разные хо- ды – тоже в зависимости от стиля. И недаром на сай- тах в Интернете выставляются партии лучших игроков в мире и, в частности, их партии с компьютерами. Но перехожу, наверное, к самому основному, то есть связанному с темой передачи. Наша группа среди про- чего делает и программы по игре в бэкгеммон. Лучше даже пока сказать – в наши отечественные «короткие нарды». По материалам этих программ были статьи в журнале «Программирование». Нужно сразу оговориться, чтобы эта тема не пока- залась слишком лёгкой, слишком ненужной – совер- шенно те же приёмы применяются нами и в несколь- ких задачах дискретной оптимизации. В гораздо бо- лее серьёзных задачах. Наверное, слово «серьёзные» я употребляю в кавычках, потому что самым серьёз- ным я считаю программирование нард. Именно там, в основном, и должен проявиться человеческий интел- лект. Это гораздо более серьёзная задача, но я назову и другие задачи, которые на слуху у математиков. Это так называемая «задача коммивояжёра». У нас есть несколько подходов к этой задаче дискретной оптимизации. Казалось бы, всё сделано, есть эвристи- ческие алгоритмы минимизации дизъюнктивных нор- мальных форм. Однако известные алгоритмы реаль- но работают только для маленьких размерностей. И я ещё не всё вспомнил, но по этим темам у меня рабо- тали в разное время 3-4 дипломника-аспиранта. Вот минимизация конечных автоматов – по этому поводу у меня постоянно защищаются дипломные работы, сей- час две диссертации на выходе. А здесь применяют- ся те же самые эвристические алгоритмы, что и в про- граммировании игр. Так что, основная, конечно, тема – это программи- рование игр, и я вернусь к программированию нард. В Интернете можно найти разные программы, играющие в бэкгеммон. И, в частности, в них во всех можно уста- навливать уровень, лучше сказать не «уровень игры», а «вариант игры», который совпадает с русской верси- ей, с более упрощённой, это короткие нарды. Но вот, к сожалению, у нас пока программы играют только в на- шу отечественную версию и, причём, после публика- ции в журнале «Программирование» двухлетней дав- ности, больших успехов с этого времени практически не случилось. Мы не поучаствовали в чемпионате ми- ра по программированию летом 2002 года (хотя соби- раемся поучаствовать в следующем чемпионате 2004 года). Не поучаствовали по той причине, что просто не хватает времени – с совершенно теми же самыми идеями – довести программу до уровня бэкгеммон. То есть, до уровня международного стандарта, несколько более усложнённого. Но я, здесь сидя, обещаю, что в 2004 году я это сделаю. То есть, мы всех должны по- бедить. Почему у меня такая уверенность? Потому что всё- таки наш русский, российский (может быть, не очень хорошо говорить «русский», потому что в разных кав- казских республиках бывшего Советского Союза ко- роткие нарды распространены больше, чем в России, поэтому лучше сказать «советский» вариант игры), по- тому что советский вариант игры – это более простой вариант. Александр Гордон. Для тех, кто знаком с правилами игры в короткие нарды, скажите, пожалуйста, в двух словах, чем отли- чается бэкгеммон от коротких нард. Борис Мельников. Самое главное отличие – то, что в бэкгеммо- не добавляется ещё один кубик, удваивающий куб. Doubling dice, даблинг дайс, по-моему, называется. Его смысл вот какой. Кубик сначала лежит на единичке и в любой момент игры любой из участников может пе- ревернуть его на двойку. И другой – либо сразу сдаёт- ся, либо любой будущий исход игры удваивается. При этом тот, кто удваивает, уже не является хозяином ку- бика. Если в самом начале кубик является общим, то удвоенный кубик лежит на стороне того, который со- гласился – не того, который предложил удваивать, а того, который согласился. И далее можно учетверять и так далее. И сначала, когда я впервые познакомился с этим правилом (это было 5 лет назад, когда Интернет стал широко доступен), то первая моя реакция была рез- ко отрицательная, я даже тогда такие примеры при- водил: играет, например, «Спартак» с «Динамо» (Ки- ев), выбегает тренер Романцев и ставит на футболь- ное поле огромный куб с двойкой. И киевляне либо со- глашаются, либо убегают с поля. Но потом я постепен- но понял, что эта аналогия всё-таки плоховата, и да- же не выдерживает никакой критики. Это нововведе- ние очень сильно, в хорошем смысле, усложняет игру, то есть разные тонкости, разные нюансы даёт. Вот это основное отличие. Но давайте ещё скажем, чтобы закончить эту мини- тему, про отличие нард об бэкгеммона. Я переписыва- юсь с разными именно нардистами, в том числе доби- вавшимися успеха в международных соревнованиях. И у меня возникло такое впечатление, что в послед- нее время ситуация в тех же программах, выставлен- ных в Интернете, немножко другая, чем была года 3-4 назад. Там в основном выставляются программы, где хорошо развита игра на деньги. Ну, и соответственно, сайты, на которых играли умнейшие люди мира (я нис- колько не шучу, таким образом действительно можно определять интеллект) – эти сайты постепенно закры- ваются, и появляются сайты, на которых можно в нар- ды поиграть, в бэкгеммон поиграть за деньги. Там тоже есть этот удваивающий куб, то есть это игры, похожие на бэкгеммон, а не на нарды… Александр Гордон. Всё-таки, возвращаясь к вашей программе, от- куда у вас уверенность в том, что она может стать чем- пионом? Борис Мельников. Да, эту мысль надо точнее развить. Мы в на- шем советском варианте обыграли всё, что у нас было. Более того, я высылал всем желающим и продолжаю высылать демонстрационную версию, которая играет- ся так называемым «Джели-фиш» (это широко извест- ная программа, даже в Интернете среди нардистов об- суждается, типа «как я играл в „Джели-фиш“). И мы его обыграли, и ещё парочку программ обыграли. То есть мы берём стабильно больше 55 % очков. Если те же са- мые методы применить к общему бэкгеммону, то есть добавить этот кубик, то выиграем и у всех оставшихся, мы просто ещё не успели это сделать. Александр Гордон. Так. Теперь – что же это за методы? Борис Мельников. Да. Но начнём с другого конца: на чём постро- ены абсолютно все остальные бэкгеммоновские про- граммы, за редчайшим исключением, за исключением, может быть, самых первых программ? Там был такой Берлинер… Может быть, вы про Берлинера расскаже- те? Алексей Радионов. В любых программах фигури- рует такая вещь, как оценка позиции, некоторые оце- ночные функции. Что это такое? В конце партии уже чётко видно, кто победил, кто проиграл – по доске мы можем сказать: да, действительно, такое-то количе- ство очков выиграл один игрок, другой, соответствен- но, другое. Это видно в самом конце игры. А как оце- нить позицию, когда мы ещё до конца игры не до- брались? Здесь, как правило, программа моделирует ходы противников с той целью, чтобы одна сторона стремилась свой выигрыш увеличить, а другая сторо- на стремилась уменьшить выигрыш противника. Вот, собственно, метод минимакса, минимизации и макси- мизации идёт отсюда. Борис Мельников. Но это стандартное. Это ещё пока не имеет от- ношения к недетерминизму. Алексей Радионов. Да. Вот на подсчёте таких чередований мини- мума и максимума получается оценка позиций, кото- рые уже не конечны, где ещё не ясно, кто и что вы- играл, позиций на некоторых промежуточных уровнях, где-то в середине игры. Таким образом программа мо- жет оценить своё положение и принять тот ход, кото- рый либо гарантирует ей выигрыш, либо гарантирует какой-то минимальный проигрыш, то есть не ухудшает ситуацию. В недетерминированных же играх появляется ещё тот фактор, что мы не знаем точно, как сложится игра в дальнейшем, то есть на игру влияют некоторые не от нас зависящие причины. Это либо показания куби- ков (когда мы не можем предсказать, что выпадет зара- нее), либо какие-то другие случайные факторы. В на- шем случае этих случайных факторов, именно пока- заний кубиков, – конечное количество вариантов, не- сколько комбинаций. Мы просматриваем каждую ком- бинацию и смотрим, как будет развиваться игра, если у нас выпали такие-то очки или другие очки, для каждой комбинации это… Александр Гордон. Но это увеличивает количество вариантов в про- грессии… Алексей Радионов. Да, там появляются дополнительные… Борис Мельников. И не только увеличивают количество вариан- тов, кроме того, непонятно, какими алгоритмами здесь пользоваться, и к этим алгоритмам существуют (я сно- ва на Берлинера клоню) разные подходы. Первый подход – это просто случайное моделиро- вание нескольких ветвей позиции, более точно – ни- ти развития игры. Всё-таки русской терминологии нету, поэтому приходится вспоминать и одновременно пере- водить. Это один вариант программы. Но это всё было давно, это самые первые нардовские программы, да- тированные примерно 80-ми, может быть, 90-м годом, но не позже. А после этого все программы – абсолют- но все, я не знаю ни одного исключения среди хоро- ших программ, кроме нашей, – написаны на так назы- ваемой нейросетевой технологии. То есть там вообще, если немножко упрощать ситуацию, фактически и нет никакого метода минимакса. А вся оценка позиции сво- дится к статической. Ещё раз повторю, что я немножко ситуацию упрощаю, но в целом говорю правильно. Александр Гордон. То есть в каждый конкретный момент позиция оценивается как единственно возможная сейчас? Борис Мельников. Да. Алексей Радионов. Здесь некоторые нюансы всё же есть – как раз с этими статическими оценками. Глядя на пози- цию, например, можно сказать, что вот в этой позиции мы гарантированно выиграем столько-то и столько-то. Остался вопрос: как получить эту точную оценку, чтобы она была как можно более адекватна? Но построение оценочной функции с нейросетевым подходом заклю- чается в том, что нейропрограмма, основанная на ней- росети, производит огромное количество партий сама с собой, то есть происходит самообучение, настройка нейросети с той целью, чтобы значение оценки для тех позиций, которые выдаёт нейросеть, было как можно более адекватно. А мера адекватности здесь уже – это количество выигрышей. Борис Мельников. Сейчас я перебью опять. Этот подход и в шахматах осуществляется, хотя я не знаю, насколь- ко успешно он применяются в Deep Thought или в бо- лее совершённых, более новых версиях этого Deep'а (я даже не выучил название последнего Deep'а). Deep Thought – это который обыграл Каспарова, а в следую- щих я даже не знаю, используют это или не использу- ют. Я просто знаю, что в шахматах такой подход тоже есть. Алексей Радионов. Собственно, всё нацелено на получение точ- ной оценки некоторой позиции. И у нас в работе такая же цель преследуется, просто делается это несколько другими методами. Опять же, если вернуться к нейросетевым методам, программа обучает нейросеть, исследователь это ви- дит по специальным характеристикам, по некоторым графикам, по частоте поражений и побед. И когда счи- тается, что нейросеть уже достаточно обучена, про- грамме достаточно перебрать возможные количества случайных исходов, может быть, на один уровень за- глянуть вниз и предусмотреть, как может пойти про- тивник, и, предполагая, что оценка позиции якобы точ- ная, программа уже делает ход. Вот, собственно, та программа, о которой Борис Феликсович уже говорил, «Джели-фиш», при достаточно небольшом количестве нейронов считается одной из самых сильных. Борис Мельников. Её, правда, обыграла «Б-Г-блиц», новая про- грамма, с которой мы хотим потягаться в следующем, 2004-м году и, в общем, уверенность есть, что в грязь лицом не ударим. Александр Гордон. А в чём принципиальная разница построения? Вы тоже используете систему нейросети? Борис Мельников. Так вот как раз и нет. Мы используем свой под- ход, этот подход можно, если совсем кратко, охарак- теризовать таким образом. То есть почему, например, меня перестали интересовать шахматы, хотя в юности я добивался каких-то успехов? То есть я развёрнуто отвечаю на ваш вопрос. Окончательно я их забросил к 25 годам, потому что достиг своего потолка, потому что больше чем кандидатом в мастера мне было не стать. Почему? Потому что у меня гораздо хуже, чем у мо- их сверстников, которые стали кандидатами в мастера не в 25, скажем, а в 17 лет, работает левое «пересчет- ное» полушарие. Я в пересчёте вариантов совершен- но слаб, несмотря на то, что до поры до времени играл с ними совершенно на равных. Это я осознал к годам к 25-ти. А тут я одновременно стал и сам экспертом в нар- дах. Я понял, что в играх вроде нард, не меньше чем левое используется и правое полушарие, то есть неко- торые вещи совершенно невозможно объяснить – по- чему одна позиция лучше другой, то есть возможно только, как я полушутя говорю, правополушарное объ- яснение. И что-то подобное я и ввожу в свои программы. Где можно, я это пытаюсь программировать, алгоритмизи- ровать, но не всегда это получается. То есть иногда именно в программах что-то совершенно невозможно объяснить. Именно в программах, именно в написан- ных текстах программы, опять же выражаясь полушу- тя, работает правое полушарие. Здесь что-то работает, программа работает, программа выдаёт хорошие ре- зультаты, и не только в программировании игр, но и в задачах дискретной оптимизации. Александр Гордон. А как, вы не знаете? Борис Мельников. А почему – не знаю. Александр Гордон. То есть вы программируете работу правого по- лушария правым полушарием и в результате получа- ется хорошая программа. Борис Мельников. Да, да, да, так иногда оно и есть. Но кое-что всё- таки можно объяснить. И как раз это объяснение и есть предмет нескольких статей, которые мы с соавторами написали, и не только про программирование игр, но и про разные другие задачи дискретной оптимизации. Кстати, не все специалисты в искусственном интел- лекте принимают эти статьи, были очень серьёзные возражения. В частности, одно из возражений можно кратко сформулировать таким образом: совершенно не объясняется никаких новых моментов, которые про- граммируются, то есть никаких новых идей, связанных с искусственным интеллектом не объясняется. А мне кажется, что всё-таки в программировании, в эвристи- ческом программировании вообще, не обязательно в программировании игр, важен конечный, конкретный результат. И когда он достигается, когда он лучше, чем при другом подходе, когда в том, что он лучше, можно убедить даже неспециалиста – это и есть решение, и это может быть значительно более важно, чем форму- лировка какого-то нового метода. Александр Гордон. Но это, извините, уже искусство. Борис Мельников. Может быть. Так игра в шахматы, в нарды тоже многими сравнивается с искусством. Но сейчас, может быть, стоит перейти к тому, что ал- горитмизуется работой правого полушария, и что на- шло отражение в программах и для игры в нарды, и в других задачах дискретной оптимизации – это динами- ческая оценка позиции, даже лучше сказать, примене- ние динамически генерируемых функций риска. Может быть, об этом вы расскажете подробнее? Алексей Радионов. Про статические оценки я коротко уже говорил. В недетерминированных играх, благодаря этой неде- терминированности, мы не знаем точно, что у нас по- лучится, и мы перебираем всевозможные случайные исходы. Выпали у нас показания кубиков такие-то, мы получаем такой-то прогноз, следующий – следующий прогноз. Итак, мы для каждого исхода случайного со- бытия имеем какую-то коллекцию прогнозов, каких-то построенных статических оценок. А как оценить вообще ситуацию для всех случайных исходов? В какую ветвь пойти нам при принятии реше- ния? Здесь можно либо просто усреднять, то есть по- лучать среднеарифметическое математическое ожи- дание и где оно нас устраивает, туда и идти. Но это не всегда бывает оправдано. Оправданным оказался подход с функцией риска – этот набор прогнозов мы усредняем, но специальным образом. Борис Мельников. Сейчас я опять перебью на секунду. Набор прогнозов можно рассматривать как вектор аргумента функций. Это не совсем правильное название, и мате- матики могут за него поругать, но это близко к истине. Алексей Радионов. Тем более там размерность нефиксированная получается. Это специальное усреднение основывается на весо- вой функции, которая у нас называется «функция рис- ка» и которая также подбирается специальным обра- зом. А подбирается она так. Если у нас дела идут в го- ру… Борис Мельников. Давайте я снова вас перебью. Итак, есть у нас набор значений статической оценки позиции. И вот эти наборы значений как-то распределены, условно гово- ря, на отрезке от минус единицы до единицы. То есть, минус единица – самый плохой результат, единица – самый хороший, это результат, зависящий от выпаде- ния кубиков. Ну, опять же, если снова говорить про бэк- геммон, про нарды, тут можно сказать, что у нас либо 21 вариант, если показания кубиков 5,6 и 6,5 считать одинаковыми, либо говорить, что 36 вариантов, если их считать разными, но это дело не меняет. Главное, что некоторое количество вариантов тут распределено. И действительно, у нас могут быть и очень хорошие, и очень плохие показания кубиков. То есть в реальных партиях, в реальных оценках пози- ции распределение этого вектора – от минус до плюс единицы. Как усреднять? Алексей говорил, что можно среднеарифметически, но лучше не так, лучше усред- нять с помощью, как он тоже начал говорить, функции риска. Что это такое. На отрезке от минус до плюс еди- ница проводится какая-то функция, и наши аргументы получают временные значения, равные высоте стол- биков ординат этой функции в нужных абсциссах. Я не очень красиво выразился, может, вы меня поправите? Алексей Радионов. Каждому прогнозу, каждой оценке как бы припи- сывается свой вес. Борис Мельников. Равный значению этой функции риска. А аб- сцисса там, где она и находится. Алексей Радионов. Потом эта система взвешивается, ищется центр тяжести. Борис Мельников. Центр тяжести – вот она главная оценка! То есть, то, чего мы не нашли ни в каких других програм- мах. Во-первых, мы применили эту оценку в задачах дис- кретной оптимизации. В общем-то, может быть, это от- дельный разговор, причём здесь задача дискретной оптимизации. Причём, например, здесь так называе- мая «задача коммивояжёра», когда там никакого неде- ретминизма нет. Есть – причём те же самые алгоритмы применяются. И там получаются достаточно хорошие результаты. Но раз уж я об этом заговорил, ещё пару слов ска- жу. Здесь неизвестность, недетерминизм, то есть неиз- вестные заранее показания кубиков. А там неизвест- ные заранее исходы, то есть продолжение пересчёта какой-то матрицы, достаточно большой. Мы можем де- лать только прогнозы, как пойдёт этот расчёт. И вот есть программы-эксперты, которые делают эти прогно- зы. То есть здесь неизвестность, а там… Ну, может быть, тоже неизвестность, полученная от разных про- гнозов. То есть те же самые приёмы применяются на- ми в классических задачах дискретной оптимизации. Александр Гордон. В казино не хотите в рулетку играть с этим под- ходом? Борис Мельников. Нет, но один из результатов этого подхода – предсказание курса валют, которые мы безуспешно всё пытаемся куда-нибудь пристроить. Но этих про- грамм-предсказателей немереное количество. Александр Гордон. Насколько аккуратны ваши действия? Борис Мельников. Предсказать какой-то катаклизм вроде нашего кризиса 98-го года, видимо, никому не удавалось и не удастся, а доказать, что наша программа лучше, на ка- ком-то более простом примере нам пока не удаётся. Но, в общем-то, это тоже не ставится как цель. Полу- чить отсюда прибыль, коммерческий эффект, это вто- рое, третье дело. Пока не получается. Получится – хо- рошо. Не получится – не страшно. Я всё-таки вижу основную цель в том, чтобы этот подход ввести в про- граммирование игр, в другие задачи. Победить – дай Бог – на следующем чемпионате мира, 2004 года. Александр Гордон. Можно ещё чуть подробнее, что такое «центр тя- жести» в данном случае, потому что я понял, но не до конца. Ещё раз можете объяснить, что такое принцип динамического подхода, присвоение веса и так далее? Алексей Радионов. То, что мы для каждого исхода случайного со- бытия имеем какую-то числовую величину – это просто набор прогнозов на будущее. Нам этот набор не делает погоды, из него надо получить какую-то одну величи- ну, одно значение, которое всю ветвь, которая следует за случайными событиями, оценивает приемлемой ве- личиной, основываясь на которой мы сделаем реше- ние – ходить нам так или предпочесть другой вариант. Так вот, на основе чего получается общая оценка это- го набора прогнозов? Каждую точку, каждую величину, грубо говоря, можно представить шариком на стержне. Стержень у нас длиной от минус единицы до единицы, минус единица – это значит, что дела для нас очень плохо пойдут. Единица – что очень хорошо, мы побе- дители. На этот стержень нанизаны шарики. Каждый на своём расстоянии от нулевой точки. Это расстояние соответствует значению прогноза. Теперь мы подбираем массу этих шариков, а масса этих шариков подбирается согласно функции риска. Борис Мельников. Чем больше значение этой функции в данной точке, тем больше масса шарика. Алексей Радионов. А потом этот стержень уравновешиваем и нахо- дим положение центра тяжести. Борис Мельников. Это, видимо, лучше объяснение, чем моё… Александр Гордон. Оно доступнее, да. Алексей Радионов. Этот центр тяжести, его положение, мы считаем величиной, которая… Александр Гордон. Оптимальной величиной, которая позволяет сделать… Алексей Радионов. Не сказать, чтобы оптимальной, это просто ха- рактерная величина, которая более-менее описывает куст с этими случайными событиями. И мы её прини- маем в качестве оценки. Борис Мельников. Давайте тогда следующий шаг сделаем. Это был первый шаг нашей оценки, именно на этом мы по- лучили достаточно хорошую программу, которая, прав- да, всё-таки была хуже этого «Джели-фиша» пресло- вутого. Следующий шаг такой. Эти функции риска, мы, как правило, брали, условно говоря, пессимистические – человек в жизни должен быть хоть немного песси- мистом и ожиданиям плохого придавать больший вес, чем ожиданию хорошего. Александр Гордон. То есть вы определяли себя игроком хуже, чем ваш партнёр? Борис Мельников. Нет, не так: плохие показания кубиков мы ожи- дали с большей вероятностью, чем хорошие показа- ния кубиков. В общем, это, наверное, естественно – когда мы идём гулять, совершенно ничего не зная про прогноз погоды, то, наверное, зонтик всё-таки стоит брать. Здесь фактически то же самое. И уже на этом мы подбирали разные виды этих функ- ций риска. Уже здесь мы почти вплотную приблизи- лись к «Джели-фишу». Если мы сейчас у него выигры- ваем (ещё раз повторяю, на нашем российском вари- анте нард) где-то 55 процентов, может, чуть побольше, тогда мы проигрывали столько же. Но это уже было хорошо. Выигрываем на убывающих функциях риска. Убывающих – это означает, что мы хоть немного, да пессимисты. Следующий шаг, про который я никак не начну го- ворить, такой. Всё-таки бывают ситуации, когда надо быть оптимистами, редко, но бывают. А, может быть, не очень редко. Что это такое? Это когда мы сильно проигрываем. То есть когда положение заведомо не в нашу пользу, всё равно нам проигрывать. Здесь нет ва- рианта проиграть слишком много. (Немножко отвлека- ясь, в бэкгеммоне есть разные варианты проигрыша, но, как правило, об этом в конкретной позиции речь не идёт.) Если идёт речь о том, чтобы проиграть либо одно очко, либо, может быть, всё-таки выиграть, нам надо строить оптимистическую функцию риска, которая бы учитывала вероятность выпадения нам хороших пока- заний кубиков. Тогда эти вероятности надо сильно уве- личить. Почему? Русская пословица есть – утопающий хватается за соломинку. Александр Гордон. Речь идёт о стратегии игры? Борис Мельников. Да, конечно. Но откуда известно, как мы стоим – хорошо или плохо? Например, по той же самой ста- тической оценке позиции, во-вторых, по динамической оценке позиции, взятой с какой-нибудь простой функ- ции риска. Вот это всё приводит к динамическому вы- бору функции риска. Примерно выбрав, как мы стоим, выигрыш, проигрыш или в серединке, мы за счёт этого динамически строим функцию риска. Например, когда априорно позиция примерно равна, эта функция рис- ка действительно немножко убывает. То есть она по- хожа на линейную функцию, константу, которая от ми- нус единицы до плюс единицы убудет, начиная со зна- чения единицы, примерно до одной второй. Пример- но такая функция риска, убывающая, немножко песси- мистическая, соответствует тому, что – пойдёт дождик или не пойдёт дождик – зонтик мы возьмём. Если же мы заведомо проигрываем, функция рис- ка сильно возрастает. Если же мы выигрываем очень сильно, то мы должны быть сверхпессимистами и очень плохие прогнозы предполагать с гораздо боль- шими вероятностями. И функция риска будет стано- виться функцией сверхпессимиста. И в зависимости от такого предварительного подсчёта, предварительной генерации, мы и строим динамическую функцию риска. Поскольку я постоянно делаю шаги в другие задачи дискретной оптимизации, то я здесь сделаю ещё один. Например, некоторые программы-эксперты высчиты- вают время, оставшееся до получения хорошего отве- та (не обязательно оптимального, но близкого к опти- мальному) в какой-нибудь задаче дискретной оптими- зации, например, в той же самой пресловутой «зада- че коммивояжёра» или в минимизации конечных ав- томатов – тоже одна из моих любимых задач. И раз- ные программы-эксперты оценивают: если в среднем эти программы дают время вычисления, которое очень высоко, гораздо больше, чем если мы пойдём по дру- гой ветке вычислений, то мы здесь применим какую-то оптимистическую функцию риска. Если время будет, наоборот, слишком маленькое, то пессимистическую. Это всё имеет выход в другие задачи дискретной опти- мизации. Александр Гордон. Это то, что у игрока называется интуицией во время игры. Борис Мельников. Да. Это второй шаг – он самый главный. Пер- вым шагом было введение функции риска, вторым – динамической функции риска. Есть и третий шаг, кото- рый тоже может быть важен, хотя менее важен, чем второй. Это применение несколько раз подряд этих функций риска, потому что после первого применения мы немножко уточняем оценку позиции. А раз немнож- ко уточняем оценку позиции, то можем немножко бо- лее определённо сказать – мы пессимисты или опти- мисты. А в следующий раз мы ещё более определённо будем говорить, ещё раз и ещё раз. Казалось бы, что это очень долгие вычисления, но нет – по сравнению со всем остальным объёмом вы- числения, связанного с получением статических оце- нок позиции, с организацией перебора и так далее. Это неоднократное применение функции риска, динамиче- ская функция риска, фактически совершенно не зани- мает времени, то есть там какие-то доли процента – даже, кажется, мы и не считали, какие именно доли процента. Даёт ли этот третий шаг большой выигрыш по сравнению только со вторым? Я затрудняюсь ска- зать, но раз без каких бы то ни было усилий мы можем получить какое-то преимущество, то, наверное, даёт. Дело в том, что у меня описаны примеры имен- но конкретных реализаций, статистических оценок по- зиций, когда это должно дать преимущество, должно дать плюсы. Но насколько часто эти примеры проявля- ются в нардах – я сказать затрудняюсь. Александр Гордон. Вы сами у своей программы выигрываете? Борис Мельников. Проигрываю. Это, кстати, интересный вопрос, хорошо, что он возник, было бы плохо, если бы он не возник. Я в нардах специалист, но, конечно, условно говоря, не гроссмейстер. Хотя, может быть, моя квали- фикация в нардах и выше, чем была моя квалифика- ция в шахматах, когда я ещё играл – кандидат в масте- ра. Вот здесь интересный момент – почему я проигры- ваю? Я всё-таки человек, и поддаюсь иногда азарту, хотя, конечно, в казино не хожу и только в дурном сне могу представить, что я в казино пойду. Там от меня ничего не зависит, там просто фишки, как выпадут, так и выпадут. А здесь от меня зависит, от моего интеллек- та. И всё-таки я азарту поддаюсь. Например, если я два хода назад стоял хорошо, на выигрыш, но что-то слу- чилось, плохо кубики упали, и я начал стоять плохо. Я просто по инерции продолжаю у себя в мозгу приме- нять пессимистическую функцию риска, оценивая по- зицию, чего, конечно, делать не надо. Программа же быстрее переключается и быстрее понимает, что всё не так хорошо происходит, как есть на самом деле, и программа переключается, например, от пессимисти- ческой к оптимистической функции риска, переключа- ется гораздо быстрее чем я. Алексей Радионов. Тут, наверное, стоит ещё заметить, что програм- ма, в которой реализованы эти алгоритмы, но в кото- рой не подобраны числовые коэффициенты (когда пе- реключаться на какую стратегию, как, собственно, ста- тично оценивать позицию, хорошая она или плохая), эта программа не является рабочей. Чтобы она зара- ботала, необходимо её обучить. Обучение программы происходит, когда она играет сама с собой, тогда про- исходит, собственно, подгонка параметров таким обра- зом, чтобы максимально улучшить качество игры, мак- симально повысить вероятность выигрыша. Но здесь возникает уже другой вопрос – каким обра- зом её учить? Если в играх сама с собой, то, наверное, это будет немного необъективно, так как в данном слу- чае отношения не транзитивны: если программа вы- играла у другой программы, а другая у третьей, то не обязательно, что первая выиграет у третьей. И выбор системы обучения – тоже очень интересная пробле- ма. И, собственно, если её грамотно решить, то можно действительно надеяться на то, что получится продукт, который в 2004 году станет играть на должном уровне. Александр Гордон. То есть эту проблему вы ещё не решили? Борис Мельников. Решаем… всё-таки можно даже сказать, что ре- шили. Здесь мы касаемся темы, о которой ещё сегодня не говорили. Это не нейросети, их мы очень мало при- меняем здесь. А это так называемые генетические ал- горитмы. В научной литературе им посвящено гораз- до меньше публикаций, чем нейросетям. Мне кажется – незаслуженно. Потому что и то, и другое – это аль- тернативный подход к эвристическому программиро- ванию. Чистые математики объясняют это так, что ней- росети – это математически объяснимо, может быть математически доказано, а генетические алгоритмы – якобы нет. И приводят ссылки на работу Колмого- рова-Арнольда, работу 50-х годов – но мне кажется, что для практического программирования эта работа представляет весьма малый интерес. И то, и другое, это разные альтернативы, разные подходы к эвристи- ческому программированию. Наша «функция риска» – это тоже подход. Просто надо всё применять в разум- ных примерах, в разумных количествах. Вот здесь возникает именно задача самообучения набора коэффициентов, среди которых, кроме всего прочего, коэффициенты самообучения функций риска, не только коэффициенты для оценки позиций, но и ко- эффициенты функций риска. Мне, по крайней мере, неизвестно хороших публикаций (чуть ли вообще ника- ких) про самообучение этих наборов коэффициентов. Есть, либо есть стандартный подход генетических ал- горитмов, в котором тоже много не совсем правильно- го, либо просто, как в упомянутых книжках Вельского с компанией, сказано: «Было произведено самообуче- ние». Было, хорошо было произведено, раз програм- ма хорошая, раз, отставая в 70-х годах от американцев по технике, на той же самой технике «Каисса», победи- ла. Значит, было хорошо самообучение произведено, но как оно было произведено, никакой теории по этому поводу не было. Александр Гордон. Получается, что в вашем случае, при ваших ал- горитмах решения, самообучение важнее, чем в слу- чае программ, которые строятся на нейросетях. Или я ошибаюсь? Алексей Радионов. В нейросетях как раз всё построено на самооб- учении… Борис Мельников. Но там своё самообучение… Алексей Радионов. Нейросеть нужно настроить, чтобы она игра- ла. Это производится за счёт самообучения, иначе это просто будет… Александр Гордон. Я неправильно задал вопрос. Что вам важнее – выбрать метод обучения программы или… Грубо гово- ря, у вас ребёнок непослушный, непредсказуемый… Алексей Радионов. Скажем так, это вопрос важный – вопрос вы- бора метода самообучения. Важный в чём? Нужно не просто чтобы программа сама с собой играла, а что- бы было много экземпляров такой программы, каждый немного по-своему настроенный. И вот эта вся тол- па, играя друг с другом, устраивает турниры, выбирает победителя. Необходимо найти критерий, по которому решается, кто из них победитель. Собственно, кажет- ся, это и есть швейцарская система? Борис Мельников. Да, в общем-то, это что-то похожее на швей- царскую систему. Потом это было немножко изменено, но это не настолько всё-таки важно, чтобы так подроб- но об этом говорить. Здесь лучше, наверное, вспомнить ещё одну вещь, которая только начала встраиваться в программу. В классической теории Адельсона-Вельского програм- ма, когда думает, за противника думает так же, как за себя. То есть на место противника ставит саму себя. Ещё один приём, который мы применяли – ставить на место противника не себя, а нечто другое, нечто бо- лее сложное, нечто более сильное. Потому что у нас- то есть действительно толпа (это такой жаргонный тер- мин – толпа игроков), толпа объектов для самообуче- ния. Это применяется, ещё раз скажу, и в других за- дачах дискретной оптимизации. И можно всегда взять того, который лидирует, в качестве условного против- ника, то есть программа, играя, в качестве условного противника берёт лидера. Что ещё можно? Ещё только начаты работы в том направлении, чтобы программа пыталась, пока про- тивник думает, начать думать за противника и стара- лась подобрать к противнику свои критерии работы. То есть пыталась представить саму себя на месте против- ника, и если у неё это получается, она на месте это- го виртуального противника подставляет саму себя со своими коэффициентами. Вот это была бы очень инте- ресная тема. Но она, как я уже сказал, только начата, и сказать, насколько она реально применяется в про- граммах, я вам пока не могу. Александр Гордон. Ну что ж, мне осталось вам пожелать удачи в 2004 году. И если победите, то приходите рассказать о том, как это было. Борис Мельников. Спасибо! Обзор темыДо сих пор не изжито представление о том, что можно создать искусственный интеллект как синоним искусственного разума. Но об этом и речи быть не может по целому ряду принципиальных соображений. Специалисты говорят исключительно об одном из важнейших направлений в информатике и математике, связанном с имитацией или моделированием на ЭВМ отдельных творческих процессов. Эта область науки мало интересуется тем, что происходит в человеческом мозгу, а занята построением ЭВМ и их программ, позволяющих воспроизвести отдельные процессы, по нашим человеческим оценкам — творческие. Шахматист, делая тот или иной ход, может руководствоваться прецедентами, прошлым опытом, умением, интуицией, догадкой, просмотром на сколько-то ходов вперед. Не все это формализуется. Зато мы в точности знаем, как это делает ЭВМ, так как человек составил для нее программу-инструкцию, позволяющую количественно оценивать ту или иную ситуацию. В машине играет в шахматы не программа, а тот человек, который сумел формализовать шахматную игру и составить программу. Рассмотрим некоторые эвристики, применяемые при программировании игр — естественно, речь идет об интеллектуальных играх, а не о значительно более популярных в настоящее время динамических играх, рассчитанных, в первую очередь, на быстроту реакции пользователя, и лишь во вторую (или даже в последнюю) — на его интеллект. Эвристики — это специальные методы, используемые в процессе открытия нового. Второе значение термина «эвристика» — наука, изучающая продуктивное творческое мышление. В качестве типичного примера интеллектуальной игры чаще всего называют шахматы. И это не случайно — при программировании огромного количества интеллектуальных игр используются те же самые модели, что и в шахматах. Математическое исследование этих моделей, обобщение накопленного к концу 70-х годов опыта уже сделано, а то, что было создано впоследствии, пока еще нуждается в подобном фундаментальном труде. По мнению Б. Ф. Мельникова, в литературе, посвященной искусственному интеллекту вообще и программированию интеллектуальных игр в частности, шахматам (и «аналогичным’ простым играм) уделено слишком большое внимание. Более того, о шахматах утвердилось мнение как о самой интеллектуальной игре, когда-либо изобретенной человеком. Математики проводят аналогии между мышлением шахматиста и математика, экономисты говорят о помощи шахматного мышления для работы „на рынке ценных бумаг“, психологи — о его помощи в разных жизненных ситуациях… Однако Б. Ф. Мельников придерживается особого мнения. Он считает, что человечество сделало ошибку, назвав именно шахматы самой интеллектуальной игрой. Ученый считает такой игрой Backgammon, почти не отличающийся от известной в России (и других странах бывшего СССР) игры „короткие нарды“. При игре в Backgammon человек занимается не только прямым пересчетом, но и — в значительно большей степени, чем при игре в шахматы — качественной оценкой позиции; за последнюю же, по-видимому, „отвечает“ правое полушарие мозга — следовательно, оба полушария в этом случае „задействованы“ полностью. Все-таки шахматы не случайно так часто упоминаются. При программировании огромного количества интеллектуальных игр используются те же самые модели, что и в шахматах. Среди таких игр можно назвать реверси, калах, оуа, рэндзю, разные (национальные) версии шашек. Стоит еще упомянуть различные игры, рассматривавшиеся М. Гарднером — в заметках, публиковавшихся в течение нескольких десятилетий в журнале „Scientific American“, а также в его книгах, некоторые из которых переведены и на русский язык. Большинство указанных игр — детерминированные; таковых в упомянутых книгах несколько десятков, тогда как недетерминированных — существенно меньше. Отметим, однако, что не во всех детерминированных играх можно использовать „шахматные“ модели, эти модели неприменимы при игре в го (эту игру часто неудачно называют японскими шашками). В различных национальных версиях шашек, для получения очень сильных программ часто достаточно использовать те же самые модели, что и в шахматах, но в значительно более простом виде. Например, программы разных версий 64-клеточных шашек обыграли действующих чемпионов мира в 60-х годах, что на 30 и более лет раньше, чем в шахматах. Кроме того, многие из методов дискретной оптимизации в задачах программирования недетерминированных интеллектуальных игр, которые будут описаны ниже, могут быть применены и в „обычных“, детерминированных играх. Кроме того, эти же методы применяются автором и в других задачах искусственного интеллекта. Карточные игры — причем все — в советское время были отнесены к „азартным“; при этом многие из них (в первую очередь такие недетерминированные игры как преферанс и бридж) совершенно несправедливо. К сожалению, это отношение перешло и на отечественные работы, связанные с программированием игр. Итак, обзор посвящен прежде всего эвристикам, применявшимся в программировании недетерминированных игр — и поэтому (в связи с наличием эвристик, желательность применения которых практически невозможно доказать строго) может быть раскритикован представителями чистой математики. Однако, в настоящее время подобная ситуация прослеживается практически во всех областях искусственного интеллекта. Динамическая оценка позиции. В чем же главное отличие недетерминированных игр от детерминированных с точки зрения программирования? В том, что дерево игры, построенное для первых, включает не только вершины, в которых игрок должен выбрать конкретный ход, но и другие — те, в которых ему следует ожидать некоторой конкретной реализации случайного события. Поэтому метод минимакса при программировании перебора в недетерминированных играх приходится обобщать. Будем исходить из предположения автора, что сам „канонический“ метод минимакса читателю известен. В недетерминированных играх чередуются: конкретная реализация некоторого случайного события, ход одной из сторон, снова реализация случайного события, ход другой стороны. Количество всевозможных исходов случайного события должно быть конечным (иначе придется применять другие модели). В результате в дереве игры появляются уровни, заключенные между уровнями очередности ходов соперников. Эти новые уровни отражают те моменты игры, в которые реализуется исход случайного события. Обобщение метода минимакса работает именно с таким деревом. Итак, считаем, что мы умеем строить статическую оценку позиции. Временным удалением недетерминированности получаются предварительные оценки позиций дерева игры. Для этого мы сначала предполагаем, что уже реализовался конкретный исход случайного события, и вычисляем динамическую оценку для данной позиции так же, как и в „обычном“ методе минимакса. Затем вычисляем динамическую оценку позиции для следующего исхода случайного события, и так далее для всех исходов. Окончательная динамическая оценка позиции определяется на основе всех детерминированных оценок, полученных для всех возможных значений случайного события. Полученные значения детерминированных (обычно — статических) оценок специальным образом усредняются — это и есть окончательная динамическая оценка. С физической точки зрения такое усреднение дает положение центра тяжести одномерной системы тел с массами, определяемыми специально подобранной функцией (функцией риска). Координаты тел системы — значения соответствующей детерминированной оценки, которая определяется только детерминированными факторами игры, как, например, в обычном минимаксе. Например, пусть a1,…, ak — значения детерминированных оценок, а f — некоторая функция риска. Тогда значение динамической оценки вычисляется по следующей формуле: Даже программа, написанная только на основе этого обобщения и имеющая самую тривиальную функцию статической оценки позиции, давала неплохие результаты — обыгрывала многие (но не все) программы. Но такие результаты, конечно же, нельзя назвать очень хорошими. В дальнейшем программа постепенно улучшалась. По мнению Б. Ф. Мельникова, все работы по улучшению можно было кратко охарактеризовать следующим образом: в них оптимизировался какой-либо способ вычисления статической оценки позиции. Автор пошел иным путем — и некоторые из направлений улучшения программы, примененные после введения простейшей динамической оценки, описаны ниже. Автоматическая смена стратегии. Отметим, что описанные далее приемы и алгоритмы могут быть реализованы, например, с помощью нейросетей. Однако в данном случае используемые здесь алгоритмы позволяют обходиться и без них, существенно упрощая работу практического программирования. Материал этого пункта не связан с автоматическим изменением набора правил, применяемых при выборе очередного хода, — работа над этой темой является задачей обозримого будущего. Однако название раздела не является преувеличением: изменение специальных коэффициентов — не являющихся коэффициентами статической оценки позиции — действительно приводит к изменению стратегии игры программы. Перед описанием таких алгоритмов рассмотрим немного подробнее, почему обобщение метода минимакса для недетерминированных игр действительно стоит формулировать именно так, как это сделано в разделе „Динамическая оценка позиции“. Покажем, что это обобщение следует из реального мышления игрока, проявляющегося далеко не только в какой-либо недетерминированной игре, но и, по большому счету, в иных различных жизненных ситуациях. Действительно, человек чаще всего не самые удачные реализации случайных факторов (в backgarnmon’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 Тема № 262(37)
|
Вспомнить все. Советские вокально-инструментальные ансамбли
Рим не сразу строился
Kapukikanuki. Подборка роликов для изучения алфавита
Шаровая молния
Интеллект-видео. 2010. RSS
|
|