Читать онлайн «О решении неточных переборных задач»

и М. М. БОТВИННИК О РЕШЕНИИ НЕТОЧНЫХ ПЕРЕБОРНЫХ ЗАДАЧ Настоящая серия печатается по рекомендации IX Международного Совещания руководителей научно-технических издательств социалистических стран (июнь 1975 г. ). В серии участвуют: Издательство «Советское радио» (СССР), Издательство технической литературы (ВНР) Издательство «Техника» (ГДР) Издательство научно-технической литературы (ЧССР) КИБЕРНЕТИКА М. М. БОТВИННИК О РЕШЕНИИ НЕТОЧНЫХ ПЕРЕБОРНЫХ ЗАДАЧ МОСКВА «СОВЕТСКОЕ РАДИО» 1979 ББК 32. 81 Б86 УДК 007+518. 92 Ботвинник М. М. О решении неточных переборных задач. — М. : Сов. радио, 1979, 152 с. (Кибернетика). В книге приводится алгоритм игры шахматного мастера, на основе которого выполнена программа «Пионер». Эта программа частично проверена в эксперименте на шахматных этюдах, и анализ шахматной позиции, полученный «Пионером», оказался весьма близок к анализу шахматного мастера. Отметим, что этюд Г. Нада- реишвили, решенный «Пионером», не смог решить чемпион мира 1977 г. среди компьютеров — американская программа «Чесе 4. 6». Новая работа экс-чемпиона мира по шахматам М. М. Ботвинника рассчитана на широкий круг читателей, интересующихся проблемами управления, планирования, шахматами и др. 48 рис. , 1 табл. , библ. 11 назв. Редакция кибернетической литературы 30501-013 БЗ-97-8-78 1502000000 046(01)-79 © Издательство «Советское радио», 1979 ПРЕДИСЛОВИЕ В книге излагается теория решения неточных переборных задач, которая является в какой-то степени гипотезой, ибо практика еще не подтверждает полностью теоретические положения. Когда искусственный шахматист — программа «Пионер» — начнет играть в силу мастера, эта теория получит достаточно прочную основу. Незаконченная история создания сильного шахматного автомата связана с борьбой двух направлений. Долгое время по. чти безраздельно господствовало мнение, что компьютер не должен копировать методы мышления шахматного мастера и что основной метод машинной игры должен базироваться на полном переборе ходов. После первых успехов «Пионера» положение несколько изменилось; можно предположить, что в будущем компьютер все больше и больше будет подражать человеку. В книге сначала приводятся общие положения, которые, по мнению автора, надлежит использовать при решении неточных переборных задач управления, а затем на примере шахматной игры показывается, как эта общая теория привела к успешным результатам. Приложения к книге написаны математиками, принимающими участие в создании программы «Пионер». Надо полагать, что эти работы заинтересуют программистов и помогут им применить приведенные методы к решению других задач, имеющих практическое значение. 1. ОБЩИЕ ПОЛОЖЕНИЯ ОПРЕДЕЛЕНИЕ НЕТОЧНОЙ ЗАДАЧИ Понятие неточной задачи было введено автором несколько лет назад [1], но тогда не было дано ее строгого определения. Неточной будем называть такую переборную задачу, которая решается с помощью минимаксной процедуры на усеченном дереве перебора (см. также словарь терминов на с. 141).