Метод поиска решения на графе пространства состояний, страница 2

Финальная расстановка – победа одного из игроков (шашки занимают угол диаметрально противоположный начальному). Расстановка проигравших шашек в конечном состоянии не отображается, т.к. не имеет принципиального значения.

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

Алгоритм программы.

После запуска программы появляется главное окно программы с заставкой, представленное на рисунке 1 (см. приложение). Для начала игры в меню «Файл» выбирается пункт «Новая игра», после чего начинается основной цикл программы. В начале работы программы вызываются предикат lets_Go(window), который выполняет прорисовку игрового поля, инициализацию базы данных и прорисовку начального положения фишек. Управление программой производится при помощи манипулятора типа «Мышь». При нажатии на правую кнопку мыши на фишке своего цвета производится пометка выбранной фишки. Нажатие на правую кнопку мыши обрабатывается предикатом right_Button_Click(window, pnt), который включает флаг выбранной фишки (предикат fishka_Selected), заносит координаты выбранной фишки в базу данных (предикат my_Move(ilist)). В случае, если фишка уже была выбрана до нажатия на правую кнопку мыши, то выбранная фишка отпускается, т. е. сбрасывается флаг fishka_Selected и удаляется из базы данных предикат my_Move.

Ход выбранной фишкой производится при нажатии на левую кнопку мыши на клетке, в которую необходимо походить. При нажатии на левую кнопку мыши, вызывается предикат left_Button_Click(window, pnt), который вызывает предикаты find_Step_Player(integer, integer) и find_Jump_Player(integer, integer) для проверки правильности хода. После успешной проверки выбранная фишка перемещается на указанную клетку. После перемещения фишки, изменяются её координаты в базе данных, и затем выполняется ход противника (компьютера).

Для выполнения хода компьютера вызывается предикат move_Computer, который вызывает предикат find_Best_Move(ilist), для поиска наилучшего хода, после возврата из предиката производится перерисовка поля и фишек. Предикат find_Best_Move(ilist) вызывает предикаты find_Step и find_Jump для генерации всевозможных шагов и прыжков через фишки, а так же вызывается предикат fin_States, для проверки на конечные состояния. Предикат find_Step берет из базы данных координаты черной фишки и вырабатывает всевозможные направления хода, при помощи предиката move. Предикат find_Jump берет из базы данных координаты черной фишки и вызывает предикат find_Jump_Find(ilist), который используя рекурсивный вызов, вырабатывает всевозможные прыжки, для этого вызывается предикат move для генерации направления прыжка; промежуточные состояния прыжка записываются в параметре этого предиката. При этом предикат проверяет клетки в направлении прыжков на занятость и не занятость другими фишками. После выхода из предиката, последовательность ходов записывается в базе данных. Затем для найденного хода считается его оценка, при помощи предиката calculate_Fishka_Number и, если ход, запомненный в базе данных хуже текущего, то текущий ход записывается в базу данных. Таким образом, предикат find_Best_Move(ilist) просматривает все возможные ходы. После выхода из этого предиката производится перерисовка поля и переход хода. Цикл повторяется сначала. Игра заканчивается, когда фишки одного из игроков будут располагаться на противоположной стороне поля. Эта поверка осуществляется в предикатах move_Player и move_Computer для игрока и компьютера соответственно.

Основные предикаты, используемые в программе.

lets_Go(window) – предикат осуществляет инициализацию базы данных и начальную прорисовку поля;

right_Button_Click(window, pnt) – предикат осуществляет обработку события нажатия на правую кнопку мыши;

left_Button_Click(window, pnt) – предикат осуществляет обработку события нажатия на левую кнопку мыши;

fishka_Selected (integer) – флаг, принимает значение 1, если выбрана фишка и 0 – в противном случае;

my_Move(ilist) – факт в базе данных, хранящий координаты выбранной фишки;

find_Step_Player(integer, integer) и find_Jump_Player(integer, integer) – предикаты, проверяющие правильность хода игрока;

find_Best_Move(ilist) – предикат осуществляет поиск наилучшего хода компьютера;