То есть почему, например, меня перестали интересовать шахматы, хотя в юности я добивался каких-то успехов? То есть я развёрнуто отвечаю на ваш вопрос. Окончательно я их забросил к 25 годам, потому что достиг своего потолка, потому что больше чем кандидатом в мастера мне было не стать. Почему? Потому что у меня гораздо хуже, чем у моих сверстников, которые стали кандидатами в мастера не в 25, скажем, а в 17 лет, работает левое «пересчетное» полушарие. Я в пересчёте вариантов совершенно слаб, несмотря на то, что до поры до времени играл с ними совершенно на равных. Это я осознал к годам к 25-ти.
А тут я одновременно стал и сам экспертом в нардах. Я понял, что в играх вроде нард, не меньше чем левое используется и правое полушарие, то есть некоторые вещи совершенно невозможно объяснить - почему одна позиция лучше другой, то есть возможно только, как я полушутя говорю, правополушарное объяснение.
И что-то подобное я и ввожу в свои программы. Где можно, я это пытаюсь программировать, алгоритмизировать, но не всегда это получается. То есть иногда именно в программах что-то совершенно невозможно объяснить. Именно в программах, именно в написанных текстах программы, опять же выражаясь полушутя, работает правое полушарие. Здесь что-то работает, программа работает, программа выдаёт хорошие результаты, и не только в программировании игр, но и в задачах дискретной оптимизации.
А.Г. А как, вы не знаете?
Б.М. А почему - не знаю.
А.Г. То есть вы программируете работу правого полушария правым полушарием и в результате получается хорошая программа.
Б.М. Да, да, да, так иногда оно и есть. Но кое-что всё-таки можно объяснить. И как раз это объяснение и есть предмет нескольких статей, которые мы с соавторами написали, и не только про программирование игр, но и про разные другие задачи дискретной оптимизации.
Кстати, не все специалисты в искусственном интеллекте принимают эти статьи, были очень серьёзные возражения. В частности, одно из возражений можно кратко сформулировать таким образом: совершенно не объясняется никаких новых моментов, которые программируются, то есть никаких новых идей, связанных с искусственным интеллектом не объясняется. А мне кажется, что всё-таки в программировании, в эвристическом программировании вообще, не обязательно в программировании игр, важен конечный, конкретный результат. И когда он достигается, когда он лучше, чем при другом подходе, когда в том, что он лучше, можно убедить даже неспециалиста - это и есть решение, и это может быть значительно более важно, чем формулировка какого-то нового метода.
А.Г. Но это, извините, уже искусство.
Б.М. Может быть. Так игра в шахматы, в нарды тоже многими сравнивается с искусством.
Но сейчас, может быть, стоит перейти к тому, что алгоритмизуется работой правого полушария, и что нашло отражение в программах и для игры в нарды, и в других задачах дискретной оптимизации - это динамическая оценка позиции, даже лучше сказать, применение динамически генерируемых функций риска. Может быть, об этом вы расскажете подробнее?
А.Р. Про статические оценки я коротко уже говорил. В недетерминированных играх, благодаря этой недетерминированности, мы не знаем точно, что у нас получится, и мы перебираем всевозможные случайные исходы. Выпали у нас показания кубиков такие-то, мы получаем такой-то прогноз, следующий - следующий прогноз. Итак, мы для каждого исхода случайного события имеем какую-то коллекцию прогнозов, каких-то построенных статических оценок.
А как оценить вообще ситуацию для всех случайных исходов? В какую ветвь пойти нам при принятии решения? Здесь можно либо просто усреднять, то есть получать среднеарифметическое математическое ожидание и где оно нас устраивает, туда и идти. Но это не всегда бывает оправдано. Оправданным оказался подход с функцией риска - этот набор прогнозов мы усредняем, но специальным образом.
Б.М. Сейчас я опять перебью на секунду. Набор прогнозов можно рассматривать как вектор аргумента функций. Это не совсем правильное название, и математики могут за него поругать, но это близко к истине.
А.Р. Тем более там размерность нефиксированная получается.
Это специальное усреднение основывается на весовой функции, которая у нас называется «функция риска» и которая также подбирается специальным образом. А подбирается она так. Если у нас дела идут в гору…
Б.М. Давайте я снова вас перебью. Итак, есть у нас набор значений статической оценки позиции. И вот эти наборы значений как-то распределены, условно говоря, на отрезке от минус единицы до единицы. То есть, минус единица - самый плохой результат, единица - самый хороший, это результат, зависящий от выпадения кубиков. Ну, опять же, если снова говорить про бэкгеммон, про нарды, тут можно сказать, что у нас либо 21 вариант, если показания кубиков 5,6 и 6,5 считать одинаковыми, либо говорить, что 36 вариантов, если их считать разными, но это дело не меняет.
Главное, что некоторое количество вариантов тут распределено. И действительно, у нас могут быть и очень хорошие, и очень плохие показания кубиков. То есть в реальных партиях, в реальных оценках позиции распределение этого вектора - от минус до плюс единицы. Как усреднять? Алексей говорил, что можно среднеарифметически, но лучше не так, лучше усреднять с помощью, как он тоже начал говорить, функции риска. Что это такое. На отрезке от минус до плюс единица проводится какая-то функция, и наши аргументы получают временные значения, равные высоте столбиков ординат этой функции в нужных абсциссах. Я не очень красиво выразился, может, вы меня поправите?
А.Р. Каждому прогнозу, каждой оценке как бы приписывается свой вес.
Б.М. Равный значению этой функции риска. А абсцисса там, где она и находится.
А.Р. Потом эта система взвешивается, ищется центр тяжести.
Б.М. Центр тяжести - вот она главная оценка! То есть, то, чего мы не нашли ни в каких других программах.
Во-первых, мы применили эту оценку в задачах дискретной оптимизации. В общем-то, может быть, это отдельный разговор, причём здесь задача дискретной оптимизации. Причём, например, здесь так называемая «задача коммивояжёра», когда там никакого недеретминизма нет. Есть - причём те же самые алгоритмы применяются. И там получаются достаточно хорошие результаты.
Но раз уж я об этом заговорил, ещё пару слов скажу. Здесь неизвестность, недетерминизм, то есть неизвестные заранее показания кубиков. А там неизвестные заранее исходы, то есть продолжение пересчёта какой-то матрицы, достаточно большой. Мы можем делать только прогнозы, как пойдёт этот расчёт. И вот есть программы-эксперты, которые делают эти прогнозы. То есть здесь неизвестность, а там… Ну, может быть, тоже неизвестность, полученная от разных прогнозов. То есть те же самые приёмы применяются нами в классических задачах дискретной оптимизации.
А.Г. В казино не хотите в рулетку играть с этим подходом?
Б.М. Нет, но один из результатов этого подхода - предсказание курса валют, которые мы безуспешно всё пытаемся куда-нибудь пристроить. Но этих программ-предсказателей немереное количество.
А.Г. Насколько аккуратны ваши действия?
Б.М. Предсказать какой-то катаклизм вроде нашего кризиса 98-го года, видимо, никому не удавалось и не удастся, а доказать, что наша программа лучше, на каком-то более простом примере нам пока не удаётся. Но, в общем-то, это тоже не ставится как цель. Получить отсюда прибыль, коммерческий эффект, это второе, третье дело. Пока не получается. Получится - хорошо. Не получится - не страшно. Я всё-таки вижу основную цель в том, чтобы этот подход ввести в программирование игр, в другие задачи. Победить - дай Бог - на следующем чемпионате мира, 2004 года.
А.Г. Можно ещё чуть подробнее, что такое «центр тяжести» в данном случае, потому что я понял, но не до конца. Ещё раз можете объяснить, что такое принцип динамического подхода, присвоение веса и так далее?
А.Р. То, что мы для каждого исхода случайного события имеем какую-то числовую величину - это просто набор прогнозов на будущее. Нам этот набор не делает погоды, из него надо получить какую-то одну величину, одно значение, которое всю ветвь, которая следует за случайными событиями, оценивает приемлемой величиной, основываясь на которой мы сделаем решение - ходить нам так или предпочесть другой вариант. Так вот, на основе чего получается общая оценка этого набора прогнозов? Каждую точку, каждую величину, грубо говоря, можно представить шариком на стержне. Стержень у нас длиной от минус единицы до единицы, минус единица - это значит, что дела для нас очень плохо пойдут. Единица - что очень хорошо, мы победители. На этот стержень нанизаны шарики. Каждый на своём расстоянии от нулевой точки. Это расстояние соответствует значению прогноза.
Теперь мы подбираем массу этих шариков, а масса этих шариков подбирается согласно функции риска.
Б.М. Чем больше значение этой функции в данной точке, тем больше масса шарика.
А.Р. А потом этот стержень уравновешиваем и находим положение центра тяжести.
Б.М. Это, видимо, лучше объяснение, чем моё…
А.Г. Оно доступнее, да.
А.Р. Этот центр тяжести, его положение, мы считаем величиной, которая…
А.Г. Оптимальной величиной, которая позволяет сделать…
А.Р. Не сказать, чтобы оптимальной, это просто характерная величина, которая более-менее описывает куст с этими случайными событиями. И мы её принимаем в качестве оценки.
Б.М. Давайте тогда следующий шаг сделаем. Это был первый шаг нашей оценки, именно на этом мы получили достаточно хорошую программу, которая, правда, всё-таки была хуже этого «Джели-фиша» пресловутого. Следующий шаг такой. Эти функции риска, мы, как правило, брали, условно говоря, пессимистические - человек в жизни должен быть хоть немного пессимистом и ожиданиям плохого придавать больший вес, чем ожиданию хорошего.
А.Г. То есть вы определяли себя игроком хуже, чем ваш партнёр?
Б.М. Нет, не так: плохие показания кубиков мы ожидали с большей вероятностью, чем хорошие показания кубиков. В общем, это, наверное, естественно - когда мы идём гулять, совершенно ничего не зная про прогноз погоды, то, наверное, зонтик всё-таки стоит брать. Здесь фактически то же самое.
И уже на этом мы подбирали разные виды этих функций риска. Уже здесь мы почти вплотную приблизились к «Джели-фишу». Если мы сейчас у него выигрываем (ещё раз повторяю, на нашем российском варианте нард) где-то 55 процентов, может, чуть побольше, тогда мы проигрывали столько же. Но это уже было хорошо. Выигрываем на убывающих функциях риска. Убывающих - это означает, что мы хоть немного, да пессимисты.
Следующий шаг, про который я никак не начну говорить, такой. Всё-таки бывают ситуации, когда надо быть оптимистами, редко, но бывают. А, может быть, не очень редко. Что это такое? Это когда мы сильно проигрываем. То есть когда положение заведомо не в нашу пользу, всё равно нам проигрывать. Здесь нет варианта проиграть слишком много. (Немножко отвлекаясь, в бэкгеммоне есть разные варианты проигрыша, но, как правило, об этом в конкретной позиции речь не идёт.) Если идёт речь о том, чтобы проиграть либо одно очко, либо, может быть, всё-таки выиграть, нам надо строить оптимистическую функцию риска, которая бы учитывала вероятность выпадения нам хороших показаний кубиков. Тогда эти вероятности надо сильно увеличить. Почему? Русская пословица есть - утопающий хватается за соломинку.
А.Г. Речь идёт о стратегии игры?
Б.М. Да, конечно. Но откуда известно, как мы стоим - хорошо или плохо? Например, по той же самой статической оценке позиции, во-вторых, по динамической оценке позиции, взятой с какой-нибудь простой функции риска. Вот это всё приводит к динамическому выбору функции риска. Примерно выбрав, как мы стоим, выигрыш, проигрыш или в серединке, мы за счёт этого динамически строим функцию риска. Например, когда априорно позиция примерно равна, эта функция риска действительно немножко убывает. То есть она похожа на линейную функцию, константу, которая от минус единицы до плюс единицы убудет, начиная со значения единицы, примерно до одной второй. Примерно такая функция риска, убывающая, немножко пессимистическая, соответствует тому, что - пойдёт дождик или не пойдёт дождик - зонтик мы возьмём.
Если же мы заведомо проигрываем, функция риска сильно возрастает. Если же мы выигрываем очень сильно, то мы должны быть сверхпессимистами и очень плохие прогнозы предполагать с гораздо большими вероятностями. И функция риска будет становиться функцией сверхпессимиста. И в зависимости от такого предварительного подсчёта, предварительной генерации, мы и строим динамическую функцию риска.
Поскольку я постоянно делаю шаги в другие задачи дискретной оптимизации, то я здесь сделаю ещё один. Например, некоторые программы-эксперты высчитывают время, оставшееся до получения хорошего ответа (не обязательно оптимального, но близкого к оптимальному) в какой-нибудь задаче дискретной оптимизации, например, в той же самой пресловутой «задаче коммивояжёра» или в минимизации конечных автоматов - тоже одна из моих любимых задач. И разные программы-эксперты оценивают: если в среднем эти программы дают время вычисления, которое очень высоко, гораздо больше, чем если мы пойдём по другой ветке вычислений, то мы здесь применим какую-то оптимистическую функцию риска. Если время будет, наоборот, слишком маленькое, то пессимистическую. Это всё имеет выход в другие задачи дискретной оптимизации.
А.Г. Это то, что у игрока называется интуицией во время игры.
Б.М. Да. Это второй шаг - он самый главный. Первым шагом было введение функции риска, вторым - динамической функции риска. Есть и третий шаг, который тоже может быть важен, хотя менее важен, чем второй. Это применение несколько раз подряд этих функций риска, потому что после первого применения мы немножко уточняем оценку позиции. А раз немножко уточняем оценку позиции, то можем немножко более определённо сказать - мы пессимисты или оптимисты. А в следующий раз мы ещё более определённо будем говорить, ещё раз и ещё раз.
Казалось бы, что это очень долгие вычисления, но нет - по сравнению со всем остальным объёмом вычисления, связанного с получением статических оценок позиции, с организацией перебора и так далее. Это неоднократное применение функции риска, динамическая функция риска, фактически совершенно не занимает времени, то есть там какие-то доли процента - даже, кажется, мы и не считали, какие именно доли процента. Даёт ли этот третий шаг большой выигрыш по сравнению только со вторым? Я затрудняюсь сказать, но раз без каких бы то ни было усилий мы можем получить какое-то преимущество, то, наверное, даёт.
Дело в том, что у меня описаны примеры именно конкретных реализаций, статистических оценок позиций, когда это должно дать преимущество, должно дать плюсы. Но насколько часто эти примеры проявляются в нардах - я сказать затрудняюсь.
А.Г. Вы сами у своей программы выигрываете?
Б.М. Проигрываю. Это, кстати, интересный вопрос, хорошо, что он возник, было бы плохо, если бы он не возник. Я в нардах специалист, но, конечно, условно говоря, не гроссмейстер. Хотя, может быть, моя квалификация в нардах и выше, чем была моя квалификация в шахматах, когда я ещё играл - кандидат в мастера. Вот здесь интересный момент - почему я проигрываю? Я всё-таки человек, и поддаюсь иногда азарту, хотя, конечно, в казино не хожу и только в дурном сне могу представить, что я в казино пойду. Там от меня ничего не зависит, там просто фишки, как выпадут, так и выпадут. А здесь от меня зависит, от моего интеллекта.
И всё-таки я азарту поддаюсь. Например, если я два хода назад стоял хорошо, на выигрыш, но что-то случилось, плохо кубики упали, и я начал стоять плохо. Я просто по инерции продолжаю у себя в мозгу применять пессимистическую функцию риска, оценивая позицию, чего, конечно, делать не надо. Программа же быстрее переключается и быстрее понимает, что всё не так хорошо происходит, как есть на самом деле, и программа переключается, например, от пессимистической к оптимистической функции риска, переключается гораздо быстрее чем я.
А.Р. Тут, наверное, стоит ещё заметить, что программа, в которой реализованы эти алгоритмы, но в которой не подобраны числовые коэффициенты (когда переключаться на какую стратегию, как, собственно, статично оценивать позицию, хорошая она или плохая), эта программа не является рабочей. Чтобы она заработала, необходимо её обучить. Обучение программы происходит, когда она играет сама с собой, тогда происходит, собственно, подгонка параметров таким образом, чтобы максимально улучшить качество игры, максимально повысить вероятность выигрыша.
Но здесь возникает уже другой вопрос - каким образом её учить? Если в играх сама с собой, то, наверное, это будет немного необъективно, так как в данном случае отношения не транзитивны:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30