параметры NULL MOVE

скажите , какие параметры чаще всего используются при вызове пустого хода ?
например , я сделал 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) Это R=1.
Обычно делают либо Depth-4 (R=3) либо Depth-3 (R=2)
То что ты делишь - такая схема обычно используется в IID, но не в Null Move.

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

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

 

NS - спасибо

 

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

 

очередь хода передать не забываю

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

 

Не понял - Как это пустой ход запихнуть перед вызовом ФВ???

 

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

 

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

 

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

 

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

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

 

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

я просто криво прочитал твой пост
все догнал (sorry)
так у меня все и сделано

 

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

 

Мне только предстоит добавлять все это дело (и бессонные ночи перед отладчиком)

 

Объясните пожалуста , что такое follow_pv?

 

gudvinn находимся в PV ветви

 

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

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

 

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

 

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

 

Нет, MTD(f) - это развитие идеи NegaScout, метод при котором нулевая ширина дерева всегда.

 

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

 

Общепринятое заблуждение.

Оригинал взят с 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

 

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

 

Посмотрел Википедию, они тоже приравняли PVS и NegaScout...
Пускай будет одно и тоже.

 

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

 

приспособил этот код в свою прогу и он несет пургу ...
это правильный код?!
это сообщение 4000 - ное

 

Я не знаю, как ты его приспособил

 

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

 

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