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

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

  1. TopicStarter Overlay

    Binary Учаcтник

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

    Binary, 28 авг 2006
    #1

  2. WinPooh В.М.

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

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

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    :)
    До этого ещё далеко ...
    просто стало интересно насколько они улучшают альфа-бету
    Binary, 28 авг 2006
    #3

  4. bankuss Александр

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    24.05.2006
    Сообщения:
    1.084
    Симпатии:
    38
    Репутация:
    6
    Оффлайн
    WinPooh хороший совет :) +1
    bankuss, 28 авг 2006
    #4

  5. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.492
    Симпатии:
    3.122
    Репутация:
    95
    Адрес:
    Москва
    Оффлайн
    Не в разы. В лучшем случае, на десятки процентов.
    А теперь - внимание, волшебная истина. Даже если вы увеличите скорость счёта вдвое, это даст прирост в глубине на... меньше чем полуход!

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

    Binary Учаcтник

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

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    кстати вы сами в своих прогах какой алгоритм используете ?
    Binary, 28 авг 2006
    #7

  8. WinPooh В.М.

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

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

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

  10. bankuss Александр

    • Заслуженный
    • Участник
    • Старожил
    Рег.:
    24.05.2006
    Сообщения:
    1.084
    Симпатии:
    38
    Репутация:
    6
    Оффлайн
    NS верно.. для начала хватит, а вот потом начинается самое интересное :)
    bankuss, 28 авг 2006
    #10
  11. TopicStarter Overlay

    Binary Учаcтник

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

  12. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    4
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Легче всего начать с PVS и не заморачиваться с окнами.
    Пустой ход можно пытаться сделать всегда. Намного хуже не будет. Зато просто.
    WildCat, 29 авг 2006
    #12

Поделиться этой страницей