Последовательность эвристик
Последовательность эвристик, приёмов
Постановка задачФункция постановки системы задач при создании инноваций / изобретений
X
Цель и алгоритм шахматной игры по М.М. Ботвиннику
«В феврале 1964 года показалось, что дело пошло, начал задачу «видеть». Этот метод работы, вероятно, характерен для шахматиста. Шахматист всегда видит позицию не только ту, что на доске, но и ту, что в варианте, то есть вслепую. Думаю, что эта способность видеть вслепую должна быть у всех крупных шахматистов: это своего рода зрительная память.
Вот я и стал «прозревать». В июне решился уже засесть за письменный стол и, к своему большому удивлению, через месяц написал что-то связное. Впоследствии понял, что написал - нашёл «цель неточной игры» в шахматах. Потом мне приходилось решать и другие нелёгкие задачи, но эта, вероятно, оказалась самой трудной. Цель игры - основа алгоритма. На поиск цели в общей сложности ушло три с половиной года.
Найденная цель игры оказалась весьма простой: надо стремиться к выигрышу материала. Собственно говоря, так интуитивно играет квалифицированный шахматист, но все об этом молчат, ибо обычно этот принцип понимают вульгарно, в том смысле, что в данный момент надо уничтожить наиболее ценную неприятельскую фигуру, - это, конечно, ошибочно. Но если эту цель игры понимать так, что надлежит стремиться к оптимальному выигрышу материала в пределах обозримого счёта вариантов, то она представляется вполне разумной.
Уже и тогда мне было ясно, что нужно формализовать и понятие позиционной игры, однако пришлось отложить решение этого вопроса. Он был решён много позже.
Цель игры (выигрыш материала) определила и следующий важный шаг. Раз надо уничтожать неприятельские фигуры, то у каждой фигуры на доске появились свои индивидуальные цели, конкретные мишени, которые должны быть поражены. Одна фигура может уничтожить другую, передвигаясь по определенным полям доски, - совокупность этих полей образует траекторию, в данном случае образует траекторию нападения. Другие неприятельские фигуры стремятся защитить свою фигуру, а фигуры того же цвета, что атакующая, - поддержать нападение. Эти фигуры также действуют по своим траекториям, условно названным траекториями отрицания. Все это я изложил в монографии. […]
Но что делать с монографией об алгоритме игры в шахматы? Дело-то важное. Система управления (в том числе и человек) выполняет три кибернетические функции: получение информации, её переработку (принятие решения) и исполнение решения. Люди сказочно усовершенствовали первую и третью функции - это относится к радиотехнике и термоядерной энергии соответственно, а вот с переработкой информации сдвигов практически нет; здесь (в сложных задачах) мозг человека сохранил монопольное положение. Необходим сильный искусственный интеллект; искусственный шахматист-гроссмейстер и будет первым шагом в этом направлении.
Подумал и решил послать работу президенту Академии наук М. Келдышу; написал, что готов работать по этой теме там, где нужно. […]
Шеннон предложил формализовать и программировать шахматы для того, чтобы использовать шахматный компьютер как модель, для решения аналогичных задач управления. Авторитет Шеннона столь велик, что его статья незамедлительно положила начало новому научному направлению.
Математики считают, что полное дерево перебора в шахматах, хотя и является конечным, содержит примерно 10120 позиций! И если партия продолжается 100 ходов, то среднюю ширину дерева составляют 10118 позиций. Получается, что это дерево - тончайший блин... Не только изучить, но и сформировать такое сверхгигантское дерево перебора нет возможности. Как же быть? Нет никакого другого выхода, как оставить лишь верхушку, то есть формировать и анализировать усечённое дерево перебора, где длина вариантов сравнительно невелика.
Мастер считает варианты на 5-6 ходов. Если измерять эти варианты в единицах шахматного времени (математики это время измеряют в полуходах), то длина вариантов равняется 10-12 полуходам. Примем, что варианты ограничены 6 полуходами, то есть в два раза короче. Примем также, что мы анализируем позицию, где в среднем в каждом узле (позиции) дерева возможно 20 различных ходов. И тогда нетрудно подсчитать, что такое усеченное дерево содержит около 70 миллионов позиций...
Математики применяют тонкий метод, который позволяет сократить число ходов в дереве перебора, так называемый метод ветвей и границ - в двусторонних играх это альфа-бета отсечение.
Суть дела в том, что далеко не все ходы в дереве необходимы для принятия решения (выбора хода). Этот метод ветвей и границ позволяет освободиться от значительной части балласта (ненужных ходов). Дерево сокращается с 70 000 000 до нескольких десятков тысяч, то есть примерно в тысячу раз. Но если учесть, что у шахматного мастера варианты анализа содержат всего десятки ходов, то мусора в дереве перебора остается более чем достаточно. Если поделить 70 000 на 6 полуходов, то средняя ширина дерева превышает 10 000 позиций...
Разрастание дерева вширь с увеличением глубины расчета происходит катастрофически. Человек решает задачи, подобные шахматам (а шахматы - типичная задача среди тех, которые непрерывно решают люди), формируя дерево перебора вариантов. Если вообще и можно решить задачу точно, то надо формировать полное дерево перебора всех вариантов. При этом оптимальный вариант определяется с помощью точной оценочной функции или соответственно - точной цели игры. Но как уже отмечалось, приходится анализировать усечённое дерево перебора. А в этом случае точная цель игры, как правило, бесполезна, нужна уже другая, неточная цель. Да, сохранять в усечённом дереве перебора».
Ботвинник М.М., Шах двадцатому веку, М., «Аст»; «Зебра Е», 2010 г., с. 271-273 и 314-315.
