Автоматизированная система управления игрой в шахматы

 

Изобретение относится к настольным играм и может быть использовано в конструкции автоматизированной системы управления игрой в шахматы. Техническим результатом является сокращение времени выбора оптимального варианта без снижения уровня игры. Система содержит блок внешнего ввода, блок перебора позиций, блок определения веса позиции, блок выдачи хода, блок индикации и коммутатор. 2 ил.

Изобретение относится к настольным играм и может быть использовано в конструкции автоматизированной системы управления игрой в шахматы (АСУШ).

Известна система управления игрой в шахматы, содержащая блок внешнего ввода, подключенный ко входу блока перебора вариантов и вычислительный узел оценки материала, подключенный к выходу блока перебора вариантов (Claude E. Shannon. Programming a computer for playing chess. Philosophical Magazine, 1950, 41, p. 256-275). Для уточнения реализуемой вычислительным узлом оценочной функции неточной цели игры в шахматы система дополнительно снабжена блоком определения горизонта дерева перебора вариантов, выполненным с возможностью минимизации времени передвижения фигур по оптимальным траекториям (Ботвинник М.М. От шахматиста - к машине. М., ФиС, 1979).

Данная система представляет собой машинный вариант системы шахматного мышления гроссмейстера, чего, как показала практика, не достаточно для обеспечения высокого класса игры компьютерных шахмат. В связи с этим была предложена система управления игрой в шахматы, содержащая блок внешнего ввода, блок перебора позиций, вычислительный блок оценки материального и позиционного преимущества, блок памяти позиций и блок индикации (Адельсон-Вельский Г. М. , Арлазаров В.Л., Битман А.Р., Донской М.В. Машина играет в шахматы. - М.: Наука, 1983).

Тем не менее, такая система управления не обеспечивает уровня игры соответствующего устройства выше 1-го спортивного разряда. Кроме того, вышеуказанные источники не содержат информации, достаточной для технической реализации АСУШ.

Известна также АСУШ, содержащая блок внешнего ввода, блок перебора позиций, узел оценки расположения фигур в зависимости от занимаемого ими поля, коммутатор очереди хода, блок индикации и блок памяти позиций, вход которого связан с блоком внешнего ввода (US 5098106, A 63 F 3/02, 1990).

Однако сила игры данной АСУШ не превышает уровня обучающегося шахматиста.

Наиболее близкой к предлагаемой является АСУШ, содержащая блок внешнего ввода, блок перебора позиций, блок определения веса позиции, блок выдачи хода, блок индикации, коммутатор, выход которого связан с первым входом блока перебора позиций и блок памяти позиций, первый вход которого подключен к информационному выходу блока перебора позиций, а его второй вход подключен к блоку определения веса позиции. В оптимальном варианте известная АСУШ дополнительно содержит блок памяти стандартных позиций и блок сравнения позиций, что позволяет скорректировать игру с учетом шахматной теории, а блок определения веса позиции формирует значения весовой функции позиции с учетом расположения фигур, их ценности и возможных результатов взаимодействия (RU 2145730, G 06 F 19/00//G 06 F 161:00, 2000).

Однако данная АСУШ обладает длительным временем выбора оптимального варианта игры.

Техническая задача предлагаемой АСУШ - сокращение времени выбора оптимального варианта без снижения уровня игры.

Решение указанной технической задачи заключается в дополнении АСУШ элементами, служащими для ограничения дерева перебираемых вариантов шахматной игры. С этой целью АСУШ, содержащая блок внешнего ввода, блок перебора позиций, блок определения веса позиции, блок выдачи хода, блок индикации, коммутатор, выход которого связан с первым входом блока перебора позиций и блок памяти позиций, первый вход которого подключен к информационному выходу блока перебора позиций, а его второй вход подключен к блоку определения веса позиции, дополнительно оснащена блоком ограничения ветвей расчета, первый вход которого соединен с выходом блока памяти позиций, второй вход блока ограничения ветвей расчета и его управляющий вход связаны, соответственно, с информационным и управляющим выходами блока выдачи хода, выход блока ограничения ветвей расчета присоединен к третьему входу блока памяти позиций, второй вход блока перебора позиций подключен к выходу блока памяти позиций, а управляющий выход блока ограничения ветвей расчета подключен к управляющему входу блока перебора позиций.

На фиг.1 приведена функциональная схема предлагаемой АСУШ.

На фиг. 2 приведена диаграмма, выведенная на блок индикации при анализе АСУШ позиции приведенного примера.

АСУШ содержит блок 1 внешнего ввода, блок 2 перебора позиций, блок 3 памяти позиций, коммутатор 4, блок 5 индикации, блок 6 выдачи хода и блок 7 определения веса позиции. Блок 1 внешнего ввода подключен к первому входу коммутатора 4, выход блока 6 выдачи хода подключен ко второму входу коммутатора 4 и ко второму входу блока 8 ограничения ветвей расчета, выход коммутатора 4 подключен к первому входу блока 2 перебора позиций и к блоку 5 индикации; информационный выход блока 2 перебора позиций связан с первым входом блока 3 памяти позиций, входом блока 7 определения веса позиции и первым входом блока 9 сравнения позиций, управляющий выход блока 2 перебора позиций соединен с управляющим входом блока 6 выдачи хода, выход блока 3 памяти позиций соединен со входом блока 6 выдачи хода, с первым входом блока 8 ограничения ветвей расчета и со вторым входом блока 2 перебора позиций; управляющий выход блока 6 выдачи хода подключен к управляющему входу блока 8 ограничения ветвей расчета, выход которого соединен с третьим входом блока 3 памяти позиций; выход блока 7 определения веса позиции соединен со вторым входом блока 3 памяти позиций; управляющий выход блока 8 ограничения ветвей расчета подключен к управляющему входу блока 2 перебора позиций; второй вход блока 9 сравнения позиций связан с первым выходом блока 10 памяти стандартных позиций, выход блока 9 сравнения позиций соединен с управляющим входом блока 10 памяти стандартных позиций, второй выход которого связан с третьим входом коммутатора 4 через датчик 11 выбора случайного варианта. Включение датчика 11 целесообразно в том случае, если блок 10 памяти стандартных позиций содержит базу данных (БД) шахматных дебютов. Если же блок 10 содержит БД по эндшпилю, его выход непосредственно подключен к третьему входу коммутатора 4.

Блок 2 перебора позиций представляет собой вычислительное устройство дерева перебора позиций, возникающих при поступлении информации о начальной, заданной, в т.ч. ходом соперника, позиции (по первому входу) или об оптимальной позиции (по второму входу), в которой АСУШ должна выбрать наилучшее продолжение игры. Он вычисляет также общее количество сделанных полуходов и/или время игры для ограничения расчетов по количеству полуходов или по времени.

Блок 3 памяти позиций служит для реализации базы данных, в 1-м, 2-м и 3-м полях которой записаны соответственно: 1) сведения о расположении фигур; 2) значение оценочной функции (веса) данной позиции; 3) количество полуходов, обязательных для расчета дерева перебора вариантов из данной позиции.

Блок 6 выдачи хода выполнен на базе регистра памяти.

Блок 7 определения веса позиции выполнен с возможностью формирования на выходе весовой функции позиции по формуле Ω = ω_м+ ω_p+ ω_в, (1) где Ω- значение весовой функции позиции; ω_м- значение весовой функции белых и черных фигур; ω_p- значение весовой функции расположения фигур; ω_в- значение весовой функции взаимодействия фигур.

Такое же исполнение блока 7 имеет место в прототипе (RU 2145730). Возможен расчет весовой функции позиции по другим формулам.

Блок 8 ограничения ветвей расчета содержит компаратор, выполненный с настраиваемой зоной нечувствительности. Он служит для исключения из блока 3 памяти позиций тех записей, в которых значения весов не входят в упомянутую зону нечувствительности, если в поле 3 анализируемой записи не предусмотрено продление расчета варианта.

Блок 9 сравнения позиций представляет собой компаратор.

Датчик 11 выбора случайного варианта выполнен на базе стандартного датчика случайных чисел.

АСУШ работает следующим образом.

Информационный сигнал начальной расстановки фигур или хода противника поступает из блока 1 внешнего ввода на первый вход коммутатора 4. Этот вход имеет наибольший приоритет и поэтому немедленно передает информацию на блок 5 индикации и первый вход блока 2 перебора позиций, где производится расчет координат расстановки фигур (позиций) дерева перебора на один полуход. Каждая позиция от блока 2 передается в блок 7 определения веса позиции. Эти позиции и соответствующие им значения весов запоминаются в записях БД, реализованной блоком 3 памяти позиций по 1-му и 2-му полям соответственно. По окончании приема данных блоком 3 от блока 2 по первому входу блок 2 выдает флажковый сигнал управления блоку 6 выдачи хода. При этом блок 6 выбирает из БД блока 3 позицию с максимальным значением веса и передает ее на второй вход коммутатора 4. Этот вход имеет более низкий приоритет, чем первый вход, и поэтому в отсутствие передачи сигнала по первому входу коммутатора 4 данные со второго входа будут выданы на блок 5 индикации и блок 2 перебора позиций.

По окончании просмотра БД блока 3 памяти позиций блоком 6 выдачи хода флажковый сигнал управления от блока 6 выдает команду пуска на управляющий вход блока 8 ограничения ветвей расчета. Блок 8 по поступлении указанного управляющего сигнала осуществляет повторный просмотр БД блока 3, сравнивая при этом текущие значения весов позиций, записанные во 2-м поле БД, с максимальным значением веса, вычисленным в предыдущем цикле просмотра БД. При попадании текущего значения Ω в зону нечувствительности блока 8 этот блок передает на третий вход блока 3 информацию о продлении расчета варианта из данной позиции еще на один полуход, которая запоминается в 3-м поле текущей записи БД. В противном случае текущая запись исключается из БД, чем и достигается уменьшение ветвей вариантов в дереве расчета, что имеет следствием сокращение времени выбора оптимального варианта без снижения уровня игры. Ширина зоны нечувствительности является настроечным параметром АСУШ. Чем шире зона нечувствительности, тем большее количество ветвей содержит дерево перебора анализируемых шахматных позиций. С ростом дерева перебора повышается вероятность нахождения лучшего варианта, но это достигается ценой снижения быстроты анализа исходной позиции.

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

При подключении блока 10 памяти стандартных позиций в режиме библиотеки дебютов блок 9 сравнения позиций просматривает БД блока 10 и при обнаружении позиции, идентичной передаваемой блоком 2, выдает на вход датчика 11 выбора случайного варианта все известные из просматриваемой позиции продолжения. Датчик 11 случайным образом выбирает одно из этих продолжений и передает его на третий вход коммутатора 4. Этот вход имеет средний приоритет и поэтому передает информацию на выход коммутатора 4 в отсутствие передачи сигнала блоком 1, игнорируя сигнал по второму входу коммутатора 4. По окончании цикла расчетов блоком 8 управление с помощью флажкового сигнала (z) от блока 8 передается блоку 2 перебора позиций. В дальнейшем циклы работы повторяются до прихода сигнала об ответном ходе противника с блока 1 внешнего ввода или сигнала об окончании расчетов по времени или по числу полуходов.

При наличии блоков и узлов фиг.1 в составе вычислительной техники универсального назначения АСУШ по предлагаемой схеме может быть реализована в программном исполнении. Однако при частом использовании АСУШ целесообразно ее выполнение в виде специализированной конструкции, в том числе подключаемой к компьютеру.

Об эффективности предлагаемой АСУШ можно судить из описываемого далее примера ее работы в составе игрового комплекса "Unique Chess". Исходная позиция (фиг. 2) из партии по переписке В. Фадеев - А. Переверзев (Санкт-Петербург 1999/2000) возникла после следующих ходов: 1. е2-е4 d7-d6 2. d2-d4 Kg8-f6 3. Kb 1-с3 g7-g6 4. Kgl-f3 Cf8-g7 5. Cfl-e2 О-О 6. О-О Cc8-g4 7. h2-h3 Cg4: f3 8. Ce2:f3 Kb8-c6 9. Ccl-е3 e7-e5 10. d4-d5 Kc6-e7 11. Фdl-d3 a7-aб 12. Cf3-e2 Kf6-d7 13. f2-f3 f7-f5 14. Λal-dl Kd7-f6 15. a2-a4 f5-f4 16. Ce3-f2 g6-g5 17. b2-b4 h7-h5 18. Λfl-el Фd8-d7 19. a4-a5 Kpg8-f7 20. Ce2-fl g5-g4 21. Cf2-h4 Ke7-g6 22. Ch4:f6 Cg7:f6 23. Λе1-е2 Λf8-g8 24. Kpgl-hl Kg6-h4 25. Λe2-f2 g4:f3 26. g2:h3 Λg8-g5 27. Kc3-e2 Λa8-g8 28. c2-c4 Kpf7-g7 29. Λd1-cl Kpg7-h6 30. c4-c5 Фd7-g7 31. c5:d6 c7:d6 32. Фd3-a3 Фg7-g6 33. Kphl-h2 Λg5-gl 34. b4-b5 a6:b5 35. Λcl-bl b5-b4 36. Фa3-d3.

Полученная позиция теоретически выиграна за черных. Однако при ее расчете с использованием прототипа (RU 2145730) на глубину 3 или 4 полухода выигрывают белые. И только при глубине расчета не менее 5 полуходов прототипная АСУШ в течение 2-3 мин обнаруживает выигрывающее за черных продолжение. Заявляемая же АСУШ в позиции фиг.2 избрала наилучшим вариант с 36.... Cf6-d8 при глубине расчета в пять полуходов, что обеспечило победу черных (в партии далее были сделаны ходы 37. Λb1-al Cd8:a5 и белые сдались из-за значительных материальных потерь). В данной позиции процесс поиска новой АСУШ не превышает 0,5 мин, что в 4-5 раз быстрее, чем при использовании прототипа. Повышение быстродействия достигнуто за счет отсечения перебора неперспективных вариантов игры.

По результатам авторских испытаний предлагаемое техническое решение в 10-60 раз сокращает время выбора оптимального варианта в сложных позициях без снижения уровня игры.

Формула изобретения

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

РИСУНКИ

Рисунок 1, Рисунок 2