VPF::алгоритм minimax(depth ) - Форум программистов

Xdelphic

Дата 20.2.2016, 01:01 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 20.2.2016

Репутация: нет
Всего: нет

Здравствуйте. Замучился с функцией minimax-a для русских шашек. Точнее она работает и вроде бы как надо, находит самый сильный ход, но лишь тогда, когда общее количество шашек на поле приблизительно больше 8 (т.е, например, осталось 4 белых и столько же черных, или же все шашки в начале просчета на местах), тогда никаких нареканий, находит самые неожиданные и сильные многоходовки для компа.

Если же, к примеру, как вариант эндшпиля, вручную выставить на поле всего 2 шашки (черную и белую) в позицию -1 (минус один) ход черной (цвет компьютера) до позиции - "друг на против друга" (т.е. когда уже будут должны ходить белые, а некуда, что естесно означает поражение белым), то в некоторых полях доски черная шашка делает наиглупейший ход в сторону, что можно расценивать, как сведение к ничьей, вместо явного выигрыша. Другими словами, оценочная функция дает сбой. Но ГДЕ и КАК найти так и не смог.
Сама оценочная функция проста и тривиальна:

Код


function TForm1.all_count:integer;
var x,y:integer; 
begin
result:=0; 
// последовательный поиск в 2-мерном массиве [1..8,1..8] field 
for x:=1 to 8 do 
for y:=1 to 8 do
//если клетка не пуста
 if not field[x,y].emp then
//если шашка черная +1, иначе, если белая -1
 if field[x,y].bl then result:= result-1 else
                               result:= result+1
end;

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

А вот сама главная функция minimax-а (закомментировал всё что можно и нельзя, для большего понимания):

Код


function TForm1.smart(black:boolean; depth:longint): integer;
var x,y,i:integer; score_best:integer;

    fra:   xfr; // промежуточный массив для поиска ударных ходов
    rsa:   xrs; // итоговый массив для всех ходов и ударов

begin
 {достигли последнего возможного хода (глубина задается пользователем,
  как параметр данной функции)}
 if depth=0 then
 begin
  {получили в результат вышеприведенную оценку материальной
   ситуации all_count и прервали дальнейшее
   выполнение текущей копии smart(depth)}
  result:=  -all_count;
  exit
 end;

 {задали начальное значение лучшего счета, как максимально низкое}
 score_best:= -maxint;

 {следующие далее 2 цикла для заполнения конечного
  массива rsa были многократно мной проверены и
  работают безукоризненно, т.е, правильно находят
  все возможные ходы \ удары для активной стороны & соперника}

 {проверка на наличие ударного ход(а-ов, так как может быть больше 1-ого),
  и добавление их в итоговый динам.массив rsa}
 for x:=1 to 8 do for y:=1 to 8 do
 if (not field[x,y].emp)and(field[x,y].bl=black) then
 begin
   fire(x, y, black, fra);
   if length(fra)=0 then continue;
   add_var(fra,rsa);
   nextsub_rec(black,fra,rsa);
   clear_fra(fra);
 end;

 {нет ударных, поиск и добавление всех разрешенных ходов}
 if length(rsa)=0 then
 for x:=1 to 8 do for y:=1 to 8 do
 if (not field[x,y].emp)and(field[x,y].bl=black) then
 begin
  moves(x, y, black, rsa);
 end;

 {здесь само собой, следует перебор всех
  возможных ходов, начиная с текущей игровой ситуации}
 {и здесь же собственно, как я уверен - начинаются те самые проблемы}
//_____________________________
 for i:=0 to high(rsa) do
 begin
 {начало перебора}

   // делаем ход (фукции do_move и следующая за ней далее - back_move
   // так же многократно проверны и работают правильно)
   do_move(i,black,rsa);

   // "уходим в себя"
   score:= -smart(not black, depth-1);

   // возвращаем сделанный выше ход
   back_move(i,black,rsa);

   //   если результат "ухода в себя" выше
   //   тек. лучшего счета best_score, делаем best_score равным ему
   if score > score_best then
   begin
    score_best:= score;
    {если глубина depth равна начальной deep, то определяем ход, как ЛУЧШИЙ}
    if depth=deep then best_index:= i;
   end;

{конец перебора}
end;
//_____________________________

 {возвращаем лучший счет}
 result:= score_best;
//-----------------------------
 {далее комп делает тот самый лучший ход, ссылка на который попала в best_index}
 {данный кусок кода можно было вынести вовне, он выполнится только 1 раз
  когда глубина depth вернется на стартовый уровень deep}
 if depth=deep then
 begin
    // делает ход для текущего цвета
    do_move(best_index,black,rsa);
    // на след. обработчик кнопки можно не обращать внимание, она отобразит конечную
    // расстановку после вышеслед. хода
    bitbtn1.click;
 end;
//-----------------------------
end;

(*
запускаю, к примеру, так:
deep:= maxlongint; best_index:= 0; smart(true,deep);
*)

Методом проб и ошибок, кажется понял, что, по крайней мере - косвенная вина проблемы в самом начальном условии smart(depth), где if depth = 0 then ...
Дело в том, что оно просто не выполняется для небольшого количества шашек на доске, как я писал в начале.
Собственно, понял я это уже давно, но меня это мало чем осенило... ))) Пробовал делать оценку allcount() чуть ли не на каждом витке рекурсии, результата никакого. Понимаю, что глупо, но отследить до конца всю работу данной функции, со всеми её рекурсивными вызовами, в голове..., не получается. Просьба ткнуть лбом, - где искать ошибку либо упущение..
Как я уже писал, от дебютного состояния игры и ~ до мительшпиля включительно, программа работает отлично, разумеется после оптимизации alpha-beta для функции smart (убрал её для простоты восприятия кода, так как на полном переборе выше, результат всё такой же прискорбный)

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Delphi: Общие вопросы \| Следующая тема »