Шахматная оптимизация

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

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

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

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

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

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

Я не уверен, что именно вы хотели бы изучить ...

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

За последний год разработки моего шахматного движка ( 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 байтом, где это возможно.
• Вернитесь из ваших методов как можно раньше возможно.
• Стеки лучше, чем списки
• Массивы лучше, чем стеки и списки.
• Если вы можете определить размер список, прежде чем заполнять его.
• Кастинг, бокс, распаковка - это зло.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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