Это старая бородатая задача, которую можно решить перебором на глубину 3..5 для одной стороны, т.е. ходы противника не учитываются. Но если отойти
от примитивизма, до задача становится интересной, потому как одна сторона должна играть в полную силу а ходы другой учитываться, но не во всех лучаях.
Правила игры.
Шашки
ставятся в углы, и целью является занять угол противника. Шашки могут
ходить на одно поля или прыгать через шашки, свои и противника.
Оценка позиции.
Оценкой может служить просто индекс 0..63 массива для верхних (черных) и
инвертированный индекс 63-n для белых. Целевые поля получают премию,
свои поля - небольшой штраф, чтобы программа их быстрее оставляла. Центр
может получить небольшую премию. Перед каждым ходом можно инициализировать генератор случайных чисел системным временем и давать
для каждой клетки небольшой случайный бонус.
srand(time(0));
score[j] = random()%2 - 1; // -1..1
0, 0, 0, 4, 5, 6, 7, 8,
1, 1, 1,12,13,14,15,16,
2, 2, 2,20,21,22,23,24,
25,26,27,30,31,30,31,32,
33,34,35,38,39,38,39,40,
41,42,43,44,45,56,57,58,
49,50,51,52,53,64,65,66,
57,58,59,60,61,72,73,74
Поиск.
Здесь я применил модифицированный вариант - первый лучший. Надо учесть что функция поиска принимает аргумент - лучший ход и начинает поиск с него и возвращает тоже лучший ход и его оценку. Без этого алгоритм первый -
лучший теряет смысл, так как первый ход должен быть осмысленным.
int search(int alpha, int beta, int depth, int color, Move* best){
Move m=0;
if(depth<=0)return Evaluate(color);
GenerateMoves();
PickBestMove(*best);
int cnt_moves=0;
for(mv in moves){
cnt_moves++;
MakeMove(mv);
if(depth<=2) tmp=-search(-beta,-alpha,depth-1,color^1,&m);
else{
for(int d=max(2,(int)sqrt(depth)); d <= depth-1; d++)
{
tmp=-search(-beta,-alpha,d,color^1,&m);
if(tmp<=alpha && cnt_moves>1)break;
}
}
UnMakeMove(mv);
if(tmp>alpha) { alpha=tmp; *best=mv;}
if(alpha>=beta) break;
}
return alpha;
}
/////
Заключение.
Этот алгоритм будет работать даже для несложных шахмат, только шахи в оконечном поиске надо расширять (глубину их поиска).
В зключении прилагаю исходники программы, написанно еще на turbo pascal 7.1. Можно запускать под dosemu.
https://disk.yandex.ru/d/QNDvuEpVQVNybg