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