Итак, первый этап пройден.
Добавлены все методы, которые я запланировал (кроме сортировки по истории). Играет он не очень сильно. Слишком маленькая глубина перебора. Может, для этой схемы это предел?
А, может, реализация слишком кривая. Ответить на эти вопросы попытаемся в этой статье.

1) ГЕНЕРАТОР ПОЗИЦИЙ.

1. Он состоит из:
1> Генератора избыточных ходов.
2> Реализатора ходов.
3> Детектора шахов.

Сейчас генератор выдает около миллиона позиций в секунду. Конечно, бывают генераторы со скоростью и 3, и 10. Т.е. тут есть куда стремиться. Вот только нужно ли мне это?

Оболочка показывает от 50 до 150 kN/s (тысяч позиций в секунду). Скорость, конечно, довольно маленькая, учитывая к тому же примитивность оценки. Но это показывает оболочка, мне надо скорость мерить самому. Измерил сам. Скорость где-то 200 kN/s. У других движков: 300 – 700.

В любом случае, разброс скоростей в рамках одного порядка. В итоге, я не думаю, что увеличение скорости даже в шесть раз (150*6=900) даст мне хотя бы полуход. Хотя, стоит признать, что чем глубже мы забираемся, тем скорость существеннее влияет на время обдумывания. Разница есть – думаем мы шесть минут или минуту.

2. Запись варианта и оценка позиции интересуют нас только с точки зрения скорости.


2) ПУТИ РЕШЕНИЯ ПРОБЛЕМЫ ПЕРЕБОРА

1. Идти можно разными путями. Можно идти путем ускорения счета, а можно путем уменьшения объема счета.
1> В первом случае мы имеем полный перебор. Генерируем все возможные позиции и оцениваем их. Очевидно, что при одинаковой глубине перебора мы имеем битвы оценок. Победит та прога, у которой лучше оценка. Тут мы четко понимаем, что оценка имеет принципиальное значение.
2> Основная проблема в том, что с глубиной количество позиций увеличивается по экспоненте. Таким образом, и скорость у нас должна расти по экспоненте, иначе будет расти по экспоненте время. А последнее неприемлемо, так как время у нас ограниченно (где-то 5 мин на партию).
3> Очевидно, что увеличивать скорость по экспоненте мы не можем. Хотя бы потому, что ресурсы машины ограниченны и программы, как правило, используют одинаковые или соизмеримые ресурсы. Таким образом, путем увеличения скорости счета задачу не решить, хотя и тут есть миниум, ниже которого опускаться не стоит. Скорость должна быть одного порядка со скоростью других прог.

2. Посмотрим на это с цифрами. Для определенности возьмем начальную позицию.

Глубина перебора    Количество узлов     Необходимая скорость для перебора за 1 секунду
3                                9 322                           ~9 kN/s
4                                206 603                       ~206 kN/s
5                                5 072 212                    ~5 072 kN/s
6                                124 132 536                ~124 132 kN/s
7                                3 320 034 396             ~3 320 034 kN/s
(8,9,10 вычислял сам)
8                                88 319 013 352           ~88 319 013 kN/s
9                                2 527 849 247 519       ~2 527 849 247 kN/s
10                              71 880 708 959 936     ~71 880 708 959 kN/s

Другими словами для перебора за секунду на:

– глубину 4 нужна скорость 206 тысяч узлов секунду;
– глубину 5 нужна скорость 5 миллионов 72 тысячи узлов в секунду;
– глубину 6 нужна скорость 124 миллиона 132 тысячи узлов в секунду;
– глубину 7 нужна скорость 3 миллиарда (!) 320 миллионов 034 тысячи узлов в секунду.

Таким образом, мы наглядно видим, что на сегодня:
– глубина 5 реальна для высокоскоростного кода на хорошей машине;
– на лучших машинах при лучшей реализации может быть и можно дотянуться до глубины 6, хотя не уверен;
– а вот глубина 7 совершенно нереальна, даже в ближайшем будущем.

Ифрит выдает скорость ~206 kN/s, так что его глубина – 4. А учитывая форсировки, вообще – 3 :). Это, конечно, маловато и надо бороться за скорость не ниже ~300 kN/s.

3. Нам остается единственный путь – это отсечение некоторых веток. В программе я использую два метода сокращения перебора – это альфа-бета и нулевой ход.

3) АЛЬФА-БЕТА ОПТИМИЗАЦИЯ
1. Для альфа-беты главным является порядок ходов. Теоретически, при идеальном порядке мы должны рассмотреть корень из числа позиций полного перебора, говоря по-другому, этот метод может дать увеличение глубины в два раза.
Для 6 нужно перебрать 11 141 узлов
Для 7 нужно перебрать 57 619 узлов
Для 8 нужно перебрать 297 185 узлов
Для 9 нужно перебрать 1 589 921 узлов
Для 10 нужно перебрать 8 478 249 узлов
2. Основной вывод такой: при скорости ~206 kN/s идеальная альфа-бета позволит достичь глубины 8 за 1,4 сек. Глубины 9 за 7,7 сек. Глубины 10 за 41 сек. Причем, полному перебору для просчета с такой скоростью на глубину 10 понадобилось бы где-то порядка 11 лет непрерывного счета! Следует уточнить, что под скоростью тут мы имеем в виду скорость перебора узлов полного перебора без учета скорости и количества узлов в форсированных вариантах.
Таким образом, даже при идеальной альфа-бете при такой скорости за секунду мы сможем дойти только до 7 глубины. Если же мы поднимем скорость до 300 kN/s, то можно будет ожидать глубину 8.

4)СОРТИРОВКИ
1. В виду того, что для альфа-беты порядок ходов принципиален, особое значение приобретают сортировки ходов.
Рассмотрим различные методы.
Выводим в следующем порядке: глубина, время перебора, количество узлов, скорость перебора, оценка, вариант

Альфа-бета без сортировки:
7/7    01:31    15.780.730

Киллер – это самая мощная сортировка:
7/7    00:16    2.271.275    167.845    +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8    01:41    15.502.822  182.253    -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3

Далее сортировка по взятиям (взятия выводим наверх):
7/7    00:43    6.561.135    173.304    +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8    04:56    44.709.148  177.208    -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3

Далее хеш:
6/6    00:06    1.157.998  193.516    -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7    00:45    6.702.890   173.045   +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+

Далее сортировка по порядку: ферзь, ладья, слон, конь, король, пешки:
7/7    00:49    7.204.299    173.598    +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8    09:58    100.368.643 182.894    -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3

2. Если применить все методы сортировки, то получим.
Альфа-бета + хеш + киллер (новая сортировка) + сортировка по взятиям + сортировка в следующем порядке: ферзь,
ладья, слон, конь, король, пешки:
7/7    00:12    1.353.303    140.837   +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8    01:01    6.926.790    140.600   -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3

При максимальной сортировке мы получили в 23 раза больше узлов, чем при идеальной сортировке.
6.926.790 узлов вместо 297 185 узлов.

3. Отдельно рассмотрим негаскаут.
Альфа-бета + хеш + киллер (новая сортировка) + сортировка по взятиям + сортировка в следующем порядке: ферзь,
ладья, слон, конь, король, пешки + негаскаут:

6/6    00:03    338.214      133.629    -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7    00:12    1.390.746   159.801    +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8    00:55    6.124.158    140.183    -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3
Без негаскаута:
8/8 01:01 6.926.790 140.600 -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3

Незначительный эффект от негаскаута есть. Так что есть смысл оставить этот метод. Он тем лучше работает, чем точнее сортировка. Если сортировки нет, то от него только хуже.
Это и понятно ведь мы смотрим первый ход с полным окном, остальные пытаемся отсечь нулевым. Если не получается, то смотрим с полным окном.
Вообще-то эффект очень незначителен, так что можно и без него. Возможно, просто реализация у меня кривая.


5) НУЛЕВОЙ ХОД
Альфа-бета + хеш + киллер (новая сортировка) + сортировка по взятиям + сортировка в следующем порядке: ферзь,
ладья, слон, конь, король, пешки + негаскаут + нулевой ход:

6/6      00:01    66.475           -                -0,05 a2a4 Nb8c6 Ng1f3 e7e5 Nb1c3 Bf8e7
7/7      00:02    99.827          138.841      +0,19 a2a4 Nb8c6 Ng1f3 e7e6 d2d4 Bf8e7 Bc1d2
8/8      00:09    838.007        119.187      -0,03 a2a4 Nb8c6 Nb1c3 Nc6d4 e2e3 Nd4f5 e3e4 Ng8f6
9/9      00:25    2.058.082     127.752      +0,22 e2e4 Nb8c6 Bf1b5 Nc6d4 Bb5e2 Ng8f6 Nb1c3 Nd4xe2 Ng1xe2
10/10  02:49    17.883.526   124.016      +0,14 g2g3 Nb8c6 Bf1g2 Nc6d4 Ng1f3 Nd4xf3+ Bg2xf3 d7d5 00 Bc8d7

Без нулевого хода:
6/6      00:03      338.214        133.629    -0,72 a2a4 g7g6 b2b4 Bf8h6 Nb1c3 Bh6xd2+
7/7      00:12      1.390.746     159.801    +0,92 e2e3 a7a5 Bf1c4 Nb8c6 Ng1e2 Ng8f6 Bc4xf7+
8/8      00:55      6.124.158     140.183    -0,77 g2g3 a7a5 Bf1g2 Ra8a6 Nb1c3 Ra6g6 Ng1f3 Rg6xg3

Ускорение от нулевого хода просто потрясающее. Для глубины 8 при идеальной сортировке нужно рассмотреть 297.185 узлов,
мы рассмотрели 838.007 узлов, всего в 2,8 раза больше.

Для глубины 10 при идеальной сортировке нужно рассмотреть 8 478 249 узлов, мы рассмотрели 17.883.526 узлов, всего в 2,1 раза больше.

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

Другой вопрос – даст ли нулевой ход прирост при идеальной альфа бете.

 

Добавление от 14.06.2010

Конечно же, нулевой ход - это отдельная эвристика, не имеющая отношения ни к альфа-бета оптимизации, ни к сортировке ходов.

В данной статье я не очень удачно выразил свою мысль. Сейчас попробую это исправить.

Если мы используем а-б с идеальной сортировкой для глубины 10 полуходов, нужно перебрать 8 478 249 узлов.

У меня же а-б с моей сортировкой + эвристика нулевого хода для глубины 10 полуходов перебрала 17.883.526 узлов. Т.е. в 2.1 раза больше.

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

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

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

Надо сказать, что и в данный момент я не могу уверенно ответить на этот вопрос.