|
Ifrit_C
Ifrit_C История разработки.
часть 2
Часть 3
______________________________________________________________________________________________
Вторник, 19 июня 2007 г.
Сделал так, чтобы король не только не ходил под шах, но и не рубил под шах. Этим мы исключаем случаи, когда загнанный в угол король рубил
защищенную атакующую фигуру, в результате движок считал, что поставил мат, но так как рубить под шах нельзя, то это был пат.
Дальше надо сделать переменную длину варианта, а то при мате появляется некорректный хвост.
______________________________________________________________________________________________
Среда, 20 июня 2007 г.
В одной определенной позиции на глубине 6
rn2kb1r/p3pppp/2pq1n2/8/Np1P3N/8/PPQ1BPPP/R1B1R1K1 b kq - 0 11
Ифрит сбрасывает ферзя «за просто так». Думаю, дело в варианте, что там глючит, а может и в сортировке. В общем, пока для меня это тайна,
борюсь я с этим как истинный шаман ввожу cout.flush(); перед сортировкой смотрите код :))
Дальше еще интереснее – перестал печатать глубину, глюки исчезли, начал печатать – вновь появились!
Убрал пару лишних массивов и, вроде, глюки пока исчезли. Видимо, все дело в переполнении стека. Вот им мы дальше и займемся. Стек, конечно,
не переполняется наглухо, иначе вылезла бы критическая ошибка, но, видимо, уже плещется возле края :)
______________________________________________________________________________________________
Пятница, 29 июня 2007 г. (ночью)
Возился со стеком
int = 32 bit = 4bytes
массив количество итераций размер стека
1 4647 18 588 bytes
10 3569 142 760
100 906 362 400
1000 244 976 000
10000 25 1 000 000
100000 2 800 000
10 * 100 240 960 000
Если же по ссылке:
4 819 и для вызова m[100] и для m[10][100]
вызывается даже больше, чем если бы инициализировали массив m[1] !
300*5 = 1500 элементов на каждом уровне для дерева 6000 bytes ~ 6kb :)
______________________________________________________________________________________________
Пятница, 29 июня 2007 г.
Поэкспериментировал со стеком. Теперь мне все ясно. Размер стека по умолчанию 1мб и этого более чем достаточно, если мы работаем
с указателями. Но я же создавал в нем массивы! Тут меня подвел опыт джавы. Я привык не пользоваться глобальными переменными,
а тут они нужны, иначе забиваем стек. Вопрос только в том, насколько это замедлит прогу.
Доска у меня 128*4 = 512 байт + 512 байт +7*4=28 – итого 1,05 килобайт, что для стека размером в мегабайт вообще
ничтожно мало.
Но, конечно, дерево перебора из таких досок в стеке лучше не строить :)
Сейчас у меня дерево на одном уровне имеет размер:
300*5*4 =6000 + 6*4=24 и того ~ 6 килобайт
Если смотрим на глубину 30, то нужно 6*30= 180 килобайт.
А на глубину 6 вообще 36 килобайт! Ну и где тут переполнение стека?
Критично для нас где-то 870 кб.
Линия варианта вообще 52*4= 208 байт * 30 = 6,3 кб.
6*164=984 кб 16 кб на все структуры?
Итак, то, что массивы объединены в структуры, на размер почти не влияет.
______________________________________________________________________________________________
Вторник, 10 июля 2007 г.
Надо осмыслить множество проблем связанных с генератором ходов.
Мы пытаемся сделать генератор максимально быстрым.
Тогда понятно, что проверку на шах в нем мы делать не должны.
Почему так?
Дело в том, что гораздо дешевле сгенерировать некорректную рокировку или ход королем, чем ради корректности
проверять все ходы на шах. Мы используем отсечение и поэтому глупо тратить время на проверку того, что нам не пригодится.
Правда называть его надо не «генератор возможных ходов», а «генератор предварительных ходов».
Отличительная черта этого генератора в том, что он выдает список ходов и не меняет позицию на доске. В результате он дает избыточные,
т.е. некорректные ходы королем и рокировки. Но это гораздо дешевле, чем вызывать детектор шахов. И кроме того, без трансформации доски
не поможет даже детектор. Из этого следует, что отсеивание данного рода ходов – это не уровень генератора, а уровень реализатора ходов.
Этот подход можно сделать более эффективным путем ввода сортировки предварительных ходов. Сейчас, в первую очередь, рассматриваю взятия,
но можно придумать и другие критерии.
Итак, в итоге генератор шахов перемещаю на уровень реализатора ходов и там ему самое место :)
______________________________________________________________________________________________
Среда, 11 июля 2007 г.
Причем, детектор шахов – это отдельный модуль. Он не встроен ни в генератор, ни в реализатор ходов. Он просто проверяет позицию на
легальность после сделанного хода. И, если позиция не легальна, то отменяет ход и возвращает все на свои места. После реализации
этого модуля программа впервые станет полностью легальной.
Дальше будем бороться с переполнением стека и продлением на взятиях и шахах. А также с различными багами.
______________________________________________________________________________________________
Пятница, 13 июля 2007 г.
Сделал детектор шахов и битое поле при рокировке. Из начальной позиции прога проходит тест до глубины 6 дальше не могу, потому что
будет считать около 10 часов. А вот тест на превращения и рокировку не проходит. Что-то с рокировкой не то.
______________________________________________________________________________________________
Суббота, 14 июля 2007 г.
С рокировкой все было нормально, просто там печаталось количество позиций на уровне, а у меня полное количество. А я два часа не мог
понять, что такое. Сделал полные превращения пешек внутри перебора. Тест проходит до глубины 5, дальше ждать долго. А вот в другой
тестовой позиции
(FEN-string: r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1) у меня не сходится на глубине 4, должно быть 4185552,
а у меня 4185557 – разница в 5 лишних позициях.
______________________________________________________________________________________________
Воскресенье, 15 июля 2007 г.
На данный момент для меня прояснилось несколько моментов:
1. Генератор ходов должен быть максимально быстрым, так как он генерирует все ходы, дальше же часть ходов отсекается. Именно поэтому в
нем нет детектора шаха. Очевидно, что часть ходов генерируемых им являются некорректными. Это касается рокировки и позиций где король
под боем. Генератор ходов выдает список избыточных ходов. Генератор работает с позицией как она есть и не двигает фигуры.
2. Реализатор ходов делает ход из списка ходов. Он делает как прямые ходы, так и возврат хода. Большим вопросом является то, куда надо
записывать промежуточную информацию для возврата хода. Сейчас я ее записываю в список избыточных ходов, но думаю, что это неправильно.
Уже сейчас эта информация не на каждый узел, а одна на уровень.
Тут надо думать, так же как надо думать о том, в каком виде подавать информацию о ходе.
3. Детектор шахов проверяет позицию выданную реализатором ходов. Если позиция не корректна, то об этом сообщается и реализатор
возвращает ход. На данный момент детектор состоит из нескольких функиций и смотрит отдельно атаку на короля, и битые поля при шахе.
Сейчас детектор очень тормозной. Его обязательно нужно будет
переписывать. Но даже такой он подтвердил работоспособность главной идеи.
4. Генератор вариантов. Сказать по другому – это просто переборщик позиций. В нем главная проблема – это запись варианта. В каком виде
его записывать и как отследить его корректность – вот главные проблемы тут. На данный момент в нем используется полный перебор с
альфа-бета отсечением. Конечно, на таком уровне сильной игры получить нельзя. Но на данный момент это не является текущей задачей,
так что элементарная а-б будет еще очень долго.
5. Оценщик позиций. Это очень важная часть программы, но до нее руки никак не доходят и еще долго не дойдут. Но надо сказать, что
с оценщиком я буду работать раньше чем с а-б и раньше чем с форсированным поиском.
6. Вообще форсированный поиск для меня очень трудная тема. Настолько, что до сих пор я не сделал ни одного рабочего варианта,
хотя пытался его сделать. За него нужно браться тогда, когда в основной части делать будет нечего, но это будет еще очень не скоро.
Самое же грустное то, что без него программа будет играть слабо из за эффекта горизонта.
Сейчас пока нужно остановиться и не писать новых структур и функций. Сейчас надо заняться любимым делом, а именно, оптимизировать код,
писать комментарии и тестировать. Главные клиенты тут – реализатор ходов и детектор шахов.
______________________________________________________________________________________________
Вторник, 17 июля 2007 г.
Вчера сделал шах кратчайшим путем. Продолжаю шлифовать код. Убрал лишний массив из дерева перебора, привел в соответствие кодировку цвета
хода и цвета фигур. По плану вначале оптимизирую генератор ходов, потом –реализатор ходов, а потом переписываю детектор шахов, дальше
оптимизируем переборщик, дальше делаем вывод превращения пешки в варианте и вообще обдумать выводы вариантов.
Перевел все переменные, где только можно, на char. Вроде, стало быстрее работать, но в любом случае целое 4 байта а символьное всего 1.
Меньше уже невозможно.
______________________________________________________________________________________________
Воскресенье, 22 июля 2007 г.
Использование char оказалось не корректным, поэтому перешел на short int. Переписал детектор шахов – теперь он заметно быстрее и проще.
Дальше его трогать пока не буду. Сделал вывод фигуры в которую превращается пешка.
Замучился искать ошибку, связанную с взятием ладьи пешкой с превращением. Теперь все тесты прога проходит. Это конечно не значит, что в
ней нет багов, конечно, есть, но я о них пока не знаю.
Сила игры проги очень низка. Перебор на шесть полуходов – это очень мало. Очевидно что взятия она должна считать глубоко или до конца. В
общем на очереди форсированный перебор. Ну и еще поработать с оценочной функцией.
______________________________________________________________________________________________
Четверг, 13 сентября 2007 г.
Форсированный перебор очень тормозит основной. Можно сказать, что я не ожидал такого падения производительности основного перебора.
Так, мне пришлось с 6 полуходов спрыгнуть на 5. И все равно перебор существенно замедлился. Уже можно говорить, что полный перебор
на 6 полуходов плюс форсированный поиск взятий себя не оправдал. К тому же, я не могу форсировано смотреть шахи, так как проверка
на шах у меня идет уже после того как я сходил.
Сейчас следует оттачивать оценку. Думаю, в итоге получу существенное замедление перебора, но тут деваться некуда.
Кроме того, следует ввести правило трех повторений. А также сделать выход из поиска в любое время.
______________________________________________________________________________________________
Суббота, 15 сентября 2007 г.
Сегодня после некоторого перерыва посмотрел свой код и очень четко понял, что комментариев не достаточно. Какими бы подробными
комментарии не были, они описывают подробности реализации. И даже если они описывают функциональность функций :), как правило,
они разбросаны и общей картины не дают.
Вобщем то это было понятно и раньше, просто сейчас я решил действовать в этом направлении. Нужно сделать описание программы на
уровне идеи, а не реализации. Причем, настолько подробно, чтобы сторонний человек мог бы, почитав это описание, реализовать его
на любом языке. Понимание идеи не должно требовать знакомства с исходниками. Но вот, читая описание, мы должны иметь возможность
легко переходить к примерам реализации.
Набросаю план дальнейших работ:
- сделать выход из перебора в любой момент;
- реализовать правило трех повторов позиции;
- сделать описание структуры программы;
- доработать оценку позиции.
Что делать с форсированными продолжениями я не знаю. С одной стороны они необходимы. С другой – их реализация в нынешнем виде –
это источник трудно уловимых багов, неоправданных тормозов и излишнего усложнения программы. При полном переборе форсированные
продолжения себя не оправдывают. Более того – они делают игру не устойчивой и временами непонятной. В итоге, я решил окончательно
от форсирования не отказываться, но плотно им займусь после того как выполню вышеописанный план работ.
Реализация этого плана не увеличит силу программы и это очень грустно. Разве что уменьшит количество ничьих.
______________________________________________________________________________________________
Вторник, 25 сентября 2007 г.
Программу первого уровня я завершил. Ничего нового в прогу я больше добавлять не буду. Теперь нужно поработать с оценкой и отладить
тестовые функции и решения. Я понимаю, что на данном этапе она очень слабая и современным движкам не соперник. Тем не менее, при форе
в ферзя она уже сейчас делает всех в том числе и Рыбку! Это наглядно показывает, что ферзь очень мощная фигура, а с другой стороны
понимаешь, что может разрыв не так уж и велик.
Выход из перебора сделал. Решение подсказали на форуме Креста. Очень грамотно и быстро. Именно поэтому я и люблю иметь дело с
профессионалами.
Правило трех повторов сделал. Правда прога ведется уже на один повтор с ее и со стороны противника, но пока этого вроде хватает,
так что углублять не буду.
Описывать логику функционирования начал. Попутно приведу в порядок комментарии в программе и причешу код. Ну это, понятно, займет
очень много времени. И делается это параллельно с другими работами.
Теперь я занялся самым интересным – оценкой программы.
И сразу понял, что прерывание варианта при взятой фигуре – это неприемлемо. Она легко может отдать (и отдает) фигуру в случаях,
когда она всегда отступает под бой. И тут уже она не видит, что фигура-то прикрыта.
Нулевая оценка – это просто просчет материала. Если прога не видит тактики, то она просто бегает фигурой туда сюда.
И когда она играет с моей прогой с более продвинутой оценкой, которая учитывает позиционный фактор, то у нее шансов нет. Это уже
проверенно. Теперь битва моих прог – это битва их оценок.
______________________________________________________________________________________________
Суббота, 29 сентября 2007 г.
Итак, очевидно, что прерывать вариант на взятой фигуре нельзя. Но и удлинять основной перебор мы не можем. Это значит, что мы в
обязательном порядке используем форсированный поиск.
______________________________________________________________________________________________
Воскресенье, 7 октября 2007 г.
Продолжаю упорядочивать тестовые блоки и описывать программу. На текущий момент вопросы вызывают модуль шаха, модуль форсированного
варианта и модуль перебора. Модуль ходов я, видимо, недостаточно описал. Надо будет к нему вернуться.
Функция Alpha_beta_816 слишком сложная и с этим надо что то делать!
Она у меня получилась просто необозримой! Такого безобразия у меня нет больше нигде!
Глаз блуждает и логики не видно. Понятно, что при таком беспорядке о дальнейшем развитии речи не заходит
и появляется сомнение в точности работы этого нагромождения. В связи с этим у меня и возникли вопросы о тестировании и описании программы.
______________________________________________________________________________________________
Суббота, 13 октября 2007 г.
Сделал тестовую функцию. Автоматизировал тесты для полного перебора. Для этого изменил альфа-бета. Также продолжил все комментировать и
реструктуризировал функцию перебора. Дальше надо заняться форсированным поиском и оценкой позиции. Ну и обдумать, как же тестировать
вывод варианта, как проверить, что варианты выдаются правильно.
______________________________________________________________________________________________
Четверг, 25 октября 2007 г.
Я хотел уже заняться итерационным углублением. Идеи у меня уже есть. Но не тут то было. Текущая 21 версия выдает такие перлы, что
говорить о дальнейшем продвижении не приходится. Следует разгрести текущие баги.
Я до сих пор не знаю, как тестировать линию варианта, оценку и альфа-бета отсечение. Как узнать, что считается именно то и выводится
то, что посчитано.
Варианты выдаются неправильно! Получается так, что у одного и того же варианта разные оценки! Почему так я уже понял. Я вывожу
оценку не лучшего варианта, а текущего. Исправил. Теперь вариант и оценка согласованы. Нужно поиграть, но и сейчас я знаю, что
иногда он делает довольно странные ходы. Будем разбираться. Пока я думаю, что это из-за форсированных вариантов.
______________________________________________________________________________________________
Понедельник, 29 октября 2007 г.
Теперь переменные я пишу со строчных букв. Начинаться с заглавных у меня будут только шаблоны и функции. Конечно это не значит,
что я брошусь все переписывать, но в дальнейшем намерен придерживаться этого правила. Опять заново переписал альфа-бета. Старая
работала правильно, но в ней ей свои приколы. Я реализовал наиболее прозрачную схему. Количество узлов при этом не изменилось.
Т.е., что при старой, что при новой – одинаково. Форсированный вариант переписал, но он еще не прозрачный. Надо еще много тестировать.
______________________________________________________________________________________________
Четверг, 22 ноября 2007 г.
Что-то я забросил ведение истории. И очень зря, потому что произошло много интересных событий и было решено много интересных проблем.
Тут надо будет описать предыдущие события.
--------------------
Добавил блиц-контроль. Правда довольно кривой (в смысле распределения времени на ход ), но на данном этапе это не имеет значения.
Добавил форсировку. Теперь у нас не только продолжается цепочка взятий, но и начинается, если при окончании основного перебора фигура
находится под боем.
Программа играет устойчиво. Но вчера неожиданно наткнулся на проблему. При попытке сделать форсирование на шахах программа стала
вылетать и говорить о переполнении стека.
С этого и начался полный развал проги. Так что, текущая версия совершенно не работоспособна! Сделаю глобальные списки избыточных
ходов, чтобы они не переполняли стек.
--------------------
Еще вчера я обнаружил, что тестовая функция (которая в автомате тестирует полный перебор) не работает. Я очень долго не мог понять,
в чем дело. И только сегодня разобрался. Дело в том, что функция strtok меняет входящую строку. В результате массив глубин в тестовой
функции оказывается искореженным. Это еще раз меня убеждает в том, что те строки и массивы, которые не должны меняться, нужно описывать
как константы. Это должно стать непререкаемым правилом. И, конечно, переменные должны передаваться по ссылке только в том случае, если
мы их меняем!
______________________________________________________________________________________________
Суббота, 24 ноября 2007 г. (ночью)
На данный момент переполнение стека является самой большой проблемой для меня. Я думал, что решу проблему создав глобальную структуру,
содержащую нужные массивы. Но получилось гораздо хуже, чем было. Самое же главное – переполнение осталось. К нему добавились сильные тормоза.
Сейчас я не понимаю, как же люди организуют хеширование на сотни мегабайт! Значит, технология есть, только я делаю что-то совсем не то!
Со стеком нужно разбираться по-новому. Впрочем, я помню выводы от 29 июня 2007 г. Но, похоже, что в случае структур они не работают, либо
я чего-то не учитываю.
______________________________________________________________________________________________
Суббота, 24 ноября 2007 г.
Понял, в чем дело. Массивы всегда передаются по ссылке, а вот структуры – нет. А так как у меня массивы были в составе структуры, то
получалось, что я в стек их копировал. Теперь переполнения стека из-за списка ходов не будет.
______________________________________________________________________________________________
Вторник, 27 ноября 2007 г.
Обнаружил списки ходов в функции оценки! И после этого я удивлялся, что у меня переполнялся стек! Сам их натыкал повсюду. Сейчас, когда
у меня структура глобальная, я пытаюсь сделать ее максимально большой и смотреть, где еще возникают переполнения. Скорее всего, я ее
глобальной не оставлю, но за эти дни увидел много интересного :)
Прога играла медленно – и не спроста! Я-то думал – это глобальные списки виноваты, а я просто не включил альфа-бета отсечение :)
|