Шахматы программирования, и такие

Еще одна история из моей дней колледжа. Будьте осторожны, длинные статьи.

Инженерные колледжей в штате Керала требуют, чтобы студенты представить мини-проект в третий год своей компьютерной науки и техники курсы. Это в дополнение к основной проект, который должен быть представлен в прошлом году курса.

Двое из моих одноклассников - Praveen Kumar (который в наших кругах считается равным Джон Скит ), Филипп и я сформировали нашу команду для этого мини-проекта. Мы были очень рады, об этом проекте, который мы начали обсуждение об этом намного раньше, чем официальное время начала проекта. После долгих дебатов поздно ночью, мы решили разработать программу шахматы.

Трое из нас делились арендовали дом у колледжа, и мы использовали для разработки программного обеспечения коммунальные услуги для различных целей, ^{№ 1.} Основной момент здесь в том, что мы разработали эти программы - вдумайтесь - Visual Basic 6.

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

Тестирование программы несколько сложнее. Альфа-бета алгоритм планирования был в рабочем состоянии и программы создания и принятия некоторые основные шаги, но мы столкнулись две проблемы:

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

Самые лучшие шахматисты могут просто взглянуть на шахматы позицию и посмотреть, 2-3 линии игры, который они должны анализировать, а не анализировать все 30 + возможных ходов. Компьютеры не могут этого делать. Компьютеры должны смотреть на все ходы, чтобы решить, следует ли анализировать эти линии играть более глубины или нет. Люди хорошо в шахматы стратегии в то время как компьютеры хороши в тактике. Это означает, что человек не может определить, является ли компьютер играет идеальную игру (для любой заданной глубине) или нет.

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

Хороший способ проверить программу Шахматы чтобы сделать его играет сам с собой ^{# 2.} Поэтому мы хотели бы код до поздней ночи, и по утрам, когда мы идем в колледж, мы хотели бы начать программу и сделать ее играет сам с собой. Когда мы вернулись бы взглянуть на журналы и посмотрите, что произошло. Как бы мы были возбужденные, результаты зачастую удручающей. Большую часть времени игра будет идти в цикл, где каждый игрок играет (туда и обратно) те же движения . Причина в том, что когда-то шахматы И. ^{# 3} нашли лучший ход для конкретной позиции борту, он просто играет двигаться считаясь ни с какими другими фактами, как история. Наилучший способ исправить это, необходимо предписать программу по изучению истории двигаться слишком при принятии решения о том, какие фишка.

Еще одна причина для частых петли, что оба игрока в игре, были той же силы (они оба думали х движется вперед). Для решения этой проблемы и увидеть некоторые реальные результаты, которые мы сделали их различной силы. Один из игроков будет думать х движется вперед, а другие будут думать, х-2 или что-то подобное. Это улучшение помог нам увидеть некоторые реальные результаты. Когда мы вернулись, чтобы проверить результаты в конце концов, мы могли бы увидеть один из игроков, мат!

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

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

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

Вы можете пойти дальше и дальше итеративно все глубже и глубже в это дерево поиска ^{# 4.} Чем глубже вы ищете, тем выше ваши решения (перемещения) будет. Для каждой позиции борту алгоритм будет назначать оценка. Оценка определяет, насколько хорошо борту позиция. Если один из ваших образцов не захватили, вы потеряете много очков. Например, если вы потеряли пешку, вы теряете 1 очко.

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

Например, в первой линии игры, компьютер получает 5 очков в первой шаг (возможно, путем захвата ладья), а в ответной меры противника наносит ответный удар, получив 3 балла (вероятно, захватив епископа / рыцарь). Теперь, как вы помните, алгоритмы смотрит на сумме очков игрока, в конце каждой строки из игры. В обоих указанных выше случаях, общая прибыль с помощью ЭВМ 2 баллов.

Если компьютер выбирает между этими двумя линиями игры случайно, вы находитесь в неприятности. Проблема в том, что компьютер не знает , что произойдет после последнего хода в линии игры. Это означает, что если вы будете следовать первой линии игры вы наверняка получили 2 очков после следующих двух движется в то время как во второй строке игры, вы потеряете 3 очка после 2 следующего хода. Может быть, вы сможете получить 5 баллов позже в игре, но что если еще два движения, когда вы можете более подробно см. в дереве, вы понимаете, что этот шаг вы видели ранее, будет иметь катастрофические последствия? Тогда вам придется изменить свою игру, и это означает, что вы не можете получить эти вопросы.

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

Второй способ заключается в использовании покоя поиска :

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

Мы сделали много изменений в код. Мы привыкли считать печатные версии исходного кода (около 100 страниц) нашего колледжа и попытался найти оптимизации, которые могут быть применены к коду. Шахматы программирования является одной из областей, где более-оптимизации не одобряется.

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

Перевод исходный код

Мы были почти счастливы, как проект должен был, когда он ударил нас - колледж положил ограничение, что все проекты должны быть сделано с помощью Java. Нам пришлось порт приложения Java в ближайшее время.

Переписав все приложения с нуля, казалось много времени и лишиться мотивации. Нам нужен более быстрый способ. Что о преобразовании источника VB6 исходного кода в код Java автоматически? Конечно, для этой работы мы должны были бы написать В.Б., чтобы переводчик языка Java. Это казалось слишком трудным учетом быстро приближается крайний срок для представления проекта. Мы загрузили некоторые программы код перевода из Интернета, и попытался их, но ни один из них, казалось, работает отлично. Преобразование сложный пользовательский интерфейс с VB6 изрядное количество пользовательских анимации Java практически невозможно даже для передовых переводчик.

Потом у нас была идея. Regex!

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

В случае каких-либо достойных шахмат программы Есть две основные части: двигатель шахматы и модуль интерфейса. Шахматы двигателя не весь комплекс расчетов - записи пользователь перемещает, узнав ли двигаться является действительным или нет, думая о том лучший ход для компьютера и т.д. отображает пользовательский интерфейс модуля шахматной доске для пользователя и позволяет пользователю делать перемещать с помощью мыши. Теперь, как вы, возможно, уже установлены, часть пользовательского интерфейса не очень переводимых между VB6 и Java. Мы решили разработать интерфейс с нуля в Java.

Самое интересное шахматный движок, что она содержит много-много расчетов, условий и петли, которые помогают это сделать умный ход. Я, вероятно, следует отметить, что шахматный движок не может считаться умными, как таковой. Шахматный движок хрустит миллионы число очень быстро, и узнает, лучше двигаться на компьютере можно было сделать против игрока-человека. Движения могут выглядеть умно человека игрока, но шахматный движок не может рассматриваться в качестве примера двигатель АИ. Это всего лишь несколько Кранчер под ее слоев. Во всяком случае то, что у нас сотни страниц код, который состоял исключительно из алгоритмов, которые помогали в компьютер играет лучше играть в шахматы.

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

1. Заменено:

  Если с, если ( 

  За то для ( 

  Затем с ( 

  Остальное с) (другое 

  Конец если, Next, End Function и т.д. с) 

  Правда с истинным 

  False ложными 

 А с и и 

  Или с | | 

  Моделирование с% 

  Для выхода с перерывом; 

  = В условных П ри == 

и т.д.

2. Добавлено; (точка с запятой) в конце строк, которые не начинаются с любой из вышеупомянутых ключевых слов.

3. Изменен код массива ссылок. in Java code. Что-то вроде Board(x,y) в VB6 код стал board[x][y] в коде Java.

4. Существовали некоторые сложные условные операторы в коде В.Б., что мы думали, было бы невозможно преобразовать в Java использованием Regex. Мы должны были преобразовать эти вручную.

5. Преобразованный цикл заявления виде

For i = 0 To NumMoves - 1 to

for(int i = 0; i < numMoves-1; i++){

6. Объявления переменных вида

Dim index As Integer to

int index = 0;

Существовал еще такого рода.

Конечно, это было не все вещи Regex. Невозможно, чтобы это право с Regex в одиночку. Программа малых мы писали перевод код читать каждую строку кода, В. Б. отдельно и превратили его в Java, главным образом с использованием Regex. Весь перевод (Regex замены) было сделано в несколько проходов. Мы никогда не осуществляются полномасштабные переводчик или языка анализатора.

Даже после того, весь этот цирк Regex перевода не была завершена. Пришлось читать на протяжении большей части кода и изменить много вещей, чтобы получить это работает правильно. Есть много различий между Языки (например, массив индексов начали 0 в Java и 1 в VB6), а также необходимо заботиться. Он сделал нас немного усилий, чтобы получить подробную правильно, но, наконец, мы завершили преобразование кода Java с гораздо меньшими усилиями, чем полностью переписав его.

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

^{# 1} Подробнее об этом чуть позже. Напомните мне, если я не забыл. Я обещаю, что это изменит жизни многих студентов.

^{# 2} Еще один хороший способ является сталкивание его с лучшей двигателей в шахматы.

^{# 3} я включил слово "AI" там просто, чтобы я мог написать эту заметку. Шахматы играть алгоритм не может рассматриваться в области искусственного интеллекта. Компьютерные шахматы хруст проблемой номер. Реализация алгоритмов в наиболее эффективным способом является лучшим способом, чтобы получить хорошие результаты. Существует никаких сведений участие (по сравнению с реальной методов, таких как А. И. нейронных сетей).

^{# 4} она ограничена вычислительной мощности у вас есть. В среднем количество действительных движется у вас есть для каждого шахматный ход около 30. Если вы собираетесь искать 8 ходов вперед, вам придется искать через 30 ^ 8 узлов, что является очень большое число.