Cтраница 1
Лос-Аламосская программа наиболее точно воплощает проект Шеннона. [1]
Лос-Аламосская программа помогает оценить тот предел, до которого можно упрощать процесс в сторону минимизации количества информации, перерабатываемой при оценке каждой позиции. Программа Тьюринга помогает оценить аналогичный предел для процесса минимизации числа исследуемых продолжений. [2]
Так же как и в Лос-Аламосской программе, варианты исследуются на два хода вперед. Однако на каждом шаге используются генераторы правдоподобных ходов, так что из каждой позиции возникает до семи вариантов. В качестве оценочной функции берется отношение двух функций - для белых и для черных. Каждая из этих функций представляет собой взвешенную сумму четырех слагаемых: материал, защита короля, контролируемая площадь и подвижность. Программа использует минимаксную процедуру и выбирает продолжение с наибольшей рабочей оценкой. [3]
Любое усложнение алгоритма приводит к увеличению сложности программы. Для работы генераторов ходов и вычисления компонент оценочной функции необходима разнообразная информация о каждой позиции. Вследствие этого как размер программы, так и время, расходуемое на оценку одной позиции, оказываются большими, чем для Лос-Аламосской программы. [4]
К сожалению, качество игры обеих программ удается сравнить лишь очень грубо. Чтобы такое сравнение было надежным, необходимо иметь вариант Лос-Аламос - ской программы для доски 8X8 и, кроме того, обеими программами должно быть сыграно больше партий. Поскольку вариант 8X8 Лос-Аламосской программы с точки зрения приближения к игре шахматиста должен быть лучше, чем вариант 6X6, будем считать, что Лос-Аламосская программа и программа Бернстейна играют примерно одинаково. В этом грубом приближении мы имеем две программы, достигающие одного и того же уровня игры разными путями: Лос-Аламосская - без использования отбора, за счет скорости, а программа Бернстейна - за счет сильного отбора, приводящего к большей затрате времени на рассмотрение каждой позиции. [5]
Поэтому по мере возрастания глубины требуемые дополнительные усилия, затрачиваемые на исследование каждой позиции, быстро окупаются, так как замедляют рост числа подлежащих рассмотрению вариантов. Сравнение обеих программ при большей глубине анализа имеет смысл, так как естественный путь совершенствования Лос-Аламосской программы состоит в повышении ее быстродействия настолько, чтобы анализ мог проводиться на глубину в три хода. Кроме того, попытка ввести в Лос-Аламосскую программу отбор продолжений обошлась бы чрезвычайно дорого по сравнению с введением дополнительного отбора в программу Бернстейна. [6]
К сожалению, качество игры обеих программ удается сравнить лишь очень грубо. Чтобы такое сравнение было надежным, необходимо иметь вариант Лос-Аламос - ской программы для доски 8X8 и, кроме того, обеими программами должно быть сыграно больше партий. Поскольку вариант 8X8 Лос-Аламосской программы с точки зрения приближения к игре шахматиста должен быть лучше, чем вариант 6X6, будем считать, что Лос-Аламосская программа и программа Бернстейна играют примерно одинаково. В этом грубом приближении мы имеем две программы, достигающие одного и того же уровня игры разными путями: Лос-Аламосская - без использования отбора, за счет скорости, а программа Бернстейна - за счет сильного отбора, приводящего к большей затрате времени на рассмотрение каждой позиции. [7]
Так как это первый пример фактически играющей машины, стоит несколько детальнее рассмотреть ее особенности. На обычной ( 8X8) шахматной доске при выборе каждого хода имеется в среднем около 30 возможностей. Таким образом, просмотр на два хода вперед требует рассмотрения ЗО4 - 800 000 продолжений. Даже при таком сокращении это число все еще очень велико. Лос-Аламосская программа затрачивает на ход в среднем около 12 мин. При такой скорости программа должна быть весьма простой. Это видно также из ее размера - всего 600 слов. Образно выражаясь, машина успевает лишь бегло взглянуть на каждую оцениваемую позицию. [8]
Поэтому по мере возрастания глубины требуемые дополнительные усилия, затрачиваемые на исследование каждой позиции, быстро окупаются, так как замедляют рост числа подлежащих рассмотрению вариантов. Сравнение обеих программ при большей глубине анализа имеет смысл, так как естественный путь совершенствования Лос-Аламосской программы состоит в повышении ее быстродействия настолько, чтобы анализ мог проводиться на глубину в три хода. Кроме того, попытка ввести в Лос-Аламосскую программу отбор продолжений обошлась бы чрезвычайно дорого по сравнению с введением дополнительного отбора в программу Бернстейна. [9]
Генератор ходов, связанный с данной целью, предлагает ходы, направленные на достижение этой цели. Эти генераторы должны находить положительные доводы в пользу предлагаемого хода. Например, в дебюте ход d2 - d4 предложит только тот генератор, который связан с контролем над центром; только генератор, связанный с материальным балансом, предложит убрать фигуру, находящуюся под ударом. Эти генераторы ходов соответствуют генераторам Бернстейна с той лишь разницей, что они предназначены исключительно для генерирования очередных ходов и не используются для генерирования продолжений, которые рассматриваются при анализе данного хода. В программе Бернстейна и тем более в Лос-Аламосской программе одни и те же генераторы используются как для отыскания возможных ходов, среди которых делается окончательный выбор, так и для получения продолжений, которые необходимо исследовать для оценки последствий того или иного хода. В нашей программе последнюю функцию выполняет отдельный набор генераторов. [10]