параметры NULL MOVE

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

  1. Binary
    Оффлайн

    Binary Учаcтник

    Репутация:
    0
    скажите , какие параметры чаще всего используются при вызове пустого хода ?
    например , я сделал 3 варианта :
    1. if( depth > 2 && !follow_pv && !IS_IN_CHECK) {
    ...
    if( -search(-beta, -alpha, depth/2 ) >= beta )
    return beta;
    }

    2. if( depth > 2 && !follow_pv && !IS_IN_CHECK) {
    ...
    if( -search(-beta, -alpha, depth/3 ) >= beta )
    return beta;
    }

    3. if( depth > 2 && !follow_pv && !IS_IN_CHECK) {
    ...
    if( -search(-beta, -alpha, depth - 2 ) >= beta )
    return beta;
    }
    самый быстрый - (2), но частенько зевает комбинации
    (3) - практически не меняет силу игры (может быть даже замедляет)
     
  2. NS
    Оффлайн

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

    Репутация:
    3
    Последний (2) Это R=1.
    Обычно делают либо Depth-4 (R=3) либо Depth-3 (R=2)
    То что ты делишь - такая схема обычно используется в IID, но не в Null Move.

    Для средней программы обычно оптимально R=2.

    Кроме проблемы горизонта (зевает комбинации) у Null Move есть еще пара побочных эффектов.
    Цуцванг - программа не видит цуцванга.
    Нестабильность перебора.
     
  3. Binary
    Оффлайн

    Binary Учаcтник

    Репутация:
    0
    NS - спасибо
     
  4. NS
    Оффлайн

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

    Репутация:
    3
    Если при Depth=0 начинается ФВ, тогда обычно
    if( depth >= 2 && !follow_pv && !IS_IN_CHECK) {
    // не забываешь передать очередь хода?
    if( -search(-beta, -beta+1, max(depth - 2 - 1, 0)) >= beta )
    return beta;
    // нужно вернуть очередь хода, и
    // наверно не просто возврат, а что-то еще в хеш нужно записать :)
     
  5. Binary
    Оффлайн

    Binary Учаcтник

    Репутация:
    0
    очередь хода передать не забываю :)

    эту процедуру я так понял надо впихнуть прямо перед вызовом quiesce (ну или ФВ другими словами)?
     
  6. NS
    Оффлайн

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

    Репутация:
    3
    Не понял - Как это пустой ход запихнуть перед вызовом ФВ???
     
  7. Binary
    Оффлайн

    Binary Учаcтник

    Репутация:
    0
    :)
    вот как у меня сделано :
    сначала search(...) -> затем на 0-ой глубине работает quiesce(...) , которая рассматривает только взятия до
    max_ply (у меня 31)
    null_move я вызываю перед рекурсивным вызовом search(...) , почему тоже самое нельзя проделать с Quiesce ?
     
  8. NS
    Оффлайн

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

    Репутация:
    3
    У тебя может быть вызван null move при Depth=0? Нет? Значит проверка, и вызов ФВ с возвратом сразу оценки - должен быть ПЕРЕД null move...
    Кстати - в пустом ходе (вызове Search) - окно ВСЕГДА нулевое!!!
    А возвращаться может как Бета, так и сам результат перебора
     
  9. Binary
    Оффлайн

    Binary Учаcтник

    Репутация:
    0
    если null move вызывать на глубине 0 после ФВ , то не теряется ли сам смысл Null move как средства отсечения
    плохих ходов?!
    ведь точнее чем ФВ NULL MOVE все равно не вернет оценку , а время потратит
     
  10. NS
    Оффлайн

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

    Репутация:
    3
    Я не понимаю тебя...
    1. яТебе написал что Null Move запускается ТОЛЬКО ПРИ DEPTH>=2
    Есно NULL MOVE не может запускаться при Depth=0,

    Я тебя спрашиваю - если при Depth=0 НЕ МОЖЕТ ЗАПУСКАТЬСЯ Null Move -
    то почему проверка на depth=0 должна выполнятся ПОСЛЕ Null Move, а не перед????
     
  11. Binary
    Оффлайн

    Binary Учаcтник

    Репутация:
    0
    проверка на depth = 0 у меня в самом начале search() если true , то я вызываю Quiesce ;

    я просто криво прочитал твой пост :)
    все догнал (sorry)
    так у меня все и сделано
     
  12. NS
    Оффлайн

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

    Репутация:
    3
    У меня проверка на Depth=0 не в самом начале, так как перед этим делаются несколько проверок, проверяется на повторение позиции, ищется оценка в Хеше, и вызов ФВ при depth<=0 идет только в случае, если король не под шахом (в схеме ФВ без шахов - это несколько поднимает силу программы)
     
  13. Binary
    Оффлайн

    Binary Учаcтник

    Репутация:
    0
    Мне только предстоит добавлять все это дело :) (и бессонные ночи перед отладчиком)
     
  14. gudvinn
    Оффлайн

    gudvinn Учаcтник

    Репутация:
    0
    Объясните пожалуста , что такое follow_pv?
     
  15. bankuss
    Оффлайн

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

    Репутация:
    6
    gudvinn находимся в PV ветви
     
  16. WildCat
    Оффлайн

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

    Репутация:
    0
    В алгоритме PVS поиск основного варианта, несколько отличается от обычного.
    follow_pv означает, что мы ищем основной вариант.

    В простой алфа-бете это может значить, что мы выполняем ходы из ранее найденного (при предыдущей итерации) основного варианта.
     
  17. gudvinn
    Оффлайн

    gudvinn Учаcтник

    Репутация:
    0
    У меня простая альфа-бета. Из предыдущего варианта таких ходов будет 2-3?
    Я пробовал делать negascout скорость возросла чуть-чуть ( например, если поставить фиксированную глубину , то разница для позиции а-б 8.5 сек , а negascout 8.4 sec).

    А где можно почитать про PVS метод?
    И про negascout — я так и не понял в чем суть этого алгоритма.
     
  18. NS
    Оффлайн

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

    Репутация:
    3
    negascout - метод дерева нулевой ширины.
    Есть теорема, что при идеальном хеше и отсутствии нестабильности перебора - он просматривает не больше узлов чем Альфа-бета... Всегда. И если доступ к такому Хешу моментален, то соответственно negascout всегда лучше Альфа-беты.
    Но на практике У нас полная нестабильность перебора, и далеко не идеальный Хеш.
    PVS - некоторые так называют negascout, но на самом деле это метод извлечения PV.
     
  19. WildCat
    Оффлайн

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

    Репутация:
    0
    Линки можно найти здесь http://wbforum.volker-pittlik.name/
    Насколько я помню, NegaScout - это то же, что и альфа-бета (минимакс), только вместо двух функций одна.
     
  20. NS
    Оффлайн

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

    Репутация:
    3
    Нет. NegaMax - Вместо двух функций одна, а NegaScout - Это и есть метод дерева нулевой ширины.
    Так как для извелечения PV при NegaScout используется PVS, то стали отожествлять PVS и NegaScout.
     
  21. WildCat
    Оффлайн

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

    Репутация:
    0
    Ты попутал с MTD(f).
     
  22. NS
    Оффлайн

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

    Репутация:
    3
    Нет, MTD(f) - это развитие идеи NegaScout, метод при котором нулевая ширина дерева всегда.
     
  23. NS
    Оффлайн

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

    Репутация:
    3
    MTD(f) is a new minimax search algorithm, simpler and more efficient than previous algorithms. In tests with a number of tournament game playing programs for chess, checkers and Othello it performed better, on average, than NegaScout/PVS (the AlphaBeta variant used in practically all good chess, checkers, and Othello programs). One of the strongest chess programs of the moment, MIT's parallel chess program Cilkchess uses MTD(f) as its search algorithm, replacing NegaScout, which was used in StarSocrates, the previous version of the program.



    http://www.cs.vu.nl/~aske/mtdf.html
     
  24. WildCat
    Оффлайн

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

    Репутация:
    0
    PVS - Principal Variation Search. Первые ходы перебираются с нулевым окном, все остальные с обычным.
     
  25. NS
    Оффлайн

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

    Репутация:
    3
    Общепринятое заблуждение. :)

    Оригинал взят с http://www.zib.de/reinefeld/nsc.html

    Нега-скаут (NegaScout)

    Подобно AlphaBeta, NegaScout - направленный алгоритм поиска для вычисления минимаксного значения узла.

    NegaScout эффективнее AlphaBeta: он никогда не исследует узла, который может быть отсечен AlphaBeta.

    Ни NegaScout не превосходит SSS*, ни наоборот: Существуют деревья, в которых NegaScout ищет строго меньшее количество узлов чем SSS* и наоборот. На среднестатистических деревьях, однако, SSS* обычно просматривает меньшее количество узлов чем NegaScout.
    Тот же самое относится к DUAL*.
    Формальные доказательства могут быть найдены в: A. Reinefeld. Spielbaum-Suchverfahren. Informatik-Fachbericht 200, Springer-Verlag, Берлин (1989), ISBN 3-540-50742-6

    C-подобный код:

    int NegaScout ( position p; int alpha, beta );
    { /* вычислить минимаксное значение позиции p */
    int a, b, t, i;

    determine successors p_1,...,p_w of p;
    if ( w == 0 )
    return ( Evaluate(p) ); /* лист дерева */
    a = alpha;
    b = beta;
    for ( i = 1; i <= w; i++ ) {
    t = -NegaScout ( p_i, -b, -a );
    if (t > a) && (t < beta) && (i > 1) && (d < maxdepth-1)
    a = -NegaScout ( p_i, -beta, -t ); /* повторный перебор */
    a = max( a, t );
    if ( a == beta )
    return ( a ); /* отсечение */
    b = a + 1; /* установить новое нулевое окно */
    }
    return ( a );
    }

    © 1999 Konrad-Zuse-Zentrum fur Informationstechnik Berlin (ZIB)
    © Перевод с английского - С. Марков, 2000

    http://www.aigroup.narod.ru/search2r.htm
    http://www.aigroup.narod.ru/indexr.htm
     
  26. WildCat
    Оффлайн

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

    Репутация:
    0
    Посмотрел в инете. Оказывается PVS и NegaScout это одно и то же. Мне приятнее называть PVS.
     
  27. WildCat
    Оффлайн

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

    Репутация:
    0
    PVS is also often called NegaScout. It gets its name from the scout search which a minimal window, which sort of probes the territory to see whether a real search is necessary.
     
  28. NS
    Оффлайн

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

    Репутация:
    3
    Недавно только стали отожествлять, изначально PVS метод извлечения PV и разделения ветвей.
    В изначальной формулировке - PVS может использоваться и при чистой Альфа-Бете, без нулевого окна - только для извлечения PV, и например для принятия решения о применения методов отсечения (LMR, Null Move, Футилити - для примера только не в PV ветвях)
     
  29. WildCat
    Оффлайн

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

    Репутация:
    0
    Все наоборот. Первый ход в полном окне, все остальные с нулевым.
    PVS == NegaScout
     
  30. NS
    Оффлайн

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

    Репутация:
    3
    Посмотрел Википедию, они тоже приравняли PVS и NegaScout...
    Пускай будет одно и тоже. :)
     
  31. варяг
    Оффлайн

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

    Репутация:
    0
    А как правильно считать размер хэш таблицы? Пусть утверждается, что, например, размер хэш-таблицы равен (допустим) 64 МБ? Пусть одна запись в хэше занимает 16 байт: 8 байт для хранения ключа и 8 байт для хранения сопутствующей информации. Означает ли это, что количество записей в хэш таблице равно 64х1024х1024=67108864 записей. Или это означает, что кол-во равно 67108864/16=4194304 записей?
     
  32. Binary
    Оффлайн

    Binary Учаcтник

    Репутация:
    0
    приспособил этот код в свою прогу и он несет пургу ...
    это правильный код?!
    это сообщение 4000 - ное :D
     
  33. NS
    Оффлайн

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

    Репутация:
    3
    Я не знаю, как ты его приспособил :)
     
  34. Binary
    Оффлайн

    Binary Учаcтник

    Репутация:
    0
    скажите , каковы параметры в IID - a то я ,как всегда, сразу не мог спросить :)
    сейчас в моих экспериментах лучшим оказывается просто quiesce(-beta , -alpha ) , т.е. поиск на глубину 0
    ... но NS говорил , что надо делить depth
     
  35. NS
    Оффлайн

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

    Репутация:
    3
    Ты после IID - получаешь лучший ход?
    Каким образом ФВ может тебе вернуть лучший ход, если в нем вообще не все ходы рассматриваются?