|
||
|
10.12.2006 And_chess_K- Предлагаю вашему вниманию шахматную
программу, написанную на языке Java. С самого
начала обращаю ваше внимание на то, что в программе нет шаха, мата и
инверсии доски, а кроме того - она легко бьет чужого короля и отдает
своего за вражеского! :). Ниже представлены предварительные версии программы Джин. Джин находится в процессе разработки т.е. каждая следующая версия делает предыдущую совершенно неактуальной. Разве что в ней появятся глюки которых не было в предыдущих :) GENIE_0_0_1 – самая первая версия программы джин.
Эта версия была написана на базе And_chess_K. В ней я заново переписал
движок. Мы используем полный перебор. Движок выводит вариант и оценку
этого варианта. Последний ход варианта дебильный. 23.12.2006 GENIE_0_0_2- в этой версии движок научился делать
рокировку. Но рокировка в оболочке не доработана так что если снимут
ранее не ходившую ладью то можно рокировать с возникновением ладьи :) В
движке этого бага нет. 30.12.2006 GENIE_0_0_3- в этой версии движок научился
бить на проходе. 1.01.2007 GENIE_0_0_4- в этой версии движок
перестал есть короля. Также он видит шах и мат и соответственно если мы
имеем матовую комбинацию то игра прекращается. Движок не знает правил
трехкратного повторения позиции и 50-го хода. 5.01.2007 GENIE_0_0_5- в этой версии
я подключил Тогу. Тога это сильнейшая бесплатная шахматная программа.
Что бы с ней играть нужно в папку где находится Джин поместить
TogaII.exe. После этого можно играть. Если же Тоги не будет а флажок
игры с ней поставлен то хода от проги вы не дождетесь :) Тогу я тоже
выложил на своем сайте. Ниже представлены предварительные версии программы Ифрит. Ифрит находится в процессе разработки т.е. каждая следующая версия делает предыдущую совершенно неактуальной. 28.01.2007 Ифрит - шахматный
UCI движок написанный на языке С++. 23.02.2007 Ifrit_C.0.0.3Сделал косметическую правку кода. Добавил комментариев. Полный перебор меня не устраивает, а "метод интересных продолжений" еще обдумываю. Отсюда и простой. 17.03.2007 Ifrit_C.0.0.4Заново переписал функцию перебора. Теперь мы оцениваем позицию на каждом полуходе. Даная реализация использует полный перебор но с оценкой в каждом узле. Комфортная глубина игры 4 полухода. Играет так же как предыдущая но углубляется медленнее. Тут заложен фундамент который должен усилить следующие версии. 31.03.2007 Ifrit_C5Сделал альфа-бета отсечение. Быстро играет при depth 4. Рекомендую устанавливать четную глубину перебора. Устанавливается глубина перебора(в полуходах) не более 9. Если поставить глубину depth 10 то Ифрит выставит 1. Программа больше не нападает на вражеского короля в матовой ситуации. Но по прежнему рокирует из под шаха и через битые поля. Не знает правила трех повторов позиции и пятидесяти ходов. От форсированных взятий пока отказался так же как и от узкого луча поиска. 07.05.2007 Ifrit_C6Заново переписал модуль правил. В модуль подается доска в виде структуры, а на выходе получаем список возможных ходов. Сделал на основе доски 8 на 16. Это известная техника и ничего нового тут я не сделал. Так как новый модуль подключен через переходники, то пока прироста скорости нет. Выложил, потому что закончился еще один этап хотя на данный момент изменения неощутимы. Уже в следующей версии должен быть прирост скорости. 13.05.2007 Ifrit_C7Заново переписал реализатор ходов. По моему прирост скорости ~20%. Теперь он напрямую завязан на модуль правил без всяких переходников. Массивы вариантов и дерево перебора остались старыми. В следующей версии я их перепишу. 22.05.2007 Ifrit_C8Полный перебор без альфа-беты. Использую как точку отсчета. 27.05.2007 Ifrit_C9Свершилось! Полностью перешел на новый генератор 8 на 16. Теперь нет никаких переходников. Все работает на новых структурах данных. Есть альфа-бета отсечение. Нормально играет при depth 5. 1.06.2007 Ifrit_C10Доработал линию вывода варианта. Это последняя версия проги, которая не знает шаха, т.е. рокирует под шахом и не умеет ставить маты. В следующей версии генератор шахов уже будет. 3.06.2007 Ifrit_C11Знает все правила кроме трехкратного повторения позиции и правила 50 ходов. Нормально играет при depth 5. Продлений нет, поэтому ярко выражен эффект горизонта. 8.06.2007 Ifrit_C12Нормально играет при depth 6. При переборе взятия рассматривает первыми. 14.06.2007 Ifrit_C13Причесал код. Сделал отключаемое средствами препроцессора тестирование. В итоге исполняемый код уменьшился до 60 кб! Сделал вывод текущего варианта. Нормально играет при depth 7. При переборе взятия рассматривает первыми. 17.06.2007 Ifrit_C14Отладил матовую атаку. Нормально играет при depth 6. 23.06.2007 Ifrit_C15Выводит варианты разной длины, но не больше максимальной глубины. Нормально играет при depth 6. 15.07.2007 Ifrit_C16Сделал честную проверку на шах. Детектор шахов крайне медленный. Нормально играет при depth 6. 16.07.2007 Ifrit_C16_1Никогда не думал, что буду выпускать версии типа 16_1 :) Но время переделки возрастает, а баги требуют немедленного исправления, так что открыл новую традицию. Ифрит, как садист, выбирал не самый короткий путь к мату. Исправил, и теперь он ищет кратчайший путь. 22.07.2007 Ifrit_C17Переписал детектор шахов. Где только можно перевел структуры с int на short int. Сделал печать фигуры превращения пешки в вариантах. Нормально играет при depth 6. 02.08.2007 Ifrit_C17_3Доработал превращение пешки при инициализации стартовой позиции. Убрал пробел в вариантах когда пешка не превращается. Раньше вместо фигуры превращения печатался пробел. 04.08.2007 Ifrit_C17_4Доработал превращение пешки при инициализации стартовой позиции. 18.08.2007 Ifrit_C18Сделал вывод дистанции до мата. Переписал вывод вариантов. Нормально играет при depth 6. Ifrit_Forced_C18 Версия с просчетом взятий до глубины depth 10. Нормально играет при основной глубине depth 5. 14.09.2007 Отредактировал главную страницу сайта(HTML-код). Добавил комментариев.Упорядочил структуру и выкинул лишнее. На внешнем виде это почти не отразилось :) 15.09.2007 Ifrit_C18_1Исправил вывод оценки. 18.09.2007 Ifrit_C19Сделал форсированный ход и корректный выход в любой момент. Нормально играет при depth 6. 23.09.2007 Ifrit_C20Добавил правило трехкратного повторения позиции. Нормально играет при depth 6. 11.10.2007 Ifrit_C20_2Добавил комментариев. 13.10.2007 Ifrit_C21Добавил функцию тестирования полного перебора(доступна только из исходников). Причесал функцию перебора и изменил альфа-бету. Добавил комментариев. 19.10.2007 Ifrit_C21Включена форсировка до 10 полуходов. 28.10.2007 Ifrit_C22Переписал функцию форсированного перебора. Включена форсировка до 10 полуходов. Подправил вывод вариантов. Сделал итерационное углубление, но пока без хеширования. 30.10.2007 Ifrit_C22_1Переписал альфу бету в основном и форсированном варианте. Реализовал самую прозрачную и эффективную версию. Конечно это на мой взгляд :) Сравнительно быстро играет при глубине depth 5. 1.11.2007 Ifrit_C22_3Убрал ограничение на глубину форсированного варианта. Исправил форсированный вариант. На глубине depth 5 думает до 16 мин(на сравнительно слабой машине). Что конечно неприемлемо. Будем с этим бороться :) 3.11.2007 Ifrit_C23Реализовал MVV/LVA(наиболее ценная жертва -наименее ценный нападающий) сортировку взятий. Для этого ввел в список избыточных ходов массив взятых фигур. Получил ощутимый прирост в скорости. На глубине depth 5 думает до 1 мин. 12.11.2007 Ifrit_C23_1Подправил форсированный вариант. Слегка подкорректировал оценку позиции. Сравнительно быстро играет при глубине depth 6. 17.11.2007 Ifrit_C24Подправил форсированный вариант. Теперь продолжаю не только когда фигура взята, но также, когда фигура под боем. Сделал блиц контроль, заданное время на ход. Пока добавление времени за ход не понимает. Весьма своеобразно распределяет время на партию. :) 18.11.2007 Ifrit_C25Добавил бесконечный анализ. Сделал отдельный генератор взятий. Движок слегка ускорился. 26.11.2007 Ifrit_C26Обнаружил, что тестовая функция не работает. Оказалось, что функция strtok разрушает входящую строку. А я довольно долго искал ошибки в переборе :) Сделал список возможных ходов глобальным. Пришлось прилично менять код. В результате быстродействие резко упало. Хотя, если отключаешь форсировку скорость на том же уровне. На глубине depth 4 думает до 1 мин. 27.11.2007 Ifrit_C26_1Забыл включить альфа-бета отсечение. Отсюда и низкая скорость. А я-то было подумал, что виноваты глобальные списки :) Это версия с форсировками. По сути, это 25-ка только с глобальными списками ходов. Ну и исправил некоторые баги. Ifrit_C26_2 Здесь подключил форсировку на шахах. Ради этого я и затеял глобальные списки. 29.11.2007 Добавил 3-ю часть истории разработки Ифрита.9.12.2007 Ifrit_C26_4Переписал альфа-бета в основном и форсированном поиске. Вернулся к схеме с амортизацией отказов. Подправил вывод варианта в форсированном поиске. Ввел контроль соответствия оценки и варианта. Сделал вывод тестовой информации в форсировке(при отладке). 12.12.2007 Ifrit_C26_5Слегка изменил оценку. Добавил бонус в пешку за существование фигур. Чтобы движок не отдавал фигуры за пешки. Все равно на их реализацию глубины не хватает. 17.12.2007 Ifrit_C27Сделал хеширование ходов. Ускорения почти нет. Зато теперь, как правило, не возвращается к кривому ходу во время итераций :) Реализация хеша предварительная и нужна для отладки. Dann Corbit посмотрел исходники Ифрита(Ifrit_С27) "I made some corrections" Dann Corbit 22.12.2007 Ifrit_C28Добавил недействительное перемещение(null move). Использую на глубине 2. Учел некоторые замечания Дена Корбита (Dann Corbit). Убрал критические баги (неинициализированная структура и переполнение буфера). Стоит ли отказываться от си-библиотек в пользу си++ я еще подумаю :) 23.12.2007 Ifrit_C28_1Исправил недействительное перемещение(null move). Использую на глубине, начиная с 2. 31.12.2007 Ifrit_C28_2Отключил недействительное перемещение (null move). Потому что в данной реализации ускорение от null move всего ~30%. Причем, тупит в цугцвангах и стиль игры мне не нравиться, поэтому решил пока обойтись без null move. По-новому отсортировал модули. Подправил оценку. Теперь есть штраф за сдвоенные пешки. Также слоны и ладьи стремятся контролировать как можно больше полей. Добавил возможность отключения методик (типа альфы-беты, хеш-таблицы и т.д.) перед компиляцией. "Причесал" код в модуле перебора. 4.1.2008 Ifrit_C29Переделал оценку. Теперь в конце основного перебора считаем только позиционный фактор, а в конце форсировки только материал. Добавил negascout, только он не ускоряет, а тормозит перебор. Пока отключил. Будем разбираться. Подправил вывод варианта. Теперь выводится ход, который обсчитывается, а не тот, который уже обсчитали. Добавил эвристику убийцы (killer heuristic). Ускорение видно. Переписал функцию форсированного поиска. 5.1.2008 Ifrit_C29_1Ограничение на форсировку на шахе увеличил до 20 полуходов. Добавил сортировку ходов. Список смотрим в следующем порядке конь, слон, ферзь, ладья, король, пешки. Продолжаю размножать модули :) 6.1.2008 Добавил компиляцию Ифрита 28_1 от Dann Corbit. Опубликовал с задержкой потому что неделю не заглядывал в почту."This is an update of your latest version. The code will compile with modern C++ compilers." Dann Corbit 7.1.2008 Ifrit_C29_2Изменил оценку. Добавил штраф за бреши в щите короля. Включил negascout. Включил null move. 10.1.2008 Добавил свои размышления о стратегии поиска. Добавил лицензионное соглашение.Хочу отметить один момент. Государственным языком у нас является русский язык и юридическую силу имеют только документы написанные на русском языке, следовательно оригинал GNU\GPL в нашей стране не действителен. :) Некоторые мысли 13.1.2008 Выложил исходники Стрелки в виде html-страниц. Теперь для их изучения нужен только интернет :)15.1.2008 Добавил текста в свои размышления о стратегии поиска.28.1.2008 Ifrit_C30Начал переход на битбоард (bitboard). В данной версии написал битбоард-генератор списка ходов. Подключил его через переходник. Реализатор ходов и все остальные части программы остались прежними. Программа получилась более тормозная, чем предыдущая. Так же: - в выводе варианта дополнительно печатем линию после прохождения очередной глубины; - сделал, чтобы корректно отображалось количество просмотренных узлов на данной глубине; - теперь считаю узлы только основного перебора, без учета форсировок; - изменил сортировку ходов. Теперь сортировка в следующем порядке: ферзь, ладья, слон, конь,король, пешки; - переделал вставку киллера. Теперь вставка со сдвигом, а не просто замена местами; - переделал вставку хеша. Теперь вставка со сдвигом, а не просто замена местами. На главную не выкладываю, так как это промежуточная версия и тестировал в ней я только генератор ходов :) 29.1.2008 Ifrit_C30_1Отключил null move. Он глючит с новым генератором. 2.2.2008 Ifrit_C30_2Разделил битбоард-генератор списка ходов. Теперь есть функция генерирующая только взятия и превращения + функция генерирующая все остальные ходы. "Причесал" код в битбоард-генераторе. Программа получилась еще более тормозная, чем предыдущая. Генератор списка ходов 0х88 больше не использую. На главную не выкладываю, так как это промежуточная версия и тестировал в ней я только генератор ходов. 18.2.2008 Ifrit_C30_3Закончил переход на битбоард. Теперь генератор ходов, детектор шахов и реализатор ходов переведены на битбоард. К сожалению, в генераторе есть баг, который проявляется в позиции: "fen r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1" начиная с глубины 4 полухода. В чем проблема я пока не понимаю. Буду думать. Вообще, хочется сказать, что написать битбоард-генератор оказалось на порядок, - а может и на два, - сложнее. Так что, я бы не советовал начинать с него. :) Выкладываю только исходники. 20.2.2008 Ifrit_C30_4Баг нашел и исправил. Пока искал во мне пошатнулась вера в человеческий разум :) Еще чуть-чуть и пошел бы искать свой бубен. Желающие могут повторить мой подвиг :) Битбоард-генератор оказался существенно быстрее предыдущего генератора. Выложил полный перебор (даже без а-б) с простейшей оценкой ( от 0.5 до 1 млн. поз/сек на селероне 2600). Сейчас выдает количество узлов на слое, а не полное количество. На главную не выкладываю, так как все эвристики отключенны, и тестировал в ней я только генератор ходов. 24.2.2008 Ifrit_b1Это Ifrit_C29_2, только с битбоард-генератором ходов. С этого движка начал линейку битбоард движков. Таким образом, в серии "с" используется 0х88-генератор, а в серии "b" используется битбоард-генератор. Движок на битбоарде играет так же, только несколько быстрее. Лично я утвердился во мнении, что для среднего движка совершенно без разницы, какой использовать генератор ходов. Скажу только, что сама идея битбоард-генератора изумительно красивая, а реализация достаточно сложная . Исходники Ifrit_b1(87Kb) Ifrit_b1(108Kb) 25.2.2008 Ifrit_b1_1Исправил баг из-за которого не работал нулевой ход . Исходники Ifrit_b1_1(87Kb) Ifrit_b1_1(108Kb) 1.3.2008 Ifrit_b1_2Отключил негаскаут. Толку от него вообще нет. Причину этого я затрудняюсь объяснить. Думаю он по жизни такой. Добавил контролирующую функцию в генератор ходов. Отловил еще пару багов. Остались очень хитрые баги. Настолько хитрые, что пока сидят тихо :) В дальнейшем продолжу политику тотального контроля. Исходники Ifrit_b1_2(87Kb) Ifrit_b1_2(108Kb) 2.3.2008 Ifrit_b1_3Отловил еще два бага в нулевом ходе. Исходники Ifrit_b1_3(88Kb) Ifrit_b1_3(108Kb) 16.3.2008 Ifrit_b1_4Проверку битых полей при рокировке перенес внутрь генератора избыточных ходов. Подправил распознавание ничьей повтором ходов. Подправил статическую оценку позиции. Нулевой ход продолжает глючить. Пока отключил. Добавил новые комментарии. Файлы залил повторно. Если Вы уже успели скачать, то лучше скачать по-новому. В старой версии баг с повтором ходов. Исходники Ifrit_b1_4(88Kb) Ifrit_b1_4(108Kb) 25.3.2008 Ifrit_b1_5Перешел с NegaMax на MiniMax. Т.е. теперь для белых и черных отдельные функции, вплоть до генератора ходов и детектора шахов. Отлавливать минусы при тестировании мне надоело :) Кроме того, на мой взгляд, MiniMax на порядок прозрачнее и несколько быстрее. Нулевой ход вообще убрал из кода. Пока и без него хватает проблем. Исходники Ifrit_b1_5(89Kb) Ifrit_b1_5(108Kb) 30.3.2008 Ifrit_b1_6Переписал Negascout под MiniMax. В этой версии он работает. При переходе на новый детектор перестала работать форсировка на шахах. Теперь снова заработала. :) Сортировка по взятиям в форсированном варианте была просто "взятая фигура - берущая фигура", теперь стало "взятая фигура*100 - берущая фигура" Ускорение есть, правда, не такое, как бы хотелось :) Исходники Ifrit_b1_6(88Kb) Ifrit_b1_6(108Kb) 12.4.2008 Ifrit_b1_7Подправил форсированный поиск. Добавил нулевой ход. Пытался добавить продление поиска в линиях с разменами. От схемы отказался. Слишком обваливается глубина основного перебора. Исходники Ifrit_b1_7(89Kb) Ifrit_b1_7(108Kb)
|