Ifrit_C

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

на главную страницу

 

Ifrit_C

Ifrit_C История разработки.
часть 1

Часть 2
____________________________________
Четверг, 5 апреля 2007 г.
Видимо, ничего лучше чем альфа отсечение я не придумаю. Именно поэтому код должен быть максимально быстрым. А для этого следует переписать весь перебор, а может, и вообще всю программу заново. Я писал старый код по принципу «лишь бы работало» и программа работает, но слишком медленно.
Конечно, новую программу я буду писать в теле старой. И постепенно заменю все части. Но самое главное – это тщательно продумать всю структуру новой программы, решить в ее рамках основные проблемы старой программы.
Цель заключается в написании как можно более быстрого переборщика.
Затратные места:
1) Мы два раза генерируем одну и ту же позицию. Причем, в каждом новом узле мы копируем целый массив размером 138 целых чисел. Значит, на глубине 5 полуходов мы копируем где то 2 миллиарда целых чисел! Очевидно, что с такими объемами далеко не уедешь. Итак, однозначно от копирования массива доски надо уходить. Это значит, что кроме функции хода нужно делать функцию возврата хода. Тогда мы во время всего перебора работаем только с одной доской! Это конечно здорово и в плане размера. Не надо создавать по двадцать новых массивов доски на каждой глубине, т.е. на глубине 5 это порядка сотни массивов.
2) Правильно ли мы делаем ходы? Правильно ли то что у нас разделены функция хода и правил. По сути, мы выделяем фигуру насчитываем массив возможных ходов, а потом его реализуем. В результате у нас промежуточный массив и множество параллельных циклов. Надо подумать, а нельзя ли их объединить и что это в итоге даст?
3) Нужно ли считать и сортировать все полуходы в каждом узле? Ведь в итоге у нас получается две сортировки списка ходов. Каков процент попадания оценки полухода и дальнейшего уточнения? Насколько вообще верна базовая концепция моего переборщика?
4) Каков вообще самый быстрый доступ к доске? Может, лучше идти не по доске, а по списку фигур?

____________________________________
Воскресенье, 29 апреля 2007 г.
Первое, что следует оптимизировать, это подпрограмму генерации всевозможных перемещений. Она получает на вход позицию и на выходе выдает множество ходов возможных в данной позиции. У меня такая в программе есть, но она еще и оценивает эти ходы. Интерфейс я, очевидно, пока оставлю, а вот внутри все изменю так как мне нужно. Очевидно, что в таком виде из-за внутренних преобразователей данных она может получится даже медленнее начальной, но потом эффект все равно скажется.
Главное сейчас – это понять, в каком виде представлять доску
____________________________________
Пятница, 4 мая 2007 г.
Сердце программы – это не альфа перебор, как я однажды прочитал, а реализация правил. В шахматах главное – это правила. По сути именно они делают шахматы шахматами, и в шахматной программе самое центральное – это блок реализации правил. И так как он вызывается для всего множества ходов, он должен быть максимально эффективен. Жалко, что я так и не смог реализовать битбоард. Пока что остановился на представлении 8 на 16. Модуль возможных ходов получает на вход позицию в виде структуры и выдает список всевозможных ходов тоже в виде структуры. Пока что делаю модуль правил, он получает позицию и имя с координатой фигуры, а выдает список ходов этой фигуры. Ближайшая задача – сделать и встроить модуль правил. Остальное пока оставим за горизонтом и не будем заморачиватся :)
____________________________________
Воскресенье, 6 мая 2007 г.
Ifrit_C6
Подключил новый блок правил. Постоянно вылезают мелкие баги. Они способны довести до сумасшествия :), и это в предварительно отлаженном модуле. Без предварительной отладки разгрести было бы нереально. Сейчас надо будет недельку погонять. Посмотреть что к чему, половить багов :), ну а дальше начинаем переписывать реализатор ходов. Следует еще обдумать перебор позиции.
Написал новые правила. Отличие от старых в том, что используем всего одну координату. Должно ускорить. Входные данные тоже в виде структуры и на выходе список возможных ходов данной фигуры. Необходимо обдумать вид этого списка. В основном, он нужен для реализатора ходов. Без нового реализатора ходов новые правила не дают никакого ускорения – все съедает переходник. Подключил я их только с целью тестирования. На первых порах без копирования доски не обойтись – это пока я буду писать модуль прямых ходов. Ну а потом наступит черед модуля инверсных ходов и тут мы уже будем работать с одной доской без всяких копирований. Это должно ускорить прогу. Очень интересно, даст ли это нам в итоге увеличение глубины хотя бы на один полуход. Кстати, багов больше не заметно, видимо, остались только самые скрытные :)
_____________________________________
Пятница, 18 мая 2007 г.

Считаем из начальной позиции.

Ifrit_C.0.0.2 двухмерная доска 8 на 8 и только прямой ход с копированием массива доски. Чистая альфа-бета.
На 6 глубину за 15 секунд – это 2.411.888 позиций.
160.792 позиций в секунду.
К огромному сожалению на том этапе меня не интересовала скорость и я не могу сказать, что в итоге дало прирост скорости в новой проге по сравнению со старой. Может, в генераторе вообще не прирост, а торможение и общий прирост из-за реализатора или все дело в отказе от копирования массива доски. В общем, сейчас я ничего сказать не могу.

Ifrit_C5 двойная сортировка и оценка в каждом узле, так же альфа-бета отсечение. Каждая позиция генерируется два раза.
На 6 глубину за 37 секунд – это 4.438.697 позиций.
119.964 позиций в секунду.

Ifrit_C6 двойная сортировка и оценка в каждом узле, так же альфа-бета отсечение. Каждая позиция генерируется два раза.
Новый блок правил.
На 6 глубину за 49 секунд – это 4.438.697 позиций.
90.585 позиций в секунду.

Ifrit_C8 полный перебор новый генератор и реализатор ходов. Полный перебор. Это точка отсчета.
На 5 глубину за 19 секунд – это 5.104.320 позиций.
268.648 позиций в секунду.

Без реализатора ходов.
На 5 глубину за 7 секунд – это 3.368.420 позиций.
481.202 позиций в секунду. Прирост в 1.8 раз.

Без оценщика позиций
На 6 глубину за 3 мин. 14 секунд – это 194 секунд, это 126.025.826 позиций.
649.617 позиций в секунду. Прирост в 2.4 раза.

Без реализатора ходов и без оценщика позиций
На 6 глубину за 30 секунд – это 67.368.420 позиций.
2.245.614 позиций в секунду!!! Вот это да! Я такого не ожидал! Прирост в 8 раз.


На 6 глубину за 7 мин. 41 секунд – это 461 секунда, это 126.025.826 позиций.
273.374 позиций в секунду.

По сравнению с самым медленным скорость увеличилась в три раза!

Теперь можно четко сказать что мой метод оценки в каждом узле на один полуход себя не оправдал. Мало того, что он замедлил прогу в два раза, так он еще увеличил количество рассмотренных позиций. И оценка после полухода позволяет сортировать только взятия, а это я могу сделать и так :)
Следует учесть что у меня еще нет детектора шахов. И отсюда недоработки с рокировкой и патом.
_____________________________________
Суббота, 19 мая 2007 г.
Посмотрел скорости ведущих движков в начальной позиции:
Тога считает где то 330.000 позиций в секунду.
Луп считает где то 370.000 позиций в секунду.
Рыбка считает где то 22.000 позиций в секунду.

Становится очевидным, что на современных процах при полном переборе максимальная комфортная глубина
где то 6-8 полуходов. Причем 8 не преодолеть ни какой оптимизацией. Таким образом 4 хода это предел полного пербора.
Очевидно, что для меня потолок 6 полуходов. Таким образом, переход на битбоард и оптимизация скорости не принципиальны. Такие вещи хороши для одинаковых в остальном программ. Нужно четко понимать, что все ухищрения по скорости дадут максимум ход. Мы ведь понимаем, что чтобы считать на полуход больше нужно считать где то в 20 раз быстрее! Итак, оптимизация по скорости вертикального прироста почти не дает даже на супер крутых алгоритмах, а вот горизонтально можно улучшить считать на глубине 6, скажем, не за 7, а 3 минуты, что тоже не плохо.
3 хода это максимум (счет где то минуты 3)
Еще раз следует подчеркнуть вывод о том, что переход на битбоард и полная оптимизация генератора не даст и полухода! Конечно, битбоарды мне очень интересны, но для моей проги сейчас они точно не актуальны. А их введение потребует полного переписывания генератора и реализатора ходов. Хотя, может, именно сейчас и стоит этим заняться, пока еще не поздно. Тем более, что все сильнейшие проги переходят на битбоард.

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

Решено. Битбоарды отложены и главный аргумент цикл 8 на 16 следует завершить! Все описать и написать генератор шахов. Так мы не прервем дугу становления и нам будет с чем сравнивать прогу на битбоарде, если я до нее дойду.
_____________________________________
Четверг, 24 мая 2007 г.

Последняя модификация движка.
Ifrit_C8 полный перебор новый генератор и реализатор ходов. Полный перебор. Это точка отсчета.
На 5 глубину за 22 секунды – это 5.104.320 позиций.
232.014 позиций в секунду.

Очень смешно, как я сделал медленный генератор! А все из за того, что не понял идеи доски 16 на 8. А что бы понять идею этого представления, нужно знать шестнадцатеричное представление. Тогда выход за пределы массива можно проверять всего одной операцией сравнения. !(N&0*88) N-это индекс доски 8 на 16. Я же проверял двумя да еще внутри использовал одну лишнюю проверку :)
_____________________________________
Пятница, 25 мая 2007 г.
Что-то утомил меня этот генератор + реализатор ходов. Он сам по себе получился довольно сложным да еще его тестирование вещь малоприятная. Я его полностью переписывал уже раз десять :) Пока что именно на генераторе фокус моего внимания. А я еще хотел переходить на битбоард! Это уж точно для меня рано. Для начала нужно отшлифовать метод 8 на 16. Генератор на нем более понятен и прозрачен для меня.
Генератор переписал на единственную проверку индекса массива, в результате на 5 глубине выиграл 3 секунды.
Вернулся к тем же самым 19 секундам, что у меня были до полной реализации рокирвки.

_____________________________________
Воскресенье, 27 мая 2007 г.
Генератор ходов дописал. Я думаю, он уже близок к окончательной форме. Мы генерируем все возможные ходы из позиции для того, чтобы потом взятия смотреть первыми, ведь именно они чаще всего вызывают отсечения. Мы записываем тип хода, иначе как нам находить взятия? Все же остальное дело техники. Итак, с генератором возможных ходов я закончил. Теперь нужно понять, почему на глубине 5 вывод варианта временами кривой. И нужно писать генератор шахов. Все остальное в данный момент не актуально.
_____________________________________
Среда, 30 мая 2007 г.
Тестировал прогу на глубине 4. Вывод варианта нормальный. Никаких глюков я не заметил. Попутно сделал интересное наблюдение при четной глубине – прога старается не оставлять фигуры под боем. Это и понятно – она же не видит ответа на взятие. Так что, прога играет пытаясь сделать так, чтобы в конце под боем было как можно меньше фигур и по пути не потерять материал. А на нечетной глубине она наоборот пытается сделать так, чтобы в конце сожрать как можно более крутую фигуру. Еще протестирую прогу на глубине 3 и если и там все будет в норме, то скорее всего дело в переполнении.
На глубине 3 все оказалось в порядке. Усечение массивов не помогло. И что самое интересное – косячный только вариант первого хода, а все остальные идут нормально. Я не могу понять, в чем тут дело.
_____________________________________
Четверг, 31 мая 2007 г.
Нашел, в чем было дело. Дело было в том, что я обновлял всю нитку, а надо начиная с текущей глубины. Теперь прога играет по-другому и вариант выводит красивый. Альфу-бету следует описать и переходить к генератору шахов.
_____________________________________
Суббота, 2 июня 2007 г.
Описание сделал и прогу выложил. Теперь следует вплотную заняться генератором шахов.


_____________________________________
Воскресенье, 3 июня 2007 г.
Сегодня доделал генератор шахов. Теперь рокировка нормальна. Король под шах не ходит. И прога не рубит вражеского короля кода в матовой ситуации. Дальше следует делать форсированные варианты. И надо сортировать взятия. Что делать после этого я не знаю. Но до этого следует тщательно протестировать прогу и сыграть с ней множество партий.

_____________________________________
Вторник, 5 июня 2007 г.
Генератор выдает список ходов. Его размер количество ходов + 1. Так, если мы не насчитали ни одного хода, то размер равен 1. Очевидно – это нелогично. Если ходов нет, то список должен содержать 0. Так и сделаем. Всем этим я озаботился, потому что в случае пата, список выходит пустой и это надо как то обрабатывать. Тут же обнаружил баг с шахом. Пешки-то ходят и рубят по разному :), а в генераторе шахов я это не учел, ведь мы проверяем на битие поле возможного хода короля, т.е. по сути пустое. Пат оцениваем как 0.
Теперь, вроде, реализовал все случаи. По крайней мере, те, что до сих пор приходили мне на ум. А я забыл еще сделать сортировку по взятиям. Думаю, именно этим я и займусь. И дальше надо будет подумать о форсированных вариантах. Видимо, они неизбежны.
_____________________________________
Вторник, 12 июня 2007 г.
Продления на взятиях пока не получается. Зато отловил еще баги. Главное – это тестирование. Очень часто даже абсолютно прозрачный код работает не так, как должен. А в сложных системах мелкие глюки, как правило, не заметны. Исчерпывающего тестирования тоже не получается. Самое правильное – это разбить прогу на модули с обозримыми потоками информации между ними и вести распечатку этой инфы. Причем, можно не постоянно, а только когда нужно. Тестовый пакет должен быть частью модуля. Модуль должен решать задачу, причем, мы на выходе теста должны четко понимать, работает он нормально или где-то глючит.
Сегодня сделал большое дело. Грамотно вывожу тестовую информацию, отсекая в рабочем режиме тестовые функции, с помощью препроцессора. Теперь они не будут влиять на быстродействие и величину кода в рабочем режиме. А с другой стороны позволят мне врубать тестовый режим, изменив всего одну переменную препроцессора. Это надо было сделать давно, но руки как-то не доходили. Так же заново прохожу по логике работы программы, описывая ее в текстовом файле.
_____________________________________
Пятница, 15 июня 2007 г.
Тестировал фен модуль. Все работает на ура. Я брал финальную позицию в базе и заставлял движок ходить в ней. При этом сравнивал позицию, полученную из фен-модуля, с той что на доске. Все совпадает идеально. Если в фен-модуле и есть багги, то они достаточно глубокие. И могут быть во взятии на проходе, в рокировке. Ну и пожалуй все. Похоже, что глубоко скрытые багги в фен-модули почти неуловимы вручную. Их можно будет заметить только, если прога сделает странный ход. Ладно, будем считать, что фен мы протестировали :)
Какая-то ерунда с оценкой в матовой ситуации. Надо будет разбираться.
_____________________________________
Суббота, 16 июня 2007 г.
Целый день провозился с матовыми позициями. Проблема была в том, что движок мат воспринимал как пат и соответственно его оценивал как нулевой. Подключить модуль взятия на проходе – это значит существенно усложнить переборщик и делать его пока рановато. Нужно тестировать и обкатывать текущий переборщик.
_____________________________________
Воскресенье, 17 июня 2007 г.
Вчера обнаружил чудовищный баг. Почему-то белые сбрасывали своего короля. Оказалось, что инвертировать оценку при взятии короля, в зависимости от хода, не нужно. Я так и не понял почему. Надо будет думать. Так же из-за того, что прога не знает шах от короля, она часто загоняет ситуацию в пат своим королем.