Ifrit_C
Часть 1
___________________
Суббота, 6 января 2007 г.
Итак, вчера я начал разработку движка Джин на Си++. Выбор языка продиктован тремя соображениями. Первое – это то, что на джаве невозможно создавать экзешники, а значит, нельзя сделать полноценный уки-движок, который можно было бы подключать к другим оболочкам. В результате пришлось отказаться от джавы. Второе – это то, что синтаксис языков очень похож и я надеюсь на минимальные переделки :). И третье – скорость экзешника. Есть еще один плюс – исходники Тоги и Крафти на си. Может, что и сдеру у них.
Это кошмар! Я не могу передать из функции простейшей строки! Хотя, везде говориться, что строки передаются только по ссылке, у меня они передаются только по значению! :) Это конечно смешно. Страшно представить, что будет, когда я подрублю двухмерные массивы!
___________________
Воскресенье, 7 января 2007 г.
С символами происходит что-то непостижимое для меня, и поэтому от символьных переменных и массивов придется отказаться. Иначе я постоянно буду получать всякие сюрпризы. В дальнейшем в описании функции для определения параметра как массива я буду использовать запись вида:
void problema(int k[]) {
Она позволяет понять, что передается именно массив и нужно помнить, что хоть тут и нет явного описания указателя, это именно указатель и массив всегда передается по ссылке. Кстати от двухмерных массивов в си я точно отказываюсь!!! Иначе будет совсем кошмар. Вместо этого буду использовать свою функцию по приведению двух координат к одной :)
___________________
Понедельник, 8 января 2007 г.
Дела помаленьку идут.
Опишем прогу.
В начале запускается цикл опроса, так что прога реагирует на внешние команды.
Инициализация в общем работает, так что в оболочке движок регистрируется.
Игра начинается с того, что оболочка передает движку позицию и ходы. Позицию я сделал, а ходы нет.
А без этого игры не будет, так что это важная задача, но для ее решения нужно знать правила и иметь генератор позиций. Так что тут надо задавать правила и генератор.
Потом идет команда на старт «go» и движок должен считать, и в конце выдать ход, а также сопроводительную инфу.
Вероятно, инфу можно менять еще не сходив, но не проверял.
Тут проблема с временем, так как мой движок считает только на определенную глубину.
Ну а за старт можно браться только, когда мы будем иметь работающий движок т.е. считающий хотя бы на ход и не раньше!

___________________
Четверг, 11 января 2007 г.
Теперь у нас будет:
0-запрет хода, 1-ход на пустое поле, 2-рокировка, 3-превращение пешки, 4-взятие, 5-взятие на проходе, 6-взятие короля.
Как обычно, сам уже запутался в структуре своей программы. Для прояснения ситуации опишу ее:

1 Genie_main.cpp –здесь стартовая функция. В ней мы работаем с потоками ввода, т.е. организован цикл, слушающий входной поток. Из нее мы обращаемся к
2 Genie_Protokol_UCI.cpp –тут мы обрабатываем команды уки. И в соответствии с ними переходим к модулям
3 Genie_C_FEN.cpp –здесь мы разбираем фен-строку и строку входящих ходов, и из нее мы вызываем
4 Genie_C_Board.cpp – тут мы работаем с одномерным массивом доски так, будто он двухмерный.
4 Genie_C_Move.cpp – тут мы реализуем позицию следующего хода
5 Genie_C_Board.cpp
4 Genie_C_Rules.cpp – тут мы описываем шахматные правила
5 Genie_C_Board.cpp
3 Genie_C_Go.cpp –тут мы разбираем команду старта и запускаем движок, он же использует
4 Genie_C_Loop.cpp –здесь цикл обсчета позиции, из него мы используем
5 Genie_C_Move.cpp
6 Genie_C_Board.cpp
5 Genie_C_Rules.cpp
6 Genie_C_Board.cpp

Дальше нужно сделать перебор на один полуход, разбор команды, старт и дописать ввод позиции через мувики, а также написать оценку. Сделав это, будем отлаживать и комментировать прогу. И пока не будет полной уверенности и прозрачности, а также пока код не станет полностью закомментированным, двигаться дальше смысла нет. Хотя на этом этапе движок будет смешно играть.
___________________
Воскресенье, 14 января 2007 г.
Последние дни интенсивно работал над движком. Кстати я переименовал его в Ifrit. Это сделано для того, чтобы не путать его с проектом на джаве. Движок на один полуход сделан! Теперь буду тестировать. Пока писал, видел много удивительного :), но рассказывать не буду т.к. это уже не актуально. Чувствую, что рекурсия поставит передо мной много проблем. Чтобы понять какие багги были, а какие возникли от рекурсии, я пока погоняю прогу как она есть, посмотрю на ее поведение, ну а потом видно будет.
___________________
Среда, 17 января 2007 г.
Всю неделю возился с движком. В результате он считает полным перебором на 4 полухода. Были глюки с расшифровкой ходов в уки-протоколе. Кое-как понял, в чем дело. Очень помогла арена. В ней можно посмотреть историю обмена сообщениями оболочки и движка. Выявили недоработки в мувиках (ходах, посредством которых получаем из стартовой текущую позицию). Недоработки касаются рокировки и взятия на проходе. Фен-позиция вроде нормально работает.
___________________
Суббота, 20 января 2007 г.
Кажется, я уперся. Для того, чтобы увеличивать глубину перебора, нужно однозначно отказываться от полного перебора. Сейчас глубина 4 полухода, т.е. 2 хода – это 426 тыс. позиций за 13 секунд, т.е. скорость – 35 тыс. поз. в секунду. Учитывая простой оценщик, скорость не впечатляет.
У того же джуниора – целый миллион! Т.е. быстрее в 30 раз. Хотя это для отладочного экзешника, а релиз позиции смотрит за 2 секунды, т.е. скорость 200 тыс. поз в сек! А это уже на уровне. Но даже с такой скоростью максимум можно выжать еще один ход, т.е. сделать на 3 хода. Очевидно, что это не решает проблемы. Сопротивление при углублении для полного перебора растет по экспоненте! Я просто физически чувствую этот информационный взрыв, это колоссальный завал. Итак, дальше придется отказываться от полного перебора. Так 4 полухода – 3 секунды, а 5 уже – 1 минута 20 сек. Понятно, что на глубину 6 считать будет уже минут 20.
Сейчас (версия 001) мы сразу заходим на предельную глубину и начинаем последовательно обходить ветки. Такой алгоритм самый простой и он хорош при полном переборе. Но он совершенно не годится для целенаправленного поиска. Для такого поиска будем применять метод ступенчатого углубления с записью варианта.

___________________
Воскресенье, 21 января 2007 г.
Сегодня наконец реализовал альфа-бета отсечение. Получил еще один полуход. Так что теперь прога считает 5 полуходов в пределах 1-10 секунд и шесть – от 15 секунд до шести, что конечно для такого уровня игры не приемлемо.
Тут же хочется дальше усложнять алгоритм перебора, делать сортировку ходов, что даст, я думаю, еще пару полуходов.
Хочется, но это неправильно. Прога играет, пусть и слабо. Теперь надо не увеличивать силу игры, а довести код до ума, т.е. убрать лишнее, сделать вывод варианта, сделать прием глубины перебора, закомментировать и, наконец, отучить ее жрать короля противника :).
Количество узлов и текущий ход оболочка фрица показывает только, начиная с глубины 6! Ну как это можно понять? Я два часа не мог врубиться, почему у меня не отображается количество просчитанных узлов! Это, конечно, форменная тупость.
Сделал прием глубины варианта. По умолчанию глубина 4. Лишнее убрал. Что считал нужным, закомментировал.

___________________
Суббота, 27 января 2007 г.
Кое-как сделал вывод варианта. Это задача оказалась на грани моих способностей :)) Как запомнить вариант, если у нас полный перебор? Я всю неделю не мог этого понять. Наконец, пошел по тому же пути, по которому я поднимаю оценку позиции. Последним подводным камнем оказалась необходимость объявлять массивы на каждой глубине. Ох уж эта передача по ссылке! Сейчас вывод варианта вроде работает, но тут надо тестировать. И тут же увидел, что моя прога тупит из-за ограниченного горизонта. Взятия нужно считать до конца, но как? Я как-то пробовал, но у меня ничего не получилось. Теперь надо приниматься за короля и не ясно, сколько это у меня займет времени.

___________________
Воскресенье, 4 февраля 2007 г.
Разработка остановилась. Дело в том, что схема по которой мы опускаемся на предельную глубину и прочесываем на ней, совершенно бесперспективна, так что отлаживать ее дальше и приделывать к ней форсированный просмотр не стоит. С другой стороны, альтернатива мне видится довольно смутно. Поэтому все и встало. Тут хотелось бы сделать философское отступление: если стоишь, то стоишь и точно никуда не придешь; а вот если движешься, даже медленно, то цели достигнешь.
Схема видимо будет такая. Смотрим на один полуход и тут же оцениваем позицию. Значит, в конце у нас будет множество оценок позиций и ходов, которые к ним привели. Дальше мы эти оценки сортируем по значимости. Дальше мы уточняем те оценки, которые самые лучшие путем просмотра еще на полуход.
___________________
Четверг, 8 февраля 2007 г.
В основе программы лежит идея. Общая теоретическая схема. И она должна быть описана до реализации. Потом идет воплощение этой идеи в конкретной схеме, ее детальная проработка. И уже потом воплощение ее в конкретной программе, на конкретном языке. До сих пор я подробно комментировал код. И это правильно, но этого не достаточно. Вначале нужно описать общую идею программы и ее схему, а уже потом описывать функции и их интерфейс, либо классы и их интерфейс. Программа на си состоит из модулей содержащей функции. Подключаем вначале модуль и можем пользоваться функциями. Все очень просто и логично.
Общая идея моей проги была такова, что мы опускаемся на предельную расчетную глубину и на ней считаем статическую оценку. Такой подход неприемлем и разрабатывать его дальше смысла нет. Я это понял, и поэтому остановил работу в этом направлении. Сейчас как раз ситуация, когда можно описать общую концепцию, что я и сделаю в отдельном файле.
___________________
Суббота, 10 февраля 2007 г.
Посмотрел описание функций в заголовочных файлах. Описания очень краткие, параметры функций не описаны. Так что, сторонний человек ничего не поймет. Ясное дело, что года я писал эти функции мне было не до полных комментариев. Но сейчас нужно довести это дело до ума. Все равно ничего нового не получается. Просмотр заголовочных файлов ничего не говорит о структуре программы. Это просто наборы функций. Мне очень нравиться, что объявления функций отделены от их реализации. Этого нет в джаве и там это напрягает особенно, если тело нельзя сворачивать. Однозначно можно сказать, что все данные должны проходить через параметры функции. Это строгое требование и оно позволяет избегать сюрпризов и неопределенностей. В этой проге я обхожусь без классов. Мне вполне хватает функций и мне нравиться именно функциональный подход, функции решают задачи. Одна задача – одна функция. В связи с этим осознал, что мы ведь в функциях используем другие функции и это никак не отражено в интерфейсе! Отсюда следует непереносимость многих функций без вникания в их тело. Нужно либо переходить к объектному подходу, либо в заголовке указывать, какие функции или модули нужны для ее работы. Указывать модули проще, а указывать функции информативнее.
То, что из просмотра заголовочных файлов ничего нельзя понять о структуре программы и ее идеи, говорит о том, что нужен файл описания идеи программы и ее структуры. Причем, эти файлы должны идти вместе с исходниками. И программист должен обратить на них внимание и понять, что это такое. Считаю, что при соблюдении всех этих условий, программа станет прозрачной и сторонний программист сходу определит, стоит в нее вникать или нет. И мне самому после долгого перерыва будет не сложно продолжить над ней работу.
___________________
Воскресенье, 11 февраля 2007 г.
Может, ядро программы реализующее полный перебор меня и не устраивает, но реализация протокола уки вполне завершена. Так же и блок правил менять пока не собираюсь. Дальнейшее продвижение застопорилось, значит, будем совершенствовать старый код, доводя его до полной завершенности. И надо, наконец, описать структуру программы!
___________________
Суббота, 17 февраля 2007 г.
Сегодня обозначил буквами a, b и т.д. иерархию модулей. Так что вызов модуля б впервые встречается в модуле а. Так можно будет отличить более ранние модули от более поздних. Все это я делаю в связи с решением задачи о полном описании программы.
___________________
Воскресенье, 4 марта 2007 г.
Конечно, хотелось бы завершенные модули отделить от разрабатываемых. Но вот только как? В принципе, можно их скинуть в отдельную библиотеку, но механизм библиотек кажется слишком сложным для восприятия и тестирования.
Проблему решил довольно просто. Ввел в дерево модулей папки и раскидал по ним модули. Причем, так получилось только в дереве проекта, а на диске файлы как лежали кучей так и лежат. Получилось, как пакеты в джаве, но без лишних заморочек. Эти папки нужны мне только для структурирования множества модулей и не более. Это сделало кучу модулей обозримой, а программу прозрачной для меня. Что в итоге позволит двигаться дальше. Главное – это переписать функцию перебора.
___________________
Пятница, 9 марта 2007 г.
Всю неделю помаленьку делаю программу. Переписываю функцию перебора. Теперь мы будем оценивать позицию на каждом полуходе и сортировать оценки. Один полуход реализован. Теперь следует подключить рекурсию. Раньше мы опускались на предельную глубину и на ней все просматривали. Теперь этот этап в прошлом. Мы будем использовать метод пошагового спуска. Пока что это тоже будет полный перебор, но это уже следующий уровень! Думаю, тут возможно реализовать шах и мат и просматривать форсированные варианты до конца. Что мне не удавалось сделать ранее. А без форсированных продолжений прога в принципе не может нормально оценивать позицию. Ее все время скидывает на полувзятия. Итак, форсированные продолжения обязательны.
___________________
Четверг, 15 марта 2007 г.
Похоже, что вывод варианта в данной версии еще труднее чем в предыдущей. Получилось только на один ход. Это грустно, потому до тех пор пока я не сделаю вывод варианта, дальше движения не будет. Очень похоже, что придется хранить все дерево перебора. Но тут надо еще подумать.
___________________
Пятница, 16 марта 2007 г.
Сегодня очень напрягался с прогой. Целый день не мог понять, почему неправильно адресуется линия перебора.
Оказалось, что я в своей функции работы со списками добавил новую переменную, а индексацию не увеличил. И так получилось, что два одинаковых поля оказались связанными. Да уж, нарочно не придумаешь. И ведь не понятно, что не работает! Еще раз убеждаюсь, что с ростом сложности функции, количество ошибок растет в геометрической прогрессии. Так что сразу написать и отладить сложную структуру невозможно. Ее можно только собрать из уже проверенных более простых кирпичиков. И даже на отладку полученной целостности из проверенных кирпичей уйдет уйма времени и сил.
Тем не менее, вывод варианта все таки был сделан! Теперь прога выводит вариант из-за которого она сделала ход. Пришлось внутри функции перебора использовать двухмерный массив для хранения линий варианта.
Интересно, что часто я не понимаю не только как решать проблему, но и саму проблему не вижу! Так что трудности появляются там, где их и не ждешь и в результате тормозишь на ровном месте.
Кстати, я наплодил такое количество двухмерных массивов, что на глубине 5 уже идет переполнение стека! Конечно, это просто ужас.
___________________
Вторник, 20 марта 2007 г.
Хотел сделать узкий поиск. Когда рассматривается например три самых перспективных продолжения. Но это не сработало. Три очень мало. И случается так, что три самых лучших полухода при уточнении оказываются проигрышными. И действительно прога стремит фигуры в центр, а они там все под боем. Таким образом, эта идея не прошла. Мне приходится не только писать код, но и понимать почему он работает именно так. И тут обычно приходится много думать. Он всегда преподносит сюрпризы, иногда из-за багов, а иногда из-за недомыслия изначальной идеи. Как в случае с идеей узкого луча. Тут стало очевидным, что отбрасывать большинство ходов на основании оценки одного полухода идея более чем дурацкая.
___________________
Четверг, 22 марта 2007 г.
Столкнулся с переполнением стека. Вот уж не ожидал. Пришлось резать двухмерный массив и писать дополнительные функции для работы со строками вариантов. При ограниченных ресурсах это вообще может угробить всю схему. Пока что ограничился 10 полуходами. Хотя, конечно, мне надо бы смотреть форсированные варианты до конца, это в пределе 32 полухода, т.е. 16 ходов. Суть проблемы в том, что идя вниз по ветке, мне неужно во всех узлах этой ветки сохранять варианты ответвлений. Это, конечно, не все дерево и тут количество массивов прибавляется, а не умножается, но и этого хватает, чтобы вызвать переполнение стека. В связи с этим, надо тщательно изучить, что такое стек и от чего зависит его размер, а также, что такое массив и как он хранится в памяти. Главный же вопрос: почему большие массивы вызвают переполнение стека? Самое грустное, что даже передача массива как параметра тоже переполняет стек. Таким образом, в данный момент лимитируют: быстродействие проца, размер стека, размер оперативки. При данной организации программы 11 полуходов – это максимум глубины, с которой я могу поднять вариант. Сейчас у меня 10, но, может, тут будут глюки и придется снижатья на пару полуходов из-за неучтенных утечек. Дальше будет видно. Вобщем, данная схема оказалась слишком расточительной и неэффективной, так что и от нее я не в восторге. Вобщем, у этой схемы я тоже увидел предел, но надо сказать, что она в два раза глубже предыдущей. Там было 4-5 полуходов, а тут – 9-10. В любом случае, возврата к схеме полного прочесывания на предельной глубине не будет. Несмотря на все ее недостатки, данная схема предпочтительней. Она гораздо более гибкая и перспективная. Да в ней приходится помнить гораздо больше информации, но это аналитическая система и тут без этого никак! Нужную информацию ты либо запоминаешь, либо считаешь по-новому. Так, в предыдущей схеме, чтобы посмотреть другой начальный полуход на большей глубине, надо по-новому все считать, так как никакой инфы не сохранилось, а в теперешней мы храним лучшие варианты для всех полуходов, и глубже посмотреть интересный вариант не проблема. Вобщем, уже сейчас ясно, что данная схема не достаточна, но надо из нее выжать все, что возможно. И только доведя ее до ума, переходить к следующей. В любом случае, только поработав с ней, я осознал ее минусы и плюсы. Конечно, грустно, что в очередную стенку я уперся так быстро.
Итак, данную схему не бросать, а довести до конца. Пусть на 10 полуходов, но считать она должна.
___________________
Пятница, 23 марта 2007 г.
В дос-программах дела с памятью обстоят вообще невыносимо (56кб). Проблему переполнения стека можно решить. Теперь я понимаю, что в случае с вариантом это, видимо, не проблема. А вот в случае с доской и списками ходов все может обстоять достаточно грустно. Теперь отлаживаем текущую схему. Как я уже говорил, несмотря на ее кажущиеся недостатки, сейчас ее не переделываю. Это касается как сортировки на каждом полуходе, так и массивов. Структуры пока вводить не буду, хотя уже очевидно, что без них дальнейшее усовершенствование невозможно. Итак, текущая задача сделать данную схему работающей без дальнейших улучшений :).

Текущие недостатки.
В выводе варианта не сделал превращения пешки в фигуру, хотя это не сложно, но вносит дополнительную путаницу. Сделаю позже, кода схема будет отлажена. Пешка превращается только в ферзя. Пока что этого мне хватает выше крыши. Глубина перебора не более 10 полуходов. Идет рокировка под боем и через битые поля. На мат прога рубит чужого короля. Не знает правила трех повторов и пятидесяти полуходов. Может принимать глубину до 9 полуходов, 10 воспринимает как 1.
___________________
Суббота, 24 марта 2007 г.
С форсированными взятиями очень сильно пролетел. И действительно – вариант, где игрок обязан брать фигуры никуда не годится и глубина значения не имеет. Простой пример, когда защищенная пешка подставляется под ферзя, игрок обязан бить и потерять ферзя и конечно же этот вариант будет оценен как лучший :). Очевидно, что должна быть альтернатива взятию. Так что должно быть как минимум два продолжения. И еще очень важный момент – при ограниченной глубине перебора и ограниченном количестве линий вариантов, глубина должна быть четной, чтобы видеть ответ противника на взятие.
___________________
Понедельник, 26 марта 2007 г.
Все варианты форсированных взятий оказались неработающими. Остался только один нормальный метод оптимизации – это альфа бета отсечение. Реализую его, и на этом пока остановлюсь.
___________________
Среда, 28 марта 2007 г.
Метод альфа бета реализовал. Он работает, но ускоряет перебор недостаточно. Так на 4 полухода тратятся буквально секунды, но вот 5 полуходов уже больше – минуты 1-3. А на 6 играть проблематично, ждать по пять минут при такой силе игры, это конечно смешно. Итак, все дело в глубине перебора максимум 3 хода :). Использование перебора только взятий не прокатило, получились поддавки. Ограничить глубину 2-3 тоже часто не проходит, так как в позиции может быть множество взятий, скажем, когда в середине ферзь. В данный момент не будем искать других отсечений. Оставим только альфа бету. Дальше надо сделать детектор шахов, чтобы прога не рокировала под боем и видела шах и мат. Сделав это, можно будет считать предварительный этап законченным. Дальше будем оптимизировать различные части проги и искать наиболее эффективные способы отсечения ненужных веток.
___________________
Среда, 28 марта 2007 г.
Сделал так, что прога больше не нападает на чужого короля в матовой ситуации. Теперь надо сделать, чтобы прога не рокировала под шахом и через битые поля. Сделав это, я впервые буду считать, что программа минимум реализована.
___________________
Суббота, 31 марта 2007 г.
Когда закончу рокировку, программа станет полной. Но она получилась очень медленной. Считает на 4-6 полуходов. Это конечно не очень хорошо, и она требует оптимизации.
___________________
Воскресенье, 1 апреля 2007 г.
Сегодня оценивал количество просмотренных узлов на глубине и скорость счета. Также сравнивал ее со старой прогой. Краткий вывод в том, что новая прога не такая тормозная, как я думал. Средняя скорость где-то 110 тысяч узлов(позиций) в секунду – у новой и 140 тысяч узлов(позиций) в секунду – у старой. Увидел, что альфа отсечение очень эффективно.
Depth 5 1 ход ;
5.104.320 ** 166.628 за 45 ** 2 секунд скорость 113.429 ** 83.314 узлов в секунду
10.567.221 ** 538.442 за 92 ** 5 секунд скорость 114.861 ** 107.688 узлов в секунду
5 Миллионов без отсечения и 166 тысяч с отсечением, т.е. практически корень квадратный!

Чувствую, что даже если я оптимизирую код, смогу выиграть еще один полуход и не более. Т.е. у такого алгоритма предел где-то 6~7 полуходов на очень мощном проце. Это значит, что если сейчас комфортно можно играть на глубине 2 хода и терпимо на 2,5 хода, то при оптимизации быстродействия глубина увеличится до 3 и максимум 3,5 ходов.
Очевидно, что это не очень большой стимул для начала поистине гигантской работы по оптимизации движка.
___________________
Четверг, 5 апреля 2007 г.
Видимо, ничего лучше чем альфа отсечение я не придумаю. Именно поэтому код должен быть максимально быстрым. А для этого следует переписать весь перебор, а может и вообще всю программу заново. Я писал старый код по принципу «лишь бы работало» и программа работает, но слишком медленно.
Конечно, новую программу я буду писать в теле старой. И постепенно заменю все части. Но самое главное это тщательно продумать всю структуру новой программы, решить в ее рамках основные проблемы старой программы.

Мы два раза генерируем одну и ту же позицию. Причем, в каждом новом узле мы копируем целый массив размером 138 целых чисел. Значит, на глубине 5 полуходов мы копируем где-то миллиард целых чисел! Очевидно, что с такими объемами далеко не уедешь.