Обсуждаем реализацию режима Multi-PV

Тема в разделе "Машинное отделение", создана пользователем варяг, 6 янв 2007.

  1. варяг
    Оффлайн

    варяг Учаcтник

    Репутация:
    0
    Винни, подскажи как лучше multi-pv сделать? Т.е. как второй и последующие pv вытаскивать?
     
    варяг, 6 янв 2007
    #1
  2. WinPooh
    Оффлайн

    WinPooh В.М. Команда форума

    Репутация:
    95
    В функции, которая делает перебор в корне, я просто запоминаю все дочерние варианты с их оценками. Когда приходит очередь их печатать, вытаскиваю по одному, в порядке убывания оценки. Так как количество вариантов, которое попросят выводить, и их очерёдность в поиске неизвестны, приходится запоминать все. Можно ли сделать проще - не уверен.

     
    WinPooh, 6 янв 2007
    #2
  3. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    Точные оценки всех ходов слишком накладны...

    Проще получать столько точных оценок, сколько задано в параметре MultiPV, а когда нужны точные оценки всех ходов - тогда просто ставить максимальное значение параметра.

    Тем более стандартная MultiPV АльфаБета очень проста, и к ней легко прикручивается либо PVS в корне, либо расширяемое окно. Но по моим тестам ни PVS, ни расширяемое окно Греке ничего не дает.
    PVS только портит, а окна в пол-пешки - пешку просто ничего не дают.
     
    NS, 6 янв 2007
    #3
  4. WinPooh
    Оффлайн

    WinPooh В.М. Команда форума

    Репутация:
    95
    Для этого надо иметь идеальную сортировку в корне, не так ли?
     
    WinPooh, 6 янв 2007
    #4
  5. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    Не надо - я же описал алгоритм MultiPV Альфа-Беты.
    Даже стандартный PVS, либо стандартная Альфа-Бета может дать больше одной точной оценки в ходе (если поменялся лучший ход) - но никто ведь не переживает по этому поводу :)

    Так-же и при МультиPV Альфа-Бете. Точных оценок будет больше параметра MultiPV только в том случае если поменялся набор из MultiPV лучших ходов.


    А в корне - простое вытягивание ходов наверх (на каждой глубине вытягивание наверх и сортировка ходов с точной оценкой) Дает отличную упорядоченность, тем более в режиме MultiPV.
     
    NS, 6 янв 2007
    #5
  6. WinPooh
    Оффлайн

    WinPooh В.М. Команда форума

    Репутация:
    95
    Псевдокод привести можешь?
     
    WinPooh, 6 янв 2007
    #6
  7. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    Да, сейчас набросаю.
     
    NS, 6 янв 2007
    #7
  8. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    МультиПВ=1;// Тут значение параметра.
    //Moves - массив записей. .Move - Ход .Score - оценка.
    //число легальных ходов kolMoves.
    //Перед перебором генерируем ходы, и сортируем стандартным способом.

    Для Глубина=1 по 40 цикл

    Для сч=1 по KolMoves Цикл
    Moves[Сч].Score:=-inf;
    КонецЦикла;

    kolScore:=0; //Количество полученных точных оценок.

    Для сч=0 по KolMoves цикл

    Если KolScore<МультиПВ Тогда
    Альфа:=-inf Иначе Альфа:=Moves[МультиПВ].Score;
    КонецЕсли;

    MakeMove(Moves[сч].Move);
    Score:=-Search(-inf,-Альфа,Глубина-1);
    UnMakeMove(Moves[сч].Move);

    Если Score>Альфа Тогда
    Moves[сч].Оценка:=Score;
    kolScore:=kolScore+1;

    // И вытягиваем ход на нужное место в списке
    Место=1;
    Пока (Moves[Место].Score>=Score) и (Место<сч) Цикл
    Место:=Место+1;
    КонецЦикла;

    запомним_ход_с_оценкой:=Moves[сч];

    For i:=сч downto Место+1 do
    Moves:=Moves[i-1]
    КонецЦикла;

    Moves[Место]:=запомним_ход_с_оценкой;
    КонецЕсли;
    КонецЦикла;
    КонецЦикла;
     
    NS, 6 янв 2007
    #8