Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Эта статья является частью серии статей о
Шахматное программирование
Шахматы Programming.svg
Представительства Совета
Шахматные компьютеры
Шахматные движки

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

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

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

Истоки [ править ]

После работы над операционной системой Unix Кен Томпсон обратил свое внимание на компьютерные шахматы. [2] Летом 1972 года он начал работу над программой для PDP-11 , которая в конечном итоге стала Belle. В соревновании эта ранняя версия побудила Томпсона использовать метод грубой силы при разработке оборудования 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] В ключевой игре против Chess 4.7 , занявшего второе место, Belle проверяла 5000 позиций в секунду, а Chess 4.7 - 3500. [9]

Чемпионат мира [ править ]

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

Мастер Рейтинг [ править ]

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

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

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

См. Также [ править ]

  • Компьютерные шахматы
  • Глоссарий компьютерных шахматных терминов
  • Кен Томпсон (программист)
  • Джозеф Генри Кондон
  • Таблица эндшпиля
  • Bell Labs
  • Шахматный эндшпиль без пешек # Браун против BELLE

Примечания [ править ]

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

Ссылки [ править ]

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