MiniMax (Полный перебор)

на главную страницу


Самое начало - это полный перебор. Из данной позиции возможно несколько легальных ходов, мы их делаем и получаем позиции следующего уровня и все повторяется. Следует обратить внимание, что мы сначала генерируем список ходов возможных из данной позиции, а уже потом делаем эти ходы, получая новые позиции. Делается это по нескольким причинам. Во-первых, довольно накладно хранить в памяти дерево позиций. Гораздо эффективнее хранить не позиции, а ходы, которые привели к данной позиции. И, во-вторых, после генерации ходов при использовании а-б отсечения их нужно будет сортировать, и многие ходы будут отброшены без генерации позиций, т.е. без делания этого хода. Но даже при максимально компактной записи ходов мы не можем держать в памяти все дерево игры, потому что оно растет по экспоненте. Приведем цифры, потому что в данном случае они красноречивее всяких слов:

Для начальной позиции
Глубина перебора   Количество узлов
3                                9 322
4                                206 603
5                                5 072 212
6                                124 132 536
7                                3 320 034 396
(8,9,10 вычислял сам)
8                                88 319 013 352
9                                2 527 849 247 519
10                              71 880 708 959 936

Мы знаем, что 1 Мб - это 1 048 576 байт. Допустим, у нас ход закодирован в целом числе int, а это 4 байт. Значит, в одном Мб можно сохранить 262144 ходов. Это значит, что для глубины 5 полуходов нам потребуется 19 Мб. А для 6 полуходов уже ~ 473Мб. И так далее по экспоненте.

Поэтому при переборе мы держим в памяти только одну ветку ту, которую в данный момент исследуем. Тогда даже при глубине 10 нам потребуется примерно 20*10 = 400 ходов. Такое дерево легко помещается даже в кэше процессора.

В результате алгоритм таков. Берем позицию и генерируем из нее список ходов, дальше берем ход из списка и делаем его, т.е. создаем позицию следующего уровня и т.д.
Позиции на предельной глубине оцениваем. И в каждом узле находим лучшую оценку. Понятно, что белые будут пытаться найти максимум, а черные минимум. Поэтому алгоритм и называется минимаксом. Это все очень просто, но как это описать?!
Пойду самым простым путем – приведу алгоритм полного перебора.

Поиск за белых{
Оценку за белых, т.е. локальный максимум устанавливаем в минимум.
Если достигли максимально заданной глубины, то вызываем статическую оценку позиции
Генерируем список легальных ходов
Просматриваем список {
Делаем ход за белых
Вызываем Поиск за черных, в результате которого получаем оценку хода
Берем назад ход за белых
Сравниваем оценку хода с нашим максимумом в узле, если больше, то делаем ее максимумом
}
Возвращаем максимум в узле
}

Поиск за черных {
Оценку за черных, т.е. локальный минимум устанавливаем в максимум.
Если достигли максимально заданной глубины, то вызываем статическую оценку позиции
Генерируем список легальных ходов
Просматриваем список {
Делаем ход за черных
Вызываем Поиск за белых, в результате которого получаем оценку хода
Берем назад ход за черных
Сравниваем оценку хода с нашим минимумом в узле, если меньше то делаем ее минимумом.
}
Возвращаем минимум в узле
}

Описание получилось какое то неконкретное, поэтому приведу код на си образном языке и в дальнейшем алгоритм словами описывать не буду (учите Си++!).

int AlphaBetaWhite(int depth) поиск за белых
{
  int tmp;
  int max = -INFINITY;// устанавливаем локальный максимум в минус бесконечность
  if(depth <= 0) return Evaluate();// на предельной глубине считаем оценку позиции
  GenerateWhite ();// генерируем список ходов за белых
  while(moveList) списки ходов локальные, т.е. действуют только в узле
  {
     MakeMoveWhite;//делаем ход
     tmp = AlphaBetaBlack(depth-1);
     UnMakeMoveWhite;// откатываем ход
     if(tmp > max) max = tmp; // белые ищут локальный максимум
  }
  return max;
}

int AlphaBetaBlack (int depth) поиск за черных
{
  int tmp;
  int min = INFINITY;
  if(depth <= 0) return Evaluate();
  GenerateBlack ();
  while(moveList)
  {
     MakeMoveBlack;
     tmp = AlphaBetaWhite (depth-1);
     UnMakeMoveBlack;
     if(tmp < min) min = tmp; // черные ищут локальный минимум
  }
  return min;
}


Очевидно, что полный перебор крайне неэффективен. И действительно для перебора за секунду на:
– глубину 4 нужна скорость 206 тысяч узлов секунду;
– глубину 5 нужна скорость 5 миллионов 72 тысячи узлов в секунду;
– глубину 6 нужна скорость 124 миллиона 132 тысячи узлов в секунду;
– глубину 7 нужна скорость 3 миллиарда (!) 320 миллионов 034 тысячи узлов в секунду.

Как видно глубины поиска просто смешные, а требуемое быстродействие совершенно неприличное. И тут не поможет никакая оптимизация.
На нынешних процессорах такая программа будет играть на глубине 4, а в лучшем случае 5 полуходов, т.е. смотреть на ~2 хода :)
Именно поэтому на полном переборе останавливаться никак нельзя и следует идти дальше. А дальше у нас alpha-beta оптимизация перебора.

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

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

В результате схема несколько усложняется.

int AlphaBetaWhite (int depth)// поиск за белых
{
  int tmp;
  int max = -INFINITY;// устанавливаем локальный максимум в минус бесконечность
  if(depth <= 0) return Evaluate ();// на предельной глубине считаем оценку позиции
  GenerateWhite ();// генерируем список избыточных ходов за белых
  while(moveList)// списки ходов локальные, т.е. действуют только в узле
  {
     MakeMoveWhite;// делаем ход
     if (King_white_check !=0 ){// проверяем под шахом ли король
       UnMakeMoveWhite;// откатываем ход, так как позиция некорректная
     }else{
       tmp = AlphaBetaBlack(depth-1);
       UnMakeMoveWhite;// откатываем ход
       if(tmp > max) max = tmp; // белые ищут локальный максимум
     }
  }
  return max;
}

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











Сайт создан в системе uCoz