Движок для русских шашек

Демо:

Установка проекта:

1. Установите g++, git, make и sfml

2. Установка

   git clone https://github.com/iv4n-t3a/checkers-engine cd checkers-engine sudo make install

Деустановка:

sudo make uninstall

Как пользоватся:

Вывод справки

checkers --help

Как работает:

Хранение позиции в памяти:

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

= 0b100010010100010

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

В данном примере взятие в этом направлении может выполнить только одна шашка

Поиск лучшего хода:

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

Этот поиск можно оптимизировать альфа-бета отсечением. В его основе лежит идея, что оценивание ветви дерева поиска может быть досрочно прекращено (без вычисления всех значений оценивающей функции), если было найдено, что для этой ветви значение оценивающей функции в любом случае хуже, чем вычисленное для предыдущей ветви. Альфа-бета-отсечение является оптимизацией, так как не влияет на корректность работы алгоритма. (Объяснение из википедии)

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

Оценка позиции:

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

• Расположение шашек в зависимости от стадии игры
• Наличие проходных шашек, у которых никто не стоит на пути в дамки
• Мобильность (количество возможных ходов)

Более выгодные расположения шашек в дебюте

в мительшпиле(середине игры)

в окончании

проходная шашка