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

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

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

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

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

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

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

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

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

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

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

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