Ifrit
Часть 6

Опубликованная версия Ifrit_j1_2

___________________________________________________________________________________
Пятница, 31 июля 2009 г.

Каким образом сильнейшим движкам удается так сильно играть?

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

Для поиска главный параметр это глубина. Смотреть нужно как можно глубже. Но для этого нужно отсекать лишнее, при этом можно отсечь стоящие варианты. В этом и проявляется главная антиномия поиска - смотреть нужно как можно глубже и как можно полнее, что невозможно.
Весь секрет в качественном отсечении лишнего и продления нужного.

Считаю, что в данный момент оценка позиции самое слабое место Ифрита. Над оценкой будем работать.
Конечно, глубина поиска тоже слишком маленькая и тут тоже нужно дорабатывать, но на поиске я и так зациклился.
В общем, и глубина, и оценка оставляют желать лучшего.

___________________________________________________________________________________
Воскресенье, 2 августа 2009 г.
Начальная позиция.
Как мы помним, для полного перебора справедливы следующие значения:
Глубина перебора    Количество узлов
 3                                            9 322
 4                                        206 603
 5                                     5 072 212
 6                                 124 132 536
 7                              3 320 034 396

Значит, глубина счета будет от 4 до 5 полуходов в секунду, в зависимости от скорости.
Для идеальной альфа беты от 8 до 10 полуходов в секунду.
Идеальная альфа-бета:
 6           11 141 узлов
 7           57 619 узлов
 8         297 185 узлов
 9      1 589 921 узлов
 10    8 478 249 узлов

Ифрит реально считает:
 6            28 тысяч узлов(2,5)
 7          382 тысяч узлов(6,5)
 8          906 тысяч узлов(3)
 9       9 988 тысяч узлов(6,2)
 10   47 804 тысяч узлов(5,6)

У Ифрита скорость ~400кн/сек., он показывает глубину 7 полуходов в секунду.
С сортировкой можно поработать, но выше 8 все равно не прыгнуть.
Таким образом, тут цена вопроса один полуход.

___________________________________________________________________________________
Суббота, 8 августа 2009 г.

У Фрукта в чистой альфа-бете скорость ~1200кн/сек., он показывает:
глубина 9 за 2 секунды и 2566 тысяч узлов.
Тут что-то не то. И это «что-то» кроется в хеш-таблице.

Отключив отсечения при использовании хеш-таблицы, получил:
9 глубина за 8 секунд и 10752 тысяч узлов.

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

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

В данный момент в Ифрите хеш-таблица используется только для сортировки. Это избавляет меня от ошибок связанных с таблицей. Все ошибки влияют на скорость и больше ни на что.
Без таблицы
 9    12 269 тысяч узлов(6,2) за 21 секунду
с таблицей
 9    9 850 тысяч узлов(6,2) за 16 секунд.

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

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


Наконец-то взялся за статическую оценку.
План того, что должно быть учтено.

Надо будет учесть следующие параметры (таблица от WildCat’а он же Игорь Коршунов)

1. проходные - 195
2. ценность полей - 173
4. мобильность - 78
3. пешечный щит - 69
5. тяжелые фигуры - 29
6. пешечная структура - 25
7. очередность хода - 18
8. атака на короля - 9
9. паттерны - 0

Элементы, отнимающие силу:

Код: Выделить всё
10. разноцвет - 19


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

___________________________________________________________________________________


Опубликованная версия Ifrit_j1_3

___________________________________________________________________________________
Среда, 19 августа 2009 г.
Вчера выложил новую версию. Вывел параметры оценки во внешний файл. Специально не стал ничего добавлять.
Таким образом, осталась корявая и недостаточно проработанная оценка. И оценку, и количество параметров надо менять.

___________________________________________________________________________________
Суббота, 22 августа 2009 г.

Похоже, что сортировка по истории в моем исполнении ничего не дает.

FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

С сортировкой по истории:
При отсечке по бете прибавляем 1
Ifrit_j1_4_Beta_24_8_2009:
10/10 01:33 40.216.875 498.331 +0,03 e2e4 Ng8f6 e4e5 Nf6d5 Ng1f3 Nd5f4 Nb1c3 Nb8c6 Nc3e2 Nf4d5

При отсечке по бете прибавляем depth
Ifrit_j1_4_Beta_24_8_2009:
10/10 01:24 35.905.985 500.320 +0,03 e2e4 Ng8f6 e4e5 Nf6d5 Ng1f3 Nd5f4 Nb1c3 Nb8c6 Nc3e2 Nf4d5

При отсечке по бете прибавляем depth_max – depth
Ifrit_j1_4_Beta_24_8_2009:
10/10 01:27 36.295.506 486.880 +0,03 e2e4 Ng8f6 e4e5 Nf6d5 Ng1f3 Nd5f4 Nb1c3 Nb8c6 Nc3e2 Nf4d5

Что-то непонятное. Отключил сортировку, но оставил историю в генераторе и в результате сюрприз.
Ifrit_j1_4_Beta_24_8_2009:
10/10 01:17 40.604.902 617.123 +0,03 e2e4 Ng8f6 e4e5 Nf6d5 Ng1f3 Nd5f4 Nb1c3 Nb8c6 Nc3e2 Nf4d5

Без сортировки тихих ходов:
Ifrit_j1_4_Beta_22_8_2009:
10/10 01:33 48.715.229 611.570 +0,03 e2e4 Ng8f6 e4e5 Nf6d5 Ng1f3 Nd5f4 Nb1c3 Nb8c6 Nc3e2 Nf4d5

Плохие взятия в конец:
Ifrit_j1_4_Beta_22_8_2009:
10/10 01:42 49.795.562 576.818 +0,03 e2e4 Ng8f6 e4e5 Nf6d5 Ng1f3 Nd5f4 Nb1c3 Nb8c6 Nc3e2 Nf4d5

___________________________________________________________________________________
Среда, 26 августа 2009 г.

Чистая альфа-бета.

FEN: 5rk1/1p6/q2P3p/2p2rp1/p1nbQ3/P1N3BP/1PR1B1P1/4K3 b - - 0 1

С сортировкой взятий.
Ifrit_j1_4_Beta__25_8_2009:
9/10 01:17 58.259.236 996.685 +1,78 b7b5 Be2d3 Kg8h8 d6d7 Rf5f7 Bd3xc4 b5xc4 Bg3e5+ Bd4xe5 Qe4xe5+

Без сортировки взятий.
Ifrit_j1_4_Beta__25_8_2009:
9/10 02:11 58.164.410 631.576 +1,78 b7b5 Be2d3 Kg8h8 d6d7 Rf5f7 Bd3xc4 b5xc4 Bg3e5+ Bd4xe5 Qe4xe5+

С сортировкой взятий встроенной в цикл обхода списка. Так что при отсечке по бете лишнее не сортируем. Почти никакого эффекта.
Решил оставить, как было. Т.е. в виде отдельной функции.
Ifrit_j1_4_Beta__25_8_2009:
9/10 01:17 58.259.236 998.016 +1,78 b7b5 Be2d3 Kg8h8 d6d7 Rf5f7 Bd3xc4 b5xc4 Bg3e5+ Bd4xe5 Qe4xe5+

Сделал фигуру которую берут на порядок тяжелее той, которой берут.
Ifrit_j1_4_Beta_26_8_2009:
9/10 00:21 15.090.935 959.068 +1,78 b7b5 Be2d3 Kg8h8 d6d7 Rf5f7 Bd3xc4 b5xc4 Bg3e5+ Bd4xe5 Qe4xe5+
10/12 01:26 28.512.975 436.044 +1,68 b7b5 Be2d3 Kg8h8 Bd3xc4 b5xc4 Qe4e2 Kh8g8 Qe2e6+ Kg8g7 Ke1d1 Bd4xc3 b2xc3

Включил delta pruning.
Ifrit_j1_4_Beta_26_8_2009:
9/10 00:18 15.091.303 1.050.926 +1,78 b7b5 Be2d3 Kg8h8 d6d7 Rf5f7 Bd3xc4 b5xc4 Bg3e5+ Bd4xe5 Qe4xe5+
10/12 01:07 28.595.814 588.475 +1,68 b7b5 Be2d3 Kg8h8 Bd3xc4 b5xc4 Qe4e2 Kh8g8 Qe2e6+ Kg8g7 Ke1d1 Bd4xc3 b2xc3

Включил запись истории (depth_max – depth).
Ifrit_j1_4_Beta_26_8_2009:
9/10 00:26 14.199.254 746.072 +1,78 b7b5 Be2d3 Kg8h8 d6d7 Rf5f7 Bd3xc4 b5xc4 Bg3e5+ Bd4xe5 Qe4xe5+
10/12 02:11 27.180.343 258.439 +1,68 b7b5 Be2d3 Kg8h8 Bd3xc4 b5xc4 Qe4e2 Kh8g8 Qe2e6+ Kg8g7 Ke1d1 Bd4xc3 b2xc3

Включил запись истории (depth).
Ifrit_j1_4_Beta_26_8_2009:
9/10 00:28 15.508.331 722.898 +1,78 b7b5 Be2d3 Kg8h8 d6d7 Rf5f7 Bd3xc4 b5xc4 Bg3e5+ Bd4xe5 Qe4xe5+
10/12 02:03 23.666.134 249.237 +1,68 b7b5 Be2d3 Kg8h8 Bd3xc4 b5xc4 Qe4e2 Kh8g8 Qe2e6+ Kg8g7 Ke1d1 Bd4xc3 b2xc3

Включил запись истории (1).
Ifrit_j1_4_Beta_26_8_2009:
9/10 00:28 15.567.000 719.861 +1,78 b7b5 Be2d3 Kg8h8 d6d7 Rf5f7 Bd3xc4 b5xc4 Bg3e5+ Bd4xe5 Qe4xe5+
10/12 02:15 25.930.328 242.196 +1,68 b7b5 Be2d3 Kg8h8 Bd3xc4 b5xc4 Qe4e2 Kh8g8 Qe2e6+ Kg8g7 Ke1d1 Bd4xc3 b2xc3


FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

Включил запись истории (1).
Ifrit_j1_4_Beta_26_8_2009:
9/9 00:13 9.872.913 886.178 +0,12 Ng1f3 Ng8f6 e2e3 e7e6 Bf1d3 Bf8d6 00 00 Nb1c3
10/10 01:22 36.201.452 523.240 +0,03 e2e4 Ng8f6 e4e5 Nf6d5 Ng1f3 Nd5f4 Nb1c3 Nb8c6 Nc3e2 Nf4d5

Без истории.
Ifrit_j1_4_Beta_26_8_2009:
9/9 00:11 8.863.088 971.297 +0,12 Ng1f3 Ng8f6 e2e3 e7e6 Bf1d3 Bf8d6 00 00 Nb1c3
10/10 01:10 39.825.148 678.590 +0,03 e2e4 Ng8f6 e4e5 Nf6d5 Ng1f3 Nd5f4 Nb1c3 Nb8c6 Nc3e2 Nf4d5

При включенной сортировке по истории количество позиций уменьшается, но весь эффект съедает уменьшение скорости.
Для альфа-беты в моем исполнении минусы сортировки по истории перевешивают плюсы.

___________________________________________________________________________________
Суббота, 29 августа 2009 г.

Futility pruning решение некоторых задач отодвигает на полуход вглубь. Мне это не нравиться, так что его я пока отключу.

Чистая альфа-бета. Дельта включена.

FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

Без Futility pruning
Ifrit_j1_4_Beta_29_8_2009:
9/9 00:11 8.863.088 969.597 +0,12 Ng1f3 Ng8f6 e2e3 e7e6 Bf1d3 Bf8d6 00 00 Nb1c3
10/10 01:08 39.825.808 698.122 +0,03 e2e4 Ng8f6 e4e5 Nf6d5 Ng1f3 Nd5f4 g2g3 Nf4e6 Bf1c4 d7d5

Используем Futility pruning
Ifrit_j1_4_Beta_29_8_2009:
9/9 00:11 8.813.266 980.995 +0,12 Ng1f3 Ng8f6 e2e3 e7e6 Bf1d3 Bf8d6 00 00 Nb1c3
10/10 01:00 34.147.833 698.891 +0,03 e2e4 Ng8f6 e4e5 Nf6d5 Ng1f3 Nd5f4 g2g3 Nf4e6 Bf1c4 d7d5

Этой эвристикой надо будет основательно заниматься. Пока что на это нет ни времени, ни желания.

Мои реализации сортировки по истории, futility pruning, IID мне не нравятся. Поэтому я их отключил. Вероятно, у меня кривые реализации или я что-то недоделал. Надо будет с ними разбираться. Выпускаю версию в таком виде.

___________________________________________________________________________________


Опубликованная версия Ifrit_j1_4

___________________________________________________________________________________
Вторник, 1 сентября 2009 г.

С хеш-таблицей у меня что-то сильно не то.
В начальной позиции только альфа-бета для глубины 4 на 1036 узлов получаю 8 коллизий. Одна коллизия на 130 позиций!
Это даже не коллизии, а ненайденный ход в этой позиции. А сколько не тех позиций, но в которых все же есть искомый ход?

___________________________________________________________________________________
Среда, 2 сентября 2009 г.

Ясно, что количество узлов недостаточно. Надо знать отношение вхождений в хеш-таблицу к количеству коллизий.
В начальной позиции только альфа-бета для глубины 4:
Записи 578
Вхождения 163
Коллизия 8

Одно вхождение на ~3,5 записей
Одна коллизия на ~20 вхождений и ~72 записей.

Записи - это сколько раз за это время писали в хеш-таблицу.
Вхождения - это сколько раз мы брали данные из таблицы.
Коллизии - это сколько раз ход из таблицы найден не был.

Типичная картина следующая:
depth 3
p_hash_moves[].depth 2
p_hash_moves[].depth_max 3
p_hash_moves[].flag_hash_moves 2
key 3901698933537210451
p_hash_moves[].key 3901698933537210451
p_hash_moves[].move 38277184
Ходящая фигура N(конь)
p_hash_moves[].score_move 7(просто шум)
b1 c3
вид хода 1(простой ход)
Взятая фигура x(взятия нет)
p_list_surplus_moves->end_list= 20(искали в списке из 20 ходов)

В начальной позиции только альфа-бета для глубины 8:
Записи 621372
Вхождения 316398
Коллизия 31474

Одно вхождение на ~2 записей
Одна коллизия на ~10 вхождений и ~20 записей.


Заменил генератор случайных чисел таблицей (на время, в качестве эксперимента).
В результате получил:
Записи 621308
Вхождения 316323
Коллизия 31469

Значит, дело не в плотности случайных чисел.

Для глубины 4 где-то пишем три позиции в одно место.


В начальной позиции только альфа-бета для глубины 7:
256 Мб
Всего в хеш-таблице позиций 8 388 607
Для записей использовали позиций 72 200
Записи 117 797
Вхождения 48 968
Коллизия 3 430

Коэффициент перезаписи 1,6 записей на место. Меня вполне устраивает.
Видно, что для глубины 7 такой объем таблицы явно избыточен.

В начальной позиции только альфа-бета для глубины 4:
Всего позиций 8388607
Для записей использовали позиций 423
Записи 578
Вхождения 163
Коллизия 8

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

___________________________________________________________________________________
Суббота, 5 сентября 2009 г.

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

___________________________________________________________________________________
Воскресенье, 6 сентября 2009 г.
Я действительно утомился отлавливать эти коллизии! Снова вытащил свой шаманский бубен :) Это напоминает времена, когда я писал генератор ходов. Очень занудное и щедрое на сюрпризы занятие. Сейчас заново переписываю функцию, меняющую ключ после хода. Все коллизии обнаруженные до сих пор имеют происхождением неправильное изменение ключа. Все-таки я надеюсь отловить все коллизии. Потом можно будет попытаться использовать оценку таблицы для отсечки. А может быть это и не нужно. Дальше будет видно. В старой хеш-таблице была где-то одна коллизия на двадцать ходов :) На самом деле мой движок совершенно не боится коллизий, так как таблица используется только для поднятия лучшего хода из списка, но все таки неприятно, когда срывается главный вариант и достаточно глубокому поиску приходится заново искать лучший ход. Это дестабилизирует и замедляет перебор. А после того как я отказался от IID, т.е. внутренних итераций, вопрос стал еще острее.

___________________________________________________________________________________
Вторник, 8 сентября 2009 г.

FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

Альфа–бета без киллера
Ifrit_j1_5_Beta_8_9_2009:
8/8 00:04 1.512.119 504.039 0,00 Ng1f3 Ng8f6 e2e3 e7e6 Bf1d3 Bf8d6 00 00
9/9 00:20 14.648.735 898.860 +0,12 Ng1f3 Ng8f6 e2e3 e7e6 Bf1d3 Bf8d6 00 00 Nb1c3
10/10 03:23 116.047.784 634.033 +0,03 e2e4 Ng8f6 e4e5 Nf6d5 Ng1f3 Nd5f4 Nb1c3 Nb8c6 Nc3e2 Nf4d5

Альфа-бета
Ifrit_j1_5_Beta_8_9_2009:
8/8 00:02 923.461 496.484 0,00 Ng1f3 Ng8f6 e2e3 e7e6 Bf1d3 Bf8d6 00 00
9/9 00:11 8.831.658 959.649 +0,12 Ng1f3 Ng8f6 e2e3 e7e6 Bf1d3 Bf8d6 00 00 Nb1c3
10/10 01:16 39.875.518 619.878 +0,03 e2e4 Ng8f6 e4e5 Nf6d5 Ng1f3 Nd5f4 Nb1c3 Nb8c6 Nc3e2 Nf4d5

Смешно что когда хеш-таблица была с коллизиями то результат был лучше
10/10 01:08 39.825.808 698.122 +0,03 e2e4 Ng8f6 e4e5 Nf6d5 Ng1f3 Nd5f4 g2g3 Nf4e6 Bf1c4 d7d5


Сделал использование оценки из хеш-таблицы
Ifrit_j1_5_Beta_8_9_2009:
8/8 00:01 615.976 498.765 0,00 Ng1f3 Ng8f6 e2e3 e7e6 Bf1d3 Bf8d6 00 00
9/9 00:06 4.143.603 858.244 +0,12 Ng1f3 Ng8f6 e2e3 e7e6 Bf1d3 Bf8d6 00 00 Nb1c3
10/11 00:52 29.598.962 640.406 +0,02 e2e4 e7e5 Bf1c4 Bf8c5 Qd1g4 g7g6 Ng1f3 Ng8f6 Qg4g5 Nf6xe4 Qg5xe5+

___________________________________________________________________________________


Опубликованная версия Ifrit_j1_5

___________________________________________________________________________________
Суббота, 12 сентября 2009 г.

Использование оценки из хеш-таблицы дало значительный прирост глубины в эндшпиле. Но как тестировать это использование? И как коллизии в таблице сказываются на игре? Я имею в виду не игру вообще, а моего движка.
Следует еще раз как можно основательнее протестировать поиск.

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

FEN: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

Используем оценку из хеш-таблицы
Ifrit_j1_6_Beta_11_9_2009:
7/7 00:00 270.594 962.967 +0,12 Ng1f3 d7d5 c2c4 d5xc4 Qd1a4+ Qd8d7 Qa4xc4
8/8 00:01 617.865 573.158 0,00 Ng1f3 Ng8f6 e2e3 e7e6 Bf1d3 Bf8d6 00 00
9/9 00:06 4.141.005 895.352 +0,12 Ng1f3 Ng8f6 e2e3 e7e6 Bf1d3 Bf8d6 00 00 Nb1c3
10/11 00:44 27.978.265 739.617 +0,02 e2e4 e7e5 Bf1c4 Bf8c5 Qd1g4 g7g6 Ng1f3 Ng8f6 Qg4g5 Nf6xe4 Qg5xe5+
11/11 03:43 159.687.121 890.241 +0,19 e2e4 d7d5 e4xd5 Qd8xd5 Nb1c3 Qd5e6+ Qd1e2 Nb8c6 Qe2xe6 Bc8xe6 Bf1e2

Проверка последнего варианта показала правильность оценки
1/1 00:00 30 3.000 +0,19 Bf1e2

Не используем оценку из хеш-таблицы
Ifrit_j1_6_Beta_11_9_2009:
7/7 00:00 442.883 1.049.485 +0,12 Ng1f3 d7d5 c2c4 d5xc4 Qd1a4+ Qd8d7 Qa4xc4
8/8 00:02 927.332 570.665 0,00 Ng1f3 Ng8f6 e2e3 e7e6 Bf1d3 Bf8d6 00 00
9/9 00:11 8.829.011 993.027 +0,12 Ng1f3 Ng8f6 e2e3 e7e6 Bf1d3 Bf8d6 00 00 Nb1c3
10/10 01:06 39.951.520 722.502 +0,03 e2e4 Ng8f6 e4e5 Nf6d5 Ng1f3 Nd5f4 Nb1c3 Nb8c6 Nc3e2 Nf4d5
11/11 05:46 276.465.236 987.869 +0,18 e2e4 Nb8c6 Bf1b5 Nc6d4 Bb5c4 b7b5 Ng1e2 Nd4f3+ g2xf3 b5xc4 Nb1c3

Не используем хеш-таблицу
Ifrit_j1_6_Beta_11_9_2009:
7/7 00:01 665.103 925.038 +0,12 Ng1f3 d7d5 e2e3 Bc8g4 Bf1d3 Bg4xf3 Qd1xf3
8/8 00:05 3.518.080 812.865 0,00 Ng1f3 Ng8f6 d2d4 c7c5 d4xc5 Qd8a5+ Qd1d2 Qa5xc5
9/9 00:29 20.965.788 857.391 +0,12 Ng1f3 Ng8f6 d2d4 c7c5 d4xc5 Qd8a5+ Qd1d2 Qa5xc5 Nb1c3
10/10 03:00 119.126.460 791.459 +0,03 e2e4 Ng8f6 e4e5 Nf6d5 Ng1f3 Nd5f4 Nb1c3 Nb8c6 Nc3e2 Nf4d5

При использовании оценки из хеш-таблицы не совпадают ни варианты, ни оценки. Причем этому поиску удалось найти даже большую оценку чем предыдущим! :) Ясно, что где-то закралось возмущение.

В последних случаях оценки совпадают, но не совпадают варианты. Впрочем, они и не обязаны совпадать.
Следует выяснить, что вносит такую нестабильность. Это либо варианты с трехкратными повторами либо delta pruning, либо киллеры.
Буду тестировать дальше. И конечно следует доделать статическую оценку позиции.

___________________________________________________________________________________
Воскресенье, 13 сентября 2009 г.

Отключил варианты с трехкратным повтором.
Выяснил, что отключение повторов картину не изменило. Особенно важно, что таинственная +0,19 осталась. Очевидно, что так быть не может. По оценкам все три случая должны быть одинаковы.

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

Отключил статический поиск, т.е. продления только взятий.
Заметно, что когда оценка так скачет, эффективность хеш-таблицы минимальна. Опять видим несовпадение оценок для поиска с оценкой. Где-то что-то работает неправильно. Будем думать.

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

Провел партию альфа-бета без сортировок против полного перебора. Глубина игры 6 для альфа-беты и 5 для переборщика. Так что видно подтверждается вариант и оценка или нет. Получил полное подтверждение и оценок, и вариантов. Так что в самой альфа-бете вроде бы ошибок нет.
Теперь, если мы включаем форсированный поиск взятий, то картина не меняется. И действительно ведь порядок ходов тот же самый. Какова картина при произвольном порядке ходов, надо еще подумать.
Включенная в альфа-бета хеш-таблица уже меняет несколько линий вариантов, хотя оценки остаются те же.
Хеш-таблица в полном переборе тоже упорядочивает ходы. Так что если ее в нем включить, то опять должны совпадать и оценки и варианты.
Проверил. Действительно совпадают.
Остается вопрос с киллерами и с использованием оценки из хеш-таблицы.

___________________________________________________________________________________
Понедельник, 14 сентября 2009 г.

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

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

___________________________________________________________________________________
Среда, 16 сентября 2009 г.

Исходная позиция
Без использования оценки из хеша 10 полу ходов за 1 39
10/10 01:39 53.101.190 759.271 -1,07 d2d4 c7c6 c2c3 Qd8a5 Qd1d3 b7b6 Bc1d2 Bc8a6 Qd3f3 Ba6xe2
Без отклонений.

Используем оценку 1го типа 10 полу ходов за 1 38
10/10 01:38 53.041.270 769.059 -1,07 d2d4 c7c6 c2c3 Qd8a5 Qd1d3 b7b6 Bc1d2 Bc8a6 Qd3f3 Ba6xe2
При игре за белых отклонений не обнаружил. А вот за черных были отклонения в разные стороны около 0,2 пешки.

Используем оценку 2го типа 10 полу ходов за 1 26
10/10 01:26 61.229.323 923.129 -1,04 e2e3 c7c5 Bf1c4 Qd8a5 c2c3 Ng8f6 Ke1f1 b7b5 Bc4e2 Qa5xc3
Отклонения до 0,4 пешки.

Используем оценку 3го типа 10 полу ходов за 55
10/10 00:55 33.059.076 825.177 -1,07 d2d4 c7c6 c2c3 Qd8a5 Qd1d3 b7b6 Bc1d2 Bc8a6 Qd3f3 Ba6xe2
За белых одно отклонение на 0,03 пешки. За черных без отклонений.

Используем оценку всех типов 10 полу ходов за 43
10/10 00:43 15.082.100 566.804 -1,07 c2c3 e7e6 d2d3 Qd8f6 Qd1d2 Bf8d6 Qd2g5 Bd6xh2 Qg5xf6 Ng8xf6
Отклонения до 0,2 пешки.

Используем оценку 1+3го типа 10 полу ходов за 55
10/10 00:55 33.029.198 822.522 -1,07 d2d4 c7c6 c2c3 Qd8a5 Qd1d3 b7b6 Bc1d2 Bc8a6 Qd3f3 Ba6xe2
За белых одно отклонение на 0,03 пешки. За черных одно отклонение на 0,2 пешки.


Используем оценку 2+3го типа 10 полу ходов за 1 01
Используем оценку1+2го типа 10 полу ходов за 1 07

Оценка первого типа значит, что улучшили альфу или бету.
Оценка второго типа значит, что имеем локальный максимум или минимум.
Оценка третьего типа значит, что имеем отсечение по альфе или бете.

Оценка второго типа может быть не точна ведь возможно, что она найдена в поиске с нулевым окном.

___________________________________________________________________________________
Суббота, 19 сентября 2009 г.

Поиск с нулевым окном стоит обдумать получше.

Посмотрим за белых.
Раньше перерасчет был при условии if((value > alpha) && (value < beta))
Сделал при условии if( value > alpha )

Проверка проводится альфа бета без оценки из хеш-таблицы с перерасчетом при условии if((value > alpha) && (value < beta))

В результате получилось

Исходная позиция
Без использования оценки из хеша 10 полу ходов за 2 58
10/10 02:58 105.853.052 810.166 -1,07 d2d4 c7c6 c2c3 Qd8a5 Qd1d3 b7b6 Bc1d2 Bc8a6 Qd3f3 Ba6xe2
Счет стал дольше на 1 01.
Без отклонений.

Используем оценку 1го типа 10 полу ходов за 2 56
10/10 02:56 105.721.041 821.038 -1,07 d2d4 c7c6 c2c3 Qd8a5 Qd1d3 b7b6 Bc1d2 Bc8a6 Qd3f3 Ba6xe2
Счет стал дольше на 1 мин.
При игре за белых отклонений не обнаружил. А вот за черных были отклонения в разные стороны около 0,2 пешки.
Думаю, что при использовании такой оценки отклонений вообще быть не должно. Непонятно, откуда они берутся.

Используем оценку 2го типа 10 полу ходов за 1 31
10/10 01:31 66.324.834 927.010 -1,03 e2e3 c7c5 Ng1h3 a7a6 Bf1e2 e7e5 Nb1c3 Qd8h4 Nh3g1 Qh4xf2+
Счет стал дольше на 5сек.
Отклонения до 0,6 пешки.

Используем оценку 3го типа 10 полу ходов за 1 19
10/10 01:19 48.674.710 837.414 -1,07 d2d4 c7c6 c2c3 Qd8a5 Qd1d3 b7b6 Bc1d2 Bc8a6 Qd3f3 Ba6xe2
Счет стал дольше на 24сек.
За белых одно отклонение на 0,03 пешки. За черных без отклонений.

Используем оценку 1+3го типа 10 полу ходов за 1 19
10/10 01:19 48.596.484 835.622 -1,07 d2d4 c7c6 c2c3 Qd8a5 Qd1d3 b7b6 Bc1d2 Bc8a6 Qd3f3 Ba6xe2
За белых одно отклонение на 0,03 пешки. За черных одно отклонение на 0,3 пешки.

Используем оценку всех типов 10 полу ходов за 45
10/10 00:45 15.983.369 571.487 -1,07 c2c3 e7e6 d2d3 Qd8f6 Qd1d2 Bf8d6 Qd2g5 Bd6xh2 Qg5xf6 Ng8xf6
Счет стал дольше на 2сек.
При такой игре проверка находит усиление в две пешки. Думаю, возможна и большая цифра.

В итоге мы видим, что пересчет при (value >= beta) совершенно излишен. Думаю, что дело в том, что нам не важна точная оценка, вызывающая отсечку за бету, важен сам факт, что она отсекает. Конечно, такая оценка не точна, но этой точности хватает, что бы принять решение о прекращении поиска.

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

Оценка второго типа не точна, потому что найдена поиском с нулевым окном и пересчета нет.
Оценка третьего типа не точна, потому что найдена поиском с нулевым окном и пересчета нет, кроме того, поиск не был завершен и как правило оценку за противника можно усилить. Так что ее можно использовать только для отсечений.
Оценка первого типа должна быть точна. Потому что был пересчет с полным окном.

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

Остается вопрос, почему при использовании оценок 1 и 3-го типов все-таки есть отклонения. Тут надо думать.

Решил немного переделать поиск с нулевым окном пересчет при повышении локального максимума. Надеюсь, это сделает легитимным использование оценок второго типа.

Без использования оценки из хеша 10 полу ходов
было
10/10 01:39 53.101.190 759.271 -1,07 d2d4 c7c6 c2c3 Qd8a5 Qd1d3 b7b6 Bc1d2 Bc8a6 Qd3f3 Ba6xe2
стало
10/10 01:53 59.701.995 742.358 -1,07 d2d4 c7c6 c2c3 Qd8a5 Qd1d3 b7b6 Bc1d2 Bc8a6 Qd3f3 Ba6xe2

Используем оценку всех типов 10 полу ходов
было
10/10 00:43 15.082.100 566.804 -1,07 c2c3 e7e6 d2d3 Qd8f6 Qd1d2 Bf8d6 Qd2g5 Bd6xh2 Qg5xf6 Ng8xf6
стало
10/10 00:45 15.248.555 547.033 -1,07 c2c3 e7e6 d2d3 Qd8f6 Qd1d2 Bf8d6 Qd2g5 Bd6xh2 Qg5xf6 Ng8xf6
То же самое.

Теперь убрал нулевое окно

Без использования оценки из хеша 10 полу ходов
10/10 03:16 107.784.127 770.486 -1,07 d2d4 c7c6 c2c3 Qd8a5 Qd1d3 b7b6 Bc1d2 Bc8a6 Qd3f3 Ba6xe2

Используем оценку всех типов 10 полу ходов
10/10 01:38 60.349.852 827.072 -1,07 d2d4 c7c6 c2c3 Qd8a5 Qd1d3 b7b6 Bc1d2 Bc8a6 Qd3f3 Ba6xe2
Даже без нулевого окна есть отклонение в 0,02 пешки! Это для меня действительно непонятно.
Если же использование оценки из хеш-таблицы отключить то никаких отклонений.

___________________________________________________________________________________
Четверг, 24 сентября 2009 г.

Начальная позиция. Альфа-бета с использованием оценки из хеш-таблицы.

Без нулевого окна.
10/10 01:41 63.369.817 842.291 -1,07 d2d4 c7c6 c2c3 Qd8a5 Qd1d3 b7b6 Bc1d2 Bc8a6 Qd3f3 Ba6xe2

С нулевым окном.
10/10 00:55 32.511.199 811.501 -1,07 d2d4 c7c6 c2c3 Qd8a5 Qd1d3 b7b6 Bc1d2 Bc8a6 Qd3f3 Ba6xe2

С нулевым окном. Без использования оценки из хеш-таблицы.
10/10 01:40 53.907.224 766.685 -1,07 d2d4 c7c6 c2c3 Qd8a5 Qd1d3 b7b6 Bc1d2 Bc8a6 Qd3f3 Ba6xe2

Таким образом, очевидно, что лучше уж использовать нулевое окно без оценки из кеша, чем без нулевого окна, но с оценкой из кеша.

Все отклонения были связаны с тем, что при улучшении альфы за белых или беты за черных мы пишем вариант, а поэтому не должны использовать оценку из хеш-таблицы, ведь там оценка без варианта.
Все же остальное было правильно.
Итак, мы используем:
Оценку 3-го типа, т.е. при просмотре позиции было отсечение по альфе, при поиске за черных или бете при поиске за белых, то мы можем использовать эту оценку только если она равна или меньше альфы (поиск черных), равна или больше беты (поиск белых)
Оценку 1-го и 2-го типов, если она меньше альфы при поиске за белых или больше беты при поиске за черных.

Посмотреть еще с добавлением остальных эвристик. Что и как влияет.
А дальше заниматься доводкой оценки до стандартного уровня.

Включил просмотр взятий до конца с использованием оценки из хеш-таблицы.
10/10 00:30 15.896.696 656.400 +0,03 e2e4 Ng8f6 e4e5 Nf6d5 Ng1f3 Nd5f4 Nb1c3 Nb8c6 Nc3e2 Nf4d5

___________________________________________________________________________________
Пятница, 25 сентября 2009 г.

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

___________________________________________________________________________________
Воскресенье, 27 сентября 2009 г.

delta pruning порождает отклонения в оценке
Продление на разменах в главной линии порождает отклонения в оценке.
LMR порождает отклонения в оценке.
Нулевой ход порождает отклонения в оценке.

Имеется в виду то, что поиск без сортировки и на меньшей на полуход глубине часто не подтверждает оценку после хода.

Может, они работают не правильно, а может так и должно быть. Сегодня я не могу сказать, насколько правильно они работают.

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

___________________________________________________________________________________
Понедельник, 28 сентября 2009 г.

То, что программа с шахами в статическом поиске видит на глубине в один полуход, программа без шахов видит только на глубине три полухода. Получается разница в два полу хода.
Это заставляет крепко задуматься о шахах в статическом поиске.

___________________________________________________________________________________
Вторник, 29 сентября 2009 г.

Удалил IID из программы. Вдруг ясно понял, что, несмотря на то, что видимо она есть во всех ведущих движках, я не смогу с ней примириться. Я просто кожей чувствую, что она бесполезна в моей программе. В общем если я к ней вернусь, то это будет не скоро и ради такого события можно ее написать по новой. :)
___________________________________________________________________________________

Опубликованная версия Ifrit_j1_6

___________________________________________________________________________________
Среда, 30 сентября 2009 г.

Что дальше?
1. Сделать нормальную статическую оценку позиции.
2. Сделать нормальный детектор ничьих трехкратным повторением.
3. Попробовать в корневом поиске сделать сортировку по уже найденным оценкам ходов. Можно испробовать и другие методы.
4. Протестировать delta pruning. Надо понять, насколько большими бывают отклонения и насколько они портят поиск.
5. Попробовать добавить продление на шахах в статическом поиске.

Это работы месяца на три, не меньше. Учитывая конечно мои темпы.

___________________________________________________________________________________
Суббота, 3 октября 2009 г.

Начал работать надо оценкой.
Начал с того, что подправил код Greko 6,5 (автор Владимир Медведев), так что она полной альфа-бетой считает только материал. Получился хороший контролер тактики.
У Ифрита тоже оставил только материал. Прогнал десятки партий и везде видел совпадения оценки. Это радует, так как значит, что ошибки поиска в этих программах, если есть, то хорошо спрятались.
Тактикой я тут называю последовательность ходов ведущих к выигрышу или потере материала, т.е. как минимум пешки.
Еще раз наглядно увидел, что достижимая глубина поиска не способна компенсировать плохую оценку позиции. Конечно, если бы мы считали до конца, то хватило бы расчета материала. Но эта идея на сегодня безумна.

Вспомним следующие параметры (таблица от WildCat он же Игорь Коршунов):
1. проходные -195
2. ценность полей -173
4. мобильность - 78
3. пешечный щит - 69
5. тяжелые фигуры - 29
6. пешечная структура - 25
7. очередность хода - 18
8. атака на короля - 9
9. паттерны - 0

Элементы, отнимающие силу:

Код: Выделить всё
10. разноцвет - 19

___________________________________________________________________________________
Вторник, 6 октября 2009 г.

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

Сейчас сделал таблицы PST (piece square tables) остается их тщательно протестировать, но уже сейчас очевидна их ограниченность. Только таблицами нормальную оценку не сделать. Ясно, что не обойтись без анализа пешечной структуры и блокированы ли проходные.

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

___________________________________________________________________________________
Суббота, 17 октября 2009 г.

Сделал сортировку по оценкам из предыдущих итераций в корневом поиске (выполнил пункт 3).

Функцию, использующую хеш-таблицу, разделил на две. Одна работает с хеш-оценкой, а другая с хеш- ходом.

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

___________________________________________________________________________________

Опубликованная версия Ifrit_j1_7

___________________________________________________________________________________
Суббота, 24 октября 2009 г.

Что дальше?
1. Сделать нормальный детектор ничьих трехкратным повторением.
2. Попробовать добавить динамическое сокращение глубины перебора для нулевого хода.
3. Модернизировать LMR.
4. Сделать нормальную статическую оценку позиции.

Очередная попытка реализовать поиск стремления(aspiration search), только теперь уже с динамическим окном. Все попытки привели к незначительному увеличению времени счета и к существенному искажению рисунка игры. Идея выглядит заманчиво, но почему-то не работает. Видимо, потому что я и так все выжал поиском в нулевом окне. А может быть, где-то ошибка. В любом случае останавливаться на нем не буду. Может быть, в будущем вернусь, а сейчас и без этого есть что улучшать и тестировать.

___________________________________________________________________________________

Опубликованная версия Ifrit_j1_8
Опубликованная версия Ifrit_j1_9

___________________________________________________________________________________
Среда, 11 ноября 2009 г.

Выполнил еще два пункта:
1. Сделать нормальный детектор ничьих трехкратным повторением.
2. Попробовать добавить динамическое сокращение глубины перебора для нулевого хода.

Что значит пункт 3 «Модернизировать LMR» я уже не помню.
А с оценкой как всегда затормозил :) Почему-то оценка у меня никак не идет.
Но все-таки доделал проходные.

Сейчас занялся просмотром и редактированием кода. Удаляю лишние строки, и все нестыковки, что накопились за прошедшие переделки.
Привожу в соответствие комментарии.
После долгих колебаний удалил сортировку по истории. Она работает во всех движках, в том числе самых сильных. Но почему-то у меня эта сортировка не дает прироста. Действительно количество рассмотренных позиций уменьшается, но выгода от этого съедается потерей в скорости.

У меня очень забавная сортировка корневого списка. Тесты показывают, что, как правило, оценки всех ходов одинаковы. При этом сортировка реально ускоряет счет! К тому же то, что изначально список не инициализирован делает варианты непредсказуемыми, хотя и одинаковыми по оценке. Так в один момент программа может играть e4, а в другой раз захочет d4. Я не сразу понял, что к чему :) Возможно, где то еще есть источники нестабильности. Надо искать.
Конечно, это забавно, но для тестов нежелательно.

Пока редактирую код, запишу, что еще хотелось бы сделать.
1. Таблицу хеш-ключей. Не генерировать их каждый раз заново, а один раз насчитать таблицу и проверить, чтобы не было совпадений.
2. Сделать нормальное распределение времени на счет. Сейчас оно слишком примитивное. Я просто оставшееся время делю на сто. :)
3. Разобраться с инициализацией хеш-таблицы.
4. Разобраться с поведением таймера.

___________________________________________________________________________________

Опубликованная версия Ifrit_j2_0