Belle (шахматная машина)

редактировать

Belle была шахматным компьютером, разработанным Джо Кондоном (оборудование) и Ken Thompson (программное обеспечение) в Bell Labs. В 1983 году это был первый компьютер, достигший мастер-уровня игры с USCF рейтингом из 2250. Он выиграл ACM Североамериканский чемпионат по компьютерным шахматам пять раз и чемпионат мира по компьютерным шахматам 1980 . Это была первая система, в которой использовалось специализированное шахматное оборудование.

В своем последнем воплощении Белль использовала LSI-11 универсальный компьютер для координации своего шахматного оборудования. Существовали три настраиваемые платы для генерации перемещений, четыре настраиваемые платы для оценки положения и микрокод реализация обрезки альфа-бета. В компьютере также был один мегабайт коммерческой памяти для хранения таблиц транспонирования.

В конце своей карьеры Belle была передана в дар Смитсоновскому институту. Общая архитектура Belle использовалась для первоначальных проектов ChipTest, прародителя IBM Deep Blue.

Содержание

  • 1 Origins
  • 2 Design
    • 2.1 Генератор аппаратных перемещений
    • 2.2 Второе поколение
    • 2.3 Третье поколение
  • 3 Карьера
    • 3.1 Ранние соревнования
    • 3.2 Чемпионат мира
    • 3.3 Мастер-рейтинг
  • 4 Анализ результатов
  • 5 См. Также
  • 6 Примечания
  • 7 Источники

Истоки

После работы над операционной системой Unix Кен Томпсон обратил свое внимание на компьютерные шахматы. Летом 1972 года он начал работу над программой для PDP-11, которая в конечном итоге стала Belle. В конкуренции эта ранняя версия побудила Томпсона придерживаться подхода грубой силы при разработке оборудования Belle.

Дизайн

Дизайн Belle претерпел множество изменений на протяжении всей своей жизни. Первоначальная шахматная программа была переписана, чтобы использовать алгоритм «ход против оценки» , поиск в состоянии покоя и оценивать позиции, отдавая приоритет материальному преимуществу. Белль также использовала таблицу транспонирования, чтобы избежать избыточных проверок позиций.

Аппаратный генератор перемещения

abcdefgh
8Chessboard480.svg черный слон d7 c6 стрелка вверх-вправо b5 черный слон e2 белая ладья f2 стрелка вправо g2 белые ладья 8
77
66
55
44
33
22
11
abcdefgh
Определение хода. . Белль представляет ход, определяя "от" «квадрат» и «квадрат» с использованием счетчика смещения ∆xy. Ход ладьи выше имеет смещение (2,0), а ход слона - (2,2).

В 1976 году Джо Кондон реализовал аппаратный генератор движений для использования с версией программного обеспечения Belle на PDP-11. Его конструкция состояла из нескольких этапов:

  1. 6-битный «from» регистр ищет на доске дружественные фигуры.
  2. Как только дружественная фигура найдена, ∆xy-смещение хода counter предоставляет битовый код для смещения перемещения, например (2,2) для слона или (2,0) для ладьи .
  3. Это смещение объединяется с содержимым регистра «от» и перемещается в 6-битный » зарегистрироваться. Эти два регистра полностью описывают возможное перемещение.
  4. . Тестовая схема сравнивает перемещение с существующей платой, чтобы определить, является ли перемещение псевдозаконным. Если это так, регистры «от» и «до» выводятся в программное обеспечение.

Аналогичная последовательность шагов использует генератор ходов для проверки того, является ли псевдозаконный ход на самом деле законным. Это гарантирует, что ход не помещает движущуюся сторону в проверку.

Второе поколение

Второе поколение Belle было завершено в 1978 году. Оно реализовало несколько улучшений по сравнению с его предшественником.

  • Генератор ходов имел свой собственный стек, который он использовал для хранения ходов, а не для их вывода в программное обеспечение.
  • Была добавлена ​​аппаратная реализация оценщика положения.
  • Аппаратная реализация транспозиционной памяти.

Эти изменения снизили роль программного обеспечения PDP-11. Теперь программное обеспечение управляло этими тремя устройствами и запускало алгоритм отсечения альфа-бета. Второе поколение Belle могло искать 5000 позиций в секунду.

Третье поколение

Последнее воплощение Belle было завершено в 1980 году. Оно заключалось в дальнейшем улучшении скорости генерации и оценки движений.

  • Генератор ходов теперь включал 64 схемы передатчика и приемника. Каждый передатчик запомнил фигуру на своем поле и возможные ходы, которые она могла сделать. Каждый получатель обнаруживал входящие ходы или угрозы от других фигур. Дополнительная схема обнаружила рокировку и проход.
  • Теперь оценщик мог исследовать квадратный контроль, используя 64 специализированных схемы, а также пешечную структуру.
  • Память для транспонирования была увеличена до 1 Мб.
  • Алгоритм Альфа-бета Белль теперь был реализован в микрокоде, управляя генератором ходов, вычислителем и таблицей транспозиции.

Третье поколение Belle управлялось компьютером LSI-11. В зависимости от стадии игры он проверял от 100 000 до 200 000 движений в секунду.

Карьера

Ранние соревнования

Программная версия Belle Кена Томпсона участвовала в соревнованиях 1972 года США Открытый чемпионат по шахматам и чемпионат по компьютерным шахматам ACM 1973 года. В течение следующего года Белль сыграла несколько игр UCSF и финишировала 3-1 в компьютерном чемпионате ACM 1974 года.

В 1978 году второе поколение Белль соревновалось на чемпионате ACM по компьютерным шахматам, выиграв с отличным результатом 4/0. В ключевой игре против Chess 4.7, занявшего второе место, Belle проверяла 5000 позиций в секунду, а Chess 4.7 - 3500.

World Championship

В 1980 г. Белль в третьем поколении выиграла третий чемпионат мира по компьютерным шахматам в Линце, Австрия. После четырех туров у него был счет 3,5 / 4, связанный с шахматной машиной. В тай-брейке за титул чемпиона мира Белль прорвала защиту Хаоса Алехина и объявила мат в 8-м ходу, выиграв игру на 41-м ходу. Belle просматривала 160 000 позиций в секунду.

Master Rating

В 1983 году Belle участвовала в US Open, где закончила 8,5 / 3,5 с рейтингом производительности 2363. Позже в том же году USCF присвоил Белль звание мастера. Поскольку она достигла этого уровня раньше, чем любой другой шахматный компьютер, Belle была награждена призом Фредкина в размере 5000 долларов. Правление Белль закончилось, когда она заняла шестое место в Четвертом чемпионате мира по компьютерным шахматам, несмотря на то, что была фаворитом на победу. Ему удалось еще раз победить на чемпионате ACM в 1986 году, прежде чем он завершил карьеру.

Анализ производительности

Благодаря своей способности генерировать и анализировать многие шахматные позиции, Belle представила подход грубой силы к шахматным вычислениям. В конце 1970-х годов Томпсон заинтересовался ограничениями этого метода, играя разные версии Belle друг против друга. Использование идентичных машин позволило ему свести к минимуму влияние стиля игры отдельного автомата, изолировав при этом эффекты глубины поиска. Например, если один компьютер Belle выполняет поиск на трех уровнях, другой может выполнять поиск до 4. Томпсон пришел к выводу, что с каждым дополнительным уровнем поиска Belle улучшалась примерно на 250 пунктов. Этот эффект был воспроизведен в экспериментах с самостоятельной игрой на разных машинах. Однако после 2000 очков Томпсон обнаружил, что улучшения стабилизировались.

См. Также

Примечания

Ссылки

  • Деннис Ричи (июнь 2001 г.). «Кен, Unix и игры». Журнал ICGA. 24 (2).
  • Condon, J.H. и К. Томпсон, "Belle Chess Hardware", In Advances in Computer Chess 3 (под редакцией М. Р. Б. Кларка), Pergamon Press, 1982.
  • Музей истории компьютеров
  • Леви, Д.; Mittman, B.; Новорожденный, М. (1980). «3-й чемпионат мира по компьютерным шахматам». Коммуникации ACM. 23 (11): 661–664. ISSN 0001-0782.
  • Хайнц, Э. А. (2001). «Самостоятельная игра, глубокий поиск и убывающая отдача - Кен Томпсон». Журнал ICGA. 24 (2): 75–79. DOI : 10.3233 / ICG-2001-24205. ISSN 1389-6911.
  • Кондон, Джозеф Х. ; Томпсон, Кен (1983). «Глава 9: Белль». Во Фрей, Питер У. (ред.). Шахматное мастерство в человеке и машине. Нью-Йорк: Springer-Verlag. С. 201–210. ISBN 978-0-387-90815-1.
  • Новорожденный, Монро. (1997). Каспаров против Deep Blue: компьютерные шахматы достигли совершеннолетия. Нью-Йорк: Спрингер. ISBN 978-0-387-94820-1.
Последняя правка сделана 2021-05-12 10:55:54
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте