Save variant

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


Как записать, сохранить и вывести вариант, насчитанный во время перебора? Надо сразу сказать, что тут я все придумал сам и до
сих пор не сравнивал с другими прогами. Так что опишу как есть на данный момент.

Спускаясь в глубину, мы в каждом узле записываем ход в текущий вариант (pv_current)
Структура для текущего варианта выглядит так:
// линия варианта (при форсировке взятий нужно 32 полухода + 40 для основного = 72)
struct T_PV {
  // описание хода смотреть в струкутре T_list_surplus_moves
  int move[100];

  // оценка варианта
  int score_move;

  // длина варианта
  int depth_max;
};

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

void Update_PV_current(int i,int depth,T_PV * pv_current,const T_list_surplus_moves * list_surplus_moves){
  // из списка возможных ходов копируем текущий ход в текущий вариант на текущей глубине.
  // мы видим, что текущий вариант прописывается до рекурсивного вызова функции Alpha-beta, т.е.
  // мы разматываем нить погружаясь в глубину
  // запись в структуре PV_current верна сверху и до текущей глубины
  // то, что расположенно ниже данного уровня не правильно, так как относится к предыдущему узлу.
  pv_current->move[depth] = list_surplus_moves->move[i];
}

И так к тому времени как мы опустились на самое дно, у нас есть линия варианта записанная в pv_current.
На дне мы оцениваем позицию и переписываем текущий вариант в лучший вариант.

void Update_PV_best_max_depth(int score,int depth,T_PV * pv_best,T_PV * pv_current){
  // мы достигли предельной глубины и статически оценили получившуюся позицию
  // погружаясь на глубину мы на каждом полуходе заносили ходы варианта в структуру PV_current
  // теперь мы перепишем его в структуру PV_best и прицепим оценку позиции
  // у нас получился вариант приводящий к данной позиции и плюс оценка этой позиции
  // ну и еще конечно длина варианта
  // внимание тут цикл идет от 0 до Depth-1
  // именно так ведь у нас начальная глубина 0
  for (int n = 0; n < depth; n++){
     pv_best->move[n ]= pv_current->move[n] ;
  }// for (int n = 0; n < Depth; n++){
  pv_best->score_move = score;
  // запоминаем глубину варианта
  pv_best->depth_max =depth;
}

В результате в лучшем варианте у нас оказывается записанной оценка позиции и линия, которая привела к этой позиции. С этими
данными мы начинаем подъем на поверхность.

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

void Update_PV_best_point(T_PV * PV_best_point,T_PV * PV_best){
  // лучший вариант, который функция перебора выдает наверх содержится в структуре PV_best
  // мы не только присваиваем оценку но и вариант соответствующий ей
  // присвоение идет структуре уникальной для каждого узла PV_best_point
  // здесь мы перезаписываем лучший вариант соответствующий лучшей оценке
  for (int n=0;n<PV_best->depth_max;n++){
    PV_best_point->move[n]=PV_best->move[n];
  }//for (int n=0;n<(Depth_Max);n++){
  PV_best_point->score_move =PV_best->score_move;
  //
  PV_best_point->depth_max =PV_best->depth_max;
}

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

Когда мы покидаем этот узел, всплывая наверх, мы лучший вариант из узла записываем в глобальный лучший вариант.

void Update_PV_best_point(T_PV * PV_best_point,T_PV * PV_best){
  // лучший вариант, который функция перебора выдает наверх, содержится в структуре PV_best
  // мы не только присваиваем оценку но и вариант соответствующий ей
  // присвоение идет структуре уникальной для каждого узла PV_best_point
  // здесь мы перезаписываем лучший вариант соответствующий лучшей оценке
  for (int n=0;n<PV_best->depth_max;n++){
    PV_best_point->move[n]=PV_best->move[n];
  }//for (int n=0;n<(Depth_Max);n++){
  PV_best_point->score_move =PV_best->score_move;
  //
  PV_best_point->depth_max =PV_best->depth_max;
}

При всплытии остается только лучший вариант, а все остальное теряется.

























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