Автоматизированная система управления игрой в шахматы
Изобретение относится к компьютерным играм и может быть использовано для управления игрой в шахматы. Техническим результатом является повышение уровня игры. Система содержит блок внешнего ввода, блок перебора позиций, блок памяти позиций, коммутатор, блок индикации, блок выдачи хода, блок сравнения позиций, блок памяти стандартных позиций, датчик выбора случайного варианта и оценки материала, узел оценки взаимодействия фигур, компаратор, задатчик и сумматор. 3 з.п. ф-лы, 2 ил., 3 табл.
Изобретение относится к настольным играм и может быть использовано в конструкции автоматизированной системы управления игрой в шахматы (АСУШ).
Известна система управления игрой в шахматы, содержащая блок внешнего ввода, подключенный ко входу блока перебора вариантов, и вычислительный узел оценки материала, подключенный к выходу блока перебора вариантов (Claude E. Shannon. Programming a computer for playing chess. Philosophical Magazihe, 1950, 41 p. 256-275). Для уточнения реализуемой вычислительным узлом оценочной функции неточной цели игры в шахматы система дополнительно снабжена блоком определения горизонта дерева перебора вариантов, выполненным с возможностью минимизации времени передвижения фигур по оптимальным траекториям (Ботвинник М.М. От шахматиста - к машине. М., ФиС, 1979). Данная система представляет собой машинный вариант системы шахматного мышления гроссмейстера, чего, как показала практика, недостаточно для обеспечения высокого класса игры компьютерных шахмат. В связи с этим была предложена система управления игрой в шахматы, содержащая блок внешнего ввода, блок перебора позиций, вычислительный блок оценки материального и позиционного преимущества, блок памяти позиций и блок индикации (Адельсон-Вельский Г.М., Арлазоров В.Л., Битман А.Р., Донской М.В. Машина играет в шахматы. М., "Наука", 1983). Тем не менее такая система управления не обеспечивает уровня игры соответствующего устройства выше 1-го спортивного разряда. Кроме того, вышеуказанные источники не содержат информации, достаточной для технической реализации АСУШ. Известна также универсальная система управления настольной игрой, включая шахматы, содержащая блок внешнего ввода, блок индикации и узлы оценки расположения фигур и вычисления динамического преимущества в зависимости от траектории их перемещения, выходы которых соединены с соответствующими входами сумматора (US 5228699, A 63 F 3/02, 1993). Однако данная система неудобна в работе, поскольку она просматривает лишь варианты игры, задаваемые пользователем. Кроме того, она неудобна в настройке для любой конкретной игры, в частности в шахматы, поскольку не содержит блоков специфической оценки шахматной позиции и динамики ее изменения, что резко снижает силу игры. Наиболее близкой к предлагаемой является АСУШ, содержащая блок внешнего ввода, блок перебора позиций, узел оценки расположения фигур в зависимости от занимаемого ими поля, коммутатор очереди хода, блок индикации и блок памяти позиций, вход которого связан с блоком внешнего ввода (US 5098106, A 63 F 3/02, 1990). Однако сила игры данной АСУШ не превышает уровня обучающего шахматиста, о чем сообщается в описании прототипа. Техническая задача предлагаемой АСУШ - повышение уровня игры в шахматы. Решение указанной технической задачи заключается в том, что в АСУШ, содержащую блок внешнего ввода, блок перебора позиций, узел оценки расположения фигур в зависимости от занимаемого ими поля, блок памяти позиций, коммутатор и блок индикации, внесены следующие изменения: 1. АСУШ дополнительно содержит: 1.1. узел оценки материала; 1.2. узел оценки взаимодействия фигур; 1.3. компаратор; 1.4. задатчик; 1.5. блок выдачи хода. 2. Функциональные блоки и узлы соединены следующим образом: блок внешнего ввода подключен в первому входу коммутатора, выход блока выдачи хода подключен ко второму входу коммутатора, выход коммутатора подключен ко входу блока перебора позиций и к блоку индикации, информационный выход блока перебора позиций связан с первым входом блока памяти позиций и входами узлов оценки расположения фигур, оценки материала и оценки взаимодействия фигур, управляющий выход блока перебора позиций соединен с управляющим входом блока выдачи хода, выходы узлов оценки расположения фигур, оценки материала и оценки взаимодействия фигур связаны, соответственно, с первым, вторым и третьим входом сумматора, первый вход компаратора соединен с выходом узла оценки материала, второй вход компаратора подключен к выходу задатчика, выход компаратора связан с управляющими входами узлов оценки расположения фигур, оценки материала, оценки взаимодействия фигур и со входом задатчика с образованием гистерезисной характеристики сигнала, поступающего на второй вход компаратора, выход сумматора связан со вторым входом блока памяти позиций, а выход блока памяти позиций соединен со входом блока выдачи хода. Оптимальным является выполнение узла оценки материала в виде вычислительного устройства, формирующего весовую функцию материала согласно формуле
м= 
Ai-aj, (1) где м - значение весовой функции материала; Ai - вес i-фигуры белых;aj - вес j-фигуры черных. Узел оценки расположения фигур может быть выполнен в виде вычислительного устройства, формирующего весовую функцию расположения фигур согласно формуле
p= Si-sj, (2)где
p - значение весовой функции расположения фигур;Si - вес i-фигуры белых на соответствующем поле;
sj - вес j-фигуры черных на соответствующем поле. Узел оценки взаимодействия фигур может быть выполнен в виде вычислительного устройства, формирующего весовую функцию взаимодействия фигур согласно формуле
в= Rim-rjn, (3)где
в - значение весовой функции взаимодействия фигур;Rim - вес i-фигуры белых в отношении m-го вида позиционного преимущества;
rjm - вес j-фигуры черных в отношении n-го вида позиционного преимущества. Для повышения культуры разыгрывания стандартных позиций, например, дебюта, АСУШ может быть оснащена блоком памяти стандартных позиций (блоком памяти дебютов) и блоком сравнения позиций. В этом варианте первый вход блока сравнения позиций связан с выходом блока перебора позиций, второй вход блока сравнения позиций связан с первым выходом блока памяти стандартных позиций, выход блока сравнения позиций соединен с управляющим входом блока памяти стандартных позиций, а выход блока памяти стандартных позиций связан с третьим входом коммутатора. Для обеспечения возможности случайного выбора известных альтернативных продолжений выход блока памяти стандартных позиций связан с третьим входом коммутатора через датчик выбора случайного варианта. Причинно-следственная связь внесенных изменений с повышением уровня игры заключается в уточнении значения формируемого на выходе сумматора сигнала, используемого для принятия блоком выдачи хода решения о выбираемом варианте перемещения фигуры. Это уточнение достигается путем формирования трех оценок просматриваемых позиций: материального преимущества, позиционного преимущества (кинетическая характеристика) и расположения сил (потенциальная характеристика). Эти оценки формируются, соответственно, узлами оценки материала, взаимодействия и расположения фигур. На фиг. 1 приведена функциональная схема предлагаемой АСУШ. На фиг. 2 приведена диаграмма, выведенная на блок индикации при анализе АСУШ позиции приведенного примера. АСУШ содержит блок 1 внешнего ввода, блок 2 перебора позиций, блок 3 памяти позиций, коммутатор 4, блок 5 индикации, блок 6 выдачи хода и блок 7 определения веса позиции, включающий узел 8 оценки расположения фигур, узел 9 оценки материала, узел 10 оценки взаимодействия фигур, компаратор 11, задатчик 12 и сумматор 13. Блок 1 внешнего ввода подключен к первому входу коммутатора 4, выход блока 6 выдачи хода подключен ко второму входу коммутатора 4, выход коммутатора 4 подключен ко входу блока 2 перебора позиций и к блоку 5 индикации; информационный выход блока 2 перебора позиций связан с первым входом блока 3 памяти позиций и входами узла 8 оценки расположения фигур, узла 9 оценки материала и узла 10 оценки взаимодействия фигур, управляющий выход блока 2 перебора позиций соединен с управляющим входом блока 6 выдачи хода, выходы узла 8 оценки расположения фигур, узла 9 оценки материала и узла 10 оценки взаимодействия фигур связаны, соответственно, с первым, вторым и третьим входом сумматора 13, первый вход компаратора 11 соединен с выходом узла 9 оценки материала, второй вход компаратора 11 подключен к выходу задатчика 12, выход компаратора 11 связан с управляющими входами узла 8 оценки расположения фигур, узла 9 оценки материала, узла 10 оценки взаимодействия фигур и со входом задатчика 12 с образованием гистерезисной характеристики сигнала, поступающего на второй вход компаратора 11, выход сумматора 13 связан со вторым входом блока 3 памяти позиций, а выход блока 3 памяти позиций соединен со входом блока 6 выдачи хода. Приведенный на фиг. 1 вариант АСУШ дополнительно содержит блок 14 сравнения позиций, блок 15 памяти стандартных позиций и датчик 16 выбора случайного варианта, причем первый вход блока 14 сравнения позиций связан с выходом блока 2 перебора позиций, второй вход блока 14 сравнения позиций связан с первым выходом блока 15 памяти стандартных позиций, выход блока 14 сравнения позиций соединен с управляющим входом блока 15 памяти стандартных позиций, выход которого связан с третьим входом коммутатора 4 через датчик 16 выбора случайного варианта. Включение датчика 16 целесообразно в том случае, если блок 15 памяти стандартных позиций содержит базу данных (БД) шахматных дебютов. Если же блок 15 содержит БД по эндшпилю, его выход непосредственно подключен к третьему входу коммутатора 4. Блок 1 внешнего ввода может быть выполнен в виде устройства для демонстрации шахматной партии, включающего шахматную доску с фигурами, выполненными с элементами кодирования, установленными в их основаниях, при этом на полях шахматной доски расположены элементы считывания кода фигуры, каждый из которых через дешифратор и блок управления связан с блоком индикации, как это описано в (SU 1787465 A1, A 63 F 3/02, 1993; RU 2075323, A 63 F 3/02, 1997). Кроме того, сигнал внешнего ввода может быть непосредственно принят с удаленного терминала, в частности, в соревновании шахматных компьютеров. Блок 2 перебора позиций может быть выполнен в виде вычислительного устройства дерева перебора позиций, выход которого связан со стеком, управляемым таймером (если игра ведется по временному контролю на партию, ход или темп игры партнера) и/или счетчиком (если расчет дерева перебора ведется на заданное число полуходов). Блок 6 выдачи хода выполнен на базе регистра памяти. Блок 14 сравнения позиций представляет собой второй компаратор. Датчик 16 выбора случайного варианта выполнен на базе стандартного датчика случайных чисел. АСУШ работает следующим образом. Информационный сигнал начальной расстановки фигур или хода противника поступает из блока 1 внешнего ввода на первый вход коммутатора 4. Этот вход имеет наибольший приоритет и поэтому немедленно передает информацию на блок 5 индикации и блок 2 перебора позиций, где производится расчет координат расстановки фигур (позиций) дерева перебора на глубину, ограниченную заданным временем расчета или числом полуходов. Каждая позиция от блока 2 передается в блок 7 определения веса позиции. Эти позиции и соответствующие им значения весов запоминаются в БД, реализованной блоком 3 памяти позиций. По окончании ввода данных в блок 3 блок 2 перебора позиций выдает сигнал управления (флажковый сигнал) блоку 6 выдачи хода. При этом блок 6 выбирает из БД блока 3 позицию с максимальным значением веса и передает ее на второй вход коммутатора 4. Этот вход имеет более низкий приоритет, чем первый вход, и поэтому в отсутствии передачи сигнала по первому входу коммутатора 4 данные со второго входа будут выданы на блок 5 индикации и блок 2 перебора позиций. В одном из двоичных разрядов данных, передаваемых от коммутатора 4 к блоку 2, передается сигнал управления очередью хода, запрещающий выдачу информации по второму входу коммутатора 4 во время обдумывания хода противником. В этом случае АСУШ находится в режиме ожидания хода от блока 1. При подключении блока 15 памяти стандартных позиций в режиме библиотеки дебютов блок 14 сравнения позиций просматривает БД блока 15 и при обнаружении позиции, идентичной передаваемой блоком 2, выдает на вход датчика 16 выбора случайного варианта все известные из просматриваемой позиции продолжения. Датчик 16 случайным образом выбирает одно из этих продолжений и передает его на третий вход коммутатора 4. Этот вход имеет средний приоритет и поэтому передает информацию на выход коммутатора 4 в отсутствии передачи сигнала блоком 1, игнорируя сигнал по второму входу коммутатора 4. При наличии блоков и узлов фиг. 1 в составе вычислительной техники универсального назначения АСУШ по описанной схеме может быть реализована в программном исполнении. Однако при частом использовании АСУШ целесообразно ее выполнение в виде специализированной конструкции, в том числе подключаемой к компьютеру. При работе данной АСУШ блок 7 определения веса позиции принимает информацию об анализируемых позициях от блока 2 перебора позиций на входы узла 8 оценки расположения фигур, узла 9 - оценки материала и узла 10 - оценки взаимодействия фигур. При этом узел 8 вычисляет значение весовой функции расположения фигур
p согласно формуле (2), узел 9 - значение весовой функции материала м согласно формуле (1), а узел 10 - значение весовой функции взаимодействия фигур в согласно формуле (3). Вычислительные значения м, p и в поступают на вход сумматора 13, который формирует и передает на второй вход блока 3 памяти позиций информацию о значении весовой функции позиции 
согласно формуле = м+p+в. (4)По сигналу от блока 2, передаваемому по одному из разрядов его выхода, блок 3 изменяет адрес записи позиции и ее веса. Весовые функции
м, p и в являются нелинейными. Нелинейности учитываются блоком 7 следующим образом:1. С помощью компаратора 11 на схеме фиг. 1 сформирована двухпозиционная гистерезисная характеристика весовых функций
м, p и в в зависимости от стадии шахматной партии - миттельшпиль и эндшпиль (возможна реализация трехпозиционной характеристики - дебют, миттельшпиль, эндшпиль, а также многопозиционных нелинейных характеристик). На первый вход компаратора 11 поступает значение функции м, имевшее место в предыдущей позиции, а на второй вход компаратора 11 - пороговое значение з, по достижении которого в связи с происходящим при игре уменьшением количества шахматных фигур наступает переход из миттельшпиля (или даже из дебюта) в эндшпиль. Этот момент фиксирует компаратор 11 изменением логического сигнала на его выходе, который используется узлами 8-10 для обращения к системам оценок значений Ai; aj; Si; sj; Rim; rjn определяемых функций с учетом стадии партии. Одновременно инвертированный сигнал с выхода компаратора 11, поступив на вход задатчика 12, изменит пороговое значение з из расчета образования гистерезисной обратной связи компаратора 11 с задатчиком 12. Новое значение з превышает предыдущее, тем самым допуская обратное переключение из эндшпиля в миттельшпиль, например, в случае проведения пешки в ферзя. Необходимость реализации гистерезисной характеристики объясняется тем, что при первом переходе порогового значения з изменяется значение весовой функции м в сторону увеличения. 2. Внутри каждой стадии шахматной партии функции Ai, aj, Si, sj, Rim, rjn, используемые для определения сложных функций м, p и в, в свою очередь, нелинейны. Поэтому они введены в БД, которыми снабжены узлы 8-10, в виде соответствующих таблиц. Фрагменты этих БД приведены в табл. 1-3. Например, для пешки АСУШ в дебюте и миттельшпиле Ai=100, а в эндшпиле - Ai=120 (табл. 1), расположение короля на поле c2 в дебюте и миттельшпиле дает оценку Si= 10, а в эндшпиле - Si=20, поскольку сила короля в эндшпиле возрастает, причем в дебюте, где важно обеспечить безопасность короля, его расположение на полях по месту рокировки - c1, g1 - оценивается выше, чем на других полях, в эндшпиле же наиболее высокое значение Si или sj дается при расположении короля в центре (табл. 2), взаиморасположение ладьи позади проходной пешки противника в дебюте и миттельшпиле не оценивается, тогда как в эндшпиле этот вид преимущества дает оценки Rim=12 и rjn=15 (табл. 3). Стиль игры под управлением АСУШ определяется нелинейными функциями, сформированными как в табл. 1-3 и занесенными в БД вычислительных узлов 8-10. Эти же функции определяют класс игры в шахматы под управлением предлагаемой АСУШ. Поэтому при эксплуатации АСУШ записи БД табл. 1-3 могут корректироваться. Об эффективности предлагаемой АСУШ можно судить из описываемого далее примера ее работы в составе игрового комплекса "Unigue Chess". Исходная позиция (фиг. 2) взята из 6-й партии шахматного матча между суперкомпьютером "Deep Blue" - Г.Каспаров (Нью-Йорк, 1997), начатой ходами: 1. e2-e4 c7-c6 2. d2-d4 d7-d5 3. Kb1-c3 d4xe4 4. Kc3xe4 Kb8-d7 5. Ke4-g5 Kg8-f6 6. Cf1-d3 e7-e6 7. Kg1-f3 h7-h6 8. Kg5xe6. В данной позиции Г.Каспаров сыграл 8. ... Фd8-e7? и после стандартного варианта 9. 0-0 f17xe6 10. Cd3-g6+ Kpe8-d8 11. Cc1-f4 получил позицию с неразвитыми заблокированными фигурами и проиграл партию, а с ней и матч, впервые в истории выигранный компьютером у чемпиона мира по шахматам. В позиции на фиг. 2 АСУШ наибольшее предпочтение отдала варианту 8. ... f7xe6 9. Cd3-g6+Kpe8-e7 10. 0-0 Фd8-c7 11. c2-c4 Kpe7-d8 12. Фd1-e2 Cf8-d6 13. Лf1-d1 Kd8-f8 14. Сg6-c2 Kf8-d7 15. c4-c5 Cd6-e7 16. Фe2xe6 g7-g5 17. Лd1-e1 Kd1-e1 Kd7xc5 18. Фе6xe7+Фc7xe7 19. Лe1xe7 Kpd8xe7 20. d4xc5 Cc8-g4, где в связи с произошедшим неизбежным разменом ферзей материальный перевес черных легко реализуем. По результатам аппробации предлагаемой АСУШ в соревнованиях с шахматистами и компьютерными шахматами ее уровень характеризуется значением коэффициента Эло 2170-2450.
Формула изобретения
м= Ai-aj,где
м - значение весовой функции белых и черных фигур;Ai - вес i-фигуры белых;
аj - вес j-фигуры черных;
узел оценки расположения фигур выполнен с возможностью формирования на выходе весовой функции расположения фигур согласно формуле
p= Si-sj,где
p - значение весовой функции расположения фигур;Si - вес i-фигуры белых на соответствующем поле;
sj - вес j-фигуры черных на соответствующем поле;
а узел оценки взаимодействия фигур выполнен с возможностью формирования на выходе весовой функции взаимодействия фигур согласно формуле
в= Rim-rjn,где
в - значение весовой функции взаимодействия фигур;Rim - вес i-фигуры белых в отношении m-го вида позиционного преимущества;
rjn - вес j-фигуры черных в отношении n-го вида позиционного преимущества. 3. Автоматизированная система управления игрой в шахматы по п.1 или 2, отличающаяся тем, что она дополнительно оснащена блоком памяти стандартных позиций и блоком сравнения позиций, причем первый вход блока сравнения позиций связан с выходом блока перебора позиций, второй вход блока сравнения позиций связан с первым выходом блока памяти стандартных позиций, выход блока сравнения позиций соединен с управляющим входом блока памяти стандартных позиций, а выход блока памяти стандартных позиций связан с третьим входом коммутатора. 4. Автоматизированная система управления игрой в шахматы по п.3, отличающаяся тем, что связь блока памяти стандартных позиций с третьим входом коммутатора выполнена через датчик выбора случайного варианта.
РИСУНКИ
Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4
Похожие патенты:
