Anechka

Code:

rootScore:=0;
delta:=50;
For Depth:=1 to 40 do
Begin
  if Depth=1 then
  begin
    a:=-inf;
    b:=inf;
  end
  else
   begin
     a:=rootScore-delta;
     b:=rootScore+delta;
   end;
   repeat
      if rootScore>=b Then b:=+inf;
      if rootScore<=a Then a:=-inf; 
      rootScore:=search_root(a,b,depth);
   until (rootScore>a) and (rootScore<b);
End;

Вот что я имел в виду.
Окно расширяем не до (rootScore,+inf), а до (а,+inf) Так как это практически не изменяет время выполнения, но при более узком окне (классическом) можно напороться на неприятности связанные с нестабильностью перебора.

Соответственно, если первый ход вызовет опровержение по бете - то произойдет выход из search_root, и первый ход будет рассмотрен с более широким окном, а если первый ход будет опровергнут по Альфа - то окно не будет расширено, и с текущим окном будут рассмотрены все остальные ходы, и только если они все будут опровергнуты по Альфа - произойдет изменение нижней границы на -inf;
При этом может поменяться лучший ход (ход, который с более широкими границами будет рассмотрен первым)

Или учше вообще сделать практически MTD(f) ???

Code:

rootScore:=0;
delta1:=50;
delta2:=50;
// Наилучшие значения найдем опытным путем....
For Depth:=1 to 40 do
Begin
  if Depth=1 then
  begin
    a:=-inf;
    b:=inf;
  end
  else
   begin
     a:=rootScore-delta1;
     b:=rootScore+delta1;
   end;
   repeat
      if rootScore>=b Then b:=rootScore+Delta2;
      if rootScore<=a Then a:=rootScore-Delta2; 
      rootScore:=search_root(a,b,depth);
   until (rootScore>a) and (rootScore<b);
End;

В SmarThink первый ход смотрится вначале с окном от eval-0.01 до eval+0.01. Потом расширяется до +/- 0.30. А затем уже до inf. Но на самом деле это не очень важно. "Узкое" окно помогает там, где оценка определяется либо одними и теми же ходами ФВ, либо отсечениями. В эндшпиле такое особенно часто происходит. Учитывая, что перебор SmarThink fail-hard, то в нем вероятность сохранения той-же оценки на следующей итерации еще выше.
В свое время я перепробовал несколько разных моделей, начиная от MTD(f) (который очень плох в сочетании с пустым ходом) и кончая разными хитрыми MT-движками. Например, можно учитывать, что если ход единственный, то нам не нужна его точная оценка и т.п. Но сила движка лежит определенно не тут...

То что сила движка лежит не тут - это ясно, я просто пытаюсь избежать провалов Брейчинг-Фактора.
а чем Fail-Soft отличается от Fail-Hard?
Я думал что у меня Fail-Soft, но теперь начинаю подозревать что всё-таки Hard
Я возвращаю максимально опровергающую оценку, плюс использую значение из Хеша в PV.
Что-то я в терминологии запутался или Fail-Safe?

Значит у меня Fail-Soft....
Что-то не могу понять, какие преимущества могут быть у Fail-Hard?
Только большая стабильность перебора?
(я правильно понял - в случае опровержения Fail-Hard возвращает либо альфу либо бету?)

Не совсем. У меня возвращается значение от alpha до inf.
В fail soft возвращается не alpha, в случае если не было ни одного значения >alpha, а максимальное из значений, которые были получены.
Преумущество у моей модели никаких, равно как никаких de facto преимуществ у fail soft. Во всяком случае на моих тестах.

У меня pvs. А что, alpha/beta с хитростями лучше pvs?
Может быть pvs это и есть лучшая хитрость для alpha/beta?

Кстати, в свое время читал много по теории переборных алгоритмов. Есть такая теорема, что mtd(f) с идеальным хэшем эквивалентен best-first

Наверно в этой теореме не учитывалась нестабильность перебора вызванная Пустым ходом и LMR

Есть теорема, в ней не учитывается время обращения к хешу (считаются только просмотренные узлы) - сылка есть на странице Plaat-а (вроде так) посвященной mtd(f)

Насколько я понимаю, что схема с возвратом оценки от Альфа до inf полностью равнозначна схеме с возвратом оценки от Альфа до Бета...
Так как оценка большая, чем Бета - в предыдущем узле (где она станет меньшей Альфы) Будет приравнена к Альфе
Разница только в значениях в Хеше на последнем Ply (пока идёт запись в хеш...)

На всех, но оценка не входящая в окно (Альфа,Бета), большая чем бета - в такой схеме может записаться только на последнем уровне...

Incidentally, one of the MTD instances is equivalent to SSS*, George Stockman's best-first minimax algorithm that promised to be more efficient than AlphaBeta. (By equivalent I mean that the two algorithms look different, but search the same nodes.) This SSS*-MTD made the first practical tests of SSS* in full-fledged game playing programs feasible, shedding new and unexpected light, after more than 15 years, on the questions posed in Stockman's 1979 article. See our 1996 article in Artificial Intelligence for more on this subject. (And yes, MTD(f) is also better than SSS*, in case you wondered.)

http://theory.lcs.mit.edu/~plaat/mtdf.html

http://theory.lcs.mit.edu/~plaat/Papers/aij-final.ps.gz

Наверно сделаю так -
При опровержении пустым ходов - возвращается Бета
В случае Futility и Extended Futility (Статистическая оценка меньше альфа-Margin (при depth=1 или depth=2)), либо LMR (у меня при depth>=3) Возращается в окне (Альфа,+inf) (так как с верификацией)
В остальных случаях возвращается реальная оценка. (Других отсечений/сокращений у меня пока нет)
Наверно четкий Fail-Hard и получается... Везде максимально достоверная опровергающая оценка.

Нет, best-first это SSS*
Там где-то было тоже самое в pdf
Но при идеальном Хеше он не смотрит лишних узлов...
Сейчас точно не помню, но вроде тот-же mtd(f), только начинаем с оценки +inf

http://66.249.93.104/search?q=cache....pdf+best-first+SSS*&hl=ru&gl=ru&ct=clnk&cd=9

Тут на 55-той странице. Но текст невнятный, вроде равносильно Mtd(f) с начальным значением +inf, с рассмотрением в первую очередь ходов имеющих максимальную оценку (в хеше) после Fail-Soft.
(то есть в хеше хранится только верхняя оценка, изначально +inf)

Это ежели я ничего не перепутал.

SSS* - один из примеров минимизации количества просмотренных узлов.
С помощью Mtd(f) (с начальным значением +inf, и уменьшением оценки) Вроде был произведен его первый практический тест.
(как раз и получается, что всё время смотрим ход с максимальной оценкой, остальные отсекаются значением в Хеше)

Так и есть, хотя последним полуход может, например, в силу возникновения мата и т.п. Плюс к этому не стоит забывать про неглубокие вспомогательные переборы, отсечения и т.д.

А чем схема их 53-го поста хуже? (чем схема с возвратом всегда в интервале (Альфа, +inf)) ?

Я не проводил таких тестов. Я же говорю: сила движка не тут. У меня по тестам fail-soft и fail-hard не отличаются в пределах погрешности.

В том то и дело - что считаем хеш идеальным - неограниченный размер, и моментальный доступ.
Тогда Mtd(f) и его модификации рулят... (+еще одно условие: стабильность поиска)

Можно попробовать сделать +3 Ply (либо гибкое увеличение глубины в зависимости от текущего depth) при переходе в пешечный эндшпиль.
До оценки со временем доберусь - но наверно после миттельшпиля. То есть в версии 0.09 сильных изменений в эндшпильной оценке не будет. (может добавлю Таблицу для Король и пешка против короля и правило квадрата - это недолго, над остальным нужно думать...)
Но защищенность короля в первую очередь - а это для меня самое сложное на данный момент, раньше особо не обдумывал.

Текущий рейтинг в третьей лиге WBEC. Посчитан Bayesian Elo:

Code:

Rank Name                Elo    +    - games score oppo. draws 
   1 Djinn 0.925x        115   77   73    56   67%    -3   30% 
   2 Muse 0.899b uci     102   73   70    58   66%     2   34% 
   3 Capture R01          63   76   74    56   58%     7   23% 
   4 Bruja 1.9            51   74   72    60   55%    13   20% 
   5 Ant 2006-F           36   72   71    60   55%    -1   23% 
   6 K9 0.32              34   74   73    56   56%   -11   30% 
   7 Tytan 8.64           33   72   71    56   54%     9   32% 
   8 Resp 0.19            25   71   70    60   55%    -9   30% 
   9 Anechka 0.07         18   70   69    60   53%     4   32% 
  10 Eeyore 1.49i         11   74   73    56   51%     1   27% 
  11 Arion 1.7             8   71   71    60   50%     7   27% 
  12 Diablo 0.4            3   72   72    58   47%    15   29% 
  13 Xpdnt 060602          0   72   72    60   51%    -4   22% 
  14 Thor'sHammer 2.28    -7   71   71    60   49%    -3   28% 
  15 Tornado 0.84.2      -25   73   73    56   48%   -12   29% 
  16 Knightx 1.92        -29   72   72    60   48%    -9   22% 
  17 Gaia 3.5            -33   73   75    56   44%     9   27% 
  18 Hermann 1.72        -41   76   77    56   45%     0   18% 
  19 Butcher 1.57        -43   70   72    60   40%    22   30% 
  20 EXchess 5.01b       -50   73   74    56   44%    -8   27% 
  21 Chispa 4.03         -61   74   76    56   41%    -2   25% 
  22 Scidlet 3.6         -65   76   78    56   43%   -13   18% 
  23 Terra 3.4           -66   76   78    56   42%    -5   20% 
  24 Waster 0.16         -79   73   76    60   40%    -7   17%

Такое впечатление что мне нехватает совсем немного...

И время. Если бы я не начал писать программу впритык, то не выдохся бы так быстро (просто устал, и получился переизбыток информации за короткое время), и успел бы прибавить сотню пунктов. А то толком до ОФ так и не дошел... А Хистори добавлял в спешке - и не успел как следует продумать.
Плюс не успел (скорее забыл) убрать излишества в ФВ (проверку на шах и проверку на легальность)