Внимание! примеры даны для шашек 4х4, но суть не меняется

Внимание! примеры даны для шашек 4х4, но суть не меняется

1. Создаем Базу возможных позиций шашек - позиций, которые могут получиться в ходе игры

1.1. Кодируем позиции (пользуемся готовым кодом!) -

В папке Редактор Позиций находим код кодирования позиций, используем его

1.2. Создаем Базу возможных позиций шашек

Создание базы запускается через консольное приложение

- Изначальная задумка - позиции располагаются  в виде txt файлов с названиями: 12х12, 12х11, 12х10, ..., 12x0, 11х12, 11x11, 11x10, ..., ..., 1х0 (соотношение сил [белых]х[черных]). При наличии у разработчика другого варианта Базы, этот (другой) вариант обговаривается

1) с представлением преимуществ этого варианта

2) с внесением изменений в Редактор Позиций (возможность чтения Редактором Позиций Базы и проверки определенной позиции на наличие в Базе)

- В Базе допускается, но крайне нежелательно наличие лишних позиций (которые не могут быть получены в ходе игры) и не допускается отсутствие возможных позиций

- Еще одно важное требование - скорость создания Базы

2. Создать Базу конечных позиций (расстановок фигур, где фигуры одной из сторон полностью съедены или заперты другой), либо написать код, который позволяет определить, является ли позиция конечной или нет

3. Написать код, генерирующий из данной позиции Материнские (на ход назад) и Дочерние (на ход вперед) позиции

4. Написать программу, которая дает оценку позициям.

Если при конечной позиции должна ходить черная - оценку даем по количеству оставшихся белых фигур;

... белая - по количеству оставшихся черных.

Позиции оцениваются относительно ходящей стороны, что учитывается знаком "+" или "-" (+ можно не писать). Плюс означает, что игрок, который сейчас ходит, имеет преимущество и при безошибочной игре на доске останется как минимум столько его шашек, сколько указано в оценке (ровно столько, сколько указано в оценке, шашек останется, если соперник начиная с текущей позиции также не будет ошибаться). Таким образом, у всех конечных позиций в оценке содержится знак «минус», это означает, сторона, которая должна была сейчас ходить, проиграла с разницей фигур в такое-то количество. Здесь рассматривался вариант, когда все шашки противника съедены. В случае же, когда в конечной позиции есть несъеденные фигуры, но все они заперты, оценка ставится по количеству оставшихся фигур выигравшей стороны

При оценке позиции у каждой предшествующей материнской позиции знаки «+» и «-« чередуются. По модулю оценка не меняется.

Алгоритм:

(1) Находим конечную позицию, ставим ей оценку.

(2) У только что оцененной позиции ищем неоцененные материнские, из которых оцененная получилась в результате вынужденного хода, присваиваем данным материнским позициям оценку (по модулю те же, что и у дочерней, но с учетом знака). Повторяем до тех пор, пока это возможно.

(3) Повторяем 1 и 2, пока не переберем все конечные позиции.

(4) Выбираем какую-нибудь оцененную позицию с двумя и более материнскими позициями, из которых хотя бы одна не оценена. Находим у одной из таких материнских позиций дочерние. Если все дочерние позиции имеют оценку, присваиваем наибольшую из них материнской.

(5) Выполняем пункт 2.

(6) Находим для выбранной в пункте 4 оцененной позиции другую материнскую позицию, остальное что и в пункте 4

(7) Выполняем пункт 2

(8) Повторяем 6 и 7, пока не переберем все материнские позиции для выбранной в пункте 4.

(9) Выполняем пункты 4-8 с другими оцененными позициями, доходим до конца базы

(10) Повторяем пункты 4-9, пока от этого есть результат

(11) Выбираем какую-нибудь оцененную позицию с двумя и более материнскими позициями, из которых хотя бы одна не оценена. Находим у одной из таких неоцененных материнских позиций дочерние. Присваиваем материнской позиции оценку, максимальную среди ее дочерних позиций

(12) Повторяем пункты 5-11, пока есть результат.

Оценка позиций Базы запускается из консольного приложения

- Скорость оценки позиций – важный показатель. Чем быстрее – тем лучше.

Неоцененные позиции.

После этих операций формально мы можем найти в Базе немало "неоцененных" позиций. На самом деле это позиции с "нулевой" оценкой - позиции, которые при безошибочной игре обоих игроков дают ничью.

Таким образом, все позиции Базы оценены.

5 Оптимизация базы

этот этап следует за оценкой базы, последний.

Цель - удалить позиции, которых не будет при игре с программой

это позиции, которых не будет НИ при игре программы за черные, НИ за белые.