Quiescence search

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


Для сглаживания эффекта горизонта взятия считаем до конца. Для этого по достижении предельной глубины полного поиска вызываем
форсировку, в которой обсчитываем только взятия. Здесь я не использую детектор шахов, поэтому возникают ситуации, когда бьют
короля и мы должны их обрабатывать.
Тут две ключевые темы - завышение альфы статической оценкой и сортировка методом mvv/lva.
Опишу алгоритм за белых.

Так это сделано в Ифрите (Ifrit_b2_6):
Forced_variant_white
{
  Считаем статическую оценку позиции. В ней мы обсчитываем только материал.
  value_max = Eval_forced;

  Пытаемся получить отсечку по бете.
  if(value_max >= beta) return value_max;

  Генерируем и сортируем ходы.
  Generator_captures_white;
  Sorting_captures_moves;

  Если список взятий пустой, то возвращаемся со статической оценкой.
  if (0 == list_surplus_moves.end_list) return value_max;

  Статической оценкой пытаемся завысить альфу.
  if(value_max >= alpha){
    alpha = value_max;
  }

  Обсчитываем список взятий.
  for (int i=0; i < list_surplus_moves.end_list; i++){

    Делаем ход.
    Onward_moves_white;

    Обрабатываем случай взятого короля.
    if (( list_surplus_moves.move[i] & 63) != 6){

      Если король еще живой то, вызываем рекурсивно перебор за черных.
      value = Forced_variant_black(depth + 1);

      Откатываем ход.
      Backs_moves_white;

      Ищем максимум.
      if (value > value_max) value_max = value;

      Пытаемся улучшить альфу и при случае отсечь по бете.
      if (value > alpha){
        alpha = value;
        if(alpha >= beta) return alpha;
      }

    }else{
      Если же короля побили, то, значит, был шах или мат и дальше считать смысла нет.
      Отнимаем глубину, что бы выбирал кратчайший путь.
      value =  (1000000 – depth * 1000);

      Откатываем ход.
      Backs_moves_white;
      return value;
    }
  }
  return value_max;
}


За черных без комментариев.

Forced_variant_black
{
  value_min = Eval_forced(bitboard);

  if(value_min <= alpha) return value_min;

  Generator_captures_black;
  Sorting_captures_moves;

  if (0 == list_surplus_moves.end_list) return value_min;

  if(value_min <= beta) beta = value_min;

  for (int i=0; I < list_surplus_moves.end_list; i++){

    Onward_moves_black;

    if (( list_surplus_moves.move[i] & 63) != 6){

      value=Forced_variant_white(depth + 1);

      Backs_moves_black;

      if (value < value_min)value_min = value;

      if (value < beta){
        beta = value;
        if(alpha >= beta) return beta;
      }

    }else{

      value =  -(1000000 – depth * 1000);
      Backs_moves_black;
      return value;
    }
  }
  return value_min;
}

Посмотрим, насколько форсировка тормозит полный перебор. Кстати, это полный настоящий перебор без а-б :)

Без форсажа.
5/5    00:05    4.865.609          1                +1,19 e2e4 e7e5 Ng1f3 Bf8e7 Nf3xe5
6/6    02:05    119.060.324      1                -0,82 e2e4 b7b6 d2d4 Bc8b7 e4e5 Bb7xg2

С форсажем.
5/5    00:10    4.865.609           506.462    +0,26 e2e4 Ng8f6 e4e5 Nf6e4 d2d4
6/6    05:14    119.060.324       407.828    +0,12 e2e4 Ng8f6 Nb1c3 d7d5 e4xd5 Nf6xd5

























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