Дневник разработчика шахматной программы часть 5

Ifrit

История разработки.

Часть 5

___________________________________________________________________________________________
Среда, 17 сентября 2008 г.
Ifrit_b2_7
Методы futility pruning и late move reductions неожиданно много прибавили к глубине
перебора. Так, если раньше блиц игрался на глубине 7-9, то после их введения 9-12. Мне это
очень понравилось. Проверка на тактику показала решение около 50% процентов позиций. Надо
сказать, что больше всего меня устраивает чистый полный перебор. Но у него есть фатальный
недостаток – безобразно маленькая глубина расчета. Именно поэтому приходится добавлять
разного рода оптимизации и эвристики. Последние две эвристики вообще кажутся мне
подозрительными, но деваться некуда ведь только с ними достигается приемлемая глубина
основного перебора. Что бы выигрывать нужно, видеть тактические удары, а для этого нужна
глубина.
Из эвристик до сих пор не сделал history и еще думаю нужно реализовать IID. В форсированном
поиске тоже бездна для всяких экспериментов.
___________________________________________________________________________________________
Четверг, 18 сентября 2008 г.
Сегодня прочитал свой дневник про разработку Джина. Последняя запись в нем от 5 января 2007
г. Прошло не так уж много времени, а мне кажется, что прошла уже вечность. В Джине ничего
нет, кроме полного перебора и генератора ходов. Причем, даже шаха и мата не было.
Добавление рокировки, взятия на проходе, превращение пешек давалось с колоссальным трудом.
Все шло на грани моих возможностей.
Сейчас пришло в голову, что ведь до сих пор я не обращал внимания, как это сделано в других
программах. Генерация и реализация ходов сделана мною самостоятельно, без всяких
заимствований, как в Джине, так и в Ифрите, а это значит, что там есть что оптимизировать,
и есть что заимствовать из других движков :)
На мой взгляд, между Джином и Ифритом бездна и кажется удивительным, что их отделяет такой
маленький промежуток времени. Это тем более удивительно, если вспомнить что я пишу его
урывками, и очень редко удается работать над ним каждый день в течение недели.
Прошла целая эпоха, и сейчас интересно посмотреть, какие идеи получили развитие.
Должен сказать, что выбор Си++ было очень правильным решением. Это колоссально мощный язык
и Джава на его фоне смотрится не лучше старого Бейсика. С тех пор я полюбил этот язык, хотя
должен признать, что его мощность позволяет создавать чудовищ похлеще Франкенштейна! Я не
утверждаю что Си++ лучше Джавы или Дельфи. Тут решающую роль играет не язык, а уровень
программиста. Но конечно однозначно старый Бейсик на порядок хуже этих трех при написании
движков. А вот зачем вообще нужен новый Бейсик, я не знаю. Он потерял простоту старого
бейсика так, что лучше уж писать на Си++, чем врубаться в этого монстра. Лучшие движки
написаны на Си++, а это значит что это подходящий инструмент :)
С другой стороны, я все еще недоволен читаемостью и прозрачностью кода. Точнее некоторые
места, по-моему, слишком усложнены и хотелось бы их упростить. В первую очередь речь идет о
переборе. Многие места далеки от оптимальности. Но в целом уровень проекта в данный момент
меня устраивает.

Что дальше?
Следует как можно полнее описать текущий уровень. С одной стороны это поможет начинающим, а
с другой я сам смогу увидеть недостатки и то куда двигаться дальше. Описание алгоритмов я
уже начал выкладывать на сайте и продолжу это в дальнейшем.

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

Из новых методов на очереди history, IID, SEE, verification search, razoring. Что добавлять
после этого я не знаю. Кстати, эффективность этих методов для Ифрита тоже под большим
вопросом.

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

В razoring я не верю. По-моему futility pruning хватит выше крыши. Но все равно надо будет
проверить, вдруг меня ждет сюрприз :)

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

Давно уже хочу реализовать history. Думаю, он слегка ускорит перебор.

Еще один интересный метод это SEE. Но его буду добавлять в быстрый поиск вместе с
детектором шахов.

Пока что это все известные мне методы.

___________________________________________________________________________________________
Суббота, 20 сентября 2008 г.
Сегодня еще тестировал IID. Метод функционирует, вот только он мне не помогает из-за того,
что у меня на разных глубинах лучший ход разный. Приведу пример:
1/1 00:00 20 1 +0,29 Nb1c3
2/2 00:00 39 1 0,00 Nb1c3 Nb8c6
3/3 00:00 465 1 +0,29 Nb1c3 Nb8c6 Ng1f3
4/4 00:00 969 1 0,00 Nb1c3 Nb8c6 Ng1f3 Ng8f6
5/5 00:00 13.452 934.063 +0,29 Nb1c3 Nb8c6 e2e4 Ng8f6 Bf1e2
6/6 00:00 55.796 649.000 0,00 d2d4 Ng8f6 Ng1f3 d7d5 Bc1d2 Bc8d7
7/7 00:01 594.900 835.183 +0,47 Ng1f3 d7d5 e2e3 Bc8f5 Bf1e2 Nb8d7 00
8/8 00:07 2.855.595 605.856 -0,08 e2e3 Ng8f6 Bf1b5 e7e6 Ng1f3 Bf8d6 00 00
9/9 00:34 18.807.906 818.937 +0,39 Nb1c3 Ng8f6 Ng1f3 e7e6 e2e4 Bf8b4 Bf1d3 00
00

Видно, что с 6 по 9 глубину все первые ходы разные. По-моему при таком разбросе данный
метод и не должен работать.
Почему же они так скачут? Может у меня в а-б баг? Проверить это проблематично, так как
полный перебор можно посмотреть до глубины 6, а дальше уже завал. Приведем полный перебор
на глубину 6. Видно, что варианты совпадают с а-б.
1/1 00:00 20 1 +0,29 Nb1c3
2/2 00:00 400 1 0,00 Nb1c3 Nb8c6
3/3 00:00 8.902 621.467 +0,29 Nb1c3 Nb8c6 Ng1f3
4/4 00:00 197.281 573.897 0,00 Nb1c3 Nb8c6 Ng1f3 Ng8f6
5/5 00:10 4.865.609 516.098 +0,29 Nb1c3 Nb8c6 e2e4 Ng8f6 Bf1e2
6/6 05:12 119.060.324 411.652 0,00 d2d4 Ng8f6 Ng1f3 d7d5 Bc1d2 Bc8d7

Кстати, только что заметил интересное дело - четные оценки более высокие, чем не четные,
т.е. для позиционного фактора эффект горизонта продолжает работать. Это и понятно – если
последний ход был за мной, противник еще меня не опроверг, и мои фигуры стоят более
выгодно. Для тактики мы эффект горизонта убрали продолжением на взятиях а вот для
позиционности нет.
___________________________________________________________________________________________
Воскресенье, 21 сентября 2008 г.
Продолжил тестирование IID. Все-таки хочется понять, почему он у меня не работает, ведь он
есть почти во всех движках.

Чистая а-б без сортировок:
7/7 00:02 1.866.372 924.124 +0,47 Ng1f3 d7d5 e2e3 Bc8f5 Bf1e2 Nb8d7 00
8/8 00:26 15.305.274 739.296 -0,08 d2d4 Nb8c6 e2e4 Ng8f6 Nb1c3 d7d5 e4xd5
Nf6xd5
9/9 03:04 117.776.781 854.775 +0,37 e2e4 Ng8f6 Nb1c3 e7e6 Bf1b5 c7c6 Bb5e2 d7d5
d2d3

С включенным IID:
7/7 00:02 1.235.168 939.478 +0,47 Ng1f3 d7d5 e2e3 Bc8f5 Bf1e2 Nb8d7 00
8/8 00:13 7.867.339 781.959 -0,06 e2e3 d7d5 c2c4 e7e6 c4xd5 e6xd5 Bf1e2 Bc8d7
9/9 01:20 46.190.892 834.662 +0,37 e2e4 Ng8f6 Nb1c3 e7e6 Bf1b5 c7c6 Bb5e2 d7d5
d2d3

Можно видеть, что ускоряет, где то раза в 2. Надо сказать это очень плохое ускорение.

Простая сортировка взятий + по централизации дает:
7/7 00:01 594.900 818.747 +0,47 Ng1f3 d7d5 e2e3 Bc8f5 Bf1e2 Nb8d7 00
8/8 00:07 2.855.595 604.193 -0,08 e2e3 Ng8f6 Bf1b5 e7e6 Ng1f3 Bf8d6 00 00
9/9 00:34 18.807.906 817.079 +0,39 Nb1c3 Ng8f6 Ng1f3 e7e6 e2e4 Bf8b4 Bf1d3 00
00

А если еще + IID:
7/7 00:01 615.142 832.484 +0,47 Ng1f3 d7d5 e2e3 Bc8f5 Bf1e2 Nb8d7 00
8/8 00:06 2.772.454 615.422 -0,08 e2e3 Ng8f6 Bf1b5 e7e6 Ng1f3 Bf8d6 00 00
9/9 00:37 19.796.627 768.466 +0,37 e2e4 Ng8f6 Nb1c3 e7e6 Bf1b5 c7c6 Bb5e2 d7d5
d2d3

Видно, что эта сортировка тормозит, а не разгоняет!

Для сравнения хеш все-таки слегка разгоняет:
7/7 00:01 488.618 835.887 +0,47 Ng1f3 d7d5 e2e3 Bc8f5 Bf1e2 Nb8d7 00
8/8 00:04 1.375.231 575.231 -0,08 e2e3 Ng8f6 Bf1b5 e7e6 Ng1f3 Bf8d6 00 00
9/9 00:24 13.086.523 763.018 +0,39 Nb1c3 Ng8f6 Ng1f3 e7e6 e2e4 Bf8b4 Bf1d3 00
00

Я думаю, что дело не в том, что метод криво реализован, а в том, что у меня слишком сильно
меняется лучший ход при переходе на следующую глубину. Видимо, все-таки в поиске есть баги.
Например, видно, что лучший вариант на 9 оценивается по-разному, но так быть не может.
Тест полного перебора показывает, что сортировки не теряют и не добавляют ходы.
Что-то не то в форсированном варианте. Когда его отключаю, варианты совпадают, и методика
IID разгоняет поиск.
Есть в нем какая-то нестабильность. Может, так и должно быть из-за статической оценки.

Пригляделся получше к форсировке и что-то она мне показалась непонятной. Похоже, это
главный источник нестабильности, из-за которого не работает IID и при различных сортировках
получается лучший вариант с разными оценками. Тут надо думать.
Форсаж слегка подправил и вроде заработал IID, хоть и слабо.
___________________________________________________________________________________________
Пятница, 26 сентября 2008 г.
Обязательно нужен нормальный детектор ничьих при трехкратном повторе позиций. Из-за
недоработки этого момента движок упускает очень много побед. До сих пор обходил стороной
проблему цугцванга. Тут тоже надо будет доработать
и может быть verification search мне в этом поможет. И, конечно же, обязательно сделать
history. После этого разработку движка первого круга можно будет считать законченной. Над
введением SEE и razoring надо будет хорошо подумать.
Насколько я сейчас себе представляю, если первый круг был debug, т.е. разработка то второй
круг будет beta, т.е. тестирование и шлифовка.
Сейчас при добавлении методов я смотрю, что вроде работает и вроде ускоряет, но полного
тестирования, конечно же, нет.
___________________________________________________________________________________________
Пятница, 10 октября 2008 г.
Запихать в движок все известные методы - это не очень хорошая идея. Так, например razoring,
если и буду добавлять, то в последнюю очередь, когда уже совсем нечего будет улучшать? ну
или ради эксперимента. Я считаю, что иметь razoring в программе, где уже есть futility
pruning и LMR, это верх идиотизма :)
Нормальный детектор трехкратного повторения пока не получается. У меня что-то не то с
генерацией ключа хеш-таблицы. Тут будет очень много тестов и кода, который заметно усложнит
движок. Пока я на это не пойду. Так что это пропускаем.
Остается только history. Надо добавить и оттестировать этот метод. После этого никаких
новых методов добавлять не планирую. Буду доводить и оттачивать то, что есть. Надо будет
написать тесты всех значимых моментов и попытаться реализовать их максимально эффективно.
___________________________________________________________________________________________
Суббота, 8 ноября 2008 г.
После всех оптимизаций генератор работает на скорости 8-10 млн. поз. в сек. Выяснилась
интересная особенность – целого числа не хватает для подсчета позиций при тесте. Так на
глубине 7 в начальной позиции их уже около 3 миллиардов. Раньше это было не актуально, а
сейчас видимо стоит расширить диапазон. Конечно, без знакового числа на конкретный случай
хватит. Но для других и этого мало. В итоге сделал 64-битное целое. Заметил ошибку в Арене.
Она не правильно печатает число на глубине 7. Ифрит выводит 3195901860, а Арена печатает
3.195.900 860. Как 1 превращается в 0 с пробелом для меня непостижимо. Сбоит она и при
выводе скорости перебора. Вещественное число отображает как 1.
Кстати историю я добавил. Честно говоря, ускорения почти не видно, а скорость перебора
упала. Тут надо будет еще думать.
В данный момент я перешел на бета-версию. Теперь только тестируем и оптимизируем методы.
Ничего нового добавлять не буду, так как смысла нет. Сейчас надо довести до ума то, что
есть.
___________________________________________________________________________________________
Пятница, 21 ноября 2008 г.
Появилось желание написать новый генератор. Или майлбукс или магический битбоард. И в том и
в другом случае хочется увеличить скорость и уйти от 64 битных чисел. Действительно ли мне
это сейчас нужно? Нет, конечно. Видимо увеличение скорости раз в 5 даст всего полу ход. А
такого ускорения точно не будет. И даже если бы оно было, это ничего не изменит, так как
другие части программы на порядок медленнее, я имею в виду форсированный поиск и оценку.
Они замедляют перебор с 10 млн. до 200 тысяч. Зачем еще напрягаться с генератором? На
данном этапе это не имеет значения и совершенно не в тему.
Копаться с уклонениями тоже сейчас не нужно. Так что с генератором закончим.
Дальше идет форсированный поиск. Сейчас его надо протестировать и оптимизировать. Может,
стоит перейти на SEE. Еще разобраться с шахами. В общем, действительно нужных дел очень
много.
___________________________________________________________________________________________
Суббота, 6 декабря 2008 г.
В форсированном поиске нашел несколько ляпов. Главный конечно то, что я позиционную оценку
считал в основном поиске, а в форсированном варианте только материал. Так конечно быстро,
но не правильно. Главным образом, потому что позиционные бонусы часто дороже пешки.
Главный вопрос, на который я хотел бы получить ответ как движкам удается так быстро
углубляться. Также стоит сказать, что у меня кошмарная оценка эндшпиля. Ее точно надо
переделывать.
___________________________________________________________________________________________
Воскресенье, 18 января 2009 г.
Выпустил Ифрит 3.5
Давно я уже не писал. Все время уходило на оптимизацию кода. Из эвристик добавил только
дельта прунинг (delta pruning). В остальном тестировал и переписывал. Стоит сказать, что
только форсированные варианты я переписывал раз семь! В результате код получился довольно
взъерошенным, комментарии часто не соответствуют реальности. Надо будет причесывать. Особо
выделил основной вариант (pv) что позволило, наконец, включить продления на разменах и
увеличило стабильность оценки в силу того, что в основном варианте использую только а-б без
других отсечений.
До сих пор не детектирую ничью в возможных вариантах. Нужно еще сделать продление на
единственном ответе. И конечно стоит довести оценку до нормального уровня. Это очевидные
недоработки. Но есть и новые идеи, хотя как они будут работать, и вообще будут ли работать
это большой вопрос.

Дальнейшие планы. Напишу, чтобы самому понять, что же я хочу. :)
Привести в порядок систему тестов. Привести в порядок комментарии. Продолжить описание
эвристик на сайте.
Добавить детектирование ничьих в варианте. Добавить продление на единственном ответе.
Видимо стоит уже задуматься о выводе настроек в таблицу и файл. Также не помешает вывод
нескольких вариантов в режиме анализа.
Насчет уклонения от шахов, о шахах в форсированном варианте и SEE нужно еще думать. А
оптимизация оценки - это вообще тема вечная :)
___________________________________________________________________________________________
Суббота, 31 января 2009 г.
Добавил комментариев. Прокомментировал параметры функций.
___________________________________________________________________________________________
Суббота, 7 февраля 2009 г.
Вызвал функции в цикле 2147483647 и еще внутренний на 20. Оказалось, что глобальная
переменная ужасно тормозит выполнение(40 сек против 0). Тоже самое происходит, если в
локальной переменной ставим префикс static. Они аналогичны.
Инициализация локальной переменной не влияет на скорость. Вызов констант из глобальных
массивов не тормозит. Структура, переданная по ссылке и по значению, не тормозит.
Глобальная структура не тормозит. Это значит, что глобальная переменная завернутая в
структуру перестает тормозить. Глобальный массив не тормозит.
Почему тормозит глобальная переменная? Я не знаю, но это факт.

Превратил все глобальные переменные либо в структуры, либо в массивы. Никакого прироста
скорости нет.
___________________________________________________________________________________________
Суббота, 14 марта 2009 г.
Переделал проект на объектную модель. Вижу, что это был очень правильный шаг. Добавил
распознавание ничьих трехкратным повторением в строке размышления.
В данный момент (Ifrit_j1_1) следует заняться оценкой. Надо сказать, что оценка всегда была
самым слабым местом. Главным образом, потому что возиться с ней мне не интересно.
Тестирование и оптимизация это непрерывный процесс. В данный момент уровень тестов меня
совершенно не устраивает.
___________________________________________________________________________________________
Воскресенье, 15 марта 2009 г.
В игре есть два аспекта. Первый - это глубина перебора. Чем он полнее и глубже, тем более
глубокие и неочевидные тактические удары видит программа. Таким образом, делают все
возможное, чтобы смотреть как можно глубже. Тактическим ударом я называю вариант, при
котором отыгрывается материал.
Нужно понимать основную антиномию. Смотреть надо как можно глубже, но для этого нужно как
можно больше отсекать. Но чем больше отсекаешь, тем больше вероятность, что отсечешь что-то
нужное и пропустишь тактический удар.

Второй аспект - это оценка позиции. Если она кривая, то компенсировать глубиной перебора
проблематично. Без корректной оценки игра будет слабой и глубина перебора тут не поможет. И
так оценка имеет принципиальное значение.

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

Первый этап.
Тестировать начал с самого начала. Это чистый полный перебор. Особенность такая, что на
нечетной глубине оценка завышена. Так как программа видит, что можно взять материал, но не
видит, что он отыгрывается. На четной наоборот занижена, потому что программа не понимает,
что фигура защищена. Это создает дикую слабость и непредсказуемость игры.
И именно здесь видно, что продление взятий до конца абсолютно необходимо.
На этом уровне тестируется генератор позиций. У нас есть позиции с количеством возможных
узлов на фиксированных глубинах. Их легко найти в интернете. Таким образом, мы можем
увидеть, что генератор работает нормально, а это значит, что все узлы (позиции)
сгенерированы.
Далее следует убедиться, что линия варианта, первый ход и оценка соответствуют конечной
позиции.
Думаю, что на данном этапе тест оценки позиции невозможен. О какой позиционной оценке может
идти речь, если программа зевает фигуры? :)
___________________________________________________________________________________________
Воскресенье, 10 мая 2009 г.

Второй этап.
Подключаем продление взятий. Следует проверить правильность линий взятий. И здесь следует
тестировать и оптимизировать оценку позиции. Линию взятий проверил. Вроде все корректно.

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

Оценка, конечно, требует существенной доработки. Сейчас она во многом нелогична. Главным
образом это касается эндшпиля.
___________________________________________________________________________________________
Среда, 13 мая 2009 г.

Третий этап.
Включаем альфа-бета оптимизацию перебора. Здесь следует проверять не только а-б, но и все
сортировки. Так же тут следует проверить футилити (futility pruning). Таким образом, этап
очень обширный.

Придумал метод проверки а-б. А-б играет на глубине 4, а полный перебор на глубине 3. Таким
образом, оценки должны совпадать. Если нет сортировки, то и варианты. А вот если есть
одинаковые сортировки там и там, то нужно думать.
Ну а если сортировки различные, то оценки должны совпадать, а вот варианты не должны.

Однако я заметил расхождения.
Первое было из-за детектора ничьих. Его отключил. Буду тестировать отдельно.
И второе было из-за дельта прунинга в форсированном варианте. Пока тоже отключил. Буду
тестировать отдельно.

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

Несмотря на то, что хеш-таблица и внутренняя итерация относятся к сортировке, они
настолько неопределенны что буду тестировать отдельно после того как удостоверюсь, что а-б
работает.
___________________________________________________________________________________________
Четверг, 14 мая 2009 г.

Продолжил тестирование. Расхождения в оценке нет. В вариантах очень редко (за партию
несколько раз) есть расхождения, но оценка у этих вариантов одинаковая. Я думаю, что так и
должно быть. Из двух одинаковых по оценке вариантов запишется тот, что первый встретился, а
из-за наличия сортировки по истории их порядок не обязан совпадать в а-б и в полном
переборе.
___________________________________________________________________________________________
Суббота, 16 мая 2009 г.

Вывод варианта протестировал. Ошибок не обнаружил.

Погонял партии с другими движками на фиксированной глубине и ясно увидел, какое
колоссальное значение имеют продления на шахах и взятиях. Бывает, что поиск на глубине 3
полуходов, но с продлениями на шахах выигрывает у поиска на 7 полу ходах, но без продлений.

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

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

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

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

Какие вопросы еще остались:
1) форсирование шахов
2) форсирование взятий
3) ничья повторением позиций
4) дельта прунинг
5) футилити прунинг
6) ЛМР

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

Рассмотрим эвристики с точки зрения игры на фиксированной глубине.

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

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

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