Эффективное представление доски для стратегии настольной игры AI
Будет ли представление в виде доски все еще столь же эффективно в тупой шахматной стратегии, которая имеет менее 64 позиций, или будет более практичной реализация почтового ящика на основе массива?
В нашем классе искусственного интеллекта проводится ежегодный конкурс, на котором профессор составляет настольную игру, и у нас есть четыре недели, чтобы создать искусственный интеллект, который будет играть в эту игру. Как правило, фигуры представляют собой подмножество шахматных фигур с похожими правилами и разыгрываются на меньшей доске. то есть 8x5, 7x7, и т. д. Я совсем не уверен, как использовать только 40 бит по сравнению с типичными 64 для шахмат.
Моя единственная проблема в том, что я не очень хорошо знаком с C или C++ и мне было бы удобнее реализовывать программу на Java. Достаточно ли их поддержки в Java для манипулирования битами, где я мог бы реализовать представление в виде битовой доски, и если это повысило бы эффективность, стоило бы добавить дополнительную сложность? Будет ли кривая обучения слишком крутой?
Мой план состоит в том, чтобы использовать поиск Negamax с сокращением AB, поиском покоя, таблицами транспозиции, движениями убийцы и т. Д. В зависимости от времени. Какие-нибудь другие советы для создания конкурентоспособного ИИ за такое короткое время?
4 ответа
Плата будет работать, но, на мой взгляд, дополнительные усилия и сложность, направленные на то, чтобы заставить ее работать должным образом, в дальнейшем не принесут никакого повышения вычислительной эффективности.
В общем масштабе любой эффективности от побитовой маскировки (& или же |) за выборку элемента массива (или даже List или же Map) будет в значительной степени омрачен любым AI или алгоритмом поиска, который вы намереваетесь использовать.
То есть алгоритм экспоненциальной или полиномиальной сложности все равно будет O(e^n) или же O(n^d) и те немногие циклы ЦП, которые вы сохраняете с помощью двоичной арифметики над разыменованием указателя, будут незначительными.
Просто перейдите к самой простой структуре данных, которую вы можете использовать на данный момент (возможно, массив или что-то еще Collection) и сосредоточиться на том, чтобы заставить ваши алгоритмы работать.
Позже, если у вас есть время, вы можете профилировать свою программу, и если вы обнаружите, что поиск в массивах занимает, скажем, 20% вашего времени выполнения, то, возможно, просто возможно, рассмотрите возможность рефакторинга всего для побитовых операций.
Лично я бы посмотрел на возможные способы параллельного поиска в пространстве решений, чтобы максимизировать несколько ядер ЦП или, еще лучше, таким образом, чтобы их можно было распределить по нескольким вычислительным узлам. Да, это, вероятно, даст вам хотя бы степень магистра, если вы обнаружите что-то действительно умное.:)
В университете у меня были конкурсы по написанию игрового ИИ, подобные вашим, и я добился наибольших ускорений не тогда, когда я беспокоился о каких-то маленьких подробностях, таких как: "кодирование вещей статически быстрее" или "проверки работоспособности замедляют мою программу? но "если я напишу свой ИИ для того, чтобы он был умнее / эффективнее, он будет работать на более высоком уровне, поэтому я собираюсь реализовать этот новый крутой трюк".
Обычными примерами ошеломительных ускорений являются альфа-бета-обрезка, убийственная эвристика и выбор хорошего алгоритма для расчета силы игрового состояния (обратите внимание, что хорошо!= Более точно - это также может означать быстрее и все еще точно. В конце концов, если ваш счет Расчет проще, он позволяет вам смотреть больше вперед, что означает, что вы наверстаете упущенное).
Вы также можете использовать битборды. Это не так уж сложно, и вы получаете значительное ускорение при генерации движений и оценке статического обмена. Ваш алгоритм искусственного интеллекта, каким бы умным он ни был, все равно должен будет выполнить множество таких задач.
На эту тему есть очень хороший сайт: http://chessprogramming.wikispaces.com/Bitboards
Поскольку ваши доски имеют разный размер, некоторые приемы могут не применяться в зависимости от того, как вы назначаете биты квадратам. С другой стороны, поскольку это только часть компонентов, некоторые проблемы, которые традиционно проблематично решить с помощью битбордов, могут не существовать.
Установка отдельного бита в битовой шкале обычно медленнее, чем элемент настроек в логическом массиве, потому что первый требует чтения + побитовое И / ИЛИ + запись, в то время как второй требует только запись.
Чтение отдельных битов в битовой шкале также происходит медленнее: чтение + побитовое И / ИЛИ + сдвиг по сравнению с только что прочитанным.
Так что если вашему ИИ понадобится много состояний чтения / записи отдельных ячеек доски, то логический массив будет более эффективным. В то же время процесс создания клона всей платы происходит быстрее, когда плата использует меньше памяти, т.е. когда ячейки упакованы в биты. Если ваш ИИ будет часто клонировать бардов и делать только несколько операций get / set между операциями клонирования, тогда битовая шкала лучше, независимо от размера платы.