За последний год разработки моего шахматного движка ( www.chessbin.com ) большая часть времени была потрачена на оптимизацию моего кода, чтобы обеспечить более быстрый и быстрый поиск по ходу. За это время я выучил несколько трюков, которыми хотел бы поделиться с вами.
Измерение производительности
По сути, вы можете улучшить свою производительность двумя способами:
- Оцените ваши узлы быстрее
- Поиск меньшего количества узлов, чтобы придумать
тот же ответ
Ваша первая проблема в оптимизации кода будет измерение. Откуда вы знаете, что вы действительно изменили ситуацию? Чтобы помочь вам с этой проблемой, вам необходимо убедиться, что вы можете записать некоторую статистику во время поиска ходов. Те, что я запечатлел в своем шахматном движке:
- Время, необходимое для поиска
полный.
- Количество найденных узлов
Это позволит вам сравнить и протестировать ваши изменения. Лучший способ приблизиться к тестированию - создать несколько сохраненных игр из начальной позиции, средней игры и конечной игры. Запишите время и количество найденных узлов для черно-белых изображений.
После внесения каких-либо изменений я обычно выполняю тесты с вышеупомянутыми сохраненными играми, чтобы увидеть, добился ли я улучшения в двух вышеупомянутых матрицах: число найденных узлов или скорость.
Чтобы усложнить ситуацию, после изменения кода вы можете запустить свой движок 3 раза и каждый раз получать 3 разных результата. Допустим, ваш шахматный движок нашел лучший ход за 9, 10 и 11 секунд. Это спред около 20%. Так вы улучшили свой движок на 10% -20% или это была просто измененная нагрузка на ваш компьютер? Откуда вы знаете? Чтобы бороться с этим, я добавил методы, которые позволят моему движку играть против себя, он будет делать ходы как для белых, так и для черных. Таким образом, вы можете проверить не только разницу во времени за один ход, но и серию из 50 ходов в течение игры. Если в прошлый раз игра занимала 10 минут, а теперь - 9, вы, вероятно, улучшили свой двигатель на 10%. Повторное выполнение теста должно подтвердить это.
Поиск прироста производительности
Теперь, когда мы знаем, как измерять прирост производительности, давайте обсудим, как определить потенциальный прирост производительности.
Если вы находитесь в среде .NET, то .NET Profiler будет вашим другом. Если у вас есть выпуск Visual Studio для разработчиков, он поставляется бесплатно, однако есть и другие сторонние инструменты, которые вы можете использовать. Этот инструмент сэкономил мне часы работы, поскольку он подскажет вам, где ваш двигатель проводит большую часть своего времени, и позволит вам сосредоточиться на проблемных местах. Если у вас нет инструмента профилирования, вам, возможно, придется каким-то образом регистрировать метки времени, поскольку ваш движок проходит через различные этапы. Я не предлагаю это. В этом случае хороший профилировщик на вес золота. Red Gate ANTS Profiler - дорогой, но лучший из тех, что я когда-либо пробовал. Если вы не можете себе этого позволить, хотя бы используйте его на 14-дневную пробную версию.
Ваш профилировщик определит вещи для вас, однако вот несколько небольших уроков, которые я усвоил, работая с C #:
- Сделай все приватнее
- Что бы ты не делал приватным, сделай
это запечатано
- Сделать столько методов статичными, сколько
возможно.
- Не делайте ваши методы болтливыми, один
длинный метод лучше чем 4 меньше
из них.
- Шахматная доска хранится в виде массива [8] [8]
медленнее, чем массив [64]
- Замените int байтом, где это возможно.
- Вернитесь из своих методов уже в
возможно.
- Стеки лучше списков
- Массивы лучше, чем стеки и
списки.
- Если вы можете определить размер
список, прежде чем его заполнить.
- Кастинг, бокс, распаковка - зло.
Дальнейшее повышение производительности:
Iнайти генерацию ходов и порядок чрезвычайно важны. Однако вот проблема, как я ее вижу. Если вы оцените счет каждого хода перед тем, как сортировать и запускать альфа-бета-версию, вы сможете оптимизировать порядок своих ходов таким образом, чтобы получить чрезвычайно быстрые отсечки альфа-бета-версии. Это потому, что вы в первую очередь сможете попробовать лучший ход.
Однако время, потраченное на оценку каждого хода, будет потрачено впустую. Например, вы могли оценить счет за 20 ходов, отсортировать свои ходы, попробовать первые 2 и получить отсечение на ходу номер 2. Теоретически время, которое вы потратили на остальные 18 ходов, было потрачено впустую.
С другой стороны, если вы выполняете более легкую и намного более быструю оценку, скажем, просто захватывает, ваш вид не будет таким хорошим, и вам придется искать больше узлов (до 60% больше). С другой стороны, вы не будете делать тяжелую оценку на каждом возможном шаге. В целом этот подход обычно быстрее .
Нахождение этого идеального баланса между наличием достаточного количества информации для хорошей сортировки и отсутствием дополнительной работы с ходами, которые вы не будете использовать, позволит вам найти огромный выигрыш в вашем алгоритме поиска. Кроме того, если вы выберете подход с более плохой сортировкой, вам нужно сначала выполнить более мелкий поиск, скажем, сгиб 3, отсортировать ваш ход, прежде чем углубляться в поиск (это часто называется итеративным углублением). Это значительно улучшит ваш вид и позволит вам искать гораздо меньше ходов.