|
||
Как записать, сохранить и вывести вариант, насчитанный во время перебора? Надо сразу сказать, что тут я все придумал сам и до сих пор не сравнивал с другими прогами. Так что опишу как есть на данный момент. Спускаясь в глубину, мы в каждом узле записываем ход в текущий вариант (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; } При всплытии остается только лучший вариант, а все остальное теряется. |