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

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

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

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

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

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

дизайн

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

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

	а	б	c	d	е	ж	грамм	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	грамм	час

Определение хода.
Belle представляет ход путем определения квадрата «от» и квадрата «к» с использованием счетчика смещения ∆xy. Ход ладьи выше имеет смещение (2,0), а ход слона - (2,2).

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

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

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

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

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

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

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

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

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

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

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

Карьера

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

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

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

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

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

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

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

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

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

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

Ноты

Ссылки

Деннис Ричи (июнь 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.

Languages

In other projects