Belle — шахматный компьютер , разработанный Джо Кондоном (аппаратное обеспечение) и Кеном Томпсоном (программное обеспечение) в Bell Labs . В 1983 году это была первая машина, достигшая уровня мастера , с рейтингом USCF 2250. Она пять раз выигрывала чемпионат ACM North American Computer Chess Championship и чемпионат мира по компьютерным шахматам 1980 года . Это была первая система, победившая с использованием специализированного шахматного оборудования.
В своем последнем воплощении Belle использовала компьютер общего назначения LSI-11 для координации своего шахматного оборудования. Было три настраиваемых доски для генерации ходов, четыре настраиваемых доски для оценки позиции и реализация микрокода альфа-бета-отсечения . Компьютер также имел один мегабайт памяти для хранения таблиц транспозиции .
В конце своей карьеры Belle был передан в дар Смитсоновскому институту . Общая архитектура Belle была использована для первоначальных проектов ChipTest , прародителя IBM Deep Blue . [1]
После работы над операционной системой Unix Кен Томпсон обратил внимание на компьютерные шахматы. [2] Летом 1972 года он начал работу над программой для PDP-11 , которая в конечном итоге стала Belle. На соревнованиях эта ранняя версия побудила Томпсона использовать подход грубой силы при проектировании оборудования Belle. [3]
Дизайн Belle претерпел множество изменений на протяжении всей своей жизни. Первоначальная шахматная программа была переписана для использования поиска покоя «ход против оценки» и оценки позиций путем отдачи приоритета материальному преимуществу . Belle также использовала таблицу транспозиции , чтобы избежать избыточных проверок позиций. [3]
В 1976 году Джо Кондон реализовал аппаратный генератор ходов для использования с программной версией Belle на PDP-11. Его проект состоял из нескольких этапов:
Похожая серия шагов использует генератор ходов для проверки того, является ли псевдолегальный ход на самом деле легальным. Это гарантирует, что ход не ставит ходящую сторону под шах . [4]
Второе поколение Belle было завершено в 1978 году. Оно имело ряд улучшений по сравнению с предшественником.
Эти изменения уменьшили роль программного обеспечения PDP-11. Теперь программное обеспечение управляло этими тремя устройствами и запускало алгоритм обрезки альфа-бета. Второе поколение Belle могло искать 5000 позиций в секунду. [5]
Окончательное воплощение Belle было завершено в 1980 году. Оно состояло из дальнейших улучшений скорости генерации и оценки ходов.
Третье поколение Belle контролировалось компьютером LSI-11. В зависимости от стадии игры он проверял от 100 000 до 200 000 ходов в секунду. [8]
Программная версия Belle Кена Томпсона участвовала в Открытом чемпионате США по шахматам 1972 года и в чемпионате ACM Computer Chess Championship 1973 года. В течение следующего года Belle сыграла несколько игр UCSF и закончила со счетом 3-1 в чемпионате ACM Computer Chess Championship 1974 года.
В 1978 году второе поколение Belle соревновалось на чемпионате ACM по компьютерным шахматам, одержав победу с результатом четыре победы в четырех играх. [5] В решающей игре против Chess 4.7 , занявшей второе место, Belle проверяла 5000 позиций в секунду, в то время как Chess 4.7 проверяла 3500. [9]
В 1980 году третье поколение Belle выиграло третий чемпионат мира по компьютерным шахматам в Линце, Австрия. После четырех туров у него был счет 3,5 в четырех играх, равный счету с шахматной машиной Chaos. [10] В тай-брейке за звание чемпиона мира Belle прорвала защиту Алехина Chaos и объявила мат за восемь ходов, выиграв игру на 41-м ходу . [11] Во время игры Belle просматривала 160 000 позиций в секунду. [12]
В 1983 году Belle принял участие в Открытом чемпионате США, где набрал 8,5 очков в двенадцати играх с рейтингом производительности 2363. Позже в том же году USCF присвоил Belle звание мастера. [13] Поскольку он достиг этого уровня раньше любого другого шахматного компьютера, Belle был награжден призом Фредкина в размере 5000 долларов. Царствование Belle закончилось, когда он занял шестое место на Четвертом чемпионате мира по шахматам среди компьютерных программ, несмотря на то, что был фаворитом на победу. [13] Ему удалось одержать еще одну победу на чемпионате ACM в 1986 году, прежде чем уйти на пенсию.
Благодаря своей способности генерировать и анализировать множество шахматных позиций, Belle представляла собой подход грубой силы к шахматным вычислениям. В конце 1970-х годов Томпсон заинтересовался пределами этого метода, играя разные версии Belle друг против друга. Использование идентичных машин позволило ему минимизировать эффекты стиля игры индивидуальной машины, одновременно изолируя эффекты глубины поиска . Например, если один компьютер Belle ищет на трех уровнях в глубину, другой может искать на четырех. Томпсон пришел к выводу, что для каждого дополнительного уровня поиска Belle улучшалась примерно на 250 очков рейтинга. [14] [15] Этот эффект был воспроизведен в экспериментах по самостоятельной игре с разными машинами. [16] Однако после 2000 очков Томпсон обнаружил, что улучшения выравниваются. [17]