Какие структуры данных вы бы использовали для представления шахматной доски для компьютерной шахматной программы?
задан 02 сен ’08, 14:09
14 ответы
Первоначально используйте Целочисленный массив 8 * 8 изображать шахматную доску.
Вы можете начать программировать, используя эту нотацию. Дайте баллы за части. Например:
**White** 9 = white queen 5 = white rook 3 = bishop 3 = knight 1 = pawn **black** -9 = white queen -5 = white rook -3 = bishop -3 = knight -1 = pawn White King: very large positive number Black King: very large negative number
и т. д. (Обратите внимание, что приведенные выше точки являются приблизительными значениями торговой силы каждой шахматной фигуры)
После того, как вы разработаете базовые основы своего приложения и четко поймете работу используемых алгоритмов, попробуйте улучшить производительность с помощью битовых плат.
В битовых платах вы используете восемь 8-битных слов для представления плат. Это представление нуждается в доске для каждой шахматной фигуры. На одной битовой доске вы будете хранить позицию ладьи, а на другой — позицию коня. и т.д.
Шахматный движок С++ #0
Битовые платы могут значительно повысить производительность вашего приложения, потому что манипулировать частями с помощью битовых плат очень просто и быстро.
Как вы отметили,
Большинство современных шахматных программ, особенно те, которые работают на 64-битном процессоре, используют растровый подход для представления шахматной доски и генерации ходов. x88 — это альтернативная модель платы для машин без 64-битных процессоров.
Как отличить слона от коня, если они оба представлены целым числом 3? — постфутурист
Нет, они не представлены цифрой 3. Это их материальная ценность (и слон, и конь стоят примерно по 3 пешки). — Филипп Класен
Для серьезного шахматного движка использование битовых досок является эффективным способом представления шахматной доски в памяти. Битовые доски быстрее, чем любое представление на основе массива, особенно в 64-битных архитектурах, где битовая доска может поместиться в один регистр ЦП.
Битборды
Основная идея битовых досок состоит в том, чтобы представить каждый тип шахматной фигуры в 64 битах. В С++/С# это будет ulong/UInt64 . Таким образом, вы будете поддерживать 12 UInt64 переменные для представления вашей шахматной доски: две (одна черная и одна белая) для каждого типа фигуры, а именно: пешка, ладья, конь, слон, ферзь и король. Каждый бит в UInt64 будет соответствовать квадрату на шахматной доске. Как правило, младший значащий бит будет квадратом a1, следующим b1, затем c1 и так далее в порядке возрастания строк. Бит, соответствующий расположению фигуры на шахматной доске, будет установлен в 1, все остальные будут установлены в 0. Например, если у вас есть две белые ладьи на a2 и h1, то битборд белых ладей будет выглядеть так:
0000000000000000000000000000000000000000000000000000000110000000
Теперь, например, если вы хотите переместить свою ладью с a2 на g2 в приведенном выше примере, все, что вам нужно сделать, это XOR вашего битборда:
Программирование на Python. Шахматы. Урок 1
0000000000000000000000000000000000000000000000000100000100000000
Bitboards имеют преимущество в производительности, когда речь идет о генерации перемещений. Существуют и другие преимущества производительности, которые естественным образом вытекают из представления битовых досок. Например, вы можете использовать незащищенные хеш-таблицы которые являются огромным преимуществом при распараллеливании алгоритма поиска.
Дальнейшее чтение
Конечным ресурсом для разработки шахматного движка является Вики по программированию шахмат. Я недавно написал этот шахматный движок который реализует битборды на C#. Еще лучший шахматный движок с открытым исходным кодом СтокРыба который также реализует битовые доски, но на C++.
ответ дан 20 дек ’13, 21:12
Источник: stackovergo.com
Программирование игры в шахматы
Одним из моих хобби является разработка программы для игры в шахматы. Я назвала мою программу в свою честь «Марией». День рождения моей «Марии» — 21 марта 1996 г. В настоящее время «Мария» играет достаточно сильно, однако до гроссмейстерского уровня ей еще далеко.
В этой теме хочу обсудить алгоритмы, используемые в шахматных программах. Могу поделиться своими идеями как об уже реализованных алгоритмах, так и о тех, которые я собираюсь реализовать в ближайшее время.
В начале немного об особенностях моей программы. «Мария» написана на современном Фортране (Compaq Visual Fortran). Фортран был самым распространенным языком программирования в эпоху моей молодости (восьмидесятые годы прошлого столетия).
В настоящее время этот язык используется почти исключительно в научных учреждениях, профессиональная деятельность которых связана с физикой и астрономией, в частности, в Пулковской обсерватории (Санкт-Петербург). Фортран является моим любимым языком программирования. Можно сказать, что я — «фанатка» Фортрана. Современный Фортран продолжает активно развиваться и в настоящее время обладает всеми возможностями структурного и объектно-ориентированного программирования. Кроме того, по сравнению с C/C++ в Фортране имеются дополнительные удобства, а именно:
1) значительно более простой синтаксис;
2) исключительно высокая точность математических вычислений (до 10 в минус 25-й степени);
3) наличие умолчаний о типах переменных;
4) возможность нумерации индексов массива с любого числа, в том числе с отрицательного (а не только с нуля или с единицы);
5) возможность свободного вызова подпрограмм и функций независимо от того, выше или ниже текста подпрограммы расположен оператор ее вызова;
6) богатые возможности конструкции выбора (в частности, возможность использования в одной ветви нескольких значений критериального выражения и/или их интервалов);
7) отсутствие необходимости подключения внешних файлов для реализации операций ввода/вывода, использования математических функций и т. д.
Описание алгоритмов моей программы буду вести большей частью в словесной формулировке. В отдельных случаях буду приводить код на Фортране.
С уважением, Мария Константиновна Фёдорова.
- Мария Константиновна
- Пользователь
#1
21:21, 5 дек 2015
Позицию я представляю как одномерный массив целых чисел с индексами от 11 до 88. Цифра десятков индекса соответствует букве горизонтали (точнее, ее порядковому номеру в латинском алфавите), а цифра единиц — цифре вертикали поля (в частности, полю e2 соответствует индекс 52). Значение каждого элемента массива соответствует фигуре, стоящей на соответствующем поле, а именно:
1) ноль соответствует свободному полю;
2) положительное число соответствует белой фигуре, а отрицательное — черной;
3) абсолютная величина числа соответствует виду фигуры, а именно:
1-пешка, 2-король, 3-конь, 4-слон, 5-ладья, 6-ферзь
(такая кодировка соответствует количеству очков, выпавшему на кости, бросаемой при игре в древнюю «чатурангу»: игрок должен был ходить соответствующей фигурой согласно результату броска кости).
Правда, при таком способе представления позиции массив позиции содержит 14 лишних элементов с индексами, последняя цифра которых — девятка или ноль (19, 20, 29, 30, . 79, 80). Все они заполняются нулями. «Поля» с девятками как бы находятся за пределами доски с верхней стороны, а с нулями — с нижней. Для отсечения возможностей ходов фигур на подобные поля я использую логическую функцию InBoard, которая принимает значение истина тогда и только тогда, когда обе цифры аргумента находятся в пределах от единицы до восьми: тогда и только тогда поле с соответствующим индексом будет находиться на доске.
Список возможных ходов одной из сторон в некоторой позиции (подпрограмма MoveList) строится следующим образом:
1. Описывается четыре одномерных целочисленных массива именованных констант, соответствующих лучам коня и дальнобойных фигур и характеризующих изменение номеров полей при ходах соответствующих фигур (для дальнобойных фигур — при самых коротких ходах):
Knight (8) = (/-21, -19, -12, -8, 8, 12, 19, 21/),
Rook (4) = (/-10, — 1, 1, 10 /), Шахматы и математика» (М., «Наука», 1983), именно таково максимальное количество возможных ходов одной стороны в позиции):
1)Move (целочисленный) — массив четырехзначных кодов ходов (первые две цифры соответствуют коду исходного поля фигуры, вторые — конечного). В частности, ходу e2-e4 соответствует код 5254. Начальные значение всех элементов массива равны нулю.
2)Attribute (целочисленный) — массив атрибутов ходов, значения которых характеризуют особенности соответствующего хода:
0 — обычный ход; 1 — взятие на проходе; 2 — превращение пешки; 3 — короткая рокировка; 4 — длинная рокировка. Начальные значения — нули.
3)Capture (логический) — значение равно True для взятий и False для тихих ходов (начальные значения — False).
4)Agressor (целочисленный) — содержит абсолютные значения кодов фигур, которые совершают соответствующий ход (начальные значения — 0).
5)Victime (целочисленный) — для взятий содержит абсолютные значения кодов забираемых фигур, для тихих ходов — нули (начальные значения — 0).
Последние два массива были добавлены недавно для обеспечения последующей сортировки взятий и тихих ходов по алгоритму «Наиболее ценная жертва — наименее ценный нападающий».
3. Начальное значение счетчика количества ходов (скалярная целочисленная переменная N) устанавливается равным нулю.
4. Организуется цикл с параметром — номером поля, изменяющимся от 11 до 88.
5. Если поле расположено на доске и занято своей фигурой (произведение кода поля и значения цвета (+1 — белые, -1 — черные) положительно), то организуется выбор согласно коду поля:
а) Исследуем поле перед пешкой (индекс данного поля равен сумме индекса поля, на котором стоит пешка, и значения цвета — легко убедиться, что для белых это будет поле, расположенное непосредственно выше пешки, а для черных — ниже). Если оно свободно (код 0), то связываем поле, на котором стоит пешка, и поле перед ней ходом (вызываем подпрограмму, которая записывает в массив Move код данного хода и увеличивает на единицу счетчик количества возможных ходов. В массив Agressor записываем единицу: «агрессором» является пешка, т. е. фигура с кодом 1.
Если при этом номер горизонтали конечного поля (остаток от деления его номера на 10) равен 8 для белых или 1 для черных (т. е. номер горизонтали конечного поля равен целой части суммы числа 4,5 и значения цвета, умноженного на 3,5), то ход пешки сопровождается ее превращением — значение соответствующего элемента массива атрибутов устанавливаем равным двум. Если же номер горизонтали начального поля равен двум для белых или семи для черных — еще раз увеличиваем номер конечного поля на значение цвета. Если новое конечное поле свободно — возможен ход пешки с исходной позиции на два поля. Записываем его код в массив Move и увеличиваем счетчик количества ходов. В массив агрессоров записываем единицу.
б) Если номер вертикали отличен от единицы (пешка стоит не на вертикали «a»), то вычитаем 10 из индекса начального поля и затем прибавляем значение цвета. Результат присваиваем индексу конечного поля. Если оно занято фигурой соперника (произведение кода поля на значение цвета отрицательно) — возможно взятие.
В массив Move записываем код хода, в массив Capture — истину, в массив Agressor — единицу, в массив Victime — абсолютную величину кода забираемой фигуры. Аналогично поступаем при номере вертикали, отличном от восьми (т. е. от «h») (на этот раз для получения индекса конечного поля прибавляем 10 к индексу начального поля и затем прибавляем значение цвета). В обоих случаях, если забираемая фигура стоит на восьмой (первой) горизонтали, атрибут хода равен двум.
в) И, наконец, взятие на проходе: с этой целью в программе организована глобальная целочисленная переменная Last, помещенная в общую область Common. Значение этой переменной равно коду последнего сделанного хода и обновляется всякий раз, когда человек или компьютер делает ход.
Если выполнена конъюнкция трех условий:
1) на поле, индекс которого равен числу, образованному двумя последними цифрами текущего значения Last, стоит пешка соперника (т. е. значение поля равно -Color);
2) разность между начальным и конечным полями хода Last равно удвоенному значению цвета (это значит, что белая пешка увеличила на два значение своего поля или черная уменьшила, т. е. пешка сделала двойной шаг; не следует забывать, что значение цвета Color по сравнению с предшествующим ходом было заменено на противоположное);
3) абсолютная величина разности поля, на котором стоит наша пешка, и конечного поля Last, равна десяти (т. е. наша пешка стоит рядом (по горизонтали) с только что сделавшей ход на два поля пешкой соперника),
то возможно взятие на проходе. Соединяем ходом поле, на котором стоит наша пешка, и увеличенное на значение цвета поле, на котором стоит пешка соперника. Взятие — true, атрибут — единица, агрессор и жертва — единицы.
а) Организуем цикл с параметром Direction, изменяющимся от одного до восьми. Для каждого из восьми направлений, характеризующимися элементами массива Queen с индексом Direction, запускаем подпрограмму KingKnight, определяющую ходы недальнобойных фигур — короля и коня. Использование массива Queen связано с тем, что направления лучей короля совпадает с направлениями лучей ферзя, с той разницей, что король не обладает дальнобойностью.
б) Если белый король стоит на e1, а черный на e8 (это определяется следующим условным оператором:
IF (Field .EQ. INT (54.5 — 3.5 * Color))
,то вызываем подпрограмму, определяющую рокировки. Для возможности короткой рокировки (с учетом уже проверенного условия) необходимо и достаточно, чтобы поля, индексы которых на 10 и 20 больше индекса поля, на котором стоит король, были свободны, а на поле с индексом, на 30 больше королевского, стояла наша ладья (код — 5 * Color).
Если эти условия выполнены, то соединяем ходом поле, на котором стоит король, и поле с индексом, на 20 большим. Атрибут — 3, агрессор — 2 (рокировка считается ходом короля). Аналогично исследуем возможность длинной рокировки (атрибут — 4). Отсутствие права на рокировку (король или соответствующая ладья уже ходили) и невозможность сделать рокировку в связи с тем, что королю объявлен шах, или он после рокировки попадает под шах, или должен пройти через битое поле, на данном этапе не учитывается — иначе возникнет бесконечная рекурсия. Отсечение нелегальных рокировок в моей программе осуществляется на более позднем этапе.
Для каждого из восьми направлений массива Knight вызываем подпрограмму KingKnight.
Старая версия подпрограммы KingKnight (без использования массивов агрессоров и жертв) очень красива. Хочу полностью привести ее код.
SUBROUTINE KingKnight (Position, Color, N, Field, Direction, Move, Capture)
INTEGER Position (11 : 88), Color, Field, Feld, Figure, Direction
LOGICAL InBoard
PARAMETER (MaxMoves = 109)
INTEGER, DIMENSION (MaxMoves) :: Move
LOGICAL, DIMENSION (MaxMoves) :: Capture
Feld = Field + Direction
IF (.NOT. InBoard (Feld)) RETURN
Figure = Position (Feld) * Color
IF (Figure) 1, 2, 3
1 Capture (N + 1) = .TRUE.
2 CALL Bind (Field, Feld, N, Move)
3 RETURN
END SUBROUTINE KingKnight
- Мария Константиновна
- Пользователь
#2
21:21, 5 дек 2015
Индекс конечного поля равен сумме индексов исходного поля и направления. Если конечное поле за пределами доски — хода нет. Сразу возвращаемся в вызвавшую подпрограмму. В противном случае определяем код фигуры, стоящей на конечном поле, и умножаем этот код на значение цвета. Если произведение отрицательно, то на конечном поле стоит чужая фигура.
Возможно взятие — записываем истину в массив Capture, связываем исходное и конечное поля ходом и возвращаемся. Если конечное поле свободно (произведение равно нулю) — возможен тихий ход. Связываем поля ходом и возвращаемся. Если на конечном поле стоит своя фигура (произведение положительно) — нет ни хода, ни взятия. Сразу возвращаемся.
После добавления агрессоров и жертв операторы с метками 1,2,3 уже не следуют непосредственно друг за другом — при неположительном значении переменной Figure необходимо выполнить несколько дополнительных действий.
4 (слон), 5 (ладья), 6 (ферзь)
Для каждого направления, соответствующего лучам данной фигуры, запускаем подпрограмму LongRange, определяющего ходы дальнобойных фигур. Без агрессоров и жертв код подпрограммы выглядит следующим образом:
SUBROUTINE LongRange (Position, Color, N, Field, Direction, Move, Capture)
INTEGER Position (11 : 88), Color, Field, Feld, Figure, Direction
LOGICAL InBoard
PARAMETER (MaxMoves = 109)
INTEGER, DIMENSION (MaxMoves) :: Move
LOGICAL, DIMENSION (MaxMoves) :: Capture
DO 4, Length = 1, 7
Feld = Field + Direction * Length
IF (.NOT. InBoard (Feld)) RETURN
Figure = Position (Feld) * Color
IF (Figure) 1, 3, 2
1 CALL Bind (Field, Feld, N, Move)
Capture (N) = .TRUE.
2 RETURN
3 CALL Bind (Field, Feld, N, Move)
4 END DO
RETURN
END SUBROUTINE LongRange
Длина хода дальнобойной фигуры по каждому направлению может варьироваться от единицы до семи. Организуем цикл по длине. Начинаем с единицы. Прибавляем к индексу исходного поля величину луча, умноженную на длину. Ушли за пределы доски — ходов по данному лучу больше нет.
Иначе определяем фигуру, стоящую на конечном поле. Поле занято чужой фигурой — возможно взятие, но дальнейших ходов по лучу нет. Поле занято своей фигурой — ни на данное, ни на дальнейшие поля ходов больше нет. Поле свободно — возможен тихий ход, и необходимо исследовать дальнейшие поля.
С уважением, Мария Константиновна Фёдорова.
#3
21:40, 5 дек 2015
вам к этому пользователю, он знает о шахматах всё, даже ММО шахматы сделал : )
Источник: gamedev.ru
Как разработать интерфейс к игре типа шахмат?
Хочу написать на С++ игру типа шахмат таким образом, чтобы можно было нажимать на фигуру на доске и после этого ходить ею. К сожалению, из графических библиотек знаком только с graphics.h, однако в ней ничего подобного не наблюдалось. Подскажите, как возможно такое реализовать (желательно чтобы работало под DevCpp или Code Blocks).
Отслеживать
852 5 5 серебряных знаков 19 19 бронзовых знаков
задан 7 апр 2015 в 18:05
214 2 2 серебряных знака 9 9 бронзовых знаков
Не понимаю людей которые минусуют вопрос и даже не пытаются аргументировать что им не нравится .
7 апр 2015 в 18:08
Мне кажется, в игре типа шахмат алгоритм во много раз сложнее кода, нужного для отображения. Начните с него.
7 апр 2015 в 18:27
Действительно, в graphics.h нет функции «нажать на фигуру на доске и после этого ходить». Шутка у нас на работе была, когда парень не смог решить дифф. уравнение в MathLab’e и спросил: «Где тут кнопка «решить дифф. уравнение»?»
7 апр 2015 в 18:28
7 апр 2015 в 18:29
7 апр 2015 в 18:31
4 ответа 4
Сортировка: Сброс на вариант по умолчанию
Несмотря на то, что ваш вопрос очень простой, дать на него ответ нелегко. Дело в том, что он слишком общий. Непонятно, каким вы видите свой интерфейс, как планируете выводить рисунки на экран, как будете развивать программу, какой у вас опыт программирования.
Вашу задачу можно довольно легко решить при помощи какой-либо из распространённых библиотек для создания графических интерфейсов. Если вы хотите использовать C++, то можете взять wxWidgets, Qt (очень мощный фреймворк, но чуть сложнее компилировать программу в сторонних IDE), Gtk. Все они умеют выводить изображения на экран (в том числе и сохранённые в форматах PNG, JPEG и т. д.), обрабатывать щелчки мышью. По ним много документации в том числе и на русском.
Также, если установите стороннее ПО, то сможете нарисовать графический интерфейс мышью, а программа сама сгенерирует нужный код.
Если вы пишете программу, чтобы попрактиковаться так как интересуетесь разработкой игр, то вам, возможно, будет полезно изучить библиотеку OpenGL (или DirectX, хотя их возможности практически равны).
И так далее. Библиотек огромное количество. Если уточните критерии, то мы сможем подобрать что-то вам по душе.
Источник: ru.stackoverflow.com