Белль (шахматная машина) - Belle (chess machine)

Эта статья является частью серии, посвященной
Шахматное программирование
Шахматы Programming.svg
Представительства Совета
Шахматные компьютеры
Шахматные движки

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

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

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

Происхождение

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

Дизайн

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

Аппаратный генератор ходов

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

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

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

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

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

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

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

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

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

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

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

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

Карьера

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

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

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

Чемпионат мира

В 1980 году третье поколение Belle выиграло третий чемпионат мира по компьютерным шахматам в Линце, Австрия. После четырех раундов у него был счет 3,5 / 4, связанный с Хаос шахматная машина.[10] В тай-брейке за титул чемпиона мира Белль прорвалась через Хаос. Защита Алехина и продолжил заявлять Шах и мат в 8, выиграв игру на 41 ходу.[11] Во время игры Белль просматривала 160000 позиций в секунду.[12]

Мастер Рейтинг

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

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

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

Смотрите также

Примечания

  1. ^ Новорожденный 1997 г.р. 147.
  2. ^ Новорожденный 1997 г.р. 91.
  3. ^ а б c Фрей 1983 г. с. 202.
  4. ^ Фрей 1983 г. с. 203.
  5. ^ а б Фрей 1983 г. с. 204.
  6. ^ Фрей 1983 г. с. 205.
  7. ^ Фрей 1983 г. с. 206.
  8. ^ Фрей 1983 г. с. 207.
  9. ^ Новорожденный 1997 г.р. 93.
  10. ^ Новорожденный 1997 г.р. 98.
  11. ^ Леви 1980 стр. 663.
  12. ^ Леви 1980 стр. 664.
  13. ^ а б Новорожденный 1997 г.р. 92.
  14. ^ Новорожденный 1997 г.р. 122.
  15. ^ Фрей 1983 г. с. 209.
  16. ^ Хайнц 2001 стр. 76.
  17. ^ Новорожденный 1997 г.р. 123.

Рекомендации

  • Деннис Ричи (Июнь 2001 г.). "Кен, Unix и игры". Журнал ICGA. 24 (2).
  • Кондон, Дж. и К. Томпсон, "Belle Chess Hardware", In Успехи в компьютерных шахматах 3 (под ред. М. Р. Б. Кларка), Pergamon Press, 1982.
  • Музей истории компьютеров
  • Леви, Д .; Mittman, B .; Новорожденный, М. (1980). «3-й чемпионат мира по компьютерным шахматам». Коммуникации ACM. 23 (11): 661–664. ISSN  0001-0782.
  • Хайнц, Э. А. (2001). «Самостоятельная игра, глубокий поиск и убывающая отдача - Кен Томпсон». Журнал ICGA. 24 (2): 75–79. Дои: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.