Вопрос про поиск

Тема в разделе "Машинное отделение", создана пользователем Binary, 28 авг 2006.

  1. Binary
    Оффлайн

    Binary Учаcтник

    Репутация:
    0
    У меня вопрос появился :
    Встречал различные улучшения Альфа-Беты , но без описания ,
    можете мне объяснить смысл алгоритмов MTD(f) , Aspiration search , OOO* [ или что-то типо этого ] ?

     
    Binary, 28 авг 2006
    #1
  2. WinPooh
    Онлайн

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

    Репутация:
    95
    Смысл в большинстве случаев заключается в оптимизации размеров окна. Чем уже окно альфа-бета, тем быстрее происходит поиск. Но если результирующая оценка вылезает за рамки первоначальной альфа-беты, то приходится делать повторный поиск с другими границами окна. То есть это в определённом смысле обмен скорости на точность, лотерея. Упомянутые методы отличаются друг от друга тем, как и в каком месте дерева они манипулируют окном. Например, Aspiration Search - это изменение окна в корне дерева по результатам предыдущей итерации поиска...

    В качестве источников могу порекомендовать, например, статью на Википедии http://en.wikipedia.org/wiki/MTD-f
    и подборку статей про поиск на http://digilander.libero.it/mizarchessengine/papers.htm
     
    WinPooh, 28 авг 2006
    #2
  3. Binary
    Оффлайн

    Binary Учаcтник

    Репутация:
    0
    :)
    До этого ещё далеко ...
    просто стало интересно насколько они улучшают альфа-бету
     
    Binary, 28 авг 2006
    #3
  4. bankuss
    Оффлайн

    bankuss Александр баннер

    Репутация:
    6
    WinPooh хороший совет :) +1
     
    bankuss, 28 авг 2006
    #4
  5. WinPooh
    Онлайн

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

    Репутация:
    95
    Не в разы. В лучшем случае, на десятки процентов.
    А теперь - внимание, волшебная истина. Даже если вы увеличите скорость счёта вдвое, это даст прирост в глубине на... меньше чем полуход!

    Вчитывайтесь в эту истину, пока не придет просветление :)
     
    WinPooh, 28 авг 2006
    #5
  6. Binary
    Оффлайн

    Binary Учаcтник

    Репутация:
    0
    я знаю ...
    вчера даже поставил эксперимент :
    в сорцах TSCP был ещё скомпиленный MS VC 6 экзешник , VC .Net2 увеличил скорость его алгоритма на 20 %
    так вот матч старой и новой компиляции из 16 партий закончился с перевесом новой в 1 очко
    [ + надо учесть погрешность таких турниров ] ... может пунктов 10 и прибавил :)
     
    Binary, 28 авг 2006
    #6
  7. Binary
    Оффлайн

    Binary Учаcтник

    Репутация:
    0
    кстати вы сами в своих прогах какой алгоритм используете ?
     
    Binary, 28 авг 2006
    #7
  8. WinPooh
    Онлайн

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

    Репутация:
    95
    Большинство сильных программ использует тот или иной вариант PVS. Некоторые - альфа-бету в чистом виде.
    На самом деле, гораздо большее значение имеют, например, алгоритмы углубления/подрезания ветвей поиска...
     
    WinPooh, 28 авг 2006
    #8
  9. NS
    Оффлайн

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

    Репутация:
    3
    Основное продление - на шахах, никакие обрезания/подрезания первой версии не нужны. Их можно добавить потом.
    Проще всего написать Negascout с пустым ходов и продлением на шахе. В ФВ взятия (можно добавить шах на входе в ФВ) Взятия должны быть отсортированы в любом случае - иначе очень сильно разрастается дерево.
     
    NS, 28 авг 2006
    #9
  10. bankuss
    Оффлайн

    bankuss Александр баннер

    Репутация:
    6
    NS верно.. для начала хватит, а вот потом начинается самое интересное :)
     
    bankuss, 28 авг 2006
    #10
  11. Binary
    Оффлайн

    Binary Учаcтник

    Репутация:
    0
    C пустым ходм у меня тоже небольшая проблема в понимании :)
    конкретно : когда его нужно использовать и сколько раз за один поиск
    пример
    ход белых ... ищем на 10 полуходов ... рассматриваем все ходы белых потом снова все ходы белых
    ( пустой ход ) или делаем пустой ход только в очевидных случаях ( ходах) например когда
    соперник предоставил на возможность что-нибудь съесть ... и вообще насколько глубоко надо рассматривать
    "дурацкие" ходы (например подстановка ферзя под бой пешки) ?
     
    Binary, 28 авг 2006
    #11
  12. WildCat
    Оффлайн

    WildCat Коршунов Игорь Команда форума

    Репутация:
    0
    Легче всего начать с PVS и не заморачиваться с окнами.
    Пустой ход можно пытаться сделать всегда. Намного хуже не будет. Зато просто.
     
    WildCat, 29 авг 2006
    #12