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

Discussion in 'Машинное отделение' started by варяг, 6 Jan 2007.

  1. TopicStarter Overlay

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

    • Участник
    Member Since:
    23.10.2006
    Message Count:
    98
    Likes Received:
    0
    Репутация:
    0
    Location:
    Гонду-Раша
    Оффлайн
    Винни, подскажи как лучше multi-pv сделать? Т.е. как второй и последующие pv вытаскивать?
    варяг, 6 Jan 2007
    #1

  2. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.494
    Likes Received:
    3.128
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    В функции, которая делает перебор в корне, я просто запоминаю все дочерние варианты с их оценками. Когда приходит очередь их печатать, вытаскиваю по одному, в порядке убывания оценки. Так как количество вариантов, которое попросят выводить, и их очерёдность в поиске неизвестны, приходится запоминать все. Можно ли сделать проще - не уверен.

    WinPooh, 6 Jan 2007
    #2

  3. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Точные оценки всех ходов слишком накладны...

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

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

  4. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.494
    Likes Received:
    3.128
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    Для этого надо иметь идеальную сортировку в корне, не так ли?
    WinPooh, 6 Jan 2007
    #4

  5. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Не надо - я же описал алгоритм MultiPV Альфа-Беты.
    Даже стандартный PVS, либо стандартная Альфа-Бета может дать больше одной точной оценки в ходе (если поменялся лучший ход) - но никто ведь не переживает по этому поводу :)

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


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

  6. WinPooh В.М.

    • Команда форума
    Member Since:
    13.02.2006
    Message Count:
    9.494
    Likes Received:
    3.128
    Репутация:
    95
    Location:
    Москва
    Оффлайн
    Псевдокод привести можешь?
    WinPooh, 6 Jan 2007
    #6

  7. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    Да, сейчас набросаю.
    NS, 6 Jan 2007
    #7

  8. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    • Старожил
    Member Since:
    02.05.2006
    Message Count:
    6.811
    Likes Received:
    96
    Репутация:
    3
    Location:
    Санкт-Петербург
    Оффлайн
    МультиПВ=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 Jan 2007
    #8

Share This Page