Ifrit
Часть 7

 

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

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

_______________________________________________________________________________________________

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

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

_______________________________________________________________________________________________

Четверг, 26 ноября 2009 г.

Вроде бы у меня лмр(LMR) сделан правильно, но он очень много пропускает. Сразу скажу, что это очень классный метод и отказываться от него у меня и в мыслях нет. Просто его нужно доработать. Сразу добавил учет шаха на предыдущей глубине.

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

Как такое возможно? Все дело в том, что программа с продлениями застревает на продлеваемых вариантах и не успевает посмотреть другие

которые возможно лучше. Ситуацию давно описали, как хвост «вытащишь нос увязнет» и наоборот.

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

Редукция нулевого хода 4 в тактике лучше, чем 3. Это, конечно, при чистом нулевом ходе.

Принципиальным является вопрос, нужны ли продления вообще или достаточно только сокращений линий?

_______________________________________________________________________________________________

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

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

_______________________________________________________________________________________________

Понедельник, 30 ноября 2009 г.

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

Кстати об оценке. Она сейчас просто примитивна. Добавление мобильности резко тормозит поиск и, по-моему, совершенно не окупается. Видимо что-то я делаю не так.

Пришло время серьезно заняться распределением времени на поиск. Решил, что в следующей версии будет нормальное распределение времени.

Проблемы и задачи:

1. До сих пор не понятно, что нужно продлевать и насколько.

2. У меня нет уклонения от шахов и поэтому не понятно, как обнаруживать единственный ответ.

3. Не понятно насколько нужно рассмотрение шахов в форсированном поиске.

4. Надо все-таки сделать приличную оценку позиции.

На этом пока, пожалуй, все :)

_______________________________________________________________________________________________

Воскресенье, 13 декабря 2009 г.

Для памяти под хеш-таблицу в 2 мегабайта

Максимальное количество элементов в таблице 52 428

Размер элемента таблицы в байтах 40

Число степени 2 : 32 768

Окончательное количество элементов 32 767

Для памяти под хеш-таблицу в 256 мегабайта

Максимальное количество элементов в таблице 6 710 886

Размер элемента таблицы в байтах 40

Число степени 2 : 4 194 304

Окончательное количество элементов 4 194 303

_______________________________________________________________________________________________

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

_______________________________________________________________________________________________

Суббота, 19 декабря 2009 г.

При использовании оценки не улучающую альфу при включенном нулевом ходе наблюдаю незначительные отклонения в оценке.

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

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

Отключил продления.

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

Лмр очень сильно искажает оценку и варианты.

Может все дело в детекторе повторов.

_______________________________________________________________________________________________

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

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

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

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

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

_______________________________________________________________________________________________

Суббота, 27 февраля 2010 г.

Достаточно давно ничего не писал. Все это время экспериментировал с хеш-таблицей.

Сейчас меня интересует два момента. Первый - это тестирование всех эвристик. И второй - доведение до ума оценки.

_______________________________________________________________________________________________

Пятница, 26 марта 2010 г.

Почему-то когда дело доходит до оценки, все как-то останавливается.

_______________________________________________________________________________________________

Суббота, 10 апреля 2010 г.

Опишу некоторые смутные желания по поводу исходного кода программы:

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

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

Хотелось бы иметь достаточные критерии уровня оптимальности работы этих блоков.

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

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

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

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

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

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

Для пользователей можно все линковать в один файл, так что им все равно.

_______________________________________________________________________________________________

Воскресенье, 11 апреля 2010 г.

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

_______________________________________________________________________________________________

Суббота, 17 апреля 2010 г.

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

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

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

Самое смешное, что те же претензии я могу предъявить любому другому исходному коду движка. Даже Фрукту. :) Конечно, все это на мой взгляд и относительно моего недопонимания.

Как оделить законченное от разрабатываемого и эффективное от излишнего? Все это очень тесно переплетено и это мне не нравиться.

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

И, конечно, стоит переписать оценку.

В целом же стоит все по-новому обдумать.

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

Каждая эвристика должна быть в отдельном модуле, который носит ее имя. Недопустимо размазывание эвристики по нескольким модулям. Также недопустимо присутствие больше одной эвристики в одном модуле.

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

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

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

Каждый уровень должен иметь набор тестов и критерии оценки эффективности его реализации. Для этого нужно использовать описание его функционала и сравнение с подобными реализациями.

Пока что все. Теперь постараюсь привести код в соответствие этим правилам.

_______________________________________________________________________________________________

Воскресенье, 18 апреля 2010 г.

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

Совсем неудивительно, что все это мне не нравилось.

_______________________________________________________________________________________________

Понедельник, 19 апреля 2010 г.

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

_______________________________________________________________________________________________

Суббота, 24 апреля 2010 г.

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

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

_______________________________________________________________________________________________

Воскресенье, 25 апреля 2010 г.

Решил отказаться от классов. Классы заменил пространствами имен. Т.о. структура программы почти не изменилась, а объекты в ней исчезли.

Получается, что я двигаюсь в сторону ассемблера. Вопросы к коду остались. Буду думать.

Сегодня выложил следующую версию.

_______________________________________________________________________________________________

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

_______________________________________________________________________________________________

Вторник, 27 апреля 2010 г.

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

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

Добавлять что-то новое, не выполнив этих требований, не имеет смысла. Даже если новые методы усилят игру, мне это не интересно.

_______________________________________________________________________________________________

Четверг, 29 апреля 2010 г.

Продолжаю обдумывать оптимальную структуру программы.

Каждый функционал должен располагаться в отдельном модуле. Расползание его по проекту недопустимо. Под функционалом я понимаю, например, кэширование ходов, нулевой ход и т.д.

Выше эта мысль звучала так: «Каждая эвристика должна быть в отдельном модуле, который носит ее имя. Недопустимо размазывание эвристики по нескольким модулям. Также недопустимо присутствие больше одной эвристики в одном модуле.»

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

Модули и функции в них должны быть хорошо описаны. К сожалению, пока это не так.

_______________________________________________________________________________________________

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

_______________________________________________________________________________________________

Среда, 5 мая 2010 г.

Пересмотрел всю программу. К сожалению самых главных вопросов так и не решил.

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

Второй задачей является переписать оценку.

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

______________________________________________________________________________________________

Суббота, 8 мая 2010 г.

Все эти дни не прикасался к коду.

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

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

В первую очередь нужно поработать с поиском.

_______________________________________________________________________________________________

Понедельник, 10 мая 2010 г.

Объектно-ориентированное программирование очень сильная техника. Поэтому надо объяснить, почему я отказался от классов.

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

Пространство имен позволило соорудить что-то похожее на абстрактные классы. К тому же это оправдание в пользу Си++. :)

Как тестировать поиск? Как оценивать его эффективность? Это главные вопросы.

_______________________________________________________________________________________________

Вторник, 11 мая 2010 г.

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

_______________________________________________________________________________________________

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

_______________________________________________________________________________________________

Воскресенье, 30 мая 2010 г.

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

Самые главные проблемы - это нормальные комментарии и полное тестирование кода.

Функция поиска слишком сложная. Статическая оценка непонятная, надо переписывать.

Продления на разменах отключил. Отношение к ним у меня неоднозначное. В одних позициях они помогают, а в других мешают.

Дальше буду комментировать, тестировать и исправлять выявленные недоработки.

_______________________________________________________________________________________________

Понедельник, 14 июня 2010 г.

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

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

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

Задачи ясны. Теперь не буду выпускать следующих версий, если не решен хотя бы один пункт.

_______________________________________________________________________________________________

Среда, 16 июня 2010 г.

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

Надо будет добавить внятные описания и на уровне модуля и на уровне функций. Следует добавить описание алгоритма работы функций -

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

Все должно быть максимально просто и понятно.

Особенно меня не устраивает функция поиска. Слишком она наворочена.

Главным вопросом остается, конечно, максимально полное тестирование.

Еще надо будет понять, почему Ифрит играет только на 2100. Что ему мешает дойти хотя бы до 2800.

_______________________________________________________________________________________________

Пятница, 18 июня 2010 г.

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

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

Вероятно, тесты стоит поместить в отдельные тестовые модули. Чтобы они были обозримыми и не смешивались с основными функциями.

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

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

Вопрос тестирования на данный момент все еще для меня неразрешим.

_______________________________________________________________________________________________

Суббота, 19 июня 2010 г.

Максимально просто и протестировано. Плюс полное описание всех функций.

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

Не вижу, как тестировать форсированный поиск.

_______________________________________________________________________________________________

Вторник, 22 июня 2010 г.

Тестирую статический поиск.

В начале просто игра на глубине один с выводом всех ходов. Дальше буду сравнивать с другими движками.

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

_______________________________________________________________________________________________

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

_______________________________________________________________________________________________

Воскресенье, 4 июля 2010 г.

Удалил futility pruning. Эвристика была отключена очень долгое время. Решил убрать, чтобы не мешалась. Когда понадобиться добавлю по новой.

Удалил продления на разменах. Поиск надолго зависал в некоторых позициях, что отрицательно сказывалось на общей картине. Решил обойтись пока без него.

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

Оценку тщательно протестировал. Нашел кучу ошибок. Протестировал статический поиск. Слегка подправил delta pruning.

В оценке очень не хватает атаки на короля. И не хватает мобильности. Надо будет обязательно добавить.

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

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

В остальном вроде нормально. Дальше буду тестировать, и писать комментарии. Ну, это процесс перманентный. :)

_______________________________________________________________________________________________

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

_______________________________________________________________________________________________

Вторник, 13 июля 2010 г.

Переписал распределение времени. Сила игры остается примерно на одном уровне. Это уже неприемлемо. Следующую версию выпущу только в том случае, если она будет примерно на сто пунктов сильнее текущей. Итак, либо следующая версия будет сильнее, либо ее вообще не будет.