Научный подход к игре нарды


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

Борис Мельников:
Считалось, что игры нарды азартные, в них играть запрещали. Я даже помню такие полуанекдотические случаи, когда за игру в карты или нарды из комсомола могли выгнать, из общежития выселить. Да, к игре нарды были подобные притязания. Александр Гордон: Конечно, кубики кидают в игре нарды... Б.М. Нарды действительно воспринималась как азартная игра. Что, конечно, не правильно. Потому что для хорошей игры в нарды тоже нужно обладать интеллектом. А.Г. Вы сейчас говорите о так называемых коротких нардах? Б.М. Да, конечно. Давайте тоже об этом расскажу. Я незаслуженно поздно познакомился с нардами. В шахматах я уже был достаточно большим специалистом для своего возраста, а про нарды узнал из публикации в "Науке и жизни" – мне было где-то 14 лет. Там была публикация про нарды, в середине 80-х годов. И были две распространенные в России версии нард – длинные и короткие. И я достаточно быстро, хоть достаточно был молод, понял, что так называемые "длинные" нарды – это игра не очень интеллектуальная. То есть, просто игра на перетаскивание фишек в зависимости от показания кубика. Интеллект иногда надо было применять, но, по моим расчетам, в длинных нардах, чтобы из новичка получить человека, который играет наравне с чемпионом, может быть трех минут мало, как в крестиках и ноликах на доске три на три, но дня – достаточно. Чего, конечно, нельзя сказать о коротких нардах. И, тем более, о расширении этой игры, международной версии "бэкгеммон", в которой добавлено еще несколько правил, несколько усложнений, которые эту игру нарды делают гораздо более интересной.

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

Недавно мне попалась книжка Гика, недавно изданная, про разные игры, в которой проводится мысль, с которой совершенно не могу согласиться. Там говорится о том, что сильные игроки в бэкгеммон, в нарды, делают практически одинаковые ходы в сложных позициях, когда знают позицию, знают показания кубиков. Ну и поэтому в партиях сильных игроков в нарды побеждает тот, кому лучше придут кубики. Конечно, это так. Лучше придут кубики – в игре нарды это очень важно, гораздо важнее, чем в шахматах, где кубиков нет. Но, однако, те же самые сильные шахматисты в схожих позициях делают разные ходы, в этом проявляется стиль шахматиста. И игроки в нарды , игроки в бэкгеммон, тоже делают разные ходы – тоже в зависимости от стиля. И недаром на сайтах в Интернете выставляются партии лучших игроков в нарды в мире и, в частности, их партии с компьютерами.

 Наша группа среди прочего делает и программы по игре в бэкгеммон. Лучше даже пока сказать – в наши отечественные "короткие нарды". По материалам этих программ были статьи в журнале "Программирование".

Так что, основная, конечно, тема – это программирование игр, и я вернусь к программированию игры нарды. В Интернете можно найти разные программы, играющие в бэкгеммон. И, в частности, в них во всех можно устанавливать уровень, лучше сказать не "уровень игры нарды", а "вариант игры нарды", который совпадает с русской версией, с более упрощенной, это короткие нарды. Но вот, к сожалению, у нас пока программы играют только в нашу отечественную версию игры нарды и, причем, после публикации в журнале "Программирование" двухлетней давности, больших успехов с этого времени практически не случилось. Мы не поучаствовали в чемпионате мира по программированию игры нарды летом 2002 года (хотя собираемся поучаствовать в следующем чемпионате 2004 года). Не поучаствовали по той причине, что просто не хватает времени – с совершенно теми же самыми идеями – довести программу игры в нарды до уровня бэкгеммон. То есть, до уровня международного стандарта, несколько более усложненного. Но я, здесь сидя, обещаю, что в 2004 году я это сделаю.

Почему у меня такая уверенность? Потому что все-таки наш русский, российский (может быть, не очень хорошо говорить "русский", потому что в разных кавказских республиках бывшего Советского Союза короткие нарды распространены больше, чем в России, поэтому лучше сказать "советский" вариант игры нарды), потому что советский вариант игры нарды – это более простой вариант. А.Г. Для тех, кто знаком с правилами игры в короткие нарды, скажите, пожалуйста, в двух словах, чем отличается бэкгеммон от коротких нард. Б.М. Самое главное отличие – то, что в бэкгеммоне добавляется еще один кубик, удваивающий куб. Doubling dice, даблинг дайс, по-моему, называется. Его смысл вот какой. Кубик для игры нарды сначала лежит на единичке и в любой момент игры любой из участников может перевернуть его на двойку. И другой – либо сразу сдается, либо любой будущий исход игры нарды удваивается. При этом тот, кто удваивает, уже не является хозяином кубика. Если в самом начале кубик является общим, то удвоенный кубик лежит на стороне того, который согласился – не того, который предложил удваивать, а того, который согласился. И далее в игре нарды можно учетверять и так далее.

И сначала, когда я впервые познакомился с этим правилом (это было 5 лет назад, когда Интернет стал широко доступен), то первая моя реакция была резко отрицательная, я даже тогда такие примеры приводил: играет как в нарды , например, "Спартак" с "Динамо" (Киев), выбегает тренер Романцев и ставит на футбольное поле огромный куб с двойкой. И киевляне либо соглашаются, либо убегают с поля. Но потом я постепенно понял, что эта аналогия всё-таки плоховата, и даже не выдерживает никакой критики. Это нововведение очень сильно, в хорошем смысле, усложняет игру нарды, то есть разные тонкости, разные нюансы игры нарды даёт. Вот это основное отличие.

Но давайте еще скажем, чтобы закончить эту минитему, про отличие игры нарды от бэкгеммона. Я переписываюсь с разными именно игроками в нарды, в том числе добивавшимися успеха в международных соревнованиях по игре нарды. И у меня возникло такое впечатление, что в последнее время ситуация в тех же программах, выставленных в Интернете, немножко другая, чем была года 3-4 назад. Там в основном выставляются программы, где хорошо развита игра нарды на деньги. Ну, и соответственно, сайты, на которых играли умнейшие люди мира (я нисколько не шучу, таким образом действительно можно определять интеллект) – эти сайты постепенно закрываются, и появляются сайты, на которых можно в игру нарды поиграть, в боггемен поиграть за деньги. Там тоже есть этот удваивающий куб, то есть это игры нарды, похожие на бэкгеммон, а не на нарды... А.Г. Всё-таки, возвращаясь к вашей программе, откуда у вас уверенность в том, что она может стать чемпионом? Б.М. Да, эту мысль надо точнее развить. Мы в нашем советском варианте обыграли в нарды всё, что у нас было. Более того, я высылал всем желающим и продолжаю высылать демонстрационную версию игры в нарды, которая играется так называемым "Джели-фиш". И мы его обыграли, и ещё парочку программ обыграли. То есть мы берем стабильно больше 55 % очков. Если те же самые методы применить к общему бэкгеммону, то есть добавить этот кубик, то выиграем в нарды и у всех оставшихся, мы просто ещё не успели это сделать. А.Г. Так. Теперь – что же это за методы? Б.М. Да. Но начнем с другого конца: на чём построены абсолютно все остальные бэкгеммоновские программы, за редчайшим исключением, за исключением, может быть, самых первых программ для игры в нарды? Там был такой Берлинер... Может быть, вы про Берлинера расскажете?Алексей Радионов: В любых программах фигурирует такая вещь, как оценка позиции в игре нарды, некоторые оценочные функции. Что это такое? В конце партии по игре нарды уже четко видно, кто победил, кто проиграл – по доске мы можем сказать: да, действительно, такое-то количество очков выиграл один игрок в нарды, другой, соответственно, другое. Это видно в самом конце игры нарды. А как оценить позицию, когда мы ещё до конца игры нарды не добрались? Здесь, как правило, программа моделирует ходы противников с той целью, чтобы одна сторона стремилась свой выигрыш увеличить, а другая сторона стремилась уменьшить выигрыш противника. Вот, собственно, метод минимакса, минимизации и максимизации идёт отсюда. Б.М. Но это стандартное. Это ещё пока не имеет отношения к недетерминизму.А.Р. Да. Вот на подсчете таких чередований минимума и максимума получается оценка позиций, которые уже не конечны, где ещё не ясно, кто и что выиграл, позиций на некоторых промежуточных уровнях, где-то в середине игры нарды. Таким образом программа может оценить своё положение и принять тот ход, который либо гарантирует ей выигрыш в игре нарды, либо гарантирует какой-то минимальный проигрыш, то есть не ухудшает ситуацию.

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

Первый подход – это просто случайное моделирование нескольких ветвей позиции, более точно – нити развития игры нарды. Это один вариант программы. Но это всё было давно, это самые первые программы для игры нарды, датированные примерно 80-ми, может быть, 90-м годом, но не позже. А после этого все программы – абсолютно все, я не знаю ни одного исключения среди хороших программ для игры нарды, кроме нашей, – написаны на так называемой нейросетевой технологии.

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

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

И уже на этом мы подбирали разные виды этих функций риска. Уже здесь мы почти вплотную приблизились к "Джели-фишу". Если мы сейчас у него выигрываем (еще раз повторяю, на нашем российском варианте нард) где-то 55 процентов, может, чуть побольше, тогда мы проигрывали в нарды столько же. Но это уже было хорошо. Выигрываем в нарды на убывающих функциях риска. Убывающих – это означает, что мы хоть немного, да пессимисты.

Следующий шаг, про который я никак не начну говорить, такой. Все-таки бывают ситуации, когда надо быть оптимистами в игре нарды , редко, но бывают. А, может быть, не очень редко. Что это такое? Это когда мы сильно проигрываем. в игре нарды. То есть когда положение заведомо не в нашу пользу, все равно нам проигрывать. Здесь нет варианта проиграть слишком много. (Немножко отвлекаясь, в бэкгеммоне есть разные варианты проигрыша, но, как правило, об этом в конкретной позиции речь не идет.) Если идет речь о том, чтобы проиграть в нарды либо одно очко, либо, может быть, все-таки выиграть в игре нарды, нам надо строить оптимистическую функцию риска, которая бы учитывала вероятность выпадения нам хороших показаний кубиков. Тогда эти вероятности надо сильно увеличить. Почему? Русская пословица есть – утопающий хватается за соломинку. А.Г. Речь идет о стратегии игры нарды? Б.М. Да, конечно. Но откуда известно, как мы стоим в игре нарды– хорошо или плохо? Например, по той же самой статической оценке позиции, во-вторых, по динамической оценке позиции в игре нарды, взятой с какой-нибудь простой функции риска. Вот это все приводит к динамическому выбору функции риска при игре нарды. Примерно выбрав, как мы стоим, выигрыш, проигрыш в нарды или в серединке, мы за счет этого динамически строим функцию риска. Например, когда априорно позиция примерно равна, эта функция риска действительно немножко убывает. То есть она похожа на линейную функцию, константу, которая от минус единицы до плюс единицы убудет, начиная со значения единицы, примерно до одной второй. Примерно такая функция риска, убывающая, немножко пессимистическая, соответствует тому, что – пойдет дождик или не пойдет дождик – зонтик мы возьмем.

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

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

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

Здесь лучше, наверное, вспомнить еще одну вещь, которая только начала встраиваться в программу для игры нарды. В классической теории Адельсона-Вельского программа для игры нарды, когда думает, за противника думает так же, как за себя. То есть на место противника ставит саму себя. Еще один прием, который мы применяли – ставить на место противника не себя, а нечто другое, нечто более сложное, нечто более сильное. Потому что у нас-то есть действительно толпа (это такой жаргонный термин – толпа игроков в нарды), толпа объектов для самообучения. Это применяется, еще раз скажу, и в других задачах дискретной оптимизации. И можно всегда взять того, который лидирует в игре нарды, в качестве условного противника, то есть программа, играя в нарды, в качестве условного противника берет лидера.

Что еще можно? Еще только начаты работы в том направлении, чтобы программа пыталась, пока противник по игре нарды думает, начать думать за противника и старалась подобрать к противнику свои критерии работы. То есть пыталась представить саму себя на месте противника игрока в нарды, и если у нее это получается, она на месте этого виртуального противника подставляет саму себя со своими коэффициентами. Вот это была бы очень интересная тема. Но она, как я уже сказал, только начата, и сказать, насколько она реально применяется в программах, я вам пока не могу.А.Г. Ну что ж, мне осталось вам пожелать удачи в 2004 году. И если победите в игре нарды, то приходите рассказать о том, как это было. Б.М. Спасибо!