Программирование игры в уголки.

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

Правила игры.

Шашки ставятся в углы, и целью является занять угол противника. Шашки могут ходить на одно поля или прыгать через шашки, свои и противника.

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

Оценкой может служить просто индекс 0..63 массива для верхних (черных) и инвертированный индекс 63-n для белых. Целевые поля получают премию, свои поля - небольшой штраф, чтобы программа их быстрее оставляла. Центр может получить небольшую премию.
Перед каждым ходом можно инициализировать генератор случайных чисел системным временем и давать для каждой клетки небольшой случайный бонус.

 

///// игра  уголки - основные структры данных и алгоритмы///
#define WHITE 0
#define BLACK 1
#define PAWN 1
#define NOPIECE 0

int pos[64];//фигуры
int color[64];//их цвет
int score[64]={
 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,62,63,64, 
49,50,51,52,53,65,66,67,  
57,58,59,60,61,68,69,70};

int random_score[64];

void InitScore(){
  srand(time(0));
  for(int sq=0;sq<64;sq++)
   random_score[j] = random()%2;
}

int Evaluate(int color, //относительно кого оценка
             int player_color,//цвет игрока
             int ply //глубина поиска
             ){

  int s[2]={0,0}; 

  for(int sq=0;sq<64;sq++)
   if(pos[sq] != NOPIECE)
   {
     if(color[sq]==BLACK)
       s[BLACK] += score[sq] + random_score[sq];
     else  
       s[WHITE] += score[63-sq] + random_score[63-sq];
   }

  if(s[color]>60*9) return INFINITY-ply;//конец игре
  if(c[color^1]>60*9) return -INFINITY+ply;

  //одна из сторон получает большую оценку, чтобы
  //не 'зажимались' фигуры  
  if(color==player_color)
    return s[color]/3 - s[color^1];
  else
    return s[color] - s[color^1]/3;
} 
 

Поиск.

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


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