Александр Гордон - Диалоги (июнь 2003 г.)

Александр Гордон

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

Программирование недетерминированных игр

Участники:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Почему у меня такая уверенность? Потому что всё-таки наш русский, российский (может быть, не очень хорошо говорить «русский», потому что в разных кавказских республиках бывшего Советского Союза короткие нарды распространены больше, чем в России, поэтому лучше сказать «советский» вариант игры), потому что советский вариант игры – это более простой вариант.

А.Г. Для тех, кто знаком с правилами игры в короткие нарды, скажите, пожалуйста, в двух словах, чем отличается бэкгеммон от коротких нард.

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

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