Лучший подход для написания шахматного движка? [закрыто]

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

Какой язык (я знаком с Java, C ++ и Python) и методологию я должен адаптировать при написании шахматного движка?

Небольшое руководство будет высоко ценится.

Редактировать:

Поэтому я решил сделать это на JavaScript. Я загружаю этот шахматный интерфейс с github, и теперь у меня все готово! Моим первым шагом было бы написать законные ходы для этого. Так кто-нибудь может указать мне правильное направление? (Я новичок в jQuery, но имею большой опыт программирования).

PS: я не пытаюсь сделать очень эффективный движок (я знаю, что он слишком сложный), я просто хочу познакомиться с процессом и изучить некоторые новые методы на этом пути.

Шахматист с рейтингом 2072 здесь. Я сделал этот сайт на чистом JavaScript за выходные. Это не шахматный движок (я разработал его для создания занимательных открывающих позиций как своего рода извращенный движок Chess960), но это отправная точка. Исходный код здесь .

Есть много сложностей, связанных с созданием функциональной доски. Это включает:

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

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

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

Это все в первую очередь при разработке алгоритма, о котором имеется достаточно информации.

Что касается того, с каким языком идти (хотя я думаю, что вы уже выбрали JavaScript), я думаю, что это зависит больше от вашей цели, чем от чего-либо еще. Я хотел сделать мой онлайн (и улучшить JavaScript), поэтому JavaScript был моим выбором. Подойдет любой объектно-ориентированный язык программирования.

Когда вы освоитесь с тем, что делаете, следующие ресурсы, вероятно, окажутся действительно полезными:

• Wiki Программирование шахмат
• Форум по шахматному программированию
• StockFish на Github

Удачи!

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

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

Если вы знакомы с правилами игры в шахматы, хорошей отправной точкой для изучения основных приемов является http://www.frayn.net/beowulf/theory.html Обширную коллекцию материалов и ссылок, которые можно найти здесь: http: // chessprogramming .wikispaces.com / И третье: учиться на чужом коде. Посмотрите на источники Crafty . Это ведущий движок с открытым исходным кодом. Очень важно подумать о тестовых случаях, чтобы увидеть, вносите ли вы улучшения: начните, например, с нескольких простых простых позиций в конце игры с 3 или 4 цифрами.

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

Если это просто забавное упражнение, вы можете закодировать его в Javascript и развернуть как веб-страницу. Если вы никогда не захотите превратить его в опытную шахматную игру, по крайней мере, другие смогут поиграть с ней и ее исходным кодом.

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

Если вы хотите ориентироваться на устройства Android, то Java будет хорошим выбором. Аналогично, Objective-C для iOS-устройств.

Короче говоря, выбор языка не существует в вакууме.

Я предполагаю, что вы уже знаете о концепции Min-Max, деревьях и обрезках, эвристических и других основах, и то, что я пишу здесь, это лишь некоторые детали, которые могли быть недооценены.

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

Поскольку мы оба были программистами Java, наш язык превратился в Java, и мы начали с объектно-ориентированного подхода. Части были объектами, доска была объектом, файлы и ранги (строки и столбцы в шахматной литературе) были объектами. И это было неправильно. Затраты были огромными, и программа изо всех сил пыталась пройти дальше, чем 2 шага (4 слоя) в дереве поиска.

Таким образом, после некоторого поиска мы получили блестящую идею (но не нашу!): Представлять фигуры и доску в виде длинных целых чисел (64 бита). Это имеет смысл, потому что шахматная доска имеет 64 квадрата. Остальные были немного мудрыми операциями (работающими очень близко к процессору = очень быстро). Например, рассмотрим двоичное 64-битное целое число, в котором те представляют квадраты на доске, на которые ваша фигура может атаковать. Теперь, если вы выполнили логическое «И» между двумя числами, как это, ненулевой результат означает, что у вас есть квадрат с атакующими. Есть несколько способов сделать шахматную доску и фигуры, поэтому:

1 - Определитесь с вашей презентацией на доске

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

2 - Найди себе вводную книгу.

Мы сделали это, но все же мы были далеко не хороши:

3 - Хороший шахматный движок должен видеть впереди 6 ходов (12 сгибов).

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

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

И все же мы были далеко от 12 слоев. Путем дополнительного изучения мы обнаружим некоторые хитрости! Например, было предложено пропустить один слой дерева и начать со следующего (как будто нет противника). Идея состоит в том, что если ход крайне идиотский, то зачем тратить время и смотреть, как противники реагируют на этот ход. Тем не менее, один хороший двигатель должен уметь различать идиотский ход и гениальную жертву королевы.

5 - Изучите приемы программирования для этой конкретной задачи (шахматы).

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

6 - Сохраните данные, которые вы генерируете ... Эффективно!

и наконец:

7 - Код с максимальной оптимизацией.

Эта проблема чрезвычайно дорогая как в процессоре, так и в памяти. Очень важно писать свой код очень эффективно. Помните, что мы говорим о факторе ветвления 35. Это означает, что бесполезное «если» где-то в вашей эвристике может быть превращено в 3.3792205e+18бесполезное «если» где-то глубоко в вашем дереве поиска.

Шахматное программирование - очень очень интересная задача, и это время, когда вы можете подвергнуть свои возможности программирования серьезному испытанию. Есть еще несколько моментов, которые я могу предложить, но я уверен, что вы сами их обнаружите. Есть еще много моментов, которые я не знаю, но вы можете найти их в Интернете!

Удачи и приятного времяпровождения!

PS Я не очень хорошо знаю javascript, но кое-что говорит мне о сложности проблемы, может быть, учитывая все, что может предложить C ++, было бы лучше отказаться от javascript и сделать это на C ++.

Согласно вашему редактированию, вы находитесь на стадии определения «законных» ходов.

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

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

После того, как вы достаточно подробно рассмотрели законные и недопустимые ходы для каждой фигуры, я бы начал добавлять проверки для других переменных (например, перемещать короля в условия «проверки» и «мат»).

Я рекомендую qunit для модульных тестов и jasmine для поведенческих тестов в JavaScript.

Я на самом деле написал шахматный движок. Приготовьтесь к удовольствию и кошмару. Когда мы с друзьями сделали это, это было на соревновании по программированию, и языком, на котором мы решили пойти, была Java. Я чувствую, что Java или C - ваш лучший выбор, но я вижу, что вы решили использовать Javascript. Я не могу по-настоящему сбить его с толку, потому что я незнаком с ним.

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

Удачи

Для части, связанной с принятием компьютерных решений игроком, я не могу рекомендовать книгу «Искусственный интеллект: современный подход» (книжный веб-сайт). http://aima.cs.berkeley.edu/ ). В зависимости от вашего уровня знаний по математике (теория графов помогает) это может быть немного высокий уровень, но он написан так же просто, как этот академический материал, и он содержит очень современный обзор (и некоторую глубину) методов для заставить программы решать вещи.

Он укажет вам такие вещи, как постановка цели (т. Е. Checkmate или null), оценка того, насколько близко конкретное состояние (макет платы) к этой цели, как генерировать различные возможные следующие состояния, начиная с текущего, и как пройти то, что является огромным проблемным пространством.

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

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

Вы можете пойти действительно так, как вы хотите, но это мои мысли на эту тему:

Я бы использовал Java, поскольку это позволяет вам быть очень высокого уровня и иметь в своем распоряжении библиотеки пользовательского интерфейса (AWT, Swing). Вы можете использовать объектно-ориентированный подход к моделированию шахматной доски и фигур. Другие объекты могут заменить историю перемещений и оценки. Даже игроки могут быть объектами, и тогда вы можете в будущем расширить свойPlayer класс, чтобы предоставить искусственного интеллектуального компьютерного игрока.

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

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

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

Теперь, если вы хотите создать ИИ для игры в шахматы, который возьмет на себя роль одного из игроков, то тут все становится сложнее. Но опять же, выбор языка здесь не самая большая проблема; понимание принципов AI является Это будет гораздо более важным фактором.

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