Cтраница 3
Особенно часто он применяется в шахматных программах. Возникновение и становление альфа-бета алгоритма имеет / довольно запутанную историю. Несколько исследователей независимо друг от друга открыли либо реализовали этот метод полностью или частично. Там же приводится более компактная формулировка альфа-бета алгоритма, использующая вместо минимаксного принципа принцип него-макса ( neg-max principle), и приводится математический анализ производительности алгоритма. Существует еще один интересный вопрос, относящийся к минимаксному принципу. Мы знаем, что статическим оценкам следует доверять только до некоторой степени. [31]
Готов ли новый чемпион сыграть с победителем в матче Карпов-Каспаров. Он курирует Премию Фредкина - награда 100000 предлагается первой шахматной программе, которая победит человека-чемпиона мира. Леви, который обыграл много шахматных программ, соглашается: Раньше игроки в шахматы смеялись. На следующий год они придут посмотреть. [32]
Например, эмпирическое исследование силы игры шахматистов-мастеров показывает, что главным источником силы мастера является хранимая в его памяти информация, позволяющая ему распознать большое количество характерных особенностей позиций на доске и их комбинаций, а также информация, использующая это узнавание, чтобы предложить действия, подходящие для распознанных особенностей позиции. Эта общая идея была, разумеется, включена в шахматные программы почти с самого начала. Новым было осознание числа таких комбинаций и связанной с ними информации, которую, возможно, придется хранить для обеспечения игры на уровне мастеров: это примерно 50000 комбинаций. [33]
Первый способ, уже проиллюстрированный примером решения алгебраического уравнения и шахматными программами, генерирующими только хорошие ходы для последующего анализа, это встроить избирательность в генератор: порождать только такие структуры, которые имеют шанс оказаться решениями или лежать на пути, ведущем к решению. Обычно это приводит к уменьшению ветвления, но не устраняет его полностью. Взрывной экспоненциальный рост в конечном итоге не предотвращается ( за исключением особенна хорошо структурированных ситуаций, как в примере из алгебры), а лишь отодвигается на некоторый срок. Поэтому интеллектуальная система должна дополнить избирательность своего генератора решений какими-то другими методами направления поиска, использующими информацию о структуре пространства решений. [34]
До сих пор в области ИИ значение машинного обучения для решения проблем осознавалось весьма слабо. Единственную, по существу за много лет заслуживающую упоминания работу представляет известная шахматная программа Сэ-мюэля и использованная в ней процедура обучения. Большой интерес в свое время вызвала предложенная Ньюэллом, Шоу и Саймоном система обучения, предназначенная для программы GPS, однако она осталась нереализованной. Как это ни удивительно, и в наши дни ситуация остается прежней. [35]
Эмпирические исследования управления поиском по деревьям больших размеров, приведшие к довольно скромным результатам, сделали это направление намного менее перспективным, чем оно было тогда, когда, шахматы были впервые выбраны в качестве подходящего объекта исследований по искусственному интеллекту. Мы должны считать этот факт одним из важных эмпирических результатов изучения шахматных программ. [36]
Почему же эта программа играет настолько лучше предыдущих. С моей точки зрения, в программу не заложены принципиально новые идеи относительно организации шахматных программ. В этой программе содержится значительно больше, чем в любой из предыдущих, конкретных сведений о шахматах. Наконец, имелась возможность, использовав сидящего за пультом управления человека, организовать прекрасный обучающий контур. Ошибки анализировались и быстро устранялись с помощью подпрограмм изменения программы и / или введения дополнительной шахматной информации. Влияние новых подпрограмм и дополнительной информации на работу системы, если оно имело место, можно было быстро обнаружить; при возникновении каких-либо осложнений это влияние устранялось. Таким способом очень удобно улучшать ( или обучать) программу, и им целесообразно пользоваться в тех случаях, когда вы больше заинтересованы в высоком качестве работы системы при разрешении конкретной задачи, чем в получении общих мо делей, обеспечивающих реализацию процессов решения проблем. Я считаю, что этот метод, хотя и в более сложных формах, будет широко использоваться во втором десятилетии. [37]
Но есть и другая сторона связи между средствами описания и сложностью: мы не можем использовать любой удобный для нас язык. Нас должны понимать то лицо или та машина, к которым мы обращаемся. Шахматная программа, написанная на английском языке, не будет работать, ибо не существует машин, понимающих английский язык. Описание на английском языке может предназначаться только для другого человека, который затем должен будет создать соответствующую машину. Преимущество машинного кода заключается именно в том, что существуют понимающие его машины. Поэтому шахматная программа, записанная в машинном коде, функционально эквивалентна машине, играющей в шахматы. [38]
Важность эмпирических работ в качестве источника общих идей в исследованиях по ИИ можно ясно продемонстрировать, проследив историю создания многочисленных программ для решения задач, в которой центральную роль играли две эти идеи: поиск с выбором первыми самых лучших кандидатов и анализ средств и целей. Шахматные программы как правило были связаны ( по соображениям экономики памяти) с поиском в глубину, дополненным после 1958 г. мощной процедурой альфа-бета усечения. Похоже, что каждый из этих методов неоднократно изобретался заново, и трудно найти общие, не зависящие от конкретной задачи теоретические обсуждения решения задач в терминах этих концепций до середины или второй половины 60 - х годов. Масштабы поддержки, которую они получили со стороны формализованной математической теории, все еще незначительны: некоторые теоремы о сокращении объема поиска, которое может быть обеспечено применением альфа-бета эвристики, пара теорем ( рассмотренных в [4]) о поиске по кратчайшему пути, и несколько полученных в самое последнее время теорем о поиске с выбором лучшей вершины с применением вероятностной оценочной функции. [39]
За много лет существования соревнований по шахматам в мире сыграны тысячи партий. Сведения о них скрупулезно собираются и накапливаются в специальных книгах - информаториях. В некоторые шахматные программы тоже встраивают электронные информатории. Если у вас есть такая программа, то во время игры всегда можно обратиться в информатории, и то да программа может подсказать, например, что Такая позиция уже встречалась в 1927 году в матче между Капаб-ланкой и Алехиным, и что в этом положении Капабланка сделал такой-то ход, а в итоге победил Алехин. [40]
Система химического синтеза сейчас находится на границе того, что можно назвать реальной экспертной системой. Подобно некоторым шахматным программам, она выполняет функции эксперта и работает по принципу поиска. Поиск осуществляется на многих уровнях дерева с аналогичной иерархией, поэтому программа достаточно сложна. Но она функционирует полностью механически, а пространство поиска относительно невелико. Мы считаем ее полезной программой, работающей в пределах возможностей простого Пролога, в пограничной зоне экспертных систем. Экспертные системы могут делать все, что вы видели, и еще многое другое. [41]
На заре исследований по ИИ считалось, что знание расфасовано пакетами размером с предложение, и что лучшим способом ввода знаний в программу был бы некий метод, позволяющий переводить факты в пассивные пакеты данных. Примером такого подхода являлись шахматные программы, в которых позиции на доске были закодированы в форме матриц или неких списков и записаны в памяти, откуда они могли быть вызваны и обработаны с помощью подпрограмм. [42]
Готов ли новый чемпион сыграть с победителем в матче Карпов-Каспаров. Он курирует Премию Фредкина - награда 100000 предлагается первой шахматной программе, которая победит человека-чемпиона мира. Леви, который обыграл много шахматных программ, соглашается: Раньше игроки в шахматы смеялись. На следующий год они придут посмотреть. [43]
Никто не собирается строить шахматные машины в буквальном смысле этого слова: собирать из электромеханических деталей играющие в шахматы автоматы. Вместо этого мы придумываем шахматную программу: на языке, который называется машинным кодом, мы пишем инструкцию, как играть в шахматы, - инструкцию, которая может быть выполнена любой стандартной цифровой вычислительной машиной. [44]
В этом направлении главным образом и ведутся исследования современных математиков. Так, Каисса во многих ситуациях уже отказывается от полного перебора вариантов. Заметим, что любой метод сокращения перебора в шахматных программах, по существу, является методом направленного поиска, широко используемого в прикладной математике. [45]