За последний год разработки моего шахматного движка (www.chessbin.com) большая часть времени была потрачена оптимизация моего кода для лучшего и более быстрого поиска ходов. За это время я научился нескольким приемам, которыми хочу поделиться с вами.

Измерение эффективности

По сути, вы можете улучшить свою производительность двумя способами:

• Оценивайте свои узлы быстрее
• Ищите меньшее количество узлов, чтобы получить тот же ответ

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

• Время, которое потребовалось для завершения поиска.
• Количество найденных узлов

Это позволит вам сравнить и протестировать ваши изменения. Лучший способ приблизиться к тестированию — создать несколько сохранений из начальной позиции, мидгейма и эндгейма. Запишите время и количество искомых узлов для черного и белого. После внесения каких-либо изменений я обычно провожу тесты с упомянутыми выше сохраненными играми, чтобы увидеть, внес ли я улучшения в две вышеупомянутые матрицы: количество искомых узлов или скорость.

Чтобы еще больше усложнить ситуацию, после внесения изменения в код вы можете запускать свой движок 3 раза и каждый раз получать 3 разных результата. Допустим, ваш шахматный движок нашел лучший ход за 9, 10 и 11 секунд. То есть разброс около 20%. Итак, вы улучшили свой движок на 10%-20% или просто изменили нагрузку на свой компьютер. Откуда вы знаете? Для борьбы с этим я добавил методы, которые позволят моему движку играть против самого себя, он будет делать ходы и за белых, и за черных. Таким образом, вы можете проверить разницу во времени не только для одного хода, но и для серии из 50 ходов в течение игры. Если в прошлый раз игра длилась 10 минут, а теперь 9, то вы, вероятно, улучшили свой движок на 10%. Повторный запуск теста должен подтвердить это.

Поиск повышения производительности

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

Если вы работаете в среде .NET, вам поможет профилировщик .NET. Если у вас есть версия Visual Studio для разработчиков, она встроена бесплатно, однако есть и другие сторонние инструменты, которые вы можете использовать. Этот инструмент сэкономил мне часы работы, так как он подскажет, где ваш двигатель тратит большую часть своего времени, и позволит вам сосредоточиться на проблемных местах. Если у вас нет инструмента профилирования, вам, возможно, придется как-то регистрировать временные метки, когда ваш движок проходит различные этапы. Я не предлагаю этого. В этом случае хороший профайлер на вес золота. Red Gate ANTS Profiler дорогой, но лучший из тех, что я когда-либо пробовал. Если вы не можете себе это позволить, по крайней мере, используйте его для их 14-дневной пробной версии.

Ваш профилировщик наверняка определит для вас некоторые вещи, однако вот несколько небольших уроков, которые я усвоил, работая с C#:

• Сделать все приватным
• Все, что вы не можете сделать приватным, сделайте это запечатанным
• Сделайте как можно больше методов статическими.
• Не делайте свои методы болтливыми, один длинный метод лучше, чем 4 маленьких.
• Шахматная доска, хранящаяся в виде массива [8][8], работает медленнее, чем массив из [64].
• Замените int на byte, где это возможно.
• Вернитесь от своих методов как можно раньше.
• Стеки лучше списков
• Массивы лучше, чем стеки и списки.
• Если вы можете определить размер списка, прежде чем заполнить его.
• Кастинг, бокс, распаковка — это зло.

Дальнейшее повышение производительности:

Я считаю, что генерация ходов и их порядок чрезвычайно важны. Однако вот в чем проблема, как я ее вижу. Если вы оцениваете счет каждого хода перед сортировкой и запуском альфа-бета, вы сможете оптимизировать порядок ходов, чтобы получить очень быстрые отсечки альфа-бета. Это потому, что вы сможете сначала попробовать лучший ход. Однако время, которое вы потратили на оценку каждого хода, будет потрачено впустую. Например, вы могли оценить счет на 20 ходах, отсортировать свои ходы, попробовать первые 2 и получить отсечку на ходу номер 2. Теоретически время, которое вы потратили на остальные 18 ходов, было потрачено впустую.

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

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

Отвечаю на старый вопрос.

Предполагая, что у вас уже есть рабочая таблица транспонирования.

Уменьшение поздних ходов. Это дало моей программе около 100 баллов Эло, и ее очень просто реализовать.

По моему опыту, если ваша реализация не очень неэффективна, фактическое представление платы (0x88, битовая плата и т. д.) не так важно.

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

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

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

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

Ваша программа может пройти долгий путь, используя только эти простые приемы!

Удачный заказ переезда!

Старый вопрос, но сейчас применяются те же методы, что и 5 лет назад. Разве мы все не пишем свои собственные шахматные движки, у меня есть свой собственный под названием Norwegian Gambit, который, я надеюсь, в конечном итоге будет конкурировать с другими движками Java в CCRL. Я, как и многие другие, использую Stockfish для поиска идей, потому что он так хорошо написан и открыт. Их среда тестирования Fishtest и ее сообщество также дают массу полезных советов. Стоит сравнить ваши оценочные баллы с тем, что получает Stockfish, поскольку то, как оценивать, вероятно, до сих пор является самым большим неизвестным в шахматном программировании, а Stockfish ушел от многих традиционных оценок, которые стали городскими легендами (например, бонус двойного слона). Самая большая разница, однако, заключалась в том, что после того, как я применил те же методы, которые вы упомянули, Negascout, TT, LMR, я начал использовать Stockfish для сравнения и заметил, что для той же глубины Stockfish искал гораздо меньше ходов, чем я получил (из-за порядка ходов ).

Основы заказа переноса

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

1. Таблица транспонирования
2. Сортировать акции и удачные захваты по их выигрышу
3. Убийца движется
4. Ходы, приводящие к шаху противника
5. Эвристика истории
6. Бесшумные ходы — сортировка по значению PSQT

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

О Java/C# и C/C++/Assembly

Методы программирования для Java такие же, как в превосходном ответе Адама Берента, который использовал C #. В дополнение к его списку я бы упомянул о том, чтобы избегать массивов объектов, а использовать множество массивов примитивов, но, вопреки его предложению использовать байты, я обнаружил, что с 64-битной java мало что можно сохранить, используя byte и int вместо 64-битная длина. Я также пошел по пути переписывания на C/C++/Assembly, и у меня нет никакого прироста производительности. Я использовал ассемблерный код для инструкций битового сканирования, таких как LZCNT и POPCNT, но позже обнаружил, что Java 8 также использует их вместо методов объекта Long. К моему удивлению, Java работает быстрее, виртуальная машина Java 8, кажется, лучше справляется с оптимизацией, чем компилятор C.

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

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

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

Я не видел обрезки нулевых ходов, таблиц транспонирования. Вы их используете? Они бы дали тебе большой толчок...

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

Большинство современных ПК имеют несколько ядер, поэтому было бы неплохо сделать их многопоточными. Для этого вам не обязательно использовать MDF(f).

Я не предлагаю переносить ваш код на битборд. Это просто слишком много работы. Несмотря на то, что битборды могут дать толчок на 64-битных машинах.

Наконец, что наиболее важно, шахматная литература доминирует над любыми оптимизациями, которые мы можем использовать. оптимизация - это слишком много работы. Посмотрите на шахматные движки с открытым исходным кодом, особенно на crafty и fruit/toga. Раньше Fruit был с открытым исходным кодом.

Поздний ответ, но это может кому-то помочь:

Учитывая все упомянутые вами оптимизации, 1450 ELO — это очень мало. Я предполагаю, что что-то очень не так с вашим кодом. Вы:

1. Написал подпрограмму perft и провел ее по набору позиций? Все тесты должны пройти, чтобы вы знали, что ваш генератор ходов не содержит ошибок. Если у вас этого нет, то и говорить об ELO не имеет смысла.

2. Написал подпрограмму mirrorBoard и пропустил код оценки через набор позиций? Результат должен быть одинаковым для нормального и зеркального положения, иначе у вас ошибка в eval.

3. У вас есть хэш-таблица (она же таблица транспонирования)? Если нет, то это обязательно. Это поможет при поиске и заказе ходов, давая зверскую разницу в скорости.

4. Как вы реализуете порядок перемещения? Это ссылка на пункт 3.

5. Вы внедрили протокол UCI? Ваша функция move parsing работает правильно? У меня была такая ошибка в движке:

     /* Parses a uci move string and return a Board object */
     Board parseUCIMoves(String moves)// e2e4 c7c5 g1f3 ...{
         //...
         if (someMove.equals("e1g1") || someMove.equals("e1c1"))
             //apply proper castle
        //...
    }
   

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

Для (1) вы можете искать каждую позицию до глубины 6. Я использую файл с ~ 1000 позиций. См. здесь https://chessprogramming.wikispaces.com/Perft

Для (2) вам просто нужен файл с миллионами позиций (только строка FEN).

Учитывая все вышеперечисленное и очень простую функцию оценки (материал, фигурные квадраты, проходные пешки, безопасность короля), он должен играть с +-2000 ELO.

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

Если вы переходите на битовые доски, покопайтесь в архивах rec.games.chess.computer и найдите несколько старых постов доктора Роберта Хайатта о Крафти (почти уверен, что он больше не публикует). Или возьмите последнюю копию с его FTP и начните копаться. Я почти уверен, что это будет значительным сдвигом для вас.

• Таблица транспонирования
• Открытие книги
• Основы столов финальной игры
• Улучшенная оценка статической платы для конечных узлов
• Bitboards для чистой скорости

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

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

Найдите горячие точки. Рефакторинг. При необходимости перепишите на ассемблере. Повторение.

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

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

Однако я не уверен, что бы вы хотели, чтобы он узнал...