Белль (шахматный автомат)
| Эта статья является частью серии, посвящённой |
| Шахматное программирование |
|---|
 |
Belle — шахматный компьютер , разработанный Джо Кондоном (аппаратное обеспечение) и Кеном Томпсоном (программное обеспечение) в Bell Labs . В 1983 году это была первая машина, достигшая уровня мастера , с USCF рейтингом 2250. Она пять раз выиграла ACM чемпионат Северной Америки по компьютерным шахматам и чемпионат мира по компьютерным шахматам 1980 года . Это была первая система, выигравшая с использованием специализированного шахматного оборудования.
В своем последнем воплощении Belle использовала LSI-11 универсальный компьютер для координации своего шахматного оборудования. Было три специальные доски для генерации ходов, четыре специальные доски для оценки позиции и микрокода реализация отсечения альфа-бета . Компьютер также имел один для хранения мегабайт памяти таблиц транспонирования .
По окончании карьеры Белль была подарена Смитсоновскому институту . Общая архитектура Belle использовалась при первоначальном проектировании ChipTest , прародителя IBM Deep Blue . [1]
Происхождение
[ редактировать ]После работы над операционной системой Unix Кен Томпсон обратил свое внимание на компьютерные шахматы. [2] Летом 1972 года он начал работу над программой для PDP-11 , которая в конечном итоге стала Belle. На соревнованиях эта ранняя версия побудила Томпсона использовать грубый подход при разработке оборудования Belle. [3]
Дизайн
[ редактировать ]Дизайн Belle за время своего существования претерпел множество изменений. Первоначальная шахматная программа была переписана, чтобы использовать поиск состояния покоя по принципу «ход против оценки» и оценивать позиции, отдавая приоритет материальному преимуществу . Белль также использовала таблицу транспонирования , чтобы избежать повторного изучения позиций. [3]
Генератор аппаратных перемещений
[ редактировать ]| а | б | с | д | и | ж | г | час | ||
| 8 |      | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| а | б | с | д | и | ж | г | час | ||
Belle представляет ход, определяя квадрат «от» и квадрат «до», используя счетчик смещения ∆xy. Ход ладьи выше имеет смещение (2,0), а ход слона – (2,2).
В 1976 году Джо Кондон реализовал аппаратный генератор движений для использования с программной версией Belle на PDP-11. Его конструкция состояла из нескольких этапов:
- «от» 6-битный регистр ищет на доске дружественные фигуры.
- Как только дружественная фигура найдена, счетчик смещения хода ∆xy выдает бит-код смещения хода, например (2,2) для слона или (2,0) для ладьи .
- Это смещение объединяется с содержимым регистра «от» и перемещается в 6-битный регистр «до». Эти два регистра полностью описывают потенциальный ход .
- Тестовая схема сравнивает ход с существующей доской, чтобы определить, является ли ход псевдозаконным . Если это так, регистры «от» и «до» выводятся в программное обеспечение. [3]
Аналогичная серия шагов использует генератор ходов, чтобы проверить, является ли псевдолегальный ход на самом деле законным. Это гарантирует, что ход не поставит под контроль движущуюся сторону . [4]
Второе поколение
[ редактировать ]Второе поколение Belle было выпущено в 1978 году. В нем было реализовано несколько улучшений по сравнению со своим предшественником.
- Генератор ходов имел собственный стек , который он использовал для хранения ходов, а не для вывода их в программное обеспечение.
- Добавлена аппаратная реализация оценщика позиции.
- Аппаратная реализация транспозиционной памяти.
Эти изменения снизили роль программного обеспечения PDP-11. Теперь программное обеспечение управляло этими тремя устройствами и запускало алгоритм альфа-бета-отсечения. Второе поколение Belle могло выполнять поиск со скоростью 5000 позиций в секунду. [5]
Третье поколение
[ редактировать ]Последнее воплощение Belle было завершено в 1980 году. Оно заключалось в дальнейших улучшениях скорости генерации и оценки ходов.
- Генератор ходов теперь включал в себя 64 схемы передатчика и приемника. Каждый передатчик запоминал фигуру на своем поле и возможные ходы, которые эта фигура могла сделать. Каждый получатель обнаруживал входящие ходы или угрозы со стороны других фигур. Дополнительная схема обнаружила рокировку и проход на проходе . [6]
- Теперь оценщик мог исследовать контроль поля, используя 64 специализированные схемы, а также пешечную структуру .
- Память для транспозиции увеличена до 1 Мб.
- Альфа-бета-алгоритм Белль теперь был реализован в микрокоде, управляя генератором ходов, оценщиком и таблицей транспонирования. [7]
Третье поколение Belle управлялось компьютером LSI-11. В зависимости от этапа игры он проверял от 100 000 до 200 000 ходов в секунду. [8]
Карьера
[ редактировать ]Ранние соревнования
[ редактировать ]Программная версия Belle, созданная Кеном Томпсоном, участвовала в Открытом чемпионате США по шахматам 1972 года и Компьютерном чемпионате ACM 1973 года. В течение следующего года Белль сыграла несколько игр UCSF и закончила со счетом 3–1 на чемпионате ACM по компьютерным шахматам 1974 года.
В 1978 году второе поколение Белль участвовало в чемпионате ACM по компьютерным шахматам, одержав четыре идеальных победы в четырех играх. [5] В ключевой игре против Chess 4.7 , занявшей второе место, Белль проверяла 5000 позиций в секунду, а Chess 4.7 проверяла 3500. [9]
Чемпионат мира
[ редактировать ]В 1980 году третье поколение Белль выиграло третий чемпионат мира по компьютерным шахматам в Линце, Австрия. После четырех раундов его результат в четырех играх составил 3,5, что сравнялось с шахматной машиной Хаоса . [10] На тай-брейке за титул чемпионки мира Белль прорвала защиту Алехина Хаоса и объявила мат за восемь ходов, выиграв партию на 41-м ходу. [11] Во время игры Белль просматривала 160 000 позиций в секунду. [12]
Мастер рейтинг
[ редактировать ]В 1983 году Белль участвовала в Открытом чемпионате США, где набрала 8,5 очков в двенадцати играх с рейтингом результативности 2363. Позже в том же году USCF присвоила Белль звание мастера. [13] Поскольку он достиг этого уровня раньше любого другого шахматного компьютера, Belle была удостоена премии Фредкина в размере 5000 долларов. Правление Белль закончилось, когда она заняла шестое место на четвертом чемпионате мира по компьютерным шахматам, несмотря на то, что была фаворитом на победу. [13] Прежде чем уйти в отставку, ему удалось еще раз одержать победу на чемпионате ACM в 1986 году.
Анализ производительности
[ редактировать ]Благодаря своей способности генерировать и анализировать множество шахматных позиций, Belle представляла собой грубый подход к шахматным вычислениям. В конце 1970-х Томпсон заинтересовался пределами этого метода, противопоставляя разные версии Белль друг другу. Использование идентичных машин позволило ему свести к минимуму влияние стиля игры отдельной машины, одновременно изолируя влияние глубины поиска . Например, если один компьютер Belle выполняет поиск на три уровня, другой может искать на четыре. Томпсон пришел к выводу, что за каждый дополнительный уровень поиска рейтинг Белль улучшался примерно на 250 пунктов. [14] [15] Этот эффект был воспроизведен в экспериментах с самостоятельной игрой на разных машинах. [16] Однако после отметки в 2000 пунктов Томпсон обнаружил, что улучшения стабилизировались. [17]
См. также
[ редактировать ]- Компьютерные шахматы
- Словарь компьютерных шахматных терминов
- Кен Томпсон (программист)
- Джозеф Генри Кондон
- База таблицы эндшпиля
- Белл Лаборатории
- Безпешечный шахматный эндшпиль § Браун против БЕЛЬ
Примечания
[ редактировать ]- ^ Новорожденный 1997 г. с. 147.
- ^ Новорожденный 1997 г. с. 91.
- ^ Перейти обратно: а б с Фрей 1983 с. 202.
- ^ Фрей 1983 с. 203.
- ^ Перейти обратно: а б Фрей 1983 с. 204.
- ^ Фрей 1983 с. 205.
- ^ Фрей 1983 с. 206.
- ^ Фрей 1983 с. 207.
- ^ Новорожденный 1997 г. с. 93.
- ^ Новорожденный 1997 г. с. 98.
- ^ Леви 1980 стр. 663.
- ^ Леви 1980 стр. 664.
- ^ Перейти обратно: а б Новорожденный 1997 г.р. 92.
- ^ Новорожденный 1997 г. с. 122.
- ^ Фрей 1983 с. 209.
- ^ Хайнц 2001 с. 76.
- ^ Новорожденный 1997 г. с. 123.
Ссылки
[ редактировать ]- Деннис Ричи (июнь 2001 г.). «Кен, Unix и игры» . Журнал ICGA . 24 (2).
- Кондон, Дж. Х. и К. Томпсон, «Оборудование Belle Chess», «Достижения в компьютерных шахматах 3 » (изд. MRBClarke), Pergamon Press, 1982.
- Музей компьютерной истории
- Леви, Д.; Миттман, Б.; Ньюборн, М. (1980). «3-й чемпионат мира по компьютерным шахматам». Коммуникации АКМ . 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 .